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?

Jones

Could you post an authoritative resource on your fairness claim. IMHO I think It can happen that a thread leaving a critical section and re-entering right away does not give any other thread a chance is not true. – Enneahedron

When a mutex is unlocked, the thread continues to run. Esp. when just before the unlock there was a thread-switch (e.g. a blocking operation) it is extremely likely that the thread goes uninterrupted to the next lock. Now, a pthread_mutex is a non-queuing mutex, so I can lock it even if some other - currently inactive - thread is blocking on the lock call. I don't have a definite resource documenting this, but stackoverflow question 3045066 shows an example and you can just run it (on a single-core system). – Jones

it's not a good idea to block or sleep inside a critical section, as the other thread cannot use this sleeping time to take its turn – Muir

For lazy people : #3045566 – Aubyn

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.

Scrubland

Should the TICKET_LOCK_INITIALIZER be updated to {PTHREAD_COND_INITIALIZER, PTHREAD_MUTEX_INITIALIZER, 0, 0 }? Seems like that would be more complete... – Vergos

@HighExodus: It could, but it's unnecessary - objects are never partially initialised in C, any aggregate members without explicit initialisers are initialised to zero of the appropriate type. – Scrubland

There's an added benefit in that it's possible to write the ticket numbers into a debug log, which can help someone to investigate e.g. deadlocks. – Finale

the 'queue_me' should be atomic initialized before the mutex lock. If this is not initialized before there is no way to guarantee the FIFO order because the first thread will get the lock and the others will wait for it. The next to wake up (after the first released it) may be any of the threads waiting to get the lock. – Alcala

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.

Sedate

Yes, this is of course a true statement. However it doesn't really solve the problem, because even if the critical sections are small, if I call them in a loop (and this does not even have to be a tight loop as thread scheduling is not in the microsecond granularity) the same issue can arise. In my particular case there is not much restructing possible due to the nature of the code that is protected. Either way, the question is how to get a fair critical section. – Jones

let me doubt you need to put "do some calculations" inside the critical section. just copy the few data you need in the section, then compute outside ( but in you loop ). – Muir

Well, if you lock in a loop, but only hold the lock for a short fraction of it, the probability that the other thread will have to wait decreases anyway. But if you can't restructure the code, than you need a fair critical section. Thinking of it, I actually believe it is. – Sedate

Answer 3

If your claim holds true (I haven't got the time to read up, and it would appear as though you have researched this before posting the question), I suggest

 sleep(0);

to explicitely yield in between critical sections.

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

Enneahedron

Well, duh :-) But I don't want to do this, as this scenario only happens in about 20% of the cases. So each time yielding the CPU will starve the threads of their allotted CPU time which will decrease performance. – Jones

Answer 4

OK, how about this:

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

Init. the semaphore count to 1. Have other threads wait on the semaphore as well before trying to get the CS and signal it when done. If the 'calculate' thread gets the sema, it can get to the CS and lock it. Once inside the lock, but before the long claculate, the sema is signaled and one other thread can then reach the CS but not get inside it. When the 'calculate' thread exits the lock, it cannot loop round and relock it because the sema. count is zero, so the other thread gets the lock. The 'calculate' thread has to wait on the sema until the other thread that got in has finished with its access and signals the sema.

In this way, another thread can 'reserve' access to the data even though it cannot actually get at it yet.

Rgds, Martin

Marvelous

OK, so my code format screwed up :( Tought I'd get that in before I'm downvoted for stupid <g> – Marvelous

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

Some days, it's just better to not get up at all :(( I tried adding backtick code in my previous comment but it still looks wrong :( – Marvelous

Answer 5

IMHO you can use a FIFO SCHEDULER on Linux and change de priority of threads:

thread_func() {
    ... 
    pthread_t t_id = pthread_self();
    struct sched_param prio_zero, prio_one;
    prio_zero.sched_priority = sched_get_priority_min(SCHED_FIFO);
    prio_one.sched_priority = sched_get_priority_min(SCHED_FIFO) + 1;
    phtread_setschedparam(t_id, SCHED_FIFO, &prio_zero);
    ...
    while(true)
    {
        ... Doing something before
        phtread_setschedparam(t_id, SCHED_FIFO, &prio_one);
        critsect.enter();
        ... do calculations ...
        ... maybe call a blocking operation so we sleep ...
        critsect.leave();
        phtread_setschedparam(t_id, SCHED_FIFO, &prio_zero);
        ... Do something after
    }
}

Epigone