Linux synchronization with FIFO waiting queue

Question

Are there locks in Linux where the waiting queue is FIFO? This seems like such an obvious thing, and yet I just discovered that pthread mutexes aren't FIFO, and semaphores apparently aren't FIFO either (I'm working on kernel 2.4 (homework))...

Does Linux have a lock with FIFO waiting queue, or is there an easy way to make one with existing mechanisms?

Answer 1

Here is a way to create a simple queueing "ticket lock", built on pthreads primitives. It should give you some ideas:

#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);
}

Answer 2

If you are asking what I think you are asking the short answer is no. Threads/processes are controlled by the OS scheduler. One random thread is going to get the lock, the others aren't. Well, potentially more than one if you are using a counting semaphore but that's probably not what you are asking.

You might want to look at pthread_setschedparam but it's not going to get you where I suspect you want to go.

You could probably write something but I suspect it will end up being inefficient and defeat using threads in the first place since you will just end up randomly yielding each thread until the one you want gets control.

Chances are good you are just thinking about the problem in the wrong way. You might want to describe your goal and get better suggestions.

Answer 3

I had a similar requirement recently, except dealing with multiple processes. Here's what I found:

• If you need 100% correct FIFO ordering, go with caf's pthread ticket lock.

• If you're happy with 99% and favor simplicity, a semaphore or a mutex can do really well actually.

Ticket lock can be made to work across processes:
You need to use shared memory, process-shared mutex and condition variable, handle processes dying with the mutex locked (-> robust mutex) ... Which is a bit overkill here, all I need is the different instances don't get scheduled at the same time and the order to be mostly fair.

Using a semaphore:

static sem_t *sem = NULL;

void fifo_init()
{
    sem = sem_open("/server_fifo", O_CREAT, 0600, 1);
    if (sem == SEM_FAILED)  fail("sem_open");
}

void fifo_lock()
{
    int r;
    struct timespec ts;
    if (clock_gettime(CLOCK_REALTIME, &ts) == -1)  fail("clock_gettime");
    ts.tv_sec += 5;     /* 5s timeout */

    while ((r = sem_timedwait(sem, &ts)) == -1 && errno == EINTR)
        continue;       /* Restart if interrupted */
    if (r == 0)  return;

    if (errno == ETIMEDOUT) fprintf(stderr, "timeout ...\n");
    else                    fail("sem_timedwait");
}

void fifo_unlock()
{
    /* If we somehow end up with more than one token, don't increment the semaphore... */
    int val;
    if (sem_getvalue(sem, &val) == 0 && val <= 0)
        if (sem_post(sem))  fail("sem_post");
    usleep(1);  /* Yield to other processes */
}

Ordering is almost 100% FIFO.

Note: This is with a 4.4 Linux kernel, 2.4 might be different.