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

I'm trying to implement a simple mutex lock using a semaphore that does not fall victim to starvation. In order to do this, I'm pretty sure I need to implement some sort of queue or other first-in-first-out approach, but semaphores in C appear to not respect any sort of FIFO structure. Given that, I've not been able to decipher how to wake and sleep threads in a proper FIFO order? Then again, perhaps I'm barking up the entirely wrong tree in my approach.

This link, https://pubs.opengroup.org/onlinepubs/7908799/xsh/sem_post.html implies something with SCHED_FIFO might be able to resolve my issue, but my relative inexperience with C left me neither sure if that could resolve my problem nor how I'd implement my solution.

Does C have a way of enabling a FIFO "fair" semaphore to make a fair lock that avoids starvation, or do you need a seperate queuing system of some sort? And in either case, how would you approach its implementation?

Thanks for any input you can provide!

CodePudding user response：

Are you only allowed to use a single semaphore as the means to block a thread? If so, then I don't think there is any pretty solution. Here's an ugly one: (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();

Suppose that thread A releases the semaphore while threads B, C, and D are awaiting it. Exactly one of B, C, or D will awaken. It will look at the queue, and if its own thread ID is at the head of the queue, it will pop the ID and proceed to do whatever. Otherwise, it will awaken one of the other two, sleep for a bit, and then try again.

In this way, each of the threads will be awakened, one-by-one, until one of them sees its own ID and breaks out of the loop.

The sleep(...) is important. Without it, the fundamental unfairness of the semaphore would make it likely that the subsequent semaphore.dec() call would immediately succeed, and the same thread would keep going round the loop, not seeing its own ID, and starving the others. The sleep(...) blocks the caller, thereby encouraging the OS to waken one of the other waiting threads.

OTOH, are you using the Posix Threads Library (pthreads)? And are you allowed to use any means available to block and awaken waiting threads? In that case, you could use a condition variable instead of the semaphore. You'd still need an explicit queue, and you'd still need a loop, but you could get rid of the sleep(...) because pthread_cond_broadcast(...) simultaneously awakens all of the waiting threads.

Condition variables are a bit trickier than semaphores—easy to make mistakes. I suggest you google for a good tutorial if you want to go that way.