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.

Answer 2

Even with a fair critical section, the code is probably going to have horrible performance, because if the critical section is being held for long periods of time, threads will be often waiting for it.

So I'd suggest you try to restructure the code so it does not need to lock critical sections over extended periods of time. Either by using different approach altogether (passing objects over message queue is often recommended, because it's easy to get right) or at least by doing most of the calculation on local variables without holding the lock and than only taking the lock to store the results. If the lock is held for shorter periods of time, the threads will spend less time waiting for it, which will generally improve performance and make fairness a non-issue. You can also try to increase lock granularity (lock smaller objects separately), which will also reduce the contention.

Edit: Ok, thinking about it, I believe every critical section in Linux is approximately fair. Whenever there are sleepers, the unlock operation has to enter kernel to tell it to wake them up. During return from kernel, scheduler runs and picks the process with highest priority. The sleepers rise in priority when waiting, so at some point they will be high enough that the release will cause a task swtich.