rakuco / peterson_futex Goto Github PK

peterson_futex
==============
Copyright (c) 2009  Raphael Kubo da Costa <[email protected]>

------------
Introduction
------------
A generalization of Peterson's mutual exclusion algorithm for N threads using futexes. For more information on Peterson's algorithm, see <http://en.wikipedia.org/wiki/Peterson's_algorithm>. For information on futexes, see <http://en.wikipedia.org/wiki/Futex>.

This implementation was created as an assignment in a course on Operating Systems at State University of Campinas, Brazil.

This program is free software and is licensed under the 2-clause BSD license.

----------
Assignment
----------
The assignment that motivated the creation of this program is available in Portuguese at <http://www.ic.unicamp.br/~islene/mc514/lab2/lab2.html>. This is subject to change, so the reader is encouraged to check <http://www.ic.unicamp.br/~islene> and look for the second assignment in 2009s1.

--------
Building
--------
The program requires Futexes, which have been implemented on Linux since the 2.6 kernel came into being. So it requires a 2.6+ kernel to compile and run. The thread manipulation code requires pthreads.

The program has only been (not so extensively) tested on Linux, under a 2.6+ kernel with NPTL.
 
Requirements
  The program only requires the GNU libc (with POSIX threads support) and a 2.6+ Linux kernel.
  If you intend to generate the documentation for the project, you need doxygen and graphviz.
 
Compilation
  To compile the program you just need to run 'make'.
  To generate the documentation, you need to run 'make doc'.

-----
Usage
-----
The program must be invoked from command line and requires a single parameter: the number of threads that shall be created.
 
Example:
  camp 7

This should create 7 threads and make them compete for the critical region.

-------------------------
Implementation discussion
-------------------------
The reader is supposed to be familiar with Peterson's algorithm for mutual exclusion in multithreaded code.

This algorithm is valid for 2 threads and uses busy waiting to prevent one thread from accessing a critical region while the other is inside it.

This program has two main purposes: generalize the algorithm to N threads and replace the busy waiting code with futexes ("fast userspace mutexes"), so that we don't waste CPU cycles on a loop.

To replace the busy waiting loop with futex calls, the following code is used:

  Original Peterson's algorithm
  *****************************
  Thread 0:
    interested[0] = 1;
    turn = 0;
    while (turn == 0 && interested[1]);
    /* Access the critical region */
    interested[0] = 0;

  Thread 1:
    interested[1] = 1;
    turn = 1;
    while (turn == 1 && interested[0]);
    /* Access the critical region */
    interested[1] = 0;

  Futex
  *****
  Thread 0:
    interested[0] = 1;
    turn = 0;
    futex_wake(&turn, 1);
    while ((interested[1]) && (!futex_wait(&turn, 0)));
    /* Access the critical region */
    interested[0] = 0;
    futex_wake(&turn, INT_MAX);

  Thread 1:
    interested[1] = 1;
    turn = 1;
    futex_wake(&turn, 1);
    while ((interested[0]) && (!futex_wait(&turn, 1)));
    /* Access the critical region */
    interested[1] = 0;
    futex_wake(&turn, 1);

Where futex_wait and futex_wait are just wrappers around syscall(SYS_futex, addr, FUTEX_WAIT/FUTEX_WAKE, val, NULL, NULL, 0).

In order to generalize the algorithm, the problem must be broken into various instances of the original 2-threads problem. Then there is a tree structure, where initially the threads compete with their sibling (if it's the nth thread, n being odd, it competes with its left sibling; otherwise, it competes with its right sibling).

The winner of the match goes up one level in the tree and competes with the winner of the match next to it, so on and so forth until it goes to the topmost level and can access the critical region.

To represent this tree and its levels the ThreadTree and ThreadLevel structures were used.

Given an initial number of threads, the total number of levels necessary to arrive at 2 threads is obtained by dividing the number of threads by 2 until it reaches 0. In each level, a ThreadLevel structure is allocated with the number of threads that compete in that level. If the number is odd, an additional position is allocated so that the matches occur normally.

In each level, there is an array turn and an array interested. The array interested has a number of positions equal to the number of threads in that level (ThreadLevel::n_elem) and is used by the threads interested in accessing the critical region so that they can mark they're interested. The array turn has half the number of threads in that level, since it's used by two threads and indicates whose turn it is in that competition.

The algorithm in f_thread uses the function enter_critical to try to ascend all levels in the competition. If the adversary thread has already run that path, the current thread will block until the other finishes accessing the critical region.

-------------
camp_errado.c
-------------
camp_errado.c is a wrong implementation of the solution as required by the assignment. In this case, access to the critical region is not always locked to a single thread a time.

This way, it is possible that something like "Thread 1, s = 2" happens.