Re: spurious wakeup
Marcin 'Qrczak' Kowalczyk
> 2.3 Is the approach that is described in the discussion "An easier to
> use Condition Variable API" the only one that tried to encapsulate the
> predicate handling into a library?
> Do you know more libraries with a similar design that offer a
> "ConditionObject" implementation?
> http://groups.google.de/groups?threadm=353C2FA9.67C212C7%40erdas.com
My experimental language Kogut uses condition variables coupled with a
mutex and a predicate. Everything I say here is not directly relevant
to pthreads or C.
There are no complete docs yet unfortunately.
Issues related to threads are currently best described in
<http://kokogut.sourceforge.net/NEWS>.
Its threads are implemented in userspace so I have control how
everything is done. Spurious wakeups can occur only as a result of
asynchronous signals sent to a thread. During handling a signal the
thread is unlinked from the condition variable, and it's simpler to
recheck the predicate than to try to keep track whether someone has
signalled it in the meantime. Integrating the predicate with a
condition makes spurious wakeups a non-issue. Kogut signals include
Unix signals but in general are a custom mechanism which I described
recently on this group, Subject: Asynchronous signals (again).
> 2.4 Did anybody try to connect the condition with a "signal handler"
> or other callback function?
> How do you think about an interpretation or approach that the signal
> call safely notifies a receiver/consumer that the predicate became
> true?
I'm not sure what do you mean.
Anyway, in Kogut a signal may be handled while waiting for a condition.
It can cause the predicate to become true, which will stop waiting.
It can perform a non-local exit which obviously stops waiting too.
Such signal is processed with the associated mutex unlocked, so the
signal handler should better lock it before manipulating the shared
state. Signals will normally not be processed while the main
computation of the thread has locked a mutex, so this is safe
wrt. locking by the thread.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Markus Elfring
> > or other callback function?
> > How do you think about an interpretation or approach that the signal
> > call safely notifies a receiver/consumer that the predicate became
> > true?
>
> I'm not sure what do you mean.
I suggest to make the next step with an approach like the one by Jason Rosenberg.
How do you think about the following interfaces?
void reaction (ConditionObject* c, void* (*callback) (void*));
int subscribe (ConditionObject* c,
void* (*action) (void*),
void* notification_context);
Is this design sketch useful to be integrated into other libraries?
struct job
{
void* (*_function) (void*);
void* _arg;
void** _result;
};
struct predicate
{
pthread_mutex_t _mutex;
pthread_cond_t _cond;
int _value;
};
struct rule
{
predicate _condition;
job _action;
};
void job_do (job* j)
{
if (j)
{
void* job_result = *(j -> _function) (j -> _arg);
if (j -> _result)
{
/* The caller is interested in the return value. */
*(j -> _result) = job_result;
}
}
}
int wait_for_work (predicate* p, job* j)
{
if (p)
{
int result;
/* Acquire a lock. */
if (result = pthread_mutex_lock(&(p -> _mutex))) == 0)
{
while (p -> _value == FALSE)
{
if (result = pthread_cond_wait(&(p -> _cond), &(p -> _mutex)))
{
return result;
}
}
/* Perform the action that is connected with the condition. */
job_do(j);
} /* end of if expression */
return result;
}
else
{
return EINVAL;
} /* end of if expression */
}
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
> How do you think about the following interfaces?
I must say emulating function closures in C is so horrible that it's
hard to see what's going on, and the resulting interface will probably
be less usable than raw mutexes and conditions just because of this,
because of the requirement of encoding everything in void * etc.
> void reaction (ConditionObject* c, void* (*callback) (void*));
> int subscribe (ConditionObject* c,
> void* (*action) (void*),
> void* notification_context);
What is the semantics?
> int wait_for_work (predicate* p, job* j)
> {
> if (p)
> {
> int result;
>
> /* Acquire a lock. */
> if (result = pthread_mutex_lock(&(p -> _mutex))) == 0)
> {
> while (p -> _value == FALSE)
> {
> if (result = pthread_cond_wait(&(p -> _cond), &(p -> _mutex)))
> {
> return result;
> }
> }
Waiting is not necessarily the first thing done after locking a mutex.
Or to put it differently, the action done while the mutex is locked
may wish to wait in other points than the beginning.
There can be several conditions associated with a mutex. (There is
generally one mutex and one predicate associated with a condition.)
If an abstraction locks the mutex and wraps the action done while the
mutex is locked, it should also unlock it.
Markus Elfring
> Or to put it differently, the action done while the mutex is locked
> may wish to wait in other points than the beginning.
>
> There can be several conditions associated with a mutex. (There is
> generally one mutex and one predicate associated with a condition.)
>
> If an abstraction locks the mutex and wraps the action done while the
> mutex is locked, it should also unlock it.
Would you like to insert more "place holders" or virtual functions for
customization?
Should the "main job" manage only the mutual exclusion for its own
data?
int wait_for_work (predicate* p,
job* j,
job* prepare = NULL,
job* cleanup = NULL)
{
if (p)
{
int result;
/* Acquire a lock. */
if ((result = pthread_mutex_lock(&(p -> _mutex))) == 0)
{
job_do(prepare);
while (p -> _value == FALSE)
{
if (result = pthread_cond_wait(&(p -> _cond), &(p -> _mutex)))
{
pthread_mutex_unlock(&(p -> _mutex));
return result;
}
}
/* Release the lock. */
if ((result = pthread_mutex_unlock(&(p -> _mutex))) == 0)
{
/* Perform the action that is connected with the condition. */
job_do(j);
job_do(cleanup);
Marcin 'Qrczak' Kowalczyk
> Would you like to insert more "place holders" or virtual functions
> for customization?
How? The control flow between various conditions to wait for, while
the mutex is locked (between waiting), can be arbitrarily complex.
For example emulating two coroutines can use two conditions and two
threads, such that one of them always waits for one of the conditions.
If the other thread finishes its part, it notifies the condition and
waits for the other. The mutex is only implicitly released during
waiting. Each thread loops through an unbounded number of waits
between initial locking and final unlocking the mutex.
> Should the "main job" manage only the mutual exclusion for its own
> data?
Probably yes. Maybe some languages try to provide different
abstractions but I haven't seen another usable choice.
The Kogut language has these concepts:
- A mutex.
- A condition, which is permanently associated with a mutex
and a predicate.
There are three basic operations:
- Locking the mutex around some code.
- Waiting for a condition (until its associated predicate becomes true).
- Notifying the condition that a predicate probably changed (two
flavors: notify all threads or notify one thread; the first is the
default and the second is an optimization when we know that only one
thread at a time can benefit from the changed predicate anyway).
Markus Elfring
> the mutex is locked (between waiting), can be arbitrarily complex.
Do you support template classes?
> For example emulating two coroutines can use two conditions and two
> threads, such that one of them always waits for one of the conditions.
> If the other thread finishes its part, it notifies the condition and
> waits for the other. The mutex is only implicitly released during
> waiting. Each thread loops through an unbounded number of waits
> between initial locking and final unlocking the mutex.
What do you mean with "coroutines"?
Do you think about such threads that cooperate and communicate similar
to a function pair?
Which "two conditions" have you got in mind?
> The Kogut language has these concepts:
> - A mutex.
> - A condition, which is permanently associated with a mutex
> and a predicate.
Which is the key part of the type "CONDITION" in your implementation
of this combination?
http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/lib/Core/Kokogut/Threads.ko?rev=1.98&view=markup
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
>> How? The control flow between various conditions to wait for, while
>> the mutex is locked (between waiting), can be arbitrarily complex.
>
> Do you support template classes?
With dynamic typing there is no place for them.
> What do you mean with "coroutines"?
Groups of threads such that only one at a time is running.
One use of coroutines is control inversion in iteration. There are two
most common iteration protocols: external iterators ("I'm giving you
an iterator, you can take a next element from it whenever you want")
and internal iterators ("give me a function, I will apply it to each
element in succession"). If a library provides external iterators,
it's easy to implement internal iteration in terms of them. The
opposite direction is harder: requires coroutines or something which
can express them, like continuations or threads.
I don't view coroutines as an important primitive concept and my
language doesn't provide them explicitly. It doesn't provide full
continuations either; it provides threads. I informally call
"coroutines" threads designed for explicit switching between contexts
of execution rather than for concurrent execution.
Here there are two complementary conditions, which tell which thread
should be running and which should wait. If the threads are the
internal iterator and the part of the program which uses the external
iterator, the conditions correspond to predicates "all produced
elements have been processed, the collection is supposed to give the
next element or signal the end of iteration" (the internal iterator
waits for this) and "the next element has been produced or the
iteration finished, the program should do something with it before
iteration proceeds further" (the main part waits for this). Each
thread signals one condition and waits for the other. This happens
as many times as there are elements.
The usual structure of code is as follows:
- There is a mutex for protecting some group of variables / fields.
- There is a number of conditions associated with the mutex, and each
condition is associated with a predicate about the protected data.
- Threads execute code which looks like this:
Lock mutex {
// code to run with the mutex being locked, which may examine
// protected data
...
// the code may include statements like
Wait someCondition;
// perhaps executed several times, perhaps on different
// conditions; the Wait checks the predicate, returns if it is
// true, otherwise unlocks the mutex, waits for some thread to
// notify about the condition, relocks the mutex, and loops again;
//
// in C this code would use an explicit while loop, because there
// is no convenient way to materialize a predicate in an object;
//
// a spurious wakeup (i.e. not caused by Notify) can occur in this
// implementation when the waiting thread receives an asynchronous
// signal; it's simpler to reevaluate the predicate than to try
// to keep track whether the condition has been notified while we
// were handling the signal
...
};
// here the mutex is unlocked again
- Threads also execute "Notify someCondition" or "Notify1 someCondition"
after they did something which made the condition true. This is often
done while the mutex is locked, but not necessarily.
>> The Kogut language has these concepts:
>> - A mutex.
>> - A condition, which is permanently associated with a mutex
>> and a predicate.
>
> Which is the key part of the type "CONDITION" in your implementation
> of this combination?
> http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/lib/Core/Kokogut/Threads.ko?rev=1.98&view=markup
I don't understand the question. This type is implemented in low level,
from the point of view of the language only its interface and behavior
matter. Anyway, it physically consists of 4 fields:
- the mutex
- the predicate (usually a function)
- the first and
- the last thread currently waiting for the condition (threads are
linked using their internal fields); these two fields are set to
KO_ABSENT if the queue is empty.
These fields are defined in C and are manipulated only from the C level,
from primitive functions defined in this module.
Markus Elfring
that you can avoid to read those documents first that might give
unclear or misleading informations and make its understanding
difficult.
1. links
1.1 succinct answers
1.1.1 DECthreads guide:
http://www.cs.arizona.edu/computer.help/policy/DIGITAL_unix/AA-Q2DPC-TKT1_html/thrd0124.html
pthread_cond_wait
"...
This routine might (with low probability) return when the condition
variable has not been signaled or broadcasted. When this occurs, the
mutex is reacquired before the routine returns. To handle this type of
situation, enclose each call to this routine in a loop that checks the
predicate. The loop provides documentation of your intent and protects
against these spurious wakeups, while also allowing correct behavior
even if another thread consumes the desired state before the awakened
thread runs.
..."
1.1.2 Multithreaded Programming :: Improving Performance through
Threads (pthreads Tutorial):
http://vergil.chemistry.gatech.edu/resources/programming/threads.html
"...
When waiting on condition variables, the wait should be inside a loop,
not in a simple if statement because of spurious wakeups. You are not
guaranteed that if a thread wakes up, it is the result of a signal or
broadcastcall.
[...]
Just because a thread has been woken does not mean it was due to a
pthread_cond_signal() or pthread_cond_broadcast() call.
..."
1.2 detailed answers with valuable background informations
1.2.1 Most Frequently Asked Questions
Q94: Spurious wakeups, absolute time, and pthread_cond_timedwait()
http://lambdacs.com/cpt/MFAQ.html#Q94
1.2.2 discussion "pthread_cond_wait waking up spuriously?"
http://groups.google.de/groups?threadm=slrn9euq45.hu.kaz%40cafe.net
1.2.3 discussion "What excatly is a spurious wakeup? (Was: discussion
on barriers)"
http://groups.google.de/groups?threadm=slrn9djb6l.ho.kaz%40cafe.net
1.2.4 discussion "pthread_cond_wait is unfair (POSIX threads)"
http://groups.google.de/groups?threadm=31B80BB0.59E2%40zko.dec.com
1.3 wording by the standard
The Open Group Base Specifications Issue 6, IEEE Std 1003.1:
http://www.opengroup.org/onlinepubs/007904975/functions/pthread_cond_wait.html
"...
Spurious wakeups from the pthread_cond_timedwait() or
pthread_cond_wait() functions may occur. Since the return from
pthread_cond_timedwait() or pthread_cond_wait() does not imply
anything about the value of this predicate, the predicate should be
re-evaluated upon such return.
[...]
If a signal is delivered to a thread waiting for a condition variable,
upon return from the signal handler the thread resumes waiting for the
condition variable as if it was not interrupted, or it shall return
zero due to spurious wakeup.
..."
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_cond_signal.html
"...
An added benefit of allowing spurious wakeups is that applications are
forced to code a predicate-testing-loop around the condition wait.
This also makes the application tolerate superfluous condition
broadcasts or signals on the same condition variable that may be coded
in some other part of the application. The resulting applications are
thus more robust.
..."
1.4 a manual page from the HP-UX documentation
http://www.calpoly.edu/cgi-bin/man-cgi?pthread_cond_timedwait+3
"...
A spurious wakeup occurs when a thread returns from a condition wait
when it should really continue waiting. A normal signal being
delivered to a thread may cause a spurious wakeup during a condition
wait. Since the return values from pthread_cond_wait() and
pthread_cond_timedwait() do not imply anything about the value of the
predicate, the predicate should be re-evaluated.
..."
2. development
2.1 I am interested in the special case when spurious wakeups must not
happen.
Does this case exist?
2.2 The pthreads interface does not officially provide this service.
Does any implementation offer a specific attribute to switch
"wake-only-once" semantics on?
2.3 Is the approach that is described in the discussion "An easier to
use Condition Variable API" the only one that tried to encapsulate the
predicate handling into a library?
Do you know more libraries with a similar design that offer a
"ConditionObject" implementation?
http://groups.google.de/groups?threadm=353C2FA9.67C212C7%40erdas.com
2.4 Did anybody try to connect the condition with a "signal handler"
or other callback function?
How do you think about an interpretation or approach that the signal
call safely notifies a receiver/consumer that the predicate became
true?
Regards,
Markus
Markus Elfring
> should be running and which should wait.
Is a single condition variable not enough in your use case?
> Wait someCondition;
> // perhaps executed several times, perhaps on different
> // conditions; the Wait checks the predicate, returns if it is
> // true, otherwise unlocks the mutex, waits for some thread to
> // notify about the condition, relocks the mutex, and loops again;
How do you think about this C++ design sketch?
template<class predicate,
class job,
class is_equal = std::equal_to<bool, bool>,
const comparison_value = false,
class lock_guard = mutex_guard>
class waiter
: public binary_function<predicate, job, void>
{
void operator() (predicate& p, job& j) // wait for work...
{
// Locked scope
{
is_equal the_same(p._value, comparison_value);
lock_guard lg(p._mutex);
j.prepare();
while (the_same())
{
p._cond.wait();
}
}
// Perform the action that is connected with the condition.
j.main();
j.cleanup();
}
}
Regards,
Markus
Markus Elfring
> Q94: Spurious wakeups, absolute time, and pthread_cond_timedwait()
> http://lambdacs.com/cpt/MFAQ.html#Q94
Do you think or want that "wake-only-once" semantics or "protection"
against spurious wakeups will be provided by the library that is
imagined or announced in the document "Memory model for multithreaded
C++"?
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1680.pdf
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
>> Here there are two complementary conditions, which tell which thread
>> should be running and which should wait.
>
> Is a single condition variable not enough in your use case?
As I said: technically it would work, it's just ugly (IMHO). The mere
fact that each time one of two variables has a statically known value
doesn't justify making them one variable.
> template<class predicate,
> class job,
> class is_equal = std::equal_to<bool, bool>,
> const comparison_value = false,
> class lock_guard = mutex_guard>
> class waiter
> : public binary_function<predicate, job, void>
> {
> void operator() (predicate& p, job& j) // wait for work...
> {
> // Locked scope
> {
> is_equal the_same(p._value, comparison_value);
> lock_guard lg(p._mutex);
> j.prepare();
>
> while (the_same())
> {
> p._cond.wait();
> }
> }
The mutex should locked around the whole computation which performs
waits at various points on various conditions, not just around
a single wait.
C++ is only a bit better than C with respect to first-class functions.
I believe that in C++, as in C, it's easier for the programmer to
write an explicit while loop than to package a predicate and actions
as objects.
The predicate is not always a simple comparison. It could be forced to
be a comparison, but this would require moving the computation to all
places which notify about a satisfied condition instead of keeping it
in one place.
Instead of theoretizing, how about testing the abstraction on
something concrete? Below is a simulator of an elevator. I hope the
language will not be a barrier, I put a lot of comments which should
explain everything.
Conditions correspond to predicates that some thread has a reason to
wait for. Other threads use Notify (analogous to pthread_cond_broadcast)
after they have changed the state to possibly satisfy the condition.
In order to simplify code they sometimes notify when the condition may
be still false for some reasons - it's harmless, because the waiting
thread will reevaluate the predicate and wait again if needed. But
it's important that they notify in *all* cases where the predicate
might become true. In other words, it's the job of the waiting thread
to ensure that it really wants to finish waiting.
use Threads;
use Random;
// Serializing lines of output, gathered from various threads.
let InfoMutex = Mutex();
let Info msg... {
Lock InfoMutex {WriteLine msg...}
};
// The state of the elevator:
type ELEVATOR = Elevator floors {
// 'floors' is the number of floors, excluding the ground floor which is
// numbered 0. This is the numbering style used e.g. in Poland.
let mutex = Mutex();
var floor = 0;
var stopped = True;
var direction = #up;
// 'direction' is the actual direction when the elevator is going, or the
// preferred direction when it's stopped.
let wantToGoUpFrom = HashDict()->WithDefault 0;
let wantToGoDownFrom = HashDict()->WithDefault 0;
// 'wantToGo{Up,Down}From' maps a floor number to the number of people
// waiting to go from that floor in the particular direction; they have
// pressed the appropriate button outside the elevator.
let wantToStopAt = HashDict()->WithDefault 0;
// 'wantToStopAt' maps a floor number to the number of people who want
// to go to that floor; they have pressed the appropriate button inside
// the elevator.
let someRequests = Condition mutex {
Some (Between 0 floors) ?f {f ~= floor & SomeRequestsAt this f}
};
// 'someRequests' is true when the elevator has a reason to go somewhere.
// Requests belonging the current floor are not counted because they mean
// that people have not completely entered or left yet.
let canGo = Condition mutex {~SomeRequestsAt this floor};
// 'canGo' is true when there are no people who are entering or leaving
// the elevator at this moment.
let stoppedAt = GenMap (Between 0 floors) ?f {
f, Condition mutex {stopped & floor == f}
}->HashDict;
// 'stoppedAt' maps a floor number to the condition which is true when
// the elevator is stopped at this floor.
};
let SomeRequestsAt elevator floor {
// There are people who want to enter or leave on this floor.
elevator.wantToGoUpFrom@floor ~= 0 |
elevator.wantToGoDownFrom@floor ~= 0 |
elevator.wantToStopAt@floor ~= 0
};
let SomeRequestsAbove elevator floor {
// There are people who want to enter or leave above this floor.
Some (Between (floor + 1) elevator.floors) (SomeRequestsAt elevator _)
};
let SomeRequestsBelow elevator floor {
// There are people who want to enter or leave below this floor.
Some (Between 0 (floor - 1)) (SomeRequestsAt elevator _)
};
let SomeRequestsUp elevator floor {
// There are people who want to enter (to go up) or leave on this floor.
elevator.wantToGoUpFrom@floor ~= 0 |
elevator.wantToStopAt@floor ~= 0
};
let SomeRequestsDown elevator floor {
// There are people who want to enter (to go down) or leave on this floor.
elevator.wantToGoDownFrom@floor ~= 0 |
elevator.wantToStopAt@floor ~= 0
};
let E1 = Elevator 12;
// We have one building with 12 floors in this world, and one elevator.
let PersonThread n {
// This is the life cycle of a person. About half of people start on
// a random floor; the other half starts outside the building.
var floor = if (RandomFloat() < 1/2) {0} else {Random 1 (E1.floors + 1)};
loop =>
Sleep (RandomFloat 1 2000);
// People outside want to go to a random floor. People inside want to go to
// the ground floor 3/4 of the times, otherwise to a random floor.
let wantedFloor = if (floor == 0 | RandomFloat() < 1/4) {
Random 1 (E1.floors + 1) // A random floor, excluding the ground floor.
}
else {0};
if (wantedFloor ~= floor) {
Info "Person " n " wants to go to from floor " floor " to " wantedFloor;
// There are two buttons for calling the elevator, depending on whether
// we want to go up or down.
let wantToGoFrom = if (wantedFloor > floor) {E1.wantToGoUpFrom}
else {E1.wantToGoDownFrom};
Lock E1.mutex {
// Press the button outside the elevator.
wantToGoFrom@floor = wantToGoFrom@floor + 1;
Notify E1.someRequests;
// Wait for the elevator to come.
Wait E1.stoppedAt@floor
};
// Entering the elevator takes some short time. For simplicity we assume
// that the elevator has no limit for the number of people.
Sleep (RandomFloat 1 2);
Info "Person " n " enters the elevator at floor " floor
" and presses button " wantedFloor;
Sleep (RandomFloat 1 2);
Lock E1.mutex {
// We have entered the elevator, so we no longer want it to come here.
wantToGoFrom@floor = wantToGoFrom@floor - 1;
Notify E1.canGo;
// Instead, we want it to go to some other floor.
E1.wantToStopAt@wantedFloor = E1.wantToStopAt@wantedFloor + 1;
Notify E1.someRequests;
// Wait until the elevator gets us to that floor.
Wait E1.stoppedAt@wantedFloor;
floor = wantedFloor
};
// Leaving the elevator also takes some short time.
Sleep (RandomFloat 1 2);
Info "Person " n " leaves the elevator at floor " floor;
Sleep (RandomFloat 1 2);
Lock E1.mutex {
// We have left the elevator, so we no longer want it to come here.
E1.wantToStopAt@floor = E1.wantToStopAt@floor - 1;
Notify E1.canGo
}
};
again()
};
// There are 100 people in this building.
Each (Between 1 100) ?n {
Thread {PersonThread n}
};
loop {
// This is the life cycle of the elevator.
let shouldStop = Lock E1.mutex {
if E1.stopped {
// Wait until somebody wants to go somewhere.
Wait E1.someRequests;
// Wait until people enter or leave the elevator completely.
Wait E1.canGo;
// If there are requests in the direction we are going in, keep the
// same direction. Otherwise change it. So if there are requests both
// above and below, we keep the same direction as before.
case E1.direction [
#up {if (~SomeRequestsAbove E1 E1.floor) {E1.direction = #down}}
#down {if (~SomeRequestsBelow E1 E1.floor) {E1.direction = #up}}
];
Info "Elevator goes " E1.direction " from floor " E1.floor;
E1.stopped = False
};
// Determine whether we will stop on the next floor. We will stop if
// there are no more requests *after* this floor, or if there are people
// who want to enter and go in the same direction as we are currently
// going, or if there are people who want to leave. We don't stop for
// people who want to go in the opposite direction if we would go further
// in our current direction; we will take them when we come here again.
case E1.direction [
#up {
let floor = E1.floor + 1;
~SomeRequestsAbove E1 floor | SomeRequestsUp E1 floor
}
#down {
let floor = E1.floor - 1;
~SomeRequestsBelow E1 floor | SomeRequestsDown E1 floor
}
]
};
// Stopping takes longer time because we must slow down gently.
Sleep (if shouldStop {3} else {2});
Lock E1.mutex {
// Update the current floor.
let floor = E1.floor = case E1.direction [
#up {E1.floor + 1}
#down {E1.floor - 1}
];
if shouldStop {
Info "Elevator stops at floor " floor;
// Tell people that we have arrived here.
E1.stopped = True;
Notify E1.stoppedAt@floor
}
else {
Info "Elevator is passing floor " floor ", going " E1.direction
}
};
again()
};
Markus Elfring
> write an explicit while loop than to package a predicate and actions
> as objects.
An other opinion is expressed in the header <functional> by the STL
designers.
> The predicate is not always a simple comparison. It could be forced to
> be a comparison, but this would require moving the computation to all
> places which notify about a satisfied condition instead of keeping it
> in one place.
How do you think about the following suggestion?
template<typename context>
struct predicate : public unary_function<context, bool>
{
virtual ~predicate () {}
virtual bool operator() (context const& c) const = 0;
}
Would you like to expect the service that a multi-threading library
notifies a caller only once if the condition will be satisfied?
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
> How do you think about the following suggestion?
>
> template<typename context>
> struct predicate : public unary_function<context, bool>
> {
> virtual ~predicate () {}
> virtual bool operator() (context const& c) const = 0;
> }
My intuition still tells that packaging a predicate as a C++ object
is inconvenient. Technically it's possible, you only have to derive
a subclass, move variables needed by the predicate to fields, write
a constructor which initializes the fields, invoke the constructor
passing free variables explicitly, and think who should free it.
That's a lot of lines compared to while (!predicate) wait(condition);
Even various lambda libraries don't help much in this case. The
function has no parameters, yet it must be delayed and evaluated
multiple times. I don't know whether those lambda libraries cover
such cases at all.
You can try it yourself and translate my elevator example to C++ to
test various abstractions around condition variables. I wonder how
much longer it gets. It may be hard to predict how well a particular
abstraction works without trying it in practice.
> Would you like to expect the service that a multi-threading library
> notifies a caller only once if the condition will be satisfied?
I don't understand the question.
If the condition variable is wrapped together with the predicate, I
expect waiting to be equivalent to the above while loop, because this
is the classic pattern of waiting for a condition. In this case it
doesn't matter whether the "raw" condition wait has spurious wakeups
(the predicate should not have side effects and should not take too
long to compute). When the predicate is satisfied, the waiting
function returns.
Markus Elfring
If you want to provide protection against spurious wakeups by a
library function or method, you need to pass the predicate and the
surrounding and corresponding code as (template) parameters.
Would you like to use a similar service quality like it is available
for the algorithms "std::for_each()" and "std::find_if()"?
> If the condition variable is wrapped together with the predicate, I
> expect waiting to be equivalent to the above while loop, because this
> is the classic pattern of waiting for a condition. In this case it
> doesn't matter whether the "raw" condition wait has spurious wakeups
> (the predicate should not have side effects and should not take too
> long to compute). When the predicate is satisfied, the waiting
> function returns.
It does matter if the documentation leaves out that spurious wakeups
can happen.
How many libraries do implement just the pthreads behaviour?
http://wefts.sourceforge.net/wefts-apidoc-0.99c/classWefts_1_1Condition.html#a0
http://www.gnu.org/software/commoncpp/docs/refman/html/class_conditional.html#a0
http://www.home.unix-ag.org/weitzel/threadspp.php
But the page "http://zthread.sourceforge.net/html/classZThread_1_1Condition.html"
contains the following statement.
"...
A Condition is not subject to spurious wakeup.
..."
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
than about C++, so I'm setting Followup-To back to comp.programming.threads.
Markus....@web.de (Markus Elfring) writes:
>> That's a lot of lines compared to while (!predicate) wait(condition);
>
> If you want to provide protection against spurious wakeups by a
> library function or method, you need to pass the predicate and the
> surrounding and corresponding code as (template) parameters.
The while loop protects against spurious wakeups too. It's not a
method, but so what? It can be wrapped in a macro if you insist on
a simpler syntax.
> Would you like to use a similar service quality like it is available
> for the algorithms "std::for_each()" and "std::find_if()"?
In these cases:
- it's not the only solution available: you can advance iterators
manually too;
- the corresponding loop is a bit more complex than this while loop,
so it's more often a win than here.
You can provide a function which takes the predicate as an object,
but I would not like to be forced to use it as the only option. It's
equivalent to the while loop anyway, so it doesn't provide anything
new. And the while loop is usually easier to write because C++ lacks
function closures.
In general I avoid C and C++ all, except for implementing a runtime
of a higher level language.
>> If the condition variable is wrapped together with the predicate, I
>> expect waiting to be equivalent to the above while loop, because this
>> is the classic pattern of waiting for a condition. In this case it
>> doesn't matter whether the "raw" condition wait has spurious wakeups
>> (the predicate should not have side effects and should not take too
>> long to compute). When the predicate is satisfied, the waiting
>> function returns.
>
> It does matter if the documentation leaves out that spurious wakeups
> can happen.
Then it's the documentation that should be fixed.
My model of usage of conditions assumes that:
- Each condition is associated with a predicate, which is consistently
used for waiting for the condition (but see below).
Technical note: in languages with function closures the predicate
is better physically attached to the condition; in languages without
closures an explicit while loop will be easier to use. The semantics
is the same in either case, as long as you stick to the conventions.
- The predicate doesn't have side effects and takes a short amount of
time, thus it doesn't matter how often it's called.
- Soon after each state change which *may* cause the predicate to
change from false to true and which is followed by releasing the
mutex, the thread calls Notify / pthread_cond_broadcast / notifyAll
/ PulseAll (whatever it's called in the given language or threading
library).
You may safely notify in more cases than needed (degrading
performance), but you must not notify less.
Even though the set of places where notification should be inserted
is roughly determined by the semantics of the code (modulo the fact
that it can be larger than needed if it's more convenient), the
programmer must do this himself. It's because it is impractical
for the compiler to detect all such cases automatically. An easily
automatizable safe approximation (e.g. notifying in all cases when
the mutex is being released) is too wasteful.
- The call to Notify can be optimized to Notify1 / pthread_cond_signal
/ notify / Pulse, in case we know that any waiting thread will cause
the predicate to become false again (or will notify another thread
itself), and thus at most one thread will benefit from being woken up.
This optimization is optional. You can stick to always notifying all
threads (degrading performance), but you must not apply it when more
than one thread should be woken up.
Again it is done manually because automatic detection by the
compiler of cases when it is safe to apply would be too hard.
Note that it's the broadcast version which is the conceptual
default. I think that languages which give the wake-up-one-thread-only
version a simpler name had made a worse choice of names.
Under these assumptions it doesn't matter whether the low-level
condition wait has spurious wakeups. There are no cases when the
predicate has become true, yet no waiting thread should be woken up
now, and the code would try to archieve that by omitting a call to
notify. This would not work (a thread could be woken up nevertheless
because of a spurious wakeup), but this never happens under these
assumptions. The code must be careful to notify in *all* cases when
the predicate might have changed to true. And if it did not change,
a spurious wakeup has no visible effect.
I believe these assumptions cover all practical uses of conditions,
i.e. using low-level condition primitives in ways not adhering to
the assumptions is never necessary. A minor speed-up caused by e.g.
evaluating the predicate after low-level waiting at least once
(if we know it was false before the loop) is really minor.
Well, in my language I allowed one extension of these assumptions
(after someone's advice in c.p.treads, and without a concrete
practical use case in mind): the predicate can be slightly different
in various invocations of Wait on the same condition, i.e. you can
supply a different predicate during waiting, which replaces the
predicate stored in the condition. All variations must be covered
by notification of course. This usage is probably very rare.
Markus Elfring
> use Condition Variable API" the only one that tried to encapsulate the
> predicate handling into a library?
> Do you know more libraries with a similar design that offer a
> "ConditionObject" implementation?
> http://groups.google.de/groups?threadm=353C2FA9.67C212C7%40erdas.com
The source code for the wait method by Eric Crahen seems to be a
different try in this direction.
http://cvs.sourceforge.net/viewcvs.py/zthread/zthread/src/ConditionImpl.h?rev=1.3&view=markup
Markus Elfring
> method, but so what? It can be wrapped in a macro if you insist on
> a simpler syntax.
You must remember to repeat this loop at all places of the wait call
if the library's implementation does not offer the suggested
protection. How big is the probability to forget its application?
Templates are the safe syntax for a lot of macros.
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
>> The while loop protects against spurious wakeups too. It's not a
>> method, but so what? It can be wrapped in a macro if you insist on
>> a simpler syntax.
>
> You must remember to repeat this loop at all places of the wait call
> if the library's implementation does not offer the suggested
> protection.
There is no substitute to remembering to use the correct API. If he
can forget that waiting should be in a loop, he can as well forget
your template name, or misuse its arguments.
The loop is usually necessary anyway, even without spurious wakeups:
- Another thread may get the mutex between the thread that notified
about change of the condition, and the thread which was woken up.
It can cause the condition to become false again.
- If several threads are woken up, it's probable that one of them will
make the condition false before others have a chance to run, and
they should wait again.
- It's can be convenient to notify when the condition *might* become
true when the thread is in a particular place, without precise
checking of all values of variables which influence the predicate.
Examples of this were in my elevator sample.
In general it's the responsibility of the waiting thread to ensure
that it really wants to proceed. Other threads must only ensure that
they will not miss any possibility of changing of the predicate,
but they may notify in more cases than needed: they don't have to
duplicate the work of checking the predicate precisely.
Thus the fact that waiting is associated wich a predicate which should
be tested in a loop should be taught when the concept of condition
variables is introduced. It is even said in X/Open documentation,
which is not a tutorial but a reference. It's just a part of the
knowledge about how to use condition variables.
I think it's easier to make a bug in emulating a first-class function
in C++, than in forgetting that pthread_cond_wait should be inside
'while' rather than 'if'.
> How big is the probability to forget its application?
> Templates are the safe syntax for a lot of macros.
If you value safety so much, using C++ is a bad idea (lots of
potential undefined behavior out there if you forget about other
things).
Markus Elfring
> be tested in a loop should be taught when the concept of condition
> variables is introduced. It is even said in X/Open documentation,
> which is not a tutorial but a reference. It's just a part of the
> knowledge about how to use condition variables.
>
> I think it's easier to make a bug in emulating a first-class function
> in C++, than in forgetting that pthread_cond_wait should be inside
> 'while' rather than 'if'.
Are you interested to encapsulate the predicate handling into a class?
Can a "convenient" wait method (without spurious wakeups) become part
of a library API?
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
> Are you interested to encapsulate the predicate handling into a class?
In languages with function closures - yes.
In languages without - no.
> Can a "convenient" wait method (without spurious wakeups) become part
> of a library API?
Depends on the above.
Markus Elfring
> In languages with function closures - yes.
> In languages without - no.
Would you like to show an example for such a "closure"?
Can it be emulated in C++?
I hope that the ZThread's wait method will not remain the only
implementation free of spurious wakeups.
Regards,
Markus
Joe Seigh
Markus Elfring wrote:
>
> > > Are you interested to encapsulate the predicate handling into a class?
> > In languages with function closures - yes.
> > In languages without - no.
>
> Would you like to show an example for such a "closure"?
> Can it be emulated in C++?
A C define should do it (error checking aside).
#define WaitForCond(cv, m, p) while (!(p)) pthread_cond_wait(cv, m)
>
> I hope that the ZThread's wait method will not remain the only
> implementation free of spurious wakeups.
>
You should probably use a different term than spurious. In Posix it
means wakeups not caused by a signal and has nothing to do with whether
a predicate is true or not on wakeup. You can have a predicate be
true on a spurious Posix wakeup.
Joe Seigh
Marcin 'Qrczak' Kowalczyk
>> > Are you interested to encapsulate the predicate handling into a class?
>> In languages with function closures - yes.
>> In languages without - no.
>
> Would you like to show an example for such a "closure"?
E.g. if the condition is "x > 0", it might look like this, depending
on the language:
Dylan: method () x > 0 end
Haskell: do v <- readIORef x; return (v > 0)
Kogut: {x > 0}
Lisp: #'(lambda () (> x 0))
; or just (> x 0) when waiting is wrapped by a macro
OCaml: fun () -> !x > 0
Perl: sub {$x > 0}
Python: lambda: x > 0
Ruby: {x > 0}
# must be written after arguments of a method call
Scheme: (lambda () (> x 0))
; or just (> x 0) when waiting is wrapped by a macro
Smalltalk: [x > 0]
SML: fn () => !x > 0
> Can it be emulated in C++?
Gt0(&x)
// when Gt0 is defined thus (at the toplevel):
class Gt0 {
int *var;
public:
Gt0(int *v): var(v) {}
bool operator() const {return *var > 0;}
};
> I hope that the ZThread's wait method will not remain the only
> implementation free of spurious wakeups.
IMHO wrapping the waiting loop in a function is not worth the price of
emulation of function closures in C++. It's simpler to remember to prefix
pthread_cond_wait by 'while' instead of 'if'.
Markus Elfring
> In languages without - no.
Would you like to adjust your view if you consider the following articles?
- http://en.wikipedia.org/wiki/Closure_%28computer_science%29
- http://en.wikipedia.org/wiki/Function_object
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
I've already said what my view is. I know what is a function closure
and I know how it can be emulated in C++. It doesn't change my view
that it's inconvenient when not supported by the language directly.
Markus Elfring
> means wakeups not caused by a signal and has nothing to do with whether
> a predicate is true or not on wakeup. You can have a predicate be
> true on a spurious Posix wakeup.
I'll try to find an alternative wording.
Would you appreciate a wait function/method in a higher level library
that will only return if a signal function/method was called?
Regards,
Markus
Markus Elfring
Would you like to offer a convenient wait method in Kogut's thread module?
Regards,
Markus
Markus Elfring
I imagine more convenience because of the code that a language's or
library's user can avoid to write.
I would like to keep the care and responsibility about the checking of
important predicates at a central place. I suggest to avoid the
distribution of while loops as a specific implementation detail.
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
>> In languages with function closures - yes.
>
> Would you like to offer a convenient wait method in Kogut's thread module?
What is provided now is as convenient as I could think of.
To make a condition:
let cond = Condition mutex {predicate};
To wait:
Wait cond;
or, for rare cases that you want a different predicate this time:
Wait cond {predicate};
In my implementation spurious wakeups can occur when the waiting
thread is interrupted by an asynchronous signal. It was simpler to
let it reevaluate the predicate than to keep track whether it was
notified while it was not waiting but handling a signal.
If the underlying implementation could cause spurious wakeups in other
cases, the API would look the same and would be used the same way. The
difference would be that sometimes the predicate is reevaluated even
if the condition has not been notified and the thread has not received
a signal.
The programmer should ensure that the condition is notified when it
can become true, so it should not be surprised if the thread finishes
waiting when the predicate is true, no matter whether he notified the
predicate or not. He should have notified it to make the behavior
predictable.
Marcin 'Qrczak' Kowalczyk
>> What is provided now is as convenient as I could think of.
> I would like to keep the care and responsibility about the checking
> of important predicates at a central place.
I don't understand. In Kogut predicates are typically written when the
condition is created. The code only includes calls to Wait, and I
don't see a way to avoid this.
> I suggest to avoid the distribution of while loops as a specific
> implementation detail.
The Wait function performs the loop itself.
Markus Elfring
> condition is created. The code only includes calls to Wait, and I
> don't see a way to avoid this.
I agree that a wait method must be called. But which variant is
protected against unsignalled wakeups?
> The Wait function performs the loop itself.
I have not recognized this detail in your previous descriptions about
Kogut's implementation. Is this not enough for protection against
spurious wakeups in your function?
Does this version still return because the wait may be "interrupted by
an asynchronous signal"?
Does your programming language support an "interruption exception"
like it is provided by Java?
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
> I agree that a wait method must be called. But which variant is
> protected against unsignalled wakeups?
Both. The only difference between Wait variants is whether the
predicate is specified when creating the condition, or when waiting.
The behavior is otherwise the same.
> Does this version still return because the wait may be "interrupted
> by an asynchronous signal"?
It reevaluates the predicate. If it's true, it returns; if it's still
false, it waits again.
So you can observe the wakeup by providing a predicate with side
effects, but Wait will not return until the predicate becomes true.
...Unless the signal handler has thrown an exception. In this case
Wait does not return at all but fails (after relocking the mutex)
and control is transferred to the appropriate exception handler.
> Does your programming language support an "interruption exception"
> like it is provided by Java?
It provides a mechanism of signals, which can be used for interruption
of a blocking operation or of computation in general. Signals are
described at various places in <http://kokogut.sourceforge.net/NEWS>.
Unfortunately there is no coherent description in one piece yet.
Markus Elfring
> false, it waits again.
Now it seems that your implementation for Kogut provides also the
service I am looking for in libraries. (That detail was not clear to
me before.)
Which source file do you recommend for reading in your CVS repository?
> Unfortunately there is no coherent description in one piece yet.
I am curious when it will become available with some clarifications.
Regards,
Markus
Marcin 'Qrczak' Kowalczyk
> Which source file do you recommend for reading in your CVS repository?
Depends on the goal.
The implementation of threads is in the module you have been looking at:
http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/lib/Core/Kokogut/Threads.ko?view=markup
There is lots of ugly low-level C code there: threads are a very
technical issue; the compiler itself almost doesn't deal with context
switching, so it is done using unusual function implementations; and
it should be fast, especially for those who don't use it explicitly.
I'm afraid this is one of the hardest module to analyse. It heavily
depends on internals of the runtime like function application protocol.
Some higher level things implemented in terms of the above:
http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/lib/Core/Threads.ko?view=markup
Example programs using threads:
http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/tests/threads/Elevator.ko?view=markup
http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/tests/threads/ReadersWriters.ko?view=markup
http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/tests/threads/Monitor.ko?view=markup
http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/examples/KoTetris/Tetris.ko?view=markup
Concurrency support in Kogut is quite young (two months) so there
isn't yet much code involved with threads.
>> Unfortunately there is no coherent description in one piece yet.
>
> I am curious when it will become available with some clarifications.
Hard to say... Currently I'm busy implementing networking. I must find
more time to sit down and write documentation.