Notes@HKU by Jax

Scheduling

Act of selecting the next process/thread to run on the CPU.

Terms

CPU-bound (compute-bound) process

When running, tends to use all the processor time allocated to it. It would go faster if the CPU were faster.

I/O-bound process

When running, tends to use the processor only briefly before generating an I/O request and relinquishing the processor. It would go faster if the I/O subsystem were faster.

Turnaround time

The amount of time to execute a particular process, from submission to complete servicing:

Tturnaround=Tcompletion−TarrivalT_{\text{turnaround}} = T_{\text{completion}} - T_{\text{arrival}}

The objective is to minimize turnaround time.

Waiting time

The amount of time a process waits in the ready queue.

Response time

The amount of time from when a process is submitted to the first time it is scheduled. This is an important performance metric for interactive tasks:

Tresponse=Tfirst run−TarrivalT_{\text{response}} = T_{\text{first run}} - T_{\text{arrival}}

The objective is to minimize response time.

Throughput

The average number of processes (jobs) that complete their execution per unit of time. The objective is to maximize throughput.

Fairness

All similar processes (jobs) are treated the same. Even if processes are in different priority classes, no process should suffer indefinite postponement (starvation).

Scheduling algorithms

Evaluating scheduling algorithms

Use a table:

ProcessArrival timeCPU burst time
A03
B26
C44
D65
E82

First-In-First-Out (FIFO)

Dispatched according to arrival time.

Example

Based on the above table:

TimeQueueCPU
0--2--A
2--3BA
3--4--B
4--6CB
6--8C,DB
8--9C,D,EB
9--13D,EC
13--18ED
18--20--E

The completion times are CA=3C_A=3, CB=9C_B=9, CC=13C_C=13, CD=18C_D=18, and CE=20C_E=20. Therefore, the turnaround times are:

TA=3,TB=9−2=7,TC=13−4=9,TD=18−6=12,TE=20−8=12.T_A=3, \quad T_B=9-2=7, \quad T_C=13-4=9, \quad T_D=18-6=12, \quad T_E=20-8=12.

Hence, the average turnaround time is

3+7+9+12+125=8.6.\frac{3+7+9+12+12}{5} = 8.6.

Shortest Job First (SJF)

Dispatched according to the shortest CPU burst time among the processes currently in the ready queue. SJF is non-preemptive, so a process runs to completion once it has been dispatched.

Example

Based on the above table:

TimeQueueCPU
0--2--A
2--3BA
3--4--B
4--6CB
6--8C,DB
8--9C,D,EB
9--11C,DE
11--15DC
15--20--D

The completion times are CA=3C_A=3, CB=9C_B=9, CC=15C_C=15, CD=20C_D=20, and CE=11C_E=11. Therefore, the turnaround times are:

TA=3,TB=9−2=7,TC=15−4=11,TD=20−6=14,TE=11−8=3.T_A=3, \quad T_B=9-2=7, \quad T_C=15-4=11, \quad T_D=20-6=14, \quad T_E=11-8=3.

Hence, the average turnaround time is

3+7+11+14+35=7.6.\frac{3+7+11+14+3}{5} = 7.6.

Highest Response Ratio Next (HRRN)

Selects the ready process with the greatest response ratio:

R=W+SS=1+WS,R = \frac{W + S}{S} = 1 + \frac{W}{S},

where WW is the waiting time and SS is the estimated CPU burst time. HRRN is non-preemptive and reduces starvation by increasing a process's priority as it waits.

Example

For the example table, the schedule is

A (0–3),B (3–9),C (9–13),E (13–15),D (15–20).A\ (0\text{--}3),\quad B\ (3\text{--}9),\quad C\ (9\text{--}13),\quad E\ (13\text{--}15),\quad D\ (15\text{--}20).

The turnaround times are 3,7,9,9,73,7,9,9,7, respectively, giving an average turnaround time of

3+7+9+9+75=7.\frac{3+7+9+9+7}{5}=7.

Preemptive scheduling

Preemptive scheduling

Running processes may be interrupted and moved to the ready queue, allowing another process to run.

Shortest Time-To-Completion First (STCF)

  • Preemptive version of SJF
  • Arriving processes will trigger scheduler to check against the remaining running time to existing and new processes
  • Schedules the process with the shortest run-time-to-completion next
Example

For the example table, the schedule is

A (0–3),B (3–4),C (4–8),E (8–10),B (10–15),D (15–20).A\ (0\text{--}3),\quad B\ (3\text{--}4),\quad C\ (4\text{--}8),\quad E\ (8\text{--}10),\quad B\ (10\text{--}15),\quad D\ (15\text{--}20).

The turnaround times are 3,13,4,14,23,13,4,14,2, respectively, giving an average turnaround time of

3+13+4+14+25=7.2.\frac{3+13+4+14+2}{5}=7.2.

Round Robin (RR)

  • Preemptive
  • Processes only run for a fixed time quantum (time slice)
  • Upon clock interrupt, if current process has its quantum expires, place to the end of the ready queue and schedule the next process in the ready queue
Example

With a time quantum of 22, the schedule for the example table is

A (0–2), B (2–4), A (4–5),B (5–7), C (7–9), B (9–11),D (11–13), E (13–15), C (15–17),D (17–19), D (19–20).A\ (0\text{--}2),\ B\ (2\text{--}4),\ A\ (4\text{--}5),\quad B\ (5\text{--}7),\ C\ (7\text{--}9),\ B\ (9\text{--}11),\quad D\ (11\text{--}13),\ E\ (13\text{--}15),\ C\ (15\text{--}17),\quad D\ (17\text{--}19),\ D\ (19\text{--}20).

The turnaround times are 5,9,13,14,75,9,13,14,7, respectively, giving an average turnaround time of

5+9+13+14+75=9.6.\frac{5+9+13+14+7}{5}=9.6.

Priority scheduling

Priority

A priority number assigned to a process. Can be static or dynamic.

Multilevel feedback queues (MLFQ)

How it works:

  • Consists of a number of queues Q1…QnQ_1\dots Q_n with priority nn and a time quantum q1…qnq_1\dots q_n for each queue
  • New job always enters at Q1Q_1
  • Scheduler always selects a process from the highest priority non-empty QQ
  • Within the same queue, processes are scheduled in a round-robin fashion
  • If a job at QiQ_i uses an entire qq (or
    time allotment
    ), it is demoted to Qi+1Q_{i+1}, else, stay at same QiQ_i
  • Priority boost
    : After some time period SS, move all jobs in the system to Q1Q_1
Example

Consider the following scenario in a single-CPU system with two processes, P1 and P2:

  • P1 is an interactive process that alternates between CPU and I/O bursts. It runs on the CPU for 1 ms, then performs I/O for 5 ms. This cycle repeats five times, followed by a final CPU burst of 1 ms. The total CPU time required by P1 is therefore 6 ms.
  • P2 is a CPU-bound process that runs continuously on the CPU for 30 ms without any I/O.
  • At t=0t = 0, both P1 and P2 are ready and P1 is ahead of P2 in the queue.
  • No priority boost is applied in this scenario.

Caveats of MLFQ:

  • Starvation
    : A process may never get CPU time if it is always preempted by higher-priority processes.

    For example, when a CPU-bound process is running, it may be preempted by a new interactive process that arrives in the system. If this happens repeatedly, the CPU-bound process may never get a chance to run. Solution:

    Priority boost

  • Misbehaving processes
    : A process can end it's CPU burst right before qq to avoid being demoted. Solution:
    Time allotment

Schedularing by fair share

Keep resource distribution even by considering the process's owner (mother process / user who initiated the process).

Lottery scheduling

Probabilistic fair share scheduling:

  • Lottery tickets are distributed to processes, each ticket represents a chance to win the CPU
  • To keep fair, a process group/user is given a number of tickets proportional to the resources it is entitled to
  • When the scheduler runs, it randomly selects a ticket and the process holding that ticket is given the CPU
  • Lottery scheduling is probabilistically fair, meaning that over time, each process will receive CPU time proportional to the number of tickets it holds

Stride scheduling

Deterministic fair share scheduling:

  • Stride = (some number n) / (tickets held by process)
  • Each process has a pass value that is initially set to 0.
  • CPU picks the process with the lowest pass value to run next.
  • After running, the process's pass value is incremented by its stride.

Multiprocessor scheduling

Edit on GitHub

Previous

Virtualization

On this page