Process Scheduling Algorithms

In this handout, there are 5 processes:
  1. Process A arrives at time 0 and takes 10 time units to execute;
  2. Process B arrives at time 1 and takes 29 time units to execute;
  3. Process C arrives at time 2 and takes 3 time units to execute;
  4. Process D arrives at time 3 and takes 7 time units to execute; and
  5. Process E arrives at time 4 and takes 12 time units to execute.

Each section shows how several process scheduling algorithms would execute the processes.

First Come First Serve (FCFS)

This policy services processes in the order they start.

process name arrival time service time start time finish time turnaround time waiting time response time
A010 01010 0 1.0
B129103938 9 1.3
C2 33942403713.3
D3 742494639 6.6
E41249615745 4.8
mean38.226 5.4

In what follows, the number in parentheses in the comment field is the remaining service time for the process. In order of execution:

timeready queuecomments
0A A(10) arrives, runs
1AB B(29) arrives, A(9) is not interrupted and continues to run
2ABC C(3) arrives and is appended to the queue; again, A(8) continues to run
3ABCD D(7) arrives and is appended to the queue; again, A(7) continues to run
4ABCDE E(12) arrives and is appended to the queue; again, A(6) continues to run
10BCDE A finishes, B(29) runs
39CDE B finishes, C(3) runs
42DE C finishes, D(7) runs
49E D finishes, E(12) runs
61 — E finishes

Shortest Process Next (SPN)

This policy services the process with the shortest service time next. It is sometimes also called “shortest job next” (SJN).

process name arrival time service time start time finish time turnaround time waiting time response time
A 0 10 0 10 10 0 1.0
B 1 29 32 61 60 31 2.1
C 2 3 10 13 11 8 3.7
D 3 7 13 20 17 10 2.4
E 4 12 20 32 28 16 2.3
mean25.2132.3

In what follows, the number in parentheses in the comment field is the remaining service time for the process. In order of execution:

timeready queuecomments
0 A A(10) arrives, runs
1 AB B(29) arrives, A(9) continues to run
2 ABC C(3) arrives and is appended to the queue; again, A(8) continues to run
3 ABCD D(7) arrives and is appended to the queue; again, A(7) continues to run
4 ABCDE E(12) arrives and is appended to the queue; again, A(6) continues to run
10 BCDE A finishes; C(3) has the shortest service time, so it runs
13 BDE C finishes, D(7) has the shortest service time, so it runs
20 BE D finishes, E(12) runs
32 B E finishes, B(29) runs
61 — B finishes

Shortest Remaining Time Next (SRTN)

This policy services the process with the shortest service time next. It is sometimes also called “preemptive shortest job next” (PSJN).

process name arrival time service time start time finish time turnaround time waiting time response time
A 0 10 0 2preempted by C
8 12 20 20 10 2.0
B 1 29 32 61 60 31 2.1
C 2 3 2 5 3 0 1.0
D 3 7 5 12 9 2 1.3
E 4 12 20 32 28 16 2.3
<mean>2411.81.7

In what follows, the number in parentheses in the comment field is the remaining service time for the process. In order of execution:

time ready queue comments
0 A A(10) arrives, runs
1 AB B(29) arrives; as its service time is greater than that of A(9), B is appended to the queue and
A continues to run
2 CAB C(3) arrives; as its service time is less than that of A(8), C runs. A’s service time is less than
that of B(29), so it goes before B in the queue
3 CDAB D(7) arrives; as its service time is greater than that of C(2), D is placed in the queue at the
appropriate place, and C continues to run
4 CDAEBE(12) arrives; as its service time is greater than that of C(1), E is placed in the queue at the
appropriate place, and C continues to run
5 DAEB C finishes; D(7) has the shortest remaining service time, so it runs
12 AEB D finishes, A(8) has the shortest remaining service time, so it runs
20 EB A finishes, E(12) has the shortest remaining service time, so it runs
32 B E finishes, B(29) has the shortest remaining service time, so it runs
61 — B finishes

Highest Response Ratio Next (HRRN)

This policy services the process with the greatest (highest) response ratio next.

process name arrival time service time start time finish time turnaround time waiting time response ratio
A 0 10 0 10 10 0 1.0
B 1 29 32 61 60 31 2.1
C 2 3 10 13 11 8 3.7
D 3 7 13 20 17 10 2.4
E 4 12 20 32 28 16 2.3
mean25.2132.3

In order of execution:

  1. At time 0, process A runs for 10 time units, then terminates. At this time:
    1. Process B’s response ratio is ((10 - 1) + 29)/29 = 1.3;
    2. Process C’s response ratio is ((10 - 2) + 3)/3 = 3.7;
    3. Process D’s response ratio is ((10 - 3) + 7)/7 = 2.0; and
    4. Process E’s response ratio is ((10 - 4) + 12)/12 = 1.5.
    so process C runs.
  2. At time 10, process C runs for 3 time units, then terminates. At this time:
    1. Process B’s response ratio is ((13 - 1) + 29)/29 = 1.4;
    2. Process D’s response ratio is ((13 - 3) + 7)/7 = 2.4; and
    3. Process E’s response ratio is ((13 - 4) + 12)/12 = 1.8 .
    so process D runs.
  3. At time 13, process D runs for 7 time units, then terminates. At this time:
    1. Process B’s response ratio is ((20 - 1) + 29)/29 = 1.7; and
    2. Process E’s response ratio is ((20 - 4) + 12)/12 = 2.3.
    so process E runs.
  4. At time 20, process E runs for 12 time units, then terminates. At this time:
    1. Process B’s response ratio is {(32 - 1) + 29)/29 = 2.1.
    so process B runs.
  5. At time 32, process B runs for 29 time units, then terminates.

UC Davis sigil
Matt Bishop
Office: 2209 Watershed Sciences
Phone: +1 (530) 752-8060
Email: mabishop@ucdavis.edu
ECS 150, Operating Systems
Version of April 17, 2022 at 9:03PM

 You can also obtain a PDF version of this.

Valid HTML 4.01 Transitional Built with BBEdit Built on a Macintosh