公平临界区 (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

即使有一个相当好的关键部分，代码也可能会具有可怕的性能，因为如果关键部分被保留很长时间，线程通常会等待它。

因此，我建议您尝试重构代码，这样就不需要长时间锁定关键部分。要么完全使用不同的方法（通常建议通过消息队列传递对象，因为它很容易正确），要么至少在不持有锁的情况下对局部变量进行大部分计算，而不是仅使用锁来存储结果。如果持有锁的时间较短，线程等待它的时间就会减少，这通常会提高性能并使公平性不再成为问题。您还可以尝试增加锁定粒度（单独锁定较小的对象），这也会减少争用。

编辑：好吧，考虑一下，我相信 Linux 中的每个关键部分都是大致公平的。每当有睡眠者时，解锁操作就必须进入内核以告诉它唤醒它们。从内核返回期间，调度程序运行并选择具有最高优先级的进程。睡眠者在等待时优先级会上升，因此在某些时候它们的优先级会足够高，以至于释放会导致任务切换。

Answer 3

如果你的主张成立（我没有时间阅读，而且看起来你在发布问题之前已经研究过这一点），我建议

 sleep(0);

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

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

Answer 4

好的，这样怎么样：

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

Init.信号量计数为 1。在尝试获取 CS 并在完成后向其发出信号之前，让其他线程也等待该信号量。如果“计算”线程获得 sema，它就可以到达 CS 并锁定它。一旦进入锁内，但在长计算之前，sema 会发出信号，然后另一个线程可以到达 CS 但不能进入其中。当“计算”线程退出锁时，它无法循环并重新锁定它，因为 sema. count 为零，因此另一个线程获得锁。 “计算”线程必须等待 sema，直到进入的另一个线程完成其访问并向 sema 发出信号。

通过这种方式，另一个线程可以“保留”对数据的访问，即使它实际上还无法获取数据。

平均值，
马丁

Answer 5

恕我直言，您可以在 Linux 上使用 FIFO SCHEDULER 并更改线程的优先级：

thread_func() {
    ... 
    pthread_t t_id = pthread_self();
    struct sched_param prio_zero, prio_one;
    prio_zero.sched_priority = sched_get_priority_min(SCHED_FIFO);
    prio_one.sched_priority = sched_get_priority_min(SCHED_FIFO) + 1;
    phtread_setschedparam(t_id, SCHED_FIFO, &prio_zero);
    ...
    while(true)
    {
        ... Doing something before
        phtread_setschedparam(t_id, SCHED_FIFO, &prio_one);
        critsect.enter();
        ... do calculations ...
        ... maybe call a blocking operation so we sleep ...
        critsect.leave();
        phtread_setschedparam(t_id, SCHED_FIFO, &prio_zero);
        ... Do something after
    }
}