CPU scheduling #

Recall the overall state diagram for a process:

Non-preemptive vs preemptive scheduling #

Preemptive here basically means “pause”. So the non-preemptive scheduling can only work in cases 1 and 4 (from prior slides). Preemptive scheduling can happen in cases 1-4.

Dispatcher #

Criteria #

These criteria can be used to evaluate the scheduler’s quality.

Waiting time is the total amount of time waiting, whereas response time is how long it takes until the request is submitted, but not necesarily completed.

Waiting time #

Note the assumptions in the above slide for later slides. Since each process runs to completion, this is non preemptive scheduling.

First come first served #

This is based on a FIFO queue.

By putting the shorter processes first, the overall average wait time is much better. So, the order in which the processes enter the queue really matters.

With a FIFO schedule, a slow process may create a blockage, known as the convoy effect:

Shortest job first #

Minimal spanning tree algorithms, like Prim’s and Kruskal’s, share the same underlying principle to a shortest job first scheduler. Shortest job first is a greedy algorithm.

Shortest remaining time first (preemptive) #

Response time #

\( P_1 \) ’s response time is 0.