公平的关键部分(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互斥锁,允许其他线程加入队列.

Answer 2

如果您的说法成立（我没有时间阅读，而且您在发布问题之前似乎已经对此进行了研究），我建议

 sleep(0);

在关键部分之间明确让步。

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