From: "Evstiounin, Mikhail" <Mikhail.Evstiounin@ca.com>
To: "Stephen Croall" <scroall@tibco.com>, <RKindred@SwRI.edu>,
<pthreads-win32@sources.redhat.com>
Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers"
Date: Thu, 08 Dec 2005 15:06:00 -0000 [thread overview]
Message-ID: <163D3F27E93137439CEB0BB9382257E7187693@USILMS12.ca.com> (raw)
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:scroall@tibco.com]
Sent: Thursday, December 08, 2005 10:01 AM
To: RKindred@SwRI.edu; Evstiounin, Mikhail;
pthreads-win32@sources.redhat.com
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. scroall@tibco.com
W. www.tibco.com
-----Original Message-----
From: Robert Kindred [mailto:RKindred@SwRI.edu]
Sent: 08 December 2005 14:52
To: Stephen Croall; Evstiounin, Mikhail;
pthreads-win32@sources.redhat.com
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: pthreads-win32-owner@sourceware.org
> [mailto:pthreads-win32-owner@sourceware.org]On Behalf Of Stephen
Croall
> Sent: Thursday, December 08, 2005 8:08 AM
> To: Evstiounin, Mikhail; pthreads-win32@sources.redhat.com
> 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:Mikhail.Evstiounin@ca.com]
> Sent: 08 December 2005 14:02
> To: Stephen Croall; pthreads-win32@sources.redhat.com
> 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: pthreads-win32-owner@sourceware.org
> [mailto:pthreads-win32-owner@sourceware.org] On Behalf Of Stephen
Croall
> Sent: Thursday, December 08, 2005 4:57 AM
> To: pthreads-win32@sources.redhat.com
> 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:rustam@unilib.neva.ru]
> 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/>
>
>
next reply other threads:[~2005-12-08 15:06 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-12-08 15:06 Evstiounin, Mikhail [this message]
-- strict thread matches above, loose matches on Subject: below --
2005-12-08 16:35 Stephen Croall
2005-12-08 15:47 Evstiounin, Mikhail
2005-12-08 15:16 Stephen Croall
2005-12-08 15:11 Stephen Croall
2005-12-08 15:09 Stephen Croall
2005-12-08 15:06 Stephen Croall
2005-12-08 15:02 Evstiounin, Mikhail
2005-12-08 15:01 Stephen Croall
2005-12-08 15:00 Evstiounin, Mikhail
2005-12-08 14:49 Stephen Croall
2005-12-08 14:09 Stephen Croall
2005-12-08 14:53 ` Robert Kindred
2005-12-08 14:02 Evstiounin, Mikhail
2005-12-08 9:57 Stephen Croall
2005-12-08 9:09 Stephen Croall
2005-12-08 14:46 ` Robert Kindred
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=163D3F27E93137439CEB0BB9382257E7187693@USILMS12.ca.com \
--to=mikhail.evstiounin@ca.com \
--cc=RKindred@SwRI.edu \
--cc=pthreads-win32@sources.redhat.com \
--cc=scroall@tibco.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).