5.1 Basic Concepts of CPU scheduling

is the basis of multiprogrammed operating systems.

The objective of multiprogramming is

• to have some processes running at all times

• to maximize CPU utilization.

Alternative sequence of CPU-bursts and I/O-bursts	Histogram of CPU-burst duration

CPU scheduler

selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.

Then, how can we select a next process?
Linked List? Binary Tree? FIFO Queue? Priority Queue?

Preemptive(先占) vs Non-preemptive(非先占)

Non-preemptive scheduling
a process keeps the CPU until it releases it, either by terminating or by switching to the waiting state.

Preemptive scheduling
a process can be preempted by the scheduler.

Decision Making for CPU-scheduling

1. When a process switches from the running to waiting state. non-preemptive

2. When a process switches from the running to ready state. preemptive or non-preemptive?

3. When a process switches from the waiting to ready state. preemptive or non-preemptive?

4. When a process terminates. non-preemptive

Dispathcer

a module that gives control of the CPU's core to the process selected by the CPU scheduler.

The functions of dispatcher

• switching context from one process to another

• switching to user mode

• jumping to the proper location to resume the user program

The dispathcer should be as fast as possible since it is invoked during every context switch.

How often do context switches occur?: 5, 30, 27 times per 1 second

$ vmstat 1 3 // 3 times check per 1 second
$ vmstat 2 3 // 3 times check per 2 second

Non-preemptive scheduling: 62 times
Preemptive scheduling: 0 times

5.2 Scheduling Criteria

1. CPU utilization: to keep the CPU as busy as possible.

2. Throughput: the number of processes completed per time unit.

3. Turnaround time:

• how long does it take to execute a process?

• from the time of submission to the time of completion.

4. Waiting time:

• the amount of time that a process spends waiting in the ready queue.

• the sum of periods spend waiting in the ready queue.

5. Response time: the time it takes to start responding (as fast as possible)

5.3 Scheduling Algorithms

CPU Scheduling Problem

decide which of the processes in the ready queue is to be allocated the CPU's core.

The solutions for the scheduling problem

1. FCFS: First-Come, First-Served (old solution)

2. SJF: Shortest Job First(SRTF: Shortest Remaining Time First)

3. RR: Round-Robin

4. Priority-based

5. MLQ: Multi-Level Queue

6. MLFQ: Multi-Level Feedback Queue

FCFS Scheduling

First-Come, First-Served: the simplest CPU-scheduling algorithm.

The process that requests the CPU first is allocated the CPU first.

FCFS Scheduling can be easily implemented with a FIFO queue.

Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds.

If the processes arrive in the order $P_1, P_2, P_3$

Gantt Chart served by the FCFS policy

Calculate the waiting time of this schedule.
Waiting Time for $P_1 = 0, P_2 = 24, P_3 = 27$
Total Waiting Time: $0 + 24 + 27 = 51$
Average Waiting Time: $51/3 = 17$'

If the processes arrive in the order $P_2, P_3, P_1$

Gantt Chart served by the FCFS policy

Calculate the waiting time of this schedule.
Waiting Time for $P_1 = 6, P_2 = 0, P_3 = 3$
Total Waiting Time: $3 + 0 + 3 = 9$
Average Waiting Time: $9/3 = 3$

Gantt Chart served by the FCFS policy

Calculate the turnaround time of this schedule.
Turnaround Time for $P_1 = 24, P_2 = 27, P_3 = 30$
Total Waiting Time: $24 + 27 + 30 = 81$
Average Waiting Time: $81/3 = 27$

Note that
The average waiting time under the FCFS policy
- is generally not minimal and may vary substantially
- if the processes' CPU-burst times vary greatly.

The FCFS scheduling algorithm is non-preemptive.

Note also that
The performance in a dynamic situation
What if we have one CPU-bound and many I/O-bound processes?
Convoy Effect
- all the other processes wait for the one big process to get off the CPU.
- results in lower CPU and device utilization than might be possible
- if the shorter processes were allowed to go first.

SJFS cheduling

Shortest-Job-First: shortest-next-CPU-burst-first scheduling.

SFJ associates with each process, the length of the process's next CPU burst.

When the CPU is available, assign it to the process that has the smallest next CPU burst.

If two or more proceese are even, break the tie with the FCFS.

Gantt Chart served by the SJFS policy

Calculate the waiting time of this schedule.
Waiting Time for $P_1 = 3, P_2 = 9, P_3 = 16, P_4 = 0$
Total Waiting Time: $3 + 16 + 9 + 0 = 28$
Average Waiting Time: $28/4 = 7$

Calculate the turnaround time of this schedule.
Turnaround Time for $P_1 = 9, P_2 = 24, P_3 = 16, P_4 = 3$
Total Waiting Time: $9 + 24 + 16 + 3 = 52$
Average Waiting Time: $52/4 = 13$

Note that
The SJF scheduling algorithm is probably optimal
- it gives the minimum average waiting time for a given set of processes.
Moving a short process before a long one
- decreases the waiting time of the short process
- more than it increases the waiting time of the long process.
- Consequently, the average waiting time decreases.

Can you implement the SJF scheduling?

There is no way to know the length of the next CPU burst.

Try to approximate the SJF scheduling

• We may be able to predict the length of the next CPU.

• Pick a process with the shortest predicted CPU burst.

How to predict the next CPU burst?

exponential average of the measured lengths of previous CPU burst.

$τ_{n+1}=aτ_n+(1-a)τ_n$, where

• $τ_n$ is the length of $n$th CPU burst,

• $τ_{n+1}$ is our predicted value for the next CPU burst,

• for $0 ≤ a ≤ 1$

$a = 1/2$

SJF scheduling is logically optimal soltuion, not really.

Note also that
SJF algorithm can be either preemptive or non-preemptive.
The choice arises
- when a new process arrives at the ready queue
- while a previous is still executing.
What if a newly arrived process is shortet than what is left of the currently executing process?

SRTF scheduling

Shortest-Remaining-Time-First: Preemptive SJF scheduling

SRTF will preempt the currently running process, whereas a non-preemptive SJF will allow it to finish its CPU burst.

Gantt Chart served by the SRTF policy

Calculate the waiting time of this schedule.
Total Waiting Time: $[(10-1)+(1-1)+(17-2)+(5-3)] = 26$
Average Waiting Time: $26/4 = 6.5$

RR scheduling

Round-Robin: preemptive FCFS with a time quantum.

A time quantum (or time slice) is a small unit of time.

The ready queue is treated as a circular queue.

The scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.

One of two thins will happen

1. The process may have a CPU burst fo less than one time quantum.

• the process itself will release the CPU voluntarily

• the scheduler will proceed to the next process in the ready queue.

2. If the CPU burst is longer than one time quantum,

• the timer will go off and will cause an interrupt to the OS

• a context switch will be executed

• the process will be put at the tail of the ready queue.

When we use a time quantum of 4 milliseconds

Gantt Chart served by the RR policy

Calculate the waiting time of this schedule.
Waiting Time for $P_1 = 10 - 4 = 6, P_2 = 4, P_3 = 7$
Total Waiting Time: $6 + 4 + 7 = 17$
Average Waiting Time: $17/3 = 5.66$

Note that
The average waiting time under the RR policy is often long.
The RR scheduling algorithm is preemptive. (definitely)
- if a process's CPU burst exceeds one time quantum,
- that process is preempted and is put back in the ready queue.

The performance of the RR scheduling algorithm depends heavily on the size of the time quantum.

Priority base Scheduling

A priority is associated with each process, and the CPU is allocated to the process with the highest priority.

Processes with equal priority are scheduled in FCFS order.

Note that
The SJF is a special case of the priority based scheduling.

In this case, the priority is the inverse of the next CPU burst

Gantt Chart served by the Priority base policy

Average Waiting Time: $8.2$
Average Turnaround Time: $?$

Priority scheduling can be either preemptive or non-preemptive.

The problem of starvation (indefinite blocking)

• a blocked process: ready to run, but waiting for the CPU.

• some low-priority processes may wait indefinitely.

A solution to the starvation problem is aging

gradually increase the priority of processes that wait in the system for a long time.

Combine RR and Priority scheduling

execute the highest-priority process and runs processes with the same priority using round-robin scheduling.

time quantum = 2

Multi-Level Queue(MLQ) Scheduling

Multi-Level Feedback Queue(MLFQ) Scheduling

5.4 Thread Scheduling

On most modern operating systems, it is kernel threads - not processes - that are being scheduled, and user threads are managed by a thread library.

So, the kernel is unaware of them, ultimately mapped to associated kernel threads.

5.6 Scheduling in the Real-Time Operating System

Soft Realtime vs Hard Realtime

Soft real-time systems

provide no guarantee as to when a critical real-time process will be scheduled

guarantee only that a critical process is preferred to noncritical one.

such as phone call

Hard real-time systems

A task must be services by its deadline.

such as rock launching process

5.6 Exercise 5.3 (p.251)