Linux与FIFO等待队列的同步

Question

Linux 中等待队列是 FIFO 的情况下是否存在锁？这似乎是一件显而易见的事情，但我刚刚发现 pthread 互斥体不是 FIFO，信号量显然也不是 FIFO（我正在研究内核 2.4（家庭作业））...

Linux 是否有锁先进先出等待队列，或者是否有一种简单的方法可以利用现有机制制作一个等待队列？

Answer 1

这是一种创建简单排队“票据锁”的方法，基于 pthreads 原语构建。它应该给你一些想法：

#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

如果你问我认为你在问什么，简短的回答是否定的。线程/进程由操作系统调度程序控制。一个随机线程将获得锁，而其他线程则不会。好吧，如果您使用计数信号量，则可能不止一个，但这可能不是您所要求的。

您可能想查看 pthread_setschedparam 但它不会让您到达我怀疑的地方想去。

你可能会写一些东西，但我怀疑它最终会效率低下，并且首先会失败，因为你最终会随机产生每个线程，直到你想要的线程获得控制权。

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

Answer 3

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

• 如果您需要 100% 正确的 FIFO 排序，请使用 caf 的 pthread 票据锁。

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

  如果您对 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% 先进先出。

注意：这是 4.4 Linux 内核的情况，2.4 可能有所不同。