Presentation - Scheduling Algorithms For Real-time Multiprocessor Systems

Scheduling Algorithms for RealTime Multiprocessor Systems NICK MATHEW

Outline  Multiprocessor Real-Time Systems  Scheduling Algorithms  Multiprocessor Scheduling  P-Fair Scheduling Algorithm

Multiprocessor Real-Time Systems  High computational demands  Telemedicine, Tracking Systems  Traditional Scheduling Assumptions  Single Processor

Scheduling Algorithms  Fixed-Priority Algorithm  Rate Monotonic Scheduling (RMS) Optimal fixed priority algorithm  At least 0.693 system utilization 

 Dynamic Priority Algorithm  Earliest Deadline First (EDF) 

Optimal dynamic-priority algorithm

* Liu & Layland, 1978

Multiprocessor Scheduling "Schedule ji jobs with length li over m processors such that none overlap“

 Traditional Scheduling Algorithms  EDF, RMS – low processor utilization

Multiprocessor Scheduling  Approaches  Partitioning Uniprocessor  Low processor utilization  Bin Packing  NP-hard problem 



Global Scheduling 

Single priority-ordered queue  Low processor utlization

* J. Carpenter, S. Funk, et al [2]

P-Fair Scheduling Algorithm  Proportionate-Fair Scheduling  Global Scheduling Algorithm  Each task executes at uniform rate

* Baruah et al.

P-Fair Scheduling Algorithm  Each task with weight w would receive w.L units of

processor time over interval L

 Each task allocated resource for x.e time units in

each interval

Advantages  Avoids bin-packing problem  Handle dynamic events  task leaving & joining a system

 Optimal

* J. Carpenter, S. Funk, et al [2]

Disadvantages  Degraded processor affinity  Preemption, Migration limit effectiveness

* J. Carpenter, S. Funk, et al [2]

Conclusion  Only known optimal approach (Srinivasan, 2003)  Basis for PD & PF algorithms  Other scheduling algorithms  Genetic Algorithms  Approximation Algorithms  Memetic Algorithms

References [1] K. Ramamritham, J.A. Stankovic, and P.-F. Shiah, "Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems," IEEE Trans. Parallel and Distributed Systems, vol. 1, no. 2, pp. 184194, Apr. 1990. [2] J. Carpenter, S. Funk, et al. A categorization of real-time multiprocessor scheduling problems and algorithms. In J. Y. Leung, editor, Handbook on Scheduling Algorithms, Methods, and Models, page 30.130.19 , 2004. [3] S. Baruah, N. Cohen, C. Plaxton and D. Varvel, "Proportionate Progress: A Notion of Fairness in Resource Allocation", Algorithmica 15(6), pgs. 600-625, 1996.

Questions ?