具有FIFO等待队列的Linux同步

Question

在等待队列为FIFO的Linux中有锁吗？这似乎是很明显的事情，然而我刚刚发现pthread互斥锁不是FIFO，信号量显然也不是FIFO (我正在做2.4内核(家庭作业))……

Linux是否有一个带有FIFO等待队列的锁，或者有没有一种简单的方法可以用现有的机制创建一个锁？

Answer 1

这里有一种创建简单队列“票证锁”的方法，构建在pthread原语之上。它应该会给你一些想法：

#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

如果你在问我认为你在问什么，简短的回答是不。线程/进程由OS调度程序控制。一个随机线程将获得锁，其他线程不会。如果你使用计数信号量，可能会有多个线程，但这可能不是你想要的。

你可能想看看pthread_setschedparam，但它不会让你得到我怀疑你想要的结果。

你可能会写一些东西，但我怀疑它最终将是低效的，而且一开始使用线程就会失败，因为你只会随机地产生每个线程，直到你想要的线程得到控制。

很有可能你只是在以错误的方式思考问题。你可能想要描述你的目标，并得到更好的建议。

Answer 3

除了处理多个进程之外，我最近也有类似的需求。这是我发现的：

如果您需要100%正确的先进先出排序，请使用的pthread ticket lock。

• 如果你对99%满意并且喜欢简单，那么信号量或互斥锁实际上可以做得很好。

可以使工单锁定跨进程工作：

您需要使用共享内存、进程共享互斥锁和条件变量，处理锁定互斥锁的进程(->健壮互斥锁) ...这在这里有点夸张，我所需要的是不同的实例不会同时调度，并且顺序基本上是公平的。

使用信号量：

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 */
}

排序几乎是100%的FIFO。

注意:这是一个4.4版的Linux内核，2.4版可能有所不同。