- n!
- In preemptive scheduling, tasks may be interrupted in order to run a different task. Nonpreemptive scheduling requires tasks to yield or complete in order to start running the next task.
- Suppose the following information:
| Process | Arrival Time | Burst Time |
|---|
| P1 | 0 | 8 |
| P2 | 0.4 | 4 |
| P3 | 1 | 1 |
Using FCFS scheduling:
| Process | Arrival Time | Burst Time | Wait Time |
|---|
| P1 | 0 | 8 | 0 |
| P2 | 0.4 | 4 | 8 |
| P3 | 1 | 1 | 12 |
| Avg. wait time = 6.6 | | | |
Using SJF scheduling:
| Process | Arrival Time | Burst Time | Wait Time |
|---|
| P1 | 0 | 8 | 0 |
| P3 | 1 | 1 | 8 |
| P2 | 0.4 | 4 | 9 |
| Avg. wait time = 5.6 | | | |
Using ‘future-knowledge’ scheduling:
| Process | Arrival Time | Burst Time | Wait Time |
|---|
| P3 | 1 | 1 | 1 |
| P2 | 0.4 | 4 | 2 |
| P1 | 0 | 8 | 6 |
| Avg. wait time = 3 | | | |
- If for example, you have queues for different types of tasks, such as interrupts being handled by the OS or a background task doing calculations, you’d want probably want a longer time quantum for tasks doing calculations as preempting this task regularly would probably make it run longer overall.
- .
- I/O bound tasks just need to read / write a request for some data and can then yield hence using little processing time.
- I/O bound tasks require the processor to wait for some external device, while CPU-bound tasks spend executing code on the processor. It is favourable to allow I/O tasks to run first so they can continue to wait in the background while CPU-tasks execute.
- .
- .
- Shortest job first
- a. The process added twice will have the opportunity to run twice as long as any other process in the queue every time the whole queue is processed.
b. It provides a simple ‘dumb’ way to do priority scheduling. It is a relatively easy algorithm to implement. It requires us to preempt processes which is more complicated than not. It does not allow us to prioritise I/O bound tasks in order to allow them to fetch in the background and hence complete earlier.
- .
- .
- .
- .
- .