0

I've been thinking about the logic behind condition variable for a while, and getting comfortable with most common questions associated with it.

Basically, if We do something like:

mutex.lock()
while(!predicate()){
    mutex.unlock();
    pthread_cond_wait(&cv); // with mutex decoupled, no mutex is passed in I guess.
    mutex.lock();
}
mutex.unlock();

The window between unlock() and wait() is something we need to eliminate, and that's pretty much why cv exists in the first place.

Then I found this:

Features of Mutexes and Condition Variables

It had been suggested that the mutex acquisition and release be decoupled from condition wait. This was rejected because it is the combined nature of the operation that, in fact, facilitates realtime implementations. Those implementations can atomically move a high-priority thread between the condition variable and the mutex in a manner that is transparent to the caller. This can prevent extra context switches and provide more deterministic acquisition of a mutex when the waiting thread is signaled. Thus, fairness and priority issues can be dealt with directly by the scheduling discipline. Furthermore, the current condition wait operation matches existing practice.

(https://linux.die.net/man/3/pthread_cond_wait)

I just don't understand how pthread_cond_wait() can be decoupled with the mutex usage.

Hope someone can show me how can it be achieved, Or: Do I misunderstand the meaning of "decouple" in the comment?

John Bollinger
  • 160,171
  • 8
  • 81
  • 157
Wenjun Fu
  • 23
  • 4

1 Answers1

1

It can be achieved in a cooperative multitasking system, where you have an implicit global mutex. The implicit global mutex is the fact that only one thread runs at a time until it yields the processor. In such a system, you can have condition variables without any explicit mutex in sight. The condition wait operation achieves atomicity by ensuring that the calling thread is prepared for the wait before giving up the processor.

It looks like the text from that manual page is cribbed from the POSIX standard; it appears in the Rationale paragraphs of the description of pthread_cond_wait.

The surest way to determine what anything means in the POSIX standard is to contact the Austin group perhaps by joining the mailing list.

I suspect what this means by "decoupled" is not that a condition not be used without a mutex but that the API somehow allow the application to control the mutex independently, such that waiting on a condition takes multiple steps.

An example of multi-step waiting where the application controls the lock is found in the Linux kernel, in the explicit use of wait queues. To wait on a wait queue, the thread holds some relevant lock. Under that lock, it adds itself to the queue and prepares to wait by changing its state to a sleep state. Then it releases the lock, and calls the scheduler to be suspended. Once past the scheduler call, the thread removes itself from the queue.

There are some advantages to the more complicated, multi-step API, such as being able to register in multiple wait queues. Imagine we had an API pthread_cond_wait_multiple where we specify a mutex, and multiple condition variables, such that the thread wakes up if any of them are broadcast. You can't build that with pthread_cond_wait, but a decoupled API could make it possible.

Kaz
  • 55,781
  • 9
  • 100
  • 149
  • But what about preemptive multitasking system? The comment from pthread manual seems not imposing such a constrain (only cooperative multitasking system) on the decoupling thing. – Wenjun Fu Apr 19 '23 at 11:18
  • 1
    @WenjunFu: a preemptive multitasking system is an example where it can't be decoupled efficiently, which is why such a design was rejected for posix condition vars. – Chris Dodd Apr 19 '23 at 11:27
  • @Chris Dodd, but I just failed to find a way to do it, even inefficiently. That's why I am curious how you can actually do it (again, even inefficiently). – Wenjun Fu Apr 19 '23 at 13:01
  • @WenjunFu, when you say "find", are you asking a practical question or a theoretical one? The practical answer is "the pthreads API does not support that". The theoretical answer is a subject for a book. – John Bollinger Apr 19 '23 at 20:05
  • @WenjunFu: decoupling like this on a preemptive system leads to unfairness and useless spinning (when tasks jump in a grab a mutex unfairly). The result is not incorrect (does not cause deadlock), but is unfair (and can result in livelock and priority failures) and inefficient. – Chris Dodd Apr 19 '23 at 21:37
  • @Kaz Are you mentioning futex implementation in the kernel? (pthread condition variable is indeed built on top of futex, and I believe it is futex that ultimately soves the lost wake-up problem by providing an atomic "compare and block" operation) If that's the case, the lock you mentioned is a lock to protect cv's internal waiters (the futex_q struct in linux kernel does contain a waiters list), not the mutex we normally pass to pthread_cond_wait, which protects the predicate. (As in your years ago answer to another related question: https://stackoverflow.com/a/23281246/12589108) – Wenjun Fu Apr 20 '23 at 02:54
  • So I still cannot see how you can decouple the mutex unlock out of pthread_cond_wait. Of course you can modify pthread_cond_wait(&cv, &mutex) into something like: pthread_cond_xxx(&cv); mutex.unlock(); pthread_cond_wait(&cv); in which pthread_cond_xxx does what originally inside cond_wait but before unlock. But I guess "decouple" in such a way is far-fetched. – Wenjun Fu Apr 20 '23 at 02:56
  • @No, I'm not talking about futexes, which exist in support of user space. I'm talking about a synchronization mechanism used in the kernel which works similarly to condition variables, but in which the locking and queuing for a wait, and actually suspending, are separate (thus decoupled) operations. – Kaz Apr 20 '23 at 03:36
  • @Kaz You can achieve it (wait for a condition) with a lock and wait queue in kernel naturally, and I believe futex_wait in the kernel itself is a solid example. But I don't think that means you can decouple mutex from pthread_cond_wait(). Could you give some sort of code snippet showing how a mutex decoupled pthread_cond_wait(&cv) can do the same job with a canonical pthread_cond_wait(&cv, &mutex)? – Wenjun Fu Apr 20 '23 at 08:26
  • Both kernel and user space code need sync with a condition, the latter cannot do it without help from the former. I did notice how kernel achieves conditional wait, but still fail to come up with a decoupled impl of pthread_cond_wait(&cv). – Wenjun Fu Apr 20 '23 at 08:33
  • @WenjunFu That is actually not true. You can build synchronization without the kernel's support. It won't make good use of system resources though. Kernel support is required because when all of our application's threads are suspended, we want to make sure the processor is available to other processes in the system. So we need to call something in the kernel to put ourselves to sleep (according to the kernel's definition of sleep, not just our local idea). – Kaz Apr 21 '23 at 01:01
  • Futexes are specifically useful because of the kernel/user boundary which is expensive. In a system that has no kernel/user boundary with memory protection and expensive system calls. The Linux kernel doesn't use futexes internally. – Kaz Apr 21 '23 at 01:02
  • @Kaz, you are right, I should say "the latter cannot do it without help from the former" in a proper way (give up processors to others). e.g you can just unlock & spin & lock in a while loop to wait for a condition to be satisfied. – Wenjun Fu Apr 21 '23 at 02:40