在pthreads中实现FIFO互斥

Question

我正在尝试实现支持并发插入的二叉树(甚至可能在节点之间发生),但无需为每个节点分配全局锁或单独的互斥锁或互斥锁.相反,分配的此类锁的数量应该是使用树的线程数量级.

因此,我最终遇到了一种锁定护航问题.更简单地解释一下,当两个或多个线程执行以下操作时,可能会发生这种情况:

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

也就是说,如果线程#1在一个"cpu突发"中执行指令4-> 5-> 1-> 2,那么线程#2将从执行中匮乏.

另一方面,如果pthreads中存在用于互斥锁的FIFO类型锁定选项,则可以避免这样的问题.那么,有没有办法在pthreads中实现FIFO类型的互斥锁？可以改变线程优先级吗？

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_mutexattr_setprioceiling函数。

int pthread_mutexattr_setprioceiling
(
    pthread_mutexatt_t * attr, 
    int prioceiling,
    int * oldceiling
);

从文档中：

pthread_mutexattr_setprioceiling(3THR) 设置互斥体属性对象的优先级上限属性。

attr 指向先前调用 pthread_mutexattr_init() 创建的互斥属性对象。

prioceiling 指定初始化互斥体的优先级上限。上限定义了执行互斥锁保护的临界区的最低优先级。prioceiling 将在 SCHED_FIFO 定义的优先级的最大范围内。为了避免优先级反转，prioceiling 将设置为高于或等于可能锁定特定互斥体的所有线程的最高优先级的优先级。

oldceiling 包含旧优先级上限值。