Distributed computing

FIRST DECISION

• Management decided that the problem was Ada.
• Do you think they were right? (Assume that they could have shortened each task by 10% and that the tasks and times are of the three task system given previously.

CASE STUDY – SOLUTIONS

• Switching from Ada probably would not have helped.
• Consider using round-robin for the three task system given before. If task T3 is allowed to run to completion, then it will prevent task T1 from running for 100 time units (or 90 with the time improvement). That is not fast enough.
• Change scheduler to give priority to task with smallest period, but tasks remain non-preemptable.
• Helps, but not enough since the T3-T1 conflict would still prevent T1 from completing.
• Change tasks so longer tasks are preemptable.
• This would solve the problem in combination with rate monotonic priority assignment. (Show this.)
• Motto: Look first at the scheduler.

PRIORITY INVERSION AND PRIORITY INHERITANCE (T1 highest, T3 lowest)

• T1
• T2
• T3

• T1 preempts

• T1 waits for lock

• T2 preempts T3 before T3 releases lock

• T3 acquires lock

Definitions

• Priority inversion: a lower priority task T2 effectively blocks a higher one T1 because T2 prevents T3 from releasing a lock.
• Priority inheritance: the idea that if T3 holds a lock and T1 waits for the lock, then T3 should “inherit” the priority of T1 while T3 holds the lock.

SPECIAL CONSIDERATIONS FOR DISTRIBUTED SYSTEMS

• Since communication is unpredictable, most distributed non-shared memory real-time systems do no dynamic task allocation. Tasks are pre-allocated to specific processors.
• Example: oil refineries where each chemical process is controlled by a separate computer.
• Message exchange is limited to communicating data (e.g., in sensor applications) or status (e.g. time out messages). Messages must be prioritized and some messages should be datagrams.
• Example: Command and control system has messages that take priority over all other messages, e.g., “hostilities have begun.”
• Special processor architectures are possible that implement a global clock (hence require real-time clock synchronization) and guaranteed message deliveries.
• Example application: airplane control with a token-passing network.