Synchronization for multiple readers, single write

Question

Another synchronization question...I hope you guys don't get annoyed ;)

Assume the following scenario: one central data structure (very large, so I don't really want to make it immutable and copy it around whenever a change occurs. I even don't want to keep multiple copies in memory), multiple reader threads that access that data structure read-only and one writer thread which keeps the data structure up to date in the background.

I currently synchronize all accesses to the data structure, which works just fine (no synchronization effects, no deadlocks). What I don't like about this approach is that most of the time I have a lot of reader threads active and the writer thread only active every now and then. Now it is completely unnecessary for the reader threads to wait for other reader threads to finish. They could easily access the data structure in parallel as long as the writer thread is not currently writing.

Is there a nice and elegant way to solve this kind of scenario?

EDIT: Thank you very much for the answers and links! Let me add just another short and related question: if the code executed within the reader's critical sections takes only a very short time (like just a hash table lookup), is it even worth considering implementing one of the techniques you describe or is the serialization effect of the locks not so bad in this case? Scalability and performance are very important. What do you think?

EDIT 2: I just looked into one implementation of a single writer / mulitple readers - lock and this implementation uses a monitor to synchronize some code in the WaitToRead method. Doesn't this cause the same serialization effect that I wanted to avoid in the first place? (Still assuming that the code to be synchronized is short and fast)

Answer 1

What you're looking for (and what vartec described) is called Reader(s)-Writer-Lock.

Answer 2

The reader-writer lock is what you need. Tutorial has a description, but I'm sure someone was adding this as standard to Delphi. May be worth checking D2009 doesn't have it already.

Answer 3

Using a Reader-Writer lock will solve the problem. Multiple readers can access a database and a writer gets a lock once all readers are finished reading.

However, this might cause the writer to never have access to the source as there are always new readers who want access. This can be solved by blocking new readers when a writer wants access: the writer has a bigger priority. The writer gets access once all the readers on the source are done reading.

Answer 4

You can find some detailed notes on solving this problem at msdn magazine and an excerpt from Programming applications for MS windows.

Answer 5

Whenever writer wants to access, you enqueue incoming readers (have them wait on Condition), wait for the active readers to finish, write and when finished let the enqueued readers access.

Answer 6

There is a class for that purpose in RTL(sysutils) : TMultiReadExclusiveWriteSynchroniser

It is very easy to use. You don't need to strictly categorize your threads like reader or writer. Just call "BeginRead" or "BeginWrite" in a thread for starting a thread safe operation. Call "EndRead" or "EndWrite" for finishing the operation.