Synchronization for multiple readers, single writer?

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)

From stackoverflow

• 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.

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

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

• 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.

• 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.

• Nobody can really answer your question whether the serialization will affect performance in your application very much - you have to profile that for yourself, and the results will depend greatly on the number of threads, cores and the specific workload.

  Note however that using more clever synchronization than critical sections, such as the reader-writer-lock, can introduce starvation problems that may be hard to debug and fix. You really need to look hard at whether the increased throughput outweighs the potential problems. Note also that there may not actually be an increase in throughput, especially if the locked code is very short and fast. There is a nice article by Jeffrey Richter that actually contains this quote:

  Performance Even when there is no contention for a ReaderWriterLock, its performance is very slow. For example, a call to its AcquireReaderLock method takes about five times longer to execute than a call to Monitor's Enter method.

  This is for .NET of course, but the underlying principles do apply as well.

  Smasher : Jeffrey Richter is talking about the implementation of a ReaderWriterLock in the .NET library. He himself presents an efficient implementation of such a lock in the very same article. But thanks! I was kind of afraid that there won't be a clear answer ;)

  mghie : @Smasher: Indeed. There were however problems with MREW implementation in the VCL, and people did not really trust it. Jeffrey Richter has been doing this stuff for > 15 years, I'd trust his judgement and implementations. Just try to be informed about what you are getting into.

• 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.

  Rob Kennedy : Beware that that class is fatally broken in some Delphi versions. It's fixed as of Delphi 2005, maybe earlier.