I'm trying to use locks and condition variable from the locks module, the documentation I found here seems to be quite poor, then I assumed that condition variables works like std::condition_variable in C++ that I've already used in the past. In particular I assumed that the wait function needs to be called on a Cond while holding a lock and this causes the thread to be stopped and the locks released until another thread calls signal on the Cond. This seems not to be the case since this very basic example results in a deadlock.
What's wrong with it and how does Cond works?
import locks
import deques
import cpuinfo
var
thr = newSeq[Thread[int]](countProcessors())
lock: Lock
cond : Cond
proc threadFunc(i: int) {.thread.} =
withLock(lock):
cond.wait(lock)
echo i
initLock(lock)
initCond(cond)
withLock(lock):
for i in 0..<thr.len:
createThread(thr[i], threadFunc, i)
for i in 0..<thr.len:
cond.signal()
for i in 0..<thr.len:
joinThreads(thr)
The implementation of condition variables, on linux at least, is pthreads. But the implementation is tangential in this case.
I think this example would deadlock in C++ as well.
You signal() all the threads in the main thread only once, and then wait for them.
It's possible that the thread scheduler will context switch to one of the other threads between each iteration of the signal() loop, in which case your code would work, but that is unlikely.
More likely, One thread will win the lock from that signal() loop, and the rest will go back to sleep. After that initial loop, there is no mechanism to wake the threads up again.
You need to either put a signal() call in threadFunc (cooperative locking), or have the main thread continue calling signal() instead of waiting.
note: that the semantics of signal() are to wake a single thread waiting on the conditional (notify_one in std::condtion_variable or pthread_cond_signal in pthreads)
It is not broadcast semantics. I.E. wakes all threads (notify_all in std::condition_variable or pthread_cond_broadcast in pthreads).
Though it might be a nice to add that api ... hint to @araq and core devs lol.
I think the problem was that when the main thread enetered the signal loop, no thread had actually started executing yet so thaht when the signal was called there were no threads waiting on the Cond, I added a sleep(1000) between the createThread loop and the signal loop and the code seems to work.
import locks
import cpuinfo
import strutils
import os
var
thr = newSeq[Thread[int]](countProcessors())
lock: Lock
cond : Cond
var counter = 0
proc threadFunc(i: int) {.thread.} =
counter += 1
withLock(lock):
cond.wait(lock)
counter -= 1
echo "$# $#" % [$i, $counter]
initLock(lock)
initCond(cond)
withLock(lock):
for i in 0..<thr.len:
createThread(thr[i], threadFunc, i)
sleep(1000)
for i in 0..<thr.len:
cond.signal()
for i in 0..<thr.len:
joinThreads(thr)
More likely, One thread will win the lock from that signal() loop, and the rest will go back to sleep. After that initial loop, there is no mechanism to wake the threads up again
Do you mean that it is possible that I call signal from the main thread with, say, two threads waiting on a Cond, then I call signal again from the main thread on the same cond, if the scheduler does not context switch to one of the two waiting thread between the two calls just one thread is woken up and the second one remains waiting?
This is an example of why multithreading is hard :-P
The Stack Overflow link from @cdunn2001 is good. It explains the concept better than me. I will try anyway:
You can't rely on all the threads being in a certain state at the same time. When you create those other threads in the creation loop, they start running on their own timeline. those threads are not guaranteed to have all gotten to the condition wait in their code by the time the main loop finishes.
If a thread isn't in the condition variable wait queue when the signal is called, it will never wake up, the signal calls are not "saved" in any way.
You "guaranteed" that all the threads are waiting on the condition variable wait queue by putting the sleep() call in. You basically gave the thread scheduler extra time to run all those other threads to the correct point.
Do you mean that it is possible that I call signal from the main thread with, say, two threads waiting on a Cond, then I call signal again from the main thread on the same cond, if the scheduler does not context switch to one of the two waiting thread between the two calls just one thread is woken up and the second one remains waiting?
No, It's more subtle than that. A condition variable is just a queue of threads. A cond.wait(), push's the thread onto the queue. A cond.signal() pops a thread off the queue.
In the two threads waiting on a Cond example that you described, There are two threads on the queue, and two calls to cond.signal(), causing both threads to be popped off the queue. The key is that both threads are actually in the Cond queue, not "almost" in the Cond queue ;-)
That's just the queue part, next you have the lock. Both threads are now awake, but both must "race" to win the lock. One thread will win the lock, and the other will lose, and be placed on the (different) queue waiting for the lock. (standard lock semantics) Which will work out just fine. No race condition or dead lock.
Hi community, just my 2cents on that topic:
I wrote a simple test (modified from the threads module doc) to explore the signalling behaviour. If signal is called first, the signal is not lost and a later wait() is not locking (on my machine). would be nice to share experience on other platforms..
here is the code:
# example taken from the module threads doc and modified for one child thread
# to explore the semantics of lock and signal
# code tested only on windows10 with a single core machine
# compiled with --d:release --threads:on
# Nim Compiler Version 0.17.3 (2017-09-16) [Windows: amd64]
# Copyright (c) 2006-2017 by Andreas Rumpf
# git hash: 12af4a3f8ac290f5c6f7d208f1a1951a141449ff
# active boot switches: -d:release
# if the signal is called before the wait is executed
# the signal is not lost, and the code is not locking
import locks,os
# globals
var
thr: Thread[int] # don´t know if there is a untyped thread possible
cLock: Lock
lockCond: Cond
proc threadFunc (param : int) {.thread.} =
signal(lockCond) # first signal call
signal(lockCond) # if you signal twice the second signal is lost (no queue)
echo "childthread: signal executed"
initLock(cLock)
initCond(lockCond)
createThread(thr, threadFunc,0)
echo "mainthread:begin"
sleep(5000) # ensure that the signal of the childthread is called first
echo "start waiting"
wait(lockCond,cLock)
# wait(lockCond,cLock)
# uncomment to check if there is a queue behind; on windows the (expected)
# behaviour is a deadlock for the second wait (second signal call is lost)
echo "end waiting"
joinThreads(thr) # should not block if the childthread is already finished
deinitLock(cLock)
deinitCond(lockCond)
echo "end"
@Mikra,
There is an error in your code. You have to acquire the lock before waiting on a condition variable, or the behavior is undefined.
@see:
http://en.cppreference.com/w/cpp/thread/condition_variable/wait
"Calling this function if lock.mutex() is not locked by the current thread is undefined behavior. "
http://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_cond_wait.html
"The pthread_cond_wait() and pthread_cond_timedwait() functions are used to block on a condition variable. They are called with mutex locked by the calling thread or undefined behaviour will result."
https://msdn.microsoft.com/en-us/library/windows/desktop/ms682052(v=vs.85).aspx
The Windows implementation doesn't explicitly state the behavior, but all the examples have a call to 'EnterCriticalSection(&CritSection);' before they wait on the condition.
@Mikra, On Mac OSX 10.12 (Sierra), I tested your code and a modified version like this:
withLock(cLock):
wait(lockCond,cLock)
wait(lockCond,cLock)
The program consistently deadlocks. The signals are consistently lost for me. Which is what I expect to happen. ¯\_(ツ)_/¯
Hi @rayman2220, thank you very much for your valuable response. You are right; I missed that "withLock(cLock):" before the wait(lockCond,cLock). Thanks for correcting me. Also thanks for the links, but I wonder how unspecified is defined :-)...
Just for clarification: your example also deadlocks with just one wait(lockCond,cLock)? Or I missed something? At least one signal shouldn`t lost because you can´t ensure that the waiting-thread is "faster"(waiting before signaling) than the signaling one. Because of that I added the extra "sleep(5000)" to test this specific condition.
I remember writing a consumer pattern using 2 threads for consumer and producer. Using channel to send the message, and using cond to wait if there's nothing to consume yet.
import locks
from strutils import parseInt
from os import sleep
when not defined(vcc):
import threadpool
var
chan: Channel[int]
cond: Cond
lock: Lock
time = 700
initLock lock
initCond cond
chan.open
proc chanWaiting() {.thread.} =
while true:
var res = tryRecv chan
if res.dataAvailable:
echo "Get the num: ", res.msg
# to simulate the congestion or slow operation
sleep time
if res.msg > 10:
echo "stopping operation"
break
# immediately for next loop if there's a value to avoid message
# congestion, in the event of there's no message then it will wait
# for the condition signaled
continue
echo "waiting for next iteration"
cond.wait lock
echo "condition signaled"
proc chanSending() {.thread.} =
while true:
var num = try: stdin.readline.parseInt
except: -1
echo "sending ", num
chan.send num
echo "going to signal the condition"
cond.signal
if num > 10:
break
when defined(vcc):
var
threadsend: Thread[void]
threadwait: Thread[void]
threadsend.createThread chanSending
threadwait.createThread chanWaiting
joinThread threadsend
joinThread threadwait
else:
spawn chanWaiting()
spawn chanSending()
sync()
From what I remembered, signaling condition before the condition waiting will make the signal lost. Also, signaling no matter how many are done, condition will only be handled once.
@mashingan, interesting example. The consumer pattern is the classic use case for a condition variable.
From what I remembered, signaling condition before the condition waiting will make the signal lost.
We agree on this point. The signal will be lost if you signal before the wait.
Also, signaling no matter how many are done, condition will only be handled once.
this is not correct. You only observe this because you only have one consumer thread.
If you had multiple consumer threads waiting on the condition, then each thread would need to be signaled.
The signal would not be "handled only once" as you say. It would be handled once for each waiting thread. (Or a broadcast call would need to be made to wake all waiting threads at once).
The canonical use case for a condition variable is single producer, multiple consumer. So multiple signals must be handled.
One other small thing is that it looks like your sample code has the same bug as @mikra, you do not acquire the lock before waiting on the condition in your chanWaiting() thread.
This may or may not affect anything, it depends on the underlying OS implementation of condition variable, but it's a good idea in order to prevent weird behavior (such as lost signals).
@rayman2220 & @mashingan many thanks for your inputs. The locking/signalling stuff seems a little bit nasty because of the behaviour of the underlying layer (OS); like always the details hurt :-)
For some usecases (especially you are looping withing the producer/consumer) it doesn`t matter if a signal is lost (signalling before owning and waiting on the lock). @mashingan besides of @rayman2220´s comments on your code I think it could be possible that (under some circumstances) your last signal-call is lost (n=10) so the chanWaiting thread could possible deadlock.
For my usecase I have a "oneshot"-like behaviour because the thread is calling signal() only once. So it´s extremely nasty in my eyes that the signal could be lost. I thought about that and finally I come up with the following solution now (testcode below). Please correct me if I missed something and the example is deadlocking on your environment (for me on windows it´s working @rayman2220:no clue how microsoft has implemented that but it seems that the signal-call on a condition is acting like a latch i.e. at least one signal-call is preserved):
import locks,os
# globals
var
thr: Thread[void]
cLock: Lock
lockCond: Cond
rcvWaiting : bool = false
proc threadFunc () {.thread.} =
echo "childthread: starting up"
while true:
# we like to model a one-shot behaviour so ensure that the receiver is owning the lock
if atomicLoadN[bool](unsafeAddr[bool](rcvWaiting),ATOMIC_SEQ_CST):
signal(lockCond)
echo "childthread: signal sent"
break
sleep(200) # ugly
echo "childthread: terminated"
initLock(cLock)
initCond(lockCond)
createThread(thr, threadFunc)
echo "mainthread:begin"
sleep(3000) # simulate childthread is running before we enter the lock
echo "mainthread: start waiting"
withLock(cLock):
# signal the sender that we are owning the lock now
atomicStoreN[bool](unsafeAddr[bool](rcvWaiting),true,ATOMIC_SEQ_CST)
wait(lockCond,cLock)
echo "mainthread: end waiting, sig received"
joinThreads(thr)
deinitLock(cLock)
deinitCond(lockCond)
echo "mainthread:end"
@Mikra,
Your code works on my machine, and seems sound. I think I have a cleaner solution though.
How about this:
import locks,os
# globals
var
thr: Thread[void]
cLock: Lock
lockCond: Cond
proc threadFunc () {.thread.} =
echo "childthread: starting up"
# one shot behavior can be achieved by leveraging the lock on the sender side as well
withLock(cLock):
signal(lockCond)
echo "childthread: signal sent"
echo "childthread: terminated"
initLock(cLock)
initCond(lockCond)
echo "mainthread:begin"
echo "mainthread: start waiting"
withLock(cLock):
# Create the sending thread after we have alread acquired the lock.
# The sender thread will be forced to wait for us because we own the lock.
createThread(thr, threadFunc)
# The wait function atomically releases the lock, allowing the sender thread to continue.
wait(lockCond,cLock)
echo "mainthread: end waiting, sig received"
joinThreads(thr)
deinitLock(cLock)
deinitCond(lockCond)
echo "mainthread:end"
Look! no timeouts! ;-)
Create the thread after you have already acquired the lock. Then you can leverage the lock on both the sender and receiver end, along with the property that waiting on a condition variable atomically unlocks the lock. The receiver thread will atomically re-acquire the lock as soon as it wakes up again.
This gives you a "latch" or "synchronization barrier" to hook in to. (Pick your terminology based your favorite text-book on multi-threading lol)
@rayman2220:no clue how microsoft has implemented that but it seems that the signal-call on a condition is acting like a latch i.e. at least one signal-call is preserved
damnit Microsoft..... y u have to be so broken?! lol
@rayman22201 ;-) your solution is much more elegant than mine and works also perfectly ; many thanks for that. yes the wait has to release the lock - anything else makes no sense (unfortunately send_all is missing in the locks-module). Decades ago I did hardware-design, so the latch is my mental model :-)
At the moment I am about to implement a softtimer-pool solution in Nim with a locking (wait) and a nonblocking (polling) api. I am not sure if I can afford acquiring a lock in my worker-thread because I like a one-thread solution and the "wait_for" stuff is missing in Nim (at the moment I am still at the beginner-street there :-) so it could be possible I have to go with my clumsy solution. When finished I will push it on github. But anyway many thanks for your great support
Glad I could help!
I don't want to disrespect your solution! You have basically implemented a spin lock, which is very high performance.
As long as you can afford to burn cpu cycles on the wait loop inside the worker, it is a good solution.
Like all important engineering problems, it is a design trade-off.
I look forward to seeing your library when it's published :-D
@rayman22201 for my very specific case (softtimerpool) the tickthread needs to sleep (after doing the counting-,signalling- and api-handling-stuff) to obtain the user-defined timebase for the artificial ticks and I don´t like a thread for each counter (that would be resource-burning :-). My solution should also run within resource-limited environments (tinyavr for instance).
@mashingan yes thanks for your hint; I looked at it but thats not multi-threaded. It runs inside the same thread(polling) - it`s for asynchronous I/O. I need a own thread to obtain the artificial ticks. Its not for critical timing purposes; often protocols need that (tcp/ip for instance) or for dimming LED´s and so on.