From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 7682 invoked by alias); 8 Dec 2005 15:47:59 -0000 Received: (qmail 7668 invoked by uid 22791); 8 Dec 2005 15:47:58 -0000 X-Spam-Check-By: sourceware.org Received: from mail15.ca.com (HELO mail15.ca.com) (208.232.182.11) by sourceware.org (qpsmtpd/0.31) with ESMTP; Thu, 08 Dec 2005 15:47:56 +0000 Received: from USILMS12.ca.com ([141.202.201.12]) by mail15.ca.com with Microsoft SMTPSVC(5.0.2195.6713); Thu, 8 Dec 2005 09:47:54 -0600 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Subject: RE: Good Algorithm for "Multiple Readers"/"Multiple Writers" Date: Thu, 08 Dec 2005 15:47:00 -0000 Message-ID: <163D3F27E93137439CEB0BB9382257E7187732@USILMS12.ca.com> From: "Evstiounin, Mikhail" To: "Stephen Croall" , , X-IsSubscribed: yes Mailing-List: contact pthreads-win32-help@sourceware.org; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: pthreads-win32-owner@sourceware.org X-SW-Source: 2005/txt/msg00144.txt.bz2 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:scroall@tibco.com]=20 Sent: Thursday, December 08, 2005 10:14 AM To: Evstiounin, Mikhail; RKindred@SwRI.edu; pthreads-win32@sources.redhat.com 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:Mikhail.Evstiounin@ca.com]=20 Sent: 08 December 2005 15:07 To: Stephen Croall; RKindred@SwRI.edu; pthreads-win32@sources.redhat.com 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:scroall@tibco.com]=20 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. --=20 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]=20 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 > >