EFFICIENT COMBINED SCHEDULING OF HARD AND SOFT REAL-TIME TASKS IN MULTIPROCESSOR SYSTEMS UNDER A PROCESSING POWER-SHARE STRATEGY
Abstract
Increasingly, real-time systems are being used in applications that contain tasks that have deadlines and require predictable performance. Many complex real-time applications require modern operating systems capable of scheduling multiple classes of tasks in an integrated way. These applications require scheduling that result in high utilization of available processing power to accommodate as many tasks as possible while satisfying the required deadlines of each task. In this paper, we propose a combined heuristic approach to schedule a set of independent soft and hard real-time tasks in multiprocessor computing systems. Each of these tasks is characterized by its arrival time, deadline and required processing power. The proposed approach distributes the total available processing power of any processor, if it is needed and possible, among more than one task, while ensuring that hard real-time tasks are given higher priority and enough processing power to meet deadlines. This strategy can be used as a tool to efficiently guide scheduling processes. In addition, it can help to optimize processor utilization and maintain higher success ratios by maximizing the schedulability of soft tasks without jeopardizing the schedulability of hard tasks.
References
- A. A. Alhamdan, Scheduling methods for efficient utilization of cluster computing environment, Ph. D. Thesis, Connecticut University, 2003 . Google Scholar
-
H. El-Rewini , T. G. Lewis and H. H. Ali , Task scheduling in parallel and distributed systems ( Prentice Hall , New Jersey , 1994 ) . Google Scholar - IEEE 82, 55 (1994). Crossref, ISI, Google Scholar
- IEEE Trans. Parallel and Distributed Systems 9, 312 (1998), DOI: 10.1109/71.674322. Crossref, ISI, Google Scholar
-
W. S. Liu , Real-time systems ( Pearson Education , Singapore , 2001 ) . Google Scholar H. Kaneko , Integrated scheduling of multimedia and hard real-time tasks, Proc. 17th IEEE Real-Time Systems Symposium (RTSS '96) (1996) pp. 206–217. Google ScholarM. Spuri and G. C. Buttazzo , Efficient aperiodic service under earliest deadline scheduling, Proc. IEEE 15th Real-Time Systems Symposium (1994) pp. 2–11. Google ScholarZ. Deng , J. W. S. Liu and J. Sun , A scheme for scheduling hard real-time applications in open system environment, Proc. 9th Euromico Workshop on Real-Time Systems (1997) pp. 165–175. Google ScholarR. Davis and A. Wellings , Dual priority scheduling, Proc. 16th IEEE Real-Time System Symposium (RTSS '95) (1995) pp. 100–109. Google ScholarJ. P. Lehoczky , L. Sha and J. K. Strosnider , Enhanced aperiodic responsiveness in hard real-time environments, Proc. Real-Time Systems Symposium (1987) pp. 261–270. Google ScholarB. Sprunt , J. Lehoczky and L. Sha , Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm, Proc. 9th IEEE Real-Time Systems Symposium (1988) pp. 251–258. Google ScholarA. Basheer and G. Manimaran , Combined scheduling of hard and soft real-time tasks in multiprocessor systems, Proc. Conf. on High Performance Computing (HiPC) (2003) pp. 279–289. Google ScholarS. Lee , H. Kim and J. Lee , A soft aperiodic task scheduling in dynamic-priority systems, Proc. 2nd Intl. Workshop on Real-Time Computing Systems and applications (RTCSA '95) (1995) pp. 68–74. Google Scholar- IEEE Trans. Comput. 48, 1035 (1999), DOI: 10.1109/12.805154. Crossref, ISI, Google Scholar
- J. Parallel and Distributed Processing Techniques and Applications II, 809 (2002). Google Scholar
S. A. Brandt , Dynamic integrated scheduling of hard real-time, soft real-time and non-real-time processes, Proc. 24th IEEE Intl. Real-Time Systems Symposium (RTSS '03) (2003) pp. 396–407. Google Scholar- J. Systems Architecture 46, 793 (2000), DOI: 10.1016/S1383-7621(99)00039-9. Crossref, ISI, Google Scholar
- J. Real-Time Systems 10, 179 (1996), DOI: 10.1007/BF00360340. Crossref, ISI, Google Scholar
E. Y. Abdel Maksoud and R. A. Ammar , A performance-effective task scheduling algorithm for multiprocessor computing systems, Proc. ISCA 20th Int. Conf. on Parallel and Distributed Computing Systems (PDCS '2007) (2007) pp. 13–18. Google ScholarJ. Regehr and J. A. Stankovic , Augmented CPU reservation: Towards predictable execution on general-purpose operating systems, Proc. 7th IEEE Real-Time Technology and Applications Symposium (RTAS '2001) (2001) pp. 141–148. Google Scholar- IEEE Trans, on Comput. 44, 1443 (1995), DOI: 10.1109/12.477249. Crossref, ISI, Google Scholar
R. I. Davis , K. W. Tindell and A. Burns , Scheduling slack time in fixed priority pre-emptive systems, Proc. 14th IEEE Real-Time System Symposium (1993) pp. 222–231. Google Scholar- SIAM J. Computing 21, 281 (1992), DOI: 10.1137/0221021. Crossref, ISI, Google Scholar


