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?
