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

# Exercise: Scheduling

1. Given the following precedence graph of four jobs:

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)}

• Modules: INF-BAS4, INF-VERT4, DSE-E9, INF-LE-EUI
• 6 Credit Points