This chart shows the function of each of the three types of schedulers (long-term, short-term, and medium-term) for each of three types of operating systems (batch, interactive, and real-time).
| batch | interactive | real-time | |
|---|---|---|---|
| long-term | job admission based on characteristics and resource needs | sessions and processes normally accepted unless capacity reached | processes either permanent or accepted at once |
| medium-term | usually none--jobs remain in storage until done | processes swapped when necessary | processes never swapped |
| short-term | processes scheduled by priority; continue until wait voluntarily, request service, or are terminated | processes scheduled on rotating basis; continue until service requested, time quantum expires, or pre-empted | scheduling based on strict priority with immediate pre-emption; may time-share processes with equal priorities |
This handout shows how the various job scheduling algorithms work.
This policy services jobs in the order they arrive.
| job 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 | 10 | 39 | 38 | 9 | 1.3 |
| C | 2 | 3 | 39 | 42 | 40 | 37 | 13.3 |
| D | 3 | 7 | 42 | 49 | 46 | 39 | 6.6 |
| E | 4 | 12 | 49 | 61 | 57 | 45 | 4.8 |
| mean | 38 | 26 | 5.4 |
This policy services the shortest job next.
| job 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 |
| mean | 25 | 13 | 2.3 |
This policy services the shortest job next, pre-emptively.
| job name | arrival time | service time | start time | finish time | turnaround time | waiting time | response ratio |
|---|---|---|---|---|---|---|---|
| A | 0 | 10 | 0 | 2 | pre-empted 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 | 24 | 12 | 1.7 | ||||
This policy services the job with the highest response ratio next.
job arrival service start finish turnaround waiting response
| job 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 |
| mean | 25 | 13 | 2.3 |
This policy services jobs for a fixed quantum (here, 5).
| job name | arrival time | service time | start time | finish time | turnaround time | waiting time | response ratio |
|---|---|---|---|---|---|---|---|
| A | 0 | 10 | 0 | 5 | end of quantum; B starts | ||
| 5 | 23 | 28 | 28 | 18 | 2.8 | ||
| B | 1 | 29 | 5 | 10 | end of quantum; C starts | ||
| 24 | 28 | 33 | end of quantum; D starts | ||||
| 19 | 40 | 45 | end of quantum; E starts | ||||
| 14 | 47 | 61 | 60 | 31 | 2.1 | ||
| C | 2 | 3 | 10 | 13 | 11 | 8 | 3.7 |
| D | 3 | 7 | 13 | 18 | end of quantum; E starts | ||
| 2 | 33 | 35 | 32 | 25 | 4.6 | ||
| E | 4 | 12 | 18 | 23 | end of quantum; A starts | ||
| 7 | 35 | 40 | end of quantum; B starts | ||||
| 2 | 45 | 47 | 43 | 31 | 3.5 | ||
| mean | 35 | 23 | 3.3 | ||||
The variant of this class of scheduling algorithms uses three levels:
The jobs A, B, C, D, and E have been augmented by F, a 1-second job arriving at time 13, and G, an 11-second job arriving at time 50. These are to demonstrate that quanta are usually not interrupted.
In what follows, the number in parentheses in the comment field is the remaining service time for the job.
| time | level 1 | level 2 | level 3 | comments |
|---|---|---|---|---|
| 0 | A | -- | -- | A(10) arrives, runs |
| 1 | AB | -- | -- | B(29) arrives, A continues quantum |
| 2 | BC | A | -- | C(3) arrives, A's quantum expires (8), moves to level 2, B runs |
| 3 | BCD | A | -- | D(7) arrives, B continues quantum |
| 4 | CDE | AB | -- | E(12) arrives, B's quantum expires (27), moves down, C runs |
| 6 | DE | ABC | -- | C's quantum expires (1), moves down, D runs |
| 8 | E | ABCD | -- | D's quantum expires (5), moves down, E runs |
| 10 | -- | ABCDE | -- | E's quantum expires (10), moves down, A runs from level 2 (level 1 is empty) |
| 13 | F | ABCDE | -- | F(1) arrives, A's quantum continues |
| 14 | F | ABCDE | -- | A's quantum expires (4), F runs (at level 1) |
| 15 | -- | ABCDE | -- | F finishes, B runs from level 2 (level 1 is empty) |
| 19 | -- | ABCDE | -- | B's quantum expires (23), C runs |
| 20 | -- | ABDE | -- | C finishes, D runs |
| 28 | -- | ABDE | -- | E's quantum expires (6), A runs |
| 32 | -- | BDE | -- | A finishes, B runs |
| 36 | -- | DE | B | B's quantum expires (19), moves down, D runs |
| 37 | -- | E | B | D finishes, E runs |
| 41 | -- | -- | BE | E's quantum expires (2), moves down, B runs from level 3 (since there is nothing in higher levels) |
| 50 | G | -- | BE | G arrives(11), B continues to run |
| 60 | G | -- | E | B finishes, G runs (since it is in the highest level) |
| 62 | -- | G | E | G's quantum expires (9), moves down, G runs from level 2 |
| 66 | -- | G | E | G's quantum expires (5), G runs |
| 70 | -- | -- | EG | G's quantum expires (1), moves down, E runs |
| 72 | -- | -- | G | E finishes, G runs |
| 73 | -- | -- | -- | G finishes |
| job name | arrival time | service time | start time | finish time | turnaround time | waiting time | response ratio |
|---|---|---|---|---|---|---|---|
| A | 0 | 10 | 0 | 2 | preempted by B | ||
| 8 | 10 | 14 | preempted by F | ||||
| 4 | 28 | 32 | 32 | 22 | 3.2 | ||
| B | 1 | 29 | 2 | 4 | preempted by C | ||
| 27 | 15 | 19 | preempted by C | ||||
| 23 | 32 | 36 | preempted by D | ||||
| 19 | 41 | 60 | 59 | 30 | 2.0 | ||
| C | 2 | 3 | 4 | 6 | preempted by D | ||
| 1 | 19 | 20 | 18 | 15 | 6.0 | ||
| D | 3 | 7 | 6 | 8 | preempted by E | ||
| 5 | 20 | 24 | preempted by E | ||||
| 1 | 36 | 37 | 34 | 27 | 4.9 | ||
| E | 4 | 12 | 8 | 10 | preempted by A | ||
| 10 | 24 | 28 | preempted by A | ||||
| 6 | 37 | 41 | preempted by B | ||||
| 2 | 70 | 72 | 68 | 56 | 5.7 | ||
| F | 13 | 1 | 14 | 15 | 2 | 1 | 2.0 |
| G | 50 | 11 | 60 | 70 | preempted by E | ||
| 1 | 72 | 73 | 23 | 12 | 2.1 | ||
| mean | 33.7 | 23.3 | 3.7 | ||||
A fair share scheduler is used when CPU time is to be divided equally between groups of processes. For this scheduling algorithm, processes are divided into groups based upon external factors. Such factors include the organizational divisions of the owners of the computer, or classes of customers, or other criteria.
For example, suppose group A has 1 process, group B has 2 processes, group C has 3 processes, and group D has 4 processes. Under a regular scheduler, each of the 10 processes would get 10% of the CPU. Under a fair share scheduler, each of the 4 groups would get 25% of the CPU.
Suppose there are 3 processes. Process p1 is in group A, and processes p2 and p3 are in group B. The following formula assigns process pi a priority Pi:
In addition, a decay function decrements the current CPU usage of all processes. This "spreads out" the priority of the processes in the ready queue. The decay Di for pi is:
In this system, the lower the numerical value of Pi, the higher the priority of process pi.
The following shows how processes execute, given a quantum of 60 ticks. All arithmetic is integer arithmetic, and the decay function is applied after the most recent CPU time is added in, but before the priorities are computed.
At the beginning of this interval, all priorities are equal, so the process to run is chosen randomly. Say p1 is selected to run. It runs, and at the end of the interval, its CPU usage is updated to 60. The group CPU usage for group A, to which p1 belongs, also is updated to 60. The decay function is then applied, cutting both to 30. The CPU usage for p2 and p3, and for group B, are 0, so the decay function does not change them. The priority P1 of p1 becomes
At the beginning of this interval, P2 and P3 are equal, and both are less than P1, so either p2 or p3 will run. Say p2 is selected to run. It runs, and at the end of the interval, its CPU usage is updated to 60. The group CPU usage for group B, to which p2 belongs, also is updated to 60. The decay function is then applied, cutting both to 30. It also cuts the CPU usage of p1 to 15, and the group CPU usage of group A to 15. The CPU usage for p3 is 0, so the decay function does not change it. The priorities become
P1 = (p1's recent CPU usage)/2 + (p1's group CPU usage)/2 = 15/2 + 15/2 = 7 + 7 = 14
P2 = (p2's recent CPU usage)/2 + p2/2 = 30/2 + 30/2 = 15 + 15 = 30
P3 = (p3's recent CPU usage)/2 + (p3's group CPU usage)/2 = 0/2 + 30/2 = 0 + 15 = 15
At the beginning of this interval, P1 is less than P2 or P3, so p1 runs. At the end of the interval, its CPU usage is updated to 15 + 60 = 75. The group CPU usage for group A, to which p1 belongs, is similarly updated to 15 + 60 = 75. The decay function is then applied, cutting both to 37. It also cuts the CPU usage of p2 to 15, and the group CPU usage of group B to 15. The CPU usage for p3 is 0, so the decay function does not change it. The priorities become
P1 = (p1's recent CPU usage)/2 + (p1's group CPU usage)/2 = 37/2 + 37/2 = 18 + 18 = 36
P2 = (p2's recent CPU usage)/2 + (p2's group CPU usage)/2 = 15/2 + 15/2 = 7 + 7 = 14
P3 = (p3's recent CPU usage)/2 + (p3's group CPU usage)/2 = 0/2 + 15/2 = 0 + 7 = 7
At the beginning of this interval, P3 is less than P1 or P2, so p3 runs. At the end of the interval, its CPU usage is updated to 0 + 60 = 60. The group CPU usage for group B, to which p2 belongs, is similarly updated to 15 + 60 = 75. The decay function is then applied, cutting p3's CPU usage to 30 and the group CPU usage to 37. It also cuts the CPU usage of p1 to 18, the CPU usage of p2 to 7, and the group CPU usage of group A to 18. The priorities become
P1 = (p1's recent CPU usage)/2 + (p1's group CPU usage)/2 =18/2 + 18/2 = 9 + 9 = 18
P2 = (p2's recent CPU usage)/2 + (p2's group CPU usage)/2 =7/2 + 37/2 = 3 + 18 = 21
P3 = (p3's recent CPU usage)/2 + (p3's group CPU usage)/2 = 30/2 + 37/2 = 15 + 18 = 33
This table summarizes the first 8 seconds. The figures shown are for after the ticks, and after the calculations of priorities.
| ticks | Priorities | CPU Usage After Decay | Group CPU Usage After Decay | runs | |||||
|---|---|---|---|---|---|---|---|---|---|
| p1 | p2 | p3 | p1 | p2 | p3 | A | B | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | A |
| 60 | 30 | 0 | 0 | 30 | 0 | 0 | 30 | 0 | B |
| 120 | 14 | 30 | 15 | 15 | 30 | 0 | 15 | 30 | A |
| 180 | 36 | 14 | 7 | 37 | 15 | 0 | 37 | 15 | C |
| 240 | 18 | 21 | 33 | 18 | 7 | 30 | 18 | 37 | A |
| 300 | 38 | 10 | 16 | 39 | 3 | 15 | 39 | 18 | B |
| 360 | 18 | 34 | 22 | 19 | 31 | 7 | 19 | 39 | A |
| 420 | 38 | 16 | 10 | 39 | 15 | 3 | 39 | 19 | C |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
| You can also obtain a PDF version of this. | Version of April 22, 2008 at 9:51 PM |