Scheduling policies

FCFS / FIFO

First-Come-First-Server (FCFS) scheduler.

Also known as First-In-First-Out (FIFO).
The oldest process in the READY queue is the first to be selected.
Non-preemptive (in strict sense).
- Can be combined with a priority schema (in which case preemption exists).
Favours CPU-bound processes over I/O-bound.
Can result in bad use of both processor and I/O devices.

Draw processor utilization, assuming FCFS policy and no priorities.

Round robin (RR) scheduler.

Preemptive (base on a clock).
- Each process is given a maximum slice of time before being preempted (time quantum).
- Also known as time slicing.
The oldest process in the READY queue is the first one to be selected (no priorities).
- Can be combined with a priority schema.
The principal design issue is the time quantum.
- very short is good, because short processes will move through the system quickly and response time is minimized.
- very short is bad, because every context switching involves a processing overhead.
Effective in general purpose time-sharing systems and in transaction processing systems.
Favours CPU-bound processes over I/O-bound.
Can result in bad use of I/O devices.

Draw processor utilization, assuming RR policy with a time quantum of 2 and no priorities.

Shortest Process Next (SPN) scheduler.

Also known as shortest job first (SJF).
Non-preemptive.
The process with the shortest expected next CPU burst time is selected next.
- FCFS is used to tie up (in case several processes have the same burst time).
Maximum throughput.
Minimum average waiting time and turnaround time.
Risk of starvation for longer processes.
Requires the knowledge in advance of the (expected) processing time.
- This value can be predicted, using the previous values.
Used in long-term scheduling in batch systems.
- Where users are motivated to estimate the process time limit accurately.

Draw processor utilization, assuming SPN policy and no priorities.

Last updated 1 year ago