Page 68 - DCAP608_REAL TIME SYSTEMS

Unit 6: Commonly used Approaches to Real-time Scheduling

The priority list is J1>J2>J3……>J8 All jobs are preemptible, scheduling decisions are made Notes
whenever some job becomes ready for execution or some job complete. (a) shows the schedule
of the jobs on the two processors generated by priority-driven algorithms. At time 0, jobs J1, J2,
J5 and J7 are ready but J1, J2 have higher priority than J7.

6.4 Dynamic versus Static System

In the discussed methods, jobs that are ready for execution are placed in a priority queue common
to all processors. When a processor is available, the job at the head of the queue executes on the
processor. Such multiprocessor systems are referred as a dynamic system as jobs are dynamically
dispatched to processors. Jobs were migratable and a job migrates if it starts execution on a
processor, is preempted, and later resumes on a different processor. Another approach in
multiprocessor and distributed systems is to partition the jobs in the system into subsystems
and assign and bind the subsystems statically to the processors. Jobs are moved only when the
operation mode of the system changes or some processor fails. Such a system is called a static
system. If jobs on different processors are dependent, the schedulers on the processors must
synchronize the jobs according to some synchronization and resource access control protocol.
For example considering last figure, put J1, J2, J3 and J4 on P1 and the remaining jobs on P2. The
priority list is segmented into (P1,P2,P3,P4) and (P5,P6,P7,P8). The scheduler of processor P1 uses
the former and that of P2 uses the later. Jobs on P1 will finish at 8 and on P2 at 11. J2 completes
by time 4 and J6 starts at time 6 so precedence constraint is also satisfied. While dynamic systems
may be more responsive on the average, their worst case real-time performance may be poorer
than static systems. As there are no reliable techniques to validate the timing constraints of
dynamic systems (exist for static), Most Hard RTSs are Static.

Self Assessment

State whether the following statements are True or False:
7. Priority Driven Approach refers to a small class of scheduling algorithms that never leave
any resource idle intentionally.

8. A resource is non-idle only when no job requiring the resource is ready for execution.
9. Scheduling decisions are made when events such as releases and completions of jobs
occur.

10. Jobs that are ready for execution are placed in a priority queue common to all processors.
11. When a processor is available, the job at the head of the queue executes on the processor.
Such multiprocessor systems are referred as a dynamic system as jobs are dynamically
dispatched to processors.
12. A job does not migrate if it starts execution on a processor, is preempted, and later resumes
on a different processor.

Task Prepare a chart to specify differences between dynamic and static system.

LOVELY PROFESSIONAL UNIVERSITY 63