Clock Driven Approach

Clock-Driven Approach

As the name suggests, when scheduling is clock-driven (also called time-driven), decisions on what jobs execute at what times are made at speciï¬Âc time instants. These instants are chosen a priori before the execution of the system begins. Typically, in a system that uses clock-driven scheduling, all the parameters of hard real-time jobs are ï¬Âxed and known. A schedule of the jobs is computed off-line and is stored for use at run time. At each scheduling decision time, the scheduler schedules the jobs according to this schedule. This way, scheduling overhead during run-time can be minimized.

A frequently adopted choice is to make scheduling decisions at regularly spaced time instants. One way to implement a scheduler that makes scheduling decisions periodically is to use a hardware timer. The timer is set to expire periodically without the intervention of the scheduler. When the system is initialized, the scheduler selects and schedules the job(s) that will execute until the next scheduling decision time and then blocks itself waiting for the expiration of the timer. When the timer expires, the scheduler awakes and repeats these actions. (Liu 60)

Weighted Round Robin Scheduling

The round-robin approach is normally used for scheduling time-shared applications. When jobs are scheduled on a round-robin basis, every job joins a First-in-ï¬Ârst-out, FIFO queue when it becomes ready for execution. The job at the head of the queue executes for at most one-time slice. (A time slice is the basic granule of time that is allocated to jobs. In a time shared environment, a time slice is typically in the order of tens of milliseconds.) If the job isn’t complete by the end of the time slice, it is preempted and is placed at the end of the queue where it waits for its next turn. When there are n number of ready jobs in the queue, each job gets one-time slice every n time slices, i.e., every round. Because the length of the time slice is short, the execution of every job begins immediately after it becomes ready. Each job gets 1/n th share of the processor when there are n jobs ready for execution. Due to this reason, the round-robin algorithm is also known as the processor-sharing algorithm.

The weighted round-robin algorithm has been used for scheduling real-time trafï¬Âc in high-speed switched networks. It is built on the basic round-robin scheme. Rather than giving all the ready jobs equal shares of the processor, different jobs may be given different weights. Here, the weight of a job means the fraction of processor time allocated to the job. Speciï¬Âcally, a job with weight wt gets wt time slices every round, and the length of a round is equal to the sum of the weights of all the jobs ready. We can speed up or retard the progress of each job toward its completion by adjusting the weights of jobs. (Liu ,61)

For example, consider two sets of jobs, J1 ={J_1,1, J_1,2}and J2 ={J_2,1, J_2,2}, shown in below. The release times of all jobs are 0, and their execution times are 1. J_1,1 and J_2,1 execute on processor P1, andJ_1,2 and J_2,2 execute on processor P2. Suppose that J_1,1 is the predecessor of J_1,2, and J_2,1 is the predecessor of J_2,2 .

Priority-driven scheduling

The priority-driven algorithms refers to a large class of scheduling algorithms that never leave any resource idle intentionally. It can be stated in another way as, a resource idles only when no job requiring their source is ready for execution. Scheduling decisions are made when events such as releases and completions of jobs occur. Therefore, priority-driven algorithms are event-driven.

Other names for this approach are greedy scheduling, list scheduling and work-conserving scheduling. A priority-driven algorithm is said to be greedy because it tries to make locally optimal decisions. Leaving a resource idle while some job is ready to use the resource is not locally optimal. So, when a processor or resource is available and some job can use it to make progress, such an algorithm never makes the job wait.

The term list scheduling is also descriptive because any priority-driven algorithm can be executed by assigning priorities to jobs. Jobs that are ready for execution are placed in one or more queues in the order of the priorities of the jobs. At any scheduling decision time, the jobs with the highest priorities are scheduled and executed on the available processors. Hence, a priority-driven scheduling algorithm is deï¬Âned to a great extent by the list of priorities it assigns to jobs; the priority list and other rules, such as whether preemption is allowed, deï¬Âne the scheduling algorithm completely. Most scheduling algorithms used in non-real-time systems are priority-driven. The examples include the FIFO (First-In-First-Out) and LIFO (Last-In-First-Out) algorithms, that assign priorities to jobs according their release times, and the SETF (Shortest-Execution-Time-First) and LETF (Longest-Execution-Time-First) algorithms, that assign priorities on the basis of job execution times. Because the priorities of jobs can be dynamically changed, even round robin scheduling can be thought of as priority-driven. The priority of the executing a job is lowered to the minimum value among all jobs waiting for execution after the job has executed for a time slice. (Liu , 62)

Dynamic System vs. Static System

If the jobs are scheduled on multiple processors and a job can be dispatched from the priority run queue to any of the processor, then the system is called dynamic. A job can migrate in a dynamic system. The migration occurs if the job starts execution on one processor and resumes on a different processors.

If the jobs are partitioned into subsystems and each subsystem is bound statically to a single processor then the system is called static system. There is no possibility of job migration in static system. The static system has inferior performance in terms of overall response time relative to dynamic system. But, it is possible to validate static system, whereas there is no possibility of such validation in dynamic system. For this reason, most of the hard real time systems are static and soft real time system can be dynamic.

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.