Sharing out a single CPU

What runs the alternation is the OS (operating system). In a phrase, the job of an OS is sharing out limited resources among the programs.

There are three things to share out.

• CPU time … who gets to run, and for how long (the subject of this lesson)
• Memory … which regions are lent out
• I/O devices and files … sorting out the contention over disks, the screen and the keyboard

The central part of the OS that handles this sharing out is the kernel.

Around it sit parts with other jobs. A device driver knows the dialect of a particular piece of equipment, such as a printer or a disk, and is the interpreter that drives the hardware directly as the application asks. The shell reads the command text you typed and starts the corresponding program. When the names line up, tell them apart by who each one deals with.

One programme worth of thing that gets alternated is a process. The exam also often says task, but for talking about sharing out the CPU you can treat them as the same.

A process is a container. Its own region of memory, the files it has open, the devices it is using — it holds them all together. So processes cannot see each other memory. Your program cannot corrupt a browser variable precisely because these are kept apart.

Within that container, the flow that actually executes the instructions one by one is a thread. One process can hold several threads.

The difference shows up here. Switching processes is heavy, because there is a lot held and so a lot to swap. Switching threads within the same process is light, since memory and open files stay shared and there is little to swap.

That lightness has a price, though. Threads of the same process share the same memory, so a value corrupted by one can be read by the other. This is exactly where the exclusive control coming later is needed.

A task does not run continuously from birth to death. It moves between three states.

• Runnable … ready to run, but waiting its turn for the CPU
• Running … it has the CPU and is actually running
• Waiting … it could not proceed even with the CPU. It is waiting for something to complete

Waiting is the least obvious, so here is an example. The moment a task issues an instruction to read a file, it can only wait for the disk to answer. Giving it the CPU would achieve nothing, so the CPU goes to another task. That is the waiting state.

The transitions have set directions. Runnable to running is being given the CPU. Running to waiting is requesting I/O yourself. Waiting to runnable is that I/O finishing. Note that when the wait clears, it does not go straight back to running: it rejoins the queue.

And there is running to runnable as well, for when the CPU is taken away mid-run. The next slide starts on that taking away.

At a changeover, two differently named jobs sit side by side. The exam asks about this directly, so learn them apart.

The scheduler is the one that decides which task is next. It compares the runnable tasks and builds an order.

The dispatcher is the one that actually hands the right to use the CPU to the task chosen. Not deciding, but handing over.

Handing over involves three things. First, save the state of the task that was running (register contents and so on). Then choose the next task. Finally restore how far that task had got last time.

That bundle of state is the context, and the switching work is a context switch. Because of the saving and restoring, the switching itself takes time. Alternate too finely and this overhead is all you get.

So how does the scheduler decide? There are four classic ways.

• First come, first served (FCFS) … queue in arrival order and give the CPU to whoever is at the front. The plainest
• Priority … run in order of importance and urgency, set in advance
• Round robin … a little each, in turn. Equal CPU time for everyone
• Shortest job first (SJF) … deal first with whatever has the shortest expected processing time

Round robin sends a task to the back of the queue once it has used up its allotted slice (the time quantum). Everybody advances a little, so nobody is left waiting indefinitely. It suits anything where you do not want to keep the person at the screen waiting.

Shortest job first is good at cutting the average wait overall. But it has a weakness: while short jobs keep arriving, a long job never gets its turn. That is starvation. Asked "which method is most likely to leave a particular task waiting?", this is the answer.

Priority carries the same danger, which is why an adjustment is sometimes added: raise the priority gradually according to how long a task has waited. Then even a low-priority task gets its turn eventually.

There is another axis besides the method: whether the CPU can be taken away from a running task.

Preemptive scheduling means the OS takes it away by force. When the time slice runs out, or when a higher-priority task becomes runnable, the running task is stopped and replaced. The stopped task has not finished, so it goes back to runnable and rejoins the queue.

Non-preemptive scheduling does not take it away. Until that task enters the waiting state of its own accord or terminates, no other task can become running.

What catches people here is where the interrupted task goes. A task preempted by a higher-priority one becomes runnable. It does not become waiting, because waiting means "held up by something such as an I/O completion, unable to proceed even with the CPU". A preempted task could carry straight on if only it had the CPU.

This distinction really does come up often. Chant it: taken away means runnable; asked for I/O yourself means waiting.

Here is one shape of calculation question to learn: how many milliseconds is the CPU used by nobody (the idle time)?

The key is the property that the CPU is free during I/O. Over the five milliseconds a task spends in I/O (5), that task is waiting and is not using the CPU, so another task can move in. Only the time nobody could move into is idle.

Counting is a matter of drawing a single time axis and filling it in from the top.

The example on the right uses priority scheduling with three tasks — high, medium and low — becoming runnable at once. High uses 3 of CPU, drops into I/O, medium moves in, then low. Once low drops out too, all three are in I/O, and that is the gap.

Two knacks when filling it in: always give the CPU to the higher-priority task, and do not forget the premise that I/O does not contend (any number can proceed at once).

What triggers the changeovers is the interrupt: an arrangement for breaking off the running processing and moving to more urgent processing.

When an interrupt occurs, the CPU first saves where it was up to. Specifically it saves the program counter, which holds the address of the next instruction. That is what lets it resume from where it was broken off once the interrupt has been handled.

Interrupts split in two by where the cause lies, and that is what the exam is after.

• Internal interrupt … caused by the running program itself: dividing by zero, an arithmetic overflow, executing a non-existent instruction, executing a software interrupt instruction
• External interrupt … caused by something outside the program: a timer signalling that the set time has passed, an I/O device signalling completion, the power supply signalling a fault

Telling them apart is simple: would it still happen if you stopped that program? A timer keeps ticking either way, so it is external; dividing by zero cannot happen unless that program runs, so it is internal.

One more idea pairs with interrupts: polling. There the CPU goes and looks repeatedly of its own accord, reading a device status register or busy signal to keep watch. An interrupt is "they call you when they are done"; polling is "you keep going to look". The direction is reversed.

Alternation brings a new worry: two tasks touching the same thing.

With only one printer, two tasks printing at once produce mingled text. Two threads rewriting a shared variable at once lose one of the writes. A half-rewritten state must not be shown to another task.

So you arrange for only one task at a time to use a shared resource. That is exclusive control.

The span of code that must honour this "one at a time" is the critical section. You take a lock on the way in and release it on the way out.

The classic lock is the semaphore. Think of the mechanism as a counter tracking the number of free slots. Take one and the count drops by one; finish and it goes back up. At zero, the next task to arrive is made to wait. One with only a single slot is specifically a mutex (binary semaphore).

What matters is that a task made to wait is not dead. Its turn comes when the previous task releases the lock. That is where it differs from the trouble on the next slide.

What if what is shared is not data but the program itself?

Two tasks running the same program at once is common. The property whereby each gets a correct result even when called from elsewhere before the earlier call has finished is being reentrant.

The condition for that is keeping the places that get written to separate per task. The run of instructions may be shared. But if everybody writes their working values to the same place, a later task overwrites an earlier one intermediate values.

Three similar-sounding properties come up together, so keep them apart.

• Reentrant … called again before finishing, it still runs correctly in parallel
• Reusable … after running once, it can be used again without being reloaded. But not at the same time
• Relocatable … it works at any address
• Recursive … it can call itself

"Safe when called at the same time" is reentrant; "can be used again" is reusable. Whether it is at the same time is the dividing line.

Introduce exclusive control and a different kind of jam appears.

Task A takes the printer and task B takes the file. Next A wants the file and B wants the printer. Each waits for the other to let go, so nothing ever moves. That is deadlock.

Keep it apart from ordinary waiting. If one side merely waits over a single resource, its turn comes when the first task releases it. Deadlock is where each demands what the other holds and the waiting has closed into a ring.

It takes certain conditions to arise. Roughly: several resources usable by only one at a time, held while waiting for the next, not taken away, and the requests forming a ring. Break any one of these and it cannot happen.

The simplest break is deciding that everybody acquires resources in the same order. Standardise on "printer then file" and B also starts with the printer, so while A holds it B simply waits there. No ring forms.

If a ring does form, the OS notices and forcibly aborts one side. It is exactly the same idea as one transaction being rolled back in the database chapter. Wherever the same resource is contended for, the same problem turns up.