You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@apr.apache.org by "Victor J. Orlikowski" <v....@gte.net> on 2001/08/01 00:31:23 UTC
Re: Conditionals...
Rather, let's be more clear.
bool held=false;
acquire(mutex2);
release(mutex1);
held=false;
release(mutex2);
nap: sleep();
acquire(mutex2);
if(held) goto nap;
acquire(mutex1);
held=true;
release(mutex2);
That explain it somewhat better? ;)
Victor
--
Victor J. Orlikowski | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com
Re: Conditionals...
Posted by Jeff Trawick <tr...@attglobal.net>.
"Roy T. Fielding" <fi...@ebuilt.com> writes:
> > > All variables are an approximation -- cosmic rays can change the value as
> > > well, with only a slightly smaller probability than mid-increment time
> > > slices in a non-test system.
> >
> > hmmm... I've seen many fixes needed for several instruction sequences
> > which did not handle being interrupted (i.e. broken serialization);
> > unclear how many of the unrepeatable bugs are due to cosmic rays...
> > as a programmer I wouldn't want to assume that any of them
> > are... certainly the customers I'm familiar with would not accept that
> > as an answer :)
>
> Due to mid-increment time slices? All of the race conditions I have seen
> in practice have been due to I/O operations (not register loads).
mid-increment? I don't recall any (in the implementation language
used on the product, a special keyword on a variable declaration
caused compare-and-swap logic to be generated; very hard to screw up)
other several instruction sequences? yep (one cause was that even
when the proper instruction sequence was known by the programmer the
compiler would sometimes play with the specified asm :( )
--
Jeff Trawick | trawick@attglobal.net | PGP public key at web site:
http://www.geocities.com/SiliconValley/Park/9289/
Born in Roswell... married an alien...
Re: Conditionals...
Posted by "Roy T. Fielding" <fi...@ebuilt.com>.
> > All variables are an approximation -- cosmic rays can change the value as
> > well, with only a slightly smaller probability than mid-increment time
> > slices in a non-test system.
>
> hmmm... I've seen many fixes needed for several instruction sequences
> which did not handle being interrupted (i.e. broken serialization);
> unclear how many of the unrepeatable bugs are due to cosmic rays...
> as a programmer I wouldn't want to assume that any of them
> are... certainly the customers I'm familiar with would not accept that
> as an answer :)
Due to mid-increment time slices? All of the race conditions I have seen
in practice have been due to I/O operations (not register loads).
In any case, I have no doubt that such a condition can occur. I am simply
saying that I don't care, and neither will the customer if I have written
the code correctly. If I did care, *then* I would use locks.
....Roy
Re: Conditionals...
Posted by Jeff Trawick <tr...@attglobal.net>.
"Roy T. Fielding" <fi...@ebuilt.com> writes:
> > > Likewise, even a mid-update context
> > > switch doesn't matter for a variable that is only incremented/decremented.
> >
> > only if the variable is used for an approximation :)
>
> I said only one writer.
Well, you certainly know how to interpret what you write and I
certainly didn't :)
> All variables are an approximation -- cosmic rays can change the value as
> well, with only a slightly smaller probability than mid-increment time
> slices in a non-test system.
hmmm... I've seen many fixes needed for several instruction sequences
which did not handle being interrupted (i.e. broken serialization);
unclear how many of the unrepeatable bugs are due to cosmic rays...
as a programmer I wouldn't want to assume that any of them
are... certainly the customers I'm familiar with would not accept that
as an answer :)
--
Jeff Trawick | trawick@attglobal.net | PGP public key at web site:
http://www.geocities.com/SiliconValley/Park/9289/
Born in Roswell... married an alien...
Re: Conditionals...
Posted by "Roy T. Fielding" <fi...@ebuilt.com>.
> > Likewise, even a mid-update context
> > switch doesn't matter for a variable that is only incremented/decremented.
>
> only if the variable is used for an approximation :)
I said only one writer.
All variables are an approximation -- cosmic rays can change the value as
well, with only a slightly smaller probability than mid-increment time
slices in a non-test system. Unless there is a bug in the code, reading
a counter in the scoreboard never needs a lock.
....Roy
Re: Conditionals...
Posted by Jeff Trawick <tr...@attglobal.net>.
"Roy T. Fielding" <fi...@ebuilt.com> writes:
> Likewise, even a mid-update context
> switch doesn't matter for a variable that is only incremented/decremented.
only if the variable is used for an approximation :)
x = 0
thread1 thread2
load x into reg A load x into reg A
TIMESLICE increment reg A
(sleeping) store reg A at x
DISPATCH
increment reg A
store reg A at x
x has been incremented twice and now has value 1
compare-and-swap can be used for this.
--
Jeff Trawick | trawick@attglobal.net | PGP public key at web site:
http://www.geocities.com/SiliconValley/Park/9289/
Born in Roswell... married an alien...
Re: Conditionals...
Posted by "Roy T. Fielding" <fi...@ebuilt.com>.
> Simply reading from a shared variable is not atomic. All accesses to a
> shared variable must be synchronized (or "serialized", if you prefer)
> with some form of mutual exclusion. (An example of this is on
> Solaris/Sparc, where a context switch can occur half-way through an update to
> a longword (or is it a word, I'm not sure).
Not all shared memory is created equal. Simple variables that only have
one writer at a time by nature do not require additional locking.
That is how the old scoreboard worked. Likewise, even a mid-update context
switch doesn't matter for a variable that is only incremented/decremented.
....Roy
Re: Conditionals...
Posted by "Victor J. Orlikowski" <v....@gte.net>.
Urgh...
Variable reuse, Victor, variable reuse.
<Victor hits head on desk, noting that he was obviously on vacation.>
> int Acquire_Condition_Lock(struct Condition *c) {
> int thrid = thread_id_of(current_thread);
> if (c->thread_id == thrid) exit(1); /* Deadlock */
> acquire(*(c->lock));
> acquire(c->condlock);
> c->thread_id = thread_id_of(current_thread);
> release(c->condlock);
> return 0;
> }
>
Make that:
int Acquire_Condition_Lock(struct Condition *c) {
int thrid = thread_id_of(current_thread);
if (c->thread_id == thrid) exit(1); /* Deadlock */
acquire(*(c->lock));
acquire(c->condlock);
c->thread_id = thrid;
release(c->condlock);
return 0;
}
Victor
--
Victor J. Orlikowski | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com
Re: Conditionals...
Posted by "Victor J. Orlikowski" <v....@gte.net>.
On Friday, 3 Aug 2001, at 15:23:22,
Victor J. Orlikowski wrote:
> How about:
>
> int Acquire_Condition_Lock(struct Condition *c) {
> acquire(c->condlock);
> acquire(*(c->lock));
> c->thread_id = thread_id_of(current_thread);
> release(c->condlock);
> return 0;
> }
>
> Hence, we simply block trying to acquire the condlock.
> Once we have the condlock, all is well, no?
>
Hum, answer my own question. No.
While driving down for vacation, I thought of all the possible
deadlocks.
However, Acquire_Condition_Lock is the only one casuing them.
The following implmentation should cure it all.
int Acquire_Condition_Lock(struct Condition *c) {
int thrid = thread_id_of(current_thread);
if (c->thread_id == thrid) exit(1); /* Deadlock */
acquire(*(c->lock));
acquire(c->condlock);
c->thread_id = thread_id_of(current_thread);
release(c->condlock);
return 0;
}
As long as we always only maintain the state of c->thread_id while
holding c->lock, all will be fine. Furthermore, reads from
c->thread_id should be safe, as all write thereto should be serialized
in the implementation that includes the above Acquire_Condition_Lock.
Victor
--
Victor J. Orlikowski | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com
Re: Conditionals...
Posted by "Victor J. Orlikowski" <v....@gte.net>.
> Simply reading from a shared variable is not atomic. All accesses to a
> shared variable must be synchronized (or "serialized", if you prefer)
> with some form of mutual exclusion. (An example of this is on
> Solaris/Sparc, where a context switch can occur half-way through an update to
> a longword (or is it a word, I'm not sure).
>
Since this is a problem, we can simply protect the test with the
condlock. Not a big change.
> > int Acquire_Condition_Lock(struct Condition *c) {
> > if (c->thread_id != -1)
> > return -1; /* Somebody's got the lock */
> > acquire(c->condlock);
> > acquire(*(c->lock));
> > c->thread_id = thread_id_of(current_thread);
> > release(c->condlock);
> > return 0;
> > }
>
> Unfortunately this won't work. If two threads are trying to signal
> they will both have to run Acquire_Condition_Lock(). The second one
> will fail. What then, spin? No.
All right. This is a valid problem.
How about:
int Acquire_Condition_Lock(struct Condition *c) {
acquire(c->condlock);
acquire(*(c->lock));
c->thread_id = thread_id_of(current_thread);
release(c->condlock);
return 0;
}
Hence, we simply block trying to acquire the condlock.
Once we have the condlock, all is well, no?
> Moving ahead, IIRC we are confident we can safely implement condition
> variables on Win32 and Unix. What do we have for beos and os2? Are there
> other platforms that will be a problem?
>
>
> (For the curious, there is an excellent paper by Douglas C. Schmidt and Irfan
> Pyarali at http://www.cs.wustl.edu/~schmidt/win32-cv-1.html called
> _Strategies for Implementing POSIX Condition Variables on Win32_. The
> paper includes multiple strategies for implementing POSIX CVs.)
>
I'll be sure to look at these.
Victor
--
Victor J. Orlikowski | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com
Re: Conditionals...
Posted by Aaron Bannert <aa...@ebuilt.com>.
On Thu, Aug 02, 2001 at 02:46:59PM -0400, Victor J. Orlikowski wrote:
> Aaron Bannert writes:
> > On Thu, Aug 02, 2001 at 12:09:05PM -0400, Victor J. Orlikowski wrote:
> > > Aaron Bannert writes:
> <snip>
> > Fair enough. The above is much more clear, but there is now another
> > problem...
> >
> > >
> > > Does the new code fit better with what you expect?
> >
> > In your above example, how can more than one thread be wait()ing on
> > a condition, if only the thread that has the "c->lock" may call
> > wait()?
> >
>
> Because, in a Condition, the thread that calls Wait releases the lock.
> Hence, another thread may acquire the lock, and call Wait thereafter.
> This will require another two functions, but that is simple enough.
>
> > Also, Signal() and Broadcast() may not be MT-safe, as they perform
> > operations on c->thread_id that are non-exclusive and may be non-atomic
> > on some platforms.
> >
>
> How?
> Only one thread may obtain c->condlock.
> Hence, only one thread may be listed in thread_id.
> We must simply protect all manipulation of c->thread_id with the condlock.
> Reading the thread_id under this implementation is perfectly safe.
Simply reading from a shared variable is not atomic. All accesses to a
shared variable must be synchronized (or "serialized", if you prefer)
with some form of mutual exclusion. (An example of this is on
Solaris/Sparc, where a context switch can occur half-way through an update to
a longword (or is it a word, I'm not sure).
> Sigh. Let me give you the rest of the puzzle.
> Let Condition have a linked list of the following structure.
>
> struct Waiter {
> Semaphore *sem;
> Waiter *next;
> Waiter *prev;
> };
>
> In Wait, allocate a new Waiter structure, with its Semaphore
> initialized to zero. Making sure to protect appends to the list with
> condlock, append this Waiter structure to the list, and then do a wait
> on the Semaphore within it.
>
> In Signal, again protect the manipulation of the list with the
> condlock. Now, remove the Waiter at the head of the list, and post on
> its semaphore.
>
> In Broadcast, once again protect accesses of the list via condlock.
> Now, remove Waiters, one at a time, from the list, posting on the
> semaphore of each as you remove it.
>
> Here is the pseudocode for the finished version (please forgive the
> C++ -isms). NOTE: this is missing many needed checks for NULL values.
>
> struct Waiter {
> Semaphore *sem;
> Waiter *next;
> Waiter *prev;
> };
>
> struct Condition {
> mutex *lock; /* mutex associated with condition */
> int thread_id; /* Current holder of the lock */
> struct Waiter *list; /* list of waiters */
> struct Waiter *tail; /* end of list */
> mutex condlock;
> };
>
> void Wait(struct Condition *c) {
> Waiter *wait;
> if (c->thread_id != thread_id_of(current_thread))
> exit(-1); /* Only the holder of the lock may call wait */
> wait = new Waiter;
> wait->sem = new Semaphore(0); /* Initialized to 0 */
> wait->next = NULL;
> wait->prev = NULL;
> acquire(c->condlock);
> l->thread_id = -1; /* or whatever invalid thread value */
> if (!(c->list))
> c->tail = wait;
> wait->next = c->list;
> c->list = wait;
> release(c->condlock);
> release(*(c->lock));
> wait(wait->sem);
> acquire(*(c->lock));
> acquire(c->condlock);
> c->thread_id = thread_id_of(current_thread);
> release(c->condlock);
> delete wait->sem;
> delete wait;
> }
>
> void Signal(struct Condition *c) {
> Waiter *wake;
> if (c->thread_id != thread_id_of(current_thread))
> exit(-1); /* Only the holder of the lock may call signal */
> acquire(c->condlock);
> if (c->tail) {
> wake = c->tail;
> c->tail = wake->prev;
> post(wake->sem);
> }
> release(c->condlock);
> }
>
> void Broadcast(struct Condition *c) {
> Waiter *wake;
> if (c->thread_id != thread_id_of(current_thread))
> exit(-1); /* Only the holder of the lock may call broadcast */
> acquire(c->condlock);
> while (c->tail) {
> wake = c->tail;
> c->tail = wake->prev;
> post(wake->sem);
> }
> release(c->condlock);
> }
>
> /* 0 for success, -1 on error */
> int Acquire_Condition_Lock(struct Condition *c) {
> if (c->thread_id != -1)
> return -1; /* Somebody's got the lock */
> acquire(c->condlock);
> acquire(*(c->lock));
> c->thread_id = thread_id_of(current_thread);
> release(c->condlock);
> return 0;
> }
Unfortunately this won't work. If two threads are trying to signal
they will both have to run Acquire_Condition_Lock(). The second one
will fail. What then, spin? No.
>
> int Release_Condition_Lock(struct Condition *c) {
> if (c->thread_id != thread_id_of(current_thread))
> return -1; /* We don't hold the lock */
> acquire(c->condlock);
> release(*(c->lock));
> c->thread_id = -1;
> release(c->condlock);
> return 0;
> }
>
> void Condition_Init(struct Condition *c, Lock *l) {
> c->condlock = new mutex;
> acquire(c->condlock);
> c->lock = l;
> c->thread_id = -1;
> c->list = c->tail = NULL;
> release(c->condlock);
> }
>
> void Condition_Destroy(struct Condition *c) {
> acquire(c->condlock);
> if (c->list || (c->thread_id != -1))
> exit(-1); /* The list should be clear before destroying, and */
> /* the lock unlocked */
> c->lock = NULL;
> release(c->condlock);
> delete c->condlock;
> delete c;
> }
>
> As you can see, thread_id manipulation only occurs in Condition_Init,
> Acquire_Condition_Lock, Release_Condition_Lock, and Wait, which
> are the only functions to manipulate c->lock beyond Condition_Destroy.
> Reading the thread_id simply serves as a sanity check in all of these functions.
>
> Victor
> --
> Victor J. Orlikowski | The Wall is Down, But the Threat Remains!
> ==================================================================
> v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com
Moving ahead, IIRC we are confident we can safely implement condition
variables on Win32 and Unix. What do we have for beos and os2? Are there
other platforms that will be a problem?
(For the curious, there is an excellent paper by Douglas C. Schmidt and Irfan
Pyarali at http://www.cs.wustl.edu/~schmidt/win32-cv-1.html called
_Strategies for Implementing POSIX Condition Variables on Win32_. The
paper includes multiple strategies for implementing POSIX CVs.)
-aaron
Re: Conditionals...
Posted by "Victor J. Orlikowski" <v....@gte.net>.
Aaron Bannert writes:
> On Thu, Aug 02, 2001 at 12:09:05PM -0400, Victor J. Orlikowski wrote:
> > Aaron Bannert writes:
<snip>
> Fair enough. The above is much more clear, but there is now another
> problem...
>
> >
> > Does the new code fit better with what you expect?
>
> In your above example, how can more than one thread be wait()ing on
> a condition, if only the thread that has the "c->lock" may call
> wait()?
>
Because, in a Condition, the thread that calls Wait releases the lock.
Hence, another thread may acquire the lock, and call Wait thereafter.
This will require another two functions, but that is simple enough.
> Also, Signal() and Broadcast() may not be MT-safe, as they perform
> operations on c->thread_id that are non-exclusive and may be non-atomic
> on some platforms.
>
How?
Only one thread may obtain c->condlock.
Hence, only one thread may be listed in thread_id.
We must simply protect all manipulation of c->thread_id with the condlock.
Reading the thread_id under this implementation is perfectly safe.
Sigh. Let me give you the rest of the puzzle.
Let Condition have a linked list of the following structure.
struct Waiter {
Semaphore *sem;
Waiter *next;
Waiter *prev;
};
In Wait, allocate a new Waiter structure, with its Semaphore
initialized to zero. Making sure to protect appends to the list with
condlock, append this Waiter structure to the list, and then do a wait
on the Semaphore within it.
In Signal, again protect the manipulation of the list with the
condlock. Now, remove the Waiter at the head of the list, and post on
its semaphore.
In Broadcast, once again protect accesses of the list via condlock.
Now, remove Waiters, one at a time, from the list, posting on the
semaphore of each as you remove it.
Here is the pseudocode for the finished version (please forgive the
C++ -isms). NOTE: this is missing many needed checks for NULL values.
struct Waiter {
Semaphore *sem;
Waiter *next;
Waiter *prev;
};
struct Condition {
mutex *lock; /* mutex associated with condition */
int thread_id; /* Current holder of the lock */
struct Waiter *list; /* list of waiters */
struct Waiter *tail; /* end of list */
mutex condlock;
};
void Wait(struct Condition *c) {
Waiter *wait;
if (c->thread_id != thread_id_of(current_thread))
exit(-1); /* Only the holder of the lock may call wait */
wait = new Waiter;
wait->sem = new Semaphore(0); /* Initialized to 0 */
wait->next = NULL;
wait->prev = NULL;
acquire(c->condlock);
l->thread_id = -1; /* or whatever invalid thread value */
if (!(c->list))
c->tail = wait;
wait->next = c->list;
c->list = wait;
release(c->condlock);
release(*(c->lock));
wait(wait->sem);
acquire(*(c->lock));
acquire(c->condlock);
c->thread_id = thread_id_of(current_thread);
release(c->condlock);
delete wait->sem;
delete wait;
}
void Signal(struct Condition *c) {
Waiter *wake;
if (c->thread_id != thread_id_of(current_thread))
exit(-1); /* Only the holder of the lock may call signal */
acquire(c->condlock);
if (c->tail) {
wake = c->tail;
c->tail = wake->prev;
post(wake->sem);
}
release(c->condlock);
}
void Broadcast(struct Condition *c) {
Waiter *wake;
if (c->thread_id != thread_id_of(current_thread))
exit(-1); /* Only the holder of the lock may call broadcast */
acquire(c->condlock);
while (c->tail) {
wake = c->tail;
c->tail = wake->prev;
post(wake->sem);
}
release(c->condlock);
}
/* 0 for success, -1 on error */
int Acquire_Condition_Lock(struct Condition *c) {
if (c->thread_id != -1)
return -1; /* Somebody's got the lock */
acquire(c->condlock);
acquire(*(c->lock));
c->thread_id = thread_id_of(current_thread);
release(c->condlock);
return 0;
}
int Release_Condition_Lock(struct Condition *c) {
if (c->thread_id != thread_id_of(current_thread))
return -1; /* We don't hold the lock */
acquire(c->condlock);
release(*(c->lock));
c->thread_id = -1;
release(c->condlock);
return 0;
}
void Condition_Init(struct Condition *c, Lock *l) {
c->condlock = new mutex;
acquire(c->condlock);
c->lock = l;
c->thread_id = -1;
c->list = c->tail = NULL;
release(c->condlock);
}
void Condition_Destroy(struct Condition *c) {
acquire(c->condlock);
if (c->list || (c->thread_id != -1))
exit(-1); /* The list should be clear before destroying, and */
/* the lock unlocked */
c->lock = NULL;
release(c->condlock);
delete c->condlock;
delete c;
}
As you can see, thread_id manipulation only occurs in Condition_Init,
Acquire_Condition_Lock, Release_Condition_Lock, and Wait, which
are the only functions to manipulate c->lock beyond Condition_Destroy.
Reading the thread_id simply serves as a sanity check in all of these functions.
Victor
--
Victor J. Orlikowski | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com
Re: Conditionals...
Posted by Aaron Bannert <aa...@ebuilt.com>.
On Thu, Aug 02, 2001 at 12:09:05PM -0400, Victor J. Orlikowski wrote:
> Aaron Bannert writes:
> > On Tue, Jul 31, 2001 at 06:31:23PM -0400, Victor J. Orlikowski wrote:
> > > Rather, let's be more clear.
> > >
> <snip>
> >
> My fault. That code is more than slightly wrong, now that I look
> at it better. Let's examine the following pseudocode, which closely
> follows some of my undergraduate OS work at the university.
> I will not be doing any checking for null values, etc.
>
> struct Condition {
> mutex *lock; /* mutex associated with condition */
> int thread_id; /* Current holder of the lock */
> mutex condlock;
> };
>
> void Wait(struct Condition *c) {
> acquire(c->condlock);
> if (c->thread_id != thread_id_of(current_thread)) {
> release(c->condlock);
> exit(-1); /* Only the holder of the lock may call wait */
> }
> l->thread_id = -1; /* or whatever invalid thread value */
> release(c->condlock);
> release(*(c->lock));
> wait_on_signal_or_broadcast(); /* hint, use a semaphore */
> acquire(*(c->lock));
> acquire(c->condlock);
> c->thread_id = thread_id_of(current_thread);
> release(c->condlock);
> }
>
> void Signal(struct Condition *c) {
> if (c->thread_id != thread_id_of(current_thread))
> exit(-1); /* Only the holder of the lock may call signal */
> wake_one_sleeper();
> }
>
> void Broadcast(struct Condition *c) {
> if (c->thread_id != thread_id_of(current_thread))
> exit(-1); /* Only the holder of the lock may call broadcast */
> wake_all_sleepers();
> }
>
> > Not really, but maybe I'm just being dense. Assuming "mutex1" is the
> > mutex associated with the condition (and therefore has the same scope),
> > what is the scope of "mutex2" and "held"?
> >
> The scope of mutex2 is not associated with the condition; it is
> intended to provided the needed mutual exclusion for mutex1 and the
> state variable held. However, you can ignore this, since that code was
> slightly wrong.
>
> > And more importantly, if you're using sleep(), then aren't you just doing
> > a primitive poll/wait loop, and therefore defeating the whole purpose
> > of event-based scheduling using CVs?
> Sleep() was not intended to be sleep; I was writing pseudocode.
> Sleep() was a place holder for whatever function you are calling
> that is used to block the current thread until is is awakened via a
> signal() or broadcast() operation. Hopefully I'm more clear in the
> above example.
Fair enough. The above is much more clear, but there is now another
problem...
>
> Does the new code fit better with what you expect?
In your above example, how can more than one thread be wait()ing on
a condition, if only the thread that has the "c->lock" may call
wait()?
Also, Signal() and Broadcast() may not be MT-safe, as they perform
operations on c->thread_id that are non-exclusive and may be non-atomic
on some platforms.
-aaron
Re: Conditionals...
Posted by "Victor J. Orlikowski" <v....@gte.net>.
> void Wait(struct Condition *c) {
if (c->thread_id != thread_id_of(current_thread))
exit(-1); /* Only the holder of the lock may call wait */
> acquire(c->condlock);
> l->thread_id = -1; /* or whatever invalid thread value */
> release(c->condlock);
> release(*(c->lock));
> wait_on_signal_or_broadcast(); /* hint, use a semaphore */
> acquire(*(c->lock));
> acquire(c->condlock);
> c->thread_id = thread_id_of(current_thread);
> release(c->condlock);
> }
And the above would be slightly better.
Victor
--
Victor J. Orlikowski | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com
Re: Conditionals...
Posted by "Victor J. Orlikowski" <v....@gte.net>.
Aaron Bannert writes:
> On Tue, Jul 31, 2001 at 06:31:23PM -0400, Victor J. Orlikowski wrote:
> > Rather, let's be more clear.
> >
<snip>
>
My fault. That code is more than slightly wrong, now that I look
at it better. Let's examine the following pseudocode, which closely
follows some of my undergraduate OS work at the university.
I will not be doing any checking for null values, etc.
struct Condition {
mutex *lock; /* mutex associated with condition */
int thread_id; /* Current holder of the lock */
mutex condlock;
};
void Wait(struct Condition *c) {
acquire(c->condlock);
if (c->thread_id != thread_id_of(current_thread)) {
release(c->condlock);
exit(-1); /* Only the holder of the lock may call wait */
}
l->thread_id = -1; /* or whatever invalid thread value */
release(c->condlock);
release(*(c->lock));
wait_on_signal_or_broadcast(); /* hint, use a semaphore */
acquire(*(c->lock));
acquire(c->condlock);
c->thread_id = thread_id_of(current_thread);
release(c->condlock);
}
void Signal(struct Condition *c) {
if (c->thread_id != thread_id_of(current_thread))
exit(-1); /* Only the holder of the lock may call signal */
wake_one_sleeper();
}
void Broadcast(struct Condition *c) {
if (c->thread_id != thread_id_of(current_thread))
exit(-1); /* Only the holder of the lock may call broadcast */
wake_all_sleepers();
}
> Not really, but maybe I'm just being dense. Assuming "mutex1" is the
> mutex associated with the condition (and therefore has the same scope),
> what is the scope of "mutex2" and "held"?
>
The scope of mutex2 is not associated with the condition; it is
intended to provided the needed mutual exclusion for mutex1 and the
state variable held. However, you can ignore this, since that code was
slightly wrong.
> And more importantly, if you're using sleep(), then aren't you just doing
> a primitive poll/wait loop, and therefore defeating the whole purpose
> of event-based scheduling using CVs?
Sleep() was not intended to be sleep; I was writing pseudocode.
Sleep() was a place holder for whatever function you are calling
that is used to block the current thread until is is awakened via a
signal() or broadcast() operation. Hopefully I'm more clear in the
above example.
Does the new code fit better with what you expect?
Victor
--
Victor J. Orlikowski | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com
Re: Conditionals...
Posted by Aaron Bannert <aa...@ebuilt.com>.
On Tue, Jul 31, 2001 at 06:31:23PM -0400, Victor J. Orlikowski wrote:
> Rather, let's be more clear.
>
> bool held=false;
>
> acquire(mutex2);
> release(mutex1);
> held=false;
> release(mutex2);
> nap: sleep();
> acquire(mutex2);
> if(held) goto nap;
> acquire(mutex1);
> held=true;
> release(mutex2);
>
> That explain it somewhat better? ;)
Not really, but maybe I'm just being dense. Assuming "mutex1" is the
mutex associated with the condition (and therefore has the same scope),
what is the scope of "mutex2" and "held"?
And more importantly, if you're using sleep(), then aren't you just doing
a primitive poll/wait loop, and therefore defeating the whole purpose
of event-based scheduling using CVs?
-aaron