Example of a race condition with and wihout locking (pthread or x86 TSL)

lab0.cpp

/*
 * =================================================
 * DAT320 Operating Systems, University of Stavanger
 *
 * LAB 0: PROTECTION AND THREADS
 * Written by Christian Stigen Larsen, 2012-08-24
 * =================================================
 *
 * ABOUT
 * -----
 *
 * The aim is to have several threads update a global counter.  Without
 * locking, this should lead to corrupted updates.  With locking, the value
 * should alway be updated correctly.
 *
 * We provide three options: No locking, locking with pthread, locking with
 * try-set-lock in x86 assembly using atomic operations
 *
 * To provoke a race condition, we spawn all the threads but have them wait
 * for a green light to start updating the global counter.  Our goal is to
 * illustrate bad updates.
 *
 * Bad updates happens because when a program updates a variable, it needs
 * to load it into a register, increment it and then store it back into
 * memory.  If two or more such substeps overlap by different threads, it
 * will lead to missed updates.
 *
 *
 * COMPILING THE PROGRAM
 * ---------------------
 *
 * To compile: g++ -Wall -lpthread -o lab0 lab0.cpp
 *
 * NOTE:  You may want to try compiling with -O0 to disable optimizations.
 *
 *
 * EXAMPLE OUTPUT
 * --------------
 *
 * $ time ./lab0 2000 0
 * DAT320 Operating Systems at University of Stavanger
 * Lab 0, by Christian Stigen Larsen
 *
 * Starting threads w/locking scheme: No lock
 * Joining threads
 * Protection misses: 4
 * FAIL
 *
 * real 0m0.626s
 * user 0m0.461s
 * sys  0m0.313s
 *
 * $ time ./lab0 2000 1
 * DAT320 Operating Systems at University of Stavanger
 * Lab 0, by Christian Stigen Larsen
 *
 * Starting threads w/locking scheme: pthread_mutex_lock
 * Joining threads
 * Protection misses: 0
 * OK
 *
 * real 0m0.608s
 * user 0m0.491s
 * sys  0m0.239s
 *
 * $ time ./lab0 2000 2
 * DAT320 Operating Systems at University of Stavanger
 * Lab 0, by Christian Stigen Larsen
 *
 * Starting threads w/locking scheme: x86 xchg instruction
 * Joining threads
 * Protection misses: 0
 * OK
 *
 * real 0m0.617s
 * user 0m0.452s
 * sys  0m0.312s
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <list>
#include <pthread.h>

/*
 * Settings and value to be modified.
 */
int count = 0;
int value = 0;
volatile bool idle_threads = true;

/*
 * Lock type and mutexes
 */
enum lock_type {LOCK_NONE=0, LOCK_OS=1, LOCK_X86=2};
int lock;

pthread_mutex_t os_mutex;
unsigned int x86_mutex;

std::list<pthread_t*> threads;

/*
 * Parse command line arguments.
 */
void parse_args(int argc, char** argv)
{
  if ( argc < 3 ) {
    printf(
      "USAGE: lab0 <threads> <lock>\n"
      "\n"
      "ARGUMENTS\n"
      "  <threads>  Number of threads to start, positive integer\n"
      "  <lock>     0 = Don't use any lock\n"
      "             1 = Use OS-specific lock\n"
      "             2 = Use x86 assembly lock\n"
      "\n"
      "Try running `lab0 10 0' first, then increase to, e.g. `lab0 1000 0'\n"
      "and run it many times to see various protection misses.  Then try\n"
      "running with a lock, e.g. `lab0 1000 1` or `lab0 1000 2`.\n"
      "\n");
    exit(1);
  }

  if ( !(sscanf(argv[1], "%d", &count) == 1 && count > 0) ) {
    printf("<threads> must be a positive integer: %s\n\n", argv[1]);
    exit(1);
  }

  if ( !(sscanf(argv[2], "%d", reinterpret_cast<int*>(&lock)) == 1 && (lock>=0 && lock<=2)) ) {
    printf("<lock> must be either of 0, 1, 2 or 3: %s\n\n", argv[2]);
    exit(1);
  }
}

/*
 * Try-set-lock (TSL).
 *
 * Returns
 *
 *   0 = lock was NOT acquired
 *   1 = lock WAS acquired
 *
 * When you are finished with your critical section, you MUST release the
 * lock by setting it to 0.
 *
 * This particular TSL is based on the x86 instruction xchgl.  We ASSUME
 * that this instruction is atomic.  Is it?  In reality, no.  Because even
 * machine code instructions are translated into MICROCODE:
 *
 *   http://en.wikipedia.org/wiki/Microcode
 *
 * And microcode can ALSO lead to race conditions.
 *
 * Fortunately, xchgl will also FREEZE other CPUs while it's running.  So
 * our only concern would be if the OS would switch threads during the
 * microcode operations -- quite unlikely.
 *
 * The code below was taken from:
 *
 *   http://ocw.mit.edu/courses/electrical-engineering-and-computer-science
 *   /6-828-operating-system-engineering-fall-2006/lecture-notes/l7_lock.pdf
 *
 * For more information, see:
 *
 *   http://en.wikipedia.org/wiki/Spinlock
 *   http://en.wikipedia.org/wiki/Test-and-set
 *
 * For an introduction to inline assembly in gcc, see:
 *
 *   http://www.ibiblio.org/gferg/ldp/GCC-Inline-Assembly-HOWTO.html
 */
int try_set_lock(unsigned int *addr)
{
  /*
   * NOTE: The `register' keyword is merely a REQUEST to the compiler to put
   * it into a register.  It might not do it.
   */
  register int content = 1;

  asm volatile (
    "xchgl %0, %1" : /* atomic operation; freezes other CPUs */
    "=r" (content),  /* output operand, write-only, any register */
    "=m" (*addr) :   /* output operand, directly in memory */
    "0" (content),   /* input operand, any register, matching digit %0 */
    "m" (*addr));    /* input operand, directly from memory */

  return content;
}

/*
 * The function that each thread will execute.
 */
void* worker(void*)
{
  /*
   * Wait until all threads have been started, then race to modify the
   * value (i.e., we want to provoke a race condition, so that a thread
   * reads, another writes and then the first writes the wrong value).
   *
   * Sleep a little between each interval (suspending thread), so that the
   * program gets a chance to start up the other threads before wreaking
   * havoc on that poor critical section below.
   */

  while ( idle_threads )
    usleep(100000);

  if ( lock == LOCK_OS )
    pthread_mutex_lock(&os_mutex);

  else if ( lock == LOCK_X86 )
    while ( try_set_lock(&x86_mutex) != 0 )
      ; // loop

  /*
   * Read and write value (this will be optimized by the compiler, but,
   * nonetheless, its microcode will consist of a READ and a STORE
   * operation, so that we could have several race conditions that could
   * lead to read-read-write-write operation among two threads.
   */

  value = value + 1;

  /*
   * Release locks
   */

  if ( lock == LOCK_OS )
    pthread_mutex_unlock(&os_mutex);

  else if ( lock == LOCK_X86 )
    x86_mutex = 0;

  return NULL;
}

int main(int argc, char** argv)
{
  parse_args(argc, argv);

  printf("DAT320 Operating Systems at University of Stavanger\n"
         "Lab 0, by Christian Stigen Larsen\n\n");

  printf("Starting threads w/locking scheme: %s\n",
    lock==LOCK_NONE? "No lock" :
    lock==LOCK_OS?   "pthread_mutex_lock" :
    lock==LOCK_X86?  "x86 xchg instruction" :
                     "x86 lock btr instruction");

  pthread_mutex_init(&os_mutex, NULL);

  for ( int n=0, i; n < count; ++n ) {
    printf("%d / %d\r", n, count); fflush(stdout);

    threads.push_back(new pthread_t());

    if ( (i = pthread_create(threads.back(), NULL, &worker, NULL)) != 0 ) {
      printf("Error: Cannot create thread %d w/error %d\n", n, i);
      exit(1);
    }
  }

  /*
   * Unpause threads
   */
  idle_threads = false;

  printf("Joining threads\n");

  for ( int n=0, i; !threads.empty(); ++n ) {
    printf("%d / %d %-40s\r", n, count, " "); fflush(stdout);

    if ( (i = pthread_join(*threads.back(), NULL)) != 0 ) {
      printf("Error: pthread_join returned %d\n", n);
      exit(1);
    }

    threads.pop_back();
  }

  printf("Protection misses: %d %-40s\n", count - value, " ");

  if ( value == count ) {
    printf("OK\n");
    return 0;
  }

  printf("FAIL\n");
  return 1;
}