Hacker News new | past | comments | ask | show | jobs | submit login

Starvation is equally an issue with semaphores.. how does that make a mutex different?



First of all, it's not clear to me that priority inversion is an issue with semaphores as normally used. If a high-priority consumer thread is waiting on a low-priority producer thread, there may just be no data ready to be consumed. There's no reason to raise the priority of the producer thread if, for example, it's just waiting for some external input.

Second, how would you solve priority inversion for general semaphores? With mutexes, you know what thread is holding the mutex, and can bump its priority correspondingly. With semaphores, there's no guarantee that the same thread that incremented the semaphore will decrement it later.


"As normally used" is part of the problem. How something is normally used has nothing to do with what it is.

General semaphores? I'll easily grant that would be difficult. Not impossible, but likely wasteful and a PITA.

Binary semaphores, which is where the debate lies? Store a whoDecremented thread pointer, cleared on increment. Which is functionally identical to Dekker's algorithm[1] and Eisenberg and McGuire's algorithm[2], except they require storage for all possible waiting threads, instead of the single storage of a semaphore.

edit: links: [1]: http://en.wikipedia.org/wiki/Dekker%27s_algorithm [2]: http://en.wikipedia.org/wiki/Eisenberg_McGuire_algorithm




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: