Good Algorithm for "Multiple Readers"/"Multiple Writers"

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall
Hi,

I'm looking for a good, performant algorithm for "multiple
reader"/"multiple writer" locking.

I'm in the process of writing my own but I would rather not fall into
any common pitfalls, especially since performance & scalability are
critical.

Is anyone aware of whether POSIX implements this type of lock?  I can't
seem to find any reference to it in the POSIX documentation.

Cheers, Steve.

--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com
Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall

Thanks, but the POSIX read/write interface supports a single writer vs.
multiple readers.  I'm after multiple writers & readers i.e. multiple
threads can perform writing but readers must wait and vice versa.

Steve.

-----Original Message-----
From: Rustam T. Usmanov [mailto:[hidden email]]
Sent: 08 December 2005 09:54
To: Stephen Croall
Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"

On Thu, 8 Dec 2005, Stephen Croall wrote:

> Is anyone aware of whether POSIX implements this type of lock?

pthread_rwlock ? See
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i
nit.html

--
Rustam Usmanov, systems engineer
Institute of Consortia Library Information Systems,
St.Petersburg State Polytechnic University
Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>
Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Evstiounin, Mikhail
In reply to this post by Stephen Croall
I did not quite get it. The difference between reader and writer is that
reader locks out writer and lets other readers continue without waiting
while writer acquire an exclusive lock. Multiple writers will have
serialized access to a resource in any case. So, there no difference
from this point of view between "one writer -- many readers" and "many
writers -- many readers". So, if you are going to use FIFO (or you don't
care -- I made an assumption that all requests for resource locking is
based on FIFO which is not true, generally speaking) in terms of how to
process request queue then posix approach is enough.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Stephen Croall
Sent: Thursday, December 08, 2005 4:57 AM
To: [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"


Thanks, but the POSIX read/write interface supports a single writer vs.
multiple readers.  I'm after multiple writers & readers i.e. multiple
threads can perform writing but readers must wait and vice versa.

Steve.

-----Original Message-----
From: Rustam T. Usmanov [mailto:[hidden email]]
Sent: 08 December 2005 09:54
To: Stephen Croall
Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"

On Thu, 8 Dec 2005, Stephen Croall wrote:

> Is anyone aware of whether POSIX implements this type of lock?

pthread_rwlock ? See
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i
nit.html

--
Rustam Usmanov, systems engineer
Institute of Consortia Library Information Systems,
St.Petersburg State Polytechnic University
Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>

Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall
In reply to this post by Stephen Croall
 
We already use read/write locks in places but for greater parallelism
multiple reader and multiple writer locks would be better.

The current read/write lock implementation in POSIX doesn't support
multiple writers.  Only one writer thread can process at a time - as I
would expect.

I'm after a good model for writing a "many readers"/"many writers" lock
implementation, which is portable from Windows to UNIX.

Steve.

-----Original Message-----
From: Evstiounin, Mikhail [mailto:[hidden email]]
Sent: 08 December 2005 14:02
To: Stephen Croall; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I did not quite get it. The difference between reader and writer is that
reader locks out writer and lets other readers continue without waiting
while writer acquire an exclusive lock. Multiple writers will have
serialized access to a resource in any case. So, there no difference
from this point of view between "one writer -- many readers" and "many
writers -- many readers". So, if you are going to use FIFO (or you don't
care -- I made an assumption that all requests for resource locking is
based on FIFO which is not true, generally speaking) in terms of how to
process request queue then posix approach is enough.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Stephen Croall
Sent: Thursday, December 08, 2005 4:57 AM
To: [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"


Thanks, but the POSIX read/write interface supports a single writer vs.
multiple readers.  I'm after multiple writers & readers i.e. multiple
threads can perform writing but readers must wait and vice versa.

Steve.

-----Original Message-----
From: Rustam T. Usmanov [mailto:[hidden email]]
Sent: 08 December 2005 09:54
To: Stephen Croall
Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"

On Thu, 8 Dec 2005, Stephen Croall wrote:

> Is anyone aware of whether POSIX implements this type of lock?

pthread_rwlock ? See
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i
nit.html

--
Rustam Usmanov, systems engineer
Institute of Consortia Library Information Systems,
St.Petersburg State Polytechnic University
Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>

Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Robert Kindred
In reply to this post by Stephen Croall
I use the pthread_rwlock_t in pthreads-win32, and it works fine.

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen Croall
> Sent: Thursday, December 08, 2005 3:10 AM
> To: [hidden email]
> Subject: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Hi,
>
> I'm looking for a good, performant algorithm for "multiple
> reader"/"multiple writer" locking.
>
> I'm in the process of writing my own but I would rather not fall into
> any common pitfalls, especially since performance & scalability are
> critical.
>
> Is anyone aware of whether POSIX implements this type of lock?  I can't
> seem to find any reference to it in the POSIX documentation.
>
> Cheers, Steve.
>
> --
>
> J. Senior Software Engineer, Tibco Software Ltd.
> T. +44 (0) 1792 360773
> M. +44 (0) 7788 971394
> E. [hidden email]
> W. www.tibco.com
>
Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall
In reply to this post by Stephen Croall

But that is for "single writer"/"multiple readers" - it doesn't support
multiple writers.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:47
To: Stephen Croall; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I use the pthread_rwlock_t in pthreads-win32, and it works fine.

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 3:10 AM
> To: [hidden email]
> Subject: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Hi,
>
> I'm looking for a good, performant algorithm for "multiple
> reader"/"multiple writer" locking.
>
> I'm in the process of writing my own but I would rather not fall into
> any common pitfalls, especially since performance & scalability are
> critical.
>
> Is anyone aware of whether POSIX implements this type of lock?  I
can't

> seem to find any reference to it in the POSIX documentation.
>
> Cheers, Steve.
>
> --
>
> J. Senior Software Engineer, Tibco Software Ltd.
> T. +44 (0) 1792 360773
> M. +44 (0) 7788 971394
> E. [hidden email]
> W. www.tibco.com
>
Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Robert Kindred
In reply to this post by Stephen Croall
Multiple writers doesn't make any sense at all to me, unless you mean a
message queue.  I copied a good algorithm for this out of the POSA2 book
(Pattern Oriented Software Architecture Volume 2, Patterns for Concurrent
and Networked Objects).

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen Croall
> Sent: Thursday, December 08, 2005 8:08 AM
> To: Evstiounin, Mikhail; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
>
> We already use read/write locks in places but for greater parallelism
> multiple reader and multiple writer locks would be better.
>
> The current read/write lock implementation in POSIX doesn't support
> multiple writers.  Only one writer thread can process at a time - as I
> would expect.
>
> I'm after a good model for writing a "many readers"/"many writers" lock
> implementation, which is portable from Windows to UNIX.
>
> Steve.
>
> -----Original Message-----
> From: Evstiounin, Mikhail [mailto:[hidden email]]
> Sent: 08 December 2005 14:02
> To: Stephen Croall; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> I did not quite get it. The difference between reader and writer is that
> reader locks out writer and lets other readers continue without waiting
> while writer acquire an exclusive lock. Multiple writers will have
> serialized access to a resource in any case. So, there no difference
> from this point of view between "one writer -- many readers" and "many
> writers -- many readers". So, if you are going to use FIFO (or you don't
> care -- I made an assumption that all requests for resource locking is
> based on FIFO which is not true, generally speaking) in terms of how to
> process request queue then posix approach is enough.
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Stephen Croall
> Sent: Thursday, December 08, 2005 4:57 AM
> To: [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Thanks, but the POSIX read/write interface supports a single writer vs.
> multiple readers.  I'm after multiple writers & readers i.e. multiple
> threads can perform writing but readers must wait and vice versa.
>
> Steve.
>
> -----Original Message-----
> From: Rustam T. Usmanov [mailto:[hidden email]]
> Sent: 08 December 2005 09:54
> To: Stephen Croall
> Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> On Thu, 8 Dec 2005, Stephen Croall wrote:
>
> > Is anyone aware of whether POSIX implements this type of lock?
>
> pthread_rwlock ? See
> http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i
> nit.html
>
> --
> Rustam Usmanov, systems engineer
> Institute of Consortia Library Information Systems,
> St.Petersburg State Polytechnic University
> Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
> Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>
>
>

Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Evstiounin, Mikhail
In reply to this post by Stephen Croall
You can get more parallelism in terms of processing, but you are not
going to get more parallelism in terms of getting access to the
protected resource. In the last sense there is no difference between
single and multiple writers and advice given by Rustam is correct. Just
call pthread_rwlock_timedwrlock in every writer. Model single writer
multiple reader means that at any given moment you can have multiple
readers having access to a resource and only one writer. That does not
mean that you have to have one writer in your program.


-----Original Message-----
From: Stephen Croall [mailto:[hidden email]]
Sent: Thursday, December 08, 2005 9:08 AM
To: Evstiounin, Mikhail; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

 
We already use read/write locks in places but for greater parallelism
multiple reader and multiple writer locks would be better.

The current read/write lock implementation in POSIX doesn't support
multiple writers.  Only one writer thread can process at a time - as I
would expect.

I'm after a good model for writing a "many readers"/"many writers" lock
implementation, which is portable from Windows to UNIX.

Steve.

-----Original Message-----
From: Evstiounin, Mikhail [mailto:[hidden email]]
Sent: 08 December 2005 14:02
To: Stephen Croall; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I did not quite get it. The difference between reader and writer is that
reader locks out writer and lets other readers continue without waiting
while writer acquire an exclusive lock. Multiple writers will have
serialized access to a resource in any case. So, there no difference
from this point of view between "one writer -- many readers" and "many
writers -- many readers". So, if you are going to use FIFO (or you don't
care -- I made an assumption that all requests for resource locking is
based on FIFO which is not true, generally speaking) in terms of how to
process request queue then posix approach is enough.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Stephen Croall
Sent: Thursday, December 08, 2005 4:57 AM
To: [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"


Thanks, but the POSIX read/write interface supports a single writer vs.
multiple readers.  I'm after multiple writers & readers i.e. multiple
threads can perform writing but readers must wait and vice versa.

Steve.

-----Original Message-----
From: Rustam T. Usmanov [mailto:[hidden email]]
Sent: 08 December 2005 09:54
To: Stephen Croall
Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"

On Thu, 8 Dec 2005, Stephen Croall wrote:

> Is anyone aware of whether POSIX implements this type of lock?

pthread_rwlock ? See
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i
nit.html

--
Rustam Usmanov, systems engineer
Institute of Consortia Library Information Systems,
St.Petersburg State Polytechnic University
Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>


Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall
In reply to this post by Stephen Croall
I'll try to explain how they can be used :)

Imagine a large list of items, each item can be written to in parallel
by multiple threads with no need to block since the writing of each item
is independent of the others.  However, some other threads require to
read all the items to be able to filter and generate a list of the
filtered items.  These threads can be run in parallel but cannot be run
at the same time as the writing threads, hence multiple readers and
multiple writers.

One solution is to have a read/write lock on every item in the list but
this is not performant for the filtering since it has to lock/unlock the
read lock in every item in turn and also it's a large resource usage,
since there are about 4 handles to every read/write lock.  On my system
here I had over 200,000 handles in use in a single process, which lead
me to start using pools of locks.

A more performant solution would be to have a single lock that
controlled the reader and writer threads.  When reading threads are
running the writers are blocked and when the writing threads are running
the reading threads are blocked.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:52
To: Stephen Croall; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Multiple writers doesn't make any sense at all to me, unless you mean a
message queue.  I copied a good algorithm for this out of the POSA2 book
(Pattern Oriented Software Architecture Volume 2, Patterns for
Concurrent
and Networked Objects).

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 8:08 AM
> To: Evstiounin, Mikhail; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
>
> We already use read/write locks in places but for greater parallelism
> multiple reader and multiple writer locks would be better.
>
> The current read/write lock implementation in POSIX doesn't support
> multiple writers.  Only one writer thread can process at a time - as I
> would expect.
>
> I'm after a good model for writing a "many readers"/"many writers"
lock

> implementation, which is portable from Windows to UNIX.
>
> Steve.
>
> -----Original Message-----
> From: Evstiounin, Mikhail [mailto:[hidden email]]
> Sent: 08 December 2005 14:02
> To: Stephen Croall; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> I did not quite get it. The difference between reader and writer is
that
> reader locks out writer and lets other readers continue without
waiting
> while writer acquire an exclusive lock. Multiple writers will have
> serialized access to a resource in any case. So, there no difference
> from this point of view between "one writer -- many readers" and "many
> writers -- many readers". So, if you are going to use FIFO (or you
don't
> care -- I made an assumption that all requests for resource locking is
> based on FIFO which is not true, generally speaking) in terms of how
to
> process request queue then posix approach is enough.
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Stephen
Croall
> Sent: Thursday, December 08, 2005 4:57 AM
> To: [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Thanks, but the POSIX read/write interface supports a single writer
vs.

> multiple readers.  I'm after multiple writers & readers i.e. multiple
> threads can perform writing but readers must wait and vice versa.
>
> Steve.
>
> -----Original Message-----
> From: Rustam T. Usmanov [mailto:[hidden email]]
> Sent: 08 December 2005 09:54
> To: Stephen Croall
> Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> On Thu, 8 Dec 2005, Stephen Croall wrote:
>
> > Is anyone aware of whether POSIX implements this type of lock?
>
> pthread_rwlock ? See
>
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i

> nit.html
>
> --
> Rustam Usmanov, systems engineer
> Institute of Consortia Library Information Systems,
> St.Petersburg State Polytechnic University
> Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
> Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>
>
>

Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Evstiounin, Mikhail
In reply to this post by Stephen Croall
Frankly, how do you think it is possible to be able to write to resource
in parallel and keep integrity of this resource all the time? There is a
reason why writer gains an exclusive lock on a resource.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Stephen Croall
Sent: Thursday, December 08, 2005 9:49 AM
To: [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"


But that is for "single writer"/"multiple readers" - it doesn't support
multiple writers.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:47
To: Stephen Croall; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I use the pthread_rwlock_t in pthreads-win32, and it works fine.

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 3:10 AM
> To: [hidden email]
> Subject: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Hi,
>
> I'm looking for a good, performant algorithm for "multiple
> reader"/"multiple writer" locking.
>
> I'm in the process of writing my own but I would rather not fall into
> any common pitfalls, especially since performance & scalability are
> critical.
>
> Is anyone aware of whether POSIX implements this type of lock?  I
can't

> seem to find any reference to it in the POSIX documentation.
>
> Cheers, Steve.
>
> --
>
> J. Senior Software Engineer, Tibco Software Ltd.
> T. +44 (0) 1792 360773
> M. +44 (0) 7788 971394
> E. [hidden email]
> W. www.tibco.com
>

Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall
In reply to this post by Stephen Croall
The writers are writing to different items in a list i.e. different
areas of memory.  They are all independent writes.  Thread 1 writes to
item 1, thread 2 writes to item 2 etc...  They will never write to the
same memory.  However, I cannot have reads going on at the same time as
the writes, unless I use a read/write lock on every single item in the
list.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Evstiounin, Mikhail [mailto:[hidden email]]
Sent: 08 December 2005 15:03
To: Stephen Croall; [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Frankly, how do you think it is possible to be able to write to resource
in parallel and keep integrity of this resource all the time? There is a
reason why writer gains an exclusive lock on a resource.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Stephen Croall
Sent: Thursday, December 08, 2005 9:49 AM
To: [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"


But that is for "single writer"/"multiple readers" - it doesn't support
multiple writers.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:47
To: Stephen Croall; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I use the pthread_rwlock_t in pthreads-win32, and it works fine.

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 3:10 AM
> To: [hidden email]
> Subject: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Hi,
>
> I'm looking for a good, performant algorithm for "multiple
> reader"/"multiple writer" locking.
>
> I'm in the process of writing my own but I would rather not fall into
> any common pitfalls, especially since performance & scalability are
> critical.
>
> Is anyone aware of whether POSIX implements this type of lock?  I
can't

> seem to find any reference to it in the POSIX documentation.
>
> Cheers, Steve.
>
> --
>
> J. Senior Software Engineer, Tibco Software Ltd.
> T. +44 (0) 1792 360773
> M. +44 (0) 7788 971394
> E. [hidden email]
> W. www.tibco.com
>

Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Evstiounin, Mikhail
In reply to this post by Stephen Croall
You are wrong. Writing is not an independent. Whatever you use -- list,
table is a resource that should be protected. No two threads could
modify this resource in parallel -- only sequentially (serialized).
Unless you have personal queue per each thread and reading threads know
about each list. But later case does not have any resources that should
be protected from access from another writing threads.

-----Original Message-----
From: Stephen Croall [mailto:[hidden email]]
Sent: Thursday, December 08, 2005 10:01 AM
To: [hidden email]; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I'll try to explain how they can be used :)

Imagine a large list of items, each item can be written to in parallel
by multiple threads with no need to block since the writing of each item
is independent of the others.  However, some other threads require to
read all the items to be able to filter and generate a list of the
filtered items.  These threads can be run in parallel but cannot be run
at the same time as the writing threads, hence multiple readers and
multiple writers.

One solution is to have a read/write lock on every item in the list but
this is not performant for the filtering since it has to lock/unlock the
read lock in every item in turn and also it's a large resource usage,
since there are about 4 handles to every read/write lock.  On my system
here I had over 200,000 handles in use in a single process, which lead
me to start using pools of locks.

A more performant solution would be to have a single lock that
controlled the reader and writer threads.  When reading threads are
running the writers are blocked and when the writing threads are running
the reading threads are blocked.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:52
To: Stephen Croall; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Multiple writers doesn't make any sense at all to me, unless you mean a
message queue.  I copied a good algorithm for this out of the POSA2 book
(Pattern Oriented Software Architecture Volume 2, Patterns for
Concurrent
and Networked Objects).

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 8:08 AM
> To: Evstiounin, Mikhail; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
>
> We already use read/write locks in places but for greater parallelism
> multiple reader and multiple writer locks would be better.
>
> The current read/write lock implementation in POSIX doesn't support
> multiple writers.  Only one writer thread can process at a time - as I
> would expect.
>
> I'm after a good model for writing a "many readers"/"many writers"
lock

> implementation, which is portable from Windows to UNIX.
>
> Steve.
>
> -----Original Message-----
> From: Evstiounin, Mikhail [mailto:[hidden email]]
> Sent: 08 December 2005 14:02
> To: Stephen Croall; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> I did not quite get it. The difference between reader and writer is
that
> reader locks out writer and lets other readers continue without
waiting
> while writer acquire an exclusive lock. Multiple writers will have
> serialized access to a resource in any case. So, there no difference
> from this point of view between "one writer -- many readers" and "many
> writers -- many readers". So, if you are going to use FIFO (or you
don't
> care -- I made an assumption that all requests for resource locking is
> based on FIFO which is not true, generally speaking) in terms of how
to
> process request queue then posix approach is enough.
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Stephen
Croall
> Sent: Thursday, December 08, 2005 4:57 AM
> To: [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Thanks, but the POSIX read/write interface supports a single writer
vs.

> multiple readers.  I'm after multiple writers & readers i.e. multiple
> threads can perform writing but readers must wait and vice versa.
>
> Steve.
>
> -----Original Message-----
> From: Rustam T. Usmanov [mailto:[hidden email]]
> Sent: 08 December 2005 09:54
> To: Stephen Croall
> Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> On Thu, 8 Dec 2005, Stephen Croall wrote:
>
> > Is anyone aware of whether POSIX implements this type of lock?
>
> pthread_rwlock ? See
>
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i

> nit.html
>
> --
> Rustam Usmanov, systems engineer
> Institute of Consortia Library Information Systems,
> St.Petersburg State Polytechnic University
> Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
> Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>
>
>


Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall
In reply to this post by Stephen Croall

This is the best alogorithm I have seen so far:

http://www.cs.umd.edu/~hollings/cs412/s96/synch/synch1.html 


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Evstiounin, Mikhail [mailto:[hidden email]]
Sent: 08 December 2005 15:03
To: Stephen Croall; [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Frankly, how do you think it is possible to be able to write to resource
in parallel and keep integrity of this resource all the time? There is a
reason why writer gains an exclusive lock on a resource.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Stephen Croall
Sent: Thursday, December 08, 2005 9:49 AM
To: [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"


But that is for "single writer"/"multiple readers" - it doesn't support
multiple writers.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:47
To: Stephen Croall; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I use the pthread_rwlock_t in pthreads-win32, and it works fine.

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 3:10 AM
> To: [hidden email]
> Subject: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Hi,
>
> I'm looking for a good, performant algorithm for "multiple
> reader"/"multiple writer" locking.
>
> I'm in the process of writing my own but I would rather not fall into
> any common pitfalls, especially since performance & scalability are
> critical.
>
> Is anyone aware of whether POSIX implements this type of lock?  I
can't

> seem to find any reference to it in the POSIX documentation.
>
> Cheers, Steve.
>
> --
>
> J. Senior Software Engineer, Tibco Software Ltd.
> T. +44 (0) 1792 360773
> M. +44 (0) 7788 971394
> E. [hidden email]
> W. www.tibco.com
>

Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall
In reply to this post by Stephen Croall
They aren't adding or deleting from the list just updating independent
items in it.  Trust me, it's what our software already does :)  I'm just
trying to find a way to remove the need to have a read/write lock in
every item, which is a performance hit when building a filtered list.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Evstiounin, Mikhail [mailto:[hidden email]]
Sent: 08 December 2005 15:07
To: Stephen Croall; [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

You are wrong. Writing is not an independent. Whatever you use -- list,
table is a resource that should be protected. No two threads could
modify this resource in parallel -- only sequentially (serialized).
Unless you have personal queue per each thread and reading threads know
about each list. But later case does not have any resources that should
be protected from access from another writing threads.

-----Original Message-----
From: Stephen Croall [mailto:[hidden email]]
Sent: Thursday, December 08, 2005 10:01 AM
To: [hidden email]; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I'll try to explain how they can be used :)

Imagine a large list of items, each item can be written to in parallel
by multiple threads with no need to block since the writing of each item
is independent of the others.  However, some other threads require to
read all the items to be able to filter and generate a list of the
filtered items.  These threads can be run in parallel but cannot be run
at the same time as the writing threads, hence multiple readers and
multiple writers.

One solution is to have a read/write lock on every item in the list but
this is not performant for the filtering since it has to lock/unlock the
read lock in every item in turn and also it's a large resource usage,
since there are about 4 handles to every read/write lock.  On my system
here I had over 200,000 handles in use in a single process, which lead
me to start using pools of locks.

A more performant solution would be to have a single lock that
controlled the reader and writer threads.  When reading threads are
running the writers are blocked and when the writing threads are running
the reading threads are blocked.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:52
To: Stephen Croall; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Multiple writers doesn't make any sense at all to me, unless you mean a
message queue.  I copied a good algorithm for this out of the POSA2 book
(Pattern Oriented Software Architecture Volume 2, Patterns for
Concurrent
and Networked Objects).

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 8:08 AM
> To: Evstiounin, Mikhail; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
>
> We already use read/write locks in places but for greater parallelism
> multiple reader and multiple writer locks would be better.
>
> The current read/write lock implementation in POSIX doesn't support
> multiple writers.  Only one writer thread can process at a time - as I
> would expect.
>
> I'm after a good model for writing a "many readers"/"many writers"
lock

> implementation, which is portable from Windows to UNIX.
>
> Steve.
>
> -----Original Message-----
> From: Evstiounin, Mikhail [mailto:[hidden email]]
> Sent: 08 December 2005 14:02
> To: Stephen Croall; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> I did not quite get it. The difference between reader and writer is
that
> reader locks out writer and lets other readers continue without
waiting
> while writer acquire an exclusive lock. Multiple writers will have
> serialized access to a resource in any case. So, there no difference
> from this point of view between "one writer -- many readers" and "many
> writers -- many readers". So, if you are going to use FIFO (or you
don't
> care -- I made an assumption that all requests for resource locking is
> based on FIFO which is not true, generally speaking) in terms of how
to
> process request queue then posix approach is enough.
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Stephen
Croall
> Sent: Thursday, December 08, 2005 4:57 AM
> To: [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Thanks, but the POSIX read/write interface supports a single writer
vs.

> multiple readers.  I'm after multiple writers & readers i.e. multiple
> threads can perform writing but readers must wait and vice versa.
>
> Steve.
>
> -----Original Message-----
> From: Rustam T. Usmanov [mailto:[hidden email]]
> Sent: 08 December 2005 09:54
> To: Stephen Croall
> Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> On Thu, 8 Dec 2005, Stephen Croall wrote:
>
> > Is anyone aware of whether POSIX implements this type of lock?
>
> pthread_rwlock ? See
>
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i

> nit.html
>
> --
> Rustam Usmanov, systems engineer
> Institute of Consortia Library Information Systems,
> St.Petersburg State Polytechnic University
> Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
> Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>
>
>


Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall
In reply to this post by Stephen Croall

You are correct that no two threads can modify the same resource but I
can guarantee that this will not happen.

What I need to do is block out any readers since I don't want them to
read the data in the single item whilst I am modifying it.

Steve.


-----Original Message-----
From: Evstiounin, Mikhail [mailto:[hidden email]]
Sent: 08 December 2005 15:07
To: Stephen Croall; [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

You are wrong. Writing is not an independent. Whatever you use -- list,
table is a resource that should be protected. No two threads could
modify this resource in parallel -- only sequentially (serialized).
Unless you have personal queue per each thread and reading threads know
about each list. But later case does not have any resources that should
be protected from access from another writing threads.

-----Original Message-----
From: Stephen Croall [mailto:[hidden email]]
Sent: Thursday, December 08, 2005 10:01 AM
To: [hidden email]; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I'll try to explain how they can be used :)

Imagine a large list of items, each item can be written to in parallel
by multiple threads with no need to block since the writing of each item
is independent of the others.  However, some other threads require to
read all the items to be able to filter and generate a list of the
filtered items.  These threads can be run in parallel but cannot be run
at the same time as the writing threads, hence multiple readers and
multiple writers.

One solution is to have a read/write lock on every item in the list but
this is not performant for the filtering since it has to lock/unlock the
read lock in every item in turn and also it's a large resource usage,
since there are about 4 handles to every read/write lock.  On my system
here I had over 200,000 handles in use in a single process, which lead
me to start using pools of locks.

A more performant solution would be to have a single lock that
controlled the reader and writer threads.  When reading threads are
running the writers are blocked and when the writing threads are running
the reading threads are blocked.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:52
To: Stephen Croall; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Multiple writers doesn't make any sense at all to me, unless you mean a
message queue.  I copied a good algorithm for this out of the POSA2 book
(Pattern Oriented Software Architecture Volume 2, Patterns for
Concurrent
and Networked Objects).

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 8:08 AM
> To: Evstiounin, Mikhail; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
>
> We already use read/write locks in places but for greater parallelism
> multiple reader and multiple writer locks would be better.
>
> The current read/write lock implementation in POSIX doesn't support
> multiple writers.  Only one writer thread can process at a time - as I
> would expect.
>
> I'm after a good model for writing a "many readers"/"many writers"
lock

> implementation, which is portable from Windows to UNIX.
>
> Steve.
>
> -----Original Message-----
> From: Evstiounin, Mikhail [mailto:[hidden email]]
> Sent: 08 December 2005 14:02
> To: Stephen Croall; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> I did not quite get it. The difference between reader and writer is
that
> reader locks out writer and lets other readers continue without
waiting
> while writer acquire an exclusive lock. Multiple writers will have
> serialized access to a resource in any case. So, there no difference
> from this point of view between "one writer -- many readers" and "many
> writers -- many readers". So, if you are going to use FIFO (or you
don't
> care -- I made an assumption that all requests for resource locking is
> based on FIFO which is not true, generally speaking) in terms of how
to
> process request queue then posix approach is enough.
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Stephen
Croall
> Sent: Thursday, December 08, 2005 4:57 AM
> To: [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Thanks, but the POSIX read/write interface supports a single writer
vs.

> multiple readers.  I'm after multiple writers & readers i.e. multiple
> threads can perform writing but readers must wait and vice versa.
>
> Steve.
>
> -----Original Message-----
> From: Rustam T. Usmanov [mailto:[hidden email]]
> Sent: 08 December 2005 09:54
> To: Stephen Croall
> Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> On Thu, 8 Dec 2005, Stephen Croall wrote:
>
> > Is anyone aware of whether POSIX implements this type of lock?
>
> pthread_rwlock ? See
>
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i

> nit.html
>
> --
> Rustam Usmanov, systems engineer
> Institute of Consortia Library Information Systems,
> St.Petersburg State Polytechnic University
> Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
> Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>
>
>


Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Evstiounin, Mikhail
In reply to this post by Stephen Croall
You described situation when you have single writer-multiple readers
repeated N times. Per each entry there is one and only one writer (in
all senses).

Now, you should realize that algorithm you found is equivalent to
association of recommended POSIX read-write lock with your list. This is
very coarse granulation for parallelism. Quote from the reference:
"So, basically, if a writer is waiting, then either readers are in the
room, and the last reader will let the writer in, or writers are in the
room, in which case we waited because readers were waiting, and thus the
last writer will let in the readers, and the last reader will let us
in."

If you associate POSIX read-write lock with every entry in the list then
you will get the finest granulation but as you mention this is a little
bit resource consuming. But only one handle associated with each entry.
And it covers your situation completely. BTW, how are you going to know
if written element has been processed by all readers?

Now, I would implement a list with buckets and associate a POSIX
read-write lock with this bucket. Each writer would have two indices --
bucket index and entry index (in the bucket). Then allocating different
numbers of element per bucket you can easily change granularity of
locking from one lock per element (bucket has only one element entry) to
a global giant lock -- one bucket (all elements are in one bucket)




-----Original Message-----
From: Stephen Croall [mailto:[hidden email]]
Sent: Thursday, December 08, 2005 10:14 AM
To: Evstiounin, Mikhail; [hidden email];
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"


You are correct that no two threads can modify the same resource but I
can guarantee that this will not happen.

What I need to do is block out any readers since I don't want them to
read the data in the single item whilst I am modifying it.

Steve.


-----Original Message-----
From: Evstiounin, Mikhail [mailto:[hidden email]]
Sent: 08 December 2005 15:07
To: Stephen Croall; [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

You are wrong. Writing is not an independent. Whatever you use -- list,
table is a resource that should be protected. No two threads could
modify this resource in parallel -- only sequentially (serialized).
Unless you have personal queue per each thread and reading threads know
about each list. But later case does not have any resources that should
be protected from access from another writing threads.

-----Original Message-----
From: Stephen Croall [mailto:[hidden email]]
Sent: Thursday, December 08, 2005 10:01 AM
To: [hidden email]; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I'll try to explain how they can be used :)

Imagine a large list of items, each item can be written to in parallel
by multiple threads with no need to block since the writing of each item
is independent of the others.  However, some other threads require to
read all the items to be able to filter and generate a list of the
filtered items.  These threads can be run in parallel but cannot be run
at the same time as the writing threads, hence multiple readers and
multiple writers.

One solution is to have a read/write lock on every item in the list but
this is not performant for the filtering since it has to lock/unlock the
read lock in every item in turn and also it's a large resource usage,
since there are about 4 handles to every read/write lock.  On my system
here I had over 200,000 handles in use in a single process, which lead
me to start using pools of locks.

A more performant solution would be to have a single lock that
controlled the reader and writer threads.  When reading threads are
running the writers are blocked and when the writing threads are running
the reading threads are blocked.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:52
To: Stephen Croall; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Multiple writers doesn't make any sense at all to me, unless you mean a
message queue.  I copied a good algorithm for this out of the POSA2 book
(Pattern Oriented Software Architecture Volume 2, Patterns for
Concurrent
and Networked Objects).

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 8:08 AM
> To: Evstiounin, Mikhail; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
>
> We already use read/write locks in places but for greater parallelism
> multiple reader and multiple writer locks would be better.
>
> The current read/write lock implementation in POSIX doesn't support
> multiple writers.  Only one writer thread can process at a time - as I
> would expect.
>
> I'm after a good model for writing a "many readers"/"many writers"
lock

> implementation, which is portable from Windows to UNIX.
>
> Steve.
>
> -----Original Message-----
> From: Evstiounin, Mikhail [mailto:[hidden email]]
> Sent: 08 December 2005 14:02
> To: Stephen Croall; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> I did not quite get it. The difference between reader and writer is
that
> reader locks out writer and lets other readers continue without
waiting
> while writer acquire an exclusive lock. Multiple writers will have
> serialized access to a resource in any case. So, there no difference
> from this point of view between "one writer -- many readers" and "many
> writers -- many readers". So, if you are going to use FIFO (or you
don't
> care -- I made an assumption that all requests for resource locking is
> based on FIFO which is not true, generally speaking) in terms of how
to
> process request queue then posix approach is enough.
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Stephen
Croall
> Sent: Thursday, December 08, 2005 4:57 AM
> To: [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Thanks, but the POSIX read/write interface supports a single writer
vs.

> multiple readers.  I'm after multiple writers & readers i.e. multiple
> threads can perform writing but readers must wait and vice versa.
>
> Steve.
>
> -----Original Message-----
> From: Rustam T. Usmanov [mailto:[hidden email]]
> Sent: 08 December 2005 09:54
> To: Stephen Croall
> Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> On Thu, 8 Dec 2005, Stephen Croall wrote:
>
> > Is anyone aware of whether POSIX implements this type of lock?
>
> pthread_rwlock ? See
>
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i

> nit.html
>
> --
> Rustam Usmanov, systems engineer
> Institute of Consortia Library Information Systems,
> St.Petersburg State Polytechnic University
> Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
> Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>
>
>



Reply | Threaded
Open this post in threaded view
|

RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Stephen Croall
In reply to this post by Stephen Croall

I like the bucket description, but this still doesn't seem to fit, since
if I have a read/write lock on a bucket entry it still only allows for
one writer thread for the bucket.  It sounds more like a lock pool,
where items are given entries in the pool.  The larger the pool the less
items are under a single read/write lock.  If you had the same number of
buckets (locks in a pool) as the number of items then each item would
have a read/write lock.  I already implement a pool of locks for the
read/write locking within each list entry, this was to reduce the over
head of having a lock for every item.  Since we can have, say, 20
different lists each with 200,000 items in, this means that there would
be over 4 million handles in use by the process if each item had its own
lock :(

> BTW, how are you going to know if written element has been processed
by all readers?

If I had a lock that was blocking out the writers, then when the lock is
released and the writer threads can contine to write the entries in the
list.

I don't think I described a single writer-multiple readers repeated N
times.  For every entry in the list, yes, there can be only one writing
thread at that specific time (it might be a different thread later on)
but there are multiple threads performing their writing in parallel.
Whilst entries are being updated in the list reader threads (which have
to read all the entries in the list) must wait until all write
operations on all items have completed.  If not and they read data that
is partially written the resulting filtered list may contain invalid
entries.

Basically, I have two sets of threads, one performing writes on
individual items in a list and the other reading the entire list.  Both
sets must work in isolation but threads within each set can run in
parallel.  My initial way of doing this was to lock in each item but
this has the problem of hitting performance on the readers filtering the
items.  

A write to a single entry may take 5ms to perform, whereas a filter
could take 10s (especially since it has to do 500,000 read lock &
unlocks, along with other filter operations).  Removing the lock and
unlocks in the filtering will reduce the time taken to run greatly and
reduce the resources in use i.e. I don't need a large lock pool for the
items in the list I just need a single "multiple readers"/"multiple
writers" lock for each list.

There is the possiblity of starvation for the writing threads (they
don't get a look in) but they could be weighted such that for every 100
writers a reader is allowed through since it will take the most time.  I
don't know, it's something that I need to test.  I have 4 nice big 8-way
machines to test on :)

Steve.

PS. Thanks for the comments.  They are appreciated, it always helps to
discuss ideas with people because you get a different standpoint :)

PPS. FYI this application is a multi-threaded RPC server process written
in C++ (I recently converted it from a single-threaded C application)
that runs on Windows, AIX, HPUX, Linux & Solaris.  It caches queues
containg large numbers of items for access by 100's of client
applications, each performing filtering on the queues according to data
held in each item.  Items are added, deleted and updated in the queues,
for which the locking is already in place.  Most of the time clients
perform filtering & sorting on the large queues to get a small subset to
work on (e.g. loan call centres, support call centres etc..).  All the
queues are stored in the database and, yes, we did think about using the
database directly or using a caching mechanism like TimesTen.  Neither
was performant for us, it takes about 5 minutes just to load all the
items and their associated data into memory :(

-----Original Message-----
From: Evstiounin, Mikhail [mailto:[hidden email]]
Sent: 08 December 2005 15:48
To: Stephen Croall; [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

You described situation when you have single writer-multiple readers
repeated N times. Per each entry there is one and only one writer (in
all senses).

Now, you should realize that algorithm you found is equivalent to
association of recommended POSIX read-write lock with your list. This is
very coarse granulation for parallelism. Quote from the reference:
"So, basically, if a writer is waiting, then either readers are in the
room, and the last reader will let the writer in, or writers are in the
room, in which case we waited because readers were waiting, and thus the
last writer will let in the readers, and the last reader will let us
in."

If you associate POSIX read-write lock with every entry in the list then
you will get the finest granulation but as you mention this is a little
bit resource consuming. But only one handle associated with each entry.
And it covers your situation completely. BTW, how are you going to know
if written element has been processed by all readers?

Now, I would implement a list with buckets and associate a POSIX
read-write lock with this bucket. Each writer would have two indices --
bucket index and entry index (in the bucket). Then allocating different
numbers of element per bucket you can easily change granularity of
locking from one lock per element (bucket has only one element entry) to
a global giant lock -- one bucket (all elements are in one bucket)




-----Original Message-----
From: Stephen Croall [mailto:[hidden email]]
Sent: Thursday, December 08, 2005 10:14 AM
To: Evstiounin, Mikhail; [hidden email];
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"


You are correct that no two threads can modify the same resource but I
can guarantee that this will not happen.

What I need to do is block out any readers since I don't want them to
read the data in the single item whilst I am modifying it.

Steve.


-----Original Message-----
From: Evstiounin, Mikhail [mailto:[hidden email]]
Sent: 08 December 2005 15:07
To: Stephen Croall; [hidden email]; [hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

You are wrong. Writing is not an independent. Whatever you use -- list,
table is a resource that should be protected. No two threads could
modify this resource in parallel -- only sequentially (serialized).
Unless you have personal queue per each thread and reading threads know
about each list. But later case does not have any resources that should
be protected from access from another writing threads.

-----Original Message-----
From: Stephen Croall [mailto:[hidden email]]
Sent: Thursday, December 08, 2005 10:01 AM
To: [hidden email]; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

I'll try to explain how they can be used :)

Imagine a large list of items, each item can be written to in parallel
by multiple threads with no need to block since the writing of each item
is independent of the others.  However, some other threads require to
read all the items to be able to filter and generate a list of the
filtered items.  These threads can be run in parallel but cannot be run
at the same time as the writing threads, hence multiple readers and
multiple writers.

One solution is to have a read/write lock on every item in the list but
this is not performant for the filtering since it has to lock/unlock the
read lock in every item in turn and also it's a large resource usage,
since there are about 4 handles to every read/write lock.  On my system
here I had over 200,000 handles in use in a single process, which lead
me to start using pools of locks.

A more performant solution would be to have a single lock that
controlled the reader and writer threads.  When reading threads are
running the writers are blocked and when the writing threads are running
the reading threads are blocked.

Steve.


--

J. Senior Software Engineer, Tibco Software Ltd.
T. +44 (0) 1792 360773
M. +44 (0) 7788 971394
E. [hidden email]
W. www.tibco.com

-----Original Message-----
From: Robert Kindred [mailto:[hidden email]]
Sent: 08 December 2005 14:52
To: Stephen Croall; Evstiounin, Mikhail;
[hidden email]
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"

Multiple writers doesn't make any sense at all to me, unless you mean a
message queue.  I copied a good algorithm for this out of the POSA2 book
(Pattern Oriented Software Architecture Volume 2, Patterns for
Concurrent
and Networked Objects).

Robert Kindred

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]]On Behalf Of Stephen
Croall

> Sent: Thursday, December 08, 2005 8:08 AM
> To: Evstiounin, Mikhail; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
>
> We already use read/write locks in places but for greater parallelism
> multiple reader and multiple writer locks would be better.
>
> The current read/write lock implementation in POSIX doesn't support
> multiple writers.  Only one writer thread can process at a time - as I
> would expect.
>
> I'm after a good model for writing a "many readers"/"many writers"
lock

> implementation, which is portable from Windows to UNIX.
>
> Steve.
>
> -----Original Message-----
> From: Evstiounin, Mikhail [mailto:[hidden email]]
> Sent: 08 December 2005 14:02
> To: Stephen Croall; [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> I did not quite get it. The difference between reader and writer is
that
> reader locks out writer and lets other readers continue without
waiting
> while writer acquire an exclusive lock. Multiple writers will have
> serialized access to a resource in any case. So, there no difference
> from this point of view between "one writer -- many readers" and "many
> writers -- many readers". So, if you are going to use FIFO (or you
don't
> care -- I made an assumption that all requests for resource locking is
> based on FIFO which is not true, generally speaking) in terms of how
to
> process request queue then posix approach is enough.
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Stephen
Croall
> Sent: Thursday, December 08, 2005 4:57 AM
> To: [hidden email]
> Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
>
> Thanks, but the POSIX read/write interface supports a single writer
vs.

> multiple readers.  I'm after multiple writers & readers i.e. multiple
> threads can perform writing but readers must wait and vice versa.
>
> Steve.
>
> -----Original Message-----
> From: Rustam T. Usmanov [mailto:[hidden email]]
> Sent: 08 December 2005 09:54
> To: Stephen Croall
> Subject: Re: Good Algorithm for "Multiple Readers"/"Multiple Writers"
>
> On Thu, 8 Dec 2005, Stephen Croall wrote:
>
> > Is anyone aware of whether POSIX implements this type of lock?
>
> pthread_rwlock ? See
>
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_i

> nit.html
>
> --
> Rustam Usmanov, systems engineer
> Institute of Consortia Library Information Systems,
> St.Petersburg State Polytechnic University
> Address:  29, Politekhnitcheskaya str., St.Petersburg, 195251, Russia
> Tel/fax: +7 812 552 7654        <URL:http://www.unilib.neva.ru/olsc/>
>
>