Process Scheduling Algorithms

First come first serve(FCFS), Shortest job first(SJF), and Shortest remaining time first(SRTF) are used in batch system. Round robin(RR), Highest response ratio next(HRRN), Priority scheduling with multilevel queue, and priority with multilevel feedback queue are used in interactive system.

Various Scheduling Examples | FCFS | Shortest-Job-First (SJR) | Round Robin (RR)

FCFS :

 Process Burst Time P1 24 P2 3 P3 3

Suppose that the processes arrive in the order: P1, P2, P3
The Gantt Chart for the schedule is:

 P1 P2 P3

0 ............................................  24 .............................. 27........................................................ 30

Waiting time for P1 = 0; P2 = 24; P3 = 27

Average waiting time: (0 + 24 + 27)/3 = 17

Suppose that the processes arrive in the order: P2 , P3 , P1 .

The Gantt chart for the schedule is:

 P2 P3 P1

0 ..................................................3.....................................6....................................................30
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Much better than the previous case.

Convoy effect short process behind long process

Shortest-Job-First (SJR) Scheduling:
Associate with each process the length of its next CPU
burst. Use these lengths to schedule the process with the shortest time.
Two schemes:
1.  non-preemptive – once CPU has given to the process it cannot
be preempted until completes its CPU burst.
2. preemptive – if a new process arrives with CPU burst length less than remaining time of the currently executing process, preempt. This scheme is known as the Shortest-Remaining-Time-First (SRTF).

SJF is optimal – gives minimum average waiting time for a given set of processes.

 Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4

SJF (non-preemptive):

 P1 P3 P2 P4

0.................................. 7................................. 8 ........................12.........................................16

Average waiting time = [0 +(8-2)+(7-4) +(12-5)] /4 =4

SJF (preemptive)

 P1 P2 P3 P2 P4 P1

0 ................... 2......................4........................5..................... 7..................... 11...................16

Average waiting time = (9 + 1 + 0 +2)/4 =3
Determining Length of Next CPU Burst Can only estimate the length. Can be done by using the length of previous CPU bursts, using exponential averaging.

Round Robin (RR):
Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.

If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits for more than (n-1)q time units.

Performance:

1. q large _ FIFO

2. q small _ q must be large with respect to context switch, otherwise overhead is too high.

Example of RR with Time Quantum = 4

 Process Burst Time P1 24 P2 3 P3 3

The Gantt chart is:

 P1 P2 P3 P1 P1 P1 P1 P1

0.............4...............7.............10............14............18 ............22.............26............ 30

Average waiting time =    [(30-24)+4+7]/3  = 17/3 =5.66

Note: If the burst time of the processes are matching then schedule the process which has lowest arrival time and if arrival time matching then schedule the process which has lowest process id

Scheduling | Important terms

Throughput - Number of processes completed per unit time. May range from 10 / second to 1 / hour depending on the specific processes.
Turnaround time - Time required for a particular process to complete, from submission time to completion. ( Wall clock time. )
Waiting time - How much time processes spend in the ready queue waiting their turn to get on the CPU.
Load average - The average number of processes sitting in the ready queue waiting their turn to get into the CPU.
Response time - Amount of time it takes from when a request was submitted until the first response is produced.
For a particular process:
Completion time - Arrival time = Burst time + Waiting time = Turn around time