RE: Buggy conditions

RE: Buggy conditions

[Medina, Aurelio]

To all,

First of all, I have just begun to use this Win32 PThreads library and at
this time I do not have a full understanding of its implementation.  Before
finding this library I had built my own simpler version of Pthreads for
WinNT.  Since I am currently using condition variables in my application I
looked into this issue.  Here is my observation:

The pthread_cond_wait() function must unlock the mutex and wait for the
condition ATOMICALLY.   If not, it is possible that after thread A unlocks
the mutex, thread B may acquire the mutex, change the condition variable,
and signal/broadcast the condition before thread A gets to wait for the
condition.  Thread A will be left waiting for a signal that might not get
regenerated and a condition variable that is set but can't get to because
its stuck in a wait state.  Hence we have a deadlock condition.

In my implementation I used the Win32 SignalObjectAndWait() (available on
WinNT 4.0 only) function to provide the necessary operation.  It provides
the ability to unlock a mutex and wait for an event in one atomic operation.
However, since the function takes only one wait object, I was only able to
implement pthread_cond_broadcast().  I like the effort put into this
library, which I must say is much farther along than mine, so I'll look into
a possible fix for this.  I first have to get familiar with the source code.
If the current PThreads library IS providing the mutex unlock and condition
wait in one atomic step somehow, then I misunderstood the source.

Other notes:
I have ported the pthread_rwlock_*() library and the POSIX Message Queue
(e.g. mq_open()) library to WinNT.  This code is almost entirely based on W.
Richard Stevens code from the book UNIX Network Programming Vol. 2.  Is
anyone interested in making this part of the Win32 Pthreads Library?

Aurelio Medina
Distributed Systems Management
Voice:	(312) 234-2105
Fax:	(312) 453-2105
mailto:aureliom@crt.com < mailto:aureliom@crt.com > 
http://cmi.il.nbgfn.com/gas/ < http://cmi.il.nbgfn.com/techserv/nsp > 


	-----Original Message-----
	From:	Peter Slacik [SMTP:Peter.Slacik@tatramed.sk]
	Sent:	Wednesday, June 23, 1999 11:54 AM
	To:	Pthreads-Win32 Mailing List
	Subject:	Buggy conditions

	Hi there,

	I've got problems with code which uses pthread_cond_timedwait() +
	pthread_cond_broadcast(). Sometimes threads deadlocks locking all
the same mutex
	(bound to the condition variable).

	It seems that if thread wakes up due to the timeout, it omits to
check whether the
	condition variable was broadcasted concurrently. The waiter returns,
but the
	signaling thread waits on cv->waitersDone event to be set. If the
last thread,
	which decrements cv->waiters, timed out in _pthread_sem_timedwait(),
	((result=errno)==0) is false and cv->waitersDone is never set. The
waiter then
	attempts to lock external mutex, locked by the broadcasting thread.

	Additionally, it turned out that cv's data is not protected enough,
e.g.
	cv->waiters may be decremented by thread waked up after timeout and
incremented by
	thread wishing to wait at the same time. Therefore cv->waitersLock
is really
	requested there.

	Just working around... I'm sorry to post untested code, I have no
opportunity to
	compile my attempt today to check it's correctness.

	One question more: What happens, if thread waits on semaphore
object, wakes up
	after timeout and then another (broadcasting) thread posts the
semaphore? Probably
	another thread will spuriously wake up next time, nothing more. Can
someone tell
	his/her opinion to this?

	--
	Peter Slacik

	 << File: condvar.c.diff >> 

Re: Buggy conditions

[Peter Slacik]

"Medina, Aurelio" wrote:

> The pthread_cond_wait() function must unlock the mutex and wait for the
> condition ATOMICALLY.   If not, it is possible that after thread A unlocks
> the mutex, thread B may acquire the mutex, change the condition variable,
> and signal/broadcast the condition before thread A gets to wait for the
> condition.

Yes, the signaling thread (or another waiter) could be able to preempt the
former waiter this way...

> Thread A will be left waiting for a signal that might not get
> regenerated and a condition variable that is set but can't get to because
> its stuck in a wait state.  Hence we have a deadlock condition.

... but no deadlock condition should arise (with my modifications). In my
opinion, the worst case would be that another thread which calls
pthread_cond_wait() would wake up sooner. I hope that no wakeup should be lost.

> If the current PThreads library IS providing the mutex unlock and condition
> wait in one atomic step somehow, then I misunderstood the source.

Although requested by the POSIX threads standard, PThreads library does not
provide this functionality correctly. Maybe "almost correctly"?

Peter Slacik

Re: Buggy conditions

[Aurelio Medina]

FYI,

After revisiting the source code, I better understand the implementation of
condition variables now.  The library does not provide a desired atomic
operation, but it does try to prevent deadlock using semaphores (I used
Win32 Events which would've caused deadlock).  As soon as possible, I will
test this implementation using my Win32/UNIX applications which constantly
has about 2-20 threads communicating with each other and hope no problems
occur.  I know that my code is well tested (i.e. in production use for well
over a year with no thread problems) and works with HP-UX and Solaris POSIX
Threads.  It should provide a very good test case for the Win32 PThread
library since it makes use of  condition variables, mutexes, thread
operations, and thread local storage.  Is there any issues I should know of
before using this library or should it just work?

Aurelio

-----Original Message-----
From: Peter Slacik <Peter.Slacik@tatramed.sk>
To: Medina, Aurelio <aureliom@crt.com>; Pthreads-Win32 Mailing List
<pthreads-win32@sourceware.cygnus.com>
Date: Thursday, June 24, 1999 9:46 AM
Subject: Re: Buggy conditions


>"Medina, Aurelio" wrote:
>
>> The pthread_cond_wait() function must unlock the mutex and wait for the
>> condition ATOMICALLY.   If not, it is possible that after thread A
unlocks
>> the mutex, thread B may acquire the mutex, change the condition variable,
>> and signal/broadcast the condition before thread A gets to wait for the
>> condition.
>
>Yes, the signaling thread (or another waiter) could be able to preempt the
>former waiter this way...
>
>> Thread A will be left waiting for a signal that might not get
>> regenerated and a condition variable that is set but can't get to because
>> its stuck in a wait state.  Hence we have a deadlock condition.
>
>... but no deadlock condition should arise (with my modifications). In my
>opinion, the worst case would be that another thread which calls
>pthread_cond_wait() would wake up sooner. I hope that no wakeup should be
lost.
>
>> If the current PThreads library IS providing the mutex unlock and
condition
>> wait in one atomic step somehow, then I misunderstood the source.
>
>Although requested by the POSIX threads standard, PThreads library does not
>provide this functionality correctly. Maybe "almost correctly"?
>
>Peter Slacik
>
>
>
>
>
>

Re: Buggy conditions

[Todd Owen]

At 06:53 PM 6/23/99 +0200, you wrote:
>One question more: What happens, if thread waits on semaphore object, wakes up
>after timeout and then another (broadcasting) thread posts the semaphore? Probably
>another thread will spuriously wake up next time, nothing more. Can someone tell
>his/her opinion to this?

As I understand it, that's the expected behaviour for a semaphore - if the semaphore value is greater than 0, wait()s will complete immediately.  So unlike condition variables, semaphores can "count", which sometimes makes them useful (such as in the old producer-consumer problem).

Todd.

....................please cut here....................
 
Todd Owen <towen@nw.com.au>
 
=== Netway Technologies ===
http://www.nw.com.au

RE: Buggy conditions

[Bossom, John]

Before making tweeks and changes with regards to
the implementation of the pthread condition variables,
please thoroughly read the following paper by
Professor Douglas Schmidt, from which this implementation
was derived. Professor Schmidt, from Washington University,
heads up the ACE (Adaptive Communication Environment) project.

This paper discusses the issues with regards to implementing
pthread condition variables on Win32.

http://www.cs.wustl.edu/~schmidt/win32-cv-1.html

John.

-----Original Message-----
From: Peter Slacik [ mailto:Peter.Slacik@tatramed.sk ]
Sent: Thursday, June 24, 1999 10:45 AM
To: Medina, Aurelio; Pthreads-Win32 Mailing List
Subject: Re: Buggy conditions


"Medina, Aurelio" wrote:

> The pthread_cond_wait() function must unlock the mutex and wait for the
> condition ATOMICALLY.   If not, it is possible that after thread A unlocks
> the mutex, thread B may acquire the mutex, change the condition variable,
> and signal/broadcast the condition before thread A gets to wait for the
> condition.

Yes, the signaling thread (or another waiter) could be able to preempt the
former waiter this way...

> Thread A will be left waiting for a signal that might not get
> regenerated and a condition variable that is set but can't get to because
> its stuck in a wait state.  Hence we have a deadlock condition.

... but no deadlock condition should arise (with my modifications). In my
opinion, the worst case would be that another thread which calls
pthread_cond_wait() would wake up sooner. I hope that no wakeup should be
lost.

> If the current PThreads library IS providing the mutex unlock and
condition
> wait in one atomic step somehow, then I misunderstood the source.

Although requested by the POSIX threads standard, PThreads library does not
provide this functionality correctly. Maybe "almost correctly"?

Peter Slacik

Buggy conditions

[Peter Slacik]

Hi there,

I've got problems with code which uses pthread_cond_timedwait() +
pthread_cond_broadcast(). Sometimes threads deadlocks locking all the same mutex
(bound to the condition variable).

It seems that if thread wakes up due to the timeout, it omits to check whether the
condition variable was broadcasted concurrently. The waiter returns, but the
signaling thread waits on cv->waitersDone event to be set. If the last thread,
which decrements cv->waiters, timed out in _pthread_sem_timedwait(),
((result=errno)==0) is false and cv->waitersDone is never set. The waiter then
attempts to lock external mutex, locked by the broadcasting thread.

Additionally, it turned out that cv's data is not protected enough, e.g.
cv->waiters may be decremented by thread waked up after timeout and incremented by
thread wishing to wait at the same time. Therefore cv->waitersLock is really
requested there.

Just working around... I'm sorry to post untested code, I have no opportunity to
compile my attempt today to check it's correctness.

One question more: What happens, if thread waits on semaphore object, wakes up
after timeout and then another (broadcasting) thread posts the semaphore? Probably
another thread will spuriously wake up next time, nothing more. Can someone tell
his/her opinion to this?

--
Peter Slacik