Reading a mutex write in C ++

Question

This is an interview question. How do you implement a read / write mutex? There will be many read and write threads to the resource. I do not know how to do that. If there is any information, please let me know.

Update: I'm not sure that my expression above is valid / understandable. But I really want to know how to implement several read operations and several records on one object in terms of a mutex and other synchronization objects?

Answer 1

Check off the Dekker algorithm .

The Decker algorithm is the first known correct solution to the exception problem in parallel programming. The solution is attributed to the Dutch mathematician Th. J. Decker by Edsger W. Dijkstra in his manuscript on the interaction of sequentially processes. It allows two threads to share a one-time resource without conflict, using only shared memory for communication.

Note that Dekker's algorithm uses spinlock (not wait ).
(Decision by T.J. Dekker, cited by E.W. Dijkstra in article EWD1303 )

Answer 2

The short answer is that it is surprisingly difficult to roll your own read / write lock. It is very easy to miss a very subtle time issue that can lead to a deadlock, two threads that think they have an “exclusive” lock, etc.

In short, you need to keep track of the number of readers at any given time. Only when the number of active readers is zero, should you grant access to stream recording. There are some options for choosing whether readers or writers need priority. (Often you want to give authors a priority based on the assumption that recording is less frequent.) (Surprisingly) the hard part is that no author gets access when there are readers, or vice versa.

There is an excellent MSDN article, “Compound Win32 Synchronization Objects,” which allows you to create read / write locks. It starts simple, and then it becomes increasingly difficult to handle all corner cases. One thing that stood out was that they showed a pattern that looked great - then they will explain why it really doesn't work. If they did not point out problems, you might never have noticed. Well worth a read.

Hope this will be helpful.

Answer 3

This sounds like a pretty tough interview question; I would not "implement" read / write mutexes, in the sense of writing from scratch - there are much better ready-made solutions. A reasonable real world would be to use an existing type of mutex. Perhaps they really wanted to know how you would use this type?

Answer 4

Afaik, you will need either an atomic comparison instruction or a replacement, or you will need to disable interrupts. See Compare-and-swap on Wikipedia. At least, how the OS will implement it. If you have an operating system, stand on your shoulders and use an existing library (like boost ).