Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm trying to wrap my head around different concurrency solutions to several threads iterating over the same collection but I'm having difficulty coming up with good realistic (but preferably easy to model) scenarios to code against. I'm looking for realistic scenarios for:

  1. A scenario where several threads can iterate over a collection simultaneously and lock each item as it comes to it and do some modification, item's can't be visible in a partially updated state
  2. A scenario where different threads try to iterate over a collection but only one at a time should be allowed to
  3. A scenario where several threads might iterate over a collection for reading, but only one thread might iterate for writing

Any other nice concurrency iterating scenarios you might come up with are welcome as well :) thanks!

share|improve this question
    
I don't really see the difference between 1. and 3. You can't read an item if is it being written to and you can't write to an item if it is being read. I mean you could, but that wouldn't really make any sense, so essentially even though you are not modifying the item when read you still need to lock it for concurrency. –  Pemdas Apr 6 '11 at 20:23
    
Also if the list is changing, which is likely in a real world scenario then you can't have multiple thread iterating over the data at the same time. –  Pemdas Apr 6 '11 at 20:24
    
Pemdas, assume the iterators are thread-safe –  konrad Apr 6 '11 at 20:34
    
@MKO it is easier to make that assumption than it is to deliver it in the real world. What happens if A is iterating over a collection at the same time that B modifies it and causes the collection to need to be resized? Lots of fun ensues. –  btilly Apr 6 '11 at 21:27
2  
@MKO: so if iterator A is sorting while iterator B is printing, what happens in the "thread-safe" iterator? A snapshot? –  Мסž Apr 6 '11 at 22:56

5 Answers 5

I am not sure about the need to find real world scenarios.

Why not just write code with these constraints where they are trying to get access to an effectively empty null object. This eliminates the need to solve the domain problem at the same time.

Add a variable time factor to the act of "touching" the null object to add some variance -- and watch the contention go, and toggle up and down the number of contenting threads and objects.

Then log all the collisions that take place - which hopefully you would have neatly protected, or watch it deadlock and trawl through your logs to spot where the deadlock happend.

share|improve this answer
1  
I find it easier to solve real problems if you have some real problem you can relate to. If you try to solve an abstract problem you tend to come up with abstract solutions –  konrad Apr 6 '11 at 21:15
    
Agreed - but in this case are you not just trying to understand the concepts of threaded race conditions.. after that then I would make a real projcet... perhaps something like a call center where the phone operators are the resource that are used for a locked period of time when on a call, and the callers who are threads searching for an available resource. Then track the time it takes to get answered :-) –  Stephen Bailey Apr 7 '11 at 7:31

Collections have specific concurrency issues. I'm a .net developer, but I can describe the issues in, fairly general terms I think.

Internally the collection could be implemented in a number of different ways. Let's assume it's just a linked list.

The collection can support a number of operations. Add and delete, delete[index] and insert. It also allows you to iterate over the collection.

So you have concurrent access. Here are some situations to consider.

You are iterating over the entire collection. You are doing something like (pseudo code)

for count = 1 to collection.count do something next

For the sake of the following, count currently = 5 and collection.count = 10.

While doing this you do any of the following. Run each scenario individually:

1) Add an item to the collection. This will probably work as long as the behaviour is to insert the item at the end.

2) Insert an item at position 3 Not too bad, count goes up one, the new item won't be included in our iteration though.

3) Delete an item at position 3 Ok, now we have issues. Count is now 9 (remember do each scenario on its own, 1) and 2) haven't happened in this case). our current position is still 5, but because 3 was removed, the list has moved left, we are now going to skip an item because item 6 is now item 5, and we're already reading 5. But it gets worse!!! Imagine your stuff that you are doing with item 5 is reading members of the object at position 5 based on its index.

thread 1 --> collection[5].element1 = 10 thread 2 --> delete item 3 thread 1 --> collection[5].element2 = 10

we've actually now set two elements on different items.

It get's worse still in the next one.

4) delete item 5 while currently on item 5. Yep, you remove the item, perhaps call its "Dispose" method as you remove it but you're still treating it as an active member of the collection on another thread.

That's simple cases. Hope it gives you some ideas.

share|improve this answer

If you're looking for concrete examples, one scenario I'd use is a simple list of items, say the database favourite "Products". You have an inwards goods department that adds products sometimes and changes the quantity of a product often. You have an outwards goods department that often changes the quantity of a product but never adds or removes products. You have a manager who adds, deletes, renames, changes quantities and reports on products. And you have a live stocktake team who add, remove and change quantities.

That covers the common CRUD actions, and makes use cases easy to generate. If your collection is also sorted you could add location to the above and sort by that (and just use another integer property for that to make it simple). I keep emphasising sorting because that rapid remove-add cycle is tricky to test.

share|improve this answer

(1) would be a naiive object-oriented approach to keeping a collection of moving objects in a simulation of sorts that needs to be made visible to other threads: The "simulator" would need to lock, not only its list (to prevent slicing), but also each "object" it is updating.

Realistically, I would do that for something like a pathfinder: Lock the agent collection to prevent slicing and iterate over all agents, putting them into a "job queue" (the queue pointers would be reserved for this purpose only, so no other thread would see it).

Then, using OpenMP or something similar, I'd have each worker thread quickly lock the queue, pop an agent off of it, then unlock the queue (or use an [almost] lock-free queue). Each worker thread locks its agent before updating it.

My answer for (1) could also apply to (2): The "simulator" and whatever keeps the collection of agents are really the only things that should be allowed to iterate over the whole list (and desirably do so in one thread at a time, or just one thread period).

An examaple for (3) would be a string table: Multiple threads can obtain a shared lock to look up existing strings, and only one thread at a time can add a string to the table.

share|improve this answer

An example I discovered at a previous workplace:

A piece of code had a collection of frame buffers that were being updated by multiple threads. The threads were:

  • A thread that received frames from the network, processed them and updated the buffer in question. (Write operation)
  • A thread that converted frames to pixels for display (Read operation)
  • Another piece of code that maintained the connection status of the network, and replaced the buffer with the text "Connection Lost". (Write operation)

These frame buffers weren't properly synchronised. I managed to find that the reading thread was iterating the frame buffers and pushing them to native code, when thread 3 came along and caused the entire app to crash.

In this case, reading and writing had to become exclusive (your scenario 2).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.