Distributed computing

RATE MONOTONIC ASSIGNMENT

• Rate monotonic would say that T1 should get highest priority (because its period is smallest and rate is highest), then T2, then T3.
• Assume that all tasks are perfectly preemptable.
• As the following figure shows, all tasks meet their deadlines. What happens if T3 is given highest priority “because it is the most important”?

• Three tasks:

Task	Period	Compute Time
T1	100	20
T2	150	40
T3	350	100

EXAMPLE OF RATE MONOTONIC SCHEDULING

• Use of rate monotonic scheduler (higher rate gets higher priority) ensures that all tasks complete by their deadlines.
• Notice that T3 completes earlier in its cycle the second time, indicating that the most-difficult-to-meet situation is the very initial one.

• T3
• T2
• T1

• T3 interrupted

• T3 completes first time

• T3 completes earlier

• 0 50 100 150 200 250 300 350 400 450 500

CASE STUDY

• A group is designing a command and control system.
• Interrupts arrive at different rates, however the maximum rate of each interrupt is predictable.
• Computation time of task associated with each interrupt is predictable.
• First implementation uses Ada and a special purpose operating system. The operating system handled interrupts in a round-robin fashion.
• That is, first the OS checked for interrupts for task 1, then task 2, and so on.
• System did not meet its deadlines, yet was grossly underutilized (about 50%).