Page 66 - DCAP608_REAL TIME SYSTEMS

Unit 6: Commonly used Approaches to Real-time Scheduling

Notes

Notes When system is initialized, scheduler selects and schedules the jobs that will executed
until the next scheduling decision time and then waits for expiration of the timer. When
the timer expires, the scheduler awakes and repeats these actions.

6.2 Weight Round–Robin Approach

Commonly used for scheduling time-shared applications. Every job joins a FIFO queue when it
is ready for execution. The job at the head of the queue executes for at most onetime slice. Time
slice is the basic granule of time that is allocated to jobs, typically in the order of tens of
milliseconds. If the job doesn’t complete by the time slice, it is preempted and placed at the end
of the queue.

Did u know? If there are n ready jobs in the queue, each job gets one time slice every n time
slices, that is a round. That’s why WRR approach is also called processor sharing algorithm.
Real-time traffic in high-speed switched networks is an example Different jobs may also be
given different weights. A job with weight wt get wt time slices every round, and the length of
a round is equal to the sum of the weights of all ready jobs. We can adjust the weights of jobs to
speed up or retard the progress of each job towards its completion. If used to schedule precedence
constrained jobs, the response time of a chain of jobs can be very large, and that is why not good
for such jobs. But a successor job may be able to incrementally consume what is produced by a
predecessor. Since a job and its successors can execute concurrently is a pipelined fashion, this is
a nice approach for such jobs. In the figure (a), the release time of all jobs are 0, and their
execution times are 1, J and J execute on processor P1 and J and J on processor P2. Suppose
1,1 2,1 1,2 2,1
J , is the predecessor of J and J2,1 is the predecessor of J . Both sets of jobs complete
1,1 1,2 2,2
approximately at time 4.

(b) shows that if the jobs on each processor are executed one after another, one of the chains can
complete at time 2, while the other can complete at time 3. Suppose that the result of the first job
in each set is piped to the second job in the set. The latter can execute after each one or a few time
slices of the former complete.

LOVELY PROFESSIONAL UNIVERSITY 61