Principles of Operating Systems Notes | B.Sc. (Computer Science) Semester 3 | Mumbai University | munotes

Two words that are easy to swap. A resource is anything a program needs and cannot have all of: the processor, memory, disk space, a printer. A service is something the operating system will do for a program if it asks: open a file, start another program, send a message. Resources are handed out. Services are performed. The next chapter is about the first and Chapter seven is about the second.

What it is, on a real machine

Four things are commonly called "the operating system" in ordinary speech, and only one of them is the operating system in the sense this paper means.

The lab machine can show that these are genuinely different things, because they have different version numbers and come from different projects.

$ uname -s
Linux
$ uname -r
6.8.0-117-generic
$ ls --version | head -1
ls (GNU coreutils) 9.4
$ bash --version | head -1
GNU bash, version 5.2.21(1)-release (aarch64-unknown-linux-gnu)
$ grep PRETTY_NAME /etc/os-release
PRETTY_NAME="Ubuntu 24.04.5 LTS"

Four different version numbers for four different things. uname -r is the kernel, which is the operating system. ls belongs to GNU coreutils, a separate project, and is a program that the kernel runs like any other. bash is another such program. Ubuntu 24.04 is the distribution, which is the box all of it came in.

That the shell is an ordinary program is worth proving, because it is the single most common misunderstanding at this stage.

$ which bash
/usr/bin/bash
$ ls -l /usr/bin/bash
-rwxr-xr-x 1 root root 1543048 Sep  1 14:30 /usr/bin/bash

It is a file, of a size, with an owner and permissions, sitting in a directory. The kernel is not a file you can list like that while it is running: it was loaded before any file system existed to list it from.

Worked example: what happens when you type a command

Anita sits at the machine and types ls and presses Enter. Eight things happen, and every one of them is a topic later in this book.

1. The keyboard raises an interrupt. The processor stops what it was doing and the kernel's

keyboard handler runs (Chapter three).

1. The kernel puts the characters where the shell can read them, and wakes the shell up, because

the shell had asked to be woken when a line arrived (Chapter seventeen).

1. The shell reads the line and works out that ls is not one of its own built in commands, so

it must be a program on the disk.

1. The shell asks the kernel to make a copy of itself, with fork (Chapter nineteen).
2. The copy asks the kernel to replace it with the program /usr/bin/ls, with exec (Chapter

twenty).

1. The kernel finds the file on the disk, gives the new program some memory, loads it, and puts

it in the queue of programs waiting for the processor (Chapters fifteen and seventeen).

1. ls asks the kernel to read the directory, and asks the kernel to write its output. It never

touches the disk or the screen itself (Chapter nine).

1. ls finishes. The kernel tells the shell, which prints a new prompt (Chapter twenty one).

Notice what Anita did and what the operating system did. Anita named a program. The operating system found it, loaded it, ran it, read a directory for it, printed for it, and cleaned up after it. That is the intermediary in the definition.

Distinctions that carry marks

What it does not mean

It is not the part you can see. The desktop, the windows and the mouse pointer are programs running on the operating system, not the operating system. A machine with no screen attached still has one, fully working.

It is not a program you run. Every other program is started by something. The operating system is started by the hardware, which is a topic of its own: a small program in the machine's own memory loads a bootstrap program from the disk, which loads the kernel.

It is not only for big machines. A washing machine, a car's engine controller and a smart watch all run one. What changes is how much of it there is, not whether there is one.

It is not optional in a machine that runs more than one program. Two programs sharing one processor and one memory need somebody to decide who gets what, and that somebody must be a program with more power than either of them.

Quick revision

• An operating system manages the hardware, provides a platform for programs, and acts as the

intermediary between the user and the machine.

• It is the program that starts first and stays in control.
• A resource is handed out (processor, memory, disk); a service is performed (open a

file, start a program).

• The kernel is the operating system proper. The shell, the utilities and the

distribution are not.

• The kernel runs in kernel mode; every other program runs in user mode.
• On the lab machine the kernel is Linux 6.8, the shell is bash 5.2, ls is GNU coreutils 9.4,

and the distribution is Ubuntu 24.04. Four version numbers, four different things.

• A job belongs in the operating system when every program needs it and it depends on the

hardware rather than on the problem.

Test yourself

1. Define an operating system in one sentence. Software that manages the computer's hardware,

provides a platform on which application programs run, and acts as an intermediary between the user and the hardware.

1. Why can a program not print to the screen by itself? Because printing means writing to the

particular hardware fitted, which differs from machine to machine, and because two programs writing at once would interfere. The operating system does it once, for everybody.

1. Is the shell part of the operating system? No. It is an ordinary program, in a file, with

permissions and a version of its own. It asks the kernel to do things, exactly as any other program does.

1. Give one example each of a resource and a service. Resource: the processor, or memory.

Service: opening a file, or starting another program.

1. What is the difference between Linux and Ubuntu? Linux is the kernel, which is the

operating system. Ubuntu is a distribution: the kernel plus a shell, utilities and thousands of programs, packaged and named. 6. A microwave oven has a timer, a display and three buttons. Does it have an operating system? It may or may not, and the test is whether more than one thing has to be managed at once. If a single program can poll the buttons and drive the display in a loop, none is needed. As soon as there are several activities to be scheduled, something must schedule them, and that something is an operating system however small.

The measures the allocator is judged by are worth meeting now, because they come back as examinable definitions in Chapter forty six.

• Utilisation: the fraction of the time a resource is busy. Higher is better.
• Throughput: how much work is finished per unit of time. Higher is better.
• Fairness: no program is starved while others are served.

Job two: the control program

The control program's work is easiest to see by asking what a program could do if nobody stopped it. On a machine with no control at all, any program could:

1. read or write any part of memory, including another program's data and the operating system's

own tables;

1. read or write any file, including other people's;
2. talk to any device directly, and confuse it;
3. never give the processor up, so that nothing else ever ran again;
4. execute an instruction that halts the machine.

Every one of those is prevented, and the mechanism is the same in each case: the hardware refuses, and the refusal becomes the operating system's business. That mechanism is the next chapter. The five protections it buys are:

Two of those five can be watched on the lab machine straight away. A program that tries to read memory it does not own is stopped by the hardware, and the operating system then kills it.

#include <stdio.h>

int main(void)
{
    int *not_mine = (int *)1;          /* an address this program does not own */
    printf("about to read address 1\n");
    printf("it holds %d\n", *not_mine);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o trespass trespass.c
$ sh -c ./trespass
about to read address 1
Segmentation fault (core dumped)
$ echo $?
139
$ kill -l 11
SEGV

The first line printed. The second never did. The program was not allowed to finish, and the message is the operating system telling you why: the program referred to a segment of memory it had no right to, so it was stopped. A signal is a short message the kernel sends to a process, and a process killed by signal number n reports the status 128 + n, so 139 means signal

1. The last command asks the shell what signal 11 is called: SEGV, for segmentation violation.

This is the control program working, not a bug in the program. A machine with no protection would have printed whatever happened to be at address 1, which might have been part of the operating system.

The file permission check is just as visible.

$ echo secret > private.txt
$ chmod 000 private.txt
$ ls -l private.txt
---------- 1 student student 7 Sep 30  2026 private.txt
$ cat private.txt
cat: private.txt: Permission denied
$ echo $?
1

cat is a perfectly ordinary program and it asked politely. The kernel said no. Notice that the refusal came from the kernel and not from cat: cat only reported it.

Worked example: two students, one machine

A college laboratory machine has one processor, four gigabytes of memory, and two students logged in. Ravi is compiling a large program. Sneha is editing a file.

The allocator gives Ravi's compiler the processor in long stretches, because it has a great deal of computing to do and nothing to wait for. When Sneha presses a key, the allocator takes the processor away from the compiler within milliseconds and gives it to the editor, because the editor has almost nothing to do but must do it now. The compiler gets most of the processor and the editor gets it promptly. Both measures are served: the machine is busy, and neither student is kept waiting.

The control program makes sure that the compiler, which uses a great deal of memory, cannot read the file Sneha is editing unless she has given it permission; that a bug in the compiler cannot crash the editor; and that if the compiler goes into an infinite loop, the timer still fires and Sneha still gets her keystrokes serviced.

Now change one thing. Suppose the allocator were removed and each program simply ran until it finished. Sneha would wait for the whole compile before her keystroke appeared. Suppose instead the control program were removed. The compiler's bug would take the machine down and both students would lose their work. Neither job is optional.

Distinctions that carry marks

What it does not mean

The operating system does not do the program's work. It does not compile, edit or calculate. It decides who computes, and it performs the jobs that need the hardware.

"Resource allocator" does not mean sharing everything equally. Fair does not mean equal. A program that needs the processor for a hundredth of a second and one that needs it for an hour are not treated the same, and should not be.

The control program is not an antivirus. It is not looking for malicious programs. It enforces rules on every program, good or bad, and it enforces them with the hardware's help rather than by inspection.

Quick revision

• The role of an operating system is two jobs: resource allocator and control program.
• The allocator hands out the processor, memory, the disk and the devices, and takes them back.
• It is judged by utilisation, throughput and fairness.
• The control program prevents errors and improper use, and it does it with the hardware's help:

address translation, permission bits, privileged instructions, and the timer.

• The two jobs conflict on purpose. The scheduling quantum and the banker's algorithm are both

the conflict being settled.

• A program that reads memory it does not own is killed with a segmentation fault, exit status

139, which is 128 plus signal 11.

• A program denied a file is denied by the kernel, not by itself.

Test yourself

1. State the operating system's role in one sentence. It acts as a resource allocator,

deciding which program gets which resource and for how long, and as a control program, controlling the execution of programs to prevent errors and improper use of the computer.

1. Name the four resources this paper is about. The processor, main memory, the disk, and the

devices.

1. Give one decision where the two jobs conflict, and say which wins. The banker's algorithm

refuses a request for free resources because granting it could lead to deadlock. The control program wins, deliberately, at a cost in utilisation.

1. Why is a segmentation fault evidence of good design rather than a failure? Because the

hardware noticed a program touching memory it did not own and the operating system stopped it. Without that, the program would have read or damaged something belonging to somebody else.

1. A program runs in an infinite loop. Which of the two jobs deals with it, and how? The

control program, using the timer interrupt: the processor is taken back whether the program co-operates or not.

1. Is "fair" the same as "equal"? No. Fairness means nobody is starved. Two programs with

completely different needs are correctly given different amounts.

1. It jumps to that routine, the interrupt service routine or handler.
2. The handler does the work, quickly.
3. The handler executes a return from interrupt instruction. The saved state comes back, the mode

bit goes back to user mode, and the interrupted program continues.

The interrupt vector is why the table is indexed rather than searched. There may be a hundred devices and an interrupt must be dispatched in nanoseconds, so the number is an index into an array, never a key to look up in a list.

The kernel keeps a running count of every interrupt it has taken, and of every context switch it has made, and publishes both in one file.

$ awk '/^intr/{print $1, $2} /^ctxt/{print $1, $2}' /proc/stat
intr 75282970
ctxt 74892941

intr is the total number of interrupts since the machine started and ctxt the total number of context switches. Those two numbers are the machine's whole history of being interrupted and of changing hands, and they never stop climbing.

$ a=$(awk '/^intr/{print $2}' /proc/stat)
$ sleep 1
$ b=$(awk '/^intr/{print $2}' /proc/stat)
$ echo "$((b - a)) interrupts in one second, with nothing happening"
4559 interrupts in one second, with nothing happening

Nobody touched the keyboard during that second. The machine was interrupted thousands of times anyway, and most of those were the timer of the next chapter.

The two modes, which are what make protection possible

The processor has a mode bit. It has two values.

A privileged instruction is one the processor will only execute in kernel mode. The set differs between machines, but it always includes:

• switching the mode bit itself (or the machine could simply promote itself);
• loading the register that controls address translation;
• talking to a device directly;
• turning interrupts off;
• halting the machine.

The first one on that list is the whole design. If a user program could set the mode bit, protection would be a suggestion. It cannot, so the only way into kernel mode is an interrupt, a trap or an exception, and every one of those lands on a handler the operating system wrote.

This answers a question beginners ask: if the operating system is just software, what stops my program from doing whatever the operating system does? The mode bit stops it, and the mode bit is hardware.

Seeing an exception happen, and learning who decides

Chapter two showed one exception already: a program read an address it did not own, the processor refused, and the kernel killed it with signal 11. Here is the other example every textbook gives, dividing by zero, and it does something worth the whole chapter.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    (void)argc;
    int top = atoi(argv[1]);
    int bottom = atoi(argv[2]);
    printf("dividing %d by %d\n", top, bottom);
    printf("the answer is %d\n", top / bottom);
    return 0;
}

The two numbers are read from the command line so that the compiler cannot work the answer out in advance. The division really happens while the program runs.

$ gcc -std=c17 -Wall -Wextra -o divzero divzero.c
$ sh -c './divzero 10 0'
dividing 10 by 0
the answer is 0
$ echo $?
0
$ uname -m
aarch64

No exception was raised. The program divided ten by zero, was told the answer is zero, and exited normally. That is not a mistake in the program and it is not a mistake in the book: it is this processor's rule. The machine is an ARM processor, and its integer divide instruction is defined to produce zero when the divisor is zero rather than to raise anything.

So an exception is not a property of the operation. It is a property of the hardware. Dividing by zero is meaningless arithmetic in either case; whether the processor notices is a design decision taken by whoever built the processor. On a machine whose divide instruction does raise, the same program dies and the kernel reports signal 8:

$ kill -l 8
FPE

SIGFPE exists, the kernel will deliver it, and nothing on this machine caused it. A student whose own laptop has a different processor may well see this program die, and both results are correct for the machine they were run on.

Write this carefully in an examination. "Division by zero raises an exception" is the answer a paper expects and is true of the processors the textbooks describe. It is more accurate to say that an arithmetic error raises an exception where the processor defines one, and to give invalid memory access as the example that holds everywhere.

Compare the two cases. The invalid address was refused by hardware on this machine and on every machine, because memory protection is the point of the memory management unit. The division was not, because this processor chose to define an answer instead. Neither program asked the kernel for anything: where the kernel arrived, it arrived because the hardware called it.

Seeing a trap happen

A trap is the deliberate version, and it is what Chapter nine is about. A single system call is enough to show one. strace asks the kernel to report every trap a program makes.

$ strace -e trace=write -o trace.txt /bin/echo hello
hello
$ cat trace.txt
write(1, "hello\n", 6)                  = 6
+++ exited with 0 +++

echo printed its word by trapping into the kernel once, with the system call named write. The program did not touch the screen. It asked.

Distinctions that carry marks

What it does not mean

An interrupt does not stop the machine halfway through an instruction. The current instruction finishes first. This matters: it is why a handler can safely assume the machine is in a consistent state.

The operating system is not "in the background". Between interrupts it is not running at all. Nothing of it is executing while your program computes.

Kernel mode is not a user account. Being the administrator, or root, is a matter of file permissions and is checked by software. Kernel mode is a bit in the processor. A root program still runs in user mode.

Turning interrupts off is not a way for a program to get more speed. It is privileged, and for good reason: a program that turned them off and looped would own the machine for ever.

Quick revision

• A modern operating system is interrupt driven: it runs when an interrupt, a trap or an

exception transfers control to it, and returns.

• Interrupt: from hardware, unexpected timing. Trap: from software, on purpose, a system

call. Exception: from software, by accident, an error.

• The steps: finish the instruction, save state, switch to kernel mode, look the number up in the

interrupt vector, run the handler, return from interrupt.

• The interrupt vector is an array indexed by interrupt number, so dispatch is one memory

reference and not a search.

• The processor has a mode bit: user mode and kernel mode. Privileged instructions run

only in kernel mode.

• Setting the mode bit is itself privileged, so the only way into the kernel is through a handler

the operating system wrote.

• An invalid memory access gives signal 11, SEGV, status 139, on every machine.
• Whether an arithmetic error raises an exception is decided by the processor. On the ARM

processor these programs were run on, integer division by zero produces zero and raises nothing; the signal for an arithmetic exception, where one is raised, is 8, FPE, status 136.

• Polling wastes the processor when nothing is happening; interrupts cost nothing until

something does.

Test yourself

1. What does "interrupt driven" mean? That the operating system is not continuously running:

control passes to it when an interrupt, trap or exception occurs, and returns to the program afterwards.

1. Distinguish an interrupt from a trap. An interrupt comes from hardware outside the

processor at an unpredictable moment; a trap is raised by the running program on purpose, to ask the operating system for a service.

1. What is the interrupt vector and why is it a table? A table holding the address of the

handler for each interrupt number. It is indexed by the number so that dispatch takes one memory reference, which matters when interrupts arrive thousands of times a second.

1. Name three privileged instructions. Setting the mode bit, loading the address translation

register, and halting the machine. Turning interrupts off and talking to a device directly are also privileged.

1. Why must setting the mode bit be privileged? Otherwise any program could put itself into

kernel mode and all protection would be voluntary.

1. A program prints one line and then dies with status 136. What happened? It was killed by

signal 8, an arithmetic exception. The processor raised the exception and the kernel killed the program. 7. Your friend's laptop kills a program that divides by zero and yours prints zero. Who is right? Both. Raising an exception on integer division by zero is a decision taken in the processor, not in the operating system and not in C. The ARM processor used in this book defines the result as zero; others raise.

1. Give one case where polling is the right choice. A device so fast that waiting for it

takes less time than taking an interrupt would, for example a high speed network card under heavy load.

$ getconf CLK_TCK
100

A hundred ticks to the second, so one tick is ten milliseconds. Every figure the kernel reports about how long a program has computed is a whole number of those ticks. That is why the processor time of a short program is often reported as zero: it did not run for a whole tick.

A program that computes is charged; a program that waits is not. That is the whole meaning of the tick, and it can be measured. Here are two programs that both take about two seconds of the world's time.

#include <stdio.h>

int main(void)
{
    volatile long i;
    long total = 0;

    for (i = 0; i < 200000000L; i++) {
        total += i & 1;
    }
    printf("total %ld\n", total);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o count count.c
$ /usr/bin/time -f "%U" -o busy.txt ./count
total 100000000
$ /usr/bin/time -f "%U" -o idle.txt sleep 2
$ awk '{print ($1 > 0.2) ? "the counting program was charged real processor time" : "charged almost nothing"}' busy.txt
the counting program was charged real processor time
$ awk '{print ($1 < 0.1) ? "the sleeping program was charged none at all" : "charged something"}' idle.txt
the sleeping program was charged none at all

%U is the processor time a program spent in user mode. The counting program used the processor and was billed for it, in ticks. The sleeping program was not running at all, so there was no tick during which it held the processor, and its bill is zero.

Preemption, watched happening

Here is the proof that the operating system gets the processor back. The program above is run, another command is run at the same time, and the second one finishes.

$ gcc -std=c17 -Wall -Wextra -o spin spin.c
$ set +m
$ ./spin & spin=$!
$ date
Tue Sep 29 10:30:17 IST 2026
$ echo 2 + 2 | bc
4
$ kill $spin 2>/dev/null
$ wait 2>/dev/null

./spin & started the loop in the background, where it does nothing but compute. The two commands after it ran perfectly, in their turn, and answered. Nothing asked the loop politely to step aside: it was interrupted by the timer, hundreds of times, and the scheduler let the other work through.

& puts a command in the background and kill %1 ends it. The loop would otherwise have run until the machine was switched off, which is the point of the chapter.

The other half of the proof is that the kernel knows how long the loop ran without the loop ever telling it.

$ set +m
$ ./spin & spin=$!
$ sleep 2
$ awk '{print "ticks charged: " $14 + $15}' /proc/$spin/stat
ticks charged: 40
$ kill $spin 2>/dev/null
$ wait 2>/dev/null

Fields 14 and 15 of that file are the ticks the program has spent in user mode and in kernel mode. The program printed nothing, asked for nothing and reported nothing. The count exists because the kernel was interrupted while the program was running, looked at whose program it was, and added one to the tally.

Thirty four ticks is a third of a second, not two, and that is honest: the lab machine shares its processors with other work, so the loop was ready far more often than it was running. On an idle machine the two figures would be much closer. What the chapter proves is that the count exists at all and that nothing the program did produced it.

Worked example: how a quantum becomes a number

A round robin scheduler wants to give each program ten milliseconds at a time. The tick is one millisecond.

1. The kernel sets the timer for ten ticks and dispatches program P1.
2. Ticks one to nine arrive. At each one the kernel adds a tick to P1's account and sees that the

quantum has not run out, so it returns to P1 immediately. Nine interrupts, nine returns.

1. Tick ten arrives. The quantum has run out. The kernel saves P1's registers into its process

control block, puts P1 at the back of the ready queue, chooses P2, loads P2's registers, and returns into P2.

1. The timer is set for ten ticks again.

Two things in that list are examinable. The first is that the quantum is counted in ticks, so a quantum cannot be shorter than a tick, and asking for a four and a half millisecond quantum on a machine with a one millisecond tick gets four or five. The second is that step 3 is the context switch of Chapter seventeen, and steps 1 to 4 happen between ten and a thousand times a second on the machine you are reading this on.

Count the cost. If a context switch takes five microseconds and the quantum is ten milliseconds, the machine spends a fraction 5 / 10005 of its time switching, which is a twentieth of a per cent. Make the quantum one hundred microseconds instead and it spends 5 / 105, about 4.8 per cent. That is the trade of Chapter fifty two, and it is arithmetic rather than opinion.

Why setting the timer is privileged

If a program could set the timer, it could set it to never fire. Everything in this chapter would then be voluntary again, and one line of C would still be the end of the session. So loading the timer is a privileged instruction, exactly like setting the mode bit, and only the kernel does it.

The same argument covers turning interrupts off. A program that could do that could ignore the timer even while it fired.

Distinctions that carry marks

What it does not mean

The timer does not cause a context switch every time it fires. Most ticks the kernel simply notes the time and returns to the same program. A switch happens when the quantum has run out or somebody more urgent is ready.

Preemption is not unfair to the program that is stopped. It loses nothing: its registers are saved and restored, and it cannot tell. The only thing it loses is the illusion that it owns the machine.

The timer is not the clock. The clock is the date and time, kept in a battery backed chip and in the kernel. The timer is a countdown device used for scheduling. They are related only in that the kernel uses timer interrupts to advance its idea of the time.

A one second sleep is not one second of processor time. A sleeping program uses none at all. TIME in the ps output above was two seconds because the loop was computing, not waiting.

Quick revision

• The operating system sets a timer to interrupt after a period. The interrupt returns

control to the kernel, which may take the processor away. Setting the timer is privileged.

• Without a timer, control returns only when the program gives it up: that is non-preemptive

or co-operative scheduling, and one infinite loop ends the session.

• A tick is the interval between timer interrupts. getconf CLK_TCK reports 100 on the lab

machine, so a tick is ten milliseconds and processor time is charged in those units.

• A quantum is how long a program may run, counted in whole ticks.
• Fields 14 and 15 of /proc/<pid>/stat are the ticks a program has been charged in user mode

and in kernel mode. A computing program's count climbs; a sleeping program's does not.

• Two designs: a periodic tick at a fixed rate, or a one shot timer set to the quantum.
• Most ticks do not cause a context switch. The kernel notes the time and returns.
• The switching overhead is the switch time divided by the quantum plus the switch time, and it

is a sum, not an opinion.

Test yourself

1. Why must the timer exist? Because without it the operating system regains control only

when the running program asks for something, so a program that computes in a loop would keep the processor for ever.

1. Why is setting the timer a privileged instruction? A program that could set it could stop

it firing, and then preemption would be voluntary again.

1. What is a tick, and what is the tick on the lab machine? The interval between two timer

interrupts. getconf CLK_TCK gives 100 ticks per second, so ten milliseconds.

1. Does every timer interrupt cause a context switch? No. Usually the kernel advances the

time, charges the running program, finds the quantum has not expired, and returns to the same program. 5. A machine has a five microsecond context switch. Compare the overhead at a ten millisecond quantum and at a one hundred microsecond quantum. the fraction 5 / 10005, a twentieth of a per cent, against 5 / 105, about 4.8 per cent. A short quantum responds faster and wastes far more.

1. A program sleeps for five seconds. How much processor time is it charged? Almost none. It

is not running while it sleeps, and processor time is charged only for ticks during which it held the processor.

Three words that are examined together and are constantly confused:

A buffer holds data on the way through. A cache holds a copy of data that is somewhere else. A spool is a queue of whole jobs.

5. Secondary storage management

The disk is where everything lives when it is not in memory. The operating system manages free space, allocates storage, and schedules the requests that reach the disk.

6. Protection and security

Protection is controlling what the programs and users on this machine may do to each other. Security is defending the machine from outside it. Both are the control program of Chapter two.

Those two words are not synonyms and a question that names one does not accept the other. Protection is internal and is enforced by the kernel on every access. Security is external: passwords, encryption, keeping the software patched.

And two that are usually added

Networking is really device management plus communication, but it is large enough that most books list it separately. Command interpretation is the shell of Chapter eight, which is not part of the kernel at all but is always shipped with it.

Seeing all six on one machine

One command each, and every one of them is the operating system reporting on a function.

$ ps -o pid,stat,comm --no-headers | head -3
      8 Ss   sh
      9 S    bash
     12 R+   ps
$ free -m | head -2
               total        used        free      shared  buff/cache   available
Mem:            3905         512         591           0        2985        3393
$ ls -l /etc/hostname
-rw-r--r-- 1 root root 7 Sep 30  2026 /etc/hostname
$ df -h / | awk 'NR==2 {print "the root file system is of type", $1}'
the root file system is of type overlay
$ id
uid=1000(student) gid=1000(student) groups=1000(student),27(sudo)

ps is process management, free is memory management, ls is file management, df is secondary storage management, and id is the identity every protection decision is made against. Not one of those commands touched the hardware. Each asked the kernel and printed the answer.

Worked example: one keystroke, all six functions

Priya presses Ctrl and S in a text editor to save her file. Follow it.

1. Device management. The keyboard interrupts. The kernel's driver reads the key and puts it

where the editor can find it.

1. Process management. The editor was blocked waiting for input. The kernel moves it from the

waiting state to the ready state, and the scheduler eventually gives it the processor.

1. File management. The editor asks the kernel to write the file. The kernel checks the file

exists, checks Priya may write it, and finds where its blocks are.

1. Protection. That permission check. If the file belonged to somebody else and was not

writable by her, the write is refused here and nothing below happens.

1. Memory management. The bytes to be written are in the editor's memory. The kernel copies

them into its own buffers, because the editor's memory may be paged out before the disk is ready.

1. Secondary storage management. The kernel decides which blocks on the disk the file will

occupy, marks them used in the free space map, and queues the write.

1. Device management again. The disk driver takes the queued request. Later the disk

interrupts to say it is done.

Every function in the list did something, for one keystroke, in a few milliseconds. That is why they are listed together.

Distinctions that carry marks

What it does not mean

The six are not six separate programs. They are six kinds of work done by one kernel, and they constantly call on each other, as the worked example shows.

"File management" does not mean an application. A file manager with icons is a program. File management is the kernel's work of turning a name into blocks on a disk.

The shell is not a function of the operating system. Command interpretation is a service that is shipped with it and runs as an ordinary program.

Quick revision

• Six functions: process management, memory management, file management, device

management, secondary storage management, protection and security. Networking and command interpretation are usually added.

• Every function is a resource with a manager, and every manager must know what it has, know who

has it, decide who is next, and take it back.

• Buffering is data in transit. Caching is a copy of data held elsewhere. Spooling is

a queue of whole jobs.

• Protection is internal and enforced by the kernel. Security is external.
• A single keystroke that saves a file uses every one of the six.

Test yourself

1. List the functions of an operating system. Process management, memory management, file

management, device or input and output management, secondary storage management, and protection and security. Networking and command interpretation are commonly added.

1. Distinguish buffering, caching and spooling. A buffer holds data in transit between a

device and a program working at different speeds. A cache holds a copy of data that lives elsewhere, so a second use is cheap. A spool queues whole jobs for a device that can handle only one at a time.

1. Distinguish protection from security. Protection controls what users and programs on this

machine may do to each other and is enforced by the kernel. Security defends the machine from outside.

1. What must any resource manager do? Know what it has, know who holds what, decide who gets

it next, and take it back when they are done.

1. Which function does the print queue belong to? Device management, as spooling.
2. Name the function that a permission check belongs to, and say when it happens. Protection,

and it happens on every access, inside the kernel, before the work is done.

This one is worth attention because it is how almost all server computing is now done, and because it is a beautiful use of Chapter three: the guest kernel runs in user mode. When it executes a privileged instruction, the processor traps, the hypervisor catches the trap, does the equivalent thing to the guest's simulated hardware, and returns. The guest's own protection still works, because the guest's programs are one further level down.

A container is the lighter relative: one kernel, but each group of processes given its own view of the file system, the process table and the network. It is not a second operating system, and that is the difference examiners look for.

Cloud computing

Computing bought by the hour over a network. Three shapes are named in every syllabus:

Cloud computing is virtualisation plus a network plus somebody else's electricity bill. The operating system ideas do not change; the question of who runs them does.

The older kinds, which a question still names

MU's own textbook came up through these, and a question asks for them by name, so they are worth a table even though the machine on your desk is none of them.

The three properties a question asks for. A batch system maximises throughput and nobody waits at a terminal; a time sharing system minimises response time and accepts more overhead to get it; a real time system guarantees a deadline and gives up average speed for predictability. Chapter forty five's five criteria are the same three ideas, measured.

The advantage of a multiprocessor system is also a stock question: more work done in the same time, better economy than that many separate machines because they share memory and devices, and more reliability, because the work of a failed processor can be taken by the others, which is called graceful degradation.

Real time embedded systems

A controller inside something else: a washing machine, an anti-lock brake, a pacemaker, a satellite. The constraint is the deadline, and this is the one environment where being late is being wrong.

A hard real time system is not a fast system. It is a predictable one. A processor twice as fast with unpredictable timing is worse, not better. That is why hard real time kernels give up features this book teaches: virtual memory is often switched off, because a page fault takes an unpredictable time, and secondary storage may be absent altogether.

The lab machine, honestly

The machine every program in this book was run on is worth describing, because it is an example of two of the environments above at once.

$ uname -s -r -m
Linux 6.8.0-117-generic aarch64
$ nproc
2
$ free -m | awk 'NR==2 {print "memory " $2 " megabytes"}'
memory 3905 megabytes
$ grep -c processor /proc/cpuinfo
2

Two processors, four gigabytes of memory, an ARM instruction set, and a Linux kernel. It is a container inside a virtual machine: a single kernel shared with its host, with this book's programs given their own view of the file system and the process table. Everything about processes, memory, synchronisation and files behaves exactly as it does on a physical machine, which is why it can be used at all.

Distinctions that carry marks

What it does not mean

"Mobile" is not a cut down desktop. The constraints are different, so the decisions are different, and a phone operating system does things a desktop would never do, like killing a running program to free memory.

The cloud is not a kind of operating system. It is a way of buying computing. Underneath it is virtualisation and the same operating systems.

Real time does not mean quick. It means on time, every time, with a known worst case.

Quick revision

• Environments: traditional, mobile, client server, peer to peer,

virtualisation, cloud, real time embedded.

• Revise each one by its dominating constraint: response time, battery, throughput, no central

authority, the guest must not tell, who pays, the deadline.

• A hypervisor runs guests whose kernels run in user mode; their privileged instructions trap

to the hypervisor.

• A container shares one kernel and is given a separate view of the system. It is not a

second operating system.

• Cloud service shapes: infrastructure, platform and software as a service.
• Hard real time means a missed deadline is a failure, and it buys predictability by giving

up features such as virtual memory. Soft real time degrades gracefully.

Test yourself

1. Name the computing environments. Traditional, mobile, client server, peer to peer,

virtualised, cloud, and real time embedded.

1. Why does a phone kill background programs when a desktop does not? Memory is limited and

there is no disk to swap to without wearing the flash storage out, so the operating system reclaims memory by ending programs the user is not looking at.

1. How does a hypervisor keep a guest kernel under control? The guest kernel runs in user

mode, so every privileged instruction it executes traps to the hypervisor, which performs the equivalent operation on the guest's simulated hardware.

1. Distinguish a virtual machine from a container. A virtual machine runs its own kernel and

can run a different operating system; a container shares the host's kernel and only gets a separate view of the file system, processes and network.

1. Is a hard real time system a fast system? No. It is a predictable one. A faster but

unpredictable machine is worse for the job.

1. Which cloud shape leaves you managing the operating system? Infrastructure as a service.

Most of what a user calls the operating system is system programs. The kernel is small and invisible; the shell, the file manager and the compiler are what a person actually touches, and replacing any of them changes nothing about the kernel underneath.

Seeing them, one at a time

Each command below is one service being asked for and given.

$ /usr/bin/time -f "the kernel accounted: %U user, %S system, %M kilobytes peak" ls > /dev/null
the kernel accounted: 0.00 user, 0.00 system, 2176 kilobytes peak
$ ipcs -l | head -4

------ Messages Limits --------
max queues system wide = 32000
max size of message (bytes) = 8192
$ id -u
1000
$ ulimit -n
1024

/usr/bin/time printed the kernel's own accounting record for a program that had just finished: processor time in both modes, and the most memory it ever held. ipcs -l listed the limits of the communication facilities the kernel offers. id -u is the identity every protection decision is made against. ulimit -u is a resource allocation limit: the most processes this user may have at once, which is what stops one account bringing the machine down by making processes for ever.

Worked example: a service refused, three ways

The same program asks for three things and is refused each time, for three different reasons. Each refusal is a service, not a failure.

$ cat /etc/shadow
cat: /etc/shadow: Permission denied
$ mkdir /usr/newdir
mkdir: cannot create directory ‘/usr/newdir’: Permission denied
$ ulimit -v 2000
$ ls
ls: error while loading shared libraries: libc.so.6: failed to map segment from shared object
$ ulimit -v unlimited
bash: ulimit: virtual memory: cannot modify limit: Operation not permitted

The first two refusals are protection: the file and the directory belong to root, and the check was made by the kernel rather than by cat or mkdir.

The third is resource allocation. The shell was told to allow itself and its children only two megabytes of virtual memory. ls could not even map the C library into that, so it never started. The kernel did not crash, did not let the program run without memory, and reported exactly what went wrong.

The fourth line is the same service again, seen from the other side. Putting the limit back was refused. Every limit of this kind has a soft value, which a program may lower and then raise again up to a hard ceiling, and a hard value, which may only ever be lowered. ulimit -v 2000 lowered both, so there was no way back. That is deliberate: a program that could raise its own ceiling would not be limited at all.

This is worth knowing before you try it on your own machine. A shell whose hard limit you have lowered cannot undo it. Close that shell and open another.

Distinctions that carry marks

What it does not mean

A service is not a program. The shell, the compiler and the file manager are programs that use services. The service is what the kernel does when asked.

Error detection does not mean the operating system fixes your bug. It means it notices, reports, and keeps the rest of the machine correct. Your program still dies.

Accounting is not surveillance of what you typed. It is a count of resources: processor time, memory, disk, network. The kernel does not read your file to account for it.

Quick revision

• Services for the program: program execution, input and output operations, file system

manipulation, communications, error detection.

• Services for the system and its users: resource allocation, accounting, protection and

security.

• The test for which group a service is in: would the program itself ask for it?
• Input and output through the operating system is protection as well as convenience: a program

that could drive the disk could read every file on it.

• Error detection means notice, report, and keep the rest of the machine correct.
• /usr/bin/time shows accounting, ipcs -l the communication facilities, id the identity

protection is checked against, ulimit an allocation limit.

• A limit has a soft value a program may lower and raise again, and a hard value that may

only be lowered. Lowering the hard value cannot be undone.

Test yourself

1. List the services an operating system provides. For programs: program execution, input and

output operations, file system manipulation, communications, error detection. For the system: resource allocation, accounting, protection and security.

1. Why is input and output a service rather than something a program does itself? Because a

program cannot be trusted or expected to drive the hardware: it would have to know which device is fitted, and it could read anything on it.

1. Which service was at work when a program died with a segmentation fault? Error detection.

The kernel noticed an invalid access, ended that program, and left the rest of the machine correct.

1. Give a service that a program would never ask for, and say who wants it. Accounting. The

owner of the machine wants it, to enforce fair use or to bill.

1. What does ulimit -n control, and which service is that? The most files a program may

have open at once. Resource allocation.

1. Why can a program lower its own resource limit and not raise it again? Because the hard

value may only be lowered. If a program could raise its own ceiling the limit would mean nothing.

1. Distinguish a service from a resource. A service is work done on request and there is

nothing to give back. A resource is held for a while and must be released.

$ type cd
cd is a shell builtin
$ type ls
ls is hashed (/usr/bin/ls)
$ type -a echo
echo is a shell builtin
echo is /usr/bin/echo
echo is /bin/echo
$ type grep
grep is /usr/bin/grep

cd has to be built in. Changing directory changes a property of the running process, and a separate program could only change its own, then exit and take the change with it. That is a favourite examination question and the reason is the whole answer.

ls is a program in a file, and "hashed" means the shell has remembered where it found it so that it need not search the next time.

echo is both: the shell has its own built in and there is also a program on the disk. The built in wins unless you ask for the other by its path. It is listed twice because /bin on this system is a link to /usr/bin, so both names reach the same file.

What the shell adds, beyond running a command

None of the following is the operating system's work. All of it is the shell doing arithmetic on file descriptors and process ids, using the same system calls any program may use.

The program never sees the pattern. By the time ls *.txt runs, ls has been given a list of names. This is worth proving, because it explains a great deal of otherwise confusing behaviour.

$ touch a.txt b.txt c.log
$ echo *.txt
a.txt b.txt
$ ls -1 *.txt
a.txt
b.txt

echo has no idea about files, and it printed two file names. The shell had already replaced the pattern.

The graphical interface

A desktop is a program too, or rather several: a display server that owns the screen and the mouse, a window manager that decides where windows go and which is in front, and a file manager that draws the icons. On Linux the display server is X11 or Wayland; on Windows and macOS the equivalent is shipped as part of the product and is not separable.

The vocabulary MU's text book uses is worth knowing: the desktop metaphor presents icons for objects, a pointer for selection, windows for the programs, and menus for the available operations. Selecting an icon and choosing an operation is the same request as typing a command; the route from there into the kernel is identical, because the file manager makes the same system calls.

$ startx

The lab machine has no screen, so nothing graphical can be run or shown here. What can be said is what the interface is made of, and that its requests reach the kernel by exactly the system calls of the next chapter.

Distinctions that carry marks

What it does not mean

The shell is not the operating system. It is a program that asks the operating system for things, and it can be replaced without touching the kernel.

A shell script is not a different language from the command line. It is the same commands, in a file.

The graphical interface is not "easier" in every sense. It is easier to start and harder to automate, which is why both survive.

Quick revision

• Two interfaces: the command line, or command interpreter or shell, and the

graphical one. Neither is part of the kernel.

• The shell's loop: print a prompt, read a line, run a built in or find and start a program and

wait, repeat. Step three is fork and exec.

• cd must be built in, because it changes the running process's own directory, and a

separate program could change only its own.

• The shell does redirection, pipes, background running, pattern expansion and variable

substitution itself, with ordinary system calls. The program is handed the result, never the pattern.

• type reports whether a command is a built in, an alias or a file. type -a shows all of

them.

• The graphical interface is a display server plus a window manager plus a file manager, and it

makes the same system calls.

Test yourself

1. Name the two kinds of user interface and say whether either is part of the operating system. The command line interpreter, or shell, and the graphical user interface. Neither is: both are programs that use the operating system.

1. Write the shell's main loop in four steps. Print a prompt; read a line; if it is a built

in do it, otherwise find the program, start it and wait; repeat.

1. Why must cd be a shell built in? It changes the current directory of the process. A

separate program could only change its own, and would then exit, taking the change with it.

1. What does ls *.txt hand to ls? A list of the matching file names. The shell expands

the pattern before ls starts, so ls never sees the asterisk.

1. Give two advantages of the command line over the desktop, and one the other way. It

composes with pipes and it can be repeated in a script; and it works over a slow connection. The desktop lets you find things without knowing their names. 6. A command is both a built in and a program on the disk. Which runs, and how would you get the other? The built in runs. Ask for the other by its full path, for example /usr/bin/echo.

Linux on this machine uses registers, which is why write takes exactly three arguments and why a call needing more, such as mmap with six, is at the practical limit.

A library call is not a system call

This is the distinction the chapter exists for. printf is a function in the C library. write is a system call. printf eventually calls write, but it is not the same thing, and the difference can be measured.

#include <stdio.h>
#include <unistd.h>
#include <string.h>

int main(void)
{
    const char *a = "written by the library, with printf\n";
    const char *b = "written by the system call, with write\n";

    printf("%s", a);
    write(STDOUT_FILENO, b, strlen(b));
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o twoways twoways.c
$ ./twoways
written by the library, with printf
written by the system call, with write

On the screen they look identical. Now send the output to a file instead, and the order changes.

$ ./twoways > out.txt
$ cat out.txt
written by the system call, with write
written by the library, with printf

The lines came out in the wrong order, and that is the proof. printf did not write anything when it was called: it put the text in a buffer inside the C library and returned. The write call went straight to the kernel. Only when the program ended did the library flush its buffer, which is why the library's line is last.

When the output was the screen, the library flushed at every newline, because a terminal is treated as interactive. When the output was a file, it flushed only when the buffer was full or the program ended. Nothing about the kernel changed. The library changed its mind.

This is a real bug students meet. A program that prints with printf and then crashes loses the printed lines, because they were never given to the kernel. A program that prints with write does not.

The count of system calls confirms it: printf called write once, at the end, with both lines buffered together or separately depending on where the output went.

What a system call looks like in the manual

Every system call has a manual page in section 2, and the lab machine also carries the POSIX standard's own page for the same call in section 3p. Reading both is how this book knows what a call promises.

$ man 2 write 2>/dev/null | sed -n '/^SYNOPSIS/,/^DESCRIPTION/p' | head -6
SYNOPSIS
       #include <unistd.h>

       ssize_t write(int fd, const void buf[.count], size_t count);

DESCRIPTION
$ man 3p write 2>/dev/null | sed -n '2,4p'

PROLOG
       This  manual  page is part of the POSIX Programmer's Manual.  The Linux

The first is what Linux does. The second is what every Unix must do. Where they differ, the Linux page says so, and this book says which one it is quoting.

Worked example: counting the doors a simple program uses

/bin/true does nothing at all. It is the simplest program on the machine. Count the system calls it makes.

$ strace -c /bin/true 2>&1 | tail -2
------ ----------- ----------- --------- --------- ----------------
100.00    0.000000           0        27         1 total

Twenty seven system calls to do nothing at all. They are the program being loaded: the kernel finding and opening the C library, mapping it into memory, arranging the stack, and then exiting. Every program pays that, and it is why starting a process is not free, which is the point Chapter thirty one makes about thread pools.

Distinctions that carry marks

What it does not mean

A system call is not slow because it does a lot. It is expensive because of the mode switch and the checking, so a program that makes a million small calls is slower than one that makes a thousand large ones. This is why buffering exists at all.

printf is not "the system call for printing". There is no system call for printing. There is write, which puts bytes somewhere, and printf is a formatting function that ends up calling it.

A system call is not a function in your program that the kernel calls back. The traffic is one way: your program asks, the kernel answers.

The number of system calls is not large. Linux has a few hundred. Everything any program does goes through them.

Quick revision

• A system call is the programming interface to the operating system's services, invoked by a

trap that switches to kernel mode.

• There is one controlled door because the program cannot enter kernel mode itself and cannot

choose where in the kernel it lands.

• The steps: number and arguments in place, trap, mode switch, handler, system call table

lookup, argument check, work, return.

• Arguments are passed in registers, in a block whose address is passed, or on the

stack.

• printf is a library function, write is a system call. Redirecting a program's

output to a file changes the order in which they appear, because the library buffers and the system call does not.

• A system call costs a mode switch, so few large calls beat many small ones.
• Manual section 2 is Linux's system calls; section 3p is the POSIX standard's own page.

Test yourself

1. Define a system call. The programming interface to the services of the operating system,

invoked by a trap instruction that switches the processor into kernel mode and enters the kernel's handler.

1. Why can a program not just call a kernel function directly? The kernel's memory is not

accessible to it and the kernel runs in kernel mode, which the program cannot enter because setting the mode bit is privileged.

1. Name the three ways arguments are passed to a system call. In registers, in a block of

memory whose address is passed in a register, and on the stack. 4. A program prints two lines, one with printf and one with write, and the output is redirected to a file. What order do they appear in and why? The write line first. printf buffered its text in the C library and the buffer was not flushed until the program ended.

1. Why is a system call more expensive than a function call? It switches processor mode twice

and the kernel must check every argument, because the arguments came from a program that may be hostile.

1. /bin/true does nothing, yet makes twenty seven system calls. What are they? The work of

starting a program: opening and mapping the C library, arranging memory, and exiting.

hello from a file

$ gcc -std=c17 -Wall -Wextra -o readone readone.c
$ strace -e trace=openat,read,write,close -o r.txt ./readone
hello from a file
$ tail -5 r.txt
openat(AT_FDCWD, "greeting.txt", O_RDONLY) = 3
read(3, "hello from a file\n", 32)      = 18
write(1, "hello from a file\n", 18)     = 18
close(3)                                = 0
+++ exited with 0 +++

Those are the last five lines: the ones above them are the C library being loaded, exactly as in the trace before. Four calls are the program's own, and every one of them is readable.

• openat returned 3. That is the file descriptor, a small integer the kernel gives the

program to refer to the open file. Descriptors 0, 1 and 2 are already taken: standard input, standard output and standard error. So the first file a program opens is almost always 3.

• read(3, ..., 32) asked for up to 32 bytes and got 18.

The return value is what was actually read, and a program that assumes it got everything it asked for is a broken program.

• write(1, ..., 18) wrote to descriptor 1, standard output, which is why the text appeared on

the screen.

• close(3) gave the descriptor back.

open appears in the trace as openat. The library calls the newer system call, which takes a directory to be relative to, and AT_FDCWD means the current directory. This is a real and common surprise: the name in your program need not be the name of the system call underneath.

Counting, rather than listing

For a large program the list is too long to read. Counting is more useful.

$ strace -c -o c.txt ./readone
hello from a file
$ awk 'NR<3 || $NF ~ /^(openat|read|close|mmap)$/ {print $(NF-1), $NF}' c.txt | sort
--------- ----------------
2 read
3 close
3 openat
6 mmap
errors syscall

The columns are the share of time, the total time, the average per call, the number of calls, the number that returned an error, and the name. The errors column is the one to look at first when a program misbehaves, because a call that failed and was ignored is the commonest cause of mysterious behaviour.

Worked example: why did it not find the file?

This is the use a student will get most value from. A program is given a name that does not exist.

$ rm -f greeting.txt
$ strace -e trace=openat -o miss.txt ./readone
open: No such file or directory
$ grep greeting miss.txt
openat(AT_FDCWD, "greeting.txt", O_RDONLY) = -1 ENOENT (No such file or directory)

The answer is -1 and the reason is ENOENT. A system call reports failure by returning -1 and setting an error number, and perror is the library function that turns that number into the sentence the program printed. Every system call in this book follows that rule, and Chapter twenty one shows the one famous exception, fork, which has three possible answers rather than two.

Distinctions that carry marks

What it does not mean

A trace is not the program's source code. It shows only what crossed the boundary. Everything the program computed between two calls is invisible here, and that is the point.

Timings under strace are not real timings. Every call stops the program twice.

Not every function in your program appears. strlen, malloc and most of printf are library code and make no system call at all, so they leave no trace.

Quick revision

• strace lists every system call a program makes, with arguments and return value. -e trace=

selects calls, -o writes to a file, -c counts instead of listing.

• A program under strace is much slower, so timings taken under it are worthless.
• The first file a program opens usually gets descriptor 3: 0, 1 and 2 are standard input,

output and error.

• read returns how much it actually read, which may be less than was asked for.
• open in a program appears as openat in the trace, with AT_FDCWD for the current

directory.

• A system call reports failure as -1 plus an error number, such as ENOENT. perror prints

it.

• Even /bin/true makes about twenty seven calls: that is the cost of starting any program.

Test yourself

1. What does strace show, and what does it not show? Every system call a program makes,

with arguments and results. It shows nothing that happens inside the program between calls.

1. Why is descriptor 3 the first one a program usually gets? Because 0, 1 and 2 are already

open as standard input, standard output and standard error, and the kernel gives out the lowest free number.

1. read(3, buf, 32) returns 18. What happened, and what must the program do? Eighteen bytes

were available and were read. The program must use the return value rather than assume it got 32, and must call read again if it needs more.

1. A program says it cannot find a file. How would you find out which name it looked for?

Trace it and look at the openat line: the trace shows the exact string and the error, for example -1 ENOENT.

1. How does a system call report failure? It returns -1 and sets an error number, which

perror or strerror turns into a message.

1. Why does strlen never appear in a trace? It is library code that computes in user mode

and makes no request of the kernel.

One from each family, run

Six programs would be six pages. One program makes one call from each family, and the trace shows all six.

#include <stdio.h>
#include <string.h>
#include <sys/utsname.h>
#include <sys/wait.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/stat.h>

int main(void)
{
    /* 1. process control */
    pid_t child = fork();
    if (child == 0) {
        _exit(0);
    }
    wait(NULL);

    /* 2. file management */
    int fd = open("six.txt", O_CREAT | O_WRONLY | O_TRUNC, 0644);
    write(fd, "six\n", 4);
    close(fd);

    /* 3. device management: a device is opened like a file */
    int null = open("/dev/null", O_WRONLY);
    write(null, "into the void\n", 14);
    close(null);

    /* 4. information maintenance */
    struct utsname u;
    uname(&u);

    /* 5. communications */
    int ends[2];
    pipe(ends);
    write(ends[1], "ping", 4);
    char got[8] = {0};
    read(ends[0], got, 4);
    close(ends[0]);
    close(ends[1]);

    /* 6. protection */
    chmod("six.txt", 0600);

    printf("kernel %s, pipe carried %s, all six families used\n", u.sysname, got);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o sixfamilies sixfamilies.c
$ ./sixfamilies
kernel Linux, pipe carried ping, all six families used
$ strace -e trace=clone,wait4,openat,uname,pipe2,fchmodat -o trace6.txt ./sixfamilies > /dev/null
$ grep -E 'clone|wait4|uname|pipe2|chmod|/dev/null' trace6.txt | sed 's/0x[0-9a-f]*/ADDRESS/g'
clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=ADDRESS) = 27
wait4(-1, NULL, 0, NULL)                = 27
openat(AT_FDCWD, "/dev/null", O_WRONLY) = 3
uname({sysname="Linux", nodename="ubuntu", ...}) = 0
pipe2([3, 4], 0)                        = 0
fchmodat(AT_FDCWD, "six.txt", 0600)     = 0
$ ls -l six.txt
-rw------- 1 student student 4 Sep 30 09:37 six.txt

Four names in the program are different names in the trace, and that is the lesson to take from this chapter beside the list. It is also a warning about strace: asking it to trace chmod shows nothing at all, because the call the machine makes is fchmodat.

The permissions at the end are the protection family's work: the file was made with 0644 and ended as 0600, which ls -l shows as -rw-------.

Distinctions that carry marks

What it does not mean

Six families does not mean six hundred calls. Linux has a few hundred in all, and most programs use twenty.

"Device management" does not mean writing a driver. The driver is inside the kernel. This family is how a program asks the driver for something.

Information maintenance is not a small family. It is where a great deal of a modern system's work lives, because so much of what a program wants to know about its environment is a call.

Quick revision

• Six families: process control, file management, device management,

information maintenance, communications, protection.

• They mirror the six functions of Chapter five, seen from the program's side.
• On Unix a device is opened by name under /dev and read and written like a file; ioctl

carries what does not fit.

• The name in your program may not be the name of the system call: fork is clone, wait is

wait4, pipe is pipe2, open is openat.

• One call from each family: fork, open, ioctl, getpid, pipe, chmod.

Test yourself

1. Name the six types of system call, with one example of each. Process control (fork),

file management (open), device management (ioctl), information maintenance (getpid), communications (pipe), protection (chmod).

1. Why do file and device calls look the same on Unix? Because a device is presented as a

name in the file system, so one interface serves both and a program need not know which it has.

1. What is ioctl for? Requests to a device that are not reading or writing, such as setting

the speed of a serial line or the size of a terminal.

1. You wrote fork and the trace says clone. Is that an error? No. Linux implements

process and thread creation with one call, clone, and fork is a particular set of its flags. The same happens to wait, which is wait4, to pipe, which is pipe2, to open, which is openat, and to chmod, which is fchmodat.

1. Which family does getrusage belong to and what does it report? Information maintenance.

It reports the resources a process has used, which is the accounting service of Chapter seven.

1. A program wants to know whether it may read a file before trying. access, in the

protection family. It answers the question without opening the file.

The second loss is why pure layering was abandoned, and the reason is worth knowing because it is a favourite question. Consider which layer holds the disk driver and which holds the memory manager. The memory manager needs the disk, to swap pages out. The disk driver needs memory, for its buffers. Each needs the other, so neither can be below the other, and a pure hierarchy is impossible.

Later systems kept a small number of layers rather than many, which is why you will read that layering "influenced" modern designs rather than that it is used.

The size of the boundary, measured

Whatever the inside looks like, the boundary a program sees is the system call interface, and it is worth knowing how wide that door is.

$ man 2 syscalls 2>/dev/null | grep -cE '^ +[a-z_0-9]+\(2\)'
484
$ ls /usr/include/asm-generic/unistd.h
/usr/include/asm-generic/unistd.h
$ grep -c '^#define __NR_' /usr/include/asm-generic/unistd.h
355

A few hundred numbered requests, listed in one header file, is the whole interface between every program on the machine and the operating system. Everything in the rest of this book happens on the far side of it.

Distinctions that carry marks

What it does not mean

"Structure" is not about source files. Every kernel is organised into files and directories. The question is which parts may call which, and whether anything enforces it.

Layering is not dead. Almost every modern kernel is layered in places, for example the file system sitting on the block layer sitting on the driver. What was abandoned is the rule that the whole kernel must be a strict hierarchy.

A monolithic kernel is not a small kernel. It is one address space, and Linux's is millions of lines.

Quick revision

• Simple structure: no boundaries at all, MS-DOS. Fast, tiny, no protection.
• Monolithic: one program in one address space in kernel mode, original UNIX. Fast

internally, a fault anywhere can damage anything, hard to change.

• Layered: layer n uses only layer n minus one. Each layer built on proved ground, a fault is

localised, but every request passes through every layer and the ordering problem is real: the memory manager needs the disk and the disk driver needs memory.

• Every structure is a trade: a clean division costs a call across the division.
• The system call interface is a few hundred numbered requests, and that is the whole door.

Test yourself

1. What is a monolithic kernel? One in which the whole operating system is a single program

running in kernel mode in one address space, with a system call boundary to user programs and no enforced boundary inside.

1. Give the advantage and the disadvantage of a layered structure. Each layer is built and

debugged on layers already known to work, so a fault is localised. Every request passes through every layer, which costs time, and deciding which layer a service belongs in is genuinely hard.

1. Why can a kernel not be strictly layered? Because some pairs of services need each other:

the memory manager needs the disk driver to swap, and the disk driver needs memory for its buffers, so neither can be below the other.

1. What did MS-DOS lack, and why? Any protection boundary. The hardware it was written for

had no mode bit, so there was nothing to enforce one with.

1. Does "monolithic" mean disorganised? No. It means there is no enforced boundary inside the

kernel. The organisation may be excellent, but it is a convention rather than a rule.

The gain over pure layering is that a module may call any other module directly, so there is no hierarchy to get wrong. The gain over a fixed monolithic kernel is that a machine only carries the drivers for the hardware it has.

$ head -5 /proc/filesystems
nodev	sysfs
nodev	tmpfs
nodev	bdev
nodev	proc
nodev	cgroup
$ cat /proc/sys/kernel/osrelease
6.8.0-117-generic

The kernel publishes the list of file system types it is able to mount, and every entry on it is a part of the kernel that is either built in or was loaded as a module. Dozens of kinds of file system from one kernel is what modularity buys: a machine carries the ones it uses and no more.

The lab machine is a container, so it shares its host's kernel and cannot load or unload a module of its own. What it can show is the mechanism's own rule, which is that a module is built for one kernel version: the version is published in that last file, and modules for a kernel are kept in a directory named after it.

The hybrid, which is what everything actually is

No shipped operating system is purely any of the five structures. Each one picks what it wants:

So the honest answer to "what structure is Linux" is "monolithic with loadable modules", and to "what structure is macOS" is "hybrid". An examination answer that says any real system is a pure microkernel is wrong.

Worked example: adding support for a new device, three ways

A new kind of camera is to be supported.

In a monolithic kernel with no modules: the driver is added to the kernel's source, the kernel is rebuilt, and the machine is restarted. Everybody who wants the camera runs a kernel containing the driver, whether they have a camera or not.

In a microkernel: the driver is written as an ordinary program. It is started like any other program. If it is wrong, it crashes, and nothing else does. The kernel is untouched.

In a modular kernel: the driver is built as a module against this kernel's version. It is loaded when the camera is plugged in and unloaded when it is removed. It runs in kernel mode, so a serious fault in it can still bring the machine down, but no machine carries it unless it has the hardware.

The third is the compromise the industry chose: the speed of the second chapter's monolithic kernel with most of the flexibility of the microkernel, and none of its protection.

Distinctions that carry marks

What it does not mean

A microkernel is not a small monolithic kernel. The difference is not size, it is where the services run: in user mode as processes, or in kernel mode.

A module is not a user program. It is kernel code and has all the kernel's power.

"Hybrid" is not a way of avoiding the question. It is the accurate answer, and naming what each system took from where is the marks.

Quick revision

• A microkernel keeps only minimal process management, minimal memory management and

communication; everything else runs as a user mode server process.

• The cost is four boundary crossings instead of two; the benefit is that a driver fault kills

one process. Mach, QNX, MINIX 3.

• A modular kernel is one address space with parts that load and unload while running. A

module runs in kernel mode and is not a process. Linux, Solaris.

• A module is built for one kernel version, which is why modules live in a directory named after

the version.

• Every real system is a hybrid. Linux is monolithic with loadable modules; macOS is Mach

plus BSD plus extensions; Windows is a layered hybrid with drivers in kernel mode.

Test yourself

1. What does a microkernel keep, and what does it move out? It keeps minimal process

management, minimal memory management and inter-process communication. File systems, drivers and the network stack move out into user mode server processes.

1. Why must a microkernel's message passing be fast? Because every service request becomes

messages through the kernel: four crossings of the user and kernel boundary instead of two.

1. Give the main advantage and the main disadvantage of a microkernel. A failing driver kills

only its own process, and services can be added without touching the kernel. The cost is performance.

1. Distinguish a kernel module from a microkernel server. A module is kernel code in kernel

mode in the kernel's address space, called as a function. A server is an ordinary user mode process reached by messages.

1. What structure is Linux? Monolithic with loadable modules. One kernel address space for

speed, with parts loaded and unloaded while the machine runs.

1. Where does a kernel publish what it can do? In /proc. The list of file system types it

can mount is one such list, and every entry is either built in or was loaded as a module.

1. Why is a module built for one particular kernel version? Because it becomes part of that

kernel and uses its internal interfaces, which are not promised to stay the same. That is why modules are stored in a directory named after the kernel's version.

$ gcc -std=c17 -Wall -Wextra -o showmap showmap.c
$ ./showmap | head -3
code   below global : yes
global below heap   : yes
heap   below stack  : yes

Those three answers are yes on every machine and on every run. The code is lowest, the global just above it, the heap higher still, and the local variable on the stack at a completely different, much larger address. That gap is the room the heap and the stack have to grow into, and it is why the two are at opposite ends.

The addresses themselves are not a fact about every run, and the program can be made to prove it.

$ a=$(./showmap | awk '/^stack/ {print $2}')
$ b=$(./showmap | awk '/^stack/ {print $2}')
$ [ "$a" != "$b" ] && echo "the stack was at a different address on the two runs"
the stack was at a different address on the two runs

The program was run twice and its stack was somewhere else each time. The kernel deliberately puts a program's pieces at random addresses, a defence called address space layout randomisation, so that an attacker who knows a program's code cannot know where anything is. That is why this book prints the order of the addresses rather than the addresses: the order is a fact about every run, and the numbers are a fact about one.

The kernel's own map of a process says the same thing with names instead of numbers. Every line is one region of memory: its address range, its permissions, and what it is.

$ awk '/\[heap\]|\[stack\]/ || (/r-xp/ && !seen++) {print $2, $6}' /proc/self/maps
r-xp /usr/bin/gawk
rw-p [heap]
rw-p [stack]

r-xp is readable and executable but not writable: that is the text section, and the kernel enforces the read only rule with the memory management unit of Chapter sixty eight. [heap] and [stack] are named by the kernel itself, and their addresses are as far apart as the four numbers above suggested.

That map belongs to the awk that printed it, because a process can only read its own. The shape is the same for every process on the machine.

Worked example: one program, three processes

Sunita opens three windows and runs the same calculator in each.

There is one file on the disk, /usr/bin/calculator. There are three processes. Each has:

• its own process id, a number the kernel gives it;
• its own data, heap and stack, so the number typed in one window is not in the

others;

• its own program counter, so one may be halfway through a multiplication while another waits

for a keystroke;

• its own entry in the kernel's tables.

They share one thing: the text. The instructions are identical and are read only, so the kernel maps the same physical memory into all three. That is a saving of two thirds and it is done without the processes knowing; Chapter eighty three is the general mechanism.

A favourite examination trap: whether two processes running the same program share their variables. They do not. They share the instructions. Every variable is private.

Distinctions that carry marks

What it does not mean

A process is not a program with extra features. It is a different kind of thing: the program is the recipe and the process is the cooking.

The stack is not "the memory". It is one of four sections, and it holds only the frames of the function calls currently in progress. A local variable disappears when its function returns, which is exactly why returning a pointer to one is a bug.

A process id is not a program's identity. It is given out by the kernel when the process starts and is reused after it ends. The same program gets a different number every time.

Quick revision

• A program is a passive file; a process is a program in execution, an active entity with

a program counter, a stack and its own data.

• Four sections of memory: text (instructions, read only), data (variables for the whole

run), heap (asked for while running), stack (one frame per call).

• The heap and the stack grow towards each other from opposite ends, so neither has a fixed

boundary.

• One program can be many processes; they share the text and share nothing else.
• A process has a process id, an owner and a parent. A program has none of those.
• Deleting the file does not stop the process.

Test yourself

1. Define a process, and distinguish it from a program. A process is a program in execution:

an active entity with a program counter, a stack and its own data. A program is passive, a file of instructions on disk.

1. Name the four sections of a process's memory and say what each holds. Text, the

instructions; data, variables that last the whole run; heap, memory asked for while running; stack, a frame per function call holding arguments, locals and the return address.

1. Why are the heap and the stack at opposite ends of the address space? So that each can

grow without a fixed boundary between them. They meet only when the process is out of memory.

1. Three windows run the same program. What is shared and what is not? The text is shared,

read only, as one copy in physical memory. Everything else, data, heap, stack, registers, process id, is separate.

1. A local variable's address is much larger than a global's. Why? The local is on the stack,

which is placed at the high end of the address space, and the global is in the data section, just above the code at the low end.

1. Is a process id a permanent name for a program? No. The kernel gives it out when the

process starts and may reuse it after the process ends.

running long enough to ask for it.

Written as a diagram, in words

The diagram to draw has five boxes. New at the top left with an arrow marked admit to Ready. Ready and Running side by side in the middle, with dispatch from Ready to Running and interrupt back the other way. Waiting below them, with input or output wait from Running down to Waiting and input or output complete from Waiting back up to Ready. Terminated at the top right, with exit from Running.

If you can label all six arrows you have the question. The two arrows that do not exist are worth a sentence underneath.

The states a real machine reports

Linux does not use those five words. It reports a letter per process, and the letters are worth knowing because a practical question will show you ps output.

$ set +m
$ sleep 30 & s=$!
$ yes > /dev/null & y=$!
$ sleep 0.3
$ ps -o pid,stat,comm -p $s -p $y --no-headers
     13 S+   sleep
     15 R+   yes
$ kill -STOP $y 2>/dev/null
$ sleep 0.2
$ ps -o pid,stat,comm -p $y --no-headers
     15 T+   yes
$ kill -CONT $y 2>/dev/null
$ kill $s $y 2>/dev/null
$ wait 2>/dev/null

Two processes were started on purpose. sleep is waiting for time to pass, so it prints S. yes computes without stopping, so it prints R. Then yes was sent a stop signal and printed T, and was let go again.

The suffixes matter less but are asked: s means the process leads a session, + means it is in the foreground, l means it has more than one thread.

R covers two of the five states. A process on the processor and a process merely able to run both print R, because from the kernel's point of view they are in one queue and only one of them happens to be executing. A student who expects a separate letter for ready will not find one.

D is the state to recognise in real life. A process in uninterruptible sleep cannot even be killed, because it is inside the kernel waiting for hardware. If a machine has a process stuck in D, the disk or the network is the problem, not the program.

Worked example: following one process through all five

Ramesh types sort bigfile.txt at the prompt.

1. New. The shell asks the kernel to make a process. The kernel allocates a process id,

builds its records, and sets up its memory. The process exists but has not executed an instruction.

1. Ready. The kernel admits it. It joins the queue of processes that could run.
2. Running. The scheduler chooses it. It executes: it asks to open the file.
3. Waiting. The file's first block is not in memory, so the kernel starts a disk read and the

process can do nothing until it arrives. It moves to waiting, and the scheduler gives the processor to somebody else. This is the step students skip, and it is the reason the state exists.

1. Ready. The disk interrupts. The block has arrived. The process becomes ready.
2. Running. Chosen again, it sorts what it has.
3. Steps 4 to 6 repeat for every block of the file, perhaps thousands of times.
4. Running to Ready whenever its quantum expires, perhaps hundreds of times.
5. Terminated. It has printed the sorted lines and calls exit. The kernel keeps its exit

status until the shell collects it, then removes its records.

Count the transitions in that story: a program that looks like one thing happening moved between states thousands of times.

Distinctions that carry marks

What it does not mean

"Waiting" does not mean waiting for the processor. That is ready. Waiting means waiting for something else.

A terminated process is not immediately gone. Its exit status has to be collected by its parent first, which is why the zombie state exists.

New is not a long state. It lasts as long as it takes to build the records, unless the system is so loaded that the long term scheduler refuses to admit more work.

Quick revision

• Five states: new, ready, running, waiting (or blocked), terminated.
• Ready needs only the processor; waiting needs an event and could not use the processor.

That is why they are separate: the scheduler chooses only from the ready.

• Six transitions: admit, dispatch, interrupt, input or output wait, input or output complete,

exit.

• Waiting to Running does not exist (it goes to ready first), and

Ready to Waiting does not exist (it must run to ask).

• On one processor exactly one process is running.
• Linux prints R for both running and ready, S for interruptible sleep, D for

uninterruptible sleep, T for stopped, Z for zombie.

• A process in D cannot be killed: the hardware it is waiting for is the problem.

Test yourself

1. Name the five states of a process. New, ready, running, waiting or blocked, and

terminated.

1. Why are ready and waiting separate states? A ready process could use the processor at

once; a waiting one could not, because it is waiting for an event. The scheduler chooses only from the ready ones, so giving the processor to a waiting process would waste it.

1. Name the six transitions with their events. New to ready on admit; ready to running on

dispatch; running to ready on interrupt or quantum expiry; running to waiting on an input or output request; waiting to ready on input or output completion; running to terminated on exit.

1. Can a process go from waiting straight to running? No. It becomes ready and must be chosen

by the scheduler like any other ready process.

1. ps shows R for a process. Which of the five states is it in? Either running or ready.

Linux does not distinguish them in that column.

1. A process is stuck in state D and kill does nothing. What does that tell you? It is in

uninterruptible sleep inside the kernel, waiting for hardware. The device, not the program, is the problem.

how much of it is actually in physical memory.

• Threads is 1, so this process has one thread (Chapter twenty six).
• voluntary_ctxt_switches is the count of times it gave the processor up by itself, which is

scheduling information.

• The directory of numbered files is its input and output status: the open descriptors 0, 1

and 2, which are standard input, standard output and standard error.

The program counter and the registers are not in that file, and they cannot be: they are the process's private state and publishing them would be a security hole. They live in the kernel's own copy of the block.

Where the blocks live

The kernel keeps every process control block in a table, and in Linux the table is a doubly linked list, so that the scheduler can walk it. The size of the table is the limit on how many processes the machine can have.

$ cat /proc/sys/kernel/pid_max
4194304
$ ps -e --no-headers | wc -l
5

The first number is the largest process id this kernel will give out, and the second is how many processes exist at this moment. On a quiet container there are a handful; on a desktop there are several hundred, and every one of them has a block.

Worked example: what a context switch actually copies

P1 is running and the timer fires. The kernel must switch to P2. Exactly this happens, and every step touches a control block.

1. The processor traps into the kernel, which saves the program counter and the flags

automatically as part of taking the interrupt.

1. The kernel's switch routine copies every remaining register into P1's control block.
2. It copies P1's state from running to ready, and appends P1 to the ready queue.
3. It updates P1's accounting: add the ticks P1 just used.
4. It chooses P2 from the ready queue, using P2's scheduling information.
5. It loads P2's memory management information into the hardware, which on a paged machine

means pointing the memory management unit at P2's page table. This is usually the most expensive step, because the translation cache must be emptied (Chapter seventy six).

1. It copies every register out of P2's control block into the processor.
2. It sets P2's state to running and returns from the interrupt, which restores P2's program

counter. P2 resumes at the instruction it was interrupted at, perhaps a second ago, and cannot tell.

Count what that cost: two blocks read or written in full, one queue operation, one page table switch, and pure overhead throughout. No user work is done during a context switch, which is why Chapter four's arithmetic about the quantum matters and why Chapter twenty seven's threads are attractive: two threads of one process share step 6, so switching between them is much cheaper.

Distinctions that carry marks

What it does not mean

The control block is not the process. It is the kernel's record of it. The process is the memory and the execution.

A process cannot read its own control block directly. It can ask the kernel for parts of it, which is what getpid and getrusage do, and on Linux it can read the published parts through /proc.

Switching is not free because the block is small. Most of the cost is the memory management information in step 6, not the registers.

Quick revision

• The process control block, also task control block, is the kernel's record of one process.
• The test of what belongs in it: would the process notice if this were lost?
• Fields: process state, process id, program counter, registers, scheduling

information, memory management information, accounting information, input and output status.

• The program counter is listed separately because its loss is unrecoverable.
• Linux publishes much of it as /proc/<pid>/status, and the open descriptors as

/proc/<pid>/fd. The registers are not published.

• A context switch saves one block, chooses from the queue, loads another block, and switches the

memory mapping. All of it is overhead, and the memory mapping is usually the most expensive part.

Test yourself

1. What is a process control block? The record the operating system keeps about a process,

holding everything needed to suspend it and resume it without the process noticing.

1. List its contents. Process state, process id, program counter, registers, scheduling

information such as priority, memory management information such as the page table, accounting information, and input and output status including open files.

1. Why is the program counter always named separately from the registers? Because it is the

one whose loss cannot be recovered from: without it there is no way to know where to resume.

1. Give the test for whether something belongs in the block. Would the process notice if it

were lost? If so, it belongs.

1. Which step of a context switch is usually the most expensive, and why? Switching the

memory management information, because the hardware's translation cache has to be emptied and refilled.

1. Can a process read its own control block? Not directly. It can ask the kernel for parts of

it with system calls, and on Linux read the published parts under /proc.

A system holding only one kind is badly used. All processor bound, and the disk is idle and the ready queue is long. All input and output bound, and the processor is idle while everybody waits. The long term scheduler tries for a mixture so that both are busy, and that sentence is a complete answer to a standard question.

The context switch

Switching the processor from one process to another means saving the old process's state into its control block and loading the new one's, exactly as Chapter sixteen's worked example sets out.

A context switch is pure overhead. During it the machine does no user work at all. Its cost is a few microseconds, and it depends on the hardware: a machine with several sets of registers can switch by changing which set is in use, and a machine with one set must copy.

The machine keeps its own count of switches, and so does every process.

$ awk '/^ctxt/ {print "context switches since boot:", $2}' /proc/stat
context switches since boot: 75038804
$ a=$(awk '/^ctxt/{print $2}' /proc/stat); sleep 1; b=$(awk '/^ctxt/{print $2}' /proc/stat)
$ echo "$((b - a)) context switches in one second on an idle machine"
4607 context switches in one second on an idle machine
$ vmstat 1 2 | tail -1 | awk '{print "vmstat agrees, cs =", $12}'
vmstat agrees, cs = 1326

Thousands a second with nothing happening. On a busy machine it is hundreds of thousands, and at some point the overhead becomes visible, which is why the number is worth watching.

A single process's own counts are published too, and they are worth reading because they separate the two reasons for switching.

$ set +m
$ sleep 5 & job=$!
$ sleep 0.2
$ grep ctxt /proc/$job/status
voluntary_ctxt_switches:	1
nonvoluntary_ctxt_switches:	1
$ wait 2>/dev/null

• Voluntary switches are the process blocking on its own: Chapter fifteen's running to

waiting.

• Nonvoluntary switches are preemption: running to ready, done to it by the timer.

Those two counts diagnose a program. A program with a huge voluntary count is waiting for devices and is input and output bound. A program with a huge nonvoluntary count is computing and is being preempted, so it is processor bound. The vocabulary of the previous section becomes two numbers you can read.

Worked example: the queues, followed

A machine has one processor. P1 is computing. P2 is waiting for the disk. P3 is ready. P4 has just been typed at a terminal.

• Job queue: P1, P2, P3, P4. Everything.
• Ready queue: P3.
• Disk's device queue: P2.
• Running: P1.

Now three things happen in turn.

1. The timer fires and P1's quantum is over. P1 moves running to ready and joins the ready

queue behind P3. The short term scheduler takes P3. P3 runs. This is a nonvoluntary switch for P1.

1. The disk finishes P2's read and interrupts. The kernel takes P2 out of the disk's device

queue and puts it in the ready queue. P2 does not start running: Chapter fifteen's rule.

1. P3 asks to read a file. P3 moves running to waiting and joins the disk's device queue.

This is a voluntary switch. The scheduler chooses from the ready queue, which now holds P1 and P2.

Three events, four queue operations, two context switches, and no user work done during either switch.

Distinctions that carry marks

What it does not mean

"Process scheduling" in MU's label is not the algorithms. It is the queues and the switching. The algorithms are her CPU Scheduling row.

The ready queue is not necessarily first in first out. It is a queue in the sense of a place to wait. Chapters forty seven to fifty three are seven different ways of choosing from it.

A context switch is not a system call. It is something the kernel does to a process, usually because of an interrupt.

Degree of multiprogramming is not the number of processors. It is the number of processes in memory.

Quick revision

• Three queues: the job queue (everything), the ready queue (ready processes), and a

device queue per device. There is no single waiting queue.

• Three schedulers: long term or job scheduler, admits processes and controls the

degree of multiprogramming; short term or CPU scheduler, chooses from the ready queue every few milliseconds; medium term, swaps a process out of memory for a while.

• The long term scheduler wants a mixture of input and output bound and

processor bound processes, so that neither the devices nor the processor is idle.

• A context switch saves one control block and loads another. It is pure overhead.
• /proc/stat's ctxt counts every switch on the machine; /proc/<pid>/status separates a

process's voluntary switches (it blocked) from its nonvoluntary ones (it was preempted).

Test yourself

1. Name the three kinds of queue and say what each holds. The job queue holds every process

in the system; the ready queue holds the processes ready to run; a device queue holds the processes waiting for one particular device.

1. Why is there no single waiting queue? Because when a device interrupts, the kernel must

wake the processes waiting for that device and nobody else.

1. Distinguish the long term from the short term scheduler. The long term, or job, scheduler

decides which processes are admitted into memory and so controls the degree of multiprogramming; it runs seldom and may take its time. The short term, or CPU, scheduler chooses which ready process runs next; it runs every few milliseconds and must be very fast, because it is overhead.

1. What is the degree of multiprogramming and who controls it? The number of processes in

memory at once. The long term scheduler, admitting them, and the medium term scheduler, swapping them out. 5. Why does the long term scheduler want a mixture of processor bound and input and output bound processes? So that both the processor and the devices stay busy. All of one kind leaves the other resource idle. 6. A process shows 40,000 voluntary and 12 nonvoluntary context switches. What kind of process is it? Input and output bound: it is giving the processor up by itself, over and over, because it is waiting for devices rather than computing.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void)
{
    printf("before the fork, I am process %d\n", getpid());

    pid_t r = fork();

    if (r < 0) {
        perror("fork");
        return 1;
    }
    if (r == 0) {
        printf("child : fork returned %d, I am %d, my parent is %d\n",
            r, getpid(), getppid());
        printf("child : this line is printed by process %d\n", getpid());
        return 0;
    }
    wait(NULL);                           /* let the child finish and speak first */
    printf("parent: fork returned %d, I am %d\n", r, getpid());
    printf("parent: this line is printed by process %d\n", getpid());
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o twosides twosides.c
$ ./twosides
before the fork, I am process 21
child : fork returned 0, I am 22, my parent is 21
child : this line is printed by process 22
parent: fork returned 22, I am 21
parent: this line is printed by process 21

Read it carefully, because four things are in those four lines.

1. "Before the fork" was printed once. There was one process then.
2. The last line was printed twice, once by each process, because both of them reached it.
3. The child's fork returned 0 and the parent's returned the child's id, 21.
4. The child's parent id is the parent's id. The family relationship is recorded in the

kernel.

The wait at the end of the parent is not optional, and leaving it out was tried. Without it the parent often finished first, and the child's getppid() then answered 1 instead of 20, because a child whose parent has gone is given to the process the kernel keeps for the purpose. That is the orphan of the next chapter, and it appeared here by accident, which is the honest way to meet it.

The order of the last two lines is not guaranteed. Both processes are ready; which the scheduler runs first is its business. Run it twenty times and you will see both orders. A program that depends on the order is wrong, and Chapters thirty three to forty two are about that problem.

Counting: how many processes does a loop of forks make?

A favourite examination question, and the answer is a power of two.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void)
{
    for (int i = 0; i < 3; i++) {
        if (fork() < 0) {
            perror("fork");
            return 1;
        }
    }
    printf("hello from %d\n", getpid());
    while (wait(NULL) > 0) {
        /* collect every child before finishing */
    }
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o howmany howmany.c
$ ./howmany | wc -l
8

Eight lines, so eight processes, from three forks.

The reason, and the general rule. After the first fork there are 2 processes. Both reach the second fork, so there are 4. All four reach the third, so there are 8. n forks in a loop give 2 to the power n processes, of which 2 to the power n minus 1 are new children. Three forks give eight processes and seven children.

The mistake to avoid: answering "three children". The children fork too.

Worked example: how a shell runs a command

This is what step 3 of Chapter eight's shell loop really does.

1. The shell reads ls.
2. The shell calls fork. There are now two shells, identical.
3. In the child (fork returned 0), the child calls exec to replace itself with ls. That

is the next chapter.

1. In the parent (fork returned the child's id), the shell calls wait on that id, and

blocks. It moves to the waiting state of Chapter fifteen.

1. ls runs and exits.
2. The kernel wakes the shell. wait returns. The shell prints a new prompt.

Why fork and exec are two calls rather than one is the deepest question in this chapter, and it is asked. Because between step 2 and step 3 the child is a copy of the shell and can change things about itself before becoming ls: it can open a file and make it descriptor 1, so that the output goes to a file; it can close descriptors; it can change directory. All of shell redirection lives in that gap. One combined call to "run a program with these settings" would need a parameter for every setting anyone might ever want.

Distinctions that carry marks

What it does not mean

fork does not start the program again from the beginning. The child begins where the parent was, at the return from fork. Nothing above the call runs twice.

fork does not make the child run first, or second. Which runs first is the scheduler's business.

fork does not copy the memory immediately in a real system. Copying megabytes that are usually thrown away at once by exec would be waste, so the kernel marks it copied and copies only what is written to. That is copy on write, Chapter eighty three, and it is why fork is fast.

A failed fork is not impossible. The system may be out of process slots or out of memory, and fork then returns -1. Every one of these programs checks.

Quick revision

• fork creates a new process by copying the caller. It returns twice.
• It returns 0 in the child, the child's process id in the parent, and -1 on failure.
• Copied: data, heap, stack, registers, descriptors. Shared: the text, read only, and the

open files the copied descriptors refer to, including the file position.

• The child gets a new process id; its parent id is the caller's id.
• n forks in a loop give 2 to the power n processes. Three forks give eight.
• The order in which parent and child run is not defined.
• fork and exec are separate so that the child can change its own settings, which is where

all shell redirection happens.

• Real systems do not copy the memory at once: they use copy on write.

Test yourself

1. What does fork return, and where? 0 in the child, the child's process id in the parent,

and -1 in the parent if it failed.

1. Why does it return twice? Because it copies the whole process including the program

counter, so the copy is also in the middle of returning from the call.

1. A program calls fork four times in a loop. How many processes exist at the end? Sixteen,

of which fifteen are children. 4. Parent and child both write to standard output, which is redirected to a file. What happens? The descriptors were copied but refer to one open file, so both writes go to the same file and the file position is shared. The output interleaves.

1. Why are fork and exec two calls? So that between them the child can change its own

environment, for example opening a file as descriptor 1 to redirect the output, before turning itself into the new program.

1. Which runs first after a fork? Undefined. Both are ready and the scheduler chooses.

fork then exec, in one program

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void)
{
    printf("shell : I am %d, about to run wc\n", getpid());
    fflush(stdout);                       /* see the note below */

    pid_t child = fork();
    if (child < 0) {
        perror("fork");
        return 1;
    }
    if (child == 0) {
        printf("child : I am %d, and I am about to become wc\n", getpid());
        fflush(stdout);
        execlp("wc", "wc", "-l", "lines.txt", NULL);
        perror("execlp");                 /* reached only if exec failed */
        _exit(127);
    }
    int status = 0;
    wait(&status);
    printf("shell : child %d finished with status %d\n", child,
        WEXITSTATUS(status));
    return 0;
}

one
two
three

$ gcc -std=c17 -Wall -Wextra -o forkexec forkexec.c
$ ./forkexec
shell : I am 24, about to run wc
child : I am 25, and I am about to become wc
3 lines.txt
shell : child 25 finished with status 0

Three observations, and each is examinable.

1. The child printed a line and then stopped being itself. The printf after execlp never

ran, and neither did perror, because the exec succeeded and the program was gone.

1. wc printed as process 21, the same process the child was. The parent waited for 21 and

got it.

1. fflush is not decoration. Chapter nine showed that printf buffers. A buffer is part of

the program's data, so exec throws it away unflushed, and the line would have been lost. The same happens across fork, where the buffer is copied and the line is printed twice.

That third point is the bug this chapter exists to prevent. A printf before a fork or an exec, with output going to a file, is printed twice or not at all. Flush, or use write.

Redirection, which is the whole reason for the gap

Now the thing Chapter eight promised. The child changes descriptor 1 before exec, and the new program never knows.

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void)
{
    pid_t child = fork();

    if (child == 0) {
        int fd = open("count.txt", O_CREAT | O_WRONLY | O_TRUNC, 0644);
        dup2(fd, STDOUT_FILENO);          /* make the file descriptor 1 */
        close(fd);
        execlp("wc", "wc", "-l", "lines.txt", NULL);
        _exit(127);
    }
    wait(NULL);
    printf("wc wrote nothing to the screen. the file holds:\n");
    fflush(stdout);
    execlp("cat", "cat", "count.txt", NULL);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o redirect redirect.c
$ ./redirect
wc wrote nothing to the screen. the file holds:
3 lines.txt

wc was given no file to write to and no flag. It wrote to descriptor 1, as it always does. The child had quietly made descriptor 1 be the file, with dup2, before becoming wc. That is exactly what the shell does when you type wc -l lines.txt > count.txt, and it is why fork and exec are two calls.

Notice the last line of the parent: it execs cat, so the parent becomes cat and never returns. There is no return 0 reached. The process ends as cat.

Distinctions that carry marks

What it does not mean

exec is not slow because it loads a program. On a paged system it maps the file rather than reading it, and pages arrive as they are touched (Chapter eighty one).

A failed exec is not a crash. It returns -1 like any call, and the program is still the old one, which is why the error must be handled: usually by exiting, because the child has nothing useful left to do.

exec does not close your files. They survive, on purpose. A descriptor that should not survive is marked close on exec when it is opened.

Quick revision

• exec replaces the program running in a process. It creates nothing, and

a successful exec never returns.

• Survives: process id, parent, open descriptors, current directory, user. Replaced: text, data,

heap, stack, registers, signal handlers.

• Six forms, from three letters: l list, v vector, p search the path, e supply the

environment. execve is the real system call.

• The first argument is given twice: what to run, and what the program's own argument zero should

be.

• Flush before fork or exec, or a buffered printf is lost or printed twice.
• Redirection is done in the gap between fork and exec, with dup2, and the new program

never knows.

Test yourself

1. What does exec do, and how many processes exist afterwards? It replaces the program

running in the calling process. One process exists, with the same id.

1. Why does a successful exec never return? Because the code that would receive the return

value has been replaced by the new program.

1. What does the line after exec mean? That the exec failed. It is an error path, and

should report and exit.

1. Explain the letters in execlp. l for a list of arguments written out in the call, p

for searching the path so that a bare program name works.

1. How does the shell implement command > file? It forks; in the child it opens the file

and makes it descriptor 1 with dup2; then it execs the command, which writes to descriptor 1 as usual and knows nothing about the redirection.

1. Why must you flush before forking? Because the C library's output buffer is part of the

process's data. After a fork both copies hold it and both print it; after an exec it is thrown away unprinted.

$ gcc -std=c17 -Wall -Wextra -o collect collect.c
$ ./collect
child 22 exited normally with status 42
child 23 was killed by signal 6

Signal 6 is SIGABRT, which is what abort raises. The parent learned how each child ended, not merely that it had.

wait waits for any child and blocks until one ends. waitpid waits for a particular child, and with the flag WNOHANG it asks without blocking, which is how a program collects children while getting on with its own work.

A zombie, made and then cleaned up

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void)
{
    pid_t child = fork();

    if (child == 0) {
        exit(0);                          /* the child ends at once */
    }
    FILE *note = fopen("child.pid", "w");   /* so the shell can find it below */
    fprintf(note, "%d\n", child);
    fclose(note);

    printf("child %d has exited and I am NOT collecting it yet\n", child);
    fflush(stdout);
    sleep(2);                             /* the parent does something else */

    wait(NULL);                           /* now collect */
    printf("collected. it is gone from the table\n");
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o zombie zombie.c
$ set +m
$ ./zombie &
$ sleep 1
child 37 has exited and I am NOT collecting it yet
$ ps -o pid,ppid,stat,comm -p "$(cat child.pid)" --no-headers
     37      35 Z+   zombie
$ wait 2>/dev/null
collected. it is gone from the table
$ ps -o pid,stat,comm -p "$(cat child.pid)" --no-headers
$ echo "the table no longer has it"
the table no longer has it

Z in the state column, and ps shows it as still named. Two seconds later the parent called wait, the record was released, and ps found nothing at all.

A zombie is cleaned up by its PARENT calling wait, and by nothing else. You cannot kill a zombie: it is already dead, and a signal to a dead process does nothing. The only two ways it goes are the parent collecting it, or the parent dying, after which the kernel's own process adopts it and collects it immediately. So a machine full of zombies is fixed by fixing or restarting the parent.

An orphan, and who adopts it

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <unistd.h>

int main(void)
{
    pid_t child = fork();

    if (child == 0) {
        FILE *log = fopen("orphan.log", "w");
        fprintf(log, "child : while my parent lived it was %d\n", getppid());
        fflush(log);
        sleep(2);                         /* outlive the parent */
        fprintf(log, "child : now my parent is %d\n", getppid());
        fclose(log);
        return 0;
    }
    printf("parent: I am %d and I am leaving now\n", getpid());
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o orphan orphan.c
$ ./orphan
parent: I am 57 and I am leaving now
$ sleep 3
$ cat orphan.log
child : while my parent lived it was 57
child : now my parent is 1

The child wrote to a file rather than to the screen, because it wakes up two seconds after the session has moved on and a line arriving in the middle of somebody else's output proves nothing. Read its two lines: the child's parent changed under it. A process whose parent dies is re-parented, on Linux to the nearest ancestor that has asked for the job, or otherwise to process 1, the first process the kernel started. That process's whole remaining duty is to wait for whatever it inherits, which is why orphans never become permanent zombies.

An orphan is not an error. A program deliberately made an orphan of itself is how a daemon is written: fork, let the parent exit, and the child runs on with no terminal and no parent.

Cascading termination, which is the other policy

A question asks for the term, and the answer is a comparison with what this chapter has just measured. When a parent dies, a system must decide what happens to its children, and there are two answers.

Cascading termination is initiated by the operating system, not by the child, and its point is that no process is left running with nobody to collect it. Linux does not do it by default, which is why the orphan above kept running and printed its line after its parent had gone.

Distinctions that carry marks

What it does not mean

A zombie is not using the processor. It is a record. The name is theatrical; the cost is one process id.

Killing a zombie is not possible and is not the fix. Fix the parent.

An orphan is not a zombie. The orphan is alive and running; the zombie is dead and uncollected. Students swap these two constantly and it is worth a line in every answer.

exit(0) and return 0 from main are the same thing, but exit from anywhere else is not the same as returning: it ends the process rather than the function.

Quick revision

• exit(n) ends a process; only the low eight bits of n survive; 0 means success.
• The parent collects with wait or waitpid and takes the status apart with WIFEXITED,

WEXITSTATUS, WIFSIGNALED, WTERMSIG.

• exit flushes the C library's buffers; _exit does not, which is why a child that failed

to exec must use _exit.

• A zombie is a dead child whose exit status has not been collected. It holds a process id

and nothing else, shows Z in ps, and cannot be killed. Only the parent's wait, or the parent's death, removes it.

• An orphan is a live child whose parent has died. It is re-parented, ultimately to process

1, whose job is to collect it.

• Making an orphan on purpose is how a daemon is started.

Test yourself

1. What is a zombie process and why does it exist? A process that has ended but whose exit

status has not yet been collected by its parent. It exists because the status cannot be thrown away before somebody asks for it.

1. How is a zombie removed? The parent calls wait or waitpid. If the parent dies, the

process the kernel keeps for the purpose adopts it and collects it at once. It cannot be killed.

1. What is an orphan, and what happens to it? A running process whose parent has exited. The

kernel re-parents it, ultimately to process 1.

1. Distinguish a zombie from an orphan in one sentence each. A zombie is dead and

uncollected. An orphan is alive and has lost its parent.

1. Why must a child use _exit rather than exit after a failed exec? Because exit

flushes the C library buffers, which were copied from the parent, so the parent's unwritten output would be printed a second time.

1. A server has accumulated 30,000 zombies. What is wrong and what fixes it? The parent is

not calling wait. Fix the parent, or restart it: its zombies are then adopted and collected. Killing the zombies does nothing.

1. Why is a machine full of zombies eventually unable to start any process? Each zombie holds

a process id, and the supply of ids is finite.

The questions a message passing scheme must answer

Any message passing system has to settle five things, and a question may ask for them.

1. Direct or indirect. Direct: the sender names the receiving process. Indirect: both use a

mailbox or port, and the sender does not know who will take the message. Indirect is more flexible, and a mailbox may be owned by a process or by the operating system.

1. Blocking or non-blocking. Chapter twenty five is this question alone.
2. Buffered or not. Zero capacity, so the sender must wait for a receiver; bounded capacity,

so the sender waits only when the buffer is full; or unbounded, where the sender never waits.

1. Fixed or variable length messages. Fixed is simple for the kernel and awkward for the

programmer; variable is the other way round.

1. What happens when things fail. A message lost, a process that ends while a message is in

flight, a message that arrives twice.

What is actually available, on a real machine

There are more than two facilities, and they sort into the two models. All of them are in the next four chapters.

$ ipcs -q -m | head -8

------ Message Queues --------
key        msqid      owner      perms      used-bytes   messages

------ Shared Memory Segments --------
key        shmid      owner      perms      bytes      nattch     status
$ ls -l /dev/mqueue 2>/dev/null | head -2 || echo "no POSIX queues exist yet"
total 0

Both tables are empty because nothing on this machine is using them yet. That the tables exist at all, and are separate from any process, is the point: a System V queue or segment belongs to the system, not to the process that made it, which is why Chapter twenty four's queue outlives the program that created it.

Worked example: choosing a model twice

A video editor and its rendering helper exchange whole frames, several megabytes each, sixty times a second. Copying that through the kernel twice per frame would cost more than the rendering. Shared memory, with a lock, is the only sensible choice, and the programmer accepts the synchronisation problem.

A print spooler and the programs that submit jobs exchange a file name and a few options, perhaps once a minute. The data is tiny, the programs are unrelated and were written by different people, and correctness matters far more than microseconds. Message passing: a queue, so the spooler need not be running when a job is submitted.

The rule the two examples give: large and frequent, share memory; small, occasional or across a network, pass messages.

What it does not mean

Shared memory is not shared variables. The processes agree on a region and must agree on what is in it, byte by byte. Nothing checks that agreement.

Message passing is not slow in absolute terms. It is slower per byte than memory. A few thousand messages a second is nothing to a modern machine.

A pipe is not shared memory even though it feels like a shared thing. Every byte through a pipe is copied by the kernel, twice.

Using shared memory does not remove the need for the kernel. It is asked for the region and asked to tear it down, and the locks the processes need are often kernel objects too.

Quick revision

• Two models: shared memory and message passing.
• Reasons to co-operate: information sharing, computation speedup, modularity, convenience.
• Shared memory: fast, no kernel involvement per access, and

synchronisation is the programmer's problem.

• Message passing: two system calls and two copies per message, slower, and the kernel

delivers each message whole, so no race arises. It works across a network.

• A message passing scheme must settle: direct or indirect (a mailbox or port), blocking

or non-blocking, buffered with zero, bounded or unbounded capacity, fixed or variable length, and what happens on failure.

• Facilities: pipes and named pipes, System V and POSIX message queues, System V and POSIX shared

memory, sockets, signals.

• Large and frequent data, share memory. Small, occasional or remote, pass messages.

Test yourself

1. Name the two models of inter-process communication and the essential difference. Shared

memory and message passing. In shared memory the kernel sets up a region once and is not involved again; in message passing every transfer goes through the kernel.

1. Why is shared memory faster, and what does that cost? Because reads and writes are

ordinary memory accesses with no system call. The cost is that nothing co-ordinates the two processes, so the programmer must prevent race conditions.

1. Give the four reasons for co-operating processes. Information sharing, computation

speedup, modularity, convenience.

1. Distinguish direct from indirect communication. In direct communication the sender names

the receiving process. In indirect communication both use a mailbox or port, and the sender need not know who receives.

1. What are the three buffering capacities? Zero, so the sender waits for a receiver;

bounded, so the sender waits only when the buffer is full; unbounded, so the sender never waits.

1. Two processes exchange five megabyte images sixty times a second. Which model, and why?

Shared memory: copying that much data through the kernel twice per image would cost more than the work itself. The programmer accepts responsibility for locking.

A segment of 4096 bytes existed, owned by student, with nattch of 0 because no process had attached it. Then it was removed and the table was empty again. No program was running at any point. The segment outlived the command that made it, which is exactly the property that makes System V shared memory useful and dangerous.

Two processes, one segment

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <string.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include <unistd.h>

struct board {
    int ready;
    int count;
    char message[64];
};

int main(void)
{
    int id = shmget(IPC_PRIVATE, sizeof(struct board), IPC_CREAT | 0600);
    if (id < 0) {
        perror("shmget");
        return 1;
    }
    printf("the segment id is %d, and it is %zu bytes\n", id, sizeof(struct board));

    pid_t child = fork();
    if (child == 0) {
        struct board *b = shmat(id, NULL, 0);
        strcpy(b->message, "the child wrote this straight into memory");
        b->count = 7;
        b->ready = 1;                     /* last, so the parent sees a whole message */
        printf("child : written, and detaching\n");
        shmdt(b);
        _exit(0);
    }
    wait(NULL);

    struct board *b = shmat(id, NULL, 0);
    printf("parent: ready is %d, count is %d\n", b->ready, b->count);
    printf("parent: message is \"%s\"\n", b->message);
    shmdt(b);
    shmctl(id, IPC_RMID, NULL);           /*  without this the segment stays */
    printf("parent: segment removed\n");
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o shareit shareit.c
$ ./shareit
the segment id is 1, and it is 72 bytes
child : written, and detaching
parent: ready is 1, count is 7
parent: message is "the child wrote this straight into memory"
parent: segment removed
$ ipcs -m | awk '$3 == "student" {print "a segment is still there"} END {print "the table has been read"}'
the table has been read

Notice what is not in that program: no send, no receive, no system call for the transfer. The child assigned to a structure and the parent read the structure. Between those two lines the kernel did nothing at all, and that is the whole reason shared memory exists.

Notice also the order of the child's three writes: the message first, the count next, the ready flag last. That is not an accident and it is the right habit: the flag says "everything else is valid", so it must be written after everything else. Chapters thirty three to forty two are about doing this properly rather than carefully.

The danger, named now and solved later

The program above is safe only because the parent called wait, so the two processes never touched the segment at the same moment. Take that away and the program is broken in a way that usually works, which is the worst kind of broken.

Shared memory with no synchronisation is a race condition waiting to be reported as an intermittent bug. Chapter thirty four makes one happen on purpose; Chapters thirty seven to forty two are the tools that fix it. The practical's own instruction is "Explore issues of race conditions and how to avoid them", and that is the honest order: see the mechanism here, see the danger in Chapter thirty four, see the fix in Chapter thirty nine.

The POSIX family, in one paragraph

POSIX shared memory does the same job with the file system as its naming scheme. shm_open("/name", ...) gives a descriptor, ftruncate sets the size, and mmap maps it. The name looks like a file name and appears under /dev/shm, so an ordinary ls finds leftovers. It is newer and easier to clean up; the System V family is what an examination question will name, because it is what MU's text book uses.

Distinctions that carry marks

What it does not mean

Shared memory is not a shared variable. There is no declaration that makes two processes share a variable. There is a region of bytes, and both programs must agree on its layout.

Attaching is not copying. shmat maps; nothing is copied, which is why it is fast however large the segment is.

Removing it is not immediate if somebody is attached. IPC_RMID marks it for destruction; it goes when the last process detaches. So a segment can be removed and still be usable by the processes already holding it, which is the safe way to clean up.

Quick revision

• Shared memory maps one piece of physical memory into two address spaces. No kernel

involvement per access, so it is the fastest form of communication.

• shmget to make or find (returns an id), shmat to attach (returns an address), shmdt

to detach, shmctl with IPC_RMID to remove.

• A key is an agreed name; IPC_PRIVATE asks for an unnamed one, enough when a child

inherits the id.

• The two processes may see the segment at different addresses, so never store a pointer in

it.

• shmdt is not IPC_RMID. Detach affects one process; remove destroys it for all. A

forgotten remove leaves the segment in the system, and ipcs -m finds it.

• Write the data first and the ready flag last.
• Shared memory with no synchronisation is a race condition. Chapters thirty four and thirty

nine.

• The POSIX family is shm_open, ftruncate, mmap, and its names appear under /dev/shm.

Test yourself

1. Name the four System V shared memory calls and what each does. shmget makes or finds a

segment and returns its id; shmat attaches it and returns an address; shmdt detaches it from this process; shmctl with IPC_RMID removes it from the system.

1. Why must a pointer never be stored in shared memory? Because each process may map the

segment at a different address, so an address valid in one is meaningless in the other. Store offsets.

1. Distinguish detaching from removing. Detaching unmaps it from the calling process only.

Removing destroys it for everybody, once the last process detaches.

1. What happens if a program forgets to remove a segment? It stays in the system after the

program ends. ipcs -m lists it and ipcrm -m removes it.

1. Why is the ready flag written last? Because it tells the reader that everything else is

valid, so it must not become true before the data it vouches for is there.

1. Why is shared memory faster than message passing? Because after the one time setup the

kernel is not involved: a transfer is an ordinary memory access rather than two system calls and two copies.

1. What is the price of that speed? Nothing co-ordinates the two processes, so preventing

race conditions becomes the programmer's job.

Three writes came out as one read, and that is the lesson. The child wrote "first", "second" and "third" separately. The parent asked for up to 64 bytes and got all 19 at once. A pipe has no message boundaries: it is a stream. A program that needs to know where one message ends must put the boundary in the bytes itself, for example a newline, which is exactly why Unix tools are line based.

Then read returned 0. That is end of file, and it happened because the child closed its write end and the parent had closed its copy. Had the parent not closed ends[1], that read would still be waiting.

Named pipes, which any two programs can use

An ordinary pipe can only be shared by inheritance, so the two processes must be related. A named pipe, also called a FIFO, is a pipe with a name in the file system, so any two programs can open it.

$ mkfifo channel
$ ls -l channel
prw-r--r-- 1 student student 0 Sep 30  2026 channel
$ set +m
$ ( echo "sent through a named pipe" > channel ) &
$ cat channel
sent through a named pipe
$ wait 2>/dev/null
$ rm channel

Three things in that transcript.

1. ls -l shows the type letter p, for pipe. It is a file system entry, with permissions,

and it is not a file: nothing is stored in it.

1. Its size is 0 and always will be. The data lives in the kernel's buffer, not on the disk.
2. The writer was put in the background on purpose.

Opening a FIFO for writing blocks until somebody opens it for reading, and the other way round, so running both in the foreground in the wrong order simply waits.

What the shell's vertical bar is

a | b is exactly this chapter plus Chapter nineteen.

1. The shell calls pipe.
2. It forks twice, once for a and once for b.
3. In the process that will be a: dup2(ends[1], 1), so the pipe's write end becomes standard

output; close both original ends; exec a.

1. In the process that will be b: dup2(ends[0], 0), so the pipe's read end becomes standard

input; close both original ends; exec b.

1. The shell closes both ends itself and waits for both children.

Neither a nor b knows a pipe exists. They write to 1 and read from 0 as always. That is why almost every Unix program composes with every other, and it is the strongest single argument for the whole design.

The capacity is real and can be measured. A writer that fills the buffer is made to wait.

$ mkfifo slow
$ set +m
$ ( yes 0123456789 | head -20000 > slow ) &
$ sleep 1
$ pgrep -c yes
1
$ ps -o stat= -p "$(pgrep -n yes)"
S+
$ head -c 20 slow
0123456789
012345678
$ kill $(jobs -p) 2>/dev/null
$ wait 2>/dev/null
$ rm -f slow

One yes is running and its state is S, sleeping: it is waiting for the write to be accepted. The + after it only means it is in the foreground of its own job. That is flow control for free, and it is why yes | head does not fill your disk.

Distinctions that carry marks

What it does not mean

A pipe is not a file. A named pipe has a name and permissions and no contents. Its size is always zero.

A pipe is not two way. Two way needs two pipes. A socket pair is the two way relative.

A pipe does not preserve write boundaries. Three writes may be one read, and one write may be several reads.

A pipe is not shared memory. Every byte is copied by the kernel, twice.

Quick revision

• A pipe is a one way byte stream with a read end, fd[0], and a write end, fd[1].
• Close the end you do not use. read returns 0 only when every write end is closed, so a

forgotten copy makes the reader wait for ever.

• There are no message boundaries. Three writes may arrive as one read; put the boundary in

the bytes, which is why Unix tools are line based.

• An ordinary pipe is shared by inheritance, so the processes must be related. A

named pipe or FIFO has a name in the file system and can be used by any two processes; ls -l shows type p and size 0.

• Opening a FIFO for writing blocks until a reader opens it, and the other way round.
• The shell's a | b is one pipe, two forks, a dup2 in each child, and exec. Neither

program knows.

• The kernel's buffer is finite, so a fast writer blocks when it is full: flow control for free.

Test yourself

1. What is a pipe and which end is which? A one way byte stream between processes. fd[0] is

the read end and fd[1] is the write end.

1. Why must each process close the end it does not use? Because a read returns end of file

only when all write ends are closed. A reader holding its own copy of the write end will wait for ever.

1. Three writes of six bytes go into a pipe. How many reads take them out? Any number from

one to eighteen. A pipe is a stream with no message boundaries.

1. Distinguish an ordinary pipe from a named pipe. An ordinary pipe has no name and can only

be shared by inheritance, so the processes must be related. A named pipe has a name in the file system and any two processes with permission can open it.

1. Explain how the shell implements sort | uniq. It creates a pipe, forks twice, in one

child makes the write end descriptor 1 and execs sort, in the other makes the read end descriptor 0 and execs uniq, closes both ends itself, and waits for both.

1. What happens when a writer fills a pipe faster than the reader empties it? The write

blocks until space is free. The kernel's finite buffer gives flow control without either program asking for it.

1. Why is a named pipe's size always zero? Because it stores nothing. The data is in the

kernel's buffer, and the file system entry is only a name.

$ gcc -std=c17 -Wall -Wextra -o poster poster.c -lrt
$ gcc -std=c17 -Wall -Wextra -o reader reader.c -lrt
$ ./poster
poster : 3 message(s) are waiting in the queue
poster : closed, and exiting. the queue stays.
$ ls -l /dev/mqueue/college
-rw------- 1 student student 80 Sep 30  2026 /dev/mqueue/college
$ cat /dev/mqueue/college
QSIZE:44         NOTIFY:0     SIGNO:0     NOTIFY_PID:0
$ ./reader
reader : priority 9, 13 bytes: URGENT notice
reader : priority 1, 15 bytes: ordinary notice
reader : priority 1, 16 bytes: another ordinary
reader : queue removed
$ ls /dev/mqueue/

Four things worth naming.

1. The poster exited and the messages stayed. Between the two programs nothing of either was

running. The queue is the kernel's, not the program's.

1. The queue appears in the file system, under /dev/mqueue, so an ordinary ls finds

leftovers and cat reports how many bytes are waiting. That is a convenience Linux adds; the standard does not require it.

1. Priority 9 came out first, although it was sent second. mq_receive always takes the

highest priority waiting, and among equal priorities the oldest. That is the difference from a pipe that an examination question is most likely to want.

1. Each receive returned exactly one message, with its own length. Fifteen, thirteen and

sixteen bytes came out as three separate messages. Compare Chapter twenty three, where three writes came out as one read.

The System V family, which MU's text book also describes

The older family is msgget, msgsnd, msgrcv and msgctl. Its differences are examinable.

The message type is the interesting difference. In a System V queue the receiver says "give me a message of type 4", so one queue can carry several independent conversations. In a POSIX queue the receiver takes whatever is most urgent.

$ ipcmk -Q
Message queue id: 0
$ ipcs -q | awk '$3 == "student" {print "id", $2, "owner", $3, "perms", $4}'
id 0 owner student perms 644
$ ipcrm -q 0

Worked example: the producer and the consumer, with a queue

The practical asks for the producer and consumer problem solved by message passing, and the point is how much simpler it is than the shared memory version of Chapter thirty nine.

• The producer loops: make an item, mq_send it. If the queue is full, mq_send blocks

until there is room.

• The consumer loops: mq_receive, use the item. If the queue is empty, mq_receive blocks

until something arrives.

That is the whole solution. There are no semaphores, no mutex, no shared counter and no race condition, because the queue has a size and the kernel does the waiting. Compare Chapter thirty nine, where the same problem in shared memory needs a mutex and two counting semaphores and can be got wrong in four different ways.

The cost is the one from Chapter twenty one: every item is copied twice and costs two system calls. For three items a second that is nothing. For three million it is everything.

Distinctions that carry marks

What it does not mean

A message queue is not shared memory. Every message is copied into the kernel and out again.

"Priority" is not a process priority. It is a number carried by the message, chosen by the sender, and it affects only the order of delivery.

The queue is not unbounded. mq_maxmsg and mq_msgsize are fixed when it is created, and both are capped by the system. A full queue blocks the sender, which is the next chapter.

A System V message type is not a priority. The receiver asks for a type it wants; it does not get the most urgent.

Quick revision

• A message queue holds whole messages, belongs to the kernel, and survives the

processes that use it.

• POSIX: mq_open, mq_send, mq_receive, mq_getattr, mq_close, mq_unlink. Names begin

with one slash. Link with -lrt.

• mq_close ends this process's use; mq_unlink removes the queue for everybody.
• mq_receive returns the highest priority message, and among equals the oldest.
• On Linux a POSIX queue appears under /dev/mqueue, so leftovers can be found with ls.
• System V: msgget, msgsnd, msgrcv, msgctl, named by a numeric key, selected by

message type, listed by ipcs -q.

• The producer and consumer problem with a queue needs no semaphores at all: the queue's size

and the kernel's blocking do the work.

Test yourself

1. Give two things a message queue does that a pipe cannot. It preserves message boundaries,

and it outlives the processes that use it, so a sender and a receiver need never run at the same time.

1. Distinguish mq_close from mq_unlink. mq_close ends the calling process's use of the

queue. mq_unlink removes the queue from the system.

1. Three messages are sent with priorities 1, 9 and 1. In what order are they received? The

priority 9 message first, then the two priority 1 messages in the order they were sent.

1. A program using mq_send fails to link. What is missing? -lrt, the real time library.
2. How is a System V queue's message type different from a POSIX priority? The receiver names

the type it wants, so one queue can carry several independent conversations. A priority only decides which waiting message is delivered first.

1. Solve producer and consumer with a message queue. The producer sends each item and blocks

if the queue is full; the consumer receives each item and blocks if it is empty. No semaphores and no mutex are needed, because the queue is bounded and the kernel does the waiting.

1. What is the cost of that simplicity? Two system calls and two copies per item, against a

memory write in the shared memory solution.

$ gcc -std=c17 -Wall -Wextra -o nonblock nonblock.c
$ ./nonblock
empty pipe, non-blocking read returned -1, errno says Resource temporarily unavailable
after a write, the same read returned 4
the pipe took 65536 bytes and then said Resource temporarily unavailable

Three facts from one program.

1. An empty pipe read -1 with EAGAIN, whose message is "Resource temporarily unavailable".

Had the pipe been blocking, the program would still be sitting there.

1. The same call succeeded the moment there was data. Non-blocking changes when the call

returns, not what it does.

1. The pipe's capacity is a real, measurable number: 65,536 bytes on this machine. A blocking

write would have waited at that point; the non-blocking one refused. That number is the flow control of Chapter twenty three, measured.

Which to choose, and the rule that answers the viva question

Use blocking unless you have another job to do. That is the whole answer, and the reasons are:

• a blocked process costs nothing, while a polling process costs a processor;
• blocking code is shorter and has fewer states, so it has fewer bugs;
• the kernel wakes you at exactly the right moment, and a poll cannot.

Use non-blocking when one process must serve many channels, which is the case blocking cannot handle: a server with a hundred connections cannot block on the first one, because the other ninety nine would wait. And that is where the third answer comes in, because polling a hundred channels in a loop is also wrong.

A tight loop of non-blocking calls is called busy waiting and it is the wrong answer to every question in this chapter. It burns a whole processor to learn nothing. The same mistake appears in Chapter thirty seven as the spinlock, where it is occasionally right, and there the reason it is right is precisely measured.

Worked example: two designs for one job

A program must read from a pipe and also update a clock on the screen every second.

With blocking alone: impossible in one process. Blocked on the pipe, it cannot touch the clock; busy waiting on the pipe, it wastes the machine. Two processes, or two threads (Chapter twenty seven), or the next answer.

With select: one call waits on the pipe and a one second timeout at the same time. It returns when either happens. The process uses no processor while waiting and never misses a second. This is the design a real program uses, and it is blocking, on several things at once.

With non-blocking and a loop: the program reads, gets EAGAIN, sleeps a little, tries again. It works, it wastes a little, and it may be up to the sleep interval late. Acceptable for a small tool and wrong for a server.

Distinctions that carry marks

What it does not mean

Blocking does not mean the machine stops. One process waits; everything else runs. A blocked process is in the waiting state of Chapter fifteen.

Non-blocking is not faster. It returns sooner. The work happens at the same time either way.

EAGAIN is not an error in the ordinary sense. It means "not now". A program that reports it to the user as a failure is wrong.

Asynchronous input and output is a third thing. Strictly, asynchronous means the kernel does the work and tells you when it is finished, which is aio_read and its family. A non-blocking call does no work at all if it cannot finish at once. An examination that uses "asynchronous" loosely means non-blocking.

Quick revision

• Blocking, or synchronous: the call waits. Non-blocking, or asynchronous: it returns -1

with EAGAIN at once.

• Four combinations, because send and receive choose separately.
• A blocked process is in the waiting state and uses no processor. Blocking is the cheap

way to wait, not the wasteful one.

• O_NONBLOCK, set at open or with fcntl, makes a channel non-blocking.
• A tight loop of non-blocking calls is busy waiting and wastes a whole processor.
• Many channels in one process: select or poll, which blocks on all of them at once.
• The measured capacity of a pipe on the lab machine is 65,536 bytes; a blocking write waits

there, a non-blocking one refuses.

Test yourself

1. Define blocking and non-blocking communication. A blocking call does not return until it

can do its job. A non-blocking call returns immediately, with -1 and EAGAIN, if it cannot.

1. How many combinations are there, and why? Four, because sending and receiving are

independent choices.

1. Does a blocking read waste the processor? No. The process is moved to the waiting state

and the processor is given to another process. It is the cheapest way to wait.

1. What does EAGAIN mean and what should a program do about it? Nothing is available now.

Try again later, ideally when told to by select or poll rather than by a loop. 5. A server handles a hundred connections in one process. Which model, and why not the others? Neither plain blocking nor a poll loop: blocking on one connection ignores the rest, and polling all of them burns a processor. Use select or poll, which blocks on all of them at once and reports which are ready.

1. Why is busy waiting almost always wrong? It uses a whole processor to discover, over and

over, that there is nothing to do, and the kernel could have woken the process at exactly the right moment for nothing.

1. Resource sharing. Threads share memory by default, with no system call and no setup. Two

processes must ask for shared memory; two threads already have it.

1. Economy. Making a thread is far cheaper than making a process, and switching between two

threads of one process is cheaper than switching between two processes. Chapter sixteen's worked example says why: the memory mapping does not change.

1. Scalability, also called utilisation of multiprocessor architectures. A process with

one thread can use one processor however many the machine has. Threads can run on all of them at once.

The fourth is the one that has changed in importance. When the four were first written, machines with more than one processor were rare. Every phone now has six or eight cores, and a single threaded program uses one of them.

Seeing threads on a real machine

A thread is not a process, but Linux shows both in the same table if you ask.

$ ps -o pid,nlwp,comm -p $$ --no-headers
      9    1 bash
$ grep Threads /proc/self/status
Threads:	1
$ ls -d /proc/$$/task/*
/proc/9/task/9

nlwp is the number of light weight processes, which is what Linux calls a thread, and Threads in the status file says the same thing. Each one has a directory of its own under task. A program with one thread has one of each, and Chapter twenty seven's program has ten.

Worked example: one job, three designs

A program must read a hundred files and count the words in each.

One process, one thread. Open a file, read it, count, next. While the disk fetches a block the program does nothing at all. On a two processor machine it uses one processor, and badly.

A hundred processes. Each counts one file. They genuinely run at once and use every processor. But each costs a full process creation, each has its own address space, and collecting the hundred answers needs inter-process communication: shared memory or a pipe per child, and Chapter twenty two or twenty three of work.

One process, several threads. Each thread takes a file from a shared list and adds its count to a shared total. They run at once, they use every processor, creation is cheap, and the answers are simply added into a shared variable with no communication machinery at all.

The third design is best and it is also the one that can go wrong in a way the other two cannot. "Adds its count to a shared total" is a race condition (Chapter thirty four) unless the addition is protected (Chapter thirty seven). Threads buy sharing and sell safety, and the whole of MU's process synchronisation row is the price.

Distinctions that carry marks

What it does not mean

Threads do not make a program faster by themselves. They let it use more processors and stop waiting. A program that is limited by the disk gets nothing from more threads.

A thread is not a lightweight process in the sense of being a small process. It has no address space of its own at all. Linux calls it a light weight process because it implements both with one mechanism.

Threads do not remove the need for synchronisation. They create it. Two processes are protected from each other by the hardware. Two threads are protected from each other by nothing.

A single threaded program is not obsolete. It is simpler, it cannot race, and for most tasks it is the right answer.

Quick revision

• A thread is the basic unit of processor utilisation: a thread id, a program counter,

registers and a stack of its own, sharing code, data, the heap and open files with its siblings.

• Shared: text, data, globals, heap, open files, the process id. Private: program

counter, registers, stack, thread id.

• A global variable is shared; a local variable is on the thread's own stack and is not.
• Four benefits: responsiveness, resource sharing, economy, scalability on

several processors.

• Threads are cheaper to make and cheaper to switch between than processes, because the address

space does not change.

• Linux calls a thread a light weight process; ps -o nlwp, /proc/<pid>/status and

/proc/<pid>/task all count them.

• Threads buy sharing and sell safety: everything in MU's synchronisation row is the price.

Test yourself

1. Define a thread. The basic unit of processor utilisation, with its own thread id, program

counter, registers and stack, sharing its code, data and operating system resources with the other threads of the same process.

1. What does a thread have of its own, and what does it share? Its own program counter,

registers, stack and thread id. It shares the text, the data section and globals, the heap, the open files and the process id.

1. Why must each thread have its own stack? Because the stack holds the frames of the calls

in progress, and two threads are inside different functions at the same moment.

1. Name the four benefits of threads. Responsiveness, resource sharing, economy, and

scalability on a machine with several processors.

1. Why is switching between two threads cheaper than between two processes? The address space

does not change, so the memory management hardware and its translation cache are untouched. 6. A program counts words in a hundred files using ten threads that add to one total. What is the danger? The shared total is changed by ten threads at once, which is a race condition. The addition must be protected by a lock.

1. Is a local variable shared between threads? No. It lives on the calling thread's own

stack. A global variable is shared, because it lives in the shared data section.

The total is the same every run and the order of the lines is not. The sum of the squares from one to ten is 385 whatever order the threads ran in, because each thread wrote to its own job. That is what makes this program correct, and Chapter thirty four is the same program written so that it is not.

The order really does change

$ for i in $(seq 20); do ./ten | head -1; done | sort -u > firsts.txt
$ n=$(wc -l < firsts.txt)
$ [ "$n" -gt 1 ] && echo "over twenty runs, $n different threads reached the screen first"
over twenty runs, 3 different threads reached the screen first

Three runs of the same program, and the thread that reached the screen first was not always the same. Nothing in the program decides that. It is the scheduler, and a program that depends on which thread runs first is wrong even when it works.

Counting the threads from outside

The kernel can be asked how many threads a process has while it is running.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <string.h>
#include <pthread.h>
#include <unistd.h>

static void *wait_a_while(void *unused)
{
    (void)unused;
    sleep(2);
    return NULL;
}

int main(void)
{
    pthread_t id[4];

    for (int i = 0; i < 4; i++) {
        pthread_create(&id[i], NULL, wait_a_while, NULL);
    }
    FILE *f = fopen("/proc/self/status", "r");
    char line[128];
    while (fgets(line, sizeof line, f)) {
        if (strncmp(line, "Threads:", 8) == 0) {
            printf("%s", line);
        }
    }
    fclose(f);
    for (int i = 0; i < 4; i++) {
        pthread_join(id[i], NULL);
    }
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -pthread -o count-threads count-threads.c
$ ./count-threads
Threads:	5

Five: the four that were created and the one that created them. The first thread of a process is a thread like any other, and main runs on it. There is no such thing as a process with no threads.

Passing an argument, and the trap in it

Passing the address of a loop variable to every thread is the commonest thread bug there is.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <pthread.h>

static void *show(void *argument)
{
    int *n = argument;

    printf("%d ", *n);
    return NULL;
}

int main(void)
{
    pthread_t id[4];

    for (int i = 0; i < 4; i++) {
        pthread_create(&id[i], NULL, show, &i);   /* the SAME address, four times */
    }
    for (int i = 0; i < 4; i++) {
        pthread_join(id[i], NULL);
    }
    printf("\n");
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -pthread -o wrong wrong.c
$ ./wrong
4 4 4 4

Four threads, and every one of them printed the same number. They were all given the address of i, which by the time they ran had reached 4. The fix is what ten.c did: give each thread a pointer to something of its own.

Distinctions that carry marks

What it does not mean

A thread function is not main. It takes one void and returns one void , and returning from it ends only that thread.

pthread_exit in main does not end the process. It ends the first thread and lets the others run on, which is occasionally what you want and usually a surprise.

Joining is not synchronisation between running threads. It waits for one to finish. Two threads that must co-ordinate while both are running need Chapters thirty seven to forty two.

Quick revision

• pthread_create(&id, attr, function, argument) starts a thread; pthread_join(id, &result)

waits for it and collects its value.

• The function takes one void and returns one void . Pass a structure for more.
• Compile with -pthread.
• Life cycle: created, running, blocked, terminated. A terminated thread's record survives until

it is joined or it was detached: the thread version of a zombie.

• The first thread of a process runs main, so a process with four created threads reports five.
• The order in which threads run is the scheduler's business and changes between runs. A

program that depends on it is wrong.

• Never pass the address of the loop variable to every thread: they all see its final value.

Test yourself

1. Which calls create a thread and wait for one? pthread_create and pthread_join.
2. What is the signature of a thread function? It takes one void * and returns one

void *.

1. What happens to a thread nobody joins? Its record and stack stay allocated, like a zombie

process. Join it, or detach it so the library cleans it up when it ends.

1. A process creates four threads. How many does the kernel report and why? Five. The thread

running main is a thread like any other. 5. Four threads are given &i, the address of the loop variable, and all print 4. Why, and what is the fix? They share one variable, which had reached its final value before they ran. Give each thread a pointer to its own data.

1. Why does the total in ten.c never change while the order of the lines does? Each thread

wrote to its own structure, so nothing was shared and no result depended on the order. Only the moment each thread reached the screen depended on the scheduler.

Work it for a program that is 25 per cent serial, so S = 0.25, on eight cores.

One divided by 0.34375 is 32 / 11, which is about 2.91.

Eight cores, and under three times the speed. That is the whole point of the law, and it is why a question asks for the number rather than the principle.

Now the same program on more and more cores, to see where it stops paying.