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.
- 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.
- Straightforward, and simple to write and understand
- 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.
- SJF is optimal, it achieves the minimum waiting time for a given set of processes.
- 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
Where
is the actual length of the nth CPU burst is the predicted value of the next burst
Preemptive SJF
This has newer and shorter processes preempt longer currently running processes.
Priority Based
Round Robin (RR)
Multilevel Queue Scheduling
Multilevel Feedback Queue 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