**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:

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:**

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):**

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

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

**SJF (preemptive)**

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:**

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

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