Using UML to detect potential race conditions in design

Question

I'm battling a potential race condition in my application, which relies on multiple threads accessing a shared object to determine what their next logical operation should be. I certainly don't have a problem just scribbling stuff on a piece of paper or on the whiteboard, and using this to map out access to this shared object. However, it would be nice to do it with UML diagrams. I typically use UML however it makes sense to me visually, and not always the "UML way". I pretty much only use simple diagrams like state, class, activity, and communication diagrams. I'm not sure which of the others available is best suited to mapping out multiple threads + shared memory. Can anyone offer their suggestions, and / or experiences with modeling this sort of thing?

Answer 1

I visualize the instruction ordering using timelines. Lets consider the following code.

x++;
y++;

So our instructions break down like this.

Read(x) --> Increment(x) --> Write(x) --> Read(y) --> Increment(y) --> Write(y)

For brevity lets shorten that to the following.

R(x) --> I(x) --> W(x) --> R(y) --> I(y) --> W(y)

So if we have 2 threads perfoming these instructions then we can draw 2 timelines like so.

T1: R(x) --> I(x) --> W(x) --> R(y) --> I(y) --> W(y)
T2: R(x) --> I(x) --> W(x) --> R(y) --> I(y) --> W(y)

Now here is the giant leap. When you draw the possible timelines do so from the perspective of another thread. This is important because instructions can be reordered from the perspective of another thread (with constraints¹). So the following diagram is a completely valid execution sequence for T1 as seen from another thread.

T1: R(y) --> R(x) --> I(x) --> I(y) --> W(y) --> W(x)

Now lets add the [ and ] characters to represent lock acquire and lock release respectively. A [ cannot move past another [ and it cannot move before a ]. Similar reordering constraints apply for the ] character. Also of importance is that no instruction can move past either [ or ], but they are still free to move around within the lock section. The end result is that locks serialize the execution of instructions (you know that already) and they prevent the reordering to some degree (that you may not have known).

T1: [ -> R(x) ------> I(x) --> W(x) ---> ] ----------------------------------------------------------------------------> [ -----> R(y) -> I(y) --> W(y) -----> ]
T2: -------------------------------------> [ -> R(x) -----> I(x) ---> W(x) ----> ] -> [ --> R(y) --> I(y) --> W(y) -> ]

So when you draw your timelines the --> (spacing between instructions) can be arbitrarily lengthened or shortened to simululate the interleaving of threads. The length of the delays of the instructions will be highly dependent on the thread scheduler, synchronization mechanisms used, etc. and will usually be very random.

Experiment with shifting the instructions left and right across the timeline to help you visualize what could occur. Create your own symbols and abbreviations for locks, instructions, and delays to help with the visualization and to provide clues on how far you can move each element to the left or the right.

¹In reality no read of the same variable can move past a write. That should be intuitive, but it does not hurt to formalize that constraint.