Jason NikasLive FPGA Lab

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

CpthreadsBashGitJason NikasPanagiotis Nikolaos TsogkasThodoris Vangos
ready queueCPUrunningtimerpreempted, back of the queueCPU over timea timer tick at every cut

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

CpthreadsJavaBashGitJason NikasPanagiotis Nikolaos TsogkasThodoris Vangos

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.

The bridge as the monitor sees it: three red and three blue cars waiting at either end, the entry queue, a queue per colour, and counts of cars on the bridge, waiting and passed

Code

A car arriving at the bridge: it claims it, waits, or goes, then wakes the next car of its colour if there is room and it is still their turn. Lines 113–135 on GitHub
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);
}

Presentation and repository

  • PresentationGreek PDF, read in a new tabReadDownload
  • RepositoryGitHub, opens in a new tabOpen

Semaphores

Bridge and roller-coaster problems

CpthreadsBashGitJason NikasPanagiotis Nikolaos TsogkasThodoris Vangos

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

Down on our semaphore: the value is changed under a lock, and the lock is let go before the thread can block. Lines 69–86 on GitHub
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;
}

Presentation and repository

  • PresentationGreek PDF, read in a new tabReadDownload
  • RepositoryGitHub, opens in a new tabOpen

Busy-wait threads

Pipe, worker pool, merge sort

CpthreadsBashGitJason NikasPanagiotis Nikolaos TsogkasThodoris Vangos

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

A worker: it spins on its command until the main thread gives it a number, then reports whether it is prime. Lines 140–158 on GitHub
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;

Presentation and repository

  • PresentationGreek PDF, read in a new tabReadDownload
  • RepositoryGitHub, opens in a new tabOpen

Tools

What this course's projects were built with. Pick one to see where else I used it.

Tap the picture to see it at full size