Multiple Joins

The task of generating only valid schedules is really more complex than I thought. As stated in the previous post, not scheduling a thread before it is started is pretty easy, I’ll just have to watch the THREADSTART synchronization point. But I also do not want to schedule a thread’s blocks interleaved with blocks of other threads that occur after a join. For example, I don’t want to let the following program

{ A1 fork B; A2 }
{ B1; B2 join A; B3 }

generate this schedule:

A1 fork B; B1; B2 join A; A2; B3

I naturally want to keep all of A’s blocks before the B2 join A. It gets more complicated if there are several joins:

{ A1 fork B; A2 fork C; A3 }
{ B1; B2 join A; B3 }
{ C1; C2; C3 join A; C4 }

Here, I have to keep all of A’s blocks before the B2 join A and before the C3 join A, or conversely stated: B2 join A; B3 may not execute until after thread A is dead, but B1, C1 and C2 may.

It is not hard to detect invalid schedules after they have been generated, for example, the schedule

A1 fork B; A2 fork C; B1; C1; C2; C3 join A; C4; B2 join A; B3

is invalid. It respects thread B’s requirement to join with A, but it doesn’t respect that of thread C. If I only want to generate valid schedules, it seems like this is a whole lot more complicated than some kind of permutations of execution opportunities for threads. Maybe I should, at least for the first cut, generate invalid schedules like the one above and then in a second stage reject them?


About Mathias

Software development engineer. Principal developer of DrJava. Recent Ph.D. graduate from the Department of Computer Science at Rice University.
This entry was posted in Concurrent Unit Testing. Bookmark the permalink.

Leave a Reply