CPU Scheduler
The CPU scheduler makes decisions about which process in RAM will run.
Link to original
Context Switching
Transclude of notes-on-current-work
When a process is running on the CPU, the value of the program counter and CPU’s registers contain values specific to the process. If a process is interrupted so that another process can run, these register values are saved in the PCB so they can be restored the next time that the process runs.
The next process that is about to run may have its own value of registers that need to be restored.
We want context switching to be a fast process to prevent slow down, modern OSs and CPUs can perform a switch in about 1 to 2 micro seconds.
Scheduling Algorithms
CPU scheduling algorithms select processes to execute. In older operating systems, processes were expected to yield to each other, which is a form of cooperative multitasking. This would not require a scheduler.
Preemptive Multitasking
Preemptive multitasking means the OS will interrupt running processes to allow other processes to run. (most modern algorithms)
Link to original
Non-preemptive multitasking
Non-preemptive multitasking means a process will control the CPU until it terminates or enters a waiting state.
Link to original
Current operating systems:
- Linux and Windows use preemptive priority scheduling.
- MacOS uses a multilevel feedback queue.
Measuring scheduling algorithm performance
The waiting time of a process is the amount of time spent in the ready queue. The average waiting time (AWT) of the processes in a queue is the average of all of the waiting times. We want to minimise this value.
For example, consider four processes P1 to P4 with their associated burst times (in context of FCFS this is time to execute without I/O time).
P1 arrives first:
| Process | Burst time (ms) | Wait time (ms) |
|---|---|---|
| P1 | 27 | 0 |
| P2 | 4 | 27 |
| P3 | 6 | 31 |
| P4 | 5 | 37 |
| AWT | 24 |
P1 arrives last:
| Process | Burst time (ms) | Wait time (ms) |
|---|---|---|
| P2 | 4 | 0 |
| P4 | 5 | 4 |
| P3 | 6 | 9 |
| P1 | 7 | 15 |
| AWT | 7 |
First come, first served (FCFS)
The most basic scheduling algorithm is simply a FIFO queue, this is non-preemptive. The process that has been in the queue the longest is selected to run.
Shortest Job First (SJF)
We can schedule jobs that will be completed soonest first based on the burst time of the processes. The major problem with this is estimating the burst time, solving this requires data to be kept on previous burst times of a process, and some sort of computation of the average burst time.
This algorithm can be preemptive or non-preemptive:
- Non-preemptive: each process is allowed to complete or enter a wait state
- Preemptive: if a new process arrives in the ready queue, the scheduler will compare the estimated remaining burst time of the currently-running process and the estimated burst time of the newly arrived process, if the latter is lower the existing process is preempted.
It could be the case that too many short jobs arrive preventing certain longer jobs from ever executing, this is called starvation. To avoid starvation, we could introduce an age factor which adds a priority value to each process which is somehow made from its burst time and age. This can be generalised as a priority scheduler.
Priority Scheduling
With more generalised priority scheduling algorithms we can build a function which determines the priority of all processes based upon a set of factors:
- Internal factors: burst time, use of I/O, memory requirements
- External factors: who owns the machines, who submitted the jobs
This algorithm can be preemptive or non-preemptive:
- Non-preemptive: higher priority processes must wait for current process to wait / exit
- Preemptive: existing process is interrupted for higher priority process
Round-Robin Scheduling
The round-robin algorithm operates similarly to FCFS but has preemption. We use a FIFO queue but it is treated as circular. This means that while a process is not terminated or waiting, it will remain in the queue. Once it has been to the front of the queue it will be returned to the back.
For this algorithm, a time quantum is specified which is the same for all processes. A time quantum is the maximum burst time allowed for a process in any one run.
This creates two possibilities:
- if the running process is finished, it is preempted for the next process
- if the process reaches its maximum time quantum, it is preempted
For example, consider a set of processes with the following burst times:
| Process | Burst time (ms) |
|---|---|
| P1 | 5 |
| P2 | 9 |
| P3 | 2 |
| P4 | 1 |
| P5 | 6 |
| P6 | 11 |
The execution times will be as follows:
| Process | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 5 | 6 | 1 | 2 | 5 | 6 | 2 | 6 | 2 | 6 | 6 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Time (ms) | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 1 |
Multilevel Queue Scheduling
Multilevel queue scheduling involves multiple queues, each containing a particular class of process, arranged in a priority order. For example, time-critical system processes, UI processes, background processes, etc.
These individual queues can also be organised by priority and each use a different scheduling algorithm.
Multilevel Feedback Queue Scheduling
A multilevel queue can be may be expanded on by allowing processes to move between queues, hence multilevel feedback queue scheduling, with this new model processes are allocated to queues according to their burst time characteristics and moved as such. Processes that use a lot of CPU time might be moved to lower priority queues.