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

0Comment