OS Lab 5 - Threads. Mutexes
In the last lab, we created new processes with fork(2), and each of them had a single task. In this lab, we will give one process several tasks, its threads, which share its memory. We will create them with pthread_create(3), wait for them with pthread_join(3), and protect the data they share with mutexes. We will also see what these functions ask of the kernel: clone(2) and futex(2). As an application, we will simulate a small bank.
Learning objectives
By the end of this lab you should be able to:
- create threads with
pthread_create(3), and wait for them withpthread_join(3); - explain which
clone(2)flags make a new task a thread of the same process; - recognize a race on shared data, and fix it with a mutex;
- explain how a mutex uses
futex(2), and why an uncontended lock needs no system call; - recognize a deadlock, and avoid it by always locking in the same order.
Threads
A thread is a task which shares memory with other tasks in a task group (process). All the threads of a process run the same program and see the same global variables and heap, but each has its own registers and its own stack, so each can be at a different point of the program, in a different function.
On Linux, threads are created and managed with the POSIX threads (pthreads) functions, which are part of glibc.
pthread_create(3)
// In: <pthread.h>
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
void *(*start_routine)(void *), void *arg);
| Parameter | Description |
|---|---|
thread |
Where to store the ID of the new thread, used later to wait for it |
attr |
Options, such as the size of the stack, or nullptr for the defaults
|
start_routine |
The function the new thread runs. When it returns, the thread ends |
arg |
The argument passed to start_routine
|
The new thread starts running start_routine(arg), while the thread that created it continues after pthread_create(3). Both arg and the return value of start_routine are void *, so a thread can be given, and can give back, a pointer to anything.
errno. They return 0 on success, or the error number itself (for example, EAGAIN) on error. The examples below use a print_error() which takes that number as a parameter.The following program starts three threads, gives each one its own number, and each of them prints its PID and its TID (thread ID), the ID of the task:
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <pthread.h>
5#include <unistd.h>
6
7#define N_THREADS 3
8
9static void print_error(const char *what, int err)
10{
11 char msg[256];
12 snprintf(msg, sizeof msg, "%s: %s\n", what, strerror(err));
13 write(STDERR_FILENO, msg, strlen(msg));
14}
15
16static void *worker(void *arg)
17{
18 int id = *(int *) arg;
19 char msg[256];
20 snprintf(msg, sizeof msg, "thread %d: PID %d, TID %d\n", id, getpid(), gettid());
21 write(STDOUT_FILENO, msg, strlen(msg));
22 return nullptr;
23}
24
25int main(void)
26{
27 pthread_t threads[N_THREADS];
28 int ids[N_THREADS];
29
30 for (int i = 0; i < N_THREADS; i++) {
31 ids[i] = i;
32 int err = pthread_create(&threads[i], nullptr, worker, &ids[i]);
33 if (err != 0) {
34 print_error("pthread_create", err);
35 return EXIT_FAILURE;
36 }
37 }
38
39 for (int i = 0; i < N_THREADS; i++) {
40 pthread_join(threads[i], nullptr);
41 }
42
43 char msg[256];
44 snprintf(msg, sizeof msg, "main: PID %d, TID %d\n", getpid(), gettid());
45 write(STDOUT_FILENO, msg, strlen(msg));
46 return EXIT_SUCCESS;
47}
$ ./build/debug/app
thread 0: PID 4307, TID 4308
thread 1: PID 4307, TID 4309
thread 2: PID 4307, TID 4310
main: PID 4307, TID 4307
All the threads have the same PID: they are one process. Each has its own TID, and the first thread of the process, the one which runs main(), has a TID equal to the PID. The three lines may come in any order: the threads run independently.
ids. Passing &i instead would be a bug: all the threads would get a pointer to the same variable, which the loop keeps changing, leading to a race condition on access.pthread_join(3)
// In: <pthread.h>
int pthread_join(pthread_t thread, void **retval);
pthread_join(3) waits for a thread to end, the way waitpid(2) waits for a child process. If retval is not nullptr, it stores there the value returned by the thread's function.
A simpler way to get results back is to give each thread a structure, with both its input and a place for its output. The following program adds up the numbers from 0 to 99,999,999 with four threads, each adding a quarter of them:
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <pthread.h>
5#include <unistd.h>
6
7#define N_THREADS 4
8#define N 100000000
9
10static void print_error(const char *what, int err)
11{
12 char msg[256];
13 snprintf(msg, sizeof msg, "%s: %s\n", what, strerror(err));
14 write(STDERR_FILENO, msg, strlen(msg));
15}
16
17// What one thread works on: its input, and a place for its result.
18struct part {
19 long from, to; // Add the numbers in [from, to)
20 long sum;
21};
22
23static void *add_range(void *arg)
24{
25 struct part *p = arg;
26 p->sum = 0;
27 for (long i = p->from; i < p->to; i++) {
28 p->sum += i;
29 }
30 return nullptr;
31}
32
33int main(void)
34{
35 pthread_t threads[N_THREADS];
36 struct part parts[N_THREADS];
37
38 for (int i = 0; i < N_THREADS; i++) {
39 parts[i].from = (long) N / N_THREADS * i;
40 parts[i].to = (long) N / N_THREADS * (i + 1);
41 int err = pthread_create(&threads[i], nullptr, add_range, &parts[i]);
42 if (err != 0) {
43 print_error("pthread_create", err);
44 return EXIT_FAILURE;
45 }
46 }
47
48 long sum = 0;
49 for (int i = 0; i < N_THREADS; i++) {
50 pthread_join(threads[i], nullptr);
51 sum += parts[i].sum;
52 }
53
54 char msg[256];
55 snprintf(msg, sizeof msg, "sum of 0..%d: %ld\n", N - 1, sum);
56 write(STDOUT_FILENO, msg, strlen(msg));
57 return EXIT_SUCCESS;
58}
$ ./build/debug/app
sum of 0..99999999: 4999999950000000
Each thread writes only to its own struct part, and main() reads it only after pthread_join(3), when the thread has ended. The threads never touch the same data at the same time, so nothing more is needed in this case.
main(), or calling exit(3) from any thread, ends the whole process, with all its threads (it uses the exit_group system call). To end only the calling thread, return from its function, or call pthread_exit(3). This is why main() must join the threads before it returns.Under the hood: clone(2)
pthread_create(3) creates the new task with the clone(2) system call, the same one fork(2) uses. The difference is in the flags, which say what the new task shares with the one that created it:
| Flag | The new task shares |
|---|---|
CLONE_VM |
The memory: the code, the global variables, the heap, and the stacks of the other threads |
CLONE_FILES |
The file descriptor table: a file opened by one thread can be used by all of them |
CLONE_SIGHAND |
The signal handlers |
CLONE_THREAD |
The process: the new task gets a new TID, but the same PID, and is not a child to be waited for with waitpid(2)
|
fork(2) calls clone(2) with none of these, so the child gets a copy of everything instead. Since the memory is shared, the new thread cannot use the stack of the thread which created it. Before calling clone(2), glibc allocates a new stack (8 MiB by default) with mmap(2), and gives its address to clone(2).
Races
Since threads share their memory, two threads can change the same variable at the same time. The following program starts two threads, and each of them increments a global counter one million times:
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <pthread.h>
5#include <unistd.h>
6
7#define N 1000000
8
9static long counter = 0;
10
11static void *increment(void *arg)
12{
13 (void) arg;
14 for (int i = 0; i < N; i++) {
15 counter++;
16 }
17 return nullptr;
18}
19
20int main(void)
21{
22 pthread_t a, b;
23 pthread_create(&a, nullptr, increment, nullptr);
24 pthread_create(&b, nullptr, increment, nullptr);
25 pthread_join(a, nullptr);
26 pthread_join(b, nullptr);
27
28 char msg[256];
29 snprintf(msg, sizeof msg, "counter = %ld (expected %d)\n", counter, 2 * N);
30 write(STDOUT_FILENO, msg, strlen(msg));
31 return EXIT_SUCCESS;
32}
$ ./build/debug/app
counter = 1018661 (expected 2000000)
$ ./build/debug/app
counter = 1008721 (expected 2000000)
The result is wrong, and different every time. counter++ looks like a single operation, but the processor does it in three steps: load the value from memory into a register, add 1 to the register, and store the register back to memory. When two threads do these steps at the same time, they can both load the same value, and one of the increments is lost.
This is a race: the result depends on how the steps of the threads happen to interleave. A part of the program which uses shared data, and must not be run by two threads at the same time, is called a critical section.
Mutexes
A mutex (mutual exclusion) is a lock which only one thread can hold at a time. A thread locks the mutex before the critical section, and unlocks it after. If another thread already holds it, pthread_mutex_lock(3) waits until it is unlocked.
// In: <pthread.h>
int pthread_mutex_init(pthread_mutex_t *m, const pthread_mutexattr_t *attr);
int pthread_mutex_lock(pthread_mutex_t *m);
int pthread_mutex_unlock(pthread_mutex_t *m);
int pthread_mutex_destroy(pthread_mutex_t *m);
A mutex must be set up with pthread_mutex_init(3) before it is used, usually before the threads which use it are created. attr can choose other kinds of mutexes, or be nullptr for a normal one, which starts unlocked. When the mutex is no longer needed, pthread_mutex_destroy(3) frees anything the mutex may hold.
To fix the counter, we add a mutex, and lock it around the increment:
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <pthread.h>
5#include <unistd.h>
6
7#define N 1000000
8
9static long counter = 0;
10static pthread_mutex_t lock;
11
12static void *increment(void *arg)
13{
14 (void) arg;
15 for (int i = 0; i < N; i++) {
16 pthread_mutex_lock(&lock);
17 counter++;
18 pthread_mutex_unlock(&lock);
19 }
20 return nullptr;
21}
22
23int main(void)
24{
25 pthread_mutex_init(&lock, nullptr);
26
27 pthread_t a, b;
28 pthread_create(&a, nullptr, increment, nullptr);
29 pthread_create(&b, nullptr, increment, nullptr);
30 pthread_join(a, nullptr);
31 pthread_join(b, nullptr);
32
33 pthread_mutex_destroy(&lock);
34
35 char msg[256];
36 snprintf(msg, sizeof msg, "counter = %ld (expected %d)\n", counter, 2 * N);
37 write(STDOUT_FILENO, msg, strlen(msg));
38 return EXIT_SUCCESS;
39}
$ ./build/debug/app
counter = 2000000 (expected 2000000)
The result is now correct, but locking has a cost: on our machine, the program became as much as 100 times slower. Every increment now also locks and unlocks the mutex, and while one thread holds it, the other has to wait. Critical sections should be kept as short as possible.
Under the hood: futex(2)
A pthread_mutex_t is, at its core, just an integer in the memory of the process. glibc uses three values:
| Value | Meaning |
|---|---|
| 0 | Unlocked |
| 1 | Locked, and no other thread is waiting |
| 2 | Locked, and other threads may be waiting |
The processor has atomic instructions, which read and change a value in memory in a single step, so that no other thread can come in between. C provides them in <stdatomic.h>:
// In: <stdatomic.h>. A is an atomic type, such as _Atomic uint32_t, and C the plain one, uint32_t.
// If *obj == *expected, sets *obj to desired and returns true.
// Otherwise, copies *obj into *expected and returns false.
bool atomic_compare_exchange_strong(volatile A *obj, C *expected, C desired);
// Sets *obj to desired, and returns its old value.
C atomic_exchange(volatile A *obj, C desired);
Locking a free mutex is a single atomic instruction, which changes it from 0 to 1. This is the fast path, and it needs no system call. The kernel is only needed when a thread has to wait, since only the kernel can put a thread to sleep and wake it up. For this, Linux provides the futex(2) (fast user-space mutex) system call:
// In: <linux/futex.h> and <sys/syscall.h>. glibc has no wrapper for it.
long syscall(SYS_futex, uint32_t *addr, int op, uint32_t val, ...);
op |
What the kernel does |
|---|---|
FUTEX_WAIT |
If *addr is still equal to val, puts the thread to sleep, until another thread wakes it. Otherwise, returns right away
|
FUTEX_WAKE |
Wakes up to val threads sleeping on addr
|
For the threads of a single process, the FUTEX_WAIT_PRIVATE and FUTEX_WAKE_PRIVATE versions are a little faster. The kernel does not know anything about mutexes: it only keeps a list of sleeping threads for each address. Using the three values above:
- lock: try to change the mutex from 0 to 1. If that worked, we hold it. Otherwise, set it to 2, to say that someone is waiting, and call
FUTEX_WAITwith 2. When woken, try again. - unlock: set the mutex to 0. If it was 2, someone may be waiting, so call
FUTEX_WAKEto wake one of them.
The check done by FUTEX_WAIT is what makes this work: if the mutex was unlocked between our failed attempt and the system call, the value is no longer 2, and the thread does not go to sleep waiting for a wake-up which already happened.
pthread_join(3) also uses futex(2). When pthread_create(3) calls clone(2), it asks the kernel (with CLONE_CHILD_CLEARTID) to set a variable holding the TID of the thread to 0 when the thread ends, and to do a FUTEX_WAKE on it. pthread_join(3) waits on that variable with FUTEX_WAIT.Deadlock
A program may need to hold several mutexes at once. If thread A locks mutex 5 and then waits for mutex 7, while thread B has locked mutex 7 and waits for mutex 5, neither of them can ever continue. This is a deadlock. The program does not crash, it just stops, using no CPU time at all.
The simplest way to avoid it is to always take the mutexes in the same order, for example in increasing order of their number. Then no thread can hold a mutex while waiting for one that comes before it, so the threads can never wait for each other in a circle.
Exercises
Write the program in a new copy of the project template. As a reminder from the first lab:
mkdir -p ~/oslab && cd ~/oslab
curl -OL https://wiki.dcae.pub.ro/images/9/93/Os_lab_skeleton.zip
unzip -d lab05 Os_lab_skeleton.zip
For this lab:
- As in the last labs, do not use the standard I/O library for output: build the text with
snprintf(3)andwrite(2)it. - Check the value returned by
pthread_create(3), and remember that it is an error number, not -1. - Use
time ./build/debug/appto measure how long the program runs.
Bank transfers
A bank has 100 accounts, each starting with 1000. 8 threads, the tellers, each make 1,000,000 random transfers between the accounts. Money only moves from one account to another, so at the end, the total must still be 100,000.
#define N_ACCOUNTS 100
#define N_THREADS 8
#define N_TRANSFERS 1000000
#define INITIAL_BALANCE 1000
struct account {
pthread_mutex_t lock; // Not used until step 3
int balance;
};
static struct account accounts[N_ACCOUNTS];
Each transfer picks two different accounts, from and to, and an amount between 1 and 100. If from has enough money, the amount moves from from to to. Otherwise, nothing happens. Use rand_r(3) for the random numbers, with a different seed for each thread: rand(3) keeps its state in a global variable, shared by all the threads.
- No locks. Write the tellers, and print the total after joining them. Run the program a few times: what happens to the total?
- One mutex for the whole bank. Lock a single global mutex around each transfer. The total is now correct. How long does the program take? Why is the
systime so large? - One mutex per account. Instead of the global mutex, lock
accounts[from].lock, thenaccounts[to].lock, do the transfer, and unlock them. Run the program: it will probably never end (Ctrl+C stops it). Explain why, in a comment. - Lock ordering. Fix step 3 by always locking the account with the lower number first. The total must be correct, and the program should now be faster than in step 2. Why?
$ ./build/debug/app
total: 766978 (expected 100000)
$ ./build/debug/app
total: 751625 (expected 100000)
$ time ./build/debug/app
total: 100000 (expected 100000)
real 0m0.304s
user 0m0.427s
sys 0m0.081s
The first output is from step 1, and the second from step 4. The times depend on the machine, but step 4 should be clearly faster than step 2.
Bonus: Write your own mutex, on top of futex(2), as described in the futex section:
typedef _Atomic uint32_t mutex_t; // 0, 1 or 2, as above
void mutex_lock(mutex_t *m);
void mutex_unlock(mutex_t *m);
Use it instead of pthread_mutex_t in step 4. The total must still be correct, and the time should be close to that of step 4.
Extra: Add an auditor thread, which checks the bank while the tellers work. Every 50 ms (nanosleep(2)), it locks all the accounts, adds up their balances, unlocks them, and prints the total, which must always be 100,000. When the tellers are done, main() tells the auditor to stop through a global atomic_bool (from <stdatomic.h>): a variable which one thread writes while another reads it must be atomic.
$ ./build/debug/app
audit: 100000
audit: 100000
audit: 100000
audit: 100000
audit: 100000
audit: 100000
total: 100000 (expected 100000)
- In which order must the auditor lock the accounts?
- Why must it hold all the locks at once? Try locking, reading and unlocking one account at a time instead: what totals do you get, and why?
