Mutex lock on write only

Question

I have a multithreaded C++ application which holds a complex data structure in memory (cached data).

Everything is great while I just read the data. I can have as many threads as I want access the data.

However the cached structure is not static.

If the requested data item is not available it will be read from database and is then inserted into the data tree. This is probably also not problematic and even if I use a mutex while I add the new data item to the tree that will only take few cycles (it's just adding a pointer).
There is a Garbage Collection process that's executed every now and then. It removes all old items from the tree. To do so I need to lock the whole thing down to make sure that no other process is currently accessing any data that's going to be removed from memory. I also have to lock the tree while I read from the cache so that I don't remove items while they are processed (kind of "the same thing the other way around").

"Pseudocode":

function getItem(key)
   lockMutex()
   foundItem = walkTreeToFindItem(key)
   copyItem(foundItem, safeCopy)
   unlockMutex()
   return safeCopy
end function

function garbageCollection()
   while item = nextItemInTree
      if (tooOld) then
         lockMutex()
         deleteItem(item)
         unlockMutex()
      end if
   end while
end function

What's bothering me: This means, that I have to lock the tree while I'm reading (to avoid the garbage collection to start while I read). However - as a side-effect - I also can't have two reading processes at the same time anymore.

Any suggestions?

Is there some kind of "this is a readonly action that only collides with writes" Mutex?

Related: http://stackoverflow.com/questions/244316/reader-writer-locks-in-c — Shay Erlichmen, Oct 21 '09 at 16:29

score 11 · Accepted Answer · edited May 23 '17 at 10:32

11

Look into read-write-lock.

You didn't specify which framework can you use but both pThread and boost have implemented that pattern.

edited May 23 '17 at 10:32

Community

1
1

answered Oct 21 '09 at 16:26

Shay Erlichmen

31,691
7
68
87

score 4 · Answer 2 · answered Oct 21 '09 at 16:32

4

The concept is a "shared reader, single writer" lock as others have stated. In Linux environments you should be able to use pthread_rwlock_t without any framework. I would suggest looking into boost::shared_lock as well.

answered Oct 21 '09 at 16:32

D.Shawley

58,213
10
98
113

score 3 · Answer 3 · answered Oct 21 '09 at 16:26

3

I suggest a reader-writer lock. The idea is you can acquire a lock for "reading" or for "writing", and the lock will allow multiple readers, but only one writer. Very handy.

answered Oct 21 '09 at 16:26

asveikau

39,039
2
53
68

3

There is also a queuing principle, so that if a writer ask for access it won't have to wait for a period of non-read, but will delay future read-requests until it has obtained its access and executed its work. – Matthieu M. Oct 21 '09 at 16:34

score 0 · Answer 4 · answered Nov 30 '19 at 14:36

In C++17 this type of access (multiple read, single write) is supported directly with std::shared_mutex. I think this was adopted from boost::shared_lock. The topic is also described with an example in Anthony Williams's C++ Concurrency in Action. https://livebook.manning.com/book/c-plus-plus-concurrency-in-action-second-edition/chapter-3/185.

The essential bits are:

use std::shared_lock on reads where shared access is allowed
- existing shared_locks don't prevent a new shared_lock from locking
use std::unique_lock on update/write functions, where exclusive access is needed
- will wait until all existing shared reads complete, as well as other writes
- precludes any other reads or writes while locked

Mutex lock on write only

4 Answers4