Single-Writer Multi-Reader lock for Win98

23 views
Skip to first unread message

Ed Peddycoart

unread,
Oct 19, 1999, 3:00:00 AM10/19/99
to
I need a single-writer multi-reader lock which will work with Win98,
preferrably in the form of a C++ class. I have been using the one
described by Jeff Claar in the Jan 99 issue of WDJ, but it is NT only.
Does anyone have one, or can anyone point to towards resources on the
internet etc. that describes such, other than the one described in
Richter's book?
Ed


Nicole Hamilton

unread,
Oct 19, 1999, 3:00:00 AM10/19/99
to
Ed Peddycoart <edpedd...@mindspring.com> wrote:
> I need a single-writer multi-reader lock which will work with Win98,
> preferrably in the form of a C++ class.

There is indeed no primitive in Win32 to achieve this, so it does have to
be built up out of other primitives. Here's an implementation using
CriticalSections that I walk my students through when I teach my Win32
class. This is the one I use myself in my C shell, which is quite highly
multi-threaded.

typedef struct sh {
CRITICAL_SECTION lock;
HANDLE writelock; /* Manual-reset event */
int readers;
} sharedread_sem;

void initialize( sharedread_sem *s )
{
InitializeCriticalSection(&s->lock);
s->readers = 0;
s->writelock = CreateEvent(NULL, TRUE,
FALSE, NULL);
}

void write_lock( sharedread_sem *s )
{
top:
EnterCriticalSection(&s->lock);
if (s->readers)
{
LeaveCriticalSection(&s->lock);
WaitForSingleObject(s->writelock, INFINITE);
goto top;
}
}

void release_write_lock( sharedread_sem *s )
{
LeaveCriticalSection(&s->lock);
}

void read_lock( sharedread_sem *s )
{
EnterCriticalSection(&s->lock);
s->readers++;
ResetEvent(s->writelock);
LeaveCriticalSection(&s->lock);
}

void release_read_lock( sharedread_sem *s )
{
EnterCriticalSection(&s->lock);
if (--s->readers == 0)
SetEvent(s->writelock);
LeaveCriticalSection(&s->lock);
}

(The rest of class is pretty good, too. :) If you'd like to see the whole
list of topics, please see http://www.hamiltonlabs.com/win32class.htm.)
--

Regards,
Nicki Hamilton

Nicole Ashley Hamilton KD1UJ hami...@hamiltonlabs.com
http://www.hamiltonlabs.com Phone 781-487-0008 FAX 781-487-0009
Hamilton Laboratories, 45 Kings Way, Unit 14, Waltham, MA 02451-9039, USA


Douglas C. Schmidt

unread,
Oct 19, 1999, 3:00:00 AM10/19/99
to
Hi Ed,

> I need a single-writer multi-reader lock which will work with Win98,
> preferrably in the form of a C++ class.

Check out the

ACE_RW_Thread_Mutex

class in ACE release, which you can download at

http://www.cs.wustl.edu/~schmidt/ACE.html

You can read about this class at

http://www.cs.wustl.edu/~schmidt/ACE_wrappers/man/html/ACE_RW_Thread_Mutex.html

and in the paper at

http://www.cs.wustl.edu/~schmidt/Concurrency.ps.gz

Take care,

Doug
--
Dr. Douglas C. Schmidt, Associate Professor
Department of Computer Science, Washington University
St. Louis, MO 63130. Work #: (314) 935-4215; FAX #: (314) 935-7302
sch...@cs.wustl.edu, www.cs.wustl.edu/~schmidt/

Ziv Caspi

unread,
Oct 20, 1999, 3:00:00 AM10/20/99
to
On Tue, 19 Oct 1999 16:29:33 GMT, "Nicole Hamilton"
<hami...@hamiltonlabs.com> wrote:

[... A simple implementation for single-writer, multiple-readers
lock...]

Forgive me for saying so, but this implementation favors
readers instead of the writer. If there are many readers,
the writer will never have a chance to write, so the information
the readers use will quickly become obsolete.

---------------------------------------------
Ziv Caspi
zi...@netvision.net.il

Nicole Hamilton

unread,
Oct 20, 1999, 3:00:00 AM10/20/99
to
Ziv Caspi <zi...@netvision.net.il> wrote:
> "Nicole Hamilton" <hami...@hamiltonlabs.com> wrote:
>
> [... A simple implementation for single-writer, multiple-readers
> lock...]
>
> Forgive me for saying so, but this implementation favors
> readers instead of the writer. If there are many readers,
> the writer will never have a chance to write, so the information
> the readers use will quickly become obsolete.

So you'd like to modify it so that if there a writer requests access, that
no new readers can be admitted until the writer has been allowed in
and out? Well, you have the code, how would you fix the sharedread_sem
structure and the various lock procedures? New readers would be
treated somewhat like writers, wouldn't they, with a loop? Can you write
the code?

Yours is the kind of question I'd be delighted to hear in my class as an
excellent exercise to see if the material was absorbed.

But of course, your comment ties in to another point I like to discuss,
which is that if you expect lots of collisions over any given resource,
then it's probably time to think about ways to replicate the resource or
reduce the amount of time each use requires, etc., all in an attempt
to reduce that bottleneck.

Nicki

Ziv Caspi

unread,
Oct 21, 1999, 3:00:00 AM10/21/99
to
On Wed, 20 Oct 1999 12:33:57 GMT, "Nicole Hamilton"
<hami...@hamiltonlabs.com> wrote:

>So you'd like to modify it so that if there a writer requests access, that
>no new readers can be admitted until the writer has been allowed in
>and out?

This is one of several possible ways to do it.

>Well, you have the code, how would you fix the sharedread_sem
>structure and the various lock procedures? New readers would be
>treated somewhat like writers, wouldn't they, with a loop? Can you write
>the code?

I can, and I have.

>Yours is the kind of question I'd be delighted to hear in my class as an
>excellent exercise to see if the material was absorbed.
>
>But of course, your comment ties in to another point I like to discuss,
>which is that if you expect lots of collisions over any given resource,
>then it's probably time to think about ways to replicate the resource or
>reduce the amount of time each use requires, etc., all in an attempt
>to reduce that bottleneck.


---------------------------------------------
Ziv Caspi
zi...@netvision.net.il

Nicole Hamilton

unread,
Oct 21, 1999, 3:00:00 AM10/21/99
to
Ziv Caspi <zi...@netvision.net.il> wrote:
> Nicole Hamilton <hami...@hamiltonlabs.com> wrote::

> >Well, you have the code, how would you fix the sharedread_sem
> >structure and the various lock procedures? ... Can you write

> >the code?
>
> I can, and I have.

Do you care to post your solution for comparison with the original
I gave?

Nicki

Jordan Zimmerman

unread,
Oct 21, 1999, 3:00:00 AM10/21/99
to
In article <01bf1af7$615751a0$0732180c@hamiltonlabs>, Nicole Hamilton
<hami...@hamiltonlabs.com> wrote:

> So you'd like to modify it so that if there a writer requests access, that
> no new readers can be admitted until the writer has been allowed in

> and out? Well, you have the code, how would you fix the sharedread_sem


> structure and the various lock procedures? New readers would be

> treated somewhat like writers, wouldn't they, with a loop? Can you write
> the code?

I've taken a stab at it...

The issue, it seems to me, is that you want to prevent new readers when
there's a pending write. So, it seems to call for another critical
section. Here's a mod on the previous code:

typedef struct sh {
CRITICAL_SECTION lock;

CRITICAL_SECTION readlock;


HANDLE writelock; /* Manual-reset event */
int readers;
} sharedread_sem;

void initialize( sharedread_sem *s )
{
InitializeCriticalSection(&s->lock);

InitializeCriticalSection(&s->readlock);


s->readers = 0;
s->writelock = CreateEvent(NULL, TRUE,
FALSE, NULL);
}

void write_lock( sharedread_sem *s )
{

EnterCriticalSection(&s->readlock);

top:
EnterCriticalSection(&s->lock);
if (s->readers)
{
LeaveCriticalSection(&s->lock);
WaitForSingleObject(s->writelock, INFINITE);
goto top;
}

LeaveCriticalSection(&s->readlock);
}

void release_write_lock( sharedread_sem *s )
{
LeaveCriticalSection(&s->lock);
}

void read_lock( sharedread_sem *s )
{

EnterCriticalSection(&s->readlock);

EnterCriticalSection(&s->lock);
s->readers++;
ResetEvent(s->writelock);
LeaveCriticalSection(&s->lock);

LeaveCriticalSection(&s->readlock);
}

void release_read_lock( sharedread_sem *s )
{
EnterCriticalSection(&s->lock);
if (--s->readers == 0)
SetEvent(s->writelock);
LeaveCriticalSection(&s->lock);
}

--
Jordan Zimmerman
Altura Software, Inc.
Catalog City, Inc. http://www.catalogcity.com

Stop the persecution of Microsoft and Capitalism:
http://www.moraldefense.com/microsoft

Nicole Hamilton

unread,
Oct 22, 1999, 3:00:00 AM10/22/99
to
Jordan Zimmerman <jor...@altura.com> wrote:
> Nicole Hamilton <hami...@hamiltonlabs.com> wrote:
> > So you'd like to modify it so that if there a writer requests access, that
> > no new readers can be admitted until the writer has been allowed in
> > and out? Well, you have the code, how would you fix the sharedread_sem
> > structure and the various lock procedures? ...

>
> I've taken a stab at it...
>
> The issue, it seems to me, is that you want to prevent new readers when
> there's a pending write. So, it seems to call for another critical
> section. Here's a mod on the previous code:

Bravo! A very nice solution!

james...@my-deja.com

unread,
Nov 2, 1999, 3:00:00 AM11/2/99
to
Don't we still have a problem with deadlocks? Suppose process A has the
read lock. Process B wants to do a write and is blocked waiting for
process A. Suppose process A decides to get the write lock (without
releasing the read lock). Now A is blocked waiting for B. Deadlock.


Sent via Deja.com http://www.deja.com/
Before you buy.

David Schwartz

unread,
Nov 2, 1999, 3:00:00 AM11/2/99
to
james...@my-deja.com wrote:
>
> Don't we still have a problem with deadlocks? Suppose process A has the
> read lock. Process B wants to do a write and is blocked waiting for
> process A. Suppose process A decides to get the write lock (without
> releasing the read lock). Now A is blocked waiting for B. Deadlock.

If you violate interface contracts, you will always have a problem with
deadlocks. But the problem is not in the lock, it's in process A which
tried to acquire the same lock twice.

DS

Carey Gregory

unread,
Nov 2, 1999, 3:00:00 AM11/2/99
to
james...@my-deja.com wrote:

>Don't we still have a problem with deadlocks? Suppose process A has the
>read lock. Process B wants to do a write and is blocked waiting for
>process A. Suppose process A decides to get the write lock (without
>releasing the read lock). Now A is blocked waiting for B. Deadlock.

Acquiring multiple locks will always lead to deadlocks if you allow blocking
on the second lock. The usual solution is to request the second lock without
blocking. If you can't obtain the second lock, release the first lock and
start over.

--
Carey Gregory

"The average dog is a nicer person than
the average person." -- A. Rooney

Nicole Hamilton

unread,
Nov 2, 1999, 3:00:00 AM11/2/99
to
Carey Gregory <cgre...@gw-tech.com> wrote:
> Acquiring multiple locks will always lead to deadlocks if you allow blocking
> on the second lock. The usual solution is to request the second lock without
> blocking. If you can't obtain the second lock, release the first lock and
> start over.

Blocking on the second lock does not, in and of itself, lead to deadlock in a
properly designed application. What is required to avoid deadlock is that
if we require multiple resources, we must always, NO EXCEPTIONS!,
request them in the same order.

Nicki

Tom Payne

unread,
Nov 2, 1999, 3:00:00 AM11/2/99
to
In comp.programming.threads Carey Gregory <cgre...@gw-tech.com> wrote:
> james...@my-deja.com wrote:

>>Don't we still have a problem with deadlocks? Suppose process A has the
>>read lock. Process B wants to do a write and is blocked waiting for
>>process A. Suppose process A decides to get the write lock (without
>>releasing the read lock). Now A is blocked waiting for B. Deadlock.

> Acquiring multiple locks will always lead to deadlocks if you allow blocking
> on the second lock.

Not always, e.g.., in the course of manipulating some lock-protected
data structure you might invoke the lock protected memory allocator.

> The usual solution is to request the second lock without blocking.
> If you can't obtain the second lock, release the first lock and
> start over.

... but taking care to restore invariants before releasing the first
lock.

Tom Payne

T.Totaler

unread,
Nov 2, 1999, 3:00:00 AM11/2/99
to
David Schwartz wrote:
>
> james...@my-deja.com wrote:
> >
> > Don't we still have a problem with deadlocks? Suppose process A has the
> > read lock. Process B wants to do a write and is blocked waiting for
> > process A. Suppose process A decides to get the write lock (without
> > releasing the read lock). Now A is blocked waiting for B. Deadlock.
>
> If you violate interface contracts, you will always have a problem with
> deadlocks. But the problem is not in the lock, it's in process A which
> tried to acquire the same lock twice.
Not necessarily. If that's a real-world possibility, then the lock has
to "know" to "promote" the read lock to the write one for the process
that already owns this read lock. That is one possibility, that is. Or,
in the simplest case, just fail. You can keep track of who locked what,
by using PIDs, for example.

--
len
if you must email, reply to:
len bel at world net dot att dot net (no spaces, ats2@, dots2.)

Carey Gregory

unread,
Nov 2, 1999, 3:00:00 AM11/2/99
to
"Nicole Hamilton" <hami...@hamiltonlabs.com> wrote:

>Blocking on the second lock does not, in and of itself, lead to deadlock in a
>properly designed application. What is required to avoid deadlock is that
>if we require multiple resources, we must always, NO EXCEPTIONS!,
>request them in the same order.

True. I should have been more precise. When in doubt, refer to Knuth.

David Schwartz

unread,
Nov 2, 1999, 3:00:00 AM11/2/99
to
"T.Totaler" wrote:
>
> David Schwartz wrote:
> >
> > james...@my-deja.com wrote:
> > >
> > > Don't we still have a problem with deadlocks? Suppose process A has the
> > > read lock. Process B wants to do a write and is blocked waiting for
> > > process A. Suppose process A decides to get the write lock (without
> > > releasing the read lock). Now A is blocked waiting for B. Deadlock.
> >
> > If you violate interface contracts, you will always have a problem with
> > deadlocks. But the problem is not in the lock, it's in process A which
> > tried to acquire the same lock twice.

> Not necessarily. If that's a real-world possibility, then the lock has
> to "know" to "promote" the read lock to the write one for the process
> that already owns this read lock. That is one possibility, that is. Or,
> in the simplest case, just fail. You can keep track of who locked what,
> by using PIDs, for example.

The overhead required to track this is generally sufficient to at least
double the cost of the locking primitive. It might be appropriate for a
debug build, but it should drop out of a release build.

If you want read/write/promote locks, you know where to find them.
Personally, I prefer to fix the architecture so such complex locking
'primitives' are not needed, but it's not always possible or practical.

DS

T.Totaler

unread,
Nov 2, 1999, 3:00:00 AM11/2/99
to
David Schwartz wrote:
> The overhead required to track this is generally sufficient to at least
> double the cost of the locking primitive.
Oh yeah. So that all really depends on the application.

james...@my-deja.com

unread,
Nov 3, 1999, 3:00:00 AM11/3/99
to
If two processes are reading and one tries to write, the lock can be
promoted (after waiting for the other process to release the read lock).

If both processes try to write, each process will block, waiting for
the other to release their read lock.

Joe Seigh

unread,
Nov 3, 1999, 3:00:00 AM11/3/99
to
james...@my-deja.com wrote:
>
> If two processes are reading and one tries to write, the lock can be
> promoted (after waiting for the other process to release the read lock).
>
> If both processes try to write, each process will block, waiting for
> the other to release their read lock.
>

The read lock is not released, but converted to a write lock after
all other reads have finished. The read lock can't be released
because the update to the shared data is going to be based on
state information gotten while the lock was read only, and if
the lock was released, even for an instant, it would be possible
for another thread to get write access and modify the shared data.

The way deadlock is prevented in the case of a read lock
being promoted to a write lock is to make it conditional and
fail the request if another thread has already requested
the lock to be promoted. Usually though, the intent to
request write promotion is indicated with the request for read access
and ensuring that only one such thread has such read access
at a time will prevent deadlock.

Joe Seigh

Tom Payne

unread,
Nov 3, 1999, 3:00:00 AM11/3/99
to

After thinking about it, I realize that I don't understand the process
of promoting read-access to write-access in the way that is being
discussed. What is it supposed to accomplish and how?

What I think I understand is that in addition to an end_read()
routine, which releases shared/read access, we need:

void end_read_and_start_write() {
if ( ! reader_count == 1 ) {
reader_count = 0;
write_in_progress = true;
} else { // the following should be inline.
end_read();
start_write();
}
}

which promotes shared/read access be promoted to exclusive/write
access. As the last writer departs, he simply sets the
write_in_progress flag, thereby obtaining exclusive access. That
saves a bit of overhead compared to releasing shared/read access and
then competing for exclusive/write access. But that only helps when
he's the last. Otherwise, he has to wait somewhere for exclusive
access, so he might as well compete for exclusive access along with
the other aspiring writers.

Now, if a thread performing such a read-followed-by-write operation
ends his writing with a normal call to end_write(), he would normally
give preference to waiting readers (if any), a protocol that allows a
steady stream of such read-followed-by-write accessing to freeze out
waiting writers. So, he needs to end his read-followed-by-write
access via a call to end_read_followed_by_write(), which behaves just
like end_write() but gives preference to waiting writers (if any) just
as end_read() does. Unfortunately, however, threads doing a
read-followed-by-write get a scheduling advantage over writers who
wait their turn, which messes with whatever scheduling discipline one
might wish to impose.

Tom Payne

tugbo...@gmail.com

unread,
Mar 3, 2016, 11:33:06 PM3/3/16
to
On Thursday, October 21, 1999 at 6:00:00 PM UTC+11, Jordan Zimmerman wrote:
> In article <01bf1af7$615751a0$0732180c@hamiltonlabs>, Nicole Hamilton
> <hami...@hamiltonlabs.com> wrote:
>
> > So you'd like to modify it so that if there a writer requests access, that
> > no new readers can be admitted until the writer has been allowed in
> > and out? Well, you have the code, how would you fix the sharedread_sem
> > structure and the various lock procedures? New readers would be
> > treated somewhat like writers, wouldn't they, with a loop? Can you write
> > the code?
>
> I've taken a stab at it...
>
> The issue, it seems to me, is that you want to prevent new readers when
> there's a pending write. So, it seems to call for another critical
> section. Here's a mod on the previous code:
>
Hi Jordan, I know it's been a while since this post :), but I have a question that I can't leave unasked.

After applying your modification (see above) it is no longer absolutely necessary to use the "goto" statement in function write_lock(). That is, now that writers are guaranteed a fair go, we should be able to define function write_lock() as:

void write_lock( sharedread_sem *s )
{

EnterCriticalSection(&s->readlock);

EnterCriticalSection(&s->lock);
if (s->readers)
{
LeaveCriticalSection(&s->lock);
WaitForSingleObject(s->writelock, INFINITE);
}

LeaveCriticalSection(&s->readlock);
}

This is because not only does the call to EnterCriticalSection(&s->readlock) serialize calls by multiple writers, it also prevents any readers from subsequently incrementing s->readers while any writer holds the critical section s->readlock. When a writer returns from the call to WaitForSingleObject(s->writelock, INFINITE) in function write_lock(), then s->readers is guaranteed to be 0 so long as the writer holds the critical section s->readlock.

Thanks in advance.

Cholo Lennon

unread,
Mar 18, 2016, 6:33:54 PM3/18/16
to
On 03/04/2016 01:33 AM, tugbo...@gmail.com wrote:
> Hi Jordan, I know it's been a while since this post:), but I have a question that I can't leave unasked.

OMG! another Back to the Future response... almost 17 years man! Did you
think about it?

--
Cholo Lennon
Bs.As.
ARG
Reply all
Reply to author
Forward
0 new messages