2.10 Scheduling in batch system
1. First-Come, First-Served (FCFS)
With this algorithm, processes are assigned the CPU in the order they request it. It is nonpreemptive.
· Example: There are three batch jobs A through C, and their arrival time and running time are as follows. If use FCFS algorithm, what is the scheduling order? Please compute the turnaround time of every job and the mean turnaround time.
Job | Arrival Time | Running Time |
A | 0 | 6 |
B | 1 | 3 |
C | 3 | 2 |
Solution:

the scheduling order: A→B→C
turnaround time: A: 6-0=6;
B: 9-1=8;
C: 11-3=8
mean turnaround time: (6+8+8)/3=22/3
2. Shortest Job First (SJF)
When several equally important jobs are sitting in the input queue waiting to be started, the scheduler picks the shortest job first. It is nonpreemptive.
※the same example as FCFS, but use SJF.
Solution:

the scheduling order: A→C→B
turnaround time: A: 6-0=6;
B: 11-1=10;
C: 8-3=5
mean turnaround time: (6+10+5)/3=21/3=7
3. Shortest Remaining Time Next (SRN)
With this algorithm, the scheduler always chooses the process whose remaining run time is the shortest. It is preemptive.
※the same example as FCFS, but use SRN.
Solution:

the scheduling order: A(1)→B→C→A(5)
turnaround time: A: 11-0=11;
B: 4-1=3;
C: 6-3=3
mean turnaround time: (11+3+3)/3=17/3
Question about CPU scheduling.
Compute the turnaround time of each process and the average turnaround time using:
1. FCFS(First-come first-served);
2. Shortest process first;
3. Shortest remaining time next;
Please draw figures to illustrate their running procedure.
Processes | Arrival time | Run time |
A | 0 | 16 |
B | 2 | 10 |
C | 4 | 6 |
Answer:

Example:
There are three batch jobs A through C, and their arrival time and running time are as follows.
Job
| Arrival Time | Running Time (min) |
A | 8:00 | 60 |
B | 8:10 | 30 |
C | 8:30 | 20 |
1. If use FCFS algorithm, when the start time an end time for every process?
2. If use SJF algorithm, when the start time an end time for every process?
3. If use SRN algorithm, when the start time an end time for every process?
Solution:
1. The scheduling order of FCFS algorithm: A→B→C, so
Job | Start Time | End Time |
A | 8:00 | 9:00 |
B | 9:00 | 9:30 |
C | 9:30 | 9:50 |
· 2.The scheduling order of SJF algorithm: A→C→B, so
Job | Start Time | End Time |
A | 8:00 | 9:00 |
B | 9:20 | 9:50 |
C | 9:00 | 9:20 |
· 3.the scheduling order of SRN algorithm: A(1)→B→C→A(5), so
Job | Start Time | End Time |
A | 8:00 | 9:50 |
B | 8:10 | 8:40 |
C | 8:40 | 9:00 |