Thread synchronisation for C++ map

Question

I'm creating a multithreaded c++ program using pthread (c++98 standard).

I have a std::map that multiple threads will access. The access will be adding and removing elements, using find, and also accessing elements using the [] operator.

I understand that reading using the [] operator, or even modifying the elements with it is thread safe, but the rest of the operations are not.

First question: do I understand this correctly?

Some threads will just access the elements via [], while others will do some of the other operations. Obviously I need some form of thread synchronisation.

The way I see this should work is: - While no "write" operation is being done to the map, threads should all be able to "read" from it concurrently. - When a thread wants to "write" to the map, it should set a lock so no thread starts any "read" or "write" operation, and then it should wait until all "read" operations have completed, at which point it would perform the operation and release the locks. - After the locks have been released, all threads should be able to read freely.

The main question is: what thread synchronisation methods can I use to achieve this behaviour?

I have read about mutex, conditional variables and semaphores, and as far as I can see they won't do excatly what I need. I'm familiar with mutex but not with cond. variables or semaphores.

The main problem I see is that I need a way of locking threads until something happens (the write operation ends) without those threads then locking anything in turn. Also I need something like an inverted semaphore, that blocks while the counter is more than 1 and then wakes when it is 0 (i.e. no read operation is being done).

Thanks in advance.

P.S. It's my first post. Kindly indicate if I'm doing something wrong!

Answer 1

I understand that reading using the [] operator, or even modifying the elements with it is thread safe, but the rest of the operations are not.

Do I understand this correctly?

Well, what you've said isn't quite true. Concurrent readers can use [] to access existing elements, or use other const functions (like find, size()...) safely if there's no simultaneous non-const operations like erase or insert mutating the map<>. Concurrent threads can modify different elements, but if one thread modifies an element you must have some synchronisation before another thread attempts to access or further modify that specific element.

When a thread wants to "write" to the map, it should set a lock so no thread starts any "read" or "write" operation, and then it should wait until all "read" operations have completed, at which point it would perform the operation and release the locks. - After the locks have been released, all threads should be able to read freely.

That's not quite the way it works... for writers to be able to 'wait until all "read" operations have completed', the reader(s) need to acquire a lock. Writers then wait for that same lock to be released, and acquire it themselves to restrict other readers or writers until they've finished their update and release it.

what thread synchronisation methods can I use to achieve this behaviour?

A mutex is indeed suitable, though you will often get higher performance from a reader-writer lock (which allows concurrent readers, some also prioritorise waiting writers over further readers). Related POSIX threads functions include: pthread_rwlock_rdlock, pthread_rwlock_wrlock, pthread_rwlock_unlock etc..

To contrast the two approaches, with readers and writers using a mutex you get serialisation something like this:

THREAD   ACTION
reader1  pthread_mutex_lock(the_mutex) returns having acquired lock, and
         thread starts reading data
reader2  pthread_mutex_lock(the_mutex) "hangs", as blocked by reader1
writer1  pthread_mutex_lock(the_mutex) hangs, as blocked by reader1
reader1  pthread_mutex_unlock(the_mutex) -> releases lock
NOTE: some systems guarantee reader2 will unblock before writer1, some don't
reader2  blocked pthread_mutex_lock(the_mutex) returns having acquired lock,
         and thread starts reading data
reader1  pthread_mutex_lock(the_mutex) hangs, as blocked by reader2
reader2  pthread_mutex_unlock(the_mutex) -> releases lock    
writer1  blocked pthread_mutex_lock(the_mutex) returns having acquired lock,
         and thread starts writing and/or reading data
writer1  pthread_mutex_unlock(the_mutex) -> releases lock    
reader1  blocked pthread_mutex_lock(the_mutex) returns having acquired lock,
         and thread starts reading data
...etc...

With a read-write lock, it might be more like this (notice the first two readers run concurrently):

THREAD   ACTION
reader1  pthread_rwlock_rdlock(the_rwlock) returns having acquired lock, and
         thread starts reading data
reader2  pthread_rwlock_rdlock(the_rwlock) returns having acquired lock, and
         thread starts reading data
writer1  pthread_rwlock_wrlock(the_rwlock) hangs, as blocked by reader1/2
reader1  pthread_rwlock_unlock(the_rwlock) -> releases lock
reader1  pthread_rwlock_rwlock(the_rwlock) hangs, as pending writer
reader2  pthread_rwlock_unlock(the_rwlock) -> releases lock    
writer1  blocked pthread_rwlock_wrlock(the_rwlock) returns having acquired lock,
         and thread starts writing and/or reading data
writer1  pthread_rwlock_unlock(the_rwlock) -> releases lock    
reader1  blocked pthread_rwlock_rwlock(the_rwlock) returns having acquired lock,
         and thread starts reading data
...etc...