Overview

Multiprogramming OSes have periods of idling on the CPU and executing work on I/O processes or CPU processes. Idling allows for scheduling of processes.

Schedulers

Schedulers are part of the OS dispatcher. It selects a few processes from memory that are ready to execute.

Goals

Maximize throughput and CPU utilization
Minimize turnaround, waiting, and response time
Be fair to all processes and users

Scheduling that happens when a process switches from the running to waiting state or when a process that terminates is non-preemptive.

Process voluntarily release the CPU
Requires no special hardware??
Poor response time for interactive and real time systems

Scheduling that happens when a process switches from the running to ready state, or the waiting/new to ready state is preemptive.

OS can force a running process to involuntarily release the CPU
- High
May require special hardware (timer)
Complicates kernel design
May require data synchronization mechanisms to maintain data consistency

Dispatcher

Scheduler is a sub-part of the dispatcher

Get new processes
Switch out context
Give CPU control to new process
Jump to proper location in program to restart

Dispatcher Queues

Job Queue
- All jobs/processes (including ones not in memory)
- Scheduled by long term scheduler
Ready Queue
- Processes ready and awaiting execution
- Scheduled by short term scheduler
Device/IO Queue

Methods of Evaluation

Deterministic Evaluation

Not very useful in industry

Queueing Models

Simulations

Scheduling Algorithms

First-Come First Served

Also known as FCFS, it assigns CPU time based on order of arrival. It is implemented using a FIFO. There is no preemption, i.e. no processes are interrupted.

This can be used in a multiprogramming OS, but is not very efficient.

Info

This is a priority scheduling algorithm. Priority is determined by which process arrives first.

Pros

Straightforward, and simple to write and understand

Cons

Average waiting time may be too long
Cannot balance CPU-bound and I/O-bound processes
Cannot be used for time-sharing systems

There can be a huge variation in when processes arrive, which may affect waiting time. The convoy effect can also apply where short processes may be scheduled behind long processes, making their time to completion much longer.

Shortest-Job-First

Also known as SJF, this orders each process based on the length of the next CPU burst. It allocates CPU to the process from the front of the list. This is non-preemptive and a greedy algorithm.

It is a good benchmark to evaluate any other algorithms.

Info

This is a priority scheduling algorithm. Priority is determined by the shortest CPU burst.

Pros

SJF is optimal, it achieves the minimum waiting time for a given set of processes.

Cons

Difficult to know the length of the next process
This can lead to starvation

SJF can use model based prediction to help solve the issue of knowing the length of the next process.

Starvation can occur if processes that are added to the ready queue are continuously smaller and smaller.

Estimated Length of Next CPU Burst Algorithm

The model uses the "history" of processes run and uses and exponential average to predict the next burst. The exponential average gives higher weightage to the lengths of recent processes.

This is not commonly used, but can be used as a baseline for testing other algorithms.

The basic formula is as follows

τ_{n + 1} = α t_{n} + (1 - α) τ_{n}

Where

$t_{n}$ is the actual length of the nth CPU burst

$0 \leq α \leq 1$

$τ_{n + 1}$ is the predicted value of the next burst

Note

$τ_{n + 1}$ is initialized to a random value.

Preemptive SJF

This has newer and shorter processes preempt longer currently running processes.

Priority Based

Aging

Pros

Cons

Round Robin (RR)

Each process is given a fixed time slice (time quantum). When the time slice is up, it will preempt the process and continue to the next one. It is by definition preemptive and can be considered #First-Come First Served with preemption.

Processes are put into a FCFS queue and allocated the CPU for one time quantum. It then preempts the process at the end of the time quantum and puts it at the end of the queue and continues with the next process.

Pros

Simple
Avoids starvation

Cons

May involve larger context switch overhead
Higher average waiting time than SJF
An I/O bound process on a heavily loaded system will run slower

Performance depends on the length of the time quantum

Larger time quantum leads to FCFS like behavior
Smaller time quantum leads to large context switch overhead

Generally time quanta range from 10ms - 100ms. Context switch time is usually around 10 microseconds.

It has a larger waiting time, but better response time for interactive systems. Turnaround time depends on the size of the time quantum. RR is also usually fair.

Lottery Scheduling

This is an adaptive scheduling approach which aims to address fairness.

Each process owns some tickets. On each time slice a ticket is randomly picked. On average the allocated CPU time is proportional to the number of tickets given to each job. In order to avoid starvation, each job is given at least one ticket.

There are multiple ways to assign tickets to jobs. In order to approximate #Shortest-Job-First the algorithm can give short jobs more tickets.

Pros

It is very fair

Cons

Multilevel Queue Scheduling

This is an algorithm which utilizes multiple queues and algorithms to prioritize execution of jobs.

The ready queue is separated into two different queues, the foreground (interactive) and background (batch). The foreground uses #Round Robin (RR) while the background uses #First-Come First Served.

Scheduling must be done between the two queues. This can be done in two ways:

Fixed priority: This allocates CPU to serve all the foreground processes before moving to background processes. It can cause starvation however.
Time slice: This allocates something like a "percentage" of time to each queue. i.e. 80% to foreground and 20% to background.

Info

This is useful when processes can be easily classified into groups. And each group has a different scheduling priority.

Pros

Cons

Multilevel Feedback Queue Scheduling

This allows for processes to move between queues. It can be used to dynamically sort processes based on their typical CPU bursts.

Generally higher priority jobs are I/O bound jobs with shorter bursts.

Approximates SRTF or shortest remaining time first. I/O bound jobs will be in a higher priority, while CPU bound jobs will usually be lower priority.

Note

This may be unfair to longer running jobs, so you can implement aging to raise the priority of a process if they are not serviced after some time. Aging is difficult to tune.

Pros

Cons

Thread Scheduling

Definitions

CPU Utilization

Percentage of time that CPU is busy.

Throughput

The number of processes that complete their execution per unit of time.

Turnaround Time

Amount of time to execute a particular process (time delta of submission time to completion).

turnaround_time = completion_time - submission_time

Waiting Time

Amount of time a process has been waiting in the ready queue.

waiting_time = completion_time - submission_time - time_burst

Response Time

Amount of time it takes from when a request was submitted until the first response is produced.

Reference

Kulkarni, Prasad Various Lectures The University of Kansas 2024

Overview

Schedulers

Dispatcher

Dispatcher Queues

Methods of Evaluation

Deterministic Evaluation

Queueing Models

Simulations

Scheduling Algorithms

First-Come First Served

Shortest-Job-First

Estimated Length of Next CPU Burst Algorithm

Preemptive SJF

Priority Based

Round Robin (RR)

Lottery Scheduling

Multilevel Queue Scheduling

Multilevel Feedback Queue Scheduling

Thread Scheduling

Definitions

Reference

Related