Describe first come first serve.
Schedule depends purely on the order which processes arrive.
State the convoy effect.
In first come first serve, short-running processes can get stuck behind long-running processes.
Describe shortest job first.
Estimate length of next CPU burst for each process. Schedule the process with the shortest next burst.
State the optimality of shortest job first.
It gives the least possible waiting time for a given set of processes.
Describe shortest remaining time first.
It is a pre-emptive version of shortest job first - reschedules processes when a new one arrives.
Why is shortest remaining time first not optimal?
Because context switches are not free.
State the assumption used when predicting burst lengths.
The next burst will not be too different from the previous.
State the method of predicting burst lengths.
Exponential averaging. $$\tau_{n+1}=\alpha t_n + (1-\alpha)\tau_n$$ where $t_n$ is the actual time and $\tau_n$ is the estimated time.
When is exponential average accurate?
If the variance is small.
Describe round robin.
Give each process a quantum of CPU time. After the quantum, the process is pre-empted.
State the effect of large and small quantum size in round robin.
$q$ too large then it is a FIFO queue. $q$ too small then too much time spent on context switches.
State the properties of round robin.
Fair: each process gets $1/n$ CPU time in chunks. Live: no process waits for more than $(n-1)q$ time.
Compare round robin to shortest time remaining first.
Higher average turnaround time. Better average response time.
Define priority scheduling.
Each process is associated with an integer priority, schedules the highest priority (lowest number) process.
Define starvation.
Starvation occurs when low priority processes never execute.
Describe dynamic priority scheduling.
The priority of a process starts from a static base, and increases as time passes without it being scheduled.
Describe the scheduler used in UNIX.
Kernel processes: fixed priority, non-preemptive. User processes: dynamic priority, pre-emptive.
State the formula for dynamic priority.
For process j at time interval i:
base_j : base priority
nice_j : user controlled parameter
load_j : average length of the run queue
CPU_j : the age counter
$$\begin{align}
\text{CPU}_j(i) &= \frac{2 \times \text{load}_j}{2 \times \text{load}_j + 1} \text{CPU}_j(i-1)
P_j(i) &= \text{base}_j + \frac{\text{CPU}_j(i)}{4} + 2 \times \text{nice}_j
\end{align}$$
Describe multilevel queues.
Ready queues are partitioned into many queues for different types of processes. Each queue can use a different scheduling algorithm.
Describe multilevel queues with fixed priority.
Lowest priority queue is served before the other one, permits starvation.
Describe multilevel queues with time slice/round robin.
Each queue gets a certain amount of CPU time.
State the parameters of a multilevel feedback queue.
Number of queues and scheduling algorithm used for each queue. Methods used to determining when to upgrade/demote a process. Method to determine which queue to service.
