Concurrent Programming
Threads that wait for each other: by spinning, with semaphores, with monitors, and finally inside a thread library of our own.
10Course grade
User-level threads
A thread library with its own preemptive scheduler
A thread library that runs many threads inside one ordinary process, with its own scheduler instead of the operating system’s. A timer interrupts the running thread, so no thread can keep the processor to itself.
Monitors
The same problems, with monitors
What it is
The same problems again, solved with monitors: one lock around shared state, and condition variables to wait on inside it. The prime-checking pool was also written in Java.
Each solution came with an argument for why it is correct, not only tests, because monitors don’t all behave alike.
Correct under any monitor
When one thread signals another, which runs first? In a signal-and-block monitor the woken thread runs at once; in signal-and-continue the signaller carries on. Some monitors also let a new thread slip in ahead of the woken one.
We wrote every solution to be right under all of them: each function signals only as its last step, and counters of waiting threads keep a newcomer from cutting in.
A semaphore from a monitor
Our binary semaphore again, now as a monitor: down lowers the value and waits if it went below zero; up raises it and wakes one waiting thread if any are left. An up when it is already 1 is still lost.
The worker pool
Two versions. In the first, the main thread hands each number to a sleeping worker and waits until it is taken. In the second, the main thread adds jobs to a queue and never waits: a worker takes the next job, or sleeps until there is one.
The bridge and the roller coaster
The bridge keeps one colour on it at a time, at most a set number of cars, and a limit on how many of one colour cross while the other waits. A car leaving decides who goes next: another of its colour, the other colour once the last car is off, or nobody, freeing the bridge.
The roller coaster’s train fills, rides and empties, with passengers waiting to board and waiting to get off.

Code
if (bridge == NOT_ASSIGNED) {
printf("%d, %c: # ENTERING # I was first on bridge! Claiming bridge...\n", id, team ? 'b' : 'r');
monitor->bridge = team;
// If the bridge is taken by another color or full (or another car is waking up)
} else if (bridge != team || *on_bridge == N || *cars_waiting > 0) {
printf("%d, %c: # ENTERING # Bridge is either full or different color! Waiting...\n", id, team ? 'b' : 'r');
(*cars_waiting)++;
pthread_cond_wait(queue, &monitor->lock);
(*cars_waiting)--;
}
// Logistics
(*on_bridge)++;
(*total_cars)++;
int opposite_cars_waiting = monitor->cars_waiting[!team];
// If another car of my color is waiting and can fit in the bridge without violating the total limit of
// cars of a certain color that can pass at once
if (*on_bridge < N && *cars_waiting > 0 && (*total_cars < TOTAL_LIMIT || !opposite_cars_waiting)) {
printf("%d, %c: # ENTERING # Waking another car from my color...\n", id, team ? 'b' : 'r');
pthread_cond_signal(queue);
}Semaphores
Bridge and roller-coaster problems
What it is
Our own semaphores, built on the ones Linux provides, then used to solve three classic problems: a pool of workers, a narrow bridge and a roller coaster. Threads now sleep while they wait instead of looping.
A binary semaphore
Our semaphore is binary: 0 or 1. An up when it is already 1 is lost, and reported as such. Each one keeps its value next to a Linux System V semaphore that does the blocking, with a lock around the value.
The order matters. A down that is about to block must let go of the lock before it blocks; otherwise no up could ever get in to wake it, and every thread using that semaphore would be stuck.
A pool of workers
The same prime-checking pool, now with two semaphores: workers sleep on a queue until the main thread lets one through, and the main thread sleeps until that worker says it has taken the number.
A narrow bridge
Cars come from both sides of a bridge that fits a few at a time and carries traffic one way at a time. The first car of a group claims the bridge for its side, the cars behind it follow while there is room, and the last one off hands the bridge back.
A roller coaster
Passengers queue for a train that leaves only when full. The last passenger to arrive wakes the train; the train lets passengers board one by one, waits for each, rides, and leaves again once enough are waiting.
Code
int mysem_down(mysem_t *s) {
if (mysem_get(s) == -1)
return -1;
struct sembuf op; op.sem_num = 0; op.sem_op = -1; op.sem_flg = 0;
//Using lock for mutual exclusion
pthread_mutex_lock(&s->lock);
--s->val;
if (s->val == 0) {
semop(s->id, &op, 1);
pthread_mutex_unlock(&s->lock);
return 1;
}
pthread_mutex_unlock(&s->lock);
semop(s->id, &op, 1);
return 1;
}Busy-wait threads
Pipe, worker pool, merge sort
What it is
Three small programs with POSIX threads, coordinated only by shared variables that threads check over and over in a loop, known as busy waiting. No locks to sleep on yet: the point was to see what it takes to get the order right by hand, and what it costs.
A pipe between threads
A pipe that one thread writes bytes into and another reads them out of, in order. It is a ring buffer with a read position and a write position. A writer facing a full buffer loops until a reader frees a place; a reader facing an empty one loops until a byte arrives, or until the writer says it is done.
A pool of workers
The main thread reads numbers and hands each one to a free worker, which checks whether it is prime. Every worker has a state, available, working or finishing, and a command from the main thread: wait, check this number, or stop. Each side loops on the other’s variable until it changes.
The order of writes matters: a worker clears its command before it says it is working, so it never checks the same number twice and never overwrites a new command.
Sorting with threads
A merge sort over a file of integers. Each thread splits its part in two and starts a thread for each half, down to parts of 64 numbers or fewer, which are sorted in memory and written back. A parent loops until both children have finished, then merges their halves in the file.
Code
void *run_worker(void *arg) {
worker_t *self = arg;
while(1) {
self->state = AVAILABLE;
while (self->command == WAIT) {}
if (self->command == TERMINATE) {
self->state = TERMINATING;
break;
}
/*
Resetting the command of the master before setting the state of the worker
so that the worker doesn't repeat the processing of the same value
and the master doesn't get its command overwritten.
*/
self->command = WAIT;
self->state = WORKING;
printf("Worker #%d: %lld is %sprime\n", self->id, self->value_to_process, is_prime(self->value_to_process) ? "" : "not ");
}
return NULL;Tools
What this course's projects were built with. Pick one to see where else I used it.