thread control by mutex, predicates and conditions puzzle

thread control by mutex, predicates and conditions puzzle

Post by rolan » Tue, 04 Jan 2005 01:03:07


I am seeking for help on a problem that
puzzles me for a while yet.


Given:
Multiple threads t1, t2, ...
A variable a,
and N variables v1, ... vN.

a is holding a state that controls global
thread (t1) behaviour, while v1,...vN deal with
interthread communication issues. E.g. a
contains a flag requesting the thread to abort
whatever it is doing and to restart.
v1..vN control buffers and the like.

My question now is how to protect the variables
correctly by mutexes and how to assign
predicates and conditions?

One obvious solution to me, is to have exactly
one mutex, one predicate and one condition.

So the next question is: Is this the only
valid solution possible?

I am afraid yes, but I did not yet manage
to prove this formally.

Some thoughts:
Assume v1 is evaluated by predicate p1, v2 by p2, ....
Variable a is evaluated by predicate pa.

Further p1 has condition c1, p2 has c2, ... and pa has ca.

Since evaluating any of predicates p1,..pN does not
reveal information about pa I need to modify my
predicates as following:
p1' = pa || p1
p2' = pa || p2
...
pN' = pa || pN
and associated conditions c1' ... cN'.

Now since a condition can be bound at most to a single
mutex, when performing a wait on any of c1,...cN I am
forced to use this mutex also for protection of a.

If it were different in order to change state of a, an
external thread would need to know on which of the
c1',...cN' the thread is currently blocked. It could then
lock a hypothetical mutex and change a. However this
information is not available. The only remedy is to have
a single mutex.

There still are mutiple predicates p1',... and conditions
c1',...
What happens when I change the state of a?
I lock the mutex, change a and then I need to
signal _all_ c1', ... cN'. (Since I do not know from
outside on which ci' the thread is currently blocking,
if at all.)

Since this is impractical from a source code
maintanance perspective (would need to add a signaling
function whenever a new predicate is added) I am stuck
with exactly one predicate condition pair.

If this result indeed is true I am asking if there is
another pattern that helps me solve this kind of problem.
If it is not true, and I am overlooking something important
I would kindly ask to point me to where I am wrong.

Thank you for your attention.

Roland
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by Jomu » Tue, 04 Jan 2005 04:01:50

Single lock will defeat most of thread usability. IMO, threads are all
about decentralization and paralelization, and smallest number of any
kind of congestion points possible. I don't really understand how that
general scheme can help you in thread programming, but your a is too
much of congestion point for healthy thread program. Just avoid it.

 
 
 

thread control by mutex, predicates and conditions puzzle

Post by rolan » Tue, 04 Jan 2005 16:03:21


True.


You might have got me wrong, but I am in no way suggesting this as
anything like a "general scheme". On the contrary I do find this
construct very problematic.


This is exactly my point: How can I avoid this sucessfully, while
still beeing able to have a "global stop/action flag"?

I.e. how can I then achieve the below behaviour correctly?



> E.g. a
> contains a flag requesting the thread to abort
> whatever it is doing and to restart.

Roland
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by Jomu » Thu, 06 Jan 2005 00:04:25

You can signal threads, and this is what I am using to alert threads
(in Modula-3 environment speak) so they can raise Alerted exception and
terminate when I need them to. This is higher level behaviour and can
be something else than you ask for. In any case, you can use such a
handler to set some flag specific to thread and check for it when
appropriate. I am using SIG39 for this and also for garbage collector's
stop-while-i-check.

This global flag can be something youcan use in your predicates, I
think.
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by rolan » Thu, 06 Jan 2005 02:56:47


So if I understand you right you are saying that the problem using
posix threads alone cannot be solved other than by my single
mutex/condition/predicate solution?

Using signals on the other hand is highly nonpartable I guess.

Roland
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by Jomu » Sat, 08 Jan 2005 19:18:34

Of course it is not nonportable. POSIX defines signaling semantics, and
it is as portable as POSIX 4a APIs.

dd
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by rolan » Sat, 08 Jan 2005 23:58:12


Do you mean, a pthread_cond_wait _must_ wakeup on a signal on any
conformant pthreads implementation?

BTW.: In the meantime I found another solution to the original problem,
which will do without signals:

Given:

a ... global state
ma ... mutex protecting global state

v ... a variable
mv ... mutex protecting variable v
pv ... predicate about v
cv ... condition for pv changed

Now define:
pa ... predicate defined as following:
bool pa() {
lock ma
evaluate predicate
unlock ma
return predicate value
}

refc ... a reference (pointer) to a condition
refm ... a reference (pointer) to a mutex

Usage:
When it is time to wait on cv

lock mv
refc = cv
refm = mv
while(!pa && !pv) wait(cv, mv)
evaluate a and /or v
unlock mv

Another thread changes a, and signals:

lock ma
a = whatever
lock refm
notify_all(refc)
unlock refm
unlock ma

Another thread changes v, and signals:

lock mv
v = whatever
notify_one(cv)
unlock mv

Remark:
notify_all is necessary, since we cannot know how many
waiters are there. The waiting and notifcation functions of
course should be wrapped into a function. Also the problem
of how to get access to the ref's has to be solved. But this
is a different matter.
Note that a cannot be changed without holding a lock to the
refm mutex. In this way it is implicitely used to protect
a as well.

Do you see any problems with this solution?

Roland
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by Jomu » Sun, 09 Jan 2005 03:15:32

There are signals which will get you out of pthread_cond_wait, probably
all (I can't recall any exceptions). Your thread waiting on condition
will get EINTR as result of pthread_cond_wait and there you can handle
situtation. Of course, signal itself is supposed to be handled in it's
handler and after getting EINTR it is up to your thread to lookup state
changed by that handler.

As for your solution, I think I am a bit too practical to see through
all this generalization :). Other elements are looking fine, except
this notify_all - you have to pthread_cond_broadcast them all (or
rewrite pthread_cond_wait so it marks used conditions at moment -
ouch). To register them, you have to use protected list or something
similar, and to notify them, you have to lock it, iterate rhtough and
broadcast every one. Very intensive variable update operation, IMO :).

What is this stop/start action thing? Do you want to freeze your
threads only at some points or wherever they happen to be when you stop
them?

dd
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by Joseph Sei » Sun, 09 Jan 2005 04:05:27


Most implementations will handle EINTR as a spurious wakeup but you
cannot depend on that behavior. The implementation is allowed to go
back into wait.

--
Joe Seigh
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by rolan » Sun, 09 Jan 2005 04:36:11


Say, your thread is blocking on IO. Now an external thread that is in
charge of master control needs to tell: quit and restart IO.
But I do not want to cancel the entire thread! (Imagine I have other
valuable
state information in my thrad.)

How should I go for it when I
1) want a single thread wide master control while still be able to
wait on different things during the threads lifetime
2) _and_ write code with portability in mind? (The IO clearly is
highly system dependant.)

I would be very glad if you could point me to such a pattern, since
I am too a bit concerned of the "thundering herd" problem my broadcast
could cause.

Roland
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by David Schw » Sun, 09 Jan 2005 12:35:12


Why not just avoid blocking on I/O?


How you do this depends upon the rest of your architecture, but
basically you just remove the I/O from the list of I/Os that your I/O-doing
threads use to decide what I/O to do.


Use non-blocking I/O. The threads that do I/O keep state on what I/Os
they're working on, and other threads can access that state information with
suitable locks. You're setting things up to be much harder than they have to
be.

DS
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by Jomu » Sun, 09 Jan 2005 20:36:47

I do not expect pthread_cond_wait (or any other blocked operation,
where other operations are as needed to be covered as pthread_*) to
return anything, I just sigwait() in signal handler for "resume"
signal. For this signal, I use pthread_kill(), of course.

My signaling thread uses sem_* family to communicate success of "pause"
from suspended thread to suspendor thread. When suspendor gets
confirmations from all suspended threads (sem_ count becomes equal to
number of signaled threads) it proceeds. Suspendor actions are covered
by general mutex which covers critical thread operations. When
suspendor completes it's task, it resumes all threads with same signal,
which all suspended threads are sigwait()-ing.

This is, of course, very general. For interested parties,
implementation (in Modula-3) is at
http://www.yqcomputer.com/ ~dragisha/gc-pthread .

dd




probably
condition
handle
it's
state
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by Jomu » Sun, 09 Jan 2005 20:47:07


stop

For I/O in threads, pthread_kill will probably do, as I/O operations
are expected to return with EINTR (/me expects someone will correct me
here if it is no always true, ie. portable). But, your I/O operations
must learn this and handle EINTRs, of course.


Of course not.


Take a look at my garbage collector solution (link in other post),
and pls tell me if ideas from there cover your needs.


My mantra is "POSIX only" :). I do take a shortcut from time to time,
of course, but always trying to play it safe.

broadcast

dd
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by rolan » Sun, 09 Jan 2005 21:24:40


Ok, I see I have mixed things here. Bad example from me.
As you can see from my OP I am actually blocking on a wait
to a condvar.

My question can be rephrased as:
When I am waiting on a particular condvar, how can I portably
wake up the thread to notify it from some global state change?

I am almost sure that wait will not EINTR on windows platform,
so I think this is not a portable solution.

Roland
 
 
 

thread control by mutex, predicates and conditions puzzle

Post by Joseph Sei » Sun, 09 Jan 2005 22:17:46


pthread_cond_wait does not return EINTR under any circumstances.
pthread_cond_wait is not required to do anything upon receipt of
a unix signal during wait. It can continue waiting or it can
return as a spurious wakeup entirely at the choice at the implementation.

You comment about sigwait is a non sequitur and has nothing to
do with pthread_cond_wait. You shouldn't top post. Not only
is it annoying but you managed to confuse yourself. Go back
as read your previous comment about signals getting you out
of pthread_cond_wait. It's quoted at the top of this post if
you've forgotten.

Joe Seigh

Joe Seigh