Computer Science Practical 3 Notes | B.Sc. (Computer Science) Semester 3 | Mumbai University | munotes

Note what is not in that list: there is no "attendance" component and no "internal test" that can rescue a term of missed practicals. The 15 marks are the work.

The certified journal, and the 80 per cent rule

MU prints two sentences under the practical paper pattern, and both are conditions on being allowed to sit the examination at all.

Certified Journal is compulsory for appearing at the time of Practical Exam

Minimum 80% practical are required to be completed

Certified means signed by the teacher who watched you do the work, and stamped by the department. An unsigned journal full of correct programs is not a certified journal.

Eighty per cent of twenty practicals is sixteen. There are twenty exercises in this paper, ten in Module 1 and ten in Module 2, so the rule says at least sixteen of them must be in your journal, completed. It does not say which sixteen, and it does not say eight from each module, but a journal with all ten of Module 2 and only six of Module 1 is a student who cannot answer Q.1, which is half the paper.

The safe reading, and the one every college applies: do all twenty. The four you are allowed to miss are there for the week you were ill, not for the four you found hard.

[Keeping the Journal, and What Goes on the Page] is the chapter on what one entry looks like.

The semester end examination

Sixty per cent of 50 is 30, and this is MU's printed pattern for it, word for word from her own table.

Two hours. Two questions. Thirty marks.

That is the whole paper, and three things follow from it that are worth saying plainly.

There is no viva question. The first year's practical papers, set under item 6.5 (R), print Q.1 for 12, Q.2 for 12 and a viva for 6. This paper, set under item 6.14 (N), prints no third question. An examiner at your machine will still ask you what your program does, because that is how a practical examination is conducted anywhere, and those questions feed the assessment of your work; but there is no separate question in the paper carrying marks for them.

Each question is worth half the paper. A student who is fluent in Module 2 and has never compiled a C program has a ceiling of 15 out of 30. The two modules are in two different languages and both of them have to work.

An hour per question is not much. A bounded-buffer program with two semaphores and a mutex is about sixty lines. An AVL tree with all four rotations is about a hundred. You will not design either of them in the hall; you will remember them. That is what the journal is for, and it is why every chapter in this book prints the whole program rather than an outline of it.

What MU says you should be able to do

Her Course Objectives (CO) and Course Outcomes (OC) are the other half of the contract, and they are a fair list of what an examiner is looking for.

Course Objectives. To develop hands-on skills in implementing core concepts of operating systems and data structures. To simulate and solve real-world problems using process management, synchronization, and memory management. To strengthen understanding of data abstraction and manipulation using linked structures, trees, graphs, and hashing. To enable students to analyze and compare algorithmic strategies for CPU scheduling, buffer control, and structured data operations. To foster problem-solving abilities through coding, debugging, and testing.

Course Outcomes. After this course a student can design and implement solutions using inter-process communication techniques such as shared memory and message passing; apply multithreading, synchronization mechanisms, and scheduling algorithms; construct and manipulate linear and non-linear data structures using custom implementations; demonstrate effective use of stack, queue, trees, graphs, and hash tables; analyze and evaluate the performance of memory and disk management techniques; and apply the result to real-time, scalable system-level applications.

Read OC 5 again: analyze and evaluate the performance. Three of the ten exercises in Module 1 are about measuring something, not just making it work: hit and miss ratios in [Practical 9: Memory Management, FIFO and LRU Page Replacement], total head movement in [Practical 10: Disk Scheduling], and waiting and turnaround time in [Practical 7: CPU Scheduling, FCFS and Non-preemptive Scheduling]. A program that prints the schedule and not the averages has answered half the question.

The two languages, and why

MU names the languages twice and both times indirectly.

Module 1 is C. She sets shared memory, semaphores and message queues, which on a Unix system are the System V interfaces, and she names pthreads where she names a threading library. Her Text Book for this module is Silberschatz, Galvin and Gagne, Operating System Concepts , 10th edition, and every program in it is C. This book therefore writes Module 1 in C on Ubuntu Linux.

Module 2 is Python. Her Text Book for this module is Aho, Ullman and Lam, Data Structures and Algorithms in Python , and one of her two Reference Books is Kanetkar, Data Structures Through Python . This course also teaches Python in Semester 1, so it is the language a second-year student already has. This book therefore writes Module 2 in Python 3.

MU writes "e.g., pthreads or Java threads" in Module 1, and her other Reference Book is Goodrich's Java edition, so a college may run either module in Java instead. If yours does, the structures and the algorithms in this book are unchanged and the chapters say where the Java form differs. What never changes is the reasoning, and that is what carries the marks.

The shape of every chapter in this book

Each of the twenty exercises is one journal entry, so each is a chapter, and each chapter is laid out the way a journal entry is laid out.

1. Aim. MU's own words for the exercise.
2. What you need to know before you start. The idea, in plain English, before any code.
3. The program, complete, with the reasoning for every part that is not obvious.
4. The run, which is the output the program actually produced.
5. Procedure, which is what you type, in order.
6. Result, which is the one sentence you write in the journal.
7. Where marks are lost, which is the list of things that go wrong in the hall.
8. For the journal, which is what goes on the page.
9. Quick revision and Questions you should be able to answer.

Six of the twenty exercises are split over two chapters, because MU's own bullets under them ask for two different programs. Practical 1 is the shared memory segment and then the race condition; Practical 2 is pipes and then message queues; Practical 10 is disk scheduling and then a file system; Practical 15 is the stack and then the expression conversion; Practical 18 is the AVL tree and then the heap. They are still one journal entry each.

What it does not mean

It does not mean the theory does not matter. It means the theory is examined in the two theory papers this practical pairs with, Principles of Operating Systems and Data Structures. What is examined here is whether you can make the thing run. In practice the students who can make it run are the students who understood it, which is why every chapter explains before it codes.

It does not mean you may skip Module 1 because C is harder. Q.1 is 15 of the 30 marks.

It does not mean the journal can be written in the last week. It is signed as the term goes on, by a teacher who was present. A journal produced complete on the last day is not certified, whatever is written in it.

Quick revision

• 2 credits, 60 hours, 50 marks. Type: Practical, so there is no theory paper.
• Internal 20: work and hands-on assessment 15, journal 5.
• External 30: two hours, Q.1 on Module 1 for 15, Q.2 on Module 2 for 15. No viva question in this

scheme.

• A certified journal is compulsory to appear, and at least 80 per cent of the practicals, which

is 16 of the 20, must be completed.

• Twenty exercises: ten on Principles of Operating Systems in C, ten on Data Structures in Python.
• Scheme: NEP 2020, MU item 6.14 (N), AC 20 May 2025, in force from 2025-26.

Questions you should be able to answer

1. How many marks does this paper carry and how are they split? Fifty. Twenty internal, which is 15 for the practical work and 5 for the journal, and thirty external, which is a two-hour practical examination of two questions worth 15 each.

2. How many practicals must be completed to be allowed to sit the examination? At least 80 per cent of them, which is 16 of the 20, and the journal must be certified.

3. Is there a viva in the semester end examination for this paper? Not as a question carrying its own marks. MU's printed pattern for this paper is Q.1 and Q.2 only. The first-year practical papers do print a viva question worth 6 marks, which is where the confusion comes from.

4. Why is a 2-credit practical 60 hours when a 2-credit theory paper is 30? Because MU counts one practical credit as 30 hours of laboratory work, against 15 hours of lectures for a theory credit.

5. Which of the two modules is examined first? Q.1 is set on Module 1, which is the operating systems half. Neither module is optional.

in Module 1 is like this: sys/shm.h for shared memory, pthread.h for threads. If you forget one, the compiler warns about an implicit declaration and the program may still build, which is worse than an error because it runs and misbehaves.

• int main(void) is where the program starts. void says it takes no arguments. Where a program

needs its command line, it is int main(int argc, char *argv[]) instead.

• printf writes to standard output. \n is a newline, and without it the shell prompt appears

on the same line as your output, which in a journal looks like a mistake.

• return 0 is the program's exit status, and 0 means success. The operating system keeps it, and

in [Processes: fork, wait, exec, and Why Two Programs Need to Talk] the parent process reads it.

Compiling and running

Two steps, always.

gcc -o hello hello.c
./hello

gcc -o hello hello.c reads hello.c and writes a program called hello. Without -o the compiler writes a file called a.out, which is a habit worth not forming: with four programs in one folder they all become a.out in turn and you run the wrong one.

./hello runs it. The ./ is not decoration. The shell looks for commands in the directories listed in PATH, and the folder you are standing in is not one of them, so hello on its own answers hello: command not found while ./hello says "the one in this directory".

The two flags that belong in every command in this book

gcc -Wall -Wextra -o hello hello.c

-Wall and -Wextra turn on the warnings. They are not on by default, and this is the single most useful habit in the module: a C program that is wrong usually compiles, and the warning is the only notice you get.

For anything with threads there is a third:

gcc -Wall -Wextra -pthread -o prog prog.c

-pthread links the threads library and sets the flags the library needs. Without it, a program using pthread_create fails at the link step with undefined reference to pthread_create, which is not a mistake in your program at all and costs students a lot of time in the hall.

Every program in this book was compiled with gcc -std=c17 -Wall -Wextra -pthread, and no warning was allowed except in the listings below, which exist to show one. A listing that warns by accident teaches a habit that will fail somebody else's compiler.

What the compiler says when you are wrong

This is the part of the chapter to read twice. Three mistakes, and the exact message each one produces, so that you recognise it rather than guess at it.

A missing semicolon

#include <stdio.h>

int main(void)
{
    printf("hello")
    return 0;
}

hello.c: In function ‘main’:
hello.c:5:20: error: expected ‘;’ before ‘return’
    5 |     printf("hello")
      |                    ^
      |                    ;
    6 |     return 0;
      |     ~~~~~~

Read the message from the left. hello.c:5:20 is file, line, column. Then error, then what it expected and what it found instead. Then it prints the line, puts a ^ at column 20, and on the next line shows the ; it wanted there.

Two things are worth noticing, and the second one is what saves time in the hall.

The column is exactly right. Column 20 of line 5 is the character after the closing bracket, which is precisely where the semicolon belongs. gcc is not guessing.

It then prints line 6 as well, underlined with ~~~~~~. That is the token it actually tripped over: return. The compiler could not know the statement had ended until it met a word that cannot continue one. So the message names two lines: the one that needs fixing, with a ^, and the one that revealed the problem, with ~. When you see two lines in an error, fix the one with the ^.

A function whose header you forgot

#include <stdio.h>

int main(void)
{
    char name[] = "Mumbai University";
    printf("%zu\n", strlen(name));
    return 0;
}

hello.c: In function ‘main’:
hello.c:6:21: warning: implicit declaration of function ‘strlen’ [-Wimplicit-function-declaration]
    6 |     printf("%zu\n", strlen(name));
      |                     ^~~~~~
hello.c:2:1: note: include ‘<string.h>’ or provide a declaration of ‘strlen’
    1 | #include <stdio.h>
  +++ |+#include <string.h>
    2 |
hello.c:6:21: warning: incompatible implicit declaration of built-in function ‘strlen’ [-Wbuiltin-declaration-mismatch]
    6 |     printf("%zu\n", strlen(name));
      |                     ^~~~~~
hello.c:6:21: note: include ‘<string.h>’ or provide a declaration of ‘strlen’

17

Look at what happened there, because it is the most dangerous thing in this chapter. Two warnings, no error, the program built, and it printed the right answer.

implicit declaration of function means: you called something I have never been told about. strlen is declared in string.h, and this program does not include it. With no declaration, C falls back on an old rule and assumes the function returns int. Here that does no visible harm, because the length of a string fits in an int, so the program is wrong and looks right. That is worse than an error, and it is the whole reason for -Wall.

Notice the third and fourth lines of the message. gcc does not only complain, it writes out the line you are missing:

  +++ |+#include <string.h>

+++ marks a suggested insertion. Add that line and both warnings go.

The same mistake, when the function returns a pointer

#include <stdio.h>

int main(void)
{
    char *copy = strdup("hello");
    printf("%s\n", copy);
    return 0;
}

hello.c: In function ‘main’:
hello.c:5:18: warning: implicit declaration of function ‘strdup’ [-Wimplicit-function-declaration]
    5 |     char *copy = strdup("hello");
      |                  ^~~~~~
hello.c:5:18: warning: initialization of ‘char *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]

The output block is empty because the program printed nothing at all. It crashed, with a segmentation fault, on every one of the five runs this page was checked over.

This is the same missing header as before, and two things about the message are worth noting before the reason. There is no suggested #include line this time, because gcc offers that hint only for the functions it knows as built-ins, and strdup is not one of them; and the second warning prints no caret line of its own. So the shape of a diagnostic is not fixed, and the part to rely on is the file, line and column at the front of it.

The second warning says why the result is different from the last program. strdup returns a pointer, which on this machine is 8 bytes. With no declaration C assumed int, which is 4 bytes, so the top half of the address was thrown away before it was stored. printf was then handed a number that is not the address of anything, and reading from it killed the program.

A segmentation fault means the program touched memory it does not own. It is the commonest way a C program dies, and in this module it almost always means a pointer that was never valid: a truncated address like this one, an address from shmat that was not checked, or a pointer used after it was freed.

What a truncated address happens to point at is not defined by the language, so on another machine this program might print rubbish instead of crashing. Either way the program is wrong, and either way the fix is #include <string.h>.

The wrong conversion in printf

#include <stdio.h>

int main(void)
{
    double average = 62.5;
    printf("average %d\n", average);
    return 0;
}

hello.c: In function ‘main’:
hello.c:6:22: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘double’ [-Wformat=]
    6 |     printf("average %d\n", average);
      |                     ~^     ~~~~~~~
      |                      |     |
      |                      int   double
      |                     %f

No output is printed for this one, and the reason is the lesson. %d tells printf to read an integer, the program handed it a double, and the number that comes out is whatever happened to be lying in the place printf looked. It is different on every run of the same program, so there is nothing a book could honestly print here.

The last line of the warning is gcc telling you the answer: %f. It prints the conversion you should have used, underneath the one you did use. The conversions worth remembering:

Comparing a signed number with an unsigned one

The last of the four, and the one that is hardest to see by reading.

#include <stdio.h>

int main(void)
{
    int i = -1;
    unsigned int u = 1;
    if (i < u) printf("i is less than u\n");
    else printf("i is NOT less than u\n");
    return 0;
}

hello.c: In function ‘main’:
hello.c:7:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘unsigned int’ [-Wsign-compare]
    7 |     if (i < u) printf("i is less than u\n");
      |           ^

i is NOT less than u

Minus one is not less than one. That is what the machine says, and it is not a bug in the machine.

When a signed and an unsigned value of the same size meet in a comparison, C converts the signed one to unsigned, and -1 as a 32-bit unsigned number is 4294967295. So the test asks whether 4294967295 is less than 1, and the answer is no.

This matters in this module because several library calls return unsigned types. A loop written for (i = 0; i < count - 1; i++) where count is unsigned and happens to be 0 does not run zero times; count - 1 is 4294967295 and the loop runs for a very long time. -Wextra is what tells you, and this warning is the reason it is on every command in this book.

And one that only the linker can catch

A function you never wrote at all gets past the compiler with the same implicit-declaration warning, because the compiler works on one file and cannot know what is in the others. The linker is what refuses it, with a message of a different shape: undefined reference to 'total', followed by collect2: error: ld returned 1 exit status.

That is the message to recognise when you forget -pthread. Nothing is wrong with your program; pthread_create exists, but the library holding it was not linked, so the linker says undefined reference to 'pthread_create' and stops. The fix is a flag, not an edit.

Reading the manual

Every system call in Module 1 has a manual page on the machine, and it is the authority. The pages are installed by manpages-dev:

sudo apt install manpages-dev
man 2 shmget
man 3 pthread_create

The number is the section: 1 is commands you type, 2 is system calls, 3 is library functions. It matters because some names are in more than one section. man 2 write is the system call; man 1 write is a command for sending a message to another logged-in user.

Every manual page has the same parts, and two of them answer almost every question:

• SYNOPSIS gives the headers to include and the exact prototype. When you cannot remember

whether shmat takes three arguments, this is faster than any web page.

• RETURN VALUE gives what it returns on success, what it returns on failure, and the fact that

it sets errno. Every failure check in this book comes from here.

Leave a manual page with q. Search inside one with /shmflg then Enter, and n for the next match.

Checking every call, which is what the marks are for

Almost every line in Module 1 asks the operating system for something, and the operating system is allowed to say no. A program that does not check is a program that crashes with no explanation, and an examiner who sees an unchecked shmget will say so.

The pattern is the same every time.

#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <sys/ipc.h>
#include <sys/shm.h>

int main(void)
{
    /* 0 bytes is not a legal size, so this call is meant to fail. */
    int id = shmget(IPC_PRIVATE, 0, IPC_CREAT | 0600);
    if (id == -1) {
        printf("shmget failed, errno %d, which means: %s\n", errno, strerror(errno));
        return 1;
    }
    printf("this line is never reached\n");
    return 0;
}

shmget failed, errno 22, which means: Invalid argument

Three parts to that, and all three are worth copying into every program you write this term.

1. The call returns a sentinel on failure, and it is -1 for almost everything in this

module. shmat is the exception: it returns (void *) -1, because it hands back a pointer.

1. errno says which failure it was. It is set by the call and it is only meaningful when the

call has just failed; reading it after a call that succeeded tells you nothing.

1. strerror(errno) turns the number into a sentence, and perror("shmget") does the same

thing in one step, writing shmget: Invalid argument to standard error. Use perror in ordinary programs; this book sometimes prints the number as well, so that the page can name it.

The errno values that come up in Module 1:

Procedure

1. Log in to a Linux machine, or start your virtual machine.
2. sudo apt update then sudo apt install gcc manpages-dev.
3. gcc --version and write the version in your journal.
4. nano hello.c, type the first program, save and leave.
5. gcc -Wall -Wextra -o hello hello.c then ./hello.
6. Remove the semicolon from the printf line, compile again, and read the error. Put it back.
7. man 2 shmget, read the SYNOPSIS and the RETURN VALUE, and leave with q.

Result

The compiler is installed, a C program has been compiled and run on Linux, the messages the compiler gives for a missing semicolon, a missing header and a wrong conversion have been observed, and the manual page for a system call has been read.

Where marks are lost

• Forgetting -pthread. Everything from

[Practical 3: Threading and Single Thread Control Flow] onwards needs it, and the failure looks like a bug in your program rather than a missing flag.

• Running hello instead of ./hello and concluding the program did not build.
• Fixing the second line an error names. An error prints the line to fix with a ^ and the

line that revealed it with ~. Fix the one with the ^.

• Ignoring warnings. A %d against a double compiles, runs, and prints rubbish. In the hall

that looks like a wrong algorithm, and you will spend twenty minutes on the wrong thing.

• Writing the program in Windows and copying it across. Windows line endings leave a \r on

every line, which gcc tolerates but which makes the output look strange. dos2unix file.c fixes it.

• Not checking a return value. Two marks, every time, in every exercise in this module.

For the journal

Write the aim, the commands you typed in order, the version of gcc, the first program, its output, and one of the compiler errors with the line you changed to produce it. One page.

Quick revision

• Module 1 is C on Linux because shared memory, semaphores, message queues and pthreads are

interfaces of a Unix operating system. They do not exist on Windows with Turbo C.

• sudo apt install gcc manpages-dev. Check with gcc --version.
• gcc -Wall -Wextra -o prog prog.c then ./prog. Add -pthread for anything with threads.
• A syntax error is reported at the first token that cannot follow, so look at the line above the

one named.

• implicit declaration of function means a missing #include.
• man 2 name for a system call, man 3 name for a library function. SYNOPSIS gives the

prototype, RETURN VALUE gives the failure check.

• Every system call is checked: -1 for almost all of them, (void *) -1 for shmat, and

perror or strerror(errno) to say why.

Questions you should be able to answer

1. Why can these programs not be written on Windows with Turbo C? Because sys/shm.h, sys/sem.h, sys/msg.h, pthread.h and fork are interfaces of a Unix operating system. Eight of the ten exercises in Module 1 would not compile.

2. What does -pthread do, and what happens without it? It links the POSIX threads library and sets the flags it needs. Without it a program using pthread_create fails at the link step with undefined reference to pthread_create.

3. The compiler reports an error on line 6 and line 6 looks correct. What has happened? The mistake is almost certainly on line 5. A syntax error is reported at the first token that cannot legally follow, which is usually on the next line.

4. What is the difference between man 2 write and man 3 printf? Section 2 is system calls, which are requests to the kernel. Section 3 is library functions, which are ordinary C functions, though many of them make system calls underneath.

5. What does shmget return on failure, and how do you find out why it failed? It returns -1 and sets errno. perror("shmget") or strerror(errno) turns that into a sentence.

6. Why is a warning about %d against a double worth stopping for? Because the program compiles and runs and prints a meaningless number, so the mistake shows up as a wrong answer rather than as a failure to build.

So if (pid == 0) is not a test of a value, it is the question "am I the child?".

Now look at counter. It was 0 before the fork. The child added 100 and printed 100. The parent added 1 and printed 1. Neither saw the other's change, because after the fork there are two variables called counter, one in each address space. The child's 100 went nowhere near the parent's copy.

That is the problem MU's first exercise solves. Shared memory is a piece of memory the operating system maps into both address spaces at once, so that a change made by one is seen by the other.

The sleep(1) in the parent is there to make the output order fixed for the page. Without it the two lines appear in whichever order the scheduler chooses, which is the subject of [Practical 3: Threading and Single Thread Control Flow].

wait: the parent waits for the child to finish

A parent that finishes first leaves the child running with no parent, and a child that finishes first leaves a record nobody has collected. Both have names, and both are avoided by the same call.

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

int main(void)
{
    pid_t pid = fork();
    if (pid == -1) {
        perror("fork");
        return 1;
    }

    if (pid == 0) {
        printf("child : working\n");
        return 7;
    }

    int status;
    pid_t done = wait(&status);

    printf("parent: child %d finished\n", done);
    if (WIFEXITED(status))
        printf("parent: it returned %d\n", WEXITSTATUS(status));
    return 0;
}

child : working
parent: child 7 finished
parent: it returned 7

wait(&status) stops the parent until one of its children finishes, and returns that child's pid. The status it fills in is not the exit code; it is a word with several pieces of information packed into it, and two macros take them out:

• WIFEXITED(status) is true if the child ended normally, by returning from main or calling

exit.

• WEXITSTATUS(status) is then the value it returned, and only the bottom 8 bits of it, so a

child that returns 300 is reported as 44.

Two macros for the other case, which matters in this module because a program that dies of a segmentation fault is a program that was killed:

• WIFSIGNALED(status) is true if the child was killed by a signal.
• WTERMSIG(status) is then the signal number: 11 is SIGSEGV, the segmentation fault.

In the run above, the child's pid and the value it returned are both 7 by coincidence. That is the container's low process numbers at work, and on your machine the pid will be a large number while the returned value stays 7.

The orphan and the zombie

Two words an examiner asks for, and they are the two halves of getting wait wrong.

An orphan is a child whose parent finished first. It is not an error and nothing is lost: the operating system gives the orphan a new parent, process number 1, which collects its exit status in due course. On a modern Linux desktop that is systemd.

A zombie is the opposite and it is a real leak. A child that has finished still has one thing left, its exit status, and the operating system must keep it until the parent asks. Until then the child is in state Z, holding a slot in the process table, using no memory and no processor. A parent that forks a thousand children and never waits leaves a thousand zombies, and when the table is full no new process can start on the machine at all.

A zombie is cleared the moment the parent calls wait, and by the parent finishing, which makes the zombie an orphan and hands it to process 1. The rule: every fork is matched by a wait.

exec: a process replaces its own program

fork makes a copy of the program you are already running. To run a different program you need the other half of the pair.

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

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

    if (pid == 0) {
        printf("child : about to become another program\n");
        fflush(stdout);
        execl("/bin/echo", "echo", "hello from echo", (char *) NULL);
        perror("execl");
        return 1;
    }

    wait(NULL);
    printf("parent: the child is done\n");
    return 0;
}

child : about to become another program
hello from echo
parent: the child is done

execl throws away the program the process is running and loads a new one in its place. The pid does not change, the open files do not change, but the code, the data and the stack are all replaced. exec does not return on success, because there is nothing left to return to; that is why the perror after it needs no if, and why reaching it at all means the call failed.

Two details in that listing which are not decoration.

fflush(stdout) before the exec. Output is buffered, so printf puts the line in a buffer that is written out when the program ends. The exec discards the whole program including that buffer, so without the flush the child's own line is lost. A student who meets this thinks printf did not run.

The (char *) NULL at the end. execl takes the arguments one after another and has no way to know how many there are, so the list ends with a null pointer. Leaving it out, or writing plain 0, is a real bug that sometimes works by luck.

The first argument is the program to run. The second is what the program will see as its own name, which is why "echo" appears twice in effect. Nearly every program on a Unix machine is started by exactly this pair of calls: the shell forks, and the child execs the command you typed.

The five calls this module is built on

Several children, and waiting for all of them

Most of MU's exercises have more than one child, so this pattern is worth having ready. It also carries the two traps that catch everybody the first time.

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

int main(void)
{
    for (int i = 1; i <= 3; i++) {
        pid_t pid = fork();
        if (pid == -1) {
            perror("fork");
            return 1;
        }
        if (pid == 0) {
            printf("child %d reporting\n", i);
            fflush(stdout);      /* or the line can be lost: see below */
            _exit(0);            /* the child must NOT go round the loop */
        }
    }

    while (wait(NULL) > 0)
        ;                        /* collect every child */

    printf("all three children are done\n");
    return 0;
}

child 1 reporting
child 2 reporting
child 3 reporting
all three children are done

The order of those first three lines is not fixed. Run it eight times and this book's check saw five different orders. Nothing decides which child reaches the screen first: all three are ready to run and the operating system picks. The last line is always last, because wait holds the parent until every child has finished, and that is the only ordering the program guarantees.

This is why the page prints the lines as a set rather than as a sequence: what is proved over every run is that the three children each reported once and the parent reported after them. A book that printed one fixed order would be showing a student something their own machine will contradict.

Trap one: a child that does not leave the loop forks again

Remove the _exit(0) and child 1 goes round to i = 2 and forks a child of its own, which goes round to i = 3. Three passes of the loop produce seven processes instead of three, and the output is a different mess every time. Every child in a forking loop ends with _exit or return , on its own line, and it is the first thing to look for when a program prints too much.

_exit rather than exit, because exit flushes the buffers the child inherited from its parent. Anything the parent had written but not yet flushed would then be written twice, once by the child and once by the parent.

Trap two: _exit throws away what the child has printed

This is the same program with the fflush taken out, and nothing else changed.

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

int main(void)
{
    for (int i = 1; i <= 3; i++) {
        pid_t pid = fork();
        if (pid == -1) {
            perror("fork");
            return 1;
        }
        if (pid == 0) {
            printf("child %d reporting\n", i);
            _exit(0);
        }
    }

    while (wait(NULL) > 0)
        ;

    printf("all three children are done\n");
    return 0;
}

all three children are done

All three children have gone. They ran, they called printf, and not one of their lines arrived.

The reason is how C buffers output, and it depends on where the output is going.

printf does not write to the screen. It writes into a buffer, and the buffer is emptied later. On a terminal that happens at each newline, so a student running this in the laboratory sees all four lines and believes the program is correct. Send the same program's output to a file, which is what this book's checker does and what ./prog > out.txt does, and the child's line is still sitting in the buffer when _exit ends the process without emptying it.

Three ways to be safe, and the first is the one to use:

1. fflush(stdout); immediately before _exit, as in the correct version above.
2. fflush(stdout); before the fork, which empties whatever the parent had pending so that no

child inherits it. Needed as well, in any program that prints before forking.

1. setbuf(stdout, NULL); at the top of main, which turns buffering off altogether. Useful

while you are debugging a program whose output arrives in the wrong order, and not worth shipping.

This is why the execl listing earlier in the chapter has an fflush in it, and it is the same rule: exec and _exit both discard the buffer, so anything you want kept has to be out of it first.

The four ways two processes can talk

Everything in Module 1 is one of these, and MU sets the first two as exercises.

The first two are the ones that matter, and the difference between them is the subject of [Practical 2 continued: Message Queues, Blocking and Non-blocking]. In one sentence: shared memory is fast and you must do the synchronising yourself; message passing is slower and the kernel does the synchronising for you.

Procedure

1. Write and run the program that prints getpid and getppid. Run it three times and note that

the pid changes.

1. Write the fork program with the counter. Confirm that the child's 100 and the parent's 1 do

not affect each other.

1. Add wait and print the child's exit status.
2. Write the execl program. Remove the fflush and run it again to see the child's own line

disappear.

1. Write the three-child loop. Run it five times and note that the order of the child lines

changes.

1. Remove the _exit(0) and count how many lines appear.
2. Put the _exit(0) back, remove the fflush, and run it twice: once as ./prog and once as

./prog > out.txt followed by cat out.txt. The child lines are in the first and gone from the second.

Result

Two processes were created with fork, told apart by its return value, and shown to have separate copies of the same variable. The parent collected each child's exit status with wait. A child replaced its own program with execl. The need for shared memory or message passing follows from the separate address spaces.

Where marks are lost

• Not checking fork for -1. One mark, and it is the easiest one in the paper.
• A child that does not _exit, so a forking loop breeds processes.
• Never calling wait, and then being unable to answer what a zombie is.
• Expecting the parent's variable to change because the child changed it. This is the

misunderstanding the whole of Practical 1 exists to correct.

• Assuming the parent runs first, or the child does. Nothing guarantees either. Where the

order matters, wait is what makes it certain.

• Forgetting fflush before an exec or an _exit, and losing output that was written. It

works in the laboratory, where output goes to a terminal, and fails the moment anybody redirects it to a file.

• Writing pid_t without #include <sys/types.h>. With -std=c17 that is an error, not a

warning: unknown type name pid_t.

For the journal

Write the aim, the fork program with the counter, its output with your own pid numbers, and one sentence saying why the two counters differ. Add the wait version and the exit status it printed. Note the definitions of orphan and zombie.

Quick revision

• A program is a file; a process is a running program, with a pid, a ppid and an address space of

its own.

• fork returns twice: 0 to the child, the child's pid to the parent, -1 on failure.
• The child gets a copy of the parent's memory, so a variable changed in one is unchanged in

the other. That is why inter-process communication is needed.

• wait(&status) blocks until a child finishes and returns its pid. WIFEXITED and WEXITSTATUS

take the exit code out; WIFSIGNALED and WTERMSIG say which signal killed it.

• Orphan: the parent died first, and process 1 adopts it. Zombie: the child died and nobody has

called wait, so its entry stays in the process table.

• exec replaces the program in the current process and does not return on success. fork plus

exec is how every command you type is run.

• Every child in a loop ends with _exit, and every fork is matched by a wait.
• Output to a terminal is flushed at each newline; output to a file or a pipe is flushed in

blocks. _exit and exec both discard the buffer, so fflush(stdout) comes first.

• The order in which several children print is not fixed. wait is the only thing that orders

anything.

Questions you should be able to answer

1. What does fork return, and to whom? Zero to the child, the child's pid to the parent, and -1 to the caller if no child could be created.

2. A parent sets x = 5, forks, and the child sets x = 9. What does the parent print? Five. The child has its own copy in its own address space.

3. What is a zombie process, and how is it cleared? A child that has finished but whose exit status has not been collected, so its entry stays in the process table. The parent calling wait clears it; so does the parent finishing, which hands the child to process 1.

4. What is the difference between an orphan and a zombie? An orphan has lost its parent and is still running or has been adopted by process 1; a zombie has finished and is waiting for a parent that has not called wait. The orphan is harmless, the zombie holds a slot in the process table.

5. Why does exec not return? Because it replaces the program that would have been returned to. If the line after it runs, the call failed.

6. Why must a forked child not fall through a forking loop? Because it would fork children of its own. Three passes of the loop would create seven processes instead of three.

7. A forking program prints correctly in the laboratory and loses lines when its output is redirected to a file. Why? Because output to a terminal is flushed at every newline and output to a file is flushed in blocks. A child that ends with _exit discards its buffer, so its line never reaches the file. fflush(stdout) before the _exit fixes it.

8. Name the two ways of passing data between processes that MU sets, and the one-line difference between them. Shared memory, which is fast and leaves the synchronising to you, and message passing, which is slower and where the kernel does the synchronising.

There is a third way, ftok, and it is further down the chapter.

Permissions, which are file permissions

The last argument to shmget carries two things joined with |:

• IPC_CREAT, meaning create the segment if it does not exist. Without it, shmget only

looks up an existing one and fails with ENOENT if there is none.

• Nine permission bits in octal, exactly as for a file: 0666 is read and write for

everybody, 0600 is read and write for the owner only. A segment created 0600 cannot be attached by another user, which in a college laboratory where everyone shares a machine is usually what you want.

IPC_EXCL may be added to IPC_CREAT, and then the call fails with EEXIST if the segment already exists rather than handing you the old one. It is how a program refuses to reuse somebody else's leftovers.

The program: a parent and a child sharing one segment

This is the version to put in the journal if the question says "using fork ".

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/shm.h>

#define SIZE 128

int main(void)
{
    /* 1. ask the kernel for a segment of SIZE bytes */
    int shmid = shmget(IPC_PRIVATE, SIZE, IPC_CREAT | 0600);
    if (shmid == -1) {
        perror("shmget");
        return 1;
    }
    printf("parent: segment id %d, %d bytes\n", shmid, SIZE);
    fflush(stdout);           /* BEFORE the fork: see the note below */

    pid_t pid = fork();
    if (pid == -1) {
        perror("fork");
        shmctl(shmid, IPC_RMID, NULL);
        return 1;
    }

    if (pid == 0) {
        /* 2. the child attaches and writes */
        char *shared = shmat(shmid, NULL, 0);
        if (shared == (void *) -1) {
            perror("child shmat");
            _exit(1);
        }
        strcpy(shared, "Mumbai University, Semester 3");
        printf("child : wrote  [%s]\n", shared);
        fflush(stdout);
        shmdt(shared);            /* 3. detach */
        _exit(0);
    }

    wait(NULL);                   /* the write must have happened first */

    /* the parent attaches to the same segment and reads */
    char *shared = shmat(shmid, NULL, 0);
    if (shared == (void *) -1) {
        perror("parent shmat");
        shmctl(shmid, IPC_RMID, NULL);
        return 1;
    }
    printf("parent: read   [%s]\n", shared);
    shmdt(shared);

    /* 4. destroy it, or it outlives the program */
    if (shmctl(shmid, IPC_RMID, NULL) == -1)
        perror("shmctl");
    else
        printf("parent: segment removed\n");
    return 0;
}

parent: segment id 0, 128 bytes
child : wrote  [Mumbai University, Semester 3]
parent: read   [Mumbai University, Semester 3]
parent: segment removed

The segment id on your machine will not be 0. Inside the container this book is checked in the machine has just started, so the kernel hands out the first identifier it has; on a college machine it will be a larger number and it changes every run.

Reading the program line by line

shmget(IPC_PRIVATE, SIZE, IPC_CREAT | 0600) asks for 128 bytes. It returns a small non-negative integer, the shared memory identifier. That number is not an address and it is not a key: it is a handle, and it is the thing the other three calls take.

The child inherits shmid through the fork, because it is an ordinary variable that was set before the fork. That is why IPC_PRIVATE is enough here and no key is needed.

shmat(shmid, NULL, 0) attaches. It returns a pointer, and from then on the segment is ordinary memory: strcpy into it, read it, put a struct in it. The NULL says "put it wherever you like", which is the right answer; asking for a particular address is a way to make a program fail on a machine where that address is busy. The 0 is the flags, and SHM_RDONLY there gives a read-only attachment.

shmat fails with (void *) -1, not NULL. It is the one call in this module whose failure value is not plain -1, and if (shared == NULL) is a check that never fires.

fflush(stdout) before the fork. This line is not decoration, and leaving it out is the mistake this page made first. The parent's printf puts its line in a buffer. The child inherits a copy of that buffer, and when the child flushes its own message it writes out the parent's line as well, so parent: segment id 0, 128 bytes appears twice, once from the child and once from the parent. Flushing before the fork means there is nothing in the buffer to be inherited. The rule was stated in [Processes: fork, wait, exec, and Why Two Programs Need to Talk] and this is what it looks like in a real program.

wait(NULL) before the parent reads. Without it the parent might read the segment before the child has written anything, and print an empty string. Nothing in shared memory tells a reader that the data has arrived; here the wait is what makes the order certain, and in a program where the two run at the same time a semaphore does that job.

shmdt(shared) detaches. The segment still exists; only this process's view of it has gone. The pointer is invalid afterwards and using it is a segmentation fault.

shmctl(shmid, IPC_RMID, NULL) destroys the segment. IPC_RMID means remove. This is the line students forget, and the next section is about what happens then.

A segment outlives the program that made it

This is the single most important fact about System V shared memory, and it surprises everybody.

A segment is not owned by a process. It is owned by the kernel, and it stays on the machine until something removes it or the machine is restarted. A program that creates a segment and exits without IPC_RMID leaves it there, attached to nothing, using memory, for ever.

You can see it. ipcs -m lists every shared memory segment on the machine, and the next program creates one and then asks ipcs to print it.

#include <stdio.h>
#include <stdlib.h>
#include <sys/ipc.h>
#include <sys/shm.h>

int main(void)
{
    int shmid = shmget(0x4d55, 1024, IPC_CREAT | 0666);
    if (shmid == -1) {
        perror("shmget");
        return 1;
    }
    printf("created segment id %d with key 0x4d55\n", shmid);
    fflush(stdout);

    system("ipcs -m");

    shmctl(shmid, IPC_RMID, NULL);
    return 0;
}

created segment id 0 with key 0x4d55

------ Shared Memory Segments --------
key        shmid      owner      perms      bytes      nattch     status
0x00004d55 0          student    666        1024       0

Read the columns, because an examiner may ask you to.

A segment with nattch of 0 that nobody is going to attach again is a leak. Two commands clear one up by hand:

ipcs -m
ipcrm -m 32768

ipcrm -m takes the shmid, not the key. There is also ipcrm -M 0x4d55, with a capital M, which takes the key.

In a college laboratory this matters more than it looks. The machine has a limit on how many segments may exist at once, and a class of forty students each leaving a few behind will reach it. When shmget starts failing with ENOSPC for no apparent reason, somebody's program forgot IPC_RMID.

Two separate programs, which is what the examiner usually asks for

The fork version works because the child inherits the identifier. Two unrelated programs cannot inherit anything, so they agree on a key instead. Here is the pair, and this is the form to have ready for the examination.

The writer, which creates the segment and puts data in it:

#include <stdio.h>
#include <string.h>
#include <sys/ipc.h>
#include <sys/shm.h>

#define KEY  0x4d55
#define SIZE 256

int main(void)
{
    int shmid = shmget(KEY, SIZE, IPC_CREAT | 0666);
    if (shmid == -1) {
        perror("writer shmget");
        return 1;
    }

    char *shared = shmat(shmid, NULL, 0);
    if (shared == (void *) -1) {
        perror("writer shmat");
        return 1;
    }

    strcpy(shared, "notes for Computer Science Practical 3");
    printf("writer: wrote to the segment with key 0x%x\n", KEY);

    shmdt(shared);
    return 0;
}

The reader, which finds the same segment and takes the data out. Note the third argument to shmget: no IPC_CREAT, because the reader must not create anything. If the segment is not there, the reader should fail and say so, not make an empty one and read nothing.

#include <stdio.h>
#include <sys/ipc.h>
#include <sys/shm.h>

#define KEY  0x4d55
#define SIZE 256

int main(void)
{
    int shmid = shmget(KEY, SIZE, 0666);
    if (shmid == -1) {
        perror("reader shmget");
        return 1;
    }

    char *shared = shmat(shmid, NULL, 0);
    if (shared == (void *) -1) {
        perror("reader shmat");
        return 1;
    }

    printf("reader: found  [%s]\n", shared);

    shmdt(shared);

    /* the reader is the last one out, so the reader cleans up */
    if (shmctl(shmid, IPC_RMID, NULL) == -1)
        perror("reader shmctl");
    else
        printf("reader: segment removed\n");
    return 0;
}

writer: wrote to the segment with key 0x4d55
reader: found  [notes for Computer Science Practical 3]
reader: segment removed

Compile and run them as two programs, in two commands:

gcc -Wall -Wextra -o writer writer.c
gcc -Wall -Wextra -o reader reader.c
./writer
./reader

The output above is exactly that session: the writer's line, then the reader's two lines. In the laboratory you can also run them in two terminals, and running ./reader first shows what a missing segment looks like: reader shmget: No such file or directory, which is ENOENT.

ftok, a key made from a file

Choosing a number by hand risks collision: two students on one machine both picking 0x1234 get each other's data. ftok makes a key from a file that already exists, so the file name is the agreement instead of the number.

#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <sys/ipc.h>

int main(void)
{
    key_t a = ftok("/tmp", 'M');
    key_t b = ftok("/tmp", 'M');
    key_t c = ftok("/tmp", 'N');

    if (a == -1 || b == -1 || c == -1) {
        perror("ftok");
        return 1;
    }

    printf("the same path and letter twice: %s\n", a == b ? "same key" : "DIFFERENT");
    printf("the same path, letter N     : %s\n", a == c ? "same key" : "different key");
    printf("the top byte of the key is  : 0x%02x, which is the letter %c\n",
           (unsigned) (a >> 24) & 0xff, (char) ((a >> 24) & 0xff));

    key_t missing = ftok("/tmp/there-is-no-such-file", 'M');
    printf("a path that does not exist  : returns %d, errno says %s\n",
           (int) missing, strerror(errno));
    return 0;
}

the same path and letter twice: same key
the same path, letter N     : different key
the top byte of the key is  : 0x4d, which is the letter M
a path that does not exist  : returns -1, errno says No such file or directory

That program proves the three things worth knowing, and deliberately does not print the key itself. ftok takes a path that must exist and a single character, the project identifier, and mixes them into a key:

• The same path and the same letter always give the same key on the same machine, which is the

whole point: both programs call it and both get the same number.

• A different letter gives a different key, so one file can name several segments.
• The path must exist. ftok on a missing file returns -1 and sets ENOENT.

Two warnings, and the second is why the listings above use a plain number instead:

• The key is built from the file's inode number, so it is a different value on every machine.

The top byte is the letter you passed, which is why the top byte above is 0x4d for 'M'; the rest comes from the file. While this page was being checked the key changed between two runs, because the container gets a fresh /tmp each time and therefore a fresh inode number. That is exactly the failure mode described next.

• Delete the file and make it again and the inode changes, so the key changes. A program that

is still running is then looking at a segment nobody else can find any more. A key written into the source as a number cannot do that.

Putting a structure in the segment, not just a string

Shared memory is bytes, so anything can go in it. A structure is the usual choice, because real data has parts.

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/shm.h>

struct student {
    int  roll;
    char name[40];
    int  marks[3];
};

int main(void)
{
    int shmid = shmget(IPC_PRIVATE, sizeof(struct student), IPC_CREAT | 0600);
    if (shmid == -1) {
        perror("shmget");
        return 1;
    }

    if (fork() == 0) {
        struct student *s = shmat(shmid, NULL, 0);
        if (s == (void *) -1) {
            perror("child shmat");
            _exit(1);
        }
        s->roll = 2331;
        strcpy(s->name, "Aarti Kulkarni");
        s->marks[0] = 78;
        s->marks[1] = 65;
        s->marks[2] = 92;
        printf("child : filled in the record\n");
        fflush(stdout);
        shmdt(s);
        _exit(0);
    }

    wait(NULL);

    struct student *s = shmat(shmid, NULL, 0);
    if (s == (void *) -1) {
        perror("parent shmat");
        shmctl(shmid, IPC_RMID, NULL);
        return 1;
    }
    int total = s->marks[0] + s->marks[1] + s->marks[2];
    printf("parent: roll %d, %s\n", s->roll, s->name);
    printf("parent: marks %d %d %d, total %d\n",
           s->marks[0], s->marks[1], s->marks[2], total);
    shmdt(s);
    shmctl(shmid, IPC_RMID, NULL);
    return 0;
}

child : filled in the record
parent: roll 2331, Aarti Kulkarni
parent: marks 78 65 92, total 235

sizeof(struct student) is the size to ask for, never a number typed by hand. And the pointer shmat returns is used as a struct student with no cast needed, because in C a void converts to any object pointer on its own.

A pointer may never be stored in shared memory. The segment appears at a different address in each process, so an address that is valid in the writer means nothing in the reader. A structure holding a char * is a bug; one holding a char name[40], as above, is correct. This is the trap that catches good students, because the program compiles and runs and only the answers are wrong.

Shared memory against the alternatives

The middle row is why MU sets both Practical 1 and Practical 2, and the full comparison is in [Practical 2 continued: Message Queues, Blocking and Non-blocking].

Procedure

1. nano shm_fork.c, type the first program, and compile it with

gcc -Wall -Wextra -o shm_fork shm_fork.c.

1. Run it. Note the segment id, and run it twice more to see the id change.
2. Run ipcs -m and confirm the segment is gone.
3. Comment out the shmctl line, compile, run, and then ipcs -m. The segment is there with

nattch 0. Remove it with ipcrm -m and the id it printed.

1. Write writer.c and reader.c. Compile both. Run ./reader first and read the error,

then ./writer and ./reader in that order.

1. Write the structure version and confirm the parent reads back all three marks.

Result

A shared memory segment was created, attached to two processes, written by one and read by the other, and removed. The identifier was seen to change on every run. A segment left behind was found with ipcs -m and removed with ipcrm. Two unrelated programs communicated through one segment by agreeing on a key.

Where marks are lost

• Checking shmat against NULL. It fails with (void *) -1. This is the commonest

single error in this exercise.

• Forgetting shmctl(shmid, IPC_RMID, NULL). The segment is left on the machine, and the

examiner can see it with ipcs -m after your program has ended.

• Putting IPC_CREAT in the reader. The reader then silently makes an empty segment when

the writer has not run, prints nothing, and looks as if the writing failed.

• Storing a pointer in the segment. The addresses differ in the two processes.
• No wait before reading, so the parent reads before the child has written.
• Using the key where the id is wanted, or the other way round. shmget takes the key and

returns the id; shmat, shmdt and shmctl take the id.

• Not checking shmget. In a laboratory where segments have been leaked all term, this is

the call that fails.

For the journal

Write the aim, MU's own wording, the first program in full, its output with your own segment id, and the ipcs -m listing before and after ipcrm. Then the writer and reader pair with the two compile commands and the session. One sentence of conclusion: shared memory let two processes exchange data without the kernel copying it, and the segment had to be removed by hand.

Quick revision

• Two processes have separate address spaces, so a variable in one is invisible in the other.

Shared memory is a block the kernel maps into both.

• Four calls: shmget to get an id, shmat to attach, shmdt to detach, shmctl with

IPC_RMID to destroy.

• shmget(key, size, IPC_CREAT | 0666). IPC_PRIVATE for a parent and child; a chosen number

or ftok for unrelated programs. IPC_EXCL refuses an existing segment.

• shmat returns a pointer and fails with (void *) -1. Every other call fails with -1.
• A segment belongs to the kernel, not to the process. It survives the program. ipcs -m lists

them and ipcrm -m <shmid> removes one.

• Shared memory is the fastest form of inter-process communication because after the setup the

kernel is not involved, and for the same reason it provides no synchronisation at all.

• Never store a pointer in shared memory. The segment sits at a different address in each

process.

Questions you should be able to answer

1. What does shmget return, and is it the key? It returns a shared memory identifier, which is a handle used by shmat, shmdt and shmctl. The key is what you pass in; the id is what you get back, and they are different numbers.

2. Why is shared memory the fastest form of inter-process communication? Because after shmat there is no system call and no copying. Both processes are reading and writing the same physical memory as if it were an ordinary variable.

3. What is the price of that speed? No synchronisation. The kernel will not stop two processes writing at once and will not tell a reader that data has arrived, so a semaphore or some other arrangement is needed.

4. What happens if a program exits without calling shmctl with IPC_RMID? The segment stays on the machine until something removes it or the machine restarts. It shows in ipcs -m with nattch 0, and enough of them will make shmget fail for everybody.

5. How does shmat report failure, and why does it catch people? It returns (void *) -1, not NULL, because NULL would be a legitimate address to be given. A check written against NULL never fires.

6. Why must the reader not pass IPC_CREAT? Because then a reader run before the writer creates an empty segment of its own and reads nothing, instead of reporting that the segment does not exist.

7. Two unrelated programs need to share a segment. How do they find the same one? They agree on a key: either a number written into both programs, or one computed by both with ftok from the same path and the same project character.

8. Why can a char * not be stored in shared memory? Because shmat may map the segment at a different address in each process, so the numeric address stored by one process does not point at the same thing in the other. Store an array instead.

expected 4000, got 2000

That number is different on your machine and different on the next run. On the machine this page was checked on it was 4000 twice and 2000 four times in six runs. It can be anything from 2000 to 4000: 2000 is what happens when the two children lose almost every update to each other, and 4000 is what happens when they happen not to overlap at all.

A book cannot print one number for that, so it prints a run and says so. What it can print is the next program's answer.

The race condition, measured

The same experiment, twenty times over, inside one program, with a verdict at the end.

#include <stdio.h>
#include <sched.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/shm.h>

#define N      2000
#define TRIALS 20

int main(void)
{
    int shmid = shmget(IPC_PRIVATE, sizeof(long), IPC_CREAT | 0600);
    if (shmid == -1) {
        perror("shmget");
        return 1;
    }
    long *counter = shmat(shmid, NULL, 0);
    if (counter == (void *) -1) {
        perror("shmat");
        return 1;
    }

    int right = 0;
    long lowest = 2L * N;

    for (int t = 0; t < TRIALS; t++) {
        *counter = 0;
        for (int p = 0; p < 2; p++) {
            if (fork() == 0) {
                long *c = shmat(shmid, NULL, 0);
                for (int i = 0; i < N; i++) {
                    long v = *c;
                    sched_yield();
                    *c = v + 1;
                }
                shmdt(c);
                _exit(0);
            }
        }
        while (wait(NULL) > 0)
            ;
        if (*counter == 2L * N)
            right++;
        if (*counter < lowest)
            lowest = *counter;
    }

    printf("trials run                      : %d\n", TRIALS);
    printf("the right answer each time      : %d\n", 2 * N);
    printf("trials that gave it             : %d\n", right);
    printf("the lowest total seen           : %ld\n", lowest);
    printf("updates were lost at least once : %s\n",
           right < TRIALS ? "yes" : "no");

    shmdt(counter);
    shmctl(shmid, IPC_RMID, NULL);
    return 0;
}

trials run                      : 20
the right answer each time      : 4000
trials that gave it             : 0
the lowest total seen           : 2000
updates were lost at least once : yes

Zero out of twenty. The last line is the one that matters, and it is the same on every run: an unprotected shared counter does not merely risk a wrong answer, it gives one.

This is also the honest way to run any experiment about timing, and it is worth remembering for [Practical 3: Threading and Single Thread Control Flow], where the same trap appears in the form of a single measurement of speed.

The semaphore

A semaphore is a counter held by the kernel, with two operations on it that the kernel performs atomically, meaning that nothing can happen in the middle of one.

P and V are Dijkstra's names for them, from the Dutch proberen and verhogen, and an examiner may use either pair.

A semaphore whose value is only ever 0 or 1 is a binary semaphore or a mutex, short for mutual exclusion. Set it to 1 and the pattern for a critical section is:

wait(mutex);          /* nobody else may be inside now */
   ... critical section ...
signal(mutex);        /* let the next one in */

The first process to arrive takes the value from 1 to 0 and goes in. The second finds 0 and blocks. When the first signals, the value goes back to 1 and the second is woken and takes it to 0 in its turn. Only one is ever inside.

A semaphore with a larger value is a counting semaphore, and it is used to count a resource: a value of 3 means three processes may hold it at once. Practical 5 and Practical 6 both use one.

The three System V calls

The thing to notice is that System V gives you a set of semaphores, not one. semget(key, 2, ...) makes two, numbered 0 and 1, and every operation names which member of the set it means. That is awkward for a single mutex and exactly right for the producer-consumer, which needs two.

union semun, which you have to declare yourself

semctl takes a fourth argument of type union semun, and the C library does not define it. The manual page says so, and every program using System V semaphores begins with this:

union semun {
    int              val;
    struct semid_ds *buf;
    unsigned short  *array;
};

Leaving it out gives unknown type name 'union semun', and it is the single commonest reason a student's semaphore program does not compile.

SEM_UNDO, which saves the laboratory

A sembuf carries a flag, and SEM_UNDO is worth understanding rather than copying.

With SEM_UNDO set, the kernel remembers what this process did to the semaphore and undoes it if the process dies. Without it, a process that takes a mutex and then crashes leaves the value at 0 for ever, and every other process blocks on it until somebody removes the set with ipcrm. In a laboratory that is a machine nobody can use.

So: SEM_UNDO on a mutex, always. It is left off the producer-consumer's two semaphores further down, on purpose, because there an undo would be wrong: a producer that dies holding an item should not silently give the slot back as though the item existed.

The counter, corrected

The same program as before, with three lines added and one pair of calls around the critical section. Nothing else has changed, including the sched_yield that made the race happen.

#include <stdio.h>
#include <sched.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/sem.h>

#define N 2000

/* the C library does not define this: every program declares it */
union semun {
    int              val;
    struct semid_ds *buf;
    unsigned short  *array;
};

static void sem_wait_(int semid)
{
    struct sembuf op = { 0, -1, SEM_UNDO };
    if (semop(semid, &op, 1) == -1)
        perror("semop wait");
}

static void sem_signal(int semid)
{
    struct sembuf op = { 0, 1, SEM_UNDO };
    if (semop(semid, &op, 1) == -1)
        perror("semop signal");
}

int main(void)
{
    int shmid = shmget(IPC_PRIVATE, sizeof(long), IPC_CREAT | 0600);
    if (shmid == -1) {
        perror("shmget");
        return 1;
    }

    int semid = semget(IPC_PRIVATE, 1, IPC_CREAT | 0600);
    if (semid == -1) {
        perror("semget");
        shmctl(shmid, IPC_RMID, NULL);
        return 1;
    }

    union semun arg;
    arg.val = 1;                          /* a mutex starts at 1 */
    if (semctl(semid, 0, SETVAL, arg) == -1) {
        perror("semctl SETVAL");
        return 1;
    }

    long *counter = shmat(shmid, NULL, 0);
    if (counter == (void *) -1) {
        perror("shmat");
        return 1;
    }
    *counter = 0;

    for (int p = 0; p < 2; p++) {
        if (fork() == 0) {
            long *c = shmat(shmid, NULL, 0);
            if (c == (void *) -1)
                _exit(1);
            for (int i = 0; i < N; i++) {
                sem_wait_(semid);         /* enter the critical section */
                long v = *c;
                sched_yield();
                *c = v + 1;
                sem_signal(semid);        /* leave it */
            }
            shmdt(c);
            _exit(0);
        }
    }

    while (wait(NULL) > 0)
        ;

    printf("expected %d, got %ld\n", 2 * N, *counter);

    shmdt(counter);
    shmctl(shmid, IPC_RMID, NULL);
    semctl(semid, 0, IPC_RMID);           /* the set must be removed too */
    return 0;
}

expected 4000, got 4000

Four thousand, every time. This listing is not marked as varying, which means the checker required that exact line on all ten runs it made of it, five under each char convention, and got it. The broken version could not make that claim and this one can.

The function is called sem_wait_ with a trailing underscore because sem_wait is already a real function, the POSIX one, declared in semaphore.h. Naming your own function sem_wait compiles here and collides the moment a program includes that header, which is the sort of bug that appears only when a program grows.

Notice also the last line: semctl(semid, 0, IPC_RMID) destroys the semaphore set, exactly as shmctl with IPC_RMID destroys the segment. A semaphore set is a System V object like any other: it survives the program, ipcs -s lists them, and ipcrm -s <id> removes one by hand.

Producer and consumer, with shared memory and semaphores

This is MU's own wording for the exercise, and it is the classic problem of the module.

A producer makes items and puts them somewhere. A consumer takes them out and uses them. The place in between holds a limited number, here exactly one, and two rules must hold at all times:

• the producer must not write into a slot that is still full;
• the consumer must not read from a slot that is empty.

Neither rule is about mutual exclusion, and that is why a mutex alone cannot solve this. What is needed is a way for each side to wait for the other, and that is what counting semaphores do.

Two of them, and their names are their meanings:

Read the table as a sentence. The producer waits for a free slot and then creates a full one; the consumer waits for a full slot and then creates a free one. The two semaphores hand the single slot back and forth.

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/sem.h>

#define ITEMS 5
#define EMPTY 0                  /* member 0 of the semaphore set */
#define FULL  1                  /* member 1 */

union semun {
    int              val;
    struct semid_ds *buf;
    unsigned short  *array;
};

/* P and V on one member of the set */
static void P(int semid, int member)
{
    struct sembuf op = { (unsigned short) member, -1, 0 };
    if (semop(semid, &op, 1) == -1)
        perror("semop P");
}

static void V(int semid, int member)
{
    struct sembuf op = { (unsigned short) member, 1, 0 };
    if (semop(semid, &op, 1) == -1)
        perror("semop V");
}

int main(void)
{
    int shmid = shmget(IPC_PRIVATE, sizeof(int), IPC_CREAT | 0600);
    if (shmid == -1) {
        perror("shmget");
        return 1;
    }
    int semid = semget(IPC_PRIVATE, 2, IPC_CREAT | 0600);
    if (semid == -1) {
        perror("semget");
        shmctl(shmid, IPC_RMID, NULL);
        return 1;
    }

    union semun arg;
    arg.val = 1;
    semctl(semid, EMPTY, SETVAL, arg);    /* one free slot */
    arg.val = 0;
    semctl(semid, FULL, SETVAL, arg);     /* no filled slot */

    int *slot = shmat(shmid, NULL, 0);
    if (slot == (void *) -1) {
        perror("shmat");
        return 1;
    }

    if (fork() == 0) {                    /* the producer */
        int *s = shmat(shmid, NULL, 0);
        for (int i = 1; i <= ITEMS; i++) {
            P(semid, EMPTY);              /* wait for a free slot */
            *s = i * i;
            printf("producer: put %d in the slot\n", *s);
            fflush(stdout);
            V(semid, FULL);               /* the slot is now full */
        }
        shmdt(s);
        _exit(0);
    }

    if (fork() == 0) {                    /* the consumer */
        int *s = shmat(shmid, NULL, 0);
        for (int i = 1; i <= ITEMS; i++) {
            P(semid, FULL);               /* wait for a full slot */
            printf("consumer: took %d out of the slot\n", *s);
            fflush(stdout);
            V(semid, EMPTY);              /* the slot is free again */
        }
        shmdt(s);
        _exit(0);
    }

    while (wait(NULL) > 0)
        ;
    printf("both finished\n");

    shmdt(slot);
    shmctl(shmid, IPC_RMID, NULL);
    semctl(semid, 0, IPC_RMID);
    return 0;
}

producer: put 1 in the slot
consumer: took 1 out of the slot
producer: put 4 in the slot
consumer: took 4 out of the slot
producer: put 9 in the slot
consumer: took 9 out of the slot
producer: put 16 in the slot
consumer: took 16 out of the slot
producer: put 25 in the slot
consumer: took 25 out of the slot
both finished

Strict alternation, and not a single item lost or read twice, on every one of the ten runs. That is not luck and it is not the scheduler being kind: with one slot, the producer cannot possibly get ahead, because after one item the empty semaphore is 0 and its next P blocks until the consumer has taken that item out.

Two things follow, and both are worth saying because they are the bridge to Practical 5.

A one-slot buffer makes the two processes run in lock-step, which is correct but slow: each side spends most of its time waiting. Give the buffer several slots and they can work at the same time, and that is [Practical 5: Process Synchronisation and the Bounded Buffer].

No mutex was needed here. With one producer and one consumer and one slot, the two semaphores already make it impossible for both to touch the slot at once. Add a second producer and that stops being true, and a third semaphore appears.

The order of the waits, which is where deadlock comes from

If the buffer had several slots and a mutex, the producer's code would be:

P(empty);             /* first wait for a slot  */
P(mutex);             /* then take the lock     */
   ... put the item in ...
V(mutex);
V(full);

Swap those first two lines and the program deadlocks. The producer takes the mutex and then blocks waiting for a free slot; the consumer cannot get the mutex to free one; neither ever moves. Wait for the resource first, take the lock second, and release in the opposite order. That single rule prevents most of the deadlocks in this module, and Practical 5 shows it happening.

Procedure

1. Write the race program. Run it ten times and write down every answer you get.
2. Remove the sched_yield() line, compile, and run it ten more times. Note how often it now

gives the right answer, and that the program is no less wrong for it.

1. Write the twenty-trial version and record the verdict.
2. Add the semaphore. Run ten times and confirm 4000 every time.
3. Run ipcs -s after a run to confirm the semaphore set was removed.
4. Write the producer-consumer program. Confirm the lines alternate strictly.
5. Swap P(empty) and P(mutex) in the form above in a buffer of three slots and see the program

hang. Press Ctrl+C, and then ipcrm whatever it left behind.

Result

An unprotected shared counter lost updates in twenty of twenty trials. A binary semaphore round the critical section made the same program give the exact answer on every run. The producer-consumer problem was solved with one shared slot and two counting semaphores, and the two processes alternated strictly with no item lost or duplicated.

Where marks are lost

• Not declaring union semun. The program does not compile, and the message names a type the

student has never heard of.

• Forgetting semctl(semid, 0, SETVAL, arg). A new semaphore set starts at 0, not 1, so a

mutex that is never initialised blocks the first process that waits on it and the program hangs for ever.

• Using one semaphore for the producer-consumer. It needs two, and an examiner asks why.
• Removing the shared memory and forgetting the semaphore set. ipcs -s shows it. Both

IPC_RMID calls are needed.

• Putting the P(mutex) before the P(empty), which deadlocks.
• Leaving SEM_UNDO off a mutex, so a crash leaves the machine locked.
• Claiming the race condition from one run. If the program happens to print 4000, a student

who says "it works" has not understood the exercise. Run it ten times.

For the journal

Write the aim, MU's own wording, the race program, and the ten answers you got, as a list. Then the semaphore version and its answer. Then the producer-consumer program and its output. The conclusion is two sentences: an unsynchronised critical section loses updates because the read and the write can be separated, and a semaphore makes the section atomic so that the answer is the same every time.

Quick revision

• A critical section is code that touches shared data. c = c + 1 is three machine steps, and a

switch between the read and the write loses an update.

• A race condition is a program whose answer depends on the scheduling order. It is wrong

sometimes, which is worse than wrong always.

• A semaphore is a kernel counter with two atomic operations: wait, also called P or down, and

signal, also called V or up. A binary semaphore, value 0 or 1, is a mutex.

• semget for a SET of semaphores, semop for the operations, semctl for SETVAL, GETVAL and

IPC_RMID. union semun is not in the library and must be declared.

• A new set starts at 0. A mutex must be set to 1 before use.
• SEM_UNDO makes the kernel undo this process's operations if it dies, and belongs on a mutex.
• Producer and consumer need two counting semaphores: empty, started at the number of slots, and

full, started at 0. The producer waits on empty and signals full; the consumer does the opposite.

• Wait for the resource before taking the lock, and release in the opposite order, or the program

deadlocks.

Questions you should be able to answer

1. What is a race condition? A situation where two or more processes access shared data at the same time and the result depends on the order in which they happen to be scheduled, so the program gives different answers on different runs.

2. Why does counter = counter + 1 need protecting when it is one line of C? Because it is three machine operations: read, add, write. A process switched out between the read and the write is working from a value that is already stale, and its write loses the other process's update.

3. What is a semaphore, and what are its two operations called? A counter held by the kernel with two atomic operations: wait, also called P or down, which decrements and blocks at 0; and signal, also called V or up, which increments and wakes a waiting process.

4. What is the difference between a binary semaphore and a counting semaphore? A binary semaphore takes only 0 and 1 and is used for mutual exclusion. A counting semaphore takes any non-negative value and counts instances of a resource.

5. Why does the producer-consumer problem need two semaphores? Because the two sides must wait for different things. The producer waits for a free slot and the consumer waits for a filled one, and one counter cannot represent both.

6. What value does a semaphore have when it is created, and why does that matter? Zero. A mutex left at zero blocks the first process that waits on it, so the program hangs, and semctl with SETVAL must be called first.

7. What does SEM_UNDO do? It makes the kernel record this process's semaphore operations and reverse them if the process dies, so a crash while holding a mutex does not leave the semaphore locked for everybody else.

8. Why must the wait on empty come before the wait on the mutex? Because a producer holding the mutex while waiting for a slot cannot be helped: the consumer needs the mutex to free a slot. Taking the lock last, and releasing in the opposite order, avoids that deadlock.

9. A student runs the unsynchronised counter once, gets the right answer, and says the program is correct. What is wrong with that? A race condition does not fail every time. The answer depends on the scheduling, so one correct run proves nothing; twenty runs on the machine this page was checked on gave the right answer zero times.

The program: a parent and a child, one pipe

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void)
{
    int fd[2];

    if (pipe(fd) == -1) {
        perror("pipe");
        return 1;
    }

    pid_t pid = fork();
    if (pid == -1) {
        perror("fork");
        return 1;
    }

    if (pid == 0) {                       /* the child writes */
        close(fd[0]);                     /* it never reads: close that end */
        const char *msg = "hello down the pipe";
        write(fd[1], msg, strlen(msg) + 1);
        close(fd[1]);
        _exit(0);
    }

    close(fd[1]);                         /* the parent never writes */
    char buf[64];
    ssize_t n = read(fd[0], buf, sizeof buf);
    printf("parent read %zd bytes: [%s]\n", n, buf);
    close(fd[0]);
    wait(NULL);
    return 0;
}

parent read 20 bytes: [hello down the pipe]

Reading the program

pipe(fd) makes the pipe and fills the array with two file descriptors. The convention is fixed and worth memorising: fd[0] is the read end, fd[1] is the write end. Zero for reading because standard input is 0; one for writing because standard output is 1.

fork after pipe, never before. The child inherits the two descriptors because they were open when it was created. A pipe made after the fork exists only in the process that made it.

Each side closes the end it does not use, and this is not tidiness. The parent has fd[1] open, so as far as the kernel is concerned there is still a writer, and when the child closes its copy the pipe does not reach end of file. A parent that forgets close(fd[1]) and reads in a loop waits for ever for data from itself. This single line is the commonest cause of a pipe program that hangs.

write(fd[1], msg, strlen(msg) + 1) writes the string and the + 1 writes the terminating zero byte as well, which is why the parent can print buf as a string and why read returned 20 for a 19-character message. A pipe carries bytes and knows nothing about strings.

read(fd[0], buf, sizeof buf) returns how many bytes it actually got, which may be fewer than you asked for. It returns -1 on error and 0 at end of file.

A pipe is a byte stream, and this is the surprise

The next program has the child write three lines with three separate calls to write, and the parent read in a loop until end of file.

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

int main(void)
{
    int fd[2];
    if (pipe(fd) == -1) {
        perror("pipe");
        return 1;
    }

    if (fork() == 0) {
        close(fd[0]);
        for (int i = 1; i <= 3; i++) {
            char line[32];
            int len = snprintf(line, sizeof line, "item %d\n", i * 10);
            write(fd[1], line, (size_t) len);       /* three writes */
        }
        close(fd[1]);
        _exit(0);
    }

    close(fd[1]);
    char buf[128];
    ssize_t n;
    while ((n = read(fd[0], buf, sizeof buf)) > 0)  /* how many reads? */
        printf("consumer got %zd bytes:\n%.*s", n, (int) n, buf);

    printf("read returned %zd, which is end of file\n", n);
    close(fd[0]);
    wait(NULL);
    return 0;
}

consumer got 24 bytes:
item 10
item 20
item 30
read returned 0, which is end of file

One read, not three. Three writes of 8 bytes each arrived as a single read of 24, on all ten runs. The pipe put the bytes in order and threw away every boundary between them.

That is what "byte stream" means, and it has three consequences a student should be able to state:

• A reader cannot tell how many writes there were. It gets bytes, and it must decide where one

message ends. Here the newline does that job; in a real program it is a length written in front of the data, or a fixed-size record.

• A read may also return less than one write. The opposite case happens with large writes: ask

for 128 bytes and you may get 40, because that is all that had arrived. This is why the read is in a while loop, and why a single read outside one is a bug waiting for a slow writer.

• This is exactly what a message queue fixes. A message queue keeps each message whole, and

that is the subject of [Practical 2 continued: Message Queues, Blocking and Non-blocking].

%.*s in that printf prints exactly n characters of buf and no more. Printing buf as a plain %s would read past the bytes that arrived, because nothing in the pipe wrote a terminating zero this time.

Producer and consumer over a pipe, which is MU's own wording

Compare this with the semaphore version in [Practical 1 continued: the Race Condition, Semaphores, and Producer and Consumer]. It does the same job and there is no semaphore in it, because the pipe blocks for you.

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

#define ITEMS 5

int main(void)
{
    int fd[2];
    if (pipe(fd) == -1) {
        perror("pipe");
        return 1;
    }

    if (fork() == 0) {                          /* the producer */
        close(fd[0]);
        for (int i = 1; i <= ITEMS; i++) {
            int item = i * i;
            if (write(fd[1], &item, sizeof item) != (ssize_t) sizeof item) {
                perror("producer write");
                _exit(1);
            }
            printf("producer: produced %d\n", item);
            fflush(stdout);
        }
        close(fd[1]);                           /* tells the consumer to stop */
        _exit(0);
    }

    close(fd[1]);                               /* the consumer */
    int item;
    ssize_t n;
    int total = 0;
    while ((n = read(fd[0], &item, sizeof item)) == (ssize_t) sizeof item) {
        printf("consumer: consumed %d\n", item);
        total = total + item;
    }
    if (n == -1)
        perror("consumer read");
    printf("consumer: the pipe is closed, the total is %d\n", total);

    close(fd[0]);
    wait(NULL);
    return 0;
}

producer: produced 1
producer: produced 4
producer: produced 9
producer: produced 16
producer: produced 25
consumer: consumed 1
consumer: consumed 4
consumer: consumed 9
consumer: consumed 16
consumer: consumed 25
consumer: the pipe is closed, the total is 55

Three things to take from that output.

The producer got all five items in before the consumer took the first one out. That is not a fault: the pipe has room, in Linux 64 kibibytes by default, and 20 bytes fits easily. The producer only waits when the pipe is full, and the consumer only waits when it is empty. Compare the one-slot semaphore version, where the two alternated strictly because the buffer held exactly one item. A pipe is a bounded buffer that the kernel provides ready-made, and its bound is the pipe's capacity.

An int was sent as four raw bytes, with write(fd[1], &item, sizeof item), and read back the same way. That works because both processes are the same program on the same machine, so the two agree about how an int is laid out. It would not be safe between machines, and it is the reason network programs convert to a defined byte order first.

close(fd[1]) in the producer is what ends the consumer's loop. Without it the consumer's read would block for ever after the fifth item, waiting for a writer that has finished but not said so. The total of 55 at the end is 1 plus 4 plus 9 plus 16 plus 25, and it is there so that the program proves nothing was lost.

A named pipe, which two unrelated programs can use

An anonymous pipe reaches only your own children. A named pipe, or FIFO, is a file in a directory, and any program that can open that file can use it. It is the pipe equivalent of giving a shared memory segment a key.

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

#define PATH "/tmp/munotes_fifo"

int main(void)
{
    unlink(PATH);                          /* in case one is left over */

    if (mkfifo(PATH, 0600) == -1) {
        perror("mkfifo");
        return 1;
    }
    printf("made the named pipe %s\n", PATH);
    fflush(stdout);
    system("ls -l /tmp/munotes_fifo | cut -c1-11");

    if (fork() == 0) {
        int fd = open(PATH, O_WRONLY);     /* blocks until a reader arrives */
        if (fd == -1) {
            perror("child open");
            _exit(1);
        }
        const char *m = "sent through a named pipe";
        write(fd, m, strlen(m) + 1);
        close(fd);
        _exit(0);
    }

    int fd = open(PATH, O_RDONLY);         /* blocks until a writer arrives */
    if (fd == -1) {
        perror("parent open");
        return 1;
    }
    char buf[64];
    ssize_t n = read(fd, buf, sizeof buf);
    printf("parent read %zd bytes: [%s]\n", n, buf);
    close(fd);

    wait(NULL);
    unlink(PATH);                          /* a FIFO must be deleted */
    return 0;
}

made the named pipe /tmp/munotes_fifo
prw-------
parent read 26 bytes: [sent through a named pipe]

The second line of that output is the evidence that a FIFO is a file of its own kind. ls -l prints a letter for the type in the first column, and here it is p, for pipe. An ordinary file prints -, a directory d, a symbolic link l.

Two behaviours of a FIFO are worth knowing and are the reason this program forks:

• open for reading blocks until a writer opens it, and open for writing blocks until a reader does.

That is how the two sides find each other, and it means the writer cannot simply run first and finish. In the laboratory you run the writer in one terminal and the reader in another and watch the first one wait.

• A FIFO is a file and has to be deleted, with unlink in a program or rm at the shell.

Like a shared memory segment, it outlives the program that made it; unlike a segment, it shows up in ls.

You can try the same thing with no C at all, which is worth doing once because it makes the idea concrete: mkfifo /tmp/f, then cat < /tmp/f in one terminal and echo hello > /tmp/f in another.

Writing to a pipe nobody is reading

The last of the five properties, and the one that produces a mysterious death.

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

int main(void)
{
    signal(SIGPIPE, SIG_IGN);              /* so we live to print the error */

    int fd[2];
    if (pipe(fd) == -1) {
        perror("pipe");
        return 1;
    }

    close(fd[0]);                          /* there is now no reader at all */

    ssize_t n = write(fd[1], "x", 1);
    printf("write returned %zd, errno says %s\n", n, strerror(errno));
    return 0;
}

write returned -1, errno says Broken pipe

Without the signal(SIGPIPE, SIG_IGN) line that program would not print anything: the kernel sends SIGPIPE to a process that writes to a pipe with no reader, and the default action for SIGPIPE is to kill it. The program simply disappears, with no message, and a student looks for a bug in the loop above.

That is also why ls | head -1 does not print an error when head stops reading: ls is killed by SIGPIPE, which is the intended design.

Pipes against shared memory

The full comparison, with message queues in it as well, is in [Practical 2 continued: Message Queues, Blocking and Non-blocking].

Procedure

1. Write the first program. Compile with gcc -Wall -Wextra -o pipe1 pipe1.c and run it.
2. Remove the parent's close(fd[1]), put the parent's read in a while loop, and run it again.

The program hangs. Press Ctrl+C and put the line back.

1. Write the three-write program and count the reads. Note that the boundaries are gone.
2. Write the producer-consumer program and confirm the total.
3. Write the FIFO program. Run ls -l /tmp/munotes_fifo yourself while it is running and note the

p.

1. At the shell: mkfifo /tmp/f, then cat < /tmp/f in one terminal and echo hello > /tmp/f in

another. Then rm /tmp/f.

Result

Two processes exchanged data through an anonymous pipe with no semaphore, because a pipe blocks on an empty read and on a full write. Three separate writes were shown to arrive as one read, which establishes that a pipe is a byte stream with no message boundaries. The producer-consumer problem was solved over a pipe and the total proved nothing was lost. A named pipe was created, seen in ls -l as type p, used between two processes and deleted.

Where marks are lost

• Not closing the unused end. The reader keeps a write end open, end of file never arrives,

and the program hangs. This is the single commonest fault in this exercise.

• pipe after fork. The two processes then have two different pipes.
• Mixing up fd[0] and fd[1]. Zero reads, one writes.
• Reading once instead of in a loop, and assuming one read returns one write.
• Printing the buffer with %s when nothing wrote a terminating zero. Use %.*s and the

count that read returned.

• Forgetting to unlink the FIFO, so the next run fails with EEXIST from mkfifo.
• Not knowing why a program writing to a closed pipe dies silently. It is SIGPIPE.

For the journal

Write the aim, MU's own wording, the first program and its output, and then the producer-consumer program with its output and the total. Add the three-write experiment and one sentence saying how many reads it took and why. If your college asks for the named pipe as well, add the mkfifo program and the ls -l line showing the p. The conclusion: a pipe gives message passing with the synchronisation done by the kernel, at the cost of copying the data and of losing the boundaries between writes.

Quick revision

• A pipe is a one-way channel in the kernel. pipe(fd) gives fd[0] to read and fd[1] to

write. Make it before the fork.

• Each process closes the end it does not use, or end of file never arrives.
• read returns the number of bytes it got, 0 at end of file, -1 on error.
• A pipe is a byte stream: three writes may arrive as one read, and one write may arrive as

several reads. The reader has to find the message boundaries itself.

• A read on an empty pipe blocks and a write to a full pipe blocks, so a pipe is a bounded buffer

the kernel provides. No semaphore is needed.

• Writing to a pipe with no reader raises SIGPIPE, which by default kills the writer; ignoring

the signal turns it into EPIPE instead.

• A named pipe is made with mkfifo, is a file whose ls -l type is p, works between unrelated

programs, blocks on open until the other side arrives, and must be deleted.

• Message passing copies the data twice and synchronises for free. Shared memory copies nothing

and synchronises not at all.

Questions you should be able to answer

1. Which of fd[0] and fd[1] is the read end? fd[0]. It matches standard input being 0 and standard output being 1.

2. Why must pipe be called before fork? Because the child inherits the descriptors that were open when it was created. A pipe made afterwards exists only in the process that made it.

3. A program reads from a pipe in a loop and never finishes, although the writer has ended. Why? The reader still has the write end open, so the kernel does not report end of file. Each side must close the end it does not use.

4. Three writes of eight bytes were made. How many reads does the other side need? It cannot be known. A pipe is a byte stream with no boundaries: in the run on this page one read of 24 bytes took all three. The reader must delimit messages itself.

5. What does read return at end of file, and when does that happen? Zero, and it happens when the pipe is empty and every write end has been closed.

6. What happens when a process writes to a pipe with no reader? It is sent SIGPIPE, which by default kills it with no message. If the signal is ignored or handled, the write fails and sets errno to EPIPE.

7. Give two differences between an anonymous pipe and a named pipe. An anonymous pipe has no name and reaches only related processes; a named pipe is a file in a directory, so any program that can open it may use it, and it has to be deleted afterwards.

8. Why does the producer-consumer over a pipe need no semaphore, when the shared memory version needs two? Because the pipe itself blocks: a read on an empty pipe waits and a write to a full pipe waits, and the kernel does the sleeping and waking. Shared memory does nothing of the kind.

sender  : sent [item 10]
sender  : sent [item 20]
sender  : sent [item 30]
receiver: got 64 bytes, type 1, [item 10]
receiver: got 64 bytes, type 1, [item 20]
receiver: got 64 bytes, type 1, [item 30]

Three sends, three receives. Compare that with the pipe, where three writes became one read. Each msgrcv returned 64 bytes, which is the size of mtext, because the sender asked for all 64 to be sent: a message queue delivers exactly what was posted, and the length is part of the message.

msgget(IPC_PRIVATE, IPC_CREAT | 0600) takes only a key and flags, and no size: a queue grows as messages are put into it, up to a system limit. The permission bits are the same idea as for shared memory.

The wait(NULL) in the middle is there only to make the page's output tidy, by letting all three messages be sent before any is received. It is not needed for correctness, and that is the point of the next section.

Blocking, which is what message passing gives you for nothing

A receive on an empty queue blocks: the process is put to sleep by the kernel and woken when a message arrives. A send to a full queue blocks in the same way.

That single behaviour is the reason the producer-consumer over a message queue needs no semaphore, no shared counter, and no wait.

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/msg.h>

#define ITEMS 5

struct message {
    long mtype;
    int  item;
};

int main(void)
{
    int q = msgget(IPC_PRIVATE, IPC_CREAT | 0600);
    if (q == -1) {
        perror("msgget");
        return 1;
    }

    if (fork() == 0) {                          /* the producer */
        struct message m = { .mtype = 1, .item = 0 };
        for (int i = 1; i <= ITEMS; i++) {
            m.item = i * i;
            if (msgsnd(q, &m, sizeof m.item, 0) == -1) {
                perror("msgsnd");
                _exit(1);
            }
            printf("producer: produced %d\n", m.item);
            fflush(stdout);
        }
        m.mtype = 2;                            /* type 2 means "I am done" */
        msgsnd(q, &m, sizeof m.item, 0);
        _exit(0);
    }

    if (fork() == 0) {                          /* the consumer */
        struct message m;
        int total = 0;
        for (;;) {
            /* -2 means: the lowest type that is 2 or less, so an item
               (type 1) is always preferred over the end marker (type 2) */
            if (msgrcv(q, &m, sizeof m.item, -2, 0) == -1) {
                perror("msgrcv");
                _exit(1);
            }
            if (m.mtype == 2)
                break;
            printf("consumer: consumed %d\n", m.item);
            fflush(stdout);
            total = total + m.item;
        }
        printf("consumer: the sender has finished, the total is %d\n", total);
        fflush(stdout);
        _exit(0);
    }

    while (wait(NULL) > 0)
        ;
    msgctl(q, IPC_RMID, NULL);
    return 0;
}

producer: produced 1
consumer: consumed 1
producer: produced 4
consumer: consumed 4
producer: produced 9
consumer: consumed 9
producer: produced 16
consumer: consumed 16
producer: produced 25
consumer: consumed 25
consumer: the sender has finished, the total is 55

That order is one run's, not the program's. The two processes are racing, and nothing here makes them take turns. This run went back and forth, a produce and then a consume. Another run sends all five before the consumer is given the processor, and prints the five produced lines in a block. Both are correct, so the check on this page compares these lines without their order, on all ten runs.

What holds on every run is this. Each square is produced once and consumed once. The consumer takes the items in the order they were sent, because a queue is first in, first out. And the total is 55, which is 1 plus 4 plus 9 plus 16 plus 25, printed so that the program proves no item was lost or counted twice.

A tidy page is exactly what the wait(NULL) in the previous program was buying. Here there is no wait, the producer and the consumer are alive at the same time, and so the page cannot be tidy. That is not a fault to be repaired. It is the blocking receive doing its work, and it is the reason this producer-consumer needs no semaphore at all.

The end marker is the idea worth taking from this program. A pipe tells the reader it is finished by reaching end of file when the writer closes it. A message queue has no such thing: it does not know who is using it. So the producer sends one last message of a different type, and the consumer stops when it sees that type. It is the standard answer, and an examiner asks for it as "how does the consumer know when to stop".

The -2 in the consumer's msgrcv is doing real work, and the next section explains it.

Selecting a message by its type

The fourth argument of msgrcv is the type to ask for, and it has three quite different meanings depending on its sign. This program sends three messages of types 10, 20 and 30 and then takes them out in a deliberately awkward order.

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <sys/ipc.h>
#include <sys/msg.h>

struct message {
    long mtype;
    char mtext[32];
};

int main(void)
{
    int q = msgget(IPC_PRIVATE, IPC_CREAT | 0600);
    if (q == -1) {
        perror("msgget");
        return 1;
    }

    struct message m;
    const char *body[] = { "for the teacher", "for the student", "for anybody" };
    long types[] = { 10, 20, 30 };

    for (int i = 0; i < 3; i++) {
        m.mtype = types[i];
        snprintf(m.mtext, sizeof m.mtext, "%s", body[i]);
        if (msgsnd(q, &m, sizeof m.mtext, 0) == -1) {
            perror("msgsnd");
            return 1;
        }
    }

    /* a positive type: exactly that type */
    msgrcv(q, &m, sizeof m.mtext, 20, 0);
    printf("asked for type 20, got type %ld: [%s]\n", m.mtype, m.mtext);

    /* a negative type: the LOWEST type that is not more than its size */
    msgrcv(q, &m, sizeof m.mtext, -25, 0);
    printf("asked for the lowest type up to 25, got type %ld: [%s]\n",
           m.mtype, m.mtext);

    /* zero: whatever is at the front of the queue */
    msgrcv(q, &m, sizeof m.mtext, 0, 0);
    printf("asked for any type, got type %ld: [%s]\n", m.mtype, m.mtext);

    /* and now the queue is empty, and we ask without waiting */
    ssize_t n = msgrcv(q, &m, sizeof m.mtext, 0, IPC_NOWAIT);
    printf("the queue is empty now: msgrcv returned %zd, errno says %s\n",
           n, strerror(errno));

    msgctl(q, IPC_RMID, NULL);
    return 0;
}

asked for type 20, got type 20: [for the student]
asked for the lowest type up to 25, got type 10: [for the teacher]
asked for any type, got type 30: [for anybody]
the queue is empty now: msgrcv returned -1, errno says No message of desired type

That output is the whole rule, and it is worth putting in a table because an examiner asks it directly.

The second line of the output is the one to look at twice. The queue held types 10, 20 and 30; type 20 had already been taken; asking for -25 means "the lowest type up to 25", and the answer was type 10, not type 20 and not the front of the queue. That is what makes a message type usable as a priority: send urgent work as type 1 and ordinary work as type 5, receive with a negative number, and the urgent work comes out first however late it arrived.

It is also why the producer-consumer above used -2: items are type 1 and the end marker is type 2, so as long as any item remains the consumer takes an item, and it sees the marker only when the items have run out. With a plain 0 there the consumer would take the marker as soon as it reached the front, and stop early.

Blocking against non-blocking

The last line of that program is the other half of MU's bullet. IPC_NOWAIT in the flags means do not block: if there is nothing to receive, fail immediately instead of waiting.

msgrcv returned -1, errno says No message of desired type

errno is ENOMSG, and the message is the system's own wording. The same flag on msgsnd means do not wait for room in a full queue, and then the error is EAGAIN.

Blocking is the right default, and a student should say so and know why: a blocked process uses no processor time at all. The kernel takes it off the run queue and puts it back when the message arrives. A non-blocking receive in a loop, by contrast, asks the kernel over and over, gets -1 every time, and keeps a whole processor busy doing nothing. That pattern is called a busy-wait or a spin, and it is almost always the wrong answer.

Non-blocking is right in exactly one situation: when the process has something else to do and wants to check the queue in passing. A program drawing a screen sixty times a second cannot afford to block, so it looks, finds nothing, and carries on drawing.

Looking at a queue from outside

ipcs -q lists the message queues on the machine, as ipcs -m does for shared memory, and msgctl with IPC_STAT lets the program ask about its own queue.

#include <stdio.h>
#include <string.h>
#include <sys/ipc.h>
#include <sys/msg.h>

struct message {
    long mtype;
    char mtext[16];
};

int main(void)
{
    int q = msgget(IPC_PRIVATE, IPC_CREAT | 0600);
    if (q == -1) {
        perror("msgget");
        return 1;
    }

    struct message m = { .mtype = 1, .mtext = "" };
    for (int i = 0; i < 4; i++) {
        snprintf(m.mtext, sizeof m.mtext, "message %d", i);
        msgsnd(q, &m, sizeof m.mtext, 0);
    }

    struct msqid_ds info;
    if (msgctl(q, IPC_STAT, &info) == -1) {
        perror("msgctl IPC_STAT");
        return 1;
    }
    printf("messages waiting in the queue : %lu\n", (unsigned long) info.msg_qnum);
    printf("the most bytes it will hold   : %lu\n", (unsigned long) info.msg_qbytes);
    printf("the permission bits           : %o\n", info.msg_perm.mode & 0777);

    msgctl(q, IPC_RMID, NULL);
    return 0;
}

messages waiting in the queue : 4
the most bytes it will hold   : 16384
the permission bits           : 600

Four messages are waiting, nobody having received any, and the queue will hold 16384 bytes in total, which is the Linux default and is the figure a send would block on. A queue is therefore a bounded buffer as well, exactly like a pipe, and this is its bound.

A note for anyone who goes looking in the manual page: struct msqid_ds also holds the number of bytes currently in the queue, and that member is not portable. On glibc it is spelled __msg_cbytes, with two leading underscores, and asking for msg_cbytes is an error: struct msqid_ds has no member named msg_cbytes; did you mean msg_qbytes?. The three members above are the ones to rely on.

A queue left behind shows in ipcs -q and is removed with ipcrm -q <msqid>, and the same warning applies as for shared memory: a laboratory full of leaked queues eventually stops working for everybody.

Shared memory against message passing, which is MU's own bullet

This is the table to learn. It is the answer to the most likely viva question on Practical 1 and Practical 2 together.

Two sentences to remember it by:

Shared memory is a noticeboard: everybody can read and write it, nobody is told when it

changes, and two people writing at once make a mess.

A message queue is a pigeonhole: things go in whole, come out whole, wait until they are

collected, and can be sorted by who they are for.

Procedure

1. Write the first program. Compile with gcc -Wall -Wextra -o mq1 mq1.c and run it. Count the

sends and the receives.

1. Change sizeof m.mtext to sizeof m in the msgsnd call and run it again. Note what the

receiver prints, and put it back.

1. Write the producer-consumer program. Confirm the total.
2. Change the consumer's -2 to 0 and run it. Explain what happened to the missing items.
3. Write the type-selection program and read the three answers carefully.
4. Write the IPC_STAT program. Then run it with the msgctl(q, IPC_RMID, NULL) line commented

out, and find the queue with ipcs -q. Remove it with ipcrm -q.

Result

Three messages were sent and received whole, each one delivered as it was posted, which a pipe cannot do. The producer-consumer problem was solved over a message queue with no semaphore and no shared counter, because a receive on an empty queue blocks. A message was selected by exact type, by lowest type and by position, and IPC_NOWAIT on an empty queue was shown to return -1 with errno set to ENOMSG instead of waiting.

Where marks are lost

• sizeof m instead of sizeof m.mtext. The size is of everything after mtype.
• mtype not first in the structure, or set to 0 or a negative number. The kernel requires a

positive type in the first member.

• Forgetting msgctl(q, IPC_RMID, NULL). The queue stays on the machine; ipcs -q shows it.
• No end marker, so the consumer blocks for ever after the last item and the program has to be

killed.

• Using 0 as the type in a consumer that also has an end marker, so it stops early.
• Saying "non-blocking is better". It is not: a blocked process uses no processor, and a

non-blocking receive in a loop is a busy-wait.

• Not checking msgsnd and msgrcv. msgrcv returns the number of bytes, and -1 on failure,

which is not the same as 0.

For the journal

Write the aim, MU's own wording, the first program and its output, and the producer-consumer program with its total. Then the type-selection program, and copy the four lines of its output into the journal because they are the answer to the viva question. Add the comparison table of shared memory against message passing; it is two marks on its own. The conclusion: a message queue keeps each message whole and blocks the receiver until one arrives, so it needs no semaphore, and it costs two copies of the data that shared memory does not.

Quick revision

• A message queue is a kernel-held list of whole messages. msgget, msgsnd, msgrcv, msgctl.
• The message structure starts with long mtype, which must be positive. The size passed to

msgsnd and msgrcv is the size of the rest, not of the whole structure.

• A message goes in whole and comes out whole, unlike a pipe, which is a byte stream.
• The type argument of msgrcv: positive means exactly that type, zero means the front of the

queue, negative means the lowest type not greater than its size. Negative is how priorities are done.

• A blocking receive on an empty queue sleeps and uses no processor. IPC_NOWAIT returns -1 at

once with ENOMSG; a non-blocking send to a full queue gives EAGAIN.

• A consumer knows the producer has finished because the producer sends a last message of a

different type. There is no end of file on a queue.

• msgctl with IPC_STAT fills a struct msqid_ds: msg_qnum is how many messages are waiting,

msg_qbytes is the capacity, 16384 by default on Linux.

• ipcs -q lists queues, ipcrm -q <id> removes one.
• Shared memory: no copies, no synchronisation. Message passing: two copies, synchronisation free.

Questions you should be able to answer

1. What must the first member of a message structure be, and why? A long holding the message type. The kernel reads it to decide which receiver the message can satisfy, and it must be a positive number.

2. What size is passed to msgsnd? The size of the structure after mtype, so sizeof m.mtext and not sizeof m.

3. Three writes were made. How many receives does a message queue need, and how many did a pipe need? The queue needs three, because each message is delivered whole. The pipe took one read of 24 bytes for three writes of 8, because it is a byte stream.

4. What are the three meanings of the type argument to msgrcv? A positive number asks for exactly that type; zero asks for the message at the front of the queue; a negative number asks for the lowest type that is not greater than its absolute value.

5. How would you give some messages priority over others? Send the urgent ones with a low type number and receive with a negative type. The lowest type present is delivered first, whenever it arrived.

6. What does a non-blocking receive return on an empty queue? Minus one, with errno set to ENOMSG, whose message is "No message of desired type".

7. Is non-blocking communication better than blocking? No. A blocked process is asleep and uses no processor time; a non-blocking receive in a loop is a busy-wait that keeps a processor working for nothing. Non-blocking is right only when the process has other work to do between checks.

8. How does a consumer on a message queue know the producer has finished? The producer sends a final message of a distinct type, which the consumer treats as an end marker. A queue has no end of file, because the kernel does not know who is using it.

9. Give the one-line difference between shared memory and message passing. Shared memory copies nothing and synchronises nothing; message passing copies the data twice and does the synchronising for you.

The first program: one thread, created and joined

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

static void *worker(void *arg)
{
    const char *name = arg;
    printf("the thread says: hello, I am %s\n", name);
    return NULL;
}

int main(void)
{
    pthread_t t;

    int rc = pthread_create(&t, NULL, worker, "worker one");
    if (rc != 0) {
        fprintf(stderr, "pthread_create: %s\n", strerror(rc));
        return 1;
    }

    printf("main   says: I made a thread and I am waiting for it\n");

    pthread_join(t, NULL);

    printf("main   says: the thread has finished\n");
    return 0;
}

main   says: I made a thread and I am waiting for it
the thread says: hello, I am worker one
main   says: the thread has finished

Those three lines are printed here in the order they came out on the first run, and it is worth being clear about which parts of that order are guaranteed and which are not.

• The third line is guaranteed to be last. pthread_join does not return until the thread has

finished.

• The first two can come in either order, because as soon as pthread_create returns there

are two threads both ready to print. And they did: the first draft of this page claimed all ten runs gave the order above, and the checker refused it, because run 3 of 5 printed the thread first. The program is not wrong when that happens, and a book that printed one order as a fact would have been.

That is the honest answer to MU's bullet about observing execution order, and the next section makes it unmistakable.

The thread function's shape is fixed: it takes a void and returns a void . Every thread function in every program looks like void name(void arg), and anything else will not compile.

Execution order, which nothing guarantees

Four threads, each printing one line, all joined afterwards.

#include <stdio.h>
#include <pthread.h>

static void *say(void *arg)
{
    long n = (long) arg;
    printf("thread %ld is running\n", n);
    return NULL;
}

int main(void)
{
    pthread_t t[4];

    for (long i = 1; i <= 4; i++) {
        if (pthread_create(&t[i - 1], NULL, say, (void *) i) != 0) {
            perror("pthread_create");
            return 1;
        }
    }
    for (int i = 0; i < 4; i++)
        pthread_join(t[i], NULL);

    printf("all four have finished\n");
    return 0;
}

thread 1 is running
thread 2 is running
thread 3 is running
thread 4 is running
all four have finished

That order is one of many. Run eight times on the machine this page was checked on, the four thread lines came out in seven different orders. The page prints them in numerical order because a book has to print something, and the checker compares the lines as a set: it requires that each of the four appears exactly once on every run, and leaves the order open, because the order is not a property of the program.

The last line is different. It is after four joins, so it is always last, and that is the point of joining.

(void *) i passes the number itself as the pointer value, and (long) arg takes it out again. It is a common shortcut and it is safe for a small integer. What is not safe, and is the classic bug in this exercise, is passing the address of the loop variable:

pthread_create(&t[i], NULL, say, &i);     /* WRONG */

Every thread then gets the same address, the loop keeps changing what is at that address, and the threads print whatever i happens to be when each of them looks. The answers are not merely unordered, they are wrong, and often all the same.

What threads share

This is the program that shows the difference from fork in one line of output. Compare it with the counter in [Processes: fork, wait, exec, and Why Two Programs Need to Talk], where the child's change was invisible to the parent.

#include <stdio.h>
#include <pthread.h>

static int shared = 0;                   /* a global: every thread sees it */

static void *bump(void *arg)
{
    (void) arg;                          /* unused, and said so */
    shared = shared + 100;
    printf("thread: I set shared to %d\n", shared);
    return NULL;
}

int main(void)
{
    pthread_t t;

    printf("main  : shared starts at %d\n", shared);
    if (pthread_create(&t, NULL, bump, NULL) != 0)
        return 1;
    pthread_join(t, NULL);
    printf("main  : after the thread, shared is %d\n", shared);
    return 0;
}

main  : shared starts at 0
thread: I set shared to 100
main  : after the thread, shared is 100

One hundred, not zero. The thread's change is visible in main, because there is only one shared and both threads are looking at it. That is the whole reason threads exist, and the whole reason they are dangerous.

(void) arg; on its own line is how a C program says "I know this parameter is unused". Without it, -Wextra warns, and a warning is not allowed in this book.

Passing an argument in and getting a result out

A thread function takes one void and returns one void , which looks restrictive until you pass the address of a structure.

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

struct job {
    int from;
    int to;
};

static void *sum_range(void *arg)
{
    struct job *j = arg;

    long *total = malloc(sizeof *total);
    if (total == NULL)
        return NULL;

    *total = 0;
    for (int i = j->from; i <= j->to; i++)
        *total = *total + i;

    return total;                        /* the caller must free this */
}

int main(void)
{
    struct job j = { 1, 100 };
    pthread_t t;

    if (pthread_create(&t, NULL, sum_range, &j) != 0)
        return 1;

    void *result;
    pthread_join(t, &result);

    long *total = result;
    printf("the thread added 1 to 100 and returned %ld\n", *total);
    free(total);
    return 0;
}

the thread added 1 to 100 and returned 5050

Five thousand and fifty is right: the sum of 1 to 100 is 100 times 101 divided by 2.

The return value is malloced, and that is not laziness. A thread's stack is gone the moment it finishes, so returning the address of a local variable returns a pointer to memory that no longer exists. The three safe ways to get a result out of a thread:

1. malloc it in the thread and free it in the joiner, as above.
2. Write it into a variable the caller owns, whose address was passed in, which is what the next

two chapters do.

1. Write it into a global or a static array, indexed by the thread's number.

Delays, and why sleep is not synchronisation

MU's bullet asks for delays to be observed, and the honest lesson is a warning.

#include <stdio.h>
#include <time.h>
#include <pthread.h>

static void *slow(void *arg)
{
    long n = (long) arg;
    struct timespec pause = { 0, 0 };
    pause.tv_nsec = n * 100000000L;      /* n tenths of a second */
    nanosleep(&pause, NULL);
    printf("thread %ld woke up after %ld tenths of a second\n", n, n);
    fflush(stdout);
    return NULL;
}

int main(void)
{
    pthread_t t[3];

    for (long i = 1; i <= 3; i++)
        pthread_create(&t[i - 1], NULL, slow, (void *) i);

    for (int i = 0; i < 3; i++)
        pthread_join(t[i], NULL);

    printf("main: all three are done\n");
    return 0;
}

thread 1 woke up after 1 tenths of a second
thread 2 woke up after 2 tenths of a second
thread 3 woke up after 3 tenths of a second
main: all three are done

Here the sleeps are far enough apart that the order comes out the same every time, and that is exactly what makes sleep so tempting and so wrong. A student who wants thread A to finish before thread B writes sleep(1) in B, sees it work, and ships it. It works until the machine is busy, or the data is bigger, or the marks are being given.

A delay is not a synchronisation. It makes a race less likely and no less possible. The

tools that actually order two threads are pthread_join, a mutex, a semaphore and a condition

variable, and they are the subject of the next three chapters.

nanosleep is used rather than sleep because sleep takes whole seconds. The structure takes seconds and nanoseconds, and tv_nsec must be less than one thousand million or the call fails with EINVAL.

Sequential against threaded: the measurement

MU's third bullet. This is the one place in the chapter where the answer depends on the machine, so the program measures and the page reports what it measured.

Work that waits

Four tasks, each of which does nothing for one second. That stands for what real programs actually spend their time on: waiting for a disk, a database or a network.

#include <stdio.h>
#include <time.h>
#include <pthread.h>

#define TASKS 4

static void *fetch(void *arg)
{
    long k = (long) arg;
    struct timespec one = { 1, 0 };
    nanosleep(&one, NULL);               /* waiting for something slow */
    printf("task %ld has its data\n", k);
    fflush(stdout);
    return NULL;
}

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double) ts.tv_sec + (double) ts.tv_nsec / 1e9;
}

int main(void)
{
    double t0 = now();
    for (long k = 1; k <= TASKS; k++)
        fetch((void *) k);
    printf("one after another : %.0f seconds\n", now() - t0);

    pthread_t t[TASKS];
    double t1 = now();
    for (long k = 1; k <= TASKS; k++)
        pthread_create(&t[k - 1], NULL, fetch, (void *) k);
    for (int k = 0; k < TASKS; k++)
        pthread_join(t[k], NULL);
    printf("all four at once  : %.0f second\n", now() - t1);
    return 0;
}

task 1 has its data
task 2 has its data
task 3 has its data
task 4 has its data
one after another : 4 seconds
task 1 has its data
task 2 has its data
task 3 has its data
task 4 has its data
all four at once  : 1 second

Four seconds against one, every time. That is a fourfold speedup and it does not depend on the machine having four processors, because the four threads are not computing, they are asleep. A sleeping thread occupies no processor at all, so all four can be asleep at once on a machine with one.

This is the single most useful thing to know about threads in practice: threads overlap waiting. A program that fetches four web pages, or reads four files, or serves four users, is four times faster with four threads on any machine.

Work that computes

Now the same experiment with arithmetic instead of sleeping, and here the answer changes.

#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>

#define THREADS 2
#define ROUNDS  30000000UL

static unsigned long answer[THREADS];

/* a chain in which each step needs the one before it, so the compiler
   cannot skip the loop and cannot do several steps at a time */
static void *work(void *arg)
{
    long k = (long) arg;
    unsigned long x = 12345UL + (unsigned long) k;
    for (unsigned long i = 0; i < ROUNDS; i++)
        x = x * 6364136223846793005UL + 1442695040888963407UL;
    answer[k] = x;
    return NULL;
}

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double) ts.tv_sec + (double) ts.tv_nsec / 1e9;
}

int main(void)
{
    printf("processors the system reports   : %ld\n",
           sysconf(_SC_NPROCESSORS_ONLN));

    double t0 = now();
    for (long k = 0; k < THREADS; k++)
        work((void *) k);
    double seq = now() - t0;
    unsigned long a = answer[0] + answer[1];

    pthread_t t[THREADS];
    double t1 = now();
    for (long k = 0; k < THREADS; k++)
        pthread_create(&t[k], NULL, work, (void *) k);
    for (int k = 0; k < THREADS; k++)
        pthread_join(t[k], NULL);
    double par = now() - t1;
    unsigned long b = answer[0] + answer[1];

    printf("one chunk after another, clock  : %.2f seconds\n", seq);
    printf("both chunks in threads, clock   : %.2f seconds\n", par);
    printf("the two answers agree           : %s\n", a == b ? "yes" : "NO");
    return 0;
}

processors the system reports   : 2
one chunk after another, clock  : 1.18 seconds
both chunks in threads, clock   : 1.29 seconds
the two answers agree           : yes

No speedup at all, and the threaded version was slightly slower.

That is a real result on a real machine and the chapter is not going to pretend otherwise. The reason is worth understanding, because it is the most important limit on threading:

Two threads doing arithmetic are only faster than one if there are

two processors free to run them. The lab container this book is checked in reports two

processors, and measuring it directly shows that two processes doing the same work take twice as

long as one, so it has one processor's worth of throughput to give. With one processor, two

threads share it, and the total time is the same plus the cost of creating and switching between

them.

On your own laboratory machine, which probably has four or eight real cores and nothing else running, the same program should show the threaded time at close to half the sequential time. Run it and see: that is the experiment, and either answer is a correct result to write in the journal as long as you also write the number of processors.

Three honest conclusions from the pair of measurements, and they are what an examiner is looking for:

1. Threads always help with work that waits, on any machine, because waiting needs no

processor.

1. Threads help with work that computes only up to the number of processors available. Eight

threads on four cores is not twice as fast as four.

1. Threads are never free. Creating one costs time, and switching between them costs time, so

a job too small to notice is slower with threads than without.

And one about measurement itself, which was learned the hard way while this page was being checked: the first version of this program used a simpler loop, s += i % 7, and with optimisation turned on the compiler removed most of the work, so the whole measurement was of nothing. A timing experiment has to be checked by looking at whether the answer it computes is actually used, and this version prints the answers and compares them for exactly that reason.

Detaching a thread, and the resources a finished thread holds

A thread that has finished is not entirely gone: its return value and a little book-keeping are kept until somebody joins it. A program that creates a thousand threads and joins none of them runs out of memory.

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <pthread.h>

static void *quick(void *arg)
{
    (void) arg;
    return NULL;
}

int main(void)
{
    int made = 0;

    for (int i = 0; i < 2000; i++) {
        pthread_t t;
        int rc = pthread_create(&t, NULL, quick, NULL);
        if (rc != 0) {
            printf("pthread_create failed at thread %d: %s\n", i, strerror(rc));
            break;
        }
        pthread_detach(t);               /* nobody will ever join it */
        made++;
    }

    printf("created and detached %d threads without running out\n", made);
    return 0;
}

created and detached 2000 threads without running out

pthread_detach(t) tells the library that nobody will join this thread, so it may release everything the moment the thread ends. Two thousand threads came and went and nothing accumulated.

The rule: every thread is either joined or detached. A joinable thread that nobody joins is a leak, exactly like a fork with no wait. Which of the two to choose is a question about the program:

An attribute can also be set before creation, with pthread_attr_setdetachstate, which is the tidier way when every thread of a kind is to be detached.

Threads against processes

The comparison table, and a likely viva question.

The line that matters most in practice is the crash: one thread that writes past the end of an array kills every thread in the process, because they are all in the same address space. That is why a web browser puts each tab in a process and not in a thread.

Procedure

1. Write the first program. Compile with gcc -Wall -Wextra -pthread -o thread1 thread1.c.
2. Leave -pthread off the command deliberately and read the error. Put it back.
3. Run the four-thread program ten times and write down the order each time.
4. Change the fourth argument of pthread_create to &i and run it again. Note that the numbers

are now wrong, not merely out of order, and put it back.

1. Write the shared-global program and confirm main sees 100.
2. Write the summing program and confirm 5050. Change the thread to return the address of a local

variable instead and note that the answer is now rubbish.

1. Write the waiting measurement and record both times.
2. Write the computing measurement, record both times and the number of processors your

machine reports, and write one sentence explaining the result you got.

1. Write the detaching program. Remove the pthread_detach line and run it again.

Result

Threads were created and joined, and the thread lifecycle from creation to joining was followed. A global variable changed by a thread was seen by main, which processes cannot do. The order in which four threads ran was found to differ from run to run, and joining was the only thing that imposed an order. An argument was passed into a thread and a result returned from it. Four tasks that wait took four seconds one after another and one second in parallel, on any machine; two tasks that compute took the same time either way on a machine with one processor's worth of throughput.

Where marks are lost

• Forgetting -pthread. The program does not link, and the message names pthread_create,

which looks like a mistake in the program.

• Checking pthread_create for -1. It returns 0 on success and an error number on failure,

and never sets errno.

• Passing &i from a loop. Every thread reads the same changing variable.
• Returning the address of a local variable from a thread function. The stack is gone.
• Neither joining nor detaching. A finished thread holds resources until one of the two

happens.

• Using sleep to make threads run in a particular order and calling it synchronisation.
• Claiming a speedup from one measurement, or without saying how many processors the machine

has. An examiner who knows the machine has one core will ask.

• Writing the thread function with the wrong shape. It is void f(void arg) and nothing

else.

For the journal

Write the aim, MU's own wording, the first program and its output, and the four-thread program with the ten orders you observed, as a list. That list is the evidence for the bullet about execution order and it is worth more than any sentence. Then the two measurements, with the number of processors your machine reports beside them, and one sentence explaining the result. The conclusion: threads share the address space, so they need no shared memory to exchange data and no order is guaranteed between them; joining is what orders them; and threading speeds up waiting on any machine but speeds up computing only up to the number of processors.

Quick revision

• A thread shares the code, the globals, the heap and the open files of its process, and has its

own stack, registers and thread identifier.

• #include <pthread.h> and compile with -pthread.
• The pthread calls return 0 on success and an error number on failure. They do not set

errno.

• A thread function is void f(void arg), always.
• Lifecycle: new, runnable, running, blocked, terminated, joined. A terminated thread that is

neither joined nor detached holds resources, like a zombie process.

• Nothing orders two threads except pthread_join, a mutex, a semaphore or a condition variable.

A sleep is not a synchronisation.

• Pass a small integer as (void *) i and read it back as (long) arg; never pass the address of

a loop variable.

• Return a result through malloced memory, or through a variable the caller owns, never through

the thread's own stack.

• Threads overlap waiting on any machine, and overlap computing only up to the number of

processors. Creating and switching them is not free.

• One thread crashing kills the whole process, which a separate process would not.

Questions you should be able to answer

1. What does a thread share with the other threads of its process, and what does it keep to itself? It shares the code, global and static variables, the heap and the open files. It keeps its own stack, so local variables are private, its own registers and its own thread identifier.

2. How does pthread_create report failure? It returns an error number, and 0 on success. It does not return -1 and it does not set errno, so strerror on the returned value is how the reason is printed.

3. Four threads each print one line. What order do the lines come out in? Any order. On the machine this page was checked on, eight runs gave seven different orders. Only pthread_join imposes an order.

4. Why must a thread not return the address of one of its local variables? Because its stack is released when it finishes, so the address points at memory that is no longer the variable.

5. What is wrong with passing &i to every thread in a loop? They all receive the same address, and the loop keeps changing what is there, so each thread reads whatever value i has when it happens to look.

6. A thread has finished and nobody has joined it. What is the problem? Its return value and its book-keeping are still held, so it is a leak. Every thread must be either joined or detached.

7. Four tasks that each wait one second: how long with one thread and how long with four? Four seconds and one second, on any machine, because a sleeping thread needs no processor.

8. Two threads doing arithmetic on a machine with one processor: how much faster? Not faster at all, and slightly slower once the cost of creating and switching them is counted. Computing overlaps only when there are processors free.

9. Why does a web browser use a separate process for each tab rather than a thread? Because threads share one address space, so a crash in one takes down the whole process. A separate process fails on its own.

The rule this illustrates is the useful one: it is not sharing that needs protecting, it is sharing at the same time.

unsigned long rather than int, because F(47) is 2971215073, which is more than an int holds on any machine a student will meet. Even unsigned long runs out at F(93). A program that prints F(100) needs a bigger type or its own addition.

Computing separate terms: four threads, four answers

Here the work really is parallel, and each thread is given a small structure of its own to write its answer into.

#include <stdio.h>
#include <pthread.h>

#define WORKERS 4

struct task {
    int           n;                  /* which Fibonacci number to compute */
    unsigned long answer;             /* where this thread puts its result */
};

static unsigned long fib_of(int n)
{
    unsigned long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        unsigned long c = a + b;
        a = b;
        b = c;
    }
    return a;
}

static void *compute(void *arg)
{
    struct task *t = arg;
    t->answer = fib_of(t->n);         /* only this thread writes this slot */
    return NULL;
}

int main(void)
{
    struct task job[WORKERS] = { { 10, 0 }, { 20, 0 }, { 30, 0 }, { 40, 0 } };
    pthread_t t[WORKERS];

    for (int i = 0; i < WORKERS; i++)
        if (pthread_create(&t[i], NULL, compute, &job[i]) != 0) {
            perror("pthread_create");
            return 1;
        }

    for (int i = 0; i < WORKERS; i++)
        pthread_join(t[i], NULL);

    for (int i = 0; i < WORKERS; i++)
        printf("thread %d: Fibonacci number %d is %lu\n",
               i + 1, job[i].n, job[i].answer);
    return 0;
}

thread 1: Fibonacci number 10 is 55
thread 2: Fibonacci number 20 is 6765
thread 3: Fibonacci number 30 is 832040
thread 4: Fibonacci number 40 is 102334155

That output is in order on every run, and there is still no mutex. Two design decisions did that, and they are the two habits worth taking from this chapter.

Each thread has a slot of its own. job[0] is written only by the first thread, job[1] only by the second. Threads that never touch the same memory cannot race, however many of them there are. This is the best kind of thread safety: the kind you get by dividing the data rather than by locking it.

Main prints after joining them all. The threads finish in whatever order they like, and the printing is done afterwards by one thread in index order, so the output is tidy without any ordering being imposed on the work. Compare [Practical 3: Threading and Single Thread Control Flow], where the threads printed for themselves and the order was different on every run.

&job[i] is passed, not &i. Passing &i would give every thread the same address, and the loop would keep changing what was there. That bug is described in Practical 3 and it is worth looking for in your own code every time you write this loop.

Thread safety: the shared counter that loses updates

Now let several threads write the same variable, with nothing to stop them. This is the thread version of the race condition from [Practical 1 continued: the Race Condition, Semaphores, and Producer and Consumer], and it is easier to produce here because threads need no shared memory segment: a plain global is enough.

Four threads, each adding one to the counter two thousand times. The right answer is eight thousand. The program runs the whole experiment twenty times and reports.

#include <stdio.h>
#include <sched.h>
#include <pthread.h>

#define THREADS 4
#define EACH    2000
#define TRIALS  20

static long counter;                  /* shared by every thread, unprotected */

static void *bump(void *arg)
{
    (void) arg;
    for (int i = 0; i < EACH; i++) {
        long v = counter;             /* read  */
        sched_yield();                /* the window the race lives in */
        counter = v + 1;              /* write */
    }
    return NULL;
}

int main(void)
{
    int right = 0;
    long lowest = (long) THREADS * EACH;

    for (int trial = 0; trial < TRIALS; trial++) {
        counter = 0;
        pthread_t t[THREADS];
        for (int i = 0; i < THREADS; i++)
            if (pthread_create(&t[i], NULL, bump, NULL) != 0)
                return 1;
        for (int i = 0; i < THREADS; i++)
            pthread_join(t[i], NULL);

        if (counter == (long) THREADS * EACH)
            right++;
        if (counter < lowest)
            lowest = counter;
    }

    printf("threads, each adding %d      : %d\n", EACH, THREADS);
    printf("the right answer each time    : %d\n", THREADS * EACH);
    printf("trials that gave it, out of %d : %d\n", TRIALS, right);
    printf("the lowest total seen         : %ld\n", lowest);
    printf("updates were lost             : %s\n", right < TRIALS ? "yes" : "no");
    return 0;
}

threads, each adding 2000      : 4
the right answer each time    : 8000
trials that gave it, out of 20 : 0
the lowest total seen         : 2000
updates were lost             : yes

Zero out of twenty, and the worst run reached only a quarter of the right total. Two thousand out of eight thousand means that on that trial, three of the four threads' work was thrown away entirely.

sched_yield() is in the loop for the reason recorded in Practical 1: without it the loop is so fast that the threads may not overlap, and a program that prints the right answer once teaches a student the opposite of the truth.

The mutex

A mutex, short for mutual exclusion, is a lock. One thread holds it at a time; a thread that asks for a held mutex waits until it is released.

A mutex that lives for the whole program needs no init at all: PTHREAD_MUTEX_INITIALIZER sets it up where it is declared, and that is what the next program uses.

A mutex and a binary semaphore do the same job and are not the same thing, and an examiner may ask for the difference:

The counter, corrected

The same program, with a mutex round the three lines that touch the counter. Nothing else has changed, including the sched_yield.

#include <stdio.h>
#include <sched.h>
#include <pthread.h>

#define THREADS 4
#define EACH    2000

static long counter;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void *bump(void *arg)
{
    (void) arg;
    for (int i = 0; i < EACH; i++) {
        pthread_mutex_lock(&lock);        /* enter the critical section */
        long v = counter;
        sched_yield();
        counter = v + 1;
        pthread_mutex_unlock(&lock);      /* leave it */
    }
    return NULL;
}

int main(void)
{
    pthread_t t[THREADS];

    for (int i = 0; i < THREADS; i++)
        if (pthread_create(&t[i], NULL, bump, NULL) != 0) {
            perror("pthread_create");
            return 1;
        }
    for (int i = 0; i < THREADS; i++)
        pthread_join(t[i], NULL);

    printf("expected %d, got %ld\n", THREADS * EACH, counter);
    return 0;
}

expected 8000, got 8000

Exactly eight thousand, on all ten runs. The sched_yield is still there, still inviting the operating system to switch threads in the middle of the critical section, and it no longer matters: any thread that is switched in finds the mutex held and waits.

Four rules about using a mutex, each of which is a mark:

1. Lock and unlock in the same function, on every path out of it. A return between the lock

and the unlock leaves the mutex held for ever and every other thread blocks.

1. Hold it for as short a time as possible. Everything inside the lock happens one thread at a

time, so a long critical section throws the benefit of threading away. Never do input, output or a sleep while holding one.

1. Lock the same mutex for the same data, everywhere. Two functions that protect the same

variable with two different mutexes protect nothing.

1. Take several mutexes in the same order in every thread. Two threads that take A then B and

B then A will deadlock, and that is the subject of [Practical 6: the Readers-Writers Problem].

What a mutex costs

The corrected program is slower than the broken one, and honestly so: every increment now costs a lock and an unlock, and with four threads on a machine with one processor's worth of throughput the whole loop runs one thread at a time. That is not a defect of the mutex, it is the nature of the problem. A counter that every thread must update cannot be parallelised; it can only be made correct.

The way out, where the problem allows it, is the one the four-thread Fibonacci program used: give each thread its own variable and add the results up once at the end. No lock in the hot loop at all, one addition afterwards. That pattern has a name, reduction, and it is the first thing to reach for when a shared counter appears in a threaded program.

Thread pooling and task delegation

MU's third bullet. The programs so far create one thread per piece of work, and that is fine for four pieces. It is wrong for four thousand: creating a thread is not free, and four thousand threads on a four-core machine spend their lives switching rather than working.

A thread pool creates a fixed number of threads once and feeds them work. Task delegation is the handing out: the pool holds a list of tasks, and each worker takes the next one whenever it is free.

#include <stdio.h>
#include <pthread.h>

#define WORKERS 3
#define TASKS   8

struct pool {
    int             next;             /* the next task nobody has taken */
    int             done;             /* how many have been finished */
    unsigned long   answer[TASKS];    /* one slot per task */
    pthread_mutex_t lock;             /* protects next and done */
    pthread_cond_t  all_done;         /* main waits on this */
};

static unsigned long fib_of(int n)
{
    unsigned long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        unsigned long c = a + b;
        a = b;
        b = c;
    }
    return a;
}

static void *worker(void *arg)
{
    struct pool *p = arg;

    for (;;) {
        /* take the next task: this is the only shared thing touched */
        pthread_mutex_lock(&p->lock);
        int task = (p->next < TASKS) ? p->next++ : -1;
        pthread_mutex_unlock(&p->lock);

        if (task < 0)
            break;                    /* no work left: this worker retires */

        /* the work itself is done OUTSIDE the lock */
        unsigned long r = fib_of(10 * (task + 1));

        pthread_mutex_lock(&p->lock);
        p->answer[task] = r;
        p->done++;
        if (p->done == TASKS)
            pthread_cond_signal(&p->all_done);
        pthread_mutex_unlock(&p->lock);
    }
    return NULL;
}

int main(void)
{
    struct pool p = { .next = 0, .done = 0 };
    pthread_mutex_init(&p.lock, NULL);
    pthread_cond_init(&p.all_done, NULL);

    pthread_t t[WORKERS];
    for (int i = 0; i < WORKERS; i++)
        if (pthread_create(&t[i], NULL, worker, &p) != 0) {
            perror("pthread_create");
            return 1;
        }

    /* wait until every task has been finished */
    pthread_mutex_lock(&p.lock);
    while (p.done < TASKS)
        pthread_cond_wait(&p.all_done, &p.lock);
    pthread_mutex_unlock(&p.lock);
    printf("main: all %d tasks are finished\n", TASKS);

    for (int i = 0; i < WORKERS; i++)
        pthread_join(t[i], NULL);

    for (int i = 0; i < TASKS; i++)
        printf("task %d: Fibonacci number %2d is %lu\n",
               i + 1, 10 * (i + 1), p.answer[i]);

    pthread_mutex_destroy(&p.lock);
    pthread_cond_destroy(&p.all_done);
    return 0;
}

main: all 8 tasks are finished
task 1: Fibonacci number 10 is 55
task 2: Fibonacci number 20 is 6765
task 3: Fibonacci number 30 is 832040
task 4: Fibonacci number 40 is 102334155
task 5: Fibonacci number 50 is 12586269025
task 6: Fibonacci number 60 is 1548008755920
task 7: Fibonacci number 70 is 190392490709135
task 8: Fibonacci number 80 is 23416728348467685

Three threads did eight tasks, and the result was byte-identical on all five runs, although which worker did which task is different every time and cannot be known from the output. That is the point of a pool: the answers are deterministic and the scheduling is not.

The three ideas in that program

One counter hands out the work. p->next++ inside the mutex is the whole of task delegation. Each worker takes a number, and the mutex guarantees no two workers take the same one. It is exactly the shared-counter problem of the previous section, and it is the one place a lock is unavoidable.

The work is done outside the lock. fib_of is called after the unlock, not before it. Had it been inside, the three workers would have taken turns and the pool would have been three threads doing one thread's work. This is rule 2 above, and it is the difference between a thread pool and a very slow loop.

A condition variable is how main waits. Main must not go on until all eight are done, and the choices are:

A condition variable is a place to wait for something to become true. Three things about it are always the same, and all three are in the program above:

• It is always used with a mutex. pthread_cond_wait(&cv, &lock) is called with the lock

held; it releases the lock while it sleeps and takes it again before returning. That is what makes testing the condition safe.

• The wait is in a while loop, never an if. A waiting thread can be woken when the

condition is still false, which is called a spurious wakeup, so it must test again.

• The signaller signals while holding the lock, and pthread_cond_signal wakes one waiter

where pthread_cond_broadcast wakes all of them.

How many workers

The useful rule of thumb, and it follows from the measurement in Practical 3:

• Work that computes: as many workers as the machine has processors.

sysconf(_SC_NPROCESSORS_ONLN) asks. More than that only adds switching.

• Work that waits: many more than the number of processors, because a waiting worker occupies

none. A program serving web requests may run hundreds.

Procedure

1. Write the single-thread generator. Compile with gcc -Wall -Wextra -pthread -o fib1 fib1.c and

run it.

1. Change N to 95 and note that the numbers go wrong: unsigned long overflows at F(93).
2. Write the four-thread version. Change &job[i] to &i and see the answers become wrong, then

put it back.

1. Write the unsafe counter and record the twenty-trial verdict.
2. Add the mutex and run it ten times. Confirm the exact answer every time.
3. Time both versions with time ./prog. The safe one is slower, and you should be able to say

why.

1. Write the thread pool. Run it five times and confirm the output does not change.
2. Move the fib_of call inside the mutex, run it again, and time it. Explain the difference.

Result

A Fibonacci sequence was generated by a thread and read by main with no mutex, the join being the only synchronisation needed. Four independent terms were computed by four threads writing into slots of their own. A shared counter updated by four threads without a mutex gave the right answer in 0 of 20 trials and lost up to three quarters of the updates; the same counter with a mutex gave the exact answer on all ten runs. A pool of three threads was given eight tasks, took them from a shared counter under a mutex, did the work outside the lock, and produced an identical result on every run, with main waiting on a condition variable.

Where marks are lost

• Saying threads make the Fibonacci sequence faster. Each term needs the one before it. What

threads can do is compute separate terms at once.

• Putting a mutex round the generator that does not need one, and not being able to say why

the join is enough.

• Using int for Fibonacci numbers. F(47) does not fit.
• Locking a mutex and returning without unlocking it. Every other thread then blocks for ever.
• Doing the work inside the critical section, which makes a thread pool slower than a loop.
• A busy-wait instead of a condition variable, or pthread_cond_wait inside an if instead

of a while.

• Reading a shared variable without the lock, even just to test it.
• Claiming a shared counter is safe because it printed the right answer once.
• Forgetting -pthread.

For the journal

Write the aim, MU's own wording, the single-thread generator and its output, and the four-thread version with its four answers. Then the unsafe counter with the twenty-trial verdict, and the safe one with its exact answer, side by side: that pair is the evidence for the thread-safety bullet and it is what an examiner reads. Then the thread pool, its output, and three sentences: one counter hands out the work under a mutex, the work itself is done outside the mutex, and main waits on a condition variable rather than spinning. The conclusion: threads are safe when they touch separate data, and need a mutex the moment they touch the same variable.

Quick revision

• F(0) is 0, F(1) is 1, F(n) is F(n-1) + F(n-2). Generating the sequence is sequential; computing

separate terms is parallel. Use unsigned long, which runs out at F(93).

• Code is thread safe if it stays correct with several threads in it at once. Local variables are

safe for free; globals, statics and anything behind a shared pointer are not.

• pthread_join is a synchronisation, and the cheapest one. Sharing needs no lock if the sharing

is not simultaneous.

• The best thread safety is to divide the data: one slot per thread, added up at the end. That is

called a reduction.

• A mutex is pthread_mutex_lock and pthread_mutex_unlock, with PTHREAD_MUTEX_INITIALIZER for

one that lives as long as the program.

• A mutex has an owner and only the locking thread may unlock it; a binary semaphore has no owner

and can be signalled by anybody.

• Rules: unlock on every path out, hold it briefly, use the same mutex for the same data, and take

several in the same order everywhere.

• A thread pool creates a fixed number of threads and feeds them tasks. The task counter is under

a mutex; the work is done outside it.

• A condition variable is how a thread waits for something to become true: always with a mutex,

always in a while loop, signalled with pthread_cond_signal or pthread_cond_broadcast.

• Workers for computing: as many as there are processors. Workers for waiting: many more.

Questions you should be able to answer

1. Why can eight threads not generate eight Fibonacci numbers at once? Because each term is the sum of the two before it, so the sequence has to be built in order. Separate terms computed from scratch are independent and can be done in parallel.

2. The generator program shares an array between a thread and main and has no mutex. Why is it correct? Because pthread_join guarantees the thread has finished before main reads the array, so the two never touch it at the same time. It is simultaneous access that needs protecting, not sharing.

3. Four threads add one to a shared counter two thousand times each. What is printed, and why? Some number between 2000 and 8000. Each increment is a read, an add and a write, and a thread switched out between the read and the write overwrites another thread's update. On the machine this page was checked on, twenty trials gave the right answer zero times and the worst was 2000.

4. What is a mutex, and how does it differ from a binary semaphore? A lock that one thread holds at a time. A mutex has an owner, so only the thread that locked it may unlock it; a binary semaphore has no owner and any thread may signal it.

5. Why is the mutex version of the counter slower than the broken one? Because every increment now happens one thread at a time. A counter every thread must update cannot be parallelised, only made correct. Giving each thread its own total and adding them up at the end avoids the lock entirely.

6. What is a thread pool, and why use one instead of a thread per task? A fixed set of threads that take tasks from a shared list. Creating a thread costs time, and far more threads than processors spend their time switching rather than working.

7. In the pool, why is fib_of called outside the mutex? Because everything inside a mutex happens one thread at a time. With the work inside, three workers would do one worker's throughput and the pool would be pointless.

8. What is a condition variable and what are the two rules for using one? A place a thread waits for something to become true. It is always used with a mutex, which it releases while waiting, and the wait is always inside a while loop testing the condition, because a thread can be woken while the condition is still false.

9. How many workers should a pool have? About as many as the machine has processors for work that computes, and many more than that for work that waits, because a waiting thread occupies no processor.

They need #include <semaphore.h> and no union semun, nothing survives the program, and there is nothing to clean up with ipcrm. The middle argument of sem_init is a flag: 0 for threads of one process, non-zero for a semaphore in shared memory that other processes can see.

The circular queue, which is how a bounded buffer is managed

MU's third bullet. A bounded buffer is an array of fixed size used as a queue, and the trick is how the two ends move.

An ordinary array queue takes items at the front and adds them at the back, and after a while both indices have walked off the end even though the array is nearly empty. A circular queue brings them back round with one operator:

in  = (in  + 1) % SIZE;      /* the producer's index */
out = (out + 1) % SIZE;      /* the consumer's index */

% SIZE is the whole idea. With SIZE of 4, in runs 0, 1, 2, 3, 0, 1, 2, 3 for ever, and the array is reused round and round with no copying and no wasted space.

Here is a buffer of four slots with two items in it, and the two indices in their places:

out points at the next item to be taken. in points at the next free slot to be filled. When in reaches 3 and the producer fills it, (3 + 1) % 4 is 0 and in is back at the beginning; by then slot 0 has long since been emptied.

The indices alone cannot tell you whether the buffer is full or empty. When in equals out, the buffer is either completely empty or completely full and the two cases look identical. There are three standard cures, and this chapter uses the first because MU asks for semaphores:

1. Let the semaphores count. empty and full know how many slots are which, so the indices

never have to be compared at all. This is the cleanest answer.

1. Keep a separate count of items. One more variable, incremented and decremented under the

mutex.

1. Leave one slot always empty, so full is (in + 1) % SIZE == out. This wastes one slot and

is what a queue with no semaphores does. It comes back in [Practical 16: Queues and Circular Queues], where it is the standard answer.

The program: two producers, three consumers, four slots

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

#define SIZE      4
#define PRODUCERS 2
#define CONSUMERS 3
#define PER       10                   /* items each producer makes */

static int  buffer[SIZE];
static int  in, out;                   /* the circular queue's two indices */
static long produced_total, consumed_total;

static sem_t empty, full;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void *producer(void *arg)
{
    long id = (long) arg;

    for (int i = 1; i <= PER; i++) {
        int item = (int) (id * 100 + i);      /* 101..110, then 201..210 */

        sem_wait(&empty);                     /* 1. wait for a free slot */
        pthread_mutex_lock(&lock);            /* 2. then take the lock */

        buffer[in] = item;
        in = (in + 1) % SIZE;
        produced_total = produced_total + item;

        pthread_mutex_unlock(&lock);          /* release in the opposite order */
        sem_post(&full);                      /* one more filled slot */
    }
    return NULL;
}

static void *consumer(void *arg)
{
    long want = (long) arg;                   /* how many this one must take */

    for (long i = 0; i < want; i++) {
        sem_wait(&full);                      /* 1. wait for a filled slot */
        pthread_mutex_lock(&lock);            /* 2. then take the lock */

        int item = buffer[out];
        out = (out + 1) % SIZE;
        consumed_total = consumed_total + item;

        pthread_mutex_unlock(&lock);
        sem_post(&empty);                     /* one more free slot */
    }
    return NULL;
}

int main(void)
{
    if (sem_init(&empty, 0, SIZE) == -1 || sem_init(&full, 0, 0) == -1) {
        perror("sem_init");
        return 1;
    }

    pthread_t p[PRODUCERS], c[CONSUMERS];
    long total = (long) PRODUCERS * PER;

    /* the work is shared out so that the consumers between them take
       exactly as many items as the producers make, and nobody is left
       waiting at the end for an item that will never come */
    long share = total / CONSUMERS;
    long extra = total % CONSUMERS;

    for (long i = 0; i < PRODUCERS; i++)
        if (pthread_create(&p[i], NULL, producer, (void *) (i + 1)) != 0)
            return 1;

    for (long i = 0; i < CONSUMERS; i++) {
        long want = share + (i < extra ? 1 : 0);
        if (pthread_create(&c[i], NULL, consumer, (void *) want) != 0)
            return 1;
    }

    for (int i = 0; i < PRODUCERS; i++)
        pthread_join(p[i], NULL);
    for (int i = 0; i < CONSUMERS; i++)
        pthread_join(c[i], NULL);

    printf("items produced by %d producers : %ld\n", PRODUCERS, total);
    printf("the sum of everything produced : %ld\n", produced_total);
    printf("the sum of everything consumed : %ld\n", consumed_total);
    printf("nothing lost, nothing doubled  : %s\n",
           produced_total == consumed_total ? "yes" : "NO");

    sem_destroy(&empty);
    sem_destroy(&full);
    return 0;
}

items produced by 2 producers : 20
the sum of everything produced : 3110
the sum of everything consumed : 3110
nothing lost, nothing doubled  : yes

Why the totals are the proof

Twenty items went through a buffer of four slots, driven by five threads, and the two sums are equal on every run.

The numbers are chosen so that the sum is worth checking by hand. Producer 1 makes 101 to 110, which adds up to 1055; producer 2 makes 201 to 210, which adds up to 2055; 1055 plus 2055 is 3110. Each item is distinct, so an item consumed twice or missed altogether would change the consumed total, and a wrong index would read a slot that had not been written and add the wrong number. The equality of the two sums is a much stronger check than printing the items, because the items come out in a different order every run and their sum does not.

That is the general lesson about testing concurrent programs: find a quantity that is invariant whatever the scheduling does, and check that.

The order of the two waits

Look at the producer again:

sem_wait(&empty);            /* first the resource  */
pthread_mutex_lock(&lock);   /* then the lock       */
   ...
pthread_mutex_unlock(&lock);
sem_post(&full);             /* release in the opposite order */

The resource first, the lock second, and release in the opposite order. That rule was stated at the end of Practical 1. The next section shows what breaking it costs, by running it.

The deadlock, run

The same program with the two waits swapped in both threads. Nothing else is different.

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

#define SIZE 2

static int  buffer[SIZE];
static int  in, out;
static sem_t empty, full;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void *producer(void *arg)
{
    (void) arg;
    for (int i = 1; i <= 10; i++) {
        pthread_mutex_lock(&lock);       /* THE WRONG WAY ROUND */
        sem_wait(&empty);
        buffer[in] = i;
        in = (in + 1) % SIZE;
        sem_post(&full);
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

static void *consumer(void *arg)
{
    (void) arg;
    for (int i = 1; i <= 10; i++) {
        pthread_mutex_lock(&lock);       /* THE WRONG WAY ROUND */
        sem_wait(&full);
        (void) buffer[out];
        out = (out + 1) % SIZE;
        sem_post(&empty);
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main(void)
{
    sem_init(&empty, 0, SIZE);
    sem_init(&full, 0, 0);

    pthread_t p, c;
    pthread_create(&p, NULL, producer, NULL);
    pthread_create(&c, NULL, consumer, NULL);
    pthread_join(p, NULL);
    pthread_join(c, NULL);

    printf("this line is never reached\n");
    return 0;
}

That program prints nothing and never ends. Run it with a stopwatch and it will still be there:

$ gcc -Wall -Wextra -pthread -o deadlock deadlock.c
$ timeout 3 ./deadlock
$ echo $?
124

timeout returns 124 when it has to kill the program, and that is what the checker for this book demanded: the listing is marked as a program that never finishes, and a version that finished would have been reported as a failure. The deadlock on this page is a measured fact, not a prediction.

Why it deadlocks

The buffer holds two slots, so after two items the empty semaphore is 0. Then:

Each holds what the other needs, and neither can move. That is a deadlock, and it is the exact picture of the four conditions Coffman set out, all of which must hold at once for one to be possible:

Break any one of the four and a deadlock is impossible. Putting sem_wait(&empty) before pthread_mutex_lock breaks hold and wait: the producer waits for the slot while holding nothing, so the consumer can always get the mutex and free a slot. That is why the rule is the rule.

This program has a second symptom, and it is worth noticing as well: it also holds the mutex while blocked, so the whole buffer is locked by a thread that is asleep. Even without the deadlock, never block while holding a lock is a rule in its own right.

Watching the buffer fill and empty

The last program prints the state after each operation, so the circular queue can be seen going round. One producer, one consumer, the consumer deliberately slower, and the buffer's occupancy read out of the semaphores.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>

#define SIZE  3
#define ITEMS 6

static int buffer[SIZE];
static int in, out;
static sem_t empty, full;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void nap(long millis)
{
    struct timespec t = { millis / 1000, (millis % 1000) * 1000000L };
    nanosleep(&t, NULL);
}

static void *producer(void *arg)
{
    (void) arg;
    for (int i = 1; i <= ITEMS; i++) {
        sem_wait(&empty);
        pthread_mutex_lock(&lock);
        buffer[in] = i * 11;
        printf("producer: put %2d at index %d\n", buffer[in], in);
        fflush(stdout);
        in = (in + 1) % SIZE;
        pthread_mutex_unlock(&lock);
        sem_post(&full);
        nap(20);
    }
    return NULL;
}

static void *consumer(void *arg)
{
    (void) arg;
    for (int i = 1; i <= ITEMS; i++) {
        sem_wait(&full);
        pthread_mutex_lock(&lock);
        printf("consumer: took %2d from index %d\n", buffer[out], out);
        fflush(stdout);
        out = (out + 1) % SIZE;
        pthread_mutex_unlock(&lock);
        sem_post(&empty);
        nap(60);                        /* three times slower than the producer */
    }
    return NULL;
}

int main(void)
{
    sem_init(&empty, 0, SIZE);
    sem_init(&full, 0, 0);

    pthread_t p, c;
    pthread_create(&p, NULL, producer, NULL);
    pthread_create(&c, NULL, consumer, NULL);
    pthread_join(p, NULL);
    pthread_join(c, NULL);

    printf("both finished, in is %d and out is %d\n", in, out);
    sem_destroy(&empty);
    sem_destroy(&full);
    return 0;
}

producer: put 11 at index 0
consumer: took 11 from index 0
producer: put 22 at index 1
producer: put 33 at index 2
producer: put 44 at index 0
consumer: took 22 from index 1
producer: put 55 at index 1
consumer: took 33 from index 2
producer: put 66 at index 2
consumer: took 44 from index 0
consumer: took 55 from index 1
consumer: took 66 from index 2
both finished, in is 0 and out is 0

Three things in that run, and all three are the point of the exercise.

The indices wrap. Index 0 is used twice, once for item 11 and again for item 44, because (2 + 1) % 3 is 0. The array of three slots carried six items.

The producer got ahead and then had to stop. It put 11, 22, 33 and 44 in before the consumer had taken much, and then it had to wait: with three slots and three items outstanding, empty was

1. That is buffer control working.

Both indices end at 0. Six items through a buffer of three slots means each index went round exactly twice, so both are back where they started. That is a small invariant worth checking in your own run: after N items through a buffer of size S, both indices are at N modulo S.

The interleaving of the lines is not the same on every run, so the checker compares them as a set; the line above is a real run. What is fixed, and what the program guarantees, is that each item is put exactly once and taken exactly once, and that no took line ever names a slot that has not been filled since it was last emptied.

Procedure

1. Write the first program. Compile with gcc -Wall -Wextra -pthread -o bb bb.c and run it five

times. Confirm the two sums are equal each time.

1. Comment out the pthread_mutex_lock and pthread_mutex_unlock lines and run it twenty times.

Note how often the two sums differ.

1. Put the mutex back. Change SIZE to 1 and confirm it still works but that the threads now

alternate strictly.

1. Write the deadlock version. Run it with timeout 3 ./deadlock; echo $? and record the 124.
2. Draw the four Coffman conditions against that program in your journal.
3. Write the watching program. Follow the indices round and check that both end at ITEMS modulo

SIZE.

1. Make the producer the slower of the two instead and run it again. The buffer now stays nearly

empty, and the consumer waits.

Result

A bounded buffer of four slots, managed as a circular queue with the modulo operator, was driven by two producer threads and three consumer threads using two counting semaphores and one mutex. Twenty distinct items were passed through it and the sum produced equalled the sum consumed on every run, which proves nothing was lost or duplicated. Swapping the semaphore wait with the mutex lock produced a deadlock, confirmed by the program being killed by a three-second timeout with status 124.

Where marks are lost

• Only two semaphores and no mutex. With more than one slot the two indices are a shared

variable and they race. The one-slot version in Practical 1 is the only case where two are enough.

• Taking the mutex before waiting on the semaphore. The deadlock above, and it is a guaranteed

loss of marks because the examiner's program hangs.

• Not releasing in the opposite order. Signal the semaphore after unlocking, not before.
• sem_init(&empty, 0, 0). The empty semaphore starts at SIZE, not at 0. This is the

commonest arithmetic mistake in the exercise and it makes the producer block immediately.

• Forgetting % SIZE. The index walks off the end of the array, which is a segmentation fault

or, worse, silent corruption.

• Comparing in with out to test for full or empty while also using semaphores. Pick one

mechanism; the semaphores already know.

• Consumers waiting for items that will never come. If the consumers between them expect more

items than the producers make, the extra consumers block for ever and the program never ends. The share-out in main is there for that reason.

• Doing input or output inside the critical section in a real program. It is done in the

watching program above only so that the reader can see the order, and it is noted as a deliberate exception.

For the journal

Write the aim, MU's own wording, the table of the three semaphores with their starting values, and the first program in full with its output. Write the two sums out and add the hand calculation that 1055 plus 2055 is 3110, because that is what shows you checked. Then the deadlock version, the timeout 3 command, the 124, and the four Coffman conditions written against it. The conclusion: a bounded buffer needs two counting semaphores for the slots and one mutex for the indices, the resource must be waited for before the lock is taken, and the circular queue is what lets a fixed array be reused for ever.

Quick revision

• A bounded buffer lets the producer run ahead of the consumer by up to SIZE items. One slot is

the special case where the two must alternate.

• Three mechanisms: empty starting at SIZE counts free slots, full starting at 0 counts filled

slots, and a mutex protects the two indices.

• The mutex is needed as soon as there is more than one slot, because two threads may then be

inside the buffer at once at different positions.

• POSIX semaphores for threads: sem_init, sem_wait, sem_post, sem_destroy, in

semaphore.h. No union semun, and nothing to remove with ipcrm.

• A circular queue is in = (in + 1) % SIZE. The indices alone cannot distinguish full from

empty; let the semaphores count, or keep a separate count, or leave one slot free.

• The order is: wait for the resource, then take the lock, then release the lock, then signal.
• Swap the first two and the program deadlocks: the producer holds the mutex while waiting for a

slot that only the consumer can free, and the consumer needs the mutex.

• Coffman's four conditions, all needed at once: mutual exclusion, hold and wait, no preemption,

circular wait. Waiting for the resource before the lock breaks hold and wait.

• Never block while holding a lock.
• Test a concurrent program by an invariant that the scheduling cannot change, such as the total

produced against the total consumed.

Questions you should be able to answer

1. Why does a bounded buffer need a mutex when the one-slot version did not? Because with several slots a producer and a consumer can legitimately be inside the buffer at the same time at different positions, and then the in and out indices are shared variables that race. With one slot the two semaphores already made simultaneous access impossible.

2. What does each of the three semaphores count, and what does each start at? empty counts free slots and starts at SIZE; full counts filled slots and starts at 0; the mutex grants the right to touch the indices and starts at 1.

3. What is the correct order of the two waits in the producer, and why? Wait on empty first, then take the mutex. A producer that holds the mutex while waiting for a slot prevents the consumer from freeing one, which is a deadlock.

4. State the four conditions for a deadlock and point to each of them in the broken program. Mutual exclusion, which is the mutex; hold and wait, which is the producer holding the mutex while waiting on empty; no preemption, since nothing can take the mutex away; and circular wait, since the producer waits for the consumer and the consumer for the producer.

5. How does the circular queue reuse the array, and what does the modulo do? in = (in + 1) % SIZE brings the index back to 0 after the last slot, so the array is used round and round with no copying. With SIZE of 3, the indices run 0, 1, 2, 0, 1, 2.

6. When in equals out, is the buffer full or empty? It cannot be told from the indices alone. The semaphores know, or a separate count of items can be kept, or one slot can be left permanently empty so that full is (in + 1) % SIZE == out.

7. How do you know that no item was lost or consumed twice? Because each item is a distinct number and the sum of what was produced equals the sum of what was consumed. The order changes on every run and the sum does not, which is what makes it a usable test.

8. Six items pass through a buffer of three slots. Where do the indices end up? Both at 0. Six modulo three is nought, so each index has gone round exactly twice.

writes made, 2 writers x 4 rounds : 8
the record is still consistent      : yes
readers that saw a half-written one : 0
more than one reader inside at once : yes

Four lines, and every one of them is a claim the program checked.

• 8 writes from two writers of four rounds each, so no write was lost: the two writers were

never inside together.

• The record is consistent at the end, and no reader ever saw a half-written one, so no

reader was ever inside while a writer was.

• Four readers were inside at once, which is the whole point. A plain mutex would have made

that number 1, and the program would have been correct and needlessly slow.

That last number is what tells you the solution is a readers-writers solution and not just a lock. It is worth printing in your own program for exactly that reason.

The three pieces of that solution

resource, a binary semaphore, is the right to touch the data. A writer takes it for itself. The readers take it collectively.

readers_inside, a counter, is how the readers know whether they are the first or the last. It is shared, so it needs its own lock.

count_lock, a mutex, guards that counter. Without it, two readers arriving together could both see readers_inside go from 0 to 1 and both call sem_wait(&resource), and the second one would block for ever on a semaphore the first one is holding.

Notice that sem_wait(&resource) is called while holding count_lock, which contradicts the rule from Practical 5 about not blocking while holding a lock. It is safe here, and knowing why is worth a mark: the only thread that can be holding resource is a writer, and a writer never asks for count_lock, so there is no cycle. The four Coffman conditions need a circular wait and there is none. That is the difference between a rule of thumb and a proof.

Writer starvation, run

The solution above has a defect, and it is not a bug: it does exactly what it was designed to do, and what it was designed to do is unfair.

resource is released only when the last reader leaves. If readers keep arriving, there is never a moment with no reader inside, so the writer waits for ever. That is starvation: not a deadlock, because everybody else is making progress, but one thread that never gets its turn.

Here is that made concrete. Two readers, staggered so that one is always inside, and a writer that asks once.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>

static int  readers_inside;
static long reads_done;
static sem_t resource;
static pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;

static void nap(long ms)
{
    struct timespec t = { ms / 1000, (ms % 1000) * 1000000L };
    nanosleep(&t, NULL);
}

static void *reader(void *arg)
{
    long stagger = (long) arg;
    nap(stagger);                        /* so the two readers overlap */

    for (;;) {
        pthread_mutex_lock(&count_lock);
        if (++readers_inside == 1)
            sem_wait(&resource);
        pthread_mutex_unlock(&count_lock);

        nap(40);                         /* a long read */

        pthread_mutex_lock(&count_lock);
        reads_done++;
        if (--readers_inside == 0)
            sem_post(&resource);
        pthread_mutex_unlock(&count_lock);
        /* and straight back round: no pause at all */
    }
    return NULL;
}

static void *writer(void *arg)
{
    (void) arg;
    sem_wait(&resource);                 /* the writer waits here for ever */
    printf("the writer got in after %ld reads\n", reads_done);
    sem_post(&resource);
    return NULL;
}

int main(void)
{
    sem_init(&resource, 0, 1);

    pthread_t r1, r2, w;
    pthread_create(&r1, NULL, reader, (void *) 0L);
    pthread_create(&r2, NULL, reader, (void *) 20L);
    nap(100);                            /* let the readers get going */
    pthread_create(&w, NULL, writer, NULL);

    pthread_join(w, NULL);
    printf("main: finished\n");
    return 0;
}

That program prints nothing at all, ever. The two readers overlap, readers_inside never reaches 0, resource is never released, and the writer sits in sem_wait until the machine is switched off:

$ gcc -Wall -Wextra -pthread -o starve starve.c
$ timeout 5 ./starve
$ echo $?
124

Three runs, three timeouts. The listing is marked in this book as a program that never finishes, so a version of it that did get the writer in would have been reported as a failure. The starvation is measured, not asserted.

Starvation is not deadlock, and an examiner will ask for the difference:

The second solution: writers preferred

The mirror image. A writer that is waiting stops new readers from going in, so the readers already inside finish and then the writer gets its turn.

It is built by counting the waiting writers as well, and giving them a semaphore of their own:

/* the writer's entry protocol */
lock(writer_count_lock);
if (++writers_waiting == 1) wait(readers_may_enter);   /* shut the door on readers */
unlock(writer_count_lock);
wait(resource);

Now the writers do not starve. The readers do: a steady stream of writers keeps readers_may_enter locked and no reader ever gets in. The problem has simply moved.

That is the honest position, and it is the answer to MU's bullet about prioritisation: neither priority is fair, and choosing one is choosing whose starvation you can live with.

The third solution: fair, with a turnstile

The fix is a single extra semaphore that everybody must pass through before joining the readers or the writers. A writer holds it while it waits, so readers arriving after the writer queue behind it; the readers already inside finish, the writer goes in, and then the queue moves again.

It is called a turnstile, and it is four lines of difference from the first program.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>

#define READERS 4
#define WRITERS 2
#define ROUNDS  4

struct record { int value; int doubled; };

static struct record shared = { 0, 0 };
static int readers_inside, max_readers, torn_reads;

static sem_t resource;                   /* one writer, or the readers as a group */
static sem_t turnstile;                  /* everybody queues here first */
static pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t tally = PTHREAD_MUTEX_INITIALIZER;

static void nap(long ms)
{
    struct timespec t = { ms / 1000, (ms % 1000) * 1000000L };
    nanosleep(&t, NULL);
}

static void *reader(void *arg)
{
    (void) arg;
    for (int r = 0; r < ROUNDS; r++) {
        sem_wait(&turnstile);            /* queue, so a waiting writer is not overtaken */
        sem_post(&turnstile);            /* and let the next one queue at once */

        pthread_mutex_lock(&count_lock);
        if (++readers_inside == 1)
            sem_wait(&resource);
        if (readers_inside > max_readers)
            max_readers = readers_inside;
        pthread_mutex_unlock(&count_lock);

        int v = shared.value;
        nap(5);
        int d = shared.doubled;
        if (d != 2 * v) {
            pthread_mutex_lock(&tally);
            torn_reads++;
            pthread_mutex_unlock(&tally);
        }

        pthread_mutex_lock(&count_lock);
        if (--readers_inside == 0)
            sem_post(&resource);
        pthread_mutex_unlock(&count_lock);

        nap(3);
    }
    return NULL;
}

static void *writer(void *arg)
{
    (void) arg;
    for (int r = 0; r < ROUNDS; r++) {
        sem_wait(&turnstile);            /* HOLD it: no new reader may join */
        sem_wait(&resource);             /* wait for the readers inside to leave */

        int n = shared.value + 1;
        shared.value = n;
        nap(5);
        shared.doubled = 2 * n;

        sem_post(&resource);
        sem_post(&turnstile);            /* let everybody through again */

        nap(3);
    }
    return NULL;
}

int main(void)
{
    sem_init(&resource, 0, 1);
    sem_init(&turnstile, 0, 1);

    pthread_t rd[READERS], wr[WRITERS];
    for (long i = 0; i < READERS; i++)
        if (pthread_create(&rd[i], NULL, reader, (void *) (i + 1)) != 0)
            return 1;
    for (long i = 0; i < WRITERS; i++)
        if (pthread_create(&wr[i], NULL, writer, (void *) (i + 1)) != 0)
            return 1;

    for (int i = 0; i < READERS; i++)
        pthread_join(rd[i], NULL);
    for (int i = 0; i < WRITERS; i++)
        pthread_join(wr[i], NULL);

    printf("writes made, %d writers x %d rounds : %d\n", WRITERS, ROUNDS, shared.value);
    printf("the record is still consistent      : %s\n",
           shared.doubled == 2 * shared.value ? "yes" : "NO");
    printf("readers that saw a half-written one : %d\n", torn_reads);
    printf("more than one reader inside at once : %s\n",
           max_readers > 1 ? "yes" : "NO");

    sem_destroy(&resource);
    sem_destroy(&turnstile);
    return 0;
}

writes made, 2 writers x 4 rounds : 8
the record is still consistent      : yes
readers that saw a half-written one : 0
more than one reader inside at once : yes

Exactly the same four answers, and readers still get in together, so nothing was given up to buy the fairness. The readers still share; they merely queue politely.

And the starvation is gone

The proof is the starving program from earlier with the turnstile added, under exactly the same load of readers that never stop.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>

static int  readers_inside;
static long reads_done;
static sem_t resource;
static sem_t turnstile;                  /* the only difference */
static pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;

static void nap(long ms)
{
    struct timespec t = { ms / 1000, (ms % 1000) * 1000000L };
    nanosleep(&t, NULL);
}

static void *reader(void *arg)
{
    long stagger = (long) arg;
    nap(stagger);

    for (;;) {
        sem_wait(&turnstile);
        sem_post(&turnstile);

        pthread_mutex_lock(&count_lock);
        if (++readers_inside == 1)
            sem_wait(&resource);
        pthread_mutex_unlock(&count_lock);

        nap(40);

        pthread_mutex_lock(&count_lock);
        reads_done++;
        if (--readers_inside == 0)
            sem_post(&resource);
        pthread_mutex_unlock(&count_lock);
    }
    return NULL;
}

static void *writer(void *arg)
{
    (void) arg;
    sem_wait(&turnstile);                /* holding this stops new readers */
    sem_wait(&resource);
    printf("the writer got in\n");
    sem_post(&resource);
    sem_post(&turnstile);
    return NULL;
}

int main(void)
{
    sem_init(&resource, 0, 1);
    sem_init(&turnstile, 0, 1);

    pthread_t r1, r2, w;
    pthread_create(&r1, NULL, reader, (void *) 0L);
    pthread_create(&r2, NULL, reader, (void *) 20L);
    nap(100);
    pthread_create(&w, NULL, writer, NULL);

    pthread_join(w, NULL);
    printf("main: finished\n");
    return 0;
}

the writer got in
main: finished

The writer gets in, on every run. The readers are still going round with no pause at all; the turnstile is what lets the writer put itself at the head of the queue.

Those two programs are the answer to MU's bullet about fairness. They differ by four lines: two in the reader and two in the writer. One never lets the writer in, and the other always does.

Deadlock prevention here

MU's third bullet ends with deadlock prevention, and in this exercise it comes down to one rule about the order the semaphores are taken.

The writer takes turnstile and then resource. Every thread that takes both takes them in that order. Reverse it in one place, and a writer holding resource while waiting for turnstile, and another holding turnstile while waiting for resource, are a circular wait.

The sem_wait(&resource) inside count_lock in every program on this page looks like a breach of the third rule, and it is safe for the reason given earlier: no writer ever asks for count_lock, so there is no cycle for the readers to complete. A rule of thumb is not a proof, and the proof is always "is there a cycle".

The three solutions, side by side

Procedure

1. Write the first program. Compile with gcc -Wall -Wextra -pthread -o rw1 rw1.c and run it five

times. Check all four printed lines each time.

1. Replace the whole reader protocol with a plain sem_wait(&resource) and sem_post(&resource),

so readers are exclusive too. Run it again: the answers are still right, and the most readers inside at once is now 1. That is a lock, not a readers-writers solution.

1. Remove count_lock from the reader's entry protocol and run it twenty times. Note what

happens, and why two readers arriving together can both try to take resource.

1. Write the starving program. Run it as timeout 5 ./starve; echo $? and record the 124.
2. Add the turnstile to it, four lines, and run it again. Record that the writer gets in.
3. Write the fair version of the full program and confirm the four answers are unchanged.
4. In your journal, write out the difference between deadlock and starvation in two sentences.

Result

Several readers were allowed into shared data at once while a writer had it exclusively, using one semaphore taken collectively by the readers and a counter under its own mutex. More than one reader was inside together on every run, no reader ever observed a half-written record, and no write was lost. Under a continuous load of readers the reader-preference solution starved the writer entirely, confirmed by the program being killed by a five-second timeout on every run. Adding a turnstile of one semaphore let the writer in on every run, with the four readers still sharing, which is fairness without loss.

Where marks are lost

• Using a plain mutex for the readers. It is correct and it is not the exercise. The number of

readers inside at once must be able to exceed one, and reporting that is how you show it.

• Printing the greatest number of readers inside as though it were fixed. It is not: it

depends on the scheduler, and this page saw both 4 and 3 with four readers.

• No mutex on readers_inside. Two readers arriving together can both believe they are the

first, and the second blocks for ever.

• The first reader locking and every reader unlocking, or the other way round. It is the

first in that locks and the last out that unlocks.

• Saying starvation is a deadlock. In a deadlock nothing progresses; under starvation

everybody else is working normally.

• Claiming a solution is fair because it worked once. Fairness shows up only under load, which

is why the starving program has readers that never pause.

• Forgetting that writers-preferred starves readers. Neither priority is fair; that is the

point of the third solution.

• Taking two semaphores in different orders in different threads, which is a circular wait.
• Not saying why sem_wait inside a mutex is safe here, when the examiner points at it.

For the journal

Write the aim, MU's own wording, and the table of who may be inside with whom. Then the first program in full with its four printed lines, and say what each line proves. Then the starving program, the timeout 5 command and the 124, and the turnstile version with its output, as a pair: those two are the evidence for the fairness bullet. Add the deadlock-against-starvation table. The conclusion: readers may share because reading changes nothing, a writer must be alone, the classical solution starves writers, and one extra semaphore that everybody queues at makes it fair without taking the sharing away.

Quick revision

• Many readers together, or one writer alone, and never both.
• Reader preference: the first reader in takes resource, the last reader out releases it, and

readers_inside is a shared counter needing its own mutex.

• Report whether more than one reader was ever inside at once. If it never was, you have written a

lock and not a readers-writers solution. Do not print the greatest number as a fact: it depends on the scheduler and changes between runs.

• Prove correctness with two fields that must agree, such as value and doubled. A reader that

sees them disagree has read a half-written record.

• Reader preference starves writers; writer preference starves readers. Neither is fair.
• Starvation is not deadlock: under starvation the rest of the system is working.
• A turnstile is one semaphore everybody passes through before entering. A writer holds it while

waiting, so readers arriving later queue behind it. Four lines, and the starvation is gone.

• Deadlock prevention here is one rule: every thread takes the semaphores in the same order, and

releases in the opposite order.

• Blocking while holding a lock is safe only when no cycle can form. The proof is always to look

for a cycle, not to recite the rule.

Questions you should be able to answer

1. State the readers-writers rule. Any number of readers may be inside together, or one writer alone. A writer may never be inside with a reader or with another writer.

2. Why may readers share when a mutex would not allow it? Because reading does not change the data, so two readers cannot interfere with each other. Only writing can leave the data in a state that another thread must not see.

3. In the reader-preference solution, which reader takes the semaphore and which releases it? The first reader to arrive takes it and the last to leave releases it. The readers in between do not touch it.

4. Why does readers_inside need a mutex of its own? Because it is shared. Without it two readers arriving together could both see the count go from 0 to 1 and both try to take resource, and the second would block for ever.

5. Why does the program report only that more than one reader was inside, and not how many? Because the greatest number depends on when the scheduler ran each thread and changes between runs: with four readers this page saw both 4 and 3. That more than one was inside together is a property of the program; the exact number is a coincidence of one run.

6. What is writer starvation, and how was it shown on this page? The writer never gets its turn because readers keep arriving and the count never reaches zero. It was shown by running the program under two readers that never pause: it printed nothing and was killed by a five-second timeout, three times out of three.

7. What is the difference between starvation and deadlock? In a deadlock every thread in the cycle is stuck and nothing at all progresses. Under starvation one thread never gets its turn while the rest of the system works normally.

8. What does a turnstile do, and what does it cost? It is one semaphore that every thread passes through before entering. A writer holds it while it waits, so readers that arrive later queue behind the writer. It costs two extra semaphore operations per reader and nothing in sharing: four readers still get in together.

9. What is the one rule that prevents deadlock in this exercise? Every thread takes the semaphores in the same order, turnstile before resource, and releases in the opposite order. That makes a circular wait impossible.

10. The reader calls sem_wait(&resource) while holding count_lock. Is that not blocking while holding a lock? It is, and it is safe here because the only thread that can hold resource is a writer, and a writer never asks for count_lock. No cycle can form, so no deadlock is possible.

The program

One program does all three algorithms, because MU's second bullet asks for the implementation to be extended rather than rewritten. The only thing that changes between them is which ready process is chosen next, so that choice is one if inside one loop and everything else is shared.

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

#define MAX 10

struct process {
    char name[6];
    int  arrival;
    int  burst;
    int  priority;
    int  start;
    int  finish;
};

/* the Gantt chart: one segment per slice of the processor */
struct slice { char name[6]; int from; int to; };
static struct slice chart[2 * MAX];
static int slices;

static void add_slice(const char *name, int from, int to)
{
    snprintf(chart[slices].name, sizeof chart[slices].name, "%s", name);
    chart[slices].from = from;
    chart[slices].to = to;
    slices++;
}

static void print_chart(void)
{
    printf("Gantt chart\n  ");
    for (int i = 0; i < slices; i++) printf("|%-4s", chart[i].name);
    printf("|\n  ");
    for (int i = 0; i < slices; i++) printf("%-5d", chart[i].from);
    printf("%d\n", chart[slices - 1].to);
}

static void report(struct process *p, int n, const char *title)
{
    printf("%s\n", title);
    print_chart();
    printf("  P   AT  BT  CT  TAT  WT\n");
    int total_tat = 0, total_wt = 0;
    for (int i = 0; i < n; i++) {
        int tat = p[i].finish - p[i].arrival;
        int wt  = tat - p[i].burst;
        total_tat += tat;
        total_wt  += wt;
        printf("  %-3s %2d  %2d  %2d  %3d  %2d\n",
               p[i].name, p[i].arrival, p[i].burst, p[i].finish, tat, wt);
    }
    printf("  average turnaround time = %d / %d = %.2f\n", total_tat, n, (double) total_tat / n);
    printf("  average waiting time    = %d / %d = %.2f\n", total_wt, n, (double) total_wt / n);
    printf("\n");
}

/* run the set under a rule: pick(available) returns the index to run next */
static void schedule(struct process *p, int n, int rule)
{
    int done[MAX] = { 0 };
    int now = 0, finished = 0;
    slices = 0;
    while (finished < n) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (done[i] || p[i].arrival > now) continue;
            if (best < 0) { best = i; continue; }
            if (rule == 0) {                                /* FCFS */
                if (p[i].arrival < p[best].arrival) best = i;
            } else if (rule == 1) {                         /* shortest job first */
                if (p[i].burst < p[best].burst
                    || (p[i].burst == p[best].burst && p[i].arrival < p[best].arrival))
                    best = i;
            } else {                                        /* priority, 1 is highest */
                if (p[i].priority < p[best].priority
                    || (p[i].priority == p[best].priority && p[i].arrival < p[best].arrival))
                    best = i;
            }
        }
        if (best < 0) {                 /* nobody has arrived: the processor is idle */
            int next = 1 << 30;
            for (int i = 0; i < n; i++)
                if (!done[i] && p[i].arrival < next) next = p[i].arrival;
            add_slice("idle", now, next);
            now = next;
            continue;
        }
        p[best].start = now;
        p[best].finish = now + p[best].burst;
        add_slice(p[best].name, p[best].start, p[best].finish);
        now = p[best].finish;
        done[best] = 1;
        finished++;
    }
}
int main(void)
{
    struct process set[4] = {
        { "P1", 0, 7, 2, 0, 0 },
        { "P2", 2, 4, 1, 0, 0 },
        { "P3", 4, 1, 3, 0, 0 },
        { "P4", 5, 4, 2, 0, 0 },
    };
    struct process work[4];

    memcpy(work, set, sizeof set);
    schedule(work, 4, 0);
    report(work, 4, "First come first serve");

    memcpy(work, set, sizeof set);
    schedule(work, 4, 1);
    report(work, 4, "Shortest job first, non-preemptive");

    memcpy(work, set, sizeof set);
    schedule(work, 4, 2);
    report(work, 4, "Priority, non-preemptive, 1 is the highest");
    return 0;
}

First come first serve
Gantt chart
  |P1  |P2  |P3  |P4  |
  0    7    11   12   16
  P   AT  BT  CT  TAT  WT
  P1   0   7   7    7   0
  P2   2   4  11    9   5
  P3   4   1  12    8   7
  P4   5   4  16   11   7
  average turnaround time = 35 / 4 = 8.75
  average waiting time    = 19 / 4 = 4.75

Shortest job first, non-preemptive
Gantt chart
  |P1  |P3  |P2  |P4  |
  0    7    8    12   16
  P   AT  BT  CT  TAT  WT
  P1   0   7   7    7   0
  P2   2   4  12   10   6
  P3   4   1   8    4   3
  P4   5   4  16   11   7
  average turnaround time = 32 / 4 = 8.00
  average waiting time    = 16 / 4 = 4.00

Priority, non-preemptive, 1 is the highest
Gantt chart
  |P1  |P2  |P4  |P3  |
  0    7    11   15   16
  P   AT  BT  CT  TAT  WT
  P1   0   7   7    7   0
  P2   2   4  11    9   5
  P3   4   1  16   12  11
  P4   5   4  15   10   6
  average turnaround time = 38 / 4 = 9.50
  average waiting time    = 22 / 4 = 5.50

Reading the program

schedule(work, n, rule) is the whole of it. At each step it looks at every process that has arrived and is not finished, picks one according to rule, and runs it to completion. Then it moves the clock to that process's finish time and picks again.

The three rules are three comparisons.

The tie-break is not decoration. In this job set P2 and P4 both have a burst of 4, and under shortest job first the program must choose one. Breaking the tie by arrival time makes the answer the same every run and the same as the examiner's model answer, which is usually worked in arrival order. A program that leaves the tie to the order of the array will sometimes disagree with the marking scheme.

memcpy(work, set, sizeof set) before each run puts the job set back as it was, because schedule writes each process's start and finish into it. Without it the second algorithm would be working on the first one's results.

The idle branch is the part most students leave out. If nothing has arrived yet, the processor is idle: the clock must jump forward to the next arrival, and the Gantt chart must show the gap. There is a program below that produces one.

Working the first table by hand

A student must be able to do this on paper, so here is the FCFS row by row.

The processes are taken in arrival order: P1, P2, P3, P4.

The averages are the sums over four:

• average turnaround time = (7 + 9 + 8 + 11) / 4 = 35 / 4 = 8.75
• average waiting time = (0 + 5 + 7 + 7) / 4 = 19 / 4 = 4.75

P1 waits nothing, because it arrived first and the processor was free. P3 waits 7 even though it needs the processor for only 1, because it arrived at 4 and P2 was in front of it. That disproportion is the whole criticism of FCFS.

And the shortest-job-first table, to see where it differs

At time 0 only P1 has arrived, so P1 runs whatever the rule is. At time 7 all three of the others are waiting, and now the rule matters: P3 needs 1, P2 needs 4, P4 needs 4. P3 goes first.

• average turnaround time = (7 + 10 + 4 + 11) / 4 = 32 / 4 = 8.00
• average waiting time = (0 + 6 + 3 + 7) / 4 = 16 / 4 = 4.00

Running the one-unit job first saved P3 four units of waiting and cost P2 one, so the average came down from 4.75 to 4.00.

The three algorithms compared on this job set

Shortest job first gives the lowest average waiting time, and that is not a coincidence. It is provably optimal among non-preemptive rules for a fixed set of jobs: moving a shorter job ahead of a longer one always reduces the total waiting. Priority did worst here because P3, the one-unit job, has the worst priority and was made to wait for everything.

The convoy effect

The strongest criticism of FCFS is worth a program of its own, because the numbers are dramatic. Three jobs, all ready at time 0, and the first one is long.

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

#define MAX 10

struct process {
    char name[6];
    int  arrival;
    int  burst;
    int  priority;
    int  start;
    int  finish;
};

/* the Gantt chart: one segment per slice of the processor */
struct slice { char name[6]; int from; int to; };
static struct slice chart[2 * MAX];
static int slices;

static void add_slice(const char *name, int from, int to)
{
    snprintf(chart[slices].name, sizeof chart[slices].name, "%s", name);
    chart[slices].from = from;
    chart[slices].to = to;
    slices++;
}

static void print_chart(void)
{
    printf("Gantt chart\n  ");
    for (int i = 0; i < slices; i++) printf("|%-4s", chart[i].name);
    printf("|\n  ");
    for (int i = 0; i < slices; i++) printf("%-5d", chart[i].from);
    printf("%d\n", chart[slices - 1].to);
}

static void report(struct process *p, int n, const char *title)
{
    printf("%s\n", title);
    print_chart();
    printf("  P   AT  BT  CT  TAT  WT\n");
    int total_tat = 0, total_wt = 0;
    for (int i = 0; i < n; i++) {
        int tat = p[i].finish - p[i].arrival;
        int wt  = tat - p[i].burst;
        total_tat += tat;
        total_wt  += wt;
        printf("  %-3s %2d  %2d  %2d  %3d  %2d\n",
               p[i].name, p[i].arrival, p[i].burst, p[i].finish, tat, wt);
    }
    printf("  average turnaround time = %d / %d = %.2f\n", total_tat, n, (double) total_tat / n);
    printf("  average waiting time    = %d / %d = %.2f\n", total_wt, n, (double) total_wt / n);
    printf("\n");
}

/* run the set under a rule: pick(available) returns the index to run next */
static void schedule(struct process *p, int n, int rule)
{
    int done[MAX] = { 0 };
    int now = 0, finished = 0;
    slices = 0;
    while (finished < n) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (done[i] || p[i].arrival > now) continue;
            if (best < 0) { best = i; continue; }
            if (rule == 0) {                                /* FCFS */
                if (p[i].arrival < p[best].arrival) best = i;
            } else if (rule == 1) {                         /* shortest job first */
                if (p[i].burst < p[best].burst
                    || (p[i].burst == p[best].burst && p[i].arrival < p[best].arrival))
                    best = i;
            } else {                                        /* priority, 1 is highest */
                if (p[i].priority < p[best].priority
                    || (p[i].priority == p[best].priority && p[i].arrival < p[best].arrival))
                    best = i;
            }
        }
        if (best < 0) {                 /* nobody has arrived: the processor is idle */
            int next = 1 << 30;
            for (int i = 0; i < n; i++)
                if (!done[i] && p[i].arrival < next) next = p[i].arrival;
            add_slice("idle", now, next);
            now = next;
            continue;
        }
        p[best].start = now;
        p[best].finish = now + p[best].burst;
        add_slice(p[best].name, p[best].start, p[best].finish);
        now = p[best].finish;
        done[best] = 1;
        finished++;
    }
}
int main(void)
{
    /* every job is ready at time 0, and one of them is very long */
    struct process set[3] = {
        { "P1", 0, 20, 1, 0, 0 },
        { "P2", 0,  2, 1, 0, 0 },
        { "P3", 0,  2, 1, 0, 0 },
    };
    struct process work[3];

    memcpy(work, set, sizeof set);
    schedule(work, 3, 0);
    report(work, 3, "First come first serve: the long job is first");

    memcpy(work, set, sizeof set);
    schedule(work, 3, 1);
    report(work, 3, "Shortest job first: the same three jobs");
    return 0;
}

First come first serve: the long job is first
Gantt chart
  |P1  |P2  |P3  |
  0    20   22   24
  P   AT  BT  CT  TAT  WT
  P1   0  20  20   20   0
  P2   0   2  22   22  20
  P3   0   2  24   24  22
  average turnaround time = 66 / 3 = 22.00
  average waiting time    = 42 / 3 = 14.00

Shortest job first: the same three jobs
Gantt chart
  |P2  |P3  |P1  |
  0    2    4    24
  P   AT  BT  CT  TAT  WT
  P1   0  20  24   24   4
  P2   0   2   2    2   0
  P3   0   2   4    4   2
  average turnaround time = 30 / 3 = 10.00
  average waiting time    = 6 / 3 = 2.00

Fourteen against two. The same three jobs, the same processor, the same total work of 24 units, and the average waiting time is seven times worse under first come first serve.

That is the convoy effect: one long process at the front holds up everything behind it, the way one slow lorry holds up a line of cars on a single-lane road. The two short jobs each wait twenty units to do two units of work.

• average waiting time under FCFS = (0 + 20 + 22) / 3 = 42 / 3 = 14.00
• average waiting time under SJF = (4 + 0 + 2) / 3 = 6 / 3 = 2.00

Notice what it cost: P1 now waits 4 where before it waited 0. Shortest job first improves the average by making the long job worse, and that is its own criticism:

Starvation and ageing are worth a sentence each, because both come up in the viva. A long job under SJF, or a low-priority job under priority scheduling, may be overtaken for ever if better candidates keep arriving. Ageing is the standard cure: improve a waiting process's priority a little for every unit of time it has waited, so that everything eventually reaches the front.

And the burst time is not actually known. No operating system is told in advance how long a process will use the processor, so real schedulers estimate it from how long the process used it last time, usually with an exponential average. That is why SJF is a benchmark to compare against rather than a scheduler anybody ships.

An idle processor, which most students forget

If nothing has arrived, the processor waits. The Gantt chart has to show it, and the clock has to jump.

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

#define MAX 10

struct process {
    char name[6];
    int  arrival;
    int  burst;
    int  priority;
    int  start;
    int  finish;
};

/* the Gantt chart: one segment per slice of the processor */
struct slice { char name[6]; int from; int to; };
static struct slice chart[2 * MAX];
static int slices;

static void add_slice(const char *name, int from, int to)
{
    snprintf(chart[slices].name, sizeof chart[slices].name, "%s", name);
    chart[slices].from = from;
    chart[slices].to = to;
    slices++;
}

static void print_chart(void)
{
    printf("Gantt chart\n  ");
    for (int i = 0; i < slices; i++) printf("|%-4s", chart[i].name);
    printf("|\n  ");
    for (int i = 0; i < slices; i++) printf("%-5d", chart[i].from);
    printf("%d\n", chart[slices - 1].to);
}

static void report(struct process *p, int n, const char *title)
{
    printf("%s\n", title);
    print_chart();
    printf("  P   AT  BT  CT  TAT  WT\n");
    int total_tat = 0, total_wt = 0;
    for (int i = 0; i < n; i++) {
        int tat = p[i].finish - p[i].arrival;
        int wt  = tat - p[i].burst;
        total_tat += tat;
        total_wt  += wt;
        printf("  %-3s %2d  %2d  %2d  %3d  %2d\n",
               p[i].name, p[i].arrival, p[i].burst, p[i].finish, tat, wt);
    }
    printf("  average turnaround time = %d / %d = %.2f\n", total_tat, n, (double) total_tat / n);
    printf("  average waiting time    = %d / %d = %.2f\n", total_wt, n, (double) total_wt / n);
    printf("\n");
}

/* run the set under a rule: pick(available) returns the index to run next */
static void schedule(struct process *p, int n, int rule)
{
    int done[MAX] = { 0 };
    int now = 0, finished = 0;
    slices = 0;
    while (finished < n) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (done[i] || p[i].arrival > now) continue;
            if (best < 0) { best = i; continue; }
            if (rule == 0) {                                /* FCFS */
                if (p[i].arrival < p[best].arrival) best = i;
            } else if (rule == 1) {                         /* shortest job first */
                if (p[i].burst < p[best].burst
                    || (p[i].burst == p[best].burst && p[i].arrival < p[best].arrival))
                    best = i;
            } else {                                        /* priority, 1 is highest */
                if (p[i].priority < p[best].priority
                    || (p[i].priority == p[best].priority && p[i].arrival < p[best].arrival))
                    best = i;
            }
        }
        if (best < 0) {                 /* nobody has arrived: the processor is idle */
            int next = 1 << 30;
            for (int i = 0; i < n; i++)
                if (!done[i] && p[i].arrival < next) next = p[i].arrival;
            add_slice("idle", now, next);
            now = next;
            continue;
        }
        p[best].start = now;
        p[best].finish = now + p[best].burst;
        add_slice(p[best].name, p[best].start, p[best].finish);
        now = p[best].finish;
        done[best] = 1;
        finished++;
    }
}
int main(void)
{
    /* nothing arrives between time 2 and time 5, so the processor is idle */
    struct process set[3] = {
        { "P1", 0, 2, 1, 0, 0 },
        { "P2", 5, 3, 1, 0, 0 },
        { "P3", 6, 2, 1, 0, 0 },
    };
    struct process work[3];

    memcpy(work, set, sizeof set);
    schedule(work, 3, 0);
    report(work, 3, "First come first serve with an idle processor");
    return 0;
}

First come first serve with an idle processor
Gantt chart
  |P1  |idle|P2  |P3  |
  0    2    5    8    10
  P   AT  BT  CT  TAT  WT
  P1   0   2   2    2   0
  P2   5   3   8    3   0
  P3   6   2  10    4   2
  average turnaround time = 9 / 3 = 3.00
  average waiting time    = 2 / 3 = 0.67

P1 finishes at 2 and P2 does not arrive until 5, so the processor is idle for three units. The chart names the gap idle, which is what an examiner looks for.

Two things follow that are easy to get wrong:

The idle time is not waiting time. No process was waiting, so nothing is added to anybody's waiting time. P2 arrives at 5, starts at 5 and waits 0.

Utilisation is now less than 100 per cent. The processor was busy for 7 of the 10 units, so utilisation is 7 / 10 = 0.70, which is 70 per cent. Every earlier job set in this chapter kept the processor busy from start to finish, so its utilisation was 100 per cent.

Drawing a Gantt chart by hand

The program prints one, and in the examination you draw it. The rules an examiner marks against:

1. One box per slice of the processor, in the order they ran, with the process name inside.
2. The times underneath, at the boundaries, starting at 0 and ending at the last completion.
3. Gaps shown, labelled idle, not closed up.
4. No gap where there is none. Boxes for consecutive processes share an edge.

For the first job set on this page:

 |  P1  |  P2  | P3 |  P4  |
 0      7      11   12     16

From that picture alone you can read off every completion time, and therefore every turnaround and waiting time, which is why it is worth drawing before filling in the table.

Procedure

1. Write the program. Compile with gcc -Wall -Wextra -o sched sched.c and run it.
2. Work the FCFS table out on paper first and check your answers against the program's.
3. Change rule to 1 and 2 in turn if your version takes it from the command line, or read the

three reports the program prints.

1. Change P3's burst time to 9 and predict what shortest job first will do before running it.
2. Write the convoy program and record both averages.
3. Write the idle-processor program and compute the utilisation by hand.
4. Add a process that arrives at 20, after everything else has finished, and check that the chart

shows a second idle gap.

Result

First come first serve, non-preemptive shortest job first and non-preemptive priority scheduling were simulated over one job set of four processes. The Gantt chart, completion time, turnaround time and waiting time were produced for each, and the averages were 4.75, 4.00 and 5.50 units of waiting respectively, so shortest job first gave the lowest average waiting time. The convoy effect was demonstrated on three jobs ready together, where first come first serve gave an average waiting time of 14.00 against 2.00 for shortest job first. An idle processor was shown in the Gantt chart and the utilisation computed as 70 per cent.

Where marks are lost

• Turnaround time computed as CT minus 0 instead of CT minus AT. It is only the same thing

when the process arrived at time 0.

• Waiting time computed from the start time when the process arrived later. WT is TAT minus

BT, which is safe in every case.

• Ignoring arrival times and scheduling everything as though it were ready at 0. Half the

marks in a scheduling question are in the arrival times.

• No idle gap in the chart when the processor had nothing to run.
• Adding the idle time to somebody's waiting time.
• Not breaking ties by arrival time, so the answer disagrees with the marking scheme.
• Forgetting to reset the job set between two algorithms in one program.
• Averaging over the wrong count, usually because an idle slice was counted as a process.
• Saying SJF is the best scheduler. It gives the lowest average waiting time and it needs the

burst time in advance, which nobody has.

For the journal

Write the aim, MU's own wording, the job set as a table, and then for each of the three algorithms the Gantt chart, the completion, turnaround and waiting times, and the two averages. Show one average as a full sum, so the working is visible. Then the convoy pair with both averages, and one sentence on what SJF cost P1 to gain it. The conclusion: a non-preemptive scheduler chooses once per process and the choice changes the average waiting time considerably; shortest job first is optimal for average waiting time and unimplementable as it stands, and first come first serve is implementable and suffers from the convoy effect.

Quick revision

• CT is read off the schedule. TAT = CT - AT. WT = TAT - BT. Response time is first start minus

AT, and equals WT for a non-preemptive scheduler.

• Non-preemptive: a process runs to completion once started. Preemptive: it can be interrupted.
• FCFS runs the earliest arrival. SJF runs the shortest burst. Priority runs the best priority,

with 1 usually the highest. All three break ties by arrival time.

• On the job set of this chapter the average waiting times are FCFS 4.75, SJF 4.00, priority 5.50.
• SJF gives the provably lowest average waiting time for a fixed set of jobs, and needs a burst

time nobody knows in advance. Real systems estimate it from the last one.

• The convoy effect: one long job at the front of an FCFS queue makes every short job behind it

wait. Fourteen against two on the three jobs in this chapter.

• Starvation under SJF or priority is cured by ageing: raise a waiting process's priority as it

waits.

• An idle processor is a labelled gap in the Gantt chart, adds to nobody's waiting time, and

brings utilisation below 100 per cent.

• The five criteria: utilisation, throughput, turnaround time, waiting time, response time. They

conflict.

Questions you should be able to answer

1. Define turnaround time and waiting time. Turnaround time is completion time minus arrival time, the whole time the process was in the system. Waiting time is turnaround time minus burst time, the part of it the process spent ready but not running.

2. Why is waiting time the figure a scheduler is judged on? Because the burst time belongs to the process and no scheduling rule can change it. The waiting is the only part the scheduler decides.

3. What is the convoy effect? Under first come first serve, one long process at the head of the queue makes every short process behind it wait for the whole of it. On the three jobs on this page it made the average waiting time 14.00 instead of 2.00.

4. Which non-preemptive algorithm gives the lowest average waiting time, and what is wrong with it? Shortest job first, provably. It needs the burst time in advance, which no operating system has, and a long job may starve if short ones keep arriving.

5. What is ageing, and what problem does it solve? Raising the priority of a process a little for every unit of time it has waited. It solves starvation under priority scheduling and under shortest job first.

6. A process arrives at 5, starts at 5 and runs for 3. What are its turnaround and waiting times? Completion 8, turnaround 8 - 5 = 3, waiting 3 - 3 = 0.

7. The processor is idle from 2 to 5. Whose waiting time does that add to? Nobody's. No process was ready during that time. It reduces utilisation, which here was 7 of 10 units, or 70 per cent.

8. Two processes have the same burst time under shortest job first. Which goes first, and why does it matter? The one that arrived earlier. It matters because a program that leaves the choice to the order of the array will sometimes give a different answer from the marking scheme.

9. For a non-preemptive scheduler, how does response time differ from waiting time? It does not: a process starts once and runs to the end, so the time until it first runs is the whole of its waiting. They differ under a preemptive scheduler such as round robin.

Reading the program

The ready queue is a circular queue, which is MU's own phrase in Practical 5 and is the right structure here for the same reason: items join at one end and leave at the other, and the array is reused round and round.

static void enqueue(int i)
{ queue[tail] = i; tail = (tail + 1) % SLOTS; count++; }

static int dequeue(void)
{ int i = queue[head]; head = (head + 1) % SLOTS; count--; return i; }

That is the whole of MU's "improve queue management" bullet. A first attempt at this program usually searches the array for the next process to run, which is a loop over every process at every step; a circular queue makes taking the next one a single operation whatever the number of processes.

p[i].left is the burst time still to do. A process is put back on the queue while left is greater than 0 and finishes when it reaches 0. This is the one field a non-preemptive simulation does not need.

The order of two lines decides the answer, and getting it wrong is the classic bug. A process that arrives while the current one is running joins the queue before the process that has just been preempted. That is the convention every textbook and every marking scheme uses, and it changes the Gantt chart: in the run above, P3 arrives at 4 while P2 is running its slice from 3 to 6, so at time 6 the queue holds P1, P3, P4 and not P1, P4, P3.

The idle branch is here too, for the same reason as in Practical 7: if the queue is empty and nothing has arrived, the clock jumps to the next arrival.

Following the run by hand

This is the part to be able to do on paper, so here is the quantum of 3, step by step.

From the completion times the rest follows. P1 finishes at 15, arrived at 0, so its turnaround is 15 and its waiting is 15 - 7 = 8. It first ran at 0, so its response time is 0. P3 finishes at 10, arrived at 4, turnaround 6, waiting 6 - 1 = 5, and it first ran at 9, so its response time is 9 - 4 = 5.

• average turnaround time = (15 + 12 + 6 + 11) / 4 = 44 / 4 = 11.00
• average waiting time = (8 + 8 + 5 + 7) / 4 = 28 / 4 = 7.00
• average response time = (0 + 1 + 5 + 5) / 4 = 11 / 4 = 2.75

What the context switch count counts

A context switch is the operating system saving one process's registers and loading another's. It is pure overhead: no user work happens during it.

The program counts one switch every time the processor changes hands, which is once for every slice except the last:

There were eight slices in that Gantt chart and seven changes of hand between them, which is the figure to expect: the number of slices minus one.

Comparing the quanta, which is the experiment

MU's second and third bullets. The same four jobs, run at nine different quanta, in one program. It is the program above with a different main, and the whole of it is printed so that it can be typed in and compiled on its own.

the same four jobs at nine different quanta
  quantum    avg TAT     avg WT     avg RT  switches
        1       9.50       5.50       0.75        15
        2       9.00       5.00       1.50         8
        3      11.00       7.00       2.75         7
        4       8.50       4.50       3.25         4
        5       9.50       5.50       3.25         4
        6      10.25       6.25       4.00         4
        7       8.75       4.75       4.75         3
        8       8.75       4.75       4.75         3
       16       8.75       4.75       4.75         3

That table is the whole chapter, and it says four things.

1. The response time falls as the quantum falls, smoothly

Read the fourth column from the bottom up: 4.75, 4.75, 4.75, 4.00, 3.25, 3.25, 2.75, 1.50, 0.75. It never goes the wrong way. A smaller quantum means every process gets its first turn sooner, and that is what round robin is for.

At a quantum of 1 the average response time is 0.75 units for jobs whose bursts are up to 7. That is the behaviour that makes a machine feel quick.

2. The context switches rise as the quantum falls, steeply

The last column, again from the bottom: 3, 3, 3, 4, 4, 4, 7, 8, 15. Going from a quantum of 8 to a quantum of 1 buys 4 units of response time and costs five times as many context switches.

That is the trade-off, and it is the answer to how the quantum should be chosen:

The quantum must be large compared with the cost of a context switch, and small compared with

the time a process typically wants the processor for.

Real numbers: a context switch costs a few microseconds, and Linux's default time slice is a few milliseconds, so the overhead is well under one per cent. A quantum of one microsecond would spend most of the machine switching.

3. Once the quantum reaches the longest burst, round robin IS first come first serve

Look at the last three rows: quantum 7, 8 and 16 give identical figures, and those figures, average turnaround 8.75 and average waiting 4.75, are exactly the first come first serve numbers from [Practical 7: CPU Scheduling, FCFS and Non-preemptive Scheduling]. The Gantt chart is the same too: P1 from 0 to 7, P2 to 11, P3 to 12, P4 to 16.

The longest burst in this job set is 7. With a quantum of 7 or more no process is ever preempted, so nothing ever goes back on the queue, so the queue is served in arrival order and never reordered. Round robin with a very large quantum degenerates into first come first serve, and this is the measured proof of a sentence every textbook states.

4. The waiting time is NOT a smooth function of the quantum

This is the result worth reporting honestly, because it contradicts the impression a student takes from most descriptions of the algorithm.

Read the third column downwards: 5.50, 5.00, 7.00, 4.50, 5.50, 6.25, 4.75, 4.75, 4.75.

It goes down, then sharply up at a quantum of 3, then down, then up twice, then settles. A quantum of 3 is the worst of the nine on this job set, and worse than the quantum of 1 that causes five times as many context switches.

The reason is arithmetic rather than principle. Whether round robin is kind to a particular process depends on whether the quantum divides its burst time neatly and on where the other processes' slices happen to fall. With a quantum of 4, P2's burst of 4 fits in exactly one slice and P2 is never preempted at all; with a quantum of 3 it takes two slices, so P2 must go round the queue again and wait behind everybody. The set here has bursts of 7, 4, 1 and 4, and 4 divides two of them.

Three conclusions follow, and they are the honest ones:

• The quantum is chosen for response time and overhead, not for waiting time. Waiting time is

what shortest job first optimises, and round robin does not try to.

• A single job set cannot tell you the best quantum. This one prefers 4; another will prefer

something else. What is general is the response time falling and the switches rising.

• A measurement that surprises you is worth printing. The table above was run before this

section was written, and the section was written to explain it.

Round robin against first come first serve

MU's second bullet names three things to compare, and the table above answers all three.

Round robin is worse on every total and better on the one thing a user notices. Turnaround up by a quarter, waiting up by nearly a half, response time down by two units, and more than twice the switches.

That is the correct summary of the two algorithms and it is what an examiner is looking for. Round robin is not an improvement on first come first serve in any arithmetic sense; it is a different objective. A batch system that runs payroll overnight wants first come first serve or shortest job first. A machine with people sitting at it wants round robin.

The two senses of fairness

Both algorithms are called fair and they mean different things by it.

• First come first serve is fair in order: a process that arrives first is served first, and

nobody ever overtakes anybody. Its unfairness is in the waiting, where a short job behind a long one waits enormously.

• Round robin is fair in share: every process gets the same size of slice, and none waits more

than one round for its next turn. Its unfairness is that a short job is interrupted just as often as a long one, so short jobs finish later than they need to.

Neither is fair in the sense of shortest job first, which is optimal for the average and openly unfair to long jobs.

Procedure

1. Write the program. Compile with gcc -Wall -Wextra -o rr rr.c.
2. Run it as ./rr 3 and check the Gantt chart against the step table above.
3. Run it at quanta 1, 2, 4, 5, 7, 8 and 16 and write every average down.
4. Confirm that at a quantum of 7 or more the answer is identical to your first come first serve

answer from Practical 7, including the Gantt chart.

1. Move the enqueueing of newly arrived processes to after the preempted process goes back on

the queue. Run at quantum 3 again and note that the chart changes.

1. Write the comparison program and reproduce the table of nine quanta.
2. Add a fifth process arriving at 30 and confirm the chart shows an idle gap.

Result

Round robin was implemented with the quantum as a command line argument and a circular queue as the ready queue. At a quantum of 3 the four processes gave an average turnaround time of 11.00, an average waiting time of 7.00, an average response time of 2.75 and 7 context switches, against 8.75, 4.75, 4.75 and 3 for first come first serve on the same job set. Over nine quanta the average response time fell monotonically as the quantum fell, from 4.75 to 0.75, while the context switches rose from 3 to 15. At a quantum of 7, equal to the longest burst, round robin produced exactly the first come first serve schedule. The average waiting time was found not to be monotonic in the quantum, being worst at a quantum of 3.

Where marks are lost

• Putting the preempted process back on the queue before the processes that arrived during its slice.

The convention is the other way round, and the Gantt chart is then wrong.

• Not tracking the remaining burst time, so a process runs its whole burst and the program is

really first come first serve.

• Computing the response time as the waiting time. Under round robin they differ, and that is

the point of the algorithm.

• Searching the array for the next process instead of keeping a queue. It gives the same

answer and misses MU's bullet about queue management.

• Not counting the context switches, or counting one per process instead of one per slice.
• Saying round robin has a better turnaround time than first come first serve. It is worse,

measurably.

• Saying a smaller quantum is always better. It improves the response time and costs switches,

and on this job set it does not even improve the waiting time reliably.

• Forgetting the idle case.

For the journal

Write the aim, MU's own wording, the job set, and the quantum 3 run in full: the Gantt chart, the table with the response time column, the three averages and the switch count. Add the step table showing the queue at each instant, because that is what an examiner asks you to produce. Then the nine-quantum table, and three sentences: the response time falls as the quantum falls, the switches rise, and at a quantum equal to the longest burst round robin becomes first come first serve. The conclusion: round robin trades turnaround time for response time and cannot starve anybody.

Quick revision

• Round robin gives each process at most one quantum, then moves it to the back of the queue. It

is first come first serve with a clock.

• The ready queue is a circular queue: advance the tail modulo the array size to join, the head to

leave.

• A process that arrives during a slice joins the queue before the process that has just been

preempted.

• Response time is until the first run; waiting time is the total time ready and not running. They

are equal only for a non-preemptive scheduler.

• No process waits longer than (n - 1) times q for its next turn, so round robin cannot starve

anybody.

• A smaller quantum: better response time, more context switches. The quantum should be large

against the cost of a switch and small against a typical burst.

• At a quantum greater than or equal to the longest burst, round robin is exactly first come first

serve. Proved here at quanta 7, 8 and 16, all giving 8.75 and 4.75.

• On the job set of this chapter: first come first serve gives turnaround 8.75, waiting 4.75,

response 4.75 and 3 switches; round robin at quantum 3 gives 11.00, 7.00, 2.75 and 7.

• The average waiting time is not monotonic in the quantum. It was worst at 3 of the nine quanta

tried, because whether the quantum divides a burst neatly matters more than its size.

• First come first serve is fair in order, round robin is fair in share, and neither is optimal

for the average.

Questions you should be able to answer

1. What is the time quantum, and what happens when it runs out? The fixed slice of processor time each process gets. When it runs out, a process that has not finished is preempted and put at the back of the ready queue, and the next process runs.

2. Why can round robin not starve a process? Because the queue is served in order and every process gets at most one quantum. With n processes and a quantum of q, nobody waits longer than (n

• 1) times q for its next turn.

3. How do response time and waiting time differ under round robin? Response time is the time from arrival until the process first runs, once. Waiting time is the total of all the periods it spent ready and not running, which under round robin is several periods.

4. What happens to the schedule as the quantum becomes very large? No process is ever preempted, so round robin becomes first come first serve. On this job set, quanta of 7, 8 and 16 all gave the first come first serve schedule and its averages exactly.

5. What happens as the quantum becomes very small? The response time improves and the number of context switches rises, here from 3 switches at a quantum of 8 to 15 at a quantum of 1. With a quantum near the cost of a switch, most of the machine's time is spent switching.

6. Compare round robin with first come first serve on this job set. Round robin at quantum 3 is worse on turnaround, 11.00 against 8.75, and worse on waiting, 7.00 against 4.75, and better on response, 2.75 against 4.75, at the cost of 7 context switches against 3.

7. A process arrives while another is using its slice. Where does it go in the queue? Before the process that is about to be preempted. That is the standard convention and it changes the Gantt chart.

8. Is a smaller quantum always better for the average waiting time? No. On the job set here the averages went 5.50, 5.00, 7.00, 4.50 for quanta 1, 2, 3 and 4: a quantum of 3 was the worst of the nine tried. Whether the quantum divides a process's burst neatly matters more than how large it is.

9. What does a context switch cost, and how does the program count them? It is the saving of one process's state and the loading of another's, and no user work happens during it. The program counts one every time the processor changes hands, which is the number of slices in the Gantt chart minus one.

The three algorithms

Optimal cannot be implemented, because it needs to know the future. It is in the program and in this chapter for one reason: it is the standard against which the other two are measured. A student who says "optimal is the best algorithm, so we should use it" has missed the point of it.

The program

One program, three algorithms, because the difference between them is entirely in the choice of victim.

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

#define MAXF 8
#define MAXR 40

/* FIFO, LRU and optimal all fit one shape: choose a frame to evict. */
enum policy { FIFO, LRU, OPTIMAL };

static const char *name_of(enum policy p)
{
    return p == FIFO ? "FIFO" : p == LRU ? "LRU" : "optimal";
}

static int run(const int *ref, int n, int frames, enum policy how, int show)
{
    int page[MAXF];               /* what is in each frame, -1 for empty   */
    int stamp[MAXF];              /* FIFO: when it came in. LRU: last used */
    int faults = 0;

    for (int f = 0; f < frames; f++) {
        page[f] = -1;
        stamp[f] = 0;
    }

    if (show) {
        printf("  %s with %d frames\n", name_of(how), frames);
        printf("  ref ");
        for (int f = 0; f < frames; f++) printf(" f%d", f);
        printf("  hit/miss\n");
    }

    for (int i = 0; i < n; i++) {
        int want = ref[i];
        int found = -1;

        for (int f = 0; f < frames; f++)
            if (page[f] == want) { found = f; break; }

        if (found >= 0) {
            if (how == LRU) stamp[found] = i;      /* used again, so it is fresh */
        } else {
            faults++;
            int victim = 0;
            int empty = -1;
            for (int f = 0; f < frames; f++)
                if (page[f] == -1) { empty = f; break; }

            if (empty >= 0) {
                victim = empty;
            } else if (how == OPTIMAL) {
                /* evict the page whose next use is furthest away */
                int best = -1;
                for (int f = 0; f < frames; f++) {
                    int next = n + 1;
                    for (int k = i + 1; k < n; k++)
                        if (ref[k] == page[f]) { next = k; break; }
                    if (next > best) { best = next; victim = f; }
                }
            } else {
                /* FIFO: the oldest arrival. LRU: the least recently used.
                   Both are the smallest stamp; only WHEN the stamp is set
                   differs, and that is the whole difference between them. */
                int oldest = stamp[0];
                victim = 0;
                for (int f = 1; f < frames; f++)
                    if (stamp[f] < oldest) { oldest = stamp[f]; victim = f; }
            }
            page[victim] = want;
            stamp[victim] = i;
        }

        if (show) {
            printf("  %3d ", want);
            for (int f = 0; f < frames; f++) {
                if (page[f] == -1) printf("  -");
                else printf(" %2d", page[f]);
            }
            printf("  %s\n", found >= 0 ? "hit" : "MISS");
        }
    }
    return faults;
}

static void summary(const int *ref, int n, int frames, enum policy how)
{
    int faults = run(ref, n, frames, how, 0);
    int hits = n - faults;
    printf("  %-7s %2d frames: %2d faults, %2d hits, hit ratio %d / %d = %.2f\n",
           name_of(how), frames, faults, hits, hits, n, (double) hits / n);
}

int main(void)
{
    /* the reference string every textbook uses for this exercise */
    int ref[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };
    int n = (int) (sizeof ref / sizeof *ref);

    printf("the reference string, %d references:\n ", n);
    for (int i = 0; i < n; i++) printf(" %d", ref[i]);
    printf("\n\n");

    run(ref, n, 3, FIFO, 1);
    printf("\n");
    run(ref, n, 3, LRU, 1);
    printf("\n");

    printf("the same string at several frame counts\n");
    for (int f = 1; f <= 5; f++) {
        summary(ref, n, f, FIFO);
        summary(ref, n, f, LRU);
        summary(ref, n, f, OPTIMAL);
        printf("\n");
    }
    return 0;
}

FIFO and LRU differ by one line

This is the neatest thing in the program and worth pointing out, because it is what makes the two algorithms comparable.

Both keep a stamp for each frame and both evict the frame with the smallest stamp. The only difference is when the stamp is written:

In the program that is the single line if (how == LRU) stamp[found] = i; inside the hit branch. Take it out and LRU becomes FIFO. That one line is what an examiner asks about, because it is the whole difference between an algorithm that ignores how a program behaves and one that pays attention to it.

Following the difference in the tables

Look at the two tables at the sixth reference, page 3, when the frames hold 2, 0, 1.

• FIFO asks which came in first. The order of arrival was 7, then 0, then 1, and 7 has already

been replaced by 2, so the oldest survivor is 0. It evicts 0. Two references later it needs 0 again, and faults.

• LRU asks which was used least recently. Page 0 was used at reference 5, one step ago; page 1

has not been touched since reference 3; page 2 came in at reference 4. So LRU evicts 1, keeps 0, and gets a hit on the next reference.

That single decision is why LRU ends with 12 faults and FIFO with 15.

The hit ratio, worked

The definitions, over 20 references with three frames:

• FIFO: 15 faults and 5 hits, so the hit ratio = 5 / 20 = 0.25 and the miss ratio = 15 / 20 = 0.75
• LRU: 12 faults and 8 hits, so the hit ratio = 8 / 20 = 0.40 and the miss ratio = 12 / 20 = 0.60
• optimal: 9 faults and 11 hits, so the hit ratio = 11 / 20 = 0.55

The two ratios add to 1, always, because every reference is either a hit or a fault. An examiner who asks for the miss ratio is asking for one minus the hit ratio.

The first references are always faults, because the frames start empty. With f frames and a string touching at least f distinct pages, the first f faults are unavoidable and are called cold start or compulsory misses. Nine of LRU's twelve faults here are genuine replacement decisions; three are cold start. That is worth saying in a journal, because it means a short reference string flatters no algorithm.

More frames, and what they buy

MU's third bullet asks for frames and memory constraints to be varied, and the table at the bottom of the output is that experiment. Reading the faults column:

Four things in that table are worth stating, and three of them surprise people.

With one frame every reference is a fault. Twenty out of twenty, for all three algorithms. There is only one frame, so there is no choice to make and no algorithm can help. It is the floor of the experiment and a useful check that the program is right.

More frames means fewer faults, usually. From 1 to 5 frames, LRU goes 20, 17, 12, 8, 7. That is the behaviour a student expects and the reason buying memory speeds a machine up.

FIFO with two frames beats LRU with two frames: 15 faults against 17. LRU is a better algorithm in general and it is not better on every string at every frame count. A single measurement never settles which algorithm is better, and this row is the proof.

Optimal is a floor nothing reaches. At three frames it needs 9 where LRU needs 12 and FIFO 15. At four and five frames LRU has caught up with it exactly, which says something about this string rather than about LRU: with enough frames, the good algorithms converge.

Belady's anomaly

The third surprise deserves a program of its own. It is the one result in this topic that most students do not believe until they have run it.

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

#define MAXF 8
#define MAXR 40

/* FIFO, LRU and optimal all fit one shape: choose a frame to evict. */
enum policy { FIFO, LRU, OPTIMAL };

static const char *name_of(enum policy p)
{
    return p == FIFO ? "FIFO" : p == LRU ? "LRU" : "optimal";
}

static int run(const int *ref, int n, int frames, enum policy how, int show)
{
    int page[MAXF];               /* what is in each frame, -1 for empty   */
    int stamp[MAXF];              /* FIFO: when it came in. LRU: last used */
    int faults = 0;

    for (int f = 0; f < frames; f++) {
        page[f] = -1;
        stamp[f] = 0;
    }

    if (show) {
        printf("  %s with %d frames\n", name_of(how), frames);
        printf("  ref ");
        for (int f = 0; f < frames; f++) printf(" f%d", f);
        printf("  hit/miss\n");
    }

    for (int i = 0; i < n; i++) {
        int want = ref[i];
        int found = -1;

        for (int f = 0; f < frames; f++)
            if (page[f] == want) { found = f; break; }

        if (found >= 0) {
            if (how == LRU) stamp[found] = i;      /* used again, so it is fresh */
        } else {
            faults++;
            int victim = 0;
            int empty = -1;
            for (int f = 0; f < frames; f++)
                if (page[f] == -1) { empty = f; break; }

            if (empty >= 0) {
                victim = empty;
            } else if (how == OPTIMAL) {
                /* evict the page whose next use is furthest away */
                int best = -1;
                for (int f = 0; f < frames; f++) {
                    int next = n + 1;
                    for (int k = i + 1; k < n; k++)
                        if (ref[k] == page[f]) { next = k; break; }
                    if (next > best) { best = next; victim = f; }
                }
            } else {
                /* FIFO: the oldest arrival. LRU: the least recently used.
                   Both are the smallest stamp; only WHEN the stamp is set
                   differs, and that is the whole difference between them. */
                int oldest = stamp[0];
                victim = 0;
                for (int f = 1; f < frames; f++)
                    if (stamp[f] < oldest) { oldest = stamp[f]; victim = f; }
            }
            page[victim] = want;
            stamp[victim] = i;
        }

        if (show) {
            printf("  %3d ", want);
            for (int f = 0; f < frames; f++) {
                if (page[f] == -1) printf("  -");
                else printf(" %2d", page[f]);
            }
            printf("  %s\n", found >= 0 ? "hit" : "MISS");
        }
    }
    return faults;
}

static void summary(const int *ref, int n, int frames, enum policy how)
{
    int faults = run(ref, n, frames, how, 0);
    int hits = n - faults;
    printf("  %-7s %2d frames: %2d faults, %2d hits, hit ratio %d / %d = %.2f\n",
           name_of(how), frames, faults, hits, hits, n, (double) hits / n);
}

int main(void)
{
    /* the string Belady used: FIFO gets WORSE when a frame is added */
    int ref[] = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
    int n = (int) (sizeof ref / sizeof *ref);

    printf("the reference string, %d references:\n ", n);
    for (int i = 0; i < n; i++) printf(" %d", ref[i]);
    printf("\n\n");

    for (int f = 3; f <= 4; f++) {
        summary(ref, n, f, FIFO);
        summary(ref, n, f, LRU);
        summary(ref, n, f, OPTIMAL);
        printf("\n");
    }
    return 0;
}

the reference string, 12 references:
  1 2 3 4 1 2 5 1 2 3 4 5

  FIFO     3 frames:  9 faults,  3 hits, hit ratio 3 / 12 = 0.25
  LRU      3 frames: 10 faults,  2 hits, hit ratio 2 / 12 = 0.17
  optimal  3 frames:  7 faults,  5 hits, hit ratio 5 / 12 = 0.42

  FIFO     4 frames: 10 faults,  2 hits, hit ratio 2 / 12 = 0.17
  LRU      4 frames:  8 faults,  4 hits, hit ratio 4 / 12 = 0.33
  optimal  4 frames:  6 faults,  6 hits, hit ratio 6 / 12 = 0.50

FIFO with three frames has 9 faults. FIFO with four frames has 10. More memory, more page faults, on the same program with the same references.

That is Belady's anomaly, named after the researcher who found it in 1969, and it is a real property of FIFO and not a mistake in the program. The reason is that FIFO's victim has nothing to do with what the program is using: adding a frame changes the arrival order of everything that follows, and the page FIFO decides to throw out can easily be one that a smaller memory would have kept.

LRU cannot do this, and neither can optimal. Both are stack algorithms: with n + 1 frames they always hold a superset of what they would hold with n frames, so a page that is present with n frames is present with n + 1, and a hit stays a hit. In the table above LRU goes from 10 faults to 8 and optimal from 7 to 6, both in the right direction.

That is the useful summary:

Notice also that on this string LRU with three frames is worse than FIFO with three frames, 10 faults against 9. Two different strings, two different winners: the general claim that LRU is better than FIFO is a claim about programs in general, not about every string.

How LRU is implemented for real

The program uses a timestamp and searches the frames for the smallest, which costs a loop over every frame at every fault. That is fine for five frames and impossible for the million frames of a real machine. Two standard implementations, both worth knowing:

Counters. Every page table entry holds the time of its last use, and the hardware writes it on every reference. Finding the victim is then a search, which is the program above. Simple, and the search is the problem.

A stack. Keep the page numbers in a doubly linked list, and move a page to the top whenever it is used. The bottom is always the least recently used, so there is no search at all. That is the doubly linked list of [Practical 14: Doubly Linked Lists], used for exactly this.

And the honest answer: no real operating system implements true LRU, because updating a timestamp or a list on every single memory reference costs more than it saves. What they use instead is an approximation:

• The second chance, or clock, algorithm. FIFO with one extra bit. Each page has a

reference bit the hardware sets when the page is used. When FIFO picks a victim, if its reference bit is 1 the bit is cleared and the page is given a second chance rather than evicted. A page in use survives; a page that is not is evicted on the next pass. It is nearly as good as LRU and it costs one bit.

• Not recently used and enhanced second chance, which add a modify bit so that a page

which has not been written can be dropped without writing it back to the disk.

Linux uses a two-list variation of the clock algorithm, and Windows a working-set scheme. Neither is LRU, and both are trying to be.

Thrashing, which is what happens when there are too few frames

The table showed faults falling as frames rose. Run the experiment the other way, on a machine with many processes and not enough memory for them, and the faults rise until the machine spends all its time paging and no time computing. That is thrashing.

The signature is easy to recognise and worth knowing for the viva: the processor utilisation drops, the operating system concludes that it should admit more processes, memory gets tighter still, and the faults rise further. A machine in that state is unusable and the disk light is permanently on.

The cures are all about the working set, meaning the set of pages a process is actively using:

• Give each process enough frames for its working set, and admit fewer processes if there is not

enough memory for all of them.

• Measure the fault rate and use it directly: too high, give the process more frames; very low,

take some away.

Procedure

1. Write the program. Compile with gcc -Wall -Wextra -o page page.c and run it.
2. Check the FIFO and LRU tables for three frames against the textbook: 15 faults and 12.
3. Remove if (how == LRU) stamp[found] = i; and run it again. LRU now gives FIFO's answer, which

is the proof that the one line is the whole difference.

1. Work the first eight references of LRU with three frames on paper and compare with the table.
2. Write the second program and confirm Belady's anomaly: 9 faults at three frames and 10 at four.
3. Change the reference string to one of your own with ten references and four distinct pages, and

predict the FIFO answer before running it.

1. Add a frame count of 6 and note that nothing improves, because the string touches only five

distinct pages.

Result

FIFO, LRU and optimal page replacement were simulated over the standard twenty-reference string. With three frames FIFO took 15 page faults, LRU 12 and optimal 9, agreeing with the published figures, giving hit ratios of 0.25, 0.40 and 0.55. The frame count was varied from 1 to 5: with one frame every reference faulted, and LRU's faults fell 20, 17, 12, 8, 7. FIFO was found to beat LRU at two frames, 15 faults against 17. On Belady's string FIFO took 9 faults with three frames and 10 with four, which is Belady's anomaly, while LRU improved from 10 to 8 as a stack algorithm must.

Where marks are lost

• Setting the LRU stamp only on a fault. The program is then FIFO with a different name, and

the examiner will see the identical answer.

• Counting the cold-start faults as replacement decisions, or forgetting that the first few

references must fault.

• Computing the hit ratio as hits over faults instead of hits over references.
• Saying more frames always means fewer faults. Under FIFO it does not: that is Belady's

anomaly, and it is a standard question.

• Saying LRU is always better than FIFO. At two frames on this string it is worse, 17 against

15.

• Saying optimal should be used. It needs the future.
• Not showing the frame contents at each step. The examiner marks the working, and the table

of frames is the working.

• Confusing a page with a frame. A page belongs to the program, a frame to the machine.

For the journal

Write the aim, MU's own wording, the reference string, and the full step tables for FIFO and LRU with three frames, because the frame contents at each step are the working. Under each, the fault count, the hit count and the hit ratio as a division. Then the table of faults against frames from 1 to 5 for all three algorithms, and the Belady run with its two lines. The conclusion: LRU beats FIFO on this string because it evicts by use rather than by age, the two differ by one line of program, and FIFO can get worse when memory is added while LRU cannot.

Quick revision

• A page belongs to the program, a frame to the machine, and demand paging brings a page in only

when it is touched. A reference to a page not in a frame is a page fault.

• Hit ratio is hits over references; miss ratio is faults over references; they add to 1.
• FIFO evicts the earliest arrival. LRU evicts the page unused for longest. Optimal evicts the

page whose next use is furthest away and cannot be implemented.

• FIFO and LRU differ by one line: LRU refreshes the stamp on a hit as well as on a load.
• On the standard string with three frames: FIFO 15 faults, LRU 12, optimal 9, hit ratios 0.25,

0.40, 0.55.

• The first f references with f frames must fault. Those are cold start or compulsory misses.
• Belady's anomaly: FIFO can take more faults with more frames. Proved here, 9 at three frames

and 10 at four, on the string 1 2 3 4 1 2 5 1 2 3 4 5.

• LRU and optimal are stack algorithms and cannot show the anomaly, because with n + 1 frames they

hold a superset of what they hold with n.

• LRU at two frames on the standard string is worse than FIFO. One measurement never settles which

algorithm is better.

• Real systems approximate LRU with the second chance or clock algorithm: FIFO plus a reference

bit the hardware sets, cleared to give a used page one more chance.

• Thrashing is a machine spending all its time paging. The cure is to fit each process's working

set, admitting fewer processes if necessary.

Questions you should be able to answer

1. What is a page fault? A reference to a page that is not in any frame. The hardware traps to the operating system, which loads the page from the disk and restarts the instruction.

2. Which page does FIFO evict, and which does LRU evict? FIFO evicts the page that has been in memory longest, by arrival. LRU evicts the page that has not been used for the longest time.

3. In a program, what is the only difference between FIFO and LRU? Whether the timestamp is refreshed on a hit. FIFO stamps a page when it is loaded and never again; LRU stamps it every time it is used.

4. Twenty references, twelve faults. What are the hit and miss ratios? Eight hits, so the hit ratio is 8 / 20 = 0.40 and the miss ratio is 12 / 20 = 0.60.

5. Does adding a frame always reduce the number of faults? No. Under FIFO it can increase them, which is Belady's anomaly: on the string 1 2 3 4 1 2 5 1 2 3 4 5 FIFO takes 9 faults with three frames and 10 with four.

6. Why can LRU not show Belady's anomaly? Because it is a stack algorithm: with n + 1 frames it always holds a superset of the pages it would hold with n, so a hit with n frames is still a hit with n + 1.

7. Why does no operating system implement true LRU? Because it would have to update a timestamp or a list on every single memory reference, which costs more than the faults it saves. They approximate it with the clock algorithm, which is FIFO plus a reference bit set by the hardware.

8. What is the optimal algorithm for, if it cannot be implemented? It is the bound. It gives the fewest faults any algorithm could take on that string, so it says how much room for improvement a real algorithm has.

9. What is thrashing, and what cures it? A machine spending nearly all its time servicing page faults, because the processes together have less memory than their working sets need. The cure is to give each process enough frames for its working set and to run fewer processes if there is not enough memory.

The five in bold are MU's. SCAN and LOOK are here because C-SCAN and C-LOOK are defined by the difference from them, and an examiner who asks for C-SCAN expects you to be able to say what the C is for. It stands for circular.

The program

One program, seven algorithms, and four of them share a single function because they differ only in two decisions: does the head go all the way to the end of the disk, and does it serve requests on the way back.

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

#define MAXQ  32
#define LOW   0          /* the lowest cylinder on the disk  */
#define HIGH  199        /* the highest                      */

/* The random order is produced by a generator written out here, not by
   rand(), so that the answer is the same on every machine and every C library.
   rand() is allowed to differ between implementations and does. */
static unsigned long seed = 12345UL;

static int next_random(int n)
{
    seed = seed * 1103515245UL + 12345UL;
    return (int) ((seed >> 16) % (unsigned long) n);
}

static int distance(int a, int b) { return a > b ? a - b : b - a; }

static void report(const char *name, const int *order, int n, int start)
{
    int total = 0, at = start;
    printf("  %-7s ", name);
    printf("%d", start);
    for (int i = 0; i < n; i++) {
        printf(" -> %d", order[i]);
        total += distance(at, order[i]);
        at = order[i];
    }
    printf("\n          total head movement = %d cylinders\n", total);
}

/* first come first serve: the queue in the order it arrived */
static void fcfs(const int *q, int n, int start)
{
    report("FCFS", q, n, start);
}

/* shortest seek time first: always the nearest request */
static void sstf(const int *q, int n, int start)
{
    int left[MAXQ], order[MAXQ], done[MAXQ] = { 0 };
    memcpy(left, q, (size_t) n * sizeof *q);
    int at = start;
    for (int k = 0; k < n; k++) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (done[i]) continue;
            if (best < 0 || distance(at, left[i]) < distance(at, left[best])) best = i;
        }
        done[best] = 1;
        order[k] = left[best];
        at = left[best];
    }
    report("SSTF", order, n, start);
}

static int by_value(const void *a, const void *b)
{
    int x = *(const int *) a, y = *(const int *) b;
    return (x > y) - (x < y);
}

/* the four sweeping algorithms differ only in where the head turns round and
   whether it serves requests on the way back */
static void sweep(const char *name, const int *q, int n, int start,
                  int to_the_end, int serve_on_return)
{
    int s[MAXQ], order[MAXQ];
    int k = 0;
    memcpy(s, q, (size_t) n * sizeof *q);
    qsort(s, (size_t) n, sizeof *s, by_value);

    int first_above = n;
    for (int i = 0; i < n; i++)
        if (s[i] >= start) { first_above = i; break; }

    /* going up, serving everything at or above the head */
    for (int i = first_above; i < n; i++) order[k++] = s[i];

    if (to_the_end) order[k++] = HIGH;          /* SCAN and C-SCAN reach the end */

    if (serve_on_return) {                      /* SCAN and LOOK: serve coming back */
        for (int i = first_above - 1; i >= 0; i--) order[k++] = s[i];
    } else {                                    /* C-SCAN and C-LOOK: jump and restart */
        if (to_the_end) order[k++] = LOW;
        for (int i = 0; i < first_above; i++) order[k++] = s[i];
    }
    report(name, order, k, start);
}

/* random scheduling: whatever comes to hand */
static void rss(const int *q, int n, int start)
{
    int left[MAXQ], order[MAXQ];
    memcpy(left, q, (size_t) n * sizeof *q);
    int count = n;
    for (int k = 0; k < n; k++) {
        int pick = next_random(count);
        order[k] = left[pick];
        left[pick] = left[--count];
    }
    report("RSS", order, n, start);
}

int main(void)
{
    int q[] = { 98, 183, 37, 122, 14, 124, 65, 67 };
    int n = (int) (sizeof q / sizeof *q);
    int start = 53;

    printf("disk cylinders %d to %d, head at %d\n", LOW, HIGH, start);
    printf("request queue:");
    for (int i = 0; i < n; i++) printf(" %d", q[i]);
    printf("\n\n");

    fcfs(q, n, start);
    sstf(q, n, start);
    sweep("SCAN",   q, n, start, 1, 1);
    sweep("C-SCAN", q, n, start, 1, 0);
    sweep("LOOK",   q, n, start, 0, 1);
    sweep("C-LOOK", q, n, start, 0, 0);
    rss(q, n, start);
    return 0;
}

The four sweeps are one function

sweep(name, q, n, start, to_the_end, serve_on_return) is the whole of SCAN, C-SCAN, LOOK and C-LOOK, and the two flags are the whole of the difference:

Writing it that way is worth a mark on its own, because it makes the relationship between the four impossible to get wrong. Two flags, four algorithms.

qsort first. All four sweeps need the requests in cylinder order, so the array is sorted and then the position of the first request at or above the head is found. Everything above that index is served going up; everything below it is served coming down or after the jump.

The random generator is written out in the source. rand() is allowed to differ between C libraries and does, so a program using it would print a different order on a different machine and the page could not claim an answer. The generator here is three lines and gives the same sequence everywhere, which is what makes the RSS line reproducible: the program was run twice and printed the same order and the same 520 both times.

The seven totals, and what they say

FCFS is the worst, and it is worth seeing why

Follow the order: 53 to 98 to 183 to 37 to 122 to 14 to 124 to 65 to 67. The arm crosses the middle of the disk five times. The distances are

• total = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640

The 146 in the middle is the arm going from cylinder 183 down to 37 and back up again afterwards. FCFS does no thinking at all, and on a busy disk it is close to the worst possible order.

Its one virtue is the same as first come first serve for the processor: nobody is overtaken, so nothing starves.

SSTF is the best here, and cannot be trusted

Two hundred and thirty-six cylinders, a little over a third of FCFS. The order goes to the two nearby requests first, then down to the pair below, then up through the rest: 53 to 65 to 67 to 37 to 14 to 98 to 122 to 124 to 183.

• total = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236

SSTF can starve a request, and that is its defect. It is the disk version of shortest job first. If requests keep arriving near the head, a request at cylinder 190 is passed over indefinitely: it is never the nearest, so it is never chosen. On a disk that is being written continuously in one region, a single read at the far edge can wait for an unbounded time.

And SSTF is not optimal, only greedy. On this queue it happens to give the lowest total of the seven, and there is no guarantee of that in general: choosing the nearest request each time can walk the head into a corner it then has to come out of.

SCAN, the elevator

The arm goes up, serving everything on the way, reaches the end of the disk, and comes back down serving everything it passed: 53 up to 199, then down to 14.

• total = 12 + 2 + 31 + 24 + 2 + 59 + 16 + 162 + 23 = 331

It is called the elevator algorithm because that is exactly what a lift does: it goes to the top serving the floors in order, then comes down serving the rest, and nobody is skipped. The consequence is the property SSTF lacks: no starvation. A request at the far edge waits at most one sweep.

C-SCAN, and why it costs more

The C is for circular. When the arm reaches the end it does not turn round and serve on the way back. It jumps straight to cylinder 0, serving nothing, and sweeps up again: 53 up to 199, jump to 0, up to 37.

• total = 12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 23 = 382

That is 51 cylinders more than SCAN, and the 199 in the middle is the jump. C-SCAN moves the head further and treats the requests more evenly, and understanding that trade is the point of the algorithm.

Under SCAN, a cylinder in the middle of the disk is passed twice per sweep and a cylinder at the edge once, so the middle gets better service. Under C-SCAN every cylinder is visited once per sweep, in the same direction, so the waiting time is uniform wherever the request is. A request just behind the head under SCAN may be served almost at once or after a whole double sweep, depending on which way the head is going; under C-SCAN it always waits one sweep.

SCAN minimises the movement. C-SCAN minimises the variation in how long a request waits. On

a disk serving many users, the second is often what you want.

LOOK and C-LOOK, which stop looking sooner

The wasted part of SCAN and C-SCAN is going all the way to cylinder 199 and 0 when the furthest requests are at 183 and 14. LOOK and C-LOOK go only as far as the last request in that direction.

• LOOK total = 12 + 2 + 31 + 24 + 2 + 59 + 146 + 23 = 299
• C-LOOK total = 12 + 2 + 31 + 24 + 2 + 59 + 169 + 23 = 322

LOOK saves 32 cylinders over SCAN and C-LOOK saves 60 over C-SCAN, on this queue, by not touching the two ends of the disk. They keep the no-starvation guarantee, because the sweep still passes every waiting request. In practice LOOK and C-LOOK are what real systems implement, and they are usually what is meant when somebody says SCAN or C-SCAN loosely.

RSS, and what it is for

Five hundred and twenty cylinders, worse than everything except FCFS, which is the answer you would expect from serving requests in no order at all.

Random scheduling is not a policy anybody ships. It is in the list, and in this program, as a baseline: it says what the total looks like when the scheduler does nothing useful, so the other algorithms can be measured against something other than each other. FCFS at least follows the arrival order; RSS follows nothing.

One honest note about it, and it is the reason the generator is written out in the program: a random algorithm's answer depends on the random numbers. The 520 above is the total for one particular sequence. Run it with a different seed and the total changes, and the average over many seeds is the meaningful figure. This program fixes the seed so that the answer can be printed and checked, and a student writing it up should say which seed they used.

The comparison to learn

Three sentences that answer most questions on this topic:

FCFS is fair and slow. SSTF is fast and can starve. The sweeping algorithms are the compromise and are what real systems use.

The C in C-SCAN and C-LOOK buys a uniform waiting time and costs extra head movement,

because the return jump serves nothing.

LOOK and C-LOOK are SCAN and C-SCAN without the pointless trip to the end of the disk.

Procedure

1. Write the program. Compile with gcc -Wall -Wextra -o disk disk.c and run it.
2. Check the FCFS total of 640 and the SSTF total of 236 by adding the distances on paper.
3. Draw all seven paths on graph paper, cylinder number up the side and order along the bottom.

The shape of each algorithm is the point, and an examiner may ask for the diagram.

1. Change the starting head position to 100 and run it again. Note which algorithm changes most.
2. Change the initial direction of the sweeps by serving the requests below the head first.

C-SCAN's total changes considerably.

1. Change the seed of the random generator and record three different RSS totals.
2. Add a request at cylinder 199 and at cylinder 0, and note that LOOK and SCAN now give the same

answer, and so do C-LOOK and C-SCAN.

Result

Seven disk scheduling algorithms were simulated over the queue 98, 183, 37, 122, 14, 124, 65, 67 with the head at cylinder 53 on a disk of 200 cylinders. The total head movement was FCFS 640, SSTF 236, SCAN 331, C-SCAN 382, LOOK 299, C-LOOK 322 and RSS 520 cylinders. The FCFS and SSTF totals agree with the published figures for this queue. SSTF gave the least movement on this queue and is the only one of the five MU names that can starve a request; C-SCAN and C-LOOK cost more movement than SCAN and LOOK and give a uniform waiting time in return.

Where marks are lost

• Not counting the movement to the end of the disk under SCAN and C-SCAN. The trip to 199 and

the jump to 0 are head movement and are counted.

• Counting the C-SCAN return jump as serving requests. It serves none; that is what makes it

circular.

• Confusing SCAN with C-SCAN, or LOOK with C-LOOK. The C means the head jumps back without

serving. LOOK means it stops at the last request instead of the disk end.

• Not stating the direction of the first sweep. The answer depends on it, and an examiner

expects it to be written down.

• Saying SSTF is optimal. It is greedy, it is not optimal, and it can starve a request.
• Giving an RSS total without saying what order was used. A random answer is not reproducible

unless the sequence is stated.

• Forgetting that the head position counts as the start and measuring from the first request.
• Saying disk scheduling matters on an SSD. It does not, and Linux ships a none scheduler

for them.

For the journal

Write the aim, MU's own wording, the disk size, the starting head position and the request queue. For each of the five algorithms MU names, write the service order, the sum of the distances as an addition, and the total. Draw the seven paths on graph paper and paste it in, because the diagram is half the marks in this exercise. Then the comparison table with the starvation and uniform-wait columns, and one sentence saying which algorithm you would choose for a disk serving many users and why. The conclusion: the order the requests are served in changes the total head movement by a factor of nearly three on this queue, and the fastest of them is the one that can starve a request.

Quick revision

• Seek time dominates a disk access and is proportional to the distance the arm moves, so the

figure to minimise is the total head movement in cylinders.

• On the queue 98, 183, 37, 122, 14, 124, 65, 67 with the head at 53: FCFS 640, SSTF 236, SCAN

331, C-SCAN 382, LOOK 299, C-LOOK 322, RSS 520.

• FCFS serves in arrival order: fair, no starvation, worst movement.
• SSTF serves the nearest: least movement here, greedy rather than optimal, and the only one of

MU's five that can starve a request.

• SCAN is the elevator: to the end of the disk, then back serving on the way. No starvation.
• C-SCAN jumps back to the start serving nothing, then sweeps again. More movement than SCAN, and

a uniform waiting time in return.

• LOOK and C-LOOK are the same two without the trip to the physical end. They are what is used in

practice.

• RSS is Random Scheduling, a baseline rather than a policy. Its answer depends on the random

sequence, so the seed must be stated.

• The C stands for circular. The difference between SCAN and LOOK is whether the head reaches the

end of the disk or only the last request.

• None of this applies to a solid state disk, which has no arm.

Questions you should be able to answer

1. Why is head movement the figure to minimise? Because the seek time is proportional to the distance the arm moves and dominates a disk access. Rotational latency and transfer time are not things the scheduler can change.

2. Which algorithm gave the least movement here, and why is it still not used? SSTF, with 236 cylinders against FCFS's 640. It can starve a request: a cylinder far from the head is never the nearest, so it may never be chosen while nearby requests keep arriving.

3. What does the C in C-SCAN stand for, and what does it change? Circular. The head does not serve requests on the way back: it jumps to the start of the disk and sweeps in the same direction again. That costs more movement, 382 against SCAN's 331 here, and gives every cylinder the same waiting time.

4. What is the difference between SCAN and LOOK? SCAN goes all the way to the physical end of the disk; LOOK turns round at the last request in that direction. Here that saved 32 cylinders, 299 against 331.

5. Why is C-SCAN's waiting time more uniform than SCAN's? Under SCAN a cylinder in the middle is passed twice per double sweep and a cylinder at the edge once, so the middle is served better. Under C-SCAN every cylinder is visited once per sweep in the same direction, so a request waits one sweep wherever it is.

6. What does RSS stand for and what is it for? Random Scheduling: the requests are served in a random order. It is a baseline for comparison, not a policy anybody ships, and its total depends on the random sequence used.

7. Two algorithms in the list cannot starve a request. Which? Every sweeping algorithm: SCAN, C-SCAN, LOOK and C-LOOK, because the sweep passes every waiting request. FCFS cannot starve anybody either, since nobody is overtaken. SSTF and RSS can.

8. Does any of this apply to a solid state disk? No. There is no arm and no seek, so every block costs the same. Linux provides a scheduler called none for them.

9. The head is at 53 and the requests are at 65 and 37. Which does SSTF serve first? Cylinder 65, which is 12 away, rather than 37, which is 16 away.

Linux uses indexed allocation, and the index is called the inode. A classical Unix inode holds twelve block numbers directly, then a pointer to a block of block numbers, then a pointer to a block of pointers to blocks of block numbers, and one more level after that. Small files need no indirection at all; large files pay for it. The program below is the first twelve, simplified to six.

The free space bitmap

The other half of the design: how does the file system know which blocks are free?

A bitmap is one bit per block, 1 for used and 0 for free. Finding a free block is a scan for a zero bit, which on real hardware is fast because whole words can be tested at once. Finding n consecutive free blocks is also easy, which matters for contiguous allocation. The cost is the size: a 1 terabyte disk with 4 kibibyte blocks needs 32 mebibytes of bitmap.

A free list is the alternative: each free block holds the number of the next free block. It costs no extra space at all, since the pointers live in blocks nobody is using, and it cannot find consecutive blocks without walking the whole list.

The program uses a bitmap and prints it as text, one character per block, so that the allocation can be watched.

The program

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

#define BLOCKS      32        /* blocks on our little disk            */
#define BLOCK_SIZE  16        /* bytes in one block                   */
#define FILES        8        /* entries the directory holds          */
#define NAME_LEN    12
#define INDEX_MAX    6        /* blocks one file may have             */

/* the disk: an array of blocks, which is what a real disk is to the
   file system: a numbered sequence of fixed-size pieces */
static char disk[BLOCKS][BLOCK_SIZE];

/* the free space bitmap: one character per block, '.' free, '#' used */
static char bitmap[BLOCKS + 1];

/* one directory entry, which in a real file system is the inode */
struct entry {
    char name[NAME_LEN];
    int  used;
    int  size;                     /* in bytes                        */
    int  count;                    /* how many blocks it holds        */
    int  index[INDEX_MAX];         /* the block numbers: the index block */
};

static struct entry directory[FILES];

static void format(void)
{
    memset(disk, 0, sizeof disk);
    memset(directory, 0, sizeof directory);
    for (int b = 0; b < BLOCKS; b++) bitmap[b] = '.';
    bitmap[BLOCKS] = '\0';
    bitmap[0] = '#';               /* block 0 is the directory itself */
    printf("formatted: %d blocks of %d bytes, %d directory entries\n",
           BLOCKS, BLOCK_SIZE, FILES);
}

static void show_bitmap(const char *why)
{
    int free_blocks = 0;
    for (int b = 0; b < BLOCKS; b++) if (bitmap[b] == '.') free_blocks++;
    printf("  bitmap %s  (%d of %d blocks free)\n", bitmap, free_blocks, BLOCKS);
    (void) why;
}

static int find(const char *name)
{
    for (int i = 0; i < FILES; i++)
        if (directory[i].used && strcmp(directory[i].name, name) == 0) return i;
    return -1;
}

static int allocate(void)
{
    for (int b = 1; b < BLOCKS; b++)
        if (bitmap[b] == '.') { bitmap[b] = '#'; return b; }
    return -1;
}

static int create(const char *name, const char *data)
{
    if (find(name) >= 0) {
        printf("create %s: a file of that name already exists\n", name);
        return -1;
    }
    int slot = -1;
    for (int i = 0; i < FILES; i++) if (!directory[i].used) { slot = i; break; }
    if (slot < 0) {
        printf("create %s: the directory is full\n", name);
        return -1;
    }

    int len = (int) strlen(data);
    int need = (len + BLOCK_SIZE - 1) / BLOCK_SIZE;   /* round UP */
    if (need == 0) need = 1;
    if (need > INDEX_MAX) {
        printf("create %s: %d bytes needs %d blocks and a file may hold %d\n",
               name, len, need, INDEX_MAX);
        return -1;
    }

    struct entry *e = &directory[slot];
    memset(e, 0, sizeof *e);
    for (int k = 0; k < need; k++) {
        int b = allocate();
        if (b < 0) {
            for (int j = 0; j < k; j++) bitmap[e->index[j]] = '.';  /* give it back */
            printf("create %s: the disk is full\n", name);
            return -1;
        }
        e->index[k] = b;
        int from = k * BLOCK_SIZE;
        int take = len - from;
        if (take > BLOCK_SIZE) take = BLOCK_SIZE;
        if (take > 0) memcpy(disk[b], data + from, (size_t) take);
    }
    snprintf(e->name, sizeof e->name, "%s", name);
    e->used = 1;
    e->size = len;
    e->count = need;

    printf("create %-9s %3d bytes in %d block(s):", name, len, need);
    for (int k = 0; k < need; k++) printf(" %d", e->index[k]);
    printf("\n");
    show_bitmap("after create");
    return slot;
}

static void read_file(const char *name)
{
    int i = find(name);
    if (i < 0) {
        printf("read %s: no such file\n", name);
        return;
    }
    struct entry *e = &directory[i];
    printf("read   %-9s [", name);
    int left = e->size;
    for (int k = 0; k < e->count; k++) {
        int take = left > BLOCK_SIZE ? BLOCK_SIZE : left;
        printf("%.*s", take, disk[e->index[k]]);
        left -= take;
    }
    printf("]\n");
}

static void delete_file(const char *name)
{
    int i = find(name);
    if (i < 0) {
        printf("delete %s: no such file\n", name);
        return;
    }
    struct entry *e = &directory[i];
    printf("delete %-9s freeing block(s):", name);
    for (int k = 0; k < e->count; k++) {
        printf(" %d", e->index[k]);
        bitmap[e->index[k]] = '.';
        memset(disk[e->index[k]], 0, BLOCK_SIZE);
    }
    printf("\n");
    memset(e, 0, sizeof *e);
    show_bitmap("after delete");
}

static void list(void)
{
    printf("directory\n");
    printf("  name        bytes blocks  block numbers\n");
    int files = 0, used = 0;
    for (int i = 0; i < FILES; i++) {
        if (!directory[i].used) continue;
        struct entry *e = &directory[i];
        printf("  %-11s %5d %6d ", e->name, e->size, e->count);
        for (int k = 0; k < e->count; k++) printf(" %d", e->index[k]);
        printf("\n");
        files++;
        used += e->count;
    }
    if (files == 0) printf("  (empty)\n");
    printf("  %d file(s), %d block(s) of data\n", files, used);
}

int main(void)
{
    format();
    show_bitmap("after format");
    printf("\n");

    create("notes.txt", "Computer Science Practical 3, Module 1");
    create("roll.txt",  "2331");
    create("marks.csv", "maths,78\nphysics,65\nchem,92\n");
    printf("\n");

    list();
    printf("\n");

    read_file("notes.txt");
    read_file("marks.csv");
    read_file("absent.txt");
    printf("\n");

    delete_file("roll.txt");
    printf("\n");

    create("new.txt", "this one reuses the block roll.txt gave back");
    printf("\n");

    list();
    return 0;
}

Reading the output, which is where the design shows

The bitmap starts with block 0 already used. Block 0 is the directory itself. Every real file system reserves its first blocks for its own structures, and a student who allocates block 0 to a file has overwritten the directory.

38 bytes took 3 blocks. The blocks are 16 bytes, and 38 bytes needs three of them: two full and one with 6 bytes in it. The arithmetic is worth writing out, because getting it wrong is the commonest bug in this exercise:

int need = (len + BLOCK_SIZE - 1) / BLOCK_SIZE;    /* rounds UP */

38 / 16 in C is 2, because integer division throws the remainder away, and a program that uses it loses the last 6 bytes of every file. Adding BLOCK_SIZE - 1 first rounds up: 38 + 15 is 53, and 53 divided by 16 is 3 and a bit, which integer division cuts to 3.

Note the form that is written there. Putting an equals sign between 53 over 16 and 3 would be wrong, because 53 over 16 is 3.3125; what is true is that C's integer division of 53 by 16 gives

1. The distinction matters in a journal, and the arithmetic checker on this book refused two

earlier drafts of this paragraph for exactly that reason.

The last block is not full, and that space is lost. Three blocks of 16 bytes is 48 bytes of disk for a 38 byte file, so 48 - 38 = 10 bytes are wasted. That is internal fragmentation, and it is unavoidable with fixed blocks. For new.txt it is 48 - 44 = 4 bytes. On a real file system with 4 kibibyte blocks, a thousand files of one byte each occupy 4 megabytes.

new.txt got blocks 4, 7 and 8, which are not consecutive. Block 4 is the one roll.txt gave back when it was deleted, and blocks 7 and 8 were the next free ones. That is indexed allocation working: the file is scattered and the index block records where the pieces are, so nothing has to be moved and no space is left unusable. Under contiguous allocation the single free block at 4 would have been too small for this file and would have stayed empty.

Deleting freed the blocks and cleared the entry. The bitmap went from seven used blocks to six, with a gap in the middle: ####.##. The blocks are also wiped, which a real file system usually does not do, and that is why deleted files can often be recovered.

Reading a missing file says so. read absent.txt: no such file, rather than crashing or printing rubbish. Every operation in the program checks first, and there are five such checks: the name already exists, the directory is full, the file is too large for its index, the disk is full, and the file does not exist.

The rollback in create, which is worth copying

If the disk fills up halfway through allocating a file, the blocks already taken must be given back:

int b = allocate();
if (b < 0) {
    for (int j = 0; j < k; j++) bitmap[e->index[j]] = '.';   /* give them back */
    printf("create %s: the disk is full\n", name);
    return -1;
}

Without those two lines a failed create leaks blocks: they are marked used, no file owns them, and nothing will ever free them. It is exactly the leak of a shared memory segment in [Practical 1: Process Communication using Shared Memory], and the same principle applies: an operation that fails halfway must undo what it has already done.

The directory, which is also the inode here

In this program one structure holds both the name and the block numbers:

struct entry {
    char name[NAME_LEN];
    int  used, size, count;
    int  index[INDEX_MAX];     /* the index block, inline */
};

Unix splits those two things, and knowing why is worth a mark. A directory entry holds only the name and an inode number; the inode holds the size, the permissions, the times and the block numbers. The split is what makes a hard link possible: two names in two directories pointing at one inode, so the file has two names and one set of blocks. The inode keeps a count of how many names point at it, and the blocks are freed only when that count reaches zero.

That is why rm on a file with two hard links does not free any space, and why the system call is called unlink and not delete.

What a real file system adds

The program is about eighty lines and a real one is hundreds of thousands. The differences worth naming:

The two most important of those are the last two but one.

A journal. Creating a file changes three things: the bitmap, the directory and the data. If the machine loses power between the first and the second, the disk is inconsistent: a block is marked used and no file owns it. A journalling file system writes what it is about to do into a log first, so that after a crash the log can be replayed or undone. ext4 does this, which is why a Linux machine that loses power usually comes back in seconds instead of running a long check.

The cache. Every read in this program goes to the array. In a real system it goes to the page cache in memory first, and reaches the disk only if it is not there. That is why reading the same file twice is far faster the second time, and it is the reason the page replacement algorithms of [Practical 9: Memory Management, FIFO and LRU Page Replacement] apply to file data as well as to program memory.

Procedure

1. Write the program. Compile with gcc -Wall -Wextra -o fs fs.c and run it.
2. Follow the bitmap through the run and write down which blocks each file holds.
3. Work out the internal fragmentation for each of the four files: blocks times 16, minus the

size.

1. Change the rounding to len / BLOCK_SIZE and run it again. Read the end of notes.txt and see

what was lost.

1. Create files until the directory is full, and then until the disk is full, and check that both

messages appear and that no blocks are leaked. Print the bitmap afterwards to be sure.

1. Add a write operation that appends to an existing file, allocating another block when the

last one is full.

1. Add a second directory, so that a file has a path of two parts. That is the step from a flat

file system to a tree.

Result

A file system was designed and implemented over a simulated disk of 32 blocks of 16 bytes, with a free space bitmap, a flat directory of 8 entries, and indexed allocation of up to 6 blocks a file. Create, read, list and delete were implemented, each with its error cases checked. A 38 byte file was seen to occupy three 16 byte blocks with 10 bytes of internal fragmentation, and a file created after a deletion was seen to reuse the freed block and two others that were not adjacent to it, which is indexed allocation doing what contiguous allocation cannot.

Where marks are lost

• Integer division for the block count. 38 / 16 is 2 and the last bytes of every file are

lost. It must round up.

• Allocating block 0, which in this design holds the directory.
• Not freeing the blocks on delete, so the disk fills with blocks nothing owns.
• Not rolling back a failed create, which leaks blocks the same way.
• No check for a duplicate name, so two directory entries claim the same name and only one can

ever be found.

• Not checking that the file fits in the index. With six block numbers the largest file is 96

bytes here, and a program that writes a seventh number writes past the end of the array.

• Printing the whole last block on read, including the bytes after the end of the file. The

size in the directory is what says where the file stops.

• Confusing internal with external fragmentation. Internal is the unused tail of the last

block; external is free space broken into pieces too small to use, which indexed allocation does not suffer from.

For the journal

Write the aim, MU's own wording, and the design first: the block size, the number of blocks, the layout of a directory entry, and which block holds the directory. Then the program, and the whole run with the bitmap after every operation, because the bitmap is the evidence that the allocation works. Add the internal fragmentation for each file as a subtraction, and one sentence on why new.txt got blocks 4, 7 and 8 rather than three consecutive ones. The conclusion: a file system is a free space map, a directory and a rule for recording which blocks a file owns, and indexed allocation lets a file be scattered so that no free space is wasted.

Quick revision

• To a file system a disk is a numbered sequence of fixed-size blocks.
• Four parts: the data blocks, the free space map, the directory, and the metadata about the disk

itself, which in Unix is the superblock.

• Contiguous allocation: fast, cannot grow, external fragmentation. Linked: grows freely, no

direct access. Indexed: an index block per file, direct access and growth, at the cost of the index.

• Linux uses indexed allocation and calls the index the inode: twelve direct block numbers

then three levels of indirection.

• Free space is tracked by a bitmap, one bit a block, or by a free list threaded through the free

blocks themselves. A bitmap can find consecutive blocks; a free list cannot.

• The block count rounds up: (len + BLOCK_SIZE - 1) / BLOCK_SIZE.
• Internal fragmentation is the unused tail of the last block, and is unavoidable. External

fragmentation is free space broken into unusable pieces, and indexed allocation avoids it.

• A create that fails halfway must give back the blocks it has already taken.
• A directory entry holds a name and an inode number; the inode holds everything else. That split

is what makes hard links possible, and why the system call is unlink.

• Deleting a file frees its blocks and usually does not wipe them, which is why deleted files can

often be recovered.

• A real file system adds a tree of directories, permissions, times, a journal against crashes and

a page cache.

Questions you should be able to answer

1. How many 16 byte blocks does a 38 byte file need, and how is that computed? Three. Add BLOCK_SIZE - 1 to the length first: 38 + 15 is 53, and C's integer division of 53 by 16 gives 3. Plain 38 / 16 gives 2 and loses the last six bytes.

2. What is internal fragmentation, and how much is there in that file? The unused part of the last block. Three blocks of 16 bytes is 48, the file is 38, so 48 - 38 = 10 bytes are wasted.

3. Give the three allocation methods and one disadvantage of each. Contiguous: a file cannot grow and free space suffers external fragmentation. Linked: there is no direct access to the middle of a file, and one damaged block loses the rest. Indexed: the index block is overhead and limits how large a file can be.

4. Which does Linux use, and what is its index called? Indexed allocation. The index is the inode, which holds twelve direct block numbers and then single, double and triple indirect blocks.

5. Why did the file created after a deletion get blocks 4, 7 and 8? Because block 4 had just been freed and was the first free block, and 7 and 8 were the next. Under indexed allocation the blocks need not be adjacent, so a single freed block in the middle of the disk is usable.

6. What is the difference between a bitmap and a free list? A bitmap is one bit per block, costs space proportional to the disk and can find consecutive free blocks quickly. A free list threads the free blocks together, costs no extra space and cannot find consecutive blocks without walking it.

7. What must a create do if the disk fills up halfway through? Free the blocks it has already allocated before reporting the failure, or they are leaked: marked used with no file owning them.

8. Why is the system call to remove a file called unlink? Because it removes one name from one directory. An inode may have several names, and its blocks are freed only when the last one goes.

9. What does a journalling file system protect against? An interrupted write leaving the disk inconsistent, for example a block marked used with no file owning it. The intended change is written to a log first, so it can be replayed or undone after a crash.

self is the object being worked on, and it is the first parameter of every method. It is not optional and it is not passed at the call: Node(10) calls __init__(new_object, 10).

nxt=None is a default. Node(10) and Node(10, None) mean the same thing, so a node made without a successor has one anyway: None.

The field is called nxt and not next on purpose. next is a built-in function in Python, and a field called next shadows nothing dangerous inside a class, but a local variable called next in a traversal does. Using nxt everywhere avoids having to remember which is safe. Some books write next and some write link; all three mean the same thing and an examiner will accept any of them.

None, and what it means in a structure

None is Python's single "there is nothing here" value. In this module it means three different things, and telling them apart is the whole of getting a linked structure right.

class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.nxt = nxt


head = None
print("empty?", head is None)

head = Node(1, Node(2, Node(3)))

count = 0
here = head
while here is not None:
    count += 1
    here = here.nxt

print("nodes:", count)
print("last node holds:", 3, "and its nxt is", head.nxt.nxt.nxt)

empty? True
nodes: 3
last node holds: 3 and its nxt is None

while here is not None is the traversal, and it appears in nine of the ten exercises. Read it as "while I am still standing on a node". The three lines of that loop are worth learning by heart:

here = head
while here is not None:
    ...
    here = here.nxt

Forgetting here = here.nxt gives an infinite loop, and it is the single commonest mistake in this module. If a program in the examination hall never finishes, that line is where to look.

Use is None, not == None. is asks whether it is the same object, which is what is meant; == calls a comparison method, which a class of your own may define and get wrong. Python itself warns about == None in some tools, and it is the house style everywhere.

The reference, which is why a node can be shared

This is the idea that makes every structure in this module work, and it is worth one program of its own.

class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.nxt = nxt


a = Node("first")
b = a                      # NOT a copy: another name for the same node

b.data = "changed"
print("a.data is now", a.data)
print("are they the same object?", a is b)

c = Node("first")
print("c looks like a, but is it a?", a is c, "and equal?", a.data == c.data)

a.data is now changed
are they the same object? True
c looks like a, but is it a? False and equal? False

A variable holds a reference, not an object. b = a makes a second name for one node, so a change through either name is seen through both. That is why head = node.nxt moves a pointer and copies nothing, and why a linked list of a million nodes can be traversed without copying anything.

The last line is worth a second look. a.data was changed to "changed" before c was made, so a.data == c.data is False. If the change had not happened they would be equal in content and still not the same object, and is and == would disagree. is asks about identity and == asks about content, and every chapter in this module needs both: is None for the end of a list, == for searching.

A readable __repr__, which saves hours of debugging

Print a node without help and this is what you get:

class Bare:
    def __init__(self, data):
        self.data = data


class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.nxt = nxt

    def __repr__(self):
        return f"Node({self.data!r})"


print(str(Bare(5)).split(" at ")[0] + " at 0x...>")
print(Node(5))
print([Node(1), Node(2), Node(3)])

<__main__.Bare object at 0x...>
Node(5)
[Node(1), Node(2), Node(3)]

The first line is what a class without __repr__ prints: its name and its address, which tells you nothing and is different on every run. Every class in this module defines __repr__, and the last line is why: printing a list of nodes then shows the nodes.

If a class defines only __repr__, print falls back on it, which is why one method is enough for this module. !r inside an f-string means "use repr on this", which is what puts the quotation marks round a string and leaves a number bare.

Raising an exception rather than returning a sentinel

Every structure in this module has operations that can fail: popping an empty stack, dequeueing an empty queue, deleting a key that is not there. There are two ways to report it and only one is right.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        if not self.items:
            raise IndexError("pop from an empty stack")
        return self.items.pop()


s = Stack()
s.push(7)
print("popped", s.pop())

try:
    s.pop()
except IndexError as e:
    print("the second pop said:", e)

popped 7
the second pop said: pop from an empty stack

Returning None or -1 for an empty stack is the wrong answer, and the reason is short: None is a value somebody may legitimately have pushed. A stack holding None and an empty stack would then be indistinguishable, and the caller has no way to tell a failure from a success.

An exception cannot be mistaken for a value. It also cannot be ignored: a caller who forgets to check a returned -1 carries on with a wrong number, while a caller who forgets to catch an exception gets a stack trace that names the line.

The exceptions this module uses, and what each is for:

Those are the same ones Python's own containers raise, which is the point: a structure of yours should fail the way a list or a dictionary fails, so that nobody has to learn your conventions.

try:
    [].pop()
except IndexError as e:
    print("list.pop on empty:", e)

try:
    {}["missing"]
except KeyError as e:
    print("dict['missing']:", e)

try:
    (1, 2)[5]
except IndexError as e:
    print("tuple[5]:", e)

list.pop on empty: pop from empty list
dict['missing']: 'missing'
tuple[5]: tuple index out of range

Those three messages are identical on Python 3.12, 3.13 and 3.14, which is how this page can print them. Some of Python's messages have changed between versions, and where a chapter in this module prints one, it has been run on all three.

The list against the node chain

Python's list is not an array and not a linked list. It is a dynamic array: a block of references that is reallocated larger when it fills up. Knowing that decides which operations are cheap.

items = [10, 20, 30]

items.append(40)          # cheap: put it at the end
items.insert(0, 5)        # dear: everything moves up one
print(items)

print("item 2 is", items[2])   # cheap: arithmetic on the address
items.pop(0)                   # dear: everything moves down one
print(items)

[5, 10, 20, 30, 40]
item 2 is 20
[10, 20, 30, 40]

That table is the answer to MU's bullet about static against dynamic, and it is measured rather than asserted in [Practical 12: Singly Linked Lists].

The cost of "walk n nodes" and "everything moves" is written O(n) and read "order n": the work grows in proportion to the number of items. "One step" is O(1), constant time, meaning the work does not depend on how many items there are. Those two symbols and O(log n) for a balanced tree are all the notation this module needs.

Measuring how long something takes

Several exercises ask for two approaches to be compared, so the measurement has to be trustworthy.

from time import perf_counter

n = 20000

start = perf_counter()
front = []
for i in range(n):
    front.insert(0, i)          # at the front: everything moves
at_front = perf_counter() - start

start = perf_counter()
back = []
for i in range(n):
    back.append(i)              # at the end
at_back = perf_counter() - start

print(f"{n} inserts at the front: {at_front:.4f} seconds")
print(f"{n} appends at the end  : {at_back:.4f} seconds")
print(f"the front was {at_front / at_back:.0f} times slower")
print("and both built the same list:", front == list(reversed(back)))

20000 inserts at the front: 0.1795 seconds
20000 appends at the end  : 0.0018 seconds
the front was 99 times slower
and both built the same list: True

Two rules about measuring, both learned the hard way in Module 1 of this book.

Print the answer, or the compiler and the interpreter may skip the work. The last line of that program compares the two lists, so neither loop can be optimised away and the reader can see that both really did build the same thing.

One measurement is not a result. The figures above are from one run on one machine and the ratio changes from run to run; what is stable is that inserting at the front of a list is far slower than appending, and that the gap grows with n. Where a chapter in this module prints a time, the timing digits are marked as varying and it is the shape that is proved, never the exact number.

perf_counter is the right clock for this: it is monotonic, it has the finest resolution the machine offers, and it measures elapsed time rather than processor time. time.time is a wall clock that can go backwards when the machine syncs its clock, and should not be used for measuring.

For a small operation that takes microseconds, the standard library has a better tool:

import timeit

setup = "items = list(range(1000))"

front = timeit.timeit("items.insert(0, 99)", setup=setup, number=1000)
back = timeit.timeit("items.append(99)", setup=setup, number=1000)

print(f"1000 inserts at the front: {front:.5f} seconds")
print(f"1000 appends at the end  : {back:.5f} seconds")

1000 inserts at the front: 0.00253 seconds
1000 appends at the end  : 0.00005 seconds

timeit runs the statement many times, uses the best clock available and turns the garbage collector off, so it is the tool to reach for when the thing being measured is fast.

The shape of every chapter in Module 2

Each of MU's ten exercises is one journal entry and one chapter, laid out the same way:

1. Aim, in MU's own words.
2. What you need to know: the structure explained before any code, with a picture in text.
3. The class, built up operation by operation, with the reasoning for each.
4. The run, which is what the program actually printed on all three interpreters.
5. The cost of each operation, as a table, because the examination asks for it.
6. Where it is used, which is MU's own third bullet in most of the exercises.
7. Procedure, Result, Where marks are lost, For the journal, Quick revision

and Questions you should be able to answer.

Procedure

1. Check your Python version with python3 --version. Anything from 3.8 onwards runs everything

in this module.

1. Type the Node program into a file and run it. Add a fourth node and count again.
2. Delete the line here = here.nxt and run it. Stop the program with Ctrl+C and note the

message, because you will see it again.

1. Add __repr__ to a class of your own and print a list of three of them.
2. Write a Stack whose pop returns None when empty, push None on to it, and satisfy

yourself that the caller cannot tell the two cases apart.

1. Run the timing program with n of 10000, 20000 and 40000, and note that the ratio grows.

Result

The tools Module 2 uses were set up and tried: a class with __init__ and self, None as the end of a structure, the reference that lets two names share one node, __repr__ for a readable printout, an exception rather than a sentinel for a failed operation, and perf_counter and timeit for measuring. Inserting at the front of a Python list was measured to be many times slower than appending, which is the fact the linked list exercise rests on.

Where marks are lost

• Using Python's own list, dictionary or deque for an exercise that asks for the structure to be built.

No marks, however correct the answer.

• Forgetting here = here.nxt, so the traversal never ends.
• == None instead of is None.
• No __repr__, so the output is a list of memory addresses and the examiner cannot see what

the program built.

• Returning None or -1 from a failed operation instead of raising an exception.
• Forgetting self in a method's parameter list, which gives a TypeError naming the wrong

number of arguments.

• Claiming a speed difference from one run without saying it was one run.

For the journal

This chapter is groundwork rather than one of the twenty, so it needs no journal entry of its own unless your teacher asks for one. If they do: the Node program, the traversal, the __repr__ before and after, and the timing figures with your own machine's numbers.

Quick revision

• A structure is a node class and a container class. __init__ is the constructor and

self is the object.

• None means empty list, last node, or missing child, depending on where it is. Test it with

is None.

• The traversal is here = head, while here is not None, and here = here.nxt at the bottom.

Leaving the last line out is an infinite loop.

• A variable holds a reference. b = a is a second name for one object, not a copy. is asks

about identity, == about content.

• Every class defines __repr__, or printing a list of nodes prints addresses.
• A failed operation raises: IndexError for a position, KeyError for a key, ValueError

for a bad value. Returning None is wrong because None may be a real item.

• Python's list is a dynamic array: cheap at the end, dear at the front. A linked list is the

opposite.

• O(1) means the work does not grow with the number of items; O(n) means it grows in proportion.
• Measure with perf_counter for anything slow and timeit for anything fast, never time.time,

and print the answer so the work cannot be skipped.

• Every listing in this module was run on Python 3.14, 3.13 and 3.12 and printed the same thing on

all three.

Questions you should be able to answer

1. What is self, and why is it the first parameter of every method? It is the object the method was called on. Python passes it automatically, so s.push(7) calls push(s, 7), and a method written without it fails with a TypeError about the number of arguments.

2. What does None mean in a linked list? Three things depending on where it is: an empty list when the head is None, the last node when a node's nxt is None, and a missing child when a tree node's left or right is None.

3. Why is None rather than == None? Because is compares identity, which is what is meant, while == calls a comparison method that a class of your own may define and get wrong.

4. b = a where a is a node. How many nodes are there? One. b is a second name for the same object, so a change through either name is visible through both.

5. Why does every class in this module define __repr__? Because without it, printing an object gives its class name and its address, which is different on every run and says nothing. With it, printing a list of nodes shows what the nodes hold.

6. Why should pop on an empty stack raise rather than return None? Because None is a value somebody may have pushed, so the caller could not tell an empty stack from a stack holding None. An exception cannot be mistaken for a value and cannot be silently ignored.

7. Which is cheaper in a Python list, append or insert(0, x), and why? append. A Python list is a dynamic array, so inserting at the front moves every other item up one, while appending usually writes into spare room at the end. Measured here, 20000 inserts at the front took about eighty times as long as 20000 appends.

8. What does O(1) mean, and what does O(n) mean? O(1) means the work does not depend on how many items there are. O(n) means it grows in proportion to the number of items.

9. Which clock should be used for timing, and which should not? time.perf_counter for anything slow and timeit for anything fast. Not time.time, which is a wall clock and can move backwards when the machine adjusts it.

tuple      : (2331, 'Aarti Kulkarni', [78, 65, 92])
  the name is student_tuple[1]: Aarti Kulkarni
dictionary : {'roll': 2331, 'name': 'Aarti Kulkarni', 'marks': [78, 65, 92]}
  the name is student_dict['name']: Aarti Kulkarni
class      : Student(2331, 'Aarti Kulkarni', [78, 65, 92])
  the name is s.name: Aarti Kulkarni
  and it can compute: total 235 average 78.33 grade first class

The tuple is the smallest and the least readable. student_tuple[1] is the name, and nothing in the program says so. Change the order of the fields and every use of it is silently wrong. A tuple is also immutable: the marks list inside it can be changed, but the roll number cannot, which is sometimes exactly right and sometimes a nuisance.

The dictionary is readable and unguarded. student_dict["name"] says what it is, which is a real improvement. But nothing stops student_dict["nmae"] = "x" from quietly adding a fourth key, nothing requires a student to have marks at all, and the dictionary cannot compute anything: the total has to be worked out by whoever wants it, everywhere.

The class is the ADT. The fields have names, the operations live with the data, and the rules can be enforced. s.grade() is written once and used everywhere; sum(student_dict["marks"]) is written everywhere and gets changed in one place out of four.

Use a tuple for a value with two or three parts that never changes, such as a coordinate. Use a

dictionary when the keys are not known until the program runs, such as data read from a file.

Use a class when the thing has rules or behaviour, which in this module it always does.

Python has a shorthand that gives a class most of its boilerplate for nothing:

from dataclasses import dataclass

@dataclass
class Student:
    roll: int
    name: str
    marks: list

That writes __init__, __repr__ and __eq__ for you. It is worth knowing and it is not used in this module, because the exercises are about writing the structure, and an examiner asking for a Student ADT wants to see __init__.

Create, update and delete, which need a collection

MU's second bullet asks for the basic operations, and they belong not to one object but to a collection of them. One Book cannot be created and deleted; a catalogue of Books can.

The four operations together are called CRUD: create, read, update, delete.

class Book:
    """A book in a library: the ADT and nothing but the ADT."""

    def __init__(self, isbn, title, author, copies):
        if copies < 0:
            raise ValueError("a book cannot have a negative number of copies")
        self.isbn = isbn
        self.title = title
        self.author = author
        self.copies = copies
        self.out = 0                      # how many are lent out

    def available(self):
        return self.copies - self.out

    def lend(self):
        if self.available() == 0:
            raise ValueError(f"no copy of {self.title!r} is available")
        self.out += 1

    def take_back(self):
        if self.out == 0:
            raise ValueError(f"no copy of {self.title!r} is out")
        self.out -= 1

    def __repr__(self):
        return (f"Book({self.isbn!r}, {self.title!r}, {self.author!r}, "
                f"{self.copies})")


class Library:
    """A collection of Books, with create, read, update and delete."""

    def __init__(self):
        self.books = {}                   # isbn -> Book

    def create(self, isbn, title, author, copies):
        if isbn in self.books:
            raise KeyError(f"{isbn} is already in the catalogue")
        self.books[isbn] = Book(isbn, title, author, copies)
        return self.books[isbn]

    def read(self, isbn):
        if isbn not in self.books:
            raise KeyError(f"{isbn} is not in the catalogue")
        return self.books[isbn]

    def update(self, isbn, **changes):
        book = self.read(isbn)
        for field, value in changes.items():
            if not hasattr(book, field):
                raise KeyError(f"a Book has no field called {field!r}")
            setattr(book, field, value)
        return book

    def delete(self, isbn):
        book = self.read(isbn)
        if book.out:
            raise ValueError(f"{book.title!r} has {book.out} copy out")
        del self.books[isbn]
        return book

    def __len__(self):
        return len(self.books)

    def report(self):
        print(f"  {'isbn':<14}{'title':<32}{'copies':>7}{'out':>5}{'free':>6}")
        for isbn in sorted(self.books):
            b = self.books[isbn]
            print(f"  {b.isbn:<14}{b.title:<32}{b.copies:>7}{b.out:>5}"
                  f"{b.available():>6}")
        print(f"  {len(self)} title(s) in the catalogue")


lib = Library()
lib.create("978-0132126", "Operating System Concepts", "Silberschatz", 3)
lib.create("978-1118290", "Data Structures in Python", "Goodrich", 2)
lib.create("978-8183332", "Data Structures Through Python", "Kanetkar", 1)
print("after three creates")
lib.report()

print()
print("read  : ", lib.read("978-1118290"))
lib.update("978-1118290", copies=5)
print("update: copies of Goodrich now", lib.read("978-1118290").copies)

lib.read("978-8183332").lend()
print("lend  : Kanetkar out", lib.read("978-8183332").out,
      "available", lib.read("978-8183332").available())

print()
for isbn, what in (("978-8183332", "delete a book that is lent out"),
                   ("978-0000000", "read a book that is not there")):
    try:
        lib.delete(isbn)
    except (KeyError, ValueError) as e:
        print(f"{what}: {type(e).__name__}: {e}")

try:
    lib.create("978-0132126", "Operating System Concepts", "Silberschatz", 1)
except KeyError as e:
    print(f"create a book twice: KeyError: {e}")

try:
    Book("978-1", "Nothing", "Nobody", -2)
except ValueError as e:
    print(f"a negative number of copies: ValueError: {e}")

print()
lib.read("978-8183332").take_back()
lib.delete("978-8183332")
print("after taking the copy back and deleting")
lib.report()

after three creates
  isbn          title                            copies  out  free
  978-0132126   Operating System Concepts             3    0     3
  978-1118290   Data Structures in Python             2    0     2
  978-8183332   Data Structures Through Python        1    0     1
  3 title(s) in the catalogue

read  :  Book('978-1118290', 'Data Structures in Python', 'Goodrich', 2)
update: copies of Goodrich now 5
lend  : Kanetkar out 1 available 0

delete a book that is lent out: ValueError: 'Data Structures Through Python' has 1 copy out
read a book that is not there: KeyError: '978-0000000 is not in the catalogue'
create a book twice: KeyError: '978-0132126 is already in the catalogue'
a negative number of copies: ValueError: a book cannot have a negative number of copies

after taking the copy back and deleting
  isbn          title                            copies  out  free
  978-0132126   Operating System Concepts             3    0     3
  978-1118290   Data Structures in Python             5    0     5
  2 title(s) in the catalogue

What that program is careful about

Every operation that can fail, checks, and raises. There are five such checks and the output shows four of them firing:

The rule from [Python for Data Structures: the Tools This Module Uses] is being followed: a failed operation raises and does not return None. And the exception type carries meaning: KeyError for something not present, ValueError for something present and wrong.

update refuses a field that does not exist. hasattr(book, field) is the guard, and without it lib.update(isbn, copyes=5) would add a new attribute called copyes and the real copies would be untouched. The program would print no error and give the wrong answer, which is the dictionary's problem from the last section appearing in a class.

delete returns the book it removed. A delete that returns the deleted object lets a caller undo it, which is how the undo of [Practical 14: Doubly Linked Lists] works.

__len__ makes len(lib) work, which is the first of Python's protocols this module uses. A class that defines __len__ can be measured with len() and is also truthy when non-empty, so if lib: works. __repr__ and __len__ are the two every container in this module defines.

The catalogue is a dictionary keyed by ISBN, so read is one step whatever the size. A list of Books would have to be searched, which is O(n). That is a data structure decision inside the ADT, and no caller can tell: swap the dictionary for a hash table of your own from [Practical 20: Hashing and Collision Handling] and every line outside the class still works. That is what "abstract" means, demonstrated.

What abstraction actually buys

The Employee, MU's third named ADT, is where the benefit is easiest to see.

# a primitive type: what it is and what you may do with it are fixed
n = 42
print("an int:", n, "of type", type(n).__name__)
print("  everything it can do is built in:", n + 1, n * 2, n ** 2)

# an abstract data type: WHAT it does is declared, HOW is hidden
class Employee:
    """Name, basic pay and a rule for the allowance. The rule is hidden."""

    HRA_RATE = 0.20
    DA_RATE = 0.10

    def __init__(self, name, basic):
        self.name = name
        self._basic = basic          # the single underscore says: not yours

    def basic(self):
        return self._basic

    def allowances(self):
        return self._basic * (Employee.HRA_RATE + Employee.DA_RATE)

    def gross(self):
        return self._basic + self.allowances()

    def raise_by(self, per_cent):
        if per_cent < 0:
            raise ValueError("a raise cannot be negative")
        self._basic = self._basic * (1 + per_cent / 100)

    def __repr__(self):
        return f"Employee({self.name!r}, {self._basic:.2f})"


e = Employee("R. Deshmukh", 30000)
print()
print("an Employee:", e)
print(f"  basic {e.basic():.2f}, allowances {e.allowances():.2f}, "
      f"gross {e.gross():.2f}")
e.raise_by(10)
print("after a 10 per cent raise:", e)
print(f"  gross is now {e.gross():.2f}")

print()
print("what makes it ABSTRACT:")
print("  the caller asks for gross() and never computes it")
print("  the two rates could become a table from a database")
print("  and not one line of the caller would change")

an int: 42 of type int
  everything it can do is built in: 43 84 1764

an Employee: Employee('R. Deshmukh', 30000.00)
  basic 30000.00, allowances 9000.00, gross 39000.00
after a 10 per cent raise: Employee('R. Deshmukh', 33000.00)
  gross is now 42900.00

what makes it ABSTRACT:
  the caller asks for gross() and never computes it
  the two rates could become a table from a database
  and not one line of the caller would change

_basic has one leading underscore. In Python that is a convention and not a lock: it means "this is not part of what I promise, do not touch it". Nothing stops a caller from writing e._basic = 0, and the underscore tells them that if they do, and it breaks later, that is their fault. Java would write private; Python writes an underscore and trusts you.

The caller never computes the gross pay. It asks. So when the allowance rule changes, and in India it changes every few years, one class changes and nothing else does. Had the caller been computing basic * 1.30 itself, in eleven places, the change would be eleven edits and one of them would be missed.

raise_by enforces a rule that an int cannot. A plain number for the basic pay would happily take a negative raise. The ADT refuses it.

Those three paragraphs are the answer to "what is the advantage of an abstract data type", and they are worth four marks:

1. Encapsulation. The data and the operations on it are in one place, so a rule is written

once.

1. Information hiding. The representation is private, so it can change without breaking

callers.

1. A validated state. The type can refuse a value that makes no sense, which a primitive

cannot.

1. Reuse. The type can be used anywhere without being re-understood.

Procedure

1. Write the three Students. Run it, then change the order of the tuple's fields and note that

student_tuple[1] now gives the wrong thing with no error.

1. Add a passed() method to the class that returns True when every mark is 40 or more.
2. Write the Library. Run it and check all four error messages appear.
3. Remove the hasattr check from update, call lib.update(isbn, copyes=9), and print the

catalogue. Nothing complains and nothing changed.

1. Replace the dictionary in Library with a list of Books and rewrite read to search it.

Confirm that no code outside the class changes.

1. Write the Employee. Change HRA_RATE to 0.25 and note that only one line moved.
2. Try e._basic = -100 and then e.gross(). The underscore is a convention, not a lock.

Result

The abstract data types Student, Book and Employee were modelled as classes. The Student was built as a tuple, a dictionary and a class and the three compared: only the class can name its fields, carry its own operations and enforce a rule. A Library of Books implemented create, read, update and delete over a collection, with five failure cases each raising the appropriate exception, and the representation inside it was shown to be replaceable without changing a line outside. The Employee showed the three benefits of abstraction: the allowance rule is written once, the representation is hidden behind an underscore, and a negative raise is refused.

Where marks are lost

• Saying an ADT is a class. A class is one way of implementing one. The ADT is the description

of the operations and their meanings.

• Not distinguishing the ADT from the data structure. A Stack is an ADT; an array is a data

structure; a Stack over an array is one implementation.

• Only the data, with no operations. A class with __init__ and nothing else is a record, not

an ADT.

• No validation. The whole answer to "why not just use an int" is that a type of your own can

refuse a wrong value.

• Returning None from a failed create or delete instead of raising.
• Using KeyError and ValueError interchangeably. Not present is a KeyError; present and

wrong is a ValueError.

• No __repr__, so the examiner sees a list of memory addresses.
• Writing update so that a misspelled field silently creates a new one.

For the journal

Write the aim, MU's own wording, and the definitions of abstract data type and data structure in your own words, because the first question is always one of those. Then the Student three ways with its output, and one sentence on which you would use and why. Then the Library program in full with its run, including the four error lines, because the failure cases are what distinguish a complete answer. Then the Employee and the four advantages of abstraction as a list. The conclusion: an ADT declares what a type does and hides how it does it, which is what lets the representation change and what lets the type enforce rules a primitive cannot.

Quick revision

• An abstract data type is the values and the operations, with the implementation unspecified.

A data structure is a way of laying the values out. One ADT, many structures.

• Primitive types come from the language, hold one value, and cannot enforce a rule. An ADT is

yours, holds several values and behaviour, and can.

• Tuple: small, ordered, immutable, unnamed fields. Dictionary: named keys, no rules, no

behaviour. Class: named fields, its own operations, and it can refuse a bad value.

• CRUD is create, read, update, delete, and they belong to a collection, not to one object.
• A failed operation raises. KeyError for not present, ValueError for present and wrong.
• update checks with hasattr that the field exists, or a misspelling silently adds a new one.
• A leading underscore means "not part of the promise". It is a convention, not a lock.
• __repr__ for a readable printout, __len__ so that len() and truthiness work.
• The four advantages: encapsulation, information hiding, a validated state, and reuse.
• The Library's catalogue is a dictionary, and could be a list or a hash table, and no caller

would know. That is abstraction in one sentence.

Questions you should be able to answer

1. Define an abstract data type. A description of a type by the values it can hold and the operations on it, with what each operation takes, gives and requires, and with nothing said about how the values are stored.

2. What is the difference between an ADT and a data structure? The ADT is the contract: what the operations are and what they mean. The data structure is the implementation: how the values are laid out in memory. One ADT can be implemented by several structures.

3. Give three differences between a primitive type and an abstract data type. A primitive comes from the language and an ADT from you; a primitive holds one value and an ADT holds several plus behaviour; a primitive cannot refuse a meaningless value and an ADT can.

4. Why model a Student as a class rather than a dictionary? Because the class names its fields, so a misspelling is an error rather than a new key; it carries its own operations, so the total and the grade are written once; and it can enforce rules, such as refusing a negative mark.

5. What are the four basic operations on a collection, and why do they not belong to one object? Create, read, update and delete. One Book cannot be created or deleted; the catalogue that holds it can.

6. lib.update(isbn, copyes=5) is called by mistake. What should happen, and what happens without a guard? It should raise a KeyError naming the unknown field. Without the hasattr guard it adds a new attribute called copyes, changes nothing that matters, and reports no error.

7. What does a single leading underscore on an attribute mean in Python? That it is not part of the class's promise and a caller should not use it. It is a convention: nothing prevents access, and a caller who relies on it has no complaint when it changes.

8. The Library keeps its books in a dictionary. What would change if it kept them in a list? Inside the class, read would have to search, so it would go from one step to O(n). Outside the class, nothing at all. That is what information hiding means.

9. Name the four advantages of using an abstract data type. Encapsulation, so the data and its operations are together; information hiding, so the representation can change; a validated state, so a meaningless value can be refused; and reuse, because the type can be used without being re-understood.