# Scheduling Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment C.L. Liu and James W. Layland Presented by Pete Perlegos Assumptions

periodic tasks while they themselves are being run, and do not themselves have hard, critical deadlines. 2 Type of Scheduling Algorithms The scheduling algorithms to be studied in this paper are preemptive and priority driven. 3 Critical Instant

A critical instant for a task is defined to be an instant at which a request for that task will have the largest response time. Theorem 1. A critical instant for any task occurs whenever the task is requested simultaneously with requests for all higher priority tasks. 4 Feasible Scheduling

One of the values of this result is that a simple direct calculation can determine whether or not a given priority assignment will yield a feasible scheduling algorithm. Specifically, if the requests for all tasks at their critical instants are fulfilled before their respective deadlines, then the scheduling algorithm is feasible. 5 Feasible Scheduling T1=2,

T2=5 C1=1, C2=1 (a) (T1 higher priority) Feasible (b) (T1 higher priority) C2 can be increased to 2 (c) (T2 higher priority) C1 and C2 can be at most 1 6

Priority Assignment More generally, it seems that a reasonable rule of priority assignment is to assign priorities to tasks according to their request rates, independent if their run-times. Specifically, tasks with higher request rates will have higher priorities. This will be called rate-monotonic priority assignment. Theorem 2. If a feasible priority assignment exists for some task set, the rate-monotonic priority assignment is feasible for that task set.

7 Processor Utilization U= m i= 1 (C /T ) i i

T=request periods 1/T=frequency C=run-time 8 Processor Utilization Theorem 3. For a set of two tasks with fixed priority assignment, the least upper bound

to the processor utilization factor is U=2(2-1). Theorem 4. For a set of m tasks with fixed priority order, and the restriction that the ratio between any two request periods is less than 2, the least upper bound to the processor utilization factor is U=m(21/m-1). Theorem 5. For a set of m tasks with fixed priority order, the least upper bound to the processor utilization factor is U=m(21/m-1). 9 Processor Utilization

For large m, U = ln2 = 0.69 This is not very good. 10 Deadline Driven Scheduling Algorithm Theorem 7. For a given set of m

tasks, the deadline driven scheduling algorithm is feasible if and only if (C1/ T1) + (C2/T2) + + (Cm/Tm) < 1 Total demand cannot exceed the available processor time. 11 Deadline Driven Scheduling Algorithm The deadline driven scheduling algorithm

is optimum in the sense that if a set of tasks can be scheduled by any algorithm, it can be scheduled by the deadline driven scheduling algorithm. 12 Mixed Scheduling Algorithm Implement deadline driven scheduler for the slower paced tasks. Let tasks 1, 2,, k, the k tasks of shortest periods, be scheduled according to the fixed priority rate-monotonic scheduling algorithm, and let the remaining tasks k+1, k+2,, m, be scheduled according to the deadline driven scheduling algorithm

when the processor is not occupied by tasks 1, 2,, k. 13 Comparison Example with 3 tasks T1=3, T2=4, T3=5 C1=1, C2=1, C3=1(rate-monotonic), 2(mixed) Fixed priority rate-monotonic scheduling algorithm: U = 1/3 + 1/4 + 1/5 = 78.3% Mixed scheduling algorithm: U = 1/3 + 1/4 + 2/5 = 98.3% 14

Conclusion A combination of the two scheduling algorithms discussed appears to provide most of the benefits of the deadline driven scheduling algorithm, and yet may be readily implemented without much additional cost beyond a fixed priority assignment. 15