# 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 |...