How do handle a mutex with a loop correctly?

Question

This is a mainly theoretical question, so please don't stone me for bringing it up.

Now, I've read that recursive mutexes are evil. And I get why.

However assume you have this little situation:

LockMutex();
for(ListIterator it = List.begin(); it != List.end(); ++it) {
    //doStuff, which might possibly alter the List contents
}
UnlockMutex();

Seems familiar to many, I'm sure. Now the big question is, how to handle this situation correctly?

After putting some thought into it and without the use of a recursive mutex (which are evil), the only possible option is to do something like this:

LockMutex();
for(ListIterator it = List.begin(); it != List.end(); ++it) {
    UnlockMutex();
    //doStuff, which might possibly alter the List contents
    LockMutex();
}
UnlockMutex();

Now, one of the reasons why 'recursive mutexes are evil' is, that they require additional overhead to remember who has the lock and how often it was locked...and it's no additional overhead to unlock and relock the mutex on every single iteration?

Furthermore, what is to happen, if another thread accesses the list while the mutex is unlocked and alters the very element this iteration is on? Possibly removes the element we're currently on, essentially invalidating the iterator, leading to a very nasty bug?

I know that by locking the entire list for the duration of the iteration is a terrible bottleneck, but I think for most light applications that's something I'd be able to live with compared to the risk of crashing the entire application by allowing a second thread to mess with the list while I'm not looking.

I've also looked at ReaderWriter-Locks, but the problem remains the same. Technically, as soon as the content of the loop MAY alter the list (which is hard to foresee, especially if you're working with polymorphism), you'd need to acquire a writing lock to the list, which again means, that no other thread may access the list at the time. And the issue of an iterator getting invalidated still stands.

So yeah, any ideas or words of wisdom for me?

In your second code segment, what are you locking? The read-only iterator? — nicky_zs, Jul 10 '14 at 14:38
@nicky_zs Technically the access to the list, so the list can not be altered while the iterator is being moved. But that won't protect the iterator from becoming invalid while the list is unlocked. — ATaylor, Jul 11 '14 at 05:14
Your code seems strange. Maybe you can rewrite you for-loop with a while-loop. And, is semaphore considered? @ATaylor — nicky_zs, Jul 11 '14 at 06:01
@nicky_zs How would putting it in a while-loop help? Or using a semaphore? (To be perfectly honest, I have yet to find a good explanation on how a semaphore works) — ATaylor, Jul 11 '14 at 06:16
I have no idea what you want to do with your code, so I can't give any suggestion. @ATaylor — nicky_zs, Jul 11 '14 at 06:19
@nicky_zs I see...well, it's been 'marked as duplicate' anyway, so thanks for trying. I'll just try to figure it out by myself. — ATaylor, Jul 11 '14 at 06:22

score 2 · Answer 1 · answered Jul 10 '14 at 14:20

//doStuff, which might possibly alter the List contents

Which means that also your iterator is maybe not longer valid. So I believe that setting a mutex is the second problem in your context.

And yes, if you can iterate through your list with a valid iterator you have to protect the complete list if the external access will modify the list in a way which makes the iterators invalid. I believe you can't guarantee that external access to the list will keep your iterators valid. As so: The mutex must be around your loop.

But first you should keep in mind that your access to the list inside your mutex protected loop must keep the iterators valid.

While inside the loop, I can at least make sure that the thread isn't altering the list in a way that invalidates the iterator, while I can't make sure that's not happening in another thread with different parameters. But thanks for the input. — ATaylor, Jul 11 '14 at 05:13

How do handle a mutex with a loop correctly?

1 Answers1