CSC5101 – Advanced Programming of Multicore Architectures

Portail informatique

Lock algorithms

This lab has the goal of measuring the performance of the basic lock algorithms: the spinlock, the ticket lock, the MC lock and the POSIX lock.

The benchmark

In this exercise, we implement the benchmark.

Arguments

Start to write an application that takes as arguments:

  • a number n of threads (an integer),
  • a number it of iteration executed by each thread (an integer),
  • a critical section delay csd (an integer),
  • a compute delay dscd (an integer),
  • a lock algorithm algo (an array of caracters).

The threads

Create the threads and waits for their termination in the main function. Each thread has to execute the function benchmark, which executes it iterations of a loop that:

  • Take a POSIX lock,
  • Waits csd nano-seconds,
  • Release a POSIX lock,
  • Waits cs nano-seconds.

In order to wait, you can use the clock_gettime function with the CLOCK_MONOTONIC mode.

Reporting

At the end of the application, reports the time taken to acquire and release a lock.

Lock algorithms

Instead of taken a POSIX lock, we want to specify the lock algorithm used in the application as an argument. We consider that these algorithms are correct:

  • none: don't take a lock, it's just to check that your application report correct values,
  • posix: take a POSIX lock, as you have done in the previous question,
  • spinlock: take a spinlock,
  • ticket: take a ticket lock,
  • mcs: take a MCS lock.

Implementing at least one of the algorithm is mandatory (spinlock, ticket or mcs). Implementing the three algorithms is interesting to compare them.

The POSIX lock implementation (optional)

Now, we want to implement our own POSIX lock. For that purpose, we have to use the futex system call provided by a Linux kernel. A thread can call this function either to wait for a variable modification (a lock release) or to wakeup the threads that wait for a variable modification.

Since the futex API is not exposed by the system library, you can copy paste the following code in your application to have an access to the futex function:

At high level, the pthread_mutex_lock should first try to atomically change the lock value from BUSY to FREE. If the lock is already taken, the thread should wait with a futex, which, contrarily to the previous algorithms, release the processor. For that reason, we say the a POSIX lock passively waits for the lock, while for the other algorithms, we say that they actively wait for the lock.

In pthread_mutex_unlock, if a thread is waiting for the lock, don't forget to use the futex function.

You can download the Makefile here. You also have to download the three files.

The POSIX cond implementation (optional)

By using the futex API, try to implement the condition variable.