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?

Participate

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

Pooch

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.

Pibgorn

I have a server-client situation going on and the server needs to keep a log file in such a way that writing into it will not interfere with its I/O, meaning that a server-clent connection thread cannot go to wait because it is waiting for a mutex for the log faile that another such thread locked. I was thinking about throwing each entry into a separate "write to logfile" thread which can go to wait without interfering with it's parent thread. The messages in logfile can be mixed up, but must maintain proper chronology per connection, which is why I need a FIFO. – Participate

Set up a queue. The c-s connections write their log info to the queue. A separate thread reads the queue and writes to the file. You still have to acquire a lock on the queue but unless you know otherwise this should be irrelevant. The amount of time acquiring the queue lock will be dwarfed by the relative slowness of file and network I/O. Since any given c-s thread is writing to the queue in order your log output will likewise be in order per thread. – Pibgorn

Yeah that's what I wanted to avoid doing (would require more changes than a FIFIO lock), but I guess I don't have a choice anymore... – Participate

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.

Kettle