After spending a couple days troubleshooting a problem, I think I’ve come to the conclusion that POSIX mutex’s aren’t FIFO but instead a free for all, first come algorithm? I’m coding on Linux. I have thread A blocking on thread B and expected when thread B released the lock that thread A would get it (next in line/fifo), but what seems to happen is thread B attempts to reacquire the lock again (assuming to block now on thread A, but instead, because thread B’s context is still active, thread B gets the lock again and thread A basically sits idle for ever, never getting the lock. I haven’t found any settings to change the way pthread_mutex_lock works so this doesn’t happen. Does anyone have a recommendation on how to do this? I don’t need to use POSIX synchronization, so I’m open to other libraries. I’ll still use POSIX threads, but the synchronization through a LOCK I don’t think should be dependant on the thread itself. Any help would be greatly appreciated. Thanks

As far as I can tell, posix mutexes are prioritised queues - threads should access in the order they attempt to acquire the mutex. Which is what you'd expect.

There are a couple of things you can try.

Firstly, delay thread B on release from the lock - do something else, sleep, whatever, anything long enough for the OS timeslice to jump to thread A. What are you doing between releasing the lock and reacquiring it? I tend to lock only when messing around with a serialised container (packet queue or such like), and lock and unlock within the acessing function only.

You could also try messing with the thread priorities, but I don't think that's really the answer.

Show the relevant code and we stand a better chance of helping. :-)

The implementation of POSIX mutexes on modern Linux systems (those using the NPTL threads implementation) are certainly free for all. The mutex implementation in the old POSIX threads implementation for Linux (LinuxThreads) were FIFO. The POSIX standard does not specify this detail of implementation--it states only that "if the mutex is already locked, the calling thread shall block until the mutex becomes available".

On most Windows systems, critical sections are FIFO, but this changes as of Windows Server 2003 SP1, where they become free for all for performance reasons. I expect Windows releases in future to retain the free for all behaviour.

Most applications that depend on FIFO behaviour for mutexes are broken (especially with respect to POSIX, but also for performant locking in general). However, there are certainly cases where FIFO locking behaviour may be a requirement.

The other side of this is that making locks fair (which usually means FIFO, but can mean other things) means that they become more expensive in all cases--because most applications do not require fairness if designed properly, it doesn't make sense to force every applications to pay an overhead for the property of fairness. Applications that require fairness can choose to pay the extra cost, and implement portable fair mutexes on top of the provided OS mutexes.

If you want to move away from using POSIX threads, you can implement your own locks on top of the fast userspace mutex (futex) primitive provided on the Linux kernel, but these won't be portable, and you'll need very detailed knowledge of assembly for each platform you need to run on. Alternatively, you could implement fair locks on top of the POSIX mutexes--this would be far easier and more portable.

If you'd like help coming up with a solution for your particular problem, you'll need to explain a bit about your design. One thing you might want to look at is using condition variables to signal readiness events between your threads, rather than just relying on fair locks.

Quote:

Original post by kinetik_mjg The implementation of POSIX mutexes on modern Linux systems (those using the NPTL threads implementation) are certainly free for all. The mutex implementation in the old POSIX threads implementation for Linux (LinuxThreads) were FIFO. The POSIX standard does not specify this detail of implementation--it states only that "if the mutex is already locked, the calling thread shall block until the mutex becomes available".

Thank God I wrapped my thread stuff into a set of classes. The implementation I'm using seems to be FIFO, but I'll have to ensure this for robustness.

In short, I have a thread walking a linked list, and another thread that wants to add an item to the linked list and a third that might remove an item from the linked list. Therefore, the owner of the list grabs a lock before it walks the list and keeps the lock for the entire duration. Then the add or delete thread try to get the lock when they need to do work. The design is for it to wait until the main thread completes processing the lest, then each of the other threads takes owner ship, adds or deletes as appropriate, then the main list continues again. I was dependant on a FIFO for this to work. There are plenty of other ways to architect it, so I don’t old the lock for the entire time I’m walking the list. Perhaps using a Queue for adds and deletes and let the main thread walk the queue, but that’s considerable more work than if FIFO worked.

You see the add and delete aren’t time critical, so I really didn’t want to get hung up on other implementations.

I also have a watchdog that walks the linked list looking to see if the thread is hung on a system call (blocking on a socket read because the client failed) or blocking on a hung database or something like that. The watchdog needs to also walk the list, very quickly, and maybe only once every second, but still needs to walk it, and the list should be locked, so I want to prevent adds and deletes while I walk it.

Hope that clarifies some things.

Is it possible to implement a non-blocking architecture into your design?

There are primitives other than mutex that may be more appropriate. Mutex is really just for a short critical section. If you need to actually signal information between threads, use something like an Event (on Windows) or monitor (on POSIX).