0

I have a multithreaded application which has a linked list. A lot of places in the code are traversing the linked list, but there is ONE place where nodes are removed. The places where the linked list is traversed need not be protected from each other, ie, they can happen parallelly but the place where the removal happens needs to happen when none of the other traversing places are in action. If I have a mutex and lock all places - both all the traversing places and the delete place, it works, but that would slow down the application as a whole. What I plan to do is, have a variable(semaphore) that would increment before the traversal starts and decrement it when the traversal ends. The increment and the decrement is protected by a mutex variable. The delete place would work by holding the mutex variable AND when the counting semaphore is 0(indicating nobody is traversing the linked list). Would this work? Is this the right way to design this situation? Are there better ways? Any help is appreciated.

TIA

quickdraw
  • 247
  • 1
  • 2
  • 12

2 Answers2

2

Your looking for a reader/writer mutex aka shared_mutex. You can implement it, use boost and C++14 or C++17

Relevant SO question:

MokaT
  • 1,416
  • 16
  • 37
  • thanks! That works! But would like to know if the solution I proposed would work? I see that reader/writer locks are implemented using mutex and signals, my solution look very simple. Would it work? – quickdraw Jan 04 '18 at 17:29
0

As others have pointed out, you should be using reader/writer locks. Still, since you are interested in whether your proposed solution is going to work as well, the answer to that is no.

Before I explain why, let me first point out that you are using the term "semaphore" incorrectly. Based on your description, it looks like you are calling a simple counter variable a "semaphore", since you are not relying on decrementing a semaphore blocking when the semaphore value is zero.

Anyway, the main reason your solution is not going to work is that you don't have a strategy for dealing with the writer thread encountering a non-zero counter variable, which indicates one or more read operations are in progress. What will your writer thread do then? Busy loop?

Joseph Artsimovich
  • 1,499
  • 10
  • 13
  • thanks for that! The reader threads just increment the counter(while being locked and release it after it increments). The writer is a background job which just returns if the counter is non-zero. It will do its work next time it comes back, it will not block anything. The writer(node deletion) if possible does the job when it comes in, otherwise just returns to do the job the next time he comes in(hes fine with the delay). I agree, it is not that efficient to the writer, but do u still think it would not work? Just learning, so wanted to know. Thanks! – quickdraw Jan 05 '18 at 05:17
  • @user7795930 If it's acceptable to simply skip write access in case a read access is in progress, then yes, your solution should work. That would be like implementing `std::shared_mutex` without `lock()` but with `try_lock()`. – Joseph Artsimovich Jan 05 '18 at 07:02