在 pthread 中实现 FIFO 互斥体

我正在尝试实现支持并发插入的二叉树（甚至可能在节点之间发生），但不必为每个节点分配全局锁或单独的互斥体。相反，分配的此类锁的数量应按线程数量使用树。

因此，我最终得到了一种锁车队 http://en.wikipedia.org/wiki/Lock_convoy问题。解释得更简单一点就是潜在地当两个或多个线程执行以下操作时会发生：

1 for(;;) {
2   lock(mutex)
3   do_stuff
4   unlock(mutex)
5 }
  

也就是说，如果 Thread#1 在一次“CPU 突发”中执行指令 4->5->1->2，那么 Thread#2 就会因执行而陷入饥饿状态。

另一方面，如果有一个 FIFO 类型的锁定选项mutexes在pthreads中，这样的问题就可以避免。那么，有没有办法在pthreads中实现FIFO类型的互斥锁呢？改变线程优先级可以实现这一点吗？

您可以实现一个公平的排队系统，其中每个线程在阻塞时都会添加到队列中，并且队列中的第一个线程始终在资源可用时获取资源。这种基于 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);
}