Scheduling

Scheduling

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

The requests for all tasks for which hard deadlines exist are periodic, with constant interval between requests. Deadlines consist of run-ability constraints only i.e. each task must be completed before the next request for it comes. The tasks are independent in that requests for a certain task do not depend on the initiation or the completion of requests for other tasks. Run-time for each task is constant for that task and does not vary with time. Run-time here refers to the time which is taken by a processor to execute the task without interruption. Any nonperiodic tasks in the system are special; they are initialization or failure-recovery routines; they displace

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

  • Cloud Architecture for Earthquake Science 7th ACES International

    Cloud Architecture for Earthquake Science 7th ACES International

    "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...
  • Do You See What I See? An Exploration

    Do You See What I See? An Exploration

    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
  • Aeronautical Decision Making (ADM)

    Aeronautical Decision Making (ADM)

    "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...
  • Queries and Lookups Simple Department Form The Simple

    Queries and Lookups Simple Department Form The Simple

    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...
  • BMES WELCOME MEETING - University of Texas at Austin

    BMES WELCOME MEETING - University of Texas at Austin

    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
  • Materials Handling Slide Presentation

    Materials Handling Slide Presentation

    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.
  • PowerPoint Presentation to Accompany Chapter 4 Hardware Visualizing

    PowerPoint Presentation to Accompany Chapter 4 Hardware Visualizing

    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...
  • PowerPoint 演示文稿

    PowerPoint 演示文稿

    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.