TUD Logo

TUD Home » ... » Teaching » Real-Time Systems » Scheduling

Operating Systems

Exercise: Scheduling

  1. Given the following precedence graph of four jobs:

    job precedence graph
    where in J e (rd] means:
    J job name
    e execution time
    r release time
    d deadline
    Explain and discuss the scheduling policies EDF, SPT, LPT, LST (MLF), LRT using the example. What follows with respect to EDF if job C has deadline 7 instead of 5?
  2. Determine the appropriate frame sizes for a cyclic schedule for the following systems of periodic preemptible tasks described by (p; e) with p: period, e: execution time.
    1. (6; 1), (10; 2), (18; 2)
    2. (4; 0,5), (5; 1), (10; 2), (24; 9)
  3. A system uses the cyclic EDF algorithm to schedule sporadic jobs. The cyclic schedule of periodic tasks in the system uses a frame size of 5, and a major cycle contains 6 frames. Suppose that the initial amounts of slack time in the frames are 1; 0.5; 0.5; 0.5; 1; and 1. Suppose that a sporadic job S1(23; 1.5) arrives in frame 1, sporadic jobs S2(16; 0.8), S3(20; 0.5), and S4(17; 0.8) arrive in frame 2 (the deadlines of the jobs are relative to the end of their respective frames). In which frame are the accepted jobs scheduled?
  4. Discuss the schedulability of the following systems of periodic tasks according to RMS and EDF. Use appropriate admission criteria.
    1. T = {(8, 3), (9, 2), (18, 3)}
    2. T = {(8, 4), (12, 4), (20, 4)}
    3. T = {(8, 4), (10, 2), (12, 3)}
    4. T = {(3, 1), (6, 2), (18, x)}
  5. Consider a fixed-priority system of 13 periodic, independent tasks with periods

    5, 24, 8, 30, 9, 12, 10, 18, 7, 21, 17, 11, 4.

    The operating system (OS) only supports 4 priority levels. Explain two methods to map the task priorities to OS priorities and describe the mapping of task priorities to OS priorities for the given task set.

  6. Construct the EDR and RMS schedules of the following periodic tasks set and discuss the results. Jobs missing their deadlines should be aborted.

    T = {(4, 1), (9, 3), (12, 7)}

Last modified: 16th Nov 2017, 4.44 PM
Author: Dr.-Ing. Michael Roitzsch

Contact
Dr.-Ing.
Michael Roitzsch

Phone: 463 42043
Fax: 463 38284
e-mail contact form

Regulations
  • ModuleModules: INF-BAS4, INF-VERT4, DSE-E9, INF-LE-EUI
  • Credits6 Credit Points
  • 2/1/0 = 3 SWS
Time and Place
  • Lecture, weekly
    TimeMon, 2.50 PM PlaceAPB E009
  • Exercise, biweekly
    TimeMon, 4.40 PM PlaceAPB E009
Mailing List