0

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!

Hailrig
  • 15
  • 5
  • 3
    Please provide the full requirements and constraints. What is the exact API you are trying to implement? What OS capabilities can or can't you use? One possibility is to use conditional variables. During unlock can broadcast signal to all block threads which could check the shared queue to see if they are the one that can unlock. But there is not enough context in your question to say whether that satisfies your requirements and constraints. – kaylum Mar 18 '22 at 22:55
  • Related question: [Fair critical section (Linux)](https://stackoverflow.com/q/6449732/12149471) – Andreas Wenzel Mar 18 '22 at 23:08
  • @kaylum Ah, right! Fair point. This stems from a really vague assignment to "use semaphores to implement a mutex that has no starvation." When I grilled my prof for clarifications, he said that he expected we would use some sort of queueing system to do it, but didn't himself know how exactly you'd implement it. I'm using Linux, I can say that much, but it's hard to provide a lot of context when the thing I'm trying to do is itself somewhat devoid of context ;-; – Hailrig Mar 18 '22 at 23:18
  • @AndreasWenzel Ooh! That might have my answer, actually. One thing I do notice is that one answer implies that the priority of threads rises with respect to the time they've spent waiting by default? Would that imply that any stock semaphore would avoid starvation in that respect by just having priorities go up internally? I really know nothing about the way its scheduling by default, I was just told semaphores wake up threads somewhat arbitrarily. – Hailrig Mar 18 '22 at 23:20
  • I believe Linux schedulers use a technique called 'priority inversion' to prevent starvation of lower priority processes. – Christian Gibbons Mar 18 '22 at 23:37
  • @AndreasWenzel after fiddling with it a bit, I'm not familiar with pthread_cond, is this solution doable with semaphores? It seems like pthread cond requires a mutex specifically, whereas I need to use semaphores. – Hailrig Mar 19 '22 at 01:59
  • 1
    Are you allowed more than one semaphore? If so, you can build a DIY 'super mutex' with an internal container of semaphores with one thread waiting on each. You can then apply any ordering, or other conditions, to release any waiting thread you require. – Martin James Mar 19 '22 at 09:10
  • 1
    @ChristianGibbons, The purpose of "priority inversion" is almost opposite to what you said. (Note: Some authors use "priority inversion" as the name of the problem, while others use it to name the solution.) Either way, the problem is that a low priority thread can lock a resource that is needed by a higher priority thread. That _effectively_ brings the priority of the blocked thread down. The solution is for the OS to _temporarily_ raise the priority of any thread that owns a mutex to be at least as high as the highest priority of any thread that is blocked waiting for it. – Solomon Slow Mar 19 '22 at 15:10
  • FYI: `SCHED_FIFO` only affects the scheduling of _runnable_ processes. It does not affect the order in which processes are unblocked when more than one awaits the same resource. – Solomon Slow Mar 19 '22 at 15:36
  • @MartinJames multiple semaphores as in one semaphore for each thread? That would requiring knowing how many threads you're going to have, right? – Hailrig Mar 19 '22 at 18:05
  • 1
    No. If a thread entets the mutex and finds it needs to wsit, it creates a semaphore, inserts it in the container, exits the mutex and waits on the semaphore it created. If the thread holding the super-mutex wants to release it, it enters the mutex, checks the list and, if there is a thread to release, signals that semaphore, removes it from the container and exits the mutex. The released thread deletes the semaphore and continues its execution. – Martin James Mar 20 '22 at 11:24
  • 1
    You could, if you wished, keep a cache of semaphores in another container in the supet-mutex, so reducing the need for semaphore create/delete calls. – Martin James Mar 20 '22 at 11:30

1 Answers1

1

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.

Solomon Slow
  • 25,130
  • 5
  • 37
  • 57
  • Wow, thanks for the answer! I agree it's not pretty, but that's something! I'm pretty sure using condition variables isn't in play, but that multiple semaphores is fair game. – Hailrig Mar 19 '22 at 18:03
  • Instead of calling `sleep`, it may be better to call [`sched_yield`](https://man7.org/linux/man-pages/man2/sched_yield.2.html). – Andreas Wenzel Mar 20 '22 at 13:42
  • @AndreasWenzel, The reason I did not suggest `sched_yield()` is that it does nothing at all if there is no other runnable thread in the system that is waiting for a CPU to run on. Of course, the preceeding `semaphore.inc()` call awakens one of the other contenders for the fair mutex, but I don't know whether it _guarantees_ to have made that other thread runnable _before_ the `inc()` call returns. – Solomon Slow Mar 20 '22 at 16:57