Distributed computing

SCHEDULING APPROACHES

• Cyclic executive – Divide processor time into endlessly repeating cycles where each cycle is some fixed length, say 1 second. During a cycle some periodic tasks may occur several times, others only once. Gaps allow sporadic tasks to enter.
• Rate-monotonic – Give tasks priority based on the frequency with which they are requested.
• Earliest-deadline first – Give the highest priority to the task with the earliest deadline.

CYCLIC EXECUTIVE STRATEGY

• A cycle design containing sub-intervals of different lengths. During a sub-interval, either a periodic task runs or a gap is permitted for sporadic tasks to run.
• Note the task T1 runs three times during each cycle. In general, different periodic tasks may have to run with different frequencies.

• Gap

• Gap

• T1

• T2

• T1

• T4

• T3

• Gap

• T1

Earliest Deadline First

• Algorithm is the title. Execute the task with the earliest deadline.
• Theorem: if any scheduler can schedule all tasks by their deadlines, then earliest deadline first can do so.
• How might you prove this?

Earliest Deadline First

• Suppose that an optimal scheduler does task t1 before t2 even though both tasks are in the system and t2 has an earlier deadline than t1. Both complete by their deadlines.
• Earliest deadline first would do t2 first, so clearly t2 finishes even earlier. But now t1 finishes when t2 would have. This was early enough for t2 and hence for t1.

Earliest Deadline First -- overload issue

• What happens on overload (i.e. not enough time to finish everything)?
• Change the model: firm real time. Get value if you finish a task by its deadline but lose nothing if you don’t.