Implementing a Mutex

README.md

Implementing a Mutex

Use the following commands to compile and link the examples:

$ gcc -std=c17 -pedantic-errors -O0 -g -S mutex.c
$ as --gstabs -o mutex.o mutex.s 
$ gcc -o mutex mutex.o -lpthread

This implementation makes use of the C11 Atomic Operations Library.

Mutexes

A mutex is a mutual exclusion lock m that is accessed only through two standard atomic operations:

• acquire(m) -- blocks while m is locked, then locks m; and
• release(m) -- unlocks m.

A mutex can be used to protect a critical section.

Locking

Consider the following line for acquiring the mutex / lock:

#define acquire(m) while (atomic_flag_test_and_set(m))

The atomic_flag_test_and_set function checks the flag value. If the value is false, then it sets the flag to true (i.e., locks the mutex). In all cases, it returns the previous value of the flag. This function is guaranteed to be atomic by <stdatomic.h>.

Therefore, the only way the while loop can break is if the flag is false (i.e., the mutex is unlocked) before the call to atomic_flag_test_and_set. Otherwise, the code will spin / busy wait until it encounters the mutex in an unlocked state. Atomicity is important here because we do not want another thread or process to acquire the lock in-between the comparison and the potential setting of the new flag value as this would mean the mutex was acquired by some other thread during that time. This atomic operation is an example of a compare-and-swap (CAS).

Mutexes in Pthreads

Pthreads comes with its own mutex implementation. You can drop it in to this example using the following:

pthread_mutex_t mut;
#define acquire(m) pthread_mutex_lock(m)
#define release(m) pthread_mutex_unlock(m)

See pthread_mutex_lock(3p) for more details.

Our Implementation

Our implementation is not limited to Pthreads. It can be used to synchronize between processes so long as the mut_t (our atomic_flag) is at an address that maps to a shared memory object.

mutex.c

#include <pthread.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdatomic.h>

#define PING "ping"
#define PONG "pong"

void critical(const char * str) {
  size_t len = strlen(str);
  for (size_t i = 0; i < len; ++i) {
    printf("%c", str[i]);
  } // for
  printf("\n");
} // str

typedef atomic_flag mut_t;
volatile mut_t mut = ATOMIC_FLAG_INIT; // false; true = locked; false = unlocked

// void acquire(mut_t * m)
#define acquire(m) while (atomic_flag_test_and_set(m))
// void release(mut_t * m)
#define release(m) atomic_flag_clear(m)

void * pingpong(void * p) {
  char * msg = (char *) p;
  for (;;) {
    acquire(&mut);
    critical(msg);
    release(&mut);
  } // for 
} // pingpong

int main() {
  setvbuf(stdout, NULL, _IONBF, 0);
  pthread_t ping;
  pthread_t pong;
  pthread_create(&ping, NULL, pingpong, PING);
  pthread_create(&pong, NULL, pingpong, PONG);
  for(;;);
  return 0;
} // main

@UserSupra, it's both! A mutex is an abstract data type (ADT) for a lock (i.e., a Boolean flag) that enforces a mutual exclusion access policy via its acquire and release operations. A spinlock is one way to implement a busy-waiting mutex. Other implementations also exist. For example, an operating system or thread library might provide a mutex acquire implementation that blocks by suspending the calling process or thread while the mutex is locked -- instead of letting the caller waste CPU time spinning, it doesn't use any CPU time again until the mutex is unlocked. In practice, adaptive implementations are used that switch between busy-waiting and suspension depending on factors like priority, context switch time, etc.