Software Development Methodology

Scheduling Algorithms
First-Come, First-Served (FCFS) Scheduling
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 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 pre- emptive – once CPU 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 current 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 |...