Andrew Que Sites list Photos
Projects Contact
Main

January 02, 2019

A.Q. CRC Goes Live

   For several weeks now I have been working on a project for generating CRC calculating source code.  Today I finished enough of the foundation to make it live.  There is still work to be done, especially rigorous testing.  But the basics are online and ready to go.

The last modification in my series about ticket locks is about aborting locks. In an ideal world every function waiting on a mutex will eventually obtain it. However, there are times we would like a blocking function to stop blocking but not get the mutex. The most common example is during application shutdown when we need all threads to stop blocking and rejoin the main thread.

Our ticket lock implementation uses conditional variables to signal threads waiting for the mutex that the mutex has been released. During an abort we simple need to signal the waiting threads but have a flag that denotes the mutex is aborting. This information needs to be relayed to the parent function requesting the lock, and that function needs to check this status. If the lock didn’t take place, the mutex wasn’t obtained, and whatever operations were supposed to happen should be aborted. In C++ throwing an exception would be appropriate. For our C implementation, simple returning a failure code for the mutex lock will suffice.

//=============================================================================
// Uses: Ticket lock with early abort example.
// Date: 2018-12-26
// Author: Andrew Que <https://www.DrQue.net>
// Notes:
//     Uses several threads that all hog a shared resource.  The ticket lock
//   will ensure all threads are able to access the resource equally.
// Compile:
//   gcc -Wall -Wextra -std=c99 -pedantic abortExample.c -O2 -pthread -o example
//
//                              Andrew Que, 2018
//                                Public domain
//=============================================================================

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <pthread.h>
#include <time.h>

// Define implementation specifics about mutex.
typedef struct
{
  // Mutex and conditional instance.
  pthread_mutex_t lock;
  pthread_cond_t condition;

  // True if thread is running.  False signifies a shutdown.
  bool volatile isRunning;

  // Id of the current thread that possesses the lock.
  pthread_t lockingThread;

  // Thread lock counts.
  // Used to track recursive locks.  Lock is free when count is 0.
  unsigned count;

  // Head/tail of mutex lock.
  // The head is the ticket being served, tail is the next trick number to
  // issue.
  unsigned volatile head;
  unsigned volatile tail;
} TicketLock;

//-----------------------------------------------------------------------------
// Uses:
//   Unlock mutex.  Must be called for each to `ticketLockAcquire`.
// Input:
//   ticketLock - Pointer to context.
// Output:
//   True if there was an error, false if not.
//-----------------------------------------------------------------------------
bool ticketLockRelease( TicketLock * ticketLock )
{
  bool isError = false;
  isError |= ( 0 != pthread_mutex_lock( &ticketLock->lock ) );

  // Decrease the mutex count.
  ticketLock->count -= 1;

  // If the mutex is free.
  if ( 0 == ticketLock->count )
  {
    ticketLock->lockingThread = 0;

    // Advance to next mutex in line.
    ticketLock->head += 1;

    // Signal other threads the resource has been released.
    isError |= ( 0 != pthread_cond_broadcast( &ticketLock->condition ) );
  }

  isError |= ( 0 != pthread_mutex_unlock( &ticketLock->lock ) );

  return isError;
}

//-----------------------------------------------------------------------------
// Uses:
//   Lock mutex.
// Input:
//   ticketLock - Pointer to context.
// Output:
//   True if there was an error, false if not.
// Note:
//   May unblock if the mutex has been signaled to shutdown.  Returns `true`
//   to denote an abnormal acquisition of resources.
//-----------------------------------------------------------------------------
bool ticketLockAcquire( TicketLock * ticketLock )
{
  bool isError = false;
  bool skipLock = false;

  // Don't try for a lock if not running--just return an error.
  isError |= ( ! ticketLock->isRunning );

  if ( ! isError )
  {
    isError |= ( 0 != pthread_mutex_lock( &ticketLock->lock ) );

    // If the same thread is requesting the lock, increase the mutex count.
    pthread_t currentThread = pthread_self();
    if ( ( ticketLock->count > 0 )
      && ( currentThread == ticketLock->lockingThread ) )
    {
      ticketLock->count += 1;
      skipLock = true;
    }

    // If the mutex doesn't already belong to us...
    if ( ! skipLock )
    {
      // Get a ticket number.
      unsigned ticket = ticketLock->tail;
      ticketLock->tail += 1;

      // Wait for our ticket number, shutdown, or an error.
      while ( ( ticketLock->head != ticket )
           && ( ticketLock->isRunning )
           && ( ! isError ) )
      {
        // Wait for mutex release.
        isError |= ( 0 != pthread_cond_wait( &ticketLock->condition, &ticketLock->lock ) );
      }

      if ( ! isError )
      {
        // Note what thread has the lock (this thread).
        ticketLock->lockingThread = currentThread;

        // Now one waiting lock count.
        ticketLock->count += 1;

        isError |= ( ! ticketLock->isRunning );
      }
    }

    isError |= ( 0 != pthread_mutex_unlock( &ticketLock->lock ) );
  }

  return isError;
}

//-----------------------------------------------------------------------------
// Uses:
//   Signal shutdown to cause all blocking threads to unblock.
// Input:
//   ticketLock - Pointer to context.
// Output:
//   True if there was an error, false if not.
// Note:
//   Calling this function will cause all locks on this mutex (pending and
//   future) to fail.
//   The mutex is not functional after shutdown and should be destroyed.
//-----------------------------------------------------------------------------
bool ticketLockShutdown( TicketLock * ticketLock )
{
  // Denote the we are no longer running.
  ticketLock->isRunning = false;

  // Signal all waiting about pending shutdown so they unblock.
  bool isError = ( 0 != pthread_cond_broadcast( &ticketLock->condition ) );

  return isError;
}

//-----------------------------------------------------------------------------
// Uses:
//   Setup a ticket mutex.  Must be called before mutex is used.
// Input:
//   ticketLock - Pointer to context to setup.
// Note:
//   Call `ticketLockDestroy` when done with mutex to release resources.
//-----------------------------------------------------------------------------
void ticketLockInitialize( TicketLock * ticketLock )
{
  // Initialize the mutex and conditional wait context.
  pthread_mutex_init( &ticketLock->lock, NULL );
  pthread_cond_init( &ticketLock->condition, NULL );

  ticketLock->isRunning = true;
  ticketLock->lockingThread = 0;
  ticketLock->count = 0;
  ticketLock->head = 0;
  ticketLock->tail = 0;
}

//-----------------------------------------------------------------------------
// Uses:
//   Release mutex resources.  Call when mutex is no longer needed.
// Input:
//   ticketLock - Pointer to context to destory.
//-----------------------------------------------------------------------------
void ticketLockDestroy( TicketLock * ticketLock )
{
  pthread_mutex_destroy( &ticketLock->lock );
  pthread_cond_destroy( &ticketLock->condition );
}

enum { THREADS = 8 };
static pthread_t threads[ THREADS ];
static TicketLock printMutex;

static bool volatile isRunning = true;

//-----------------------------------------------------------------------------
// Uses:
//   Sleep specified number of milliseconds.
// Input:
//   ms - Milliseconds to sleep.  Must be less than 1000.
//-----------------------------------------------------------------------------
static void sleep_ms( unsigned ms )
{
  struct timespec sleepValue = { 00 };
  sleepValue.tv_nsec = ms * 1000000;
  nanosleep( &sleepValue, NULL );
}

//-----------------------------------------------------------------------------
// Uses:
//   Thread to hog print mutex.
// Input:
//   parameter - Thread ID.
// Output:
//   Output is unused and simple returns parameter.
//-----------------------------------------------------------------------------
static void * threadFunction( void * parameter )
{
  // Recast parameter as unsigned.
  // Double-cast needed.
  unsigned threadIndex = (unsigned)(uintptr_t)parameter;

  // Random sleep before thread begins.
  sleep_ms( rand() % 50 );

  bool isError = false;
  while ( ( isRunning )
      && ( ! isError ) )
  {
    isError |= ticketLockAcquire( &printMutex );

    if ( ! isError )
      printf( "Thread: %u\n", threadIndex );

    struct timespec sleepValue = { 0 };
    sleepValue.tv_nsec = ( 150 + rand() % 150 ) * 1000000;
    nanosleep( &sleepValue, NULL );

    isError |= ticketLockRelease( &printMutex );
  }

  if ( isError )
    fprintf( stderr, "****** Thread %u had an error! ******\n", threadIndex );

  return parameter;
}

//-----------------------------------------------------------------------------
// Uses:
//   Ticket lock example.
// Output:
//   Always returns 0.
//-----------------------------------------------------------------------------
int main()
{
  // Setup random number generator.
  srand( time( NULL ) );

  ticketLockInitialize( &printMutex );

  printf( "Hit a Enter to stop.\n" );

  // Create and start all threads.
  for ( unsigned index = 0; index < THREADS; index += 1 )
    pthread_create( &threads[ index ], NULL, threadFunction, (void*)(uintptr_t)index );

  // Wait for enter to be pressed.
  fgetc( stdin );

  // Shutdown print mutex.  Should cause an error.
  ticketLockShutdown( &printMutex );

  // Signal shutdown.
  isRunning = false;

  // Wait for all threads to stop.
  for ( unsigned index = 0; index < THREADS; index += 1 )
    pthread_join( threads[ index ], NULL );

  ticketLockDestroy( &printMutex );

  return 0;
}

There are just two changes and one new function. The ticket lock context will get a flag called isRunning. By default this flag is true. When forcibly shutting down, the flag is set to false. A new function called ticketLockShutdown sets the flag to false, and broadcasts a condition change to all blocking threads. The last change is in the while loop used to wait for the desired ticket number. It will additionally stop if isRunning is not set and return an error should that condition arise.

December 26, 2018

Recursive Ticket Lock

I wrote about why one would need a ticket lock and how to implement one. Now I’d like to improve on this concept by adding recursion to the ticket lock.

First, what is meant by recursion? A mutex is usually used to isolate a resource so only one thread can use it at a time. Typically a mutex is used to a wrapped critical section. The critical section starts with the mutex being locked and ends when the mutex is released. It is a good practice to keep critical sections short as not to starve other threads that may want the resource.

Now consider that you have a resource used in several smaller functions, but also in larger functions. Think of a scenario where there are functions to print a header, body, and footer as well as a function to print the entire page that calls each of the proceeding functions. The header, body and footer functions all use a mutex to lock the print function. However, the print page function wants to lock the print function so that the entire page is not interrupted.

If the page function calls the individual header, body and footer functions, there is the chance another thread could grab the mutex after the header or body and insert text. This is especially true with a ticket lock where mutex request order is guaranteed. The page function could re-implement the header, body and footer functions and wrap them all with the mutex but that is bad pratice. What would be best is if the page function could simple request the mutex, call each of the sub-functions that also request the mutex, and then release the mutex. What we want is a recursive mutex.

A recursive mutex allows the same thread to make multiple requests for a mutex lock. The most basic mutex could dead lock itself by simply requesting the same mutex twice. The first lock it will get, but the second lock it can never get because it didn’t release the lock it already had. Many mutex implementation allow a thread to obtain a mutex if the it is the same thread already holding the lock. In addition, such implementations also require the same number of unlocks as locks before the mutex is freed by a thread. That is, if a thread requests a mutex 3 times, it must release it 3 times before the mutex actually becomes free. We would like this functionality extended to a ticket lock.

So what additional requirements are there for a recursive ticket lock? The mutex only needs to know the ID of the thread which currently holds the lock, and a count of how many times the current thread has locked the mutex. If the mutex is already locked, but the locking thread ID matches the current thread ID, the lock count is increased and there is no block. When unlocking the mutex, the lock count is decreased. If the count is zero, the mutex is actually released. If the count is not zero, the lock remains.

//=============================================================================
// Uses: Ticket lock with recursion example.
// Date: 2018-12-26
// Author: Andrew Que <https://www.DrQue.net>
// Notes:
//     Uses several threads that all hog a shared resource.  The ticket lock
//   will ensure all threads are able to access the resource equally.
// Compile:
//   gcc -Wall -Wextra -std=c99 -pedantic recursionExample.c -O2 -pthread -o example
//
//                              Andrew Que, 2018
//                                Public domain
//=============================================================================

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <pthread.h>
#include <time.h>

// Define implementation specifics about mutex.
typedef struct
{
  // Mutex and conditional instance.
  pthread_mutex_t lock;
  pthread_cond_t condition;

  // Id of the current thread that possesses the lock.
  pthread_t lockingThread;

  // Thread lock counts.
  // Used to track recursive locks.  Lock is free when count is 0.
  unsigned count;

  // Head/tail of mutex lock.
  // The head is the ticket being served, tail is the next trick number to
  // issue.
  unsigned volatile head;
  unsigned volatile tail;
} TicketLock;

//-----------------------------------------------------------------------------
// Uses:
//   Lock mutex.
// Input:
//   ticketLock - Pointer to context.
//-----------------------------------------------------------------------------
void ticketLockAcquire( TicketLock * ticketLock )
{
  bool skipLock = false;

  pthread_mutex_lock( &ticketLock->lock );

  // If the same thread is requesting the lock, increase the mutex count.
  pthread_t currentThread = pthread_self();
  if ( ( ticketLock->count > 0 )
    && ( currentThread == ticketLock->lockingThread ) )
  {
    ticketLock->count += 1;
    skipLock = true;
  }

  // If the mutex doesn't already belong to us...
  if ( ! skipLock )
  {
    // Get a ticket number.
    unsigned ticket = ticketLock->tail;
    ticketLock->tail += 1;

    // Wait for our ticket number.
    while ( ticketLock->head != ticket )
      pthread_cond_wait( &ticketLock->condition, &ticketLock->lock );

    // Note what thread has the lock (this thread).
    ticketLock->lockingThread = currentThread;

    // Now one waiting lock count.
    ticketLock->count += 1;
  }

  pthread_mutex_unlock( &ticketLock->lock );
}

//-----------------------------------------------------------------------------
// Uses:
//   Unlock mutex.  Must be called for each to `ticketLockAcquire`.
// Input:
//   ticketLock - Pointer to context.
//-----------------------------------------------------------------------------
void ticketLockRelease( TicketLock * ticketLock )
{
  pthread_mutex_lock( &ticketLock->lock );

  // Decrease the mutex count.
  ticketLock->count -= 1;

  // If the mutex is free.
  if ( 0 == ticketLock->count )
  {
    ticketLock->lockingThread = 0;

    // Advance to next mutex in line.
    ticketLock->head += 1;

    // Signal other threads the resource has been released.
    pthread_cond_broadcast( &ticketLock->condition );
  }

  pthread_mutex_unlock( &ticketLock->lock );
}

//-----------------------------------------------------------------------------
// Uses:
//   Setup a ticket mutex.  Must be called before mutex is used.
// Input:
//   ticketLock - Pointer to context to setup.
// Note:
//   Call `ticketLockDestroy` when done with mutex to release resources.
//-----------------------------------------------------------------------------
void ticketLockInitialize( TicketLock * ticketLock )
{
  // Initialize the mutex and conditional wait context.
  pthread_mutex_init( &ticketLock->lock, NULL );
  pthread_cond_init( &ticketLock->condition, NULL );

  ticketLock->lockingThread = 0;
  ticketLock->count = 0;
  ticketLock->head = 0;
  ticketLock->tail = 0;
}

//-----------------------------------------------------------------------------
// Uses:
//   Release mutex resources.  Call when mutex is no longer needed.
// Input:
//   ticketLock - Pointer to context to destory.
//-----------------------------------------------------------------------------
void ticketLockDestroy( TicketLock * ticketLock )
{
  pthread_mutex_destroy( &ticketLock->lock );
  pthread_cond_destroy( &ticketLock->condition );
}

enum { THREADS = 8 };
static pthread_t threads[ THREADS ];
static TicketLock printMutex;

static bool volatile isRunning = true;

//-----------------------------------------------------------------------------
// Uses:
//   Sleep specified number of milliseconds.
// Input:
//   ms - Milliseconds to sleep.  Must be less than 1000.
//-----------------------------------------------------------------------------
static void sleep_ms( unsigned ms )
{
  struct timespec sleepValue = { 00 };
  sleepValue.tv_nsec = ms * 1000000;
  nanosleep( &sleepValue, NULL );
}

//-----------------------------------------------------------------------------
// Uses:
//   Thread to hog print mutex.
// Input:
//   parameter - Thread ID.
// Output:
//   Output is unused and simple returns parameter.
//-----------------------------------------------------------------------------
static void * threadFunction( void * parameter )
{
  // Recast parameter as unsigned.
  // Double-cast needed.
  unsigned threadIndex = (unsigned)(uintptr_t)parameter;

  // Random sleep before thread begins.
  sleep_ms( rand() % 50 );

  while ( isRunning )
  {
    // Acquire lock multiple times prior to printing.
    ticketLockAcquire( &printMutex );
    ticketLockAcquire( &printMutex );
    ticketLockAcquire( &printMutex );

    // Print.
    printf( "Thread: %u\n", threadIndex );

    // Give up one of the locks.
    ticketLockRelease( &printMutex );

    // Waste time while holding the lock.
    sleep_ms( 10 + rand() % 50 );

    // Give up remaining locks.
    ticketLockRelease( &printMutex );
    ticketLockRelease( &printMutex );
  }

  return parameter;
}

//-----------------------------------------------------------------------------
// Uses:
//   Ticket lock example.
// Output:
//   Always returns 0.
//-----------------------------------------------------------------------------
int main()
{
  // Setup random number generator.
  srand( time( NULL ) );

  ticketLockInitialize( &printMutex );

  printf( "Hit a Enter to stop.\n" );

  // Create and start all threads.
  for ( unsigned index = 0; index < THREADS; index += 1 )
    pthread_create( &threads[ index ], NULL, threadFunction, (void*)(uintptr_t)index );

  // Wait for enter to be pressed.
  fgetc( stdin );

  // Signal shutdown.
  isRunning = false;

  // Wait for all threads to stop.
  for ( unsigned index = 0; index < THREADS; index += 1 )
    pthread_join( threads[ index ], NULL );

  ticketLockDestroy( &printMutex );

  return 0;
}

You almost always desire a recursive ticket lock implementation. The only item to consider is that you must have the same number of locks as unlocks or you can create a deadlock. Combine with single-entry single exit practices and starting/ending functions with lock/unlock virtually guarantees there will never be deadlock. Since the mutex is recursive all functions that use the resource can use their own lock/unlock and not have to worry about resource overlap or deadlock.

December 25, 2018

Ticket Lock in pthread

I wrote about the theory of a ticket lock and would now like to explore an example. First we need to demonstrate what can happen without a ticket lock. The implementations will use POSIX threads (pthreads).

//=============================================================================
// Uses: Resource hog example.
// Date: 2018-12-25
// Author: Andrew Que <https://www.DrQue.net>
// Compile:
//   gcc -Wall -Wextra -std=c99 -pedantic hogExample.c -O2 -pthread -o example
//
//                              Andrew Que, 2018
//                                Public domain
//=============================================================================

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <pthread.h>
#include <time.h>

enum { THREADS = 16 };
static pthread_t threads[ THREADS ];
static pthread_mutex_t printMutex;

static bool volatile isRunning = true;

//-----------------------------------------------------------------------------
// Uses:
//   Sleep specified number of milliseconds.
// Input:
//   ms - Milliseconds to sleep.  Must be less than 1000.
//-----------------------------------------------------------------------------
static void sleep_ms( unsigned ms )
{
  struct timespec sleepValue = { 00 };
  sleepValue.tv_nsec = ms * 1000000;
  nanosleep( &sleepValue, NULL );
}

//-----------------------------------------------------------------------------
// Uses:
//   Thread to hog print mutex.
// Input:
//   parameter - Thread ID.
// Output:
//   Output is unused and simple returns parameter.
//-----------------------------------------------------------------------------
static void * threadFunction( void * parameter )
{
  // Recast parameter as unsigned.
  // Double-cast needed.
  unsigned threadIndex = (unsigned)(uintptr_t)parameter;

  // Random sleep before thread begins.
  sleep_ms( rand() % 50 );

  while ( isRunning )
  {
    // Acquire lock prior to printing.
    pthread_mutex_lock( &printMutex );

    // Print.
    printf( "Thread: %u\n", threadIndex );

    // Waste time while holding the lock.
    sleep_ms( 10 + rand() % 50 );

    // Give up the lock.
    pthread_mutex_unlock( &printMutex );
  }

  return parameter;
}

//-----------------------------------------------------------------------------
// Uses:
//   Ticket lock example.
// Output:
//   Always returns 0.
//-----------------------------------------------------------------------------
int main()
{
  // Setup random number generator.
  srand( time( NULL ) );

  pthread_mutex_init( &printMutex, NULL );

  printf( "Hit a Enter to stop.\n" );

  // Create and start all threads.
  for ( unsigned index = 0; index < THREADS; index += 1 )
    pthread_create( &threads[ index ], NULL, threadFunction, (void*)(uintptr_t)index );

  // Wait for enter to be pressed.
  fgetc( stdin );

  // Signal shutdown.
  isRunning = false;

  // Wait for all threads to stop.
  for ( unsigned index = 0; index < THREADS; index += 1 )
    pthread_join( threads[ index ], NULL );

  pthread_mutex_destroy( &printMutex );

  return 0;
}

In this example several threads are created that all want the print resource. The thread hogs the resource by releasing the lock but immediately asking for the lock again. Typically what one will expect to see is a single thread printing its ID over and over, occasionally switching to another. The switch can happen if the operating system does a task switch just after the lock is released. Rare but it will eventually happen. The exact results will depend on the environment.

Now the same example, but with the addition of ticket locks.

//=============================================================================
// Uses: Ticket lock example.
// Date: 2018-12-25
// Author: Andrew Que <https://www.DrQue.net>
// Notes:
//     Uses several threads that all hog a shared resource.  The ticket lock
//   will ensure all threads are able to access the resource equally.
// Compile:
//   gcc -Wall -Wextra -std=c99 -pedantic ticketLockExample.c -O2 -pthread -o example
//
//                              Andrew Que, 2018
//                                Public domain
//=============================================================================

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <pthread.h>
#include <time.h>

// Context of a ticket lock.
typedef struct
{
  // Mutex and conditional instance.
  pthread_mutex_t lock;
  pthread_cond_t condition;

  // Head/tail of ticket.
  // The head is the ticket being served, tail is the next tricked number.
  unsigned volatile head;
  unsigned volatile tail;
} TicketLock;


//-----------------------------------------------------------------------------
// Uses:
//   Unlock mutex.  Must be called for each to `ticketLockAcquire`.
// Input:
//   ticketLock - Pointer to context.
//-----------------------------------------------------------------------------
void ticketLockRelease( TicketLock * ticketLock )
{
  pthread_mutex_lock( &ticketLock->lock );

  // Advance to next mutex in line.
  ticketLock->head += 1;

  // Signal other threads the resource has been released.
  pthread_cond_broadcast( &ticketLock->condition );
  pthread_mutex_unlock( &ticketLock->lock );
}

//-----------------------------------------------------------------------------
// Uses:
//   Lock mutex.
// Input:
//   ticketLock - Pointer to context.
// Note:
//   May unblock if the mutex has been signaled to shutdown.  Returns `true`
//   to denote an abnormal acquisition of resources.
//-----------------------------------------------------------------------------
void ticketLockAcquire( TicketLock * ticketLock )
{
  pthread_mutex_lock( &ticketLock->lock );

  // Get a ticket number.
  unsigned ticket = ticketLock->tail;
  ticketLock->tail += 1;

  // Wait for item to be added to queue.
  while ( ticketLock->head != ticket )
    pthread_cond_wait( &ticketLock->condition, &ticketLock->lock );

  pthread_mutex_unlock( &ticketLock->lock );
}

//-----------------------------------------------------------------------------
// Uses:
//   Setup a ticket mutex.  Must be called before mutex is used.
// Input:
//   ticketLock - Pointer to context to setup.
// Note:
//   Call `ticketLockDestroy` when done with mutex to release resources.
//-----------------------------------------------------------------------------
void ticketLockInitialize( TicketLock * ticketLock )
{
  // Initialize the mutex and conditional wait context.
  pthread_mutex_init( &ticketLock->lock, NULL );
  pthread_cond_init( &ticketLock->condition, NULL );

  ticketLock->head = 0;
  ticketLock->tail = 0;
}

//-----------------------------------------------------------------------------
// Uses:
//   Release mutex resources.  Call when mutex is no longer needed.
// Input:
//   ticketLock - Pointer to context to destory.
//-----------------------------------------------------------------------------
void ticketLockDestroy( TicketLock * ticketLock )
{
  pthread_mutex_destroy( &ticketLock->lock );
  pthread_cond_destroy( &ticketLock->condition );
}

enum { THREADS = 8 };
static pthread_t threads[ THREADS ];
static TicketLock printMutex;

static bool volatile isRunning = true;

//-----------------------------------------------------------------------------
// Uses:
//   Sleep specified number of milliseconds.
// Input:
//   ms - Milliseconds to sleep.  Must be less than 1000.
//-----------------------------------------------------------------------------
static void sleep_ms( unsigned ms )
{
  struct timespec sleepValue = { 00 };
  sleepValue.tv_nsec = ms * 1000000;
  nanosleep( &sleepValue, NULL );
}

//-----------------------------------------------------------------------------
// Uses:
//   Thread to hog print mutex.
// Input:
//   parameter - Thread ID.
// Output:
//   Output is unused and simple returns parameter.
//-----------------------------------------------------------------------------
static void * threadFunction( void * parameter )
{
  // Recast parameter as unsigned.
  // Double-cast needed.
  unsigned threadIndex = (unsigned)(uintptr_t)parameter;

  // Random sleep before thread begins.
  sleep_ms( rand() % 50 );

  while ( isRunning )
  {
    // Acquire lock prior to printing.
    ticketLockAcquire( &printMutex );

    // Print.
    printf( "Thread: %u\n", threadIndex );

    // Waste time while holding the lock.
    sleep_ms( 10 + rand() % 50 );

    // Give up the lock.
    ticketLockRelease( &printMutex );
  }

  return parameter;
}

//-----------------------------------------------------------------------------
// Uses:
//   Ticket lock example.
// Output:
//   Always returns 0.
//-----------------------------------------------------------------------------
int main()
{
  // Setup random number generator.
  srand( time( NULL ) );

  ticketLockInitialize( &printMutex );

  printf( "Hit a Enter to stop.\n" );

  // Create and start all threads.
  for ( unsigned index = 0; index < THREADS; index += 1 )
    pthread_create( &threads[ index ], NULL, threadFunction, (void*)(uintptr_t)index );

  // Wait for enter to be pressed.
  fgetc( stdin );

  // Signal shutdown.
  isRunning = false;

  // Wait for all threads to stop.
  for ( unsigned index = 0; index < THREADS; index += 1 )
    pthread_join( threads[ index ], NULL );

  ticketLockDestroy( &printMutex );

  return 0;
}

In this example, the first string of output can vary depending on the sleep time. However, that sequence will repeat thereafter.

Something to note about pthread conditional variables. There are two signaling functions available, pthread_cond_signal and pthread_cond_broadcast. The broadcast alerts all waiting threads, but the signal will just signal one of the threads. We need to use broadcast because the thread that gets notified in a single signal might not be the next ticket holder and the process will deadlock.

I have found that the hog example is identical to the ticket lock example when compiled under Cygwin. This is likely because the mutex the port of pthreads is using in this environment is already a ticket lock.