linux - 公平临界区 (Linux)

Question

在多线程 Linux 应用程序中，我对关键部分使用互斥锁。除了公平性问题外，这非常有效。一个线程离开临界区并立即重新进入可能不会给任何其他线程机会。例如

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

很可能会阻止任何其他线程进入同一临界区。互斥锁不公平。

是否有解决方案来制作公平的临界区？我正在考虑添加一个队列，以便关键部分按照它们“到达”的顺序执行。或者，如果其他线程正在等待，至少有一个计数器可以在解锁后执行 pthread_yield()。

是否有针对此类要求的推荐做法？

Answer 1

您可以在 pthreads 互斥量之上构建一个 FIFO“票证锁”，按照以下行:

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

在这种方案下，当线程处于票锁保护的临界区内时，不会持有低级 pthreads 互斥量，从而允许其他线程加入队列。