Fair critical section (Linux)

Question

On a multi-threaded Linux application I use a mutex for critical sections. This works very well except for the fairness issue. It can happen that a thread leaving a critical section and re-entering right away does not give any other thread a chance. For example

while(true)
{
    critsect.enter();
    ... do calculations ...
    ... maybe call a blocking operation so we sleep ...
    critsect.leave();
}

might very likely stop any other thread to enter the same critical section. Mutexe are not fair.

Is there a solution to making a fair critical section? I was thinking of adding a queue so that critical sections are executed in the order of their 'arrival'. Alternatively at least a counter to maybe do a pthread_yield() after unlock if other threads are waiting.

Is there a recommended practice for this kind of requirement?

Answer 1

You can build a FIFO "ticket lock" on top of pthreads mutexes, along these lines:

#include <pthread.h>

typedef struct ticket_lock {
    pthread_cond_t cond;
    pthread_mutex_t mutex;
    unsigned long queue_head, queue_tail;
} ticket_lock_t;

#define TICKET_LOCK_INITIALIZER { PTHREAD_COND_INITIALIZER, PTHREAD_MUTEX_INITIALIZER }

void ticket_lock(ticket_lock_t *ticket)
{
    unsigned long queue_me;

    pthread_mutex_lock(&ticket->mutex);
    queue_me = ticket->queue_tail++;
    while (queue_me != ticket->queue_head)
    {
        pthread_cond_wait(&ticket->cond, &ticket->mutex);
    }
    pthread_mutex_unlock(&ticket->mutex);
}

void ticket_unlock(ticket_lock_t *ticket)
{
    pthread_mutex_lock(&ticket->mutex);
    ticket->queue_head++;
    pthread_cond_broadcast(&ticket->cond);
    pthread_mutex_unlock(&ticket->mutex);
}

Under this kind of scheme, no low-level pthreads mutex is held while a thread is within the ticketlock protected critical section, allowing other threads to join the queue.