# 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

## Recently Viewed Presentations

• "Microsoft will cram between 150 and 220 shipping containers filled with data center gear into a new 500,000 square foot Chicago facility. This move marks the most significant, public use of the shipping container systems popularized by the likes of...
• Broad range of issues; service models, time, pressure, managing risk, limited resources, staff turnover, policies that don't work, programs that don't work, issues that affect Aboriginal families, outside their role/function or too big for them. Factors that Affect Service Receiving
• "ADM is a systematic approach to the mental processes used by pilots to consistently determine the best course of action in response to a given set of circumstances." (FAA PHAK) AOPA - " The goal of ADM is simple: doing...
• Module Views Module View Looks Like Ordinary Module Module Component API Oracle Designer creates the view for you, when you tell it to. Use MCAPI. Creates DDL for the view The Underlying View The View Based Form Querying Inserting New...
• Track 1: Skills. Image and signal processing. Analog/digital network analysis. Software/hardware programming. Circuit Design. Data acquisition. Computational analysis of data in regard to living systems
• Introduction. Lesson objectives: Identify types of material handling equipment. Describe hazards associated with material handling activities. Identify methods to prevent hazards associated with material handling equipment.
• The USB port is a standard port type used to connect many kinds of devices. An advantage of USB devices is that they are hot-swappable. That means they can be plugged in and unplugged without turning off the computer. A...
• Probit model. The selection decision regarding whether to organize the process internally or to subcontract the work. Structural cost equations of the model. Estimate internal organization costs to correct for selectivity using an index constructed from the first-stage results.