Mutual exclusion

Mandatory assignment

In this assignment you will study different methods to enforce mutual exclusion.

Overview

File to use
module-4/mandatory/src/mutex.c
Description
In this program, a process creates a number of threads and waits for their termination. The threads are divided into two sets I and D. A shared variable which works as a counter is initialized to 0 and then incremented by the threads in set I and decremented by the threads in set D. The sum of all the increments is equal to the absolute value of the sum of all the decrements.
Example
There are five threads in set I, each incrementing the counter 20 times by 2. In total the counter will be incremented by 5*20*2 = 200. There are two threads in set D, each decrementing the counter 20 times by 5. In total the counter will be decremented by 2*20*5 = 200.
Desired behavior
When all threads are done executing the value of the shared counter should be 0 (the same as value it was initialized with).

Compile and run

In the terminal, navigate to the module-4/mandatory directory. Use make to compile the program.

$ make

The executable will be named mutex and placed in the bin sub directory. Run the program from the terminal.

$ ./bin/mutex

Questions

Run the program several times and study the provided source code.

  1. Does the program work according to the specification?
  2. Can you predict the output before execution? Why?

Identify the critical sections

Identify the critical sections in the program. The critical sections should be as small as possible.

Mutual exclusion

Your task is to make sure that at any time, at most one thread execute in a critical section, i.e., access to the critical sections should be mutual exclusive. You will use three different methods to ensure that updates to the shared counter variable appear to the system to occur instantaneously, i.e., make sure updates are atomic.

Method 1 - pthread mutex locks

The first option you will study is to use the mutex lock provided by the pthreads library to enforce mutual exclusion when accessing the shared counter variable. Add the needed synchronization in the functions inc_mutex and dec_mutex to make the program execute according to the desired behavior.

Reference

Method 2 - test and set

An alternative to mutex locks is to use the atomic test-and-set built-in provided by the GCC compiler to implement a spinlock.

At the beginning of mutex.c you find the following declaration.

/* Shared variable used to implement a spinlock */
volatile int lock = false;
  • Use the shared lock variable to implement the spin_lock() and spin_unlock() operations.
  • Change the functions inc_tas_spinlock and dec_tas_spinlock to use use the test-and-set spinlock to enforce mutual exclusion.

Reference

Method 3 - atomic addition and subtraction

A third option is to use the atomic addition and subtraction GCC built-ins. Change the functions inc_atomic and dec_atomic to use atomic addition and subtraction to make the program execute according to the desired behavior.

Reference

Evaluation

Observe the throughput of the three different approaches (operations per second).