Real Time Tasks Scheduling Using Hybrid Genetic Algorithm
The objective of the scheduling soft real-time tasks is to minimize total tardiness and the scheduling these tasks on multiprocessor system is NP-hard problem. In this chapter, scheduling algorithms for soft real-time tasks using genetic algorithm (GA) ar
- PDF / 1,162,222 Bytes
- 32 Pages / 595 x 842 pts (A4) Page_size
- 0 Downloads / 189 Views
2
Graduate School of Information, Production and Systems, Waseda University, Japan, [email protected] Department of Computer Science and Media Engineering, Musashi Institute of Technology, Japan, [email protected]
Summary. The objective of the scheduling soft real-time tasks is to minimize total tardiness and the scheduling these tasks on multiprocessor system is NP-hard problem. In this chapter, scheduling algorithms for soft real-time tasks using genetic algorithm (GA) are introduced. GA has been known to offer significant advantages against conventional heuristics by using simultaneously several search principles and heuristics. The objective of this study is to propose reasonable solutions for NP-hard scheduling problem which much less difficulties than those of traditional mathematical methods. A continuous task scheduling, real-time task scheduling on homogeneous system and real-time task scheduling on heterogeneous system are included in this chapter.
1 Introduction Real-time tasks can be classified to many kinds. Some real-time tasks are invoked repetitively. For example, one may wish to monitor the speed, altitude, and attitude of an aircraft every 100 ms. This sensor information will be used by periodic tasks that control the control surfaces of the aircraft, in order to maintain stability and other desired characteristics. In contrast, there are many other tasks that are aperiodic, that occur only occasionally. A periodic tasks with a bounded interarrival time are called sporadic tasks. Real-time tasks can also be classified according to the consequences of their not being executed on time. Critical (or hard real-time) tasks are those whose timely execution is critical. If deadline are missed, catastrophes occur. Noncritical (or soft real-time) tasks are, as name implies, not critical to the application [1]. For task scheduling, the purpose of general task scheduling is fairness which means that the computer’s resources must be shared out equitably among users. However, the purpose of hard real-time task scheduling is to execute, by the appropriate deadlines, its critical control tasks and the objective of the scheduling soft real-time tasks is to minimize total tardiness [2]. M. Gen and M. Yoo: Real Time Tasks Scheduling Using Hybrid Genetic Algorithm, Studies in Computational Intelligence (SCI) 96, 319–350 (2008) c Springer-Verlag Berlin Heidelberg 2008 www.springerlink.com
320
M. Gen and M. Yoo
There are some traditional scheduling algorithm for hard real-time tasks on uniprocessor, such as rate monotonic (RM) and earliest deadline first (EDF) [3] scheduling algorithm. They guarantee the optimality in somewhat restricted environments. Several derived algorithm from RM, EDF is used for soft real-time tasks. However, these algorithms have some drawbacks in resource utilization and pattern of degradation under the overloaded situation. With the growth of soft real time applications, the necessity of scheduling algorithms for soft real-time tasks is on the increase. Rate regulating proportional shar
Data Loading...
