Lecture 5 about 30 min 20 quiz questions

Process Scheduling

How the OS keeps the CPU busy: the queues a process moves through, the three schedulers that move it, and the cost of every context switch.

Start reading Jump to quiz Play the process state game

What you will be able to do

Tell a stack from a queue and explain why the ready queue must be a queue.
Name the job, ready, and device queues and say which processes live in each.
Trace a process through the queueing diagram for an I/O request, a fork, and an interrupt.
Compare the long-term, short-term, and medium-term schedulers on what they pick, how often, and how fast.
Compute scheduling overhead as a percentage of CPU time.
Describe what a context switch saves and restores, and why it is pure overhead.

Warm-up: stacks and queues

Two data structures, one question: who gets served next?

The scheduler is a queue manager. Before we look at its queues, the slides recap the two simplest ways to line things up: the stack (last in, first out) and the queue (first in, first out). The difference is only about which end you insert at and which end you remove from.

Stack versus queue at a glance

	Stack	Queue
Order	LIFO: last in, first out	FIFO: first in, first out
Access point	One end only, called the top	Both ends: insert at the rear, remove at the front
Insert operation	`push`	`enqueue`
Remove operation	`pop`	`dequeue`
Everyday example	A stack of plates, browser back button, function calls	A ticket line, a printer spool, the ready queue

Walk the slide's stack trace

1Start empty. push A, push B, push C: the stack reads C on top of B on top of A.
2pop removes C, the most recent item. B is now on top.
3push D, push E: E sits on top of D, D on top of B.
4pop removes E. The stack is D, B, A. Notice A, the oldest item, has never been touched.

Walk the slide's queue trace

1enqueue 10, enqueue 20, enqueue 30: the queue reads 10 at the front, 30 at the rear.
2dequeue removes 10, the oldest item. The front is now 20.
3enqueue 40, then dequeue twice: 20 and 30 leave in the order they arrived. Only 40 remains.
4enqueue 50: 40 at the front, 50 at the rear. Arrival order is always preserved.

1 of 6

What process scheduling is for

Two objectives, and they pull in opposite directions.

The slides state two objectives for process scheduling. First, keep the CPU busy at all times. Second, deliver acceptable response times for all programs, particularly interactive ones. The process scheduler meets both by implementing policies for swapping processes in and out of the CPU.

Recap of the five-state diagram. Scheduling is the set of rules that move a process along the Ready, Running, and Waiting arrows.

Remember from Lecture 4 that each process is represented by its Process Control Block (PCB): state, program counter, registers, scheduling information, memory limits, accounting data, and open files. Scheduling queues are simply linked lists of PCBs.

Play the process state gameGiven an event such as an I/O request, a timer interrupt, or a completed read, pick the next state. Fast drill for the arrows you need in this lecture.

2 of 6

The three scheduling queues

Job queue, ready queue, device queues. Know who is in memory and who is not.

The ready queue feeds the CPU. Processes that block on I/O sit in a device queue until the device finishes, then return to the ready queue.

The scheduling queues the process scheduler maintains

Queue	Who is in it	Key fact
Job queue	All processes in the system, entered as processes arrive	Includes processes that are not yet in main memory
Ready queue	Processes in main memory that are ready and waiting to execute	Stored as a linked list of PCBs
Device queue	Processes waiting for a particular I/O device	One queue per device; also called an I/O queue

How the ready queue is stored

It is generally a linked list.
The ready-queue header holds pointers to the first and the final PCB in the list.
Each PCB has a pointer field that points to the next PCB in the ready queue.
Processes migrate among the queues as their state changes.

3 of 6

The queueing diagram: a process's life in the queues

Dispatch, then one of three things happens.

The queueing diagram shows queues as boxes, resources such as the CPU and I/O devices as circles, and the flow of processes as arrows. It is the map of where a process can go after it is dispatched.

One trip around the diagram

1
Admit
A new process is put in the ready queue. It waits there until it is selected for execution, or dispatched.
2
Run
The process is allocated the CPU and executes. Now one of three events can occur.
3
Event 1: I/O request
The process issues an I/O request and is placed in an I/O queue (device queue). When the I/O completes, it moves from Waiting to Ready and rejoins the ready queue.
4
Event 2: fork and wait
The process creates a child and waits for the child's termination. It is in the Waiting state until the child exits, then goes back to the ready queue.
5
Event 3: interrupt
The process is removed forcibly from the CPU by an interrupt, for example a timer expiry, and is put straight back in the ready queue. No waiting state involved.
6
Terminate
The cycle repeats until the process terminates. It is then removed from all queues and its PCB and resources are deallocated.

Two ways to leave the CPU

Voluntarily (I/O or wait for child)

Running to Waiting
Sits in a device queue or waits for an event
Returns to Ready only when the event happens

Forcibly (interrupt)

Running to Ready directly
Nothing to wait for; it was simply preempted
Competes for the CPU again immediately

4 of 6

Long-term, short-term, medium-term

Three schedulers with three very different clocks.

Where each scheduler acts: the long-term scheduler admits jobs into memory, the short-term scheduler picks who runs, the medium-term scheduler swaps processes out to disk and back.

The three schedulers side by side

	Long-term (job) scheduler	Short-term (CPU) scheduler	Medium-term scheduler
Selects	Which processes are brought into the ready queue	Which ready process executes next and gets the CPU	Which processes to remove from memory and later bring back
Invoked	Infrequently: seconds, minutes	Frequently: milliseconds	When the degree of multiprogramming must decrease
Speed needed	May be slow	Must be fast	Moderate
Controls	The degree of multiprogramming	CPU allocation	Reduces the degree of multiprogramming via swapping
Aims for	A good process mix of I/O-bound and CPU-bound	Meeting the scheduling criteria of Lecture 6	Freeing memory, improving the mix
Presence	Often absent in time-sharing systems	Sometimes the only scheduler in a system	Optional addition

The process mix the long-term scheduler wants

I/O-bound process

Spends more time doing I/O than computation
Many short CPU bursts
Example: a text editor waiting on keystrokes

CPU-bound process

Spends more time computing
Few very long CPU bursts
Example: video encoding

The medium-term scheduler exists because sometimes too many processes are in memory. It removes a process from memory, stores it on disk, and later brings it back to continue execution. This is swapping. The process is not killed, just parked.

Worked numeric: the cost of a slow short-term scheduler

1
Slide example
The scheduler takes 10 ms to decide, then the chosen process runs for 100 ms. Total elapsed is 10 + 100 = 110 ms.
2
Overhead fraction
Time spent scheduling divided by total time: 10 / 110 = 0.0909, about 9% of the CPU used just to schedule work.
3
Recap question 6
5 ms per decision, 25 decisions in 1000 ms. Scheduling time is 25 x 5 = 125 ms. Fraction is 125 / 1000 = 12.5%.

5 of 6

Context switching

Saving one process, loading another, doing no useful work in between.

When the CPU switches to another process, the system must save the state of the old process and load the saved state of the new process. This is a context switch. The context of a process is exactly what is stored in its PCB.

Anatomy of a context switch

1
Interrupt or system call
The running process P0 is stopped by a timer interrupt, an I/O request, or another trap into the kernel.
2
Save state into PCB0
Program counter, registers, and other context are written into P0's PCB.
3
Reload state from PCB1
The kernel picks P1 and loads its saved program counter and registers.
4
Resume P1
P1 continues exactly where it left off. Later the reverse happens: save into PCB1, reload from PCB0.

What the slides stress

Context-switch time is overhead. The system does no useful work while switching.
The more complex the OS and the PCB, the longer the context switch.
Time depends on hardware support. Some hardware provides multiple sets of registers per CPU, so multiple contexts can be loaded at once and a switch becomes just changing a pointer.

6 of 6

Before the exam

The lines worth memorising, and the mistakes that lose marks.

Remember this

1Stack: LIFO, one end (top), push and pop. Queue: FIFO, insert at rear, remove at front, enqueue and dequeue.
2Two scheduling objectives: keep the CPU busy, and give acceptable response time, especially to interactive programs.
3Job queue: all processes, even those not in memory. Ready queue: in memory, waiting for CPU. Device queue: waiting for one I/O device.
4Ready queue is a linked list of PCBs; the header points to the first and last PCB; each PCB points to the next.
5After dispatch: I/O request goes to an I/O queue, fork-and-wait goes to Waiting, an interrupt puts the process straight back in the ready queue.
6I/O request sequence: Running, I/O queue, Ready. Never via the job queue.
7Long-term scheduler: admits processes, controls the degree of multiprogramming, slow, seconds to minutes.
8Short-term scheduler: picks the next process for the CPU, milliseconds, must be fast, sometimes the only scheduler.
9Medium-term scheduler: swaps processes out to disk and back to reduce the degree of multiprogramming.
10I/O-bound: many short CPU bursts. CPU-bound: few very long bursts. Long-term scheduler wants a mix.
11Scheduling overhead = decision time / total time. 10 ms decide + 100 ms run gives 9%. 25 decisions of 5 ms in 1000 ms gives 12.5%.
12Context switch = save old PCB, load new PCB. Pure overhead. Longer with a complex PCB; shorter with multiple register sets.

Exam traps

Thinking the ready queue holds every process. It holds only processes in main memory that are ready. The job queue holds everything.
Sending an interrupted process to Waiting. An interrupt sends it straight back to Ready; only I/O or an event wait sends it to Waiting.
Confusing the long-term and short-term schedulers. Long-term decides who enters memory and controls the degree of multiprogramming; short-term decides who gets the CPU next.
Assuming every system has all three schedulers. Time-sharing systems often have no long-term scheduler; the short-term scheduler may be the only one.
Believing the medium-term scheduler terminates processes. It swaps them to disk temporarily; they come back and continue.
Treating a context switch as useful work. It is overhead; the CPU runs kernel code that advances no user process.
Dividing by the wrong total in overhead questions. Use decision time plus run time when no window is given; use the given window when one is stated.
Saying the ready queue header stores registers or priorities. It stores pointers to the first and last PCBs.

Quiz yourself

One question at a time with instant feedback. Your best score is saved.

Timed version →

Q 1 / 20 · Stack and queueeasyscore 0

Which statement correctly distinguishes a stack from a queue?

Not quite

A stack works at a single end, the top. A queue inserts at the rear and removes from the front, so it uses opposite ends.

Finished reading?

Mark this lecture as done

Take the quiz above first so your score is saved here.

Practise itPlay the process state game Up nextLecture 6: CPU Scheduling