如何在 C 语言中使用信号量实现具有先进先出结构的互斥锁

Question

我正在尝试使用不会成为饥饿受害者的信号量来实现一个简单的互斥锁。为了做到这一点，我很确定我需要实现某种队列或其他先进先出的方法，但 C 中的信号量似乎不遵守任何类型的 FIFO 结构。鉴于此，我无法破译如何以正确的 FIFO 顺序唤醒和休眠线程？再一次，也许我在我的方法中咆哮着完全错误的树。

link，https://pubs.opengroup.org/onlinepubs/7908799/xsh/sem_post.html 暗示 SCHED_FIFO 可能可以解决我的问题，但我对 C 的相对缺乏经验让我不确定这是否可以解决我的问题，也我将如何实施我的解决方案。

C 是否有启用 FIFO“公平”信号量的方法来创建避免饥饿的公平锁，或者您是否需要某种单独的排队系统？在任何一种情况下，您将如何实施？

感谢您提供的任何意见！

Answer 1

是否只允许使用单个信号量作为阻塞线程的方法？如果是这样，那么我认为没有任何漂亮的解决方案。这是一个丑陋的：(pseudo-code)

queue.put(my_thread_id);
semaphore.dec();

while (queue.head() != my_thread_id) {
    semaphore.inc();
    sleep(VERY_SMALL_TIME_INTERVAL)
    semaphore.dec();
}
(void) queue.pop();

...do whatever...

semaphore.inc();

假设线程A释放了信号量，而线程B、C和D正在等待它。 B、C、D 中只有一个会觉醒。它会查看队列，如果它自己的线程 ID 在队列的头部，它会弹出 ID 并继续执行任何操作。否则，它会唤醒另外两个中的一个，睡一会，然后再试。

这样，每个线程都会被唤醒，one-by-one，直到其中一个线程看到自己的ID并跳出循环。

sleep(...) 很重要。没有它，信号量的根本不公平性会使后续的 semaphore.dec() 调用很可能会立即成功，并且同一个线程将继续循环，看不到自己的 ID，并使其他线程挨饿。 sleep(...) 阻止调用者，从而鼓励 OS 唤醒 other 等待线程之一。

OTOH，您在使用 Posix 线程库 (pthreads) 吗？您是否被允许使用任何可用的方法来阻止和唤醒等待线程？在这种情况下，您可以使用 condition variable 而不是信号量。你仍然需要一个明确的队列，你仍然需要一个循环，但你可以摆脱 sleep(...) 因为 pthread_cond_broadcast(...) 同时唤醒 all of等待线程。

条件变量比信号量要复杂一些——容易出错。如果您想这样做，我建议您 google 获得一个很好的教程。

如何在 C 语言中使用信号量实现具有先进先出结构的互斥锁

How to use a semaphore in C to implement a mutex that respects starvation with a first in first out structure

c

concurrency

semaphore