Scheduling: preemptive scheduling

Preemptive Scheduling: In contrast to non preemptive scheduling, a scheduling decision can be made even while the job is executing whereas in non preemptive scheduling, a scheduling decision is made only after job completes its execution. Therefor preemptive scheduling may force a job in execution to release the processor, so that the execution of some other job can be undertaken, in order to improve throughput considerably.

Types of preemptive scheduling:

1) Round Robin scheduling algorithm: the round Robin scheduling is designed for time sharing systems. The primary objective of round Robin scheduling are interactive use, good response time and sharing the resources equitable among processes. It is similar to FCFS, but preemption is added to switch between processes.

The processes are alocated a small unit of time. Known as time Quantum or time slice is in rotation until the completion of processes.

To implement round Robin scheduling, a FIFO(first in first out) queue is maintained where the new processes are attached at the tail of the queue. The schedule pick.s the first process from the ready queue, set a timer interrupt after one time Quantum and dispatch the process.

Example:

PROCESS	BURST TIME
P1	20
P2	5
P3	10

 

Let the time Quantum is 5 milliseconds. The resulting round Robin scheduling is shown below:

P1

P2

P3

P1

P3

P1

P1

……………..

0                   5                    10                   15                   20                  25                   30                  35 

The selection of time Quantum is very critical to the performance of round Robin scheduling.

 If the time Quantum is very small then the process which is rapidly from running to ready state. This switching need some amount of time and the process is known as context switching.

 If the time Quantum is large, then the round Robin scheduling becomes the FCFS scheduling.

Short Remaining Time Next Scheduling:

In this scheduling, a job process is selected on the basis of the shortest remaining execution time.

It may be implemented either in preemptive or non-preemptive version. The shortest remaining time next is one of the optical scheduling discipline, that minimizes the average waiting time of the system.

In other words we can say the shortest remaining time is the preemptive version of the shortest job next algorithm.