4.8 KiB
05/10/20
The OS is responsible for managing and scheduling processes
Decide when to admit processes to the system (new -> ready)
Decide which process to run next (ready -> run)
Decide when and which processes to interrupt (running -> ready)
It relies on the scheduler (dispatcher) to decide which process to run next, which uses a scheduling algorithm to do so.
The type of algorithm used by the scheduler is influenced by the type of operating system e.g. real time vs batch.
Long Term
- Applies to new processes and controls the degree of multi-programming by deciding which processes to admit to the system when:
- A good mix of CPU and I/O bound processes is favourable to keep all resources as bust as possible
- Usually absent in popular modern OS
Medium Term
Controls swapping and the degree of multi-programming
Short Term
- Decide which process to run next
- Manages the ready queue
- Invoked very frequency, hence must be fast
- Usually called in response to clock interrupts, I/O interrupts, or blocking system calls
Non-preemptive processes are only interrupted voluntarily (e.g. I/O operation or "nice" system call yield())
Windows 3.1 and DOS were non-preemptive
The issue with this is if the process in control goes wrong or gets stuck in a infinite loop then the CPU will never regain control.
Preemptive processes can be interrupted forcefully or voluntarily
This required context switches which generate overhead, too many of them show me avoided.
Prevents processes from monopolising the CPU
Most popular modern OS use this kind.
Overhead - wasted CPU cycles How can we objectively critic the OS?
User Oriented criteria Response time minimise the time between creating the job and its first execution (time between clicking the button and it starting) Turnaround time minimise the time between creating the job and finishing it Predictability minimise the variance in processing times
System oriented criteria Throughput: maximise the number of jobs processed per hour Fairness:
> Are processing power/waiting time equally distributed?
> Are some processes kept waiting excessively long - **starvation**
Different types of Scheduling Algorithms
[NOTE: FCFS = FIFO]
First come first serve Concept: a non-preemptive algorithm that operates as a strict queuing mechanism and schedules the processes in the same order that they were added to the queue.
| Pros | Cons |
|---|---|
| Positional fairness | Favours long processes over short ones (think supermarket checkout) |
| Easy to implement | Could compromise resource utilisation |
Shortest job first A non-preemptive algorithm that starts processes in order of ascending processing time using a provided estimate of the processing
| Pros | Cons |
|---|---|
| Always results an optimal turnaround time | Starvation might occur |
| - | Fairness and predictability are compromised |
| - | Processing times need to be known in advanced |
Round Robin A preemptive version of FCFS that focuses context switches at periodic intervals or time slices
Processes run in order that they were added to the queue. Processes are forcefully interrupted by the timer.
| Pros | Cons |
|---|---|
| Improved response time | Increased context switching and overhead |
| Effective for general purpose interactive/time sharing systems | Favours CPU processes over I/O |
| - | Can reduce to FCFS |
Exam 2013: Round Robin is said to favour CPU bound processes over I/O bound processes. Explain why this may be the case.
I/O processes will spend a lot of their allocated time waiting for data to come back from memory, therefore less processing can occur before the time slice runs out.
If the time slice is only used partially the next process starts immediately The length of the time slice must be carefully considered.
A small time slice (~ 1ms) gives a good response time. A large time slice (~ 1000ms) gives a high throughput.
Priority Queue A preemptive algorithm that schedules processes by priority
A round robin is used for processes with the same priority level The process priority is saved in the process control block
| Pros | Cons |
|---|---|
| Can prioritise I/O bound jobs | Low priority processes might suffer from starvation |
Low priority starvation only happens when a static priority level is used. You could give higher priority processes a larger time slice to improve efficiency
Exam Q 2013: Which algorithms above lead to starvation?
Shortest job first and highest priority first.
