When I implemented last night’s sketch, I realized that the LASTBUFFER flag actually doesn’t quite work. The problem is that, when a thread has been woken up, I don’t have to check if the currently pointed to sync point is SP\_END – that is the thread that was just put to sleep. I have to look at the sync point beyond that, so a look-ahead of just 1 is not enough. Assume for a second that a look-ahead of 2 is enough. Then there are the following cases possible:
-
index-1: thread just woken up, currently running index : thread just put to sleep index+1: SP_END
-
index-1: thread just woken up, currently running index : thread just put to sleep -------- end of buffer -------- 0 : SP_END
-
index-1: thread just woken up, currently running -------- end of buffer -------- 0 : thread just put to sleep 1 : SP_END
Case 3 actually doesn’t quite happen this way. The thread entering compactWait notices that a thread has been waiting for this sync point already, so it wakes it up and scans for its own sync point. It doesn’t find its sync point, so it waits for the next buffer load.
Case 1 is the easiest to handle: I can just check if the end of schedule marker is at index+1. Cases 2 and 3, however, would have to involve the LASTBUFFER flag. Again, assuming a look-ahead of 2 is enough, LASTBUFFER would be true if the next buffer is either a) completely empty, b) contains just SP\_END, or c) contains one sync point and SP\_END.
This would be easy enough to handle. Unfortunately, I don’t think it works. Assume a schedule that ends like this:
... x : SP_MONITOREXIT 1 (1 waits) x+1: SP_MONITOREXIT 2 x+2: SP_MONITOREXIT 3 (3 waits) x+3: SP_MONITOREXIT 4 (4 waits) x+4: SP_END 0
Let us furthermore assume that threads 1, 3, and 4 have entered compactWait but weren’t supposed to run, so they are waiting for the sync points at x, x+2, and x+3. Let index = x right now.
Now thread 2 enters compactWait and notices that thread 1 has been waiting for this sync point at index. So it wakes thread 1 up and puts itself to sleep. Thread 1 increments index, so index = x+1 now. Then thread 1 exits compactWait and terminates – it was the last sync point for thread 1.
The result is that threads 2, 3, and 4 are all waiting to be woken up, but all threads are asleep, even though x+1 wasn’t the sync point immediately before SP\_END. This can, of course, be extended to any number of sync points.
I think I’m on the wrong path here.
For a while, I also thought that I could just disable scheduled replay as soon as I see a thread ID 9 (“DestroyJavaVMâ€). I haven’t tried yet, but I’m pretty sure that thread won’t be launched until all other threads have finished. If there’s still one thread asleep, waiting for a sync point, I won’t ever get a thread ID 9. This would be the easiest solution, but I’m rather sure it won’t work.
I think I’m beginning to understand that this whole issue isn’t about the end of the schedule, it’s about the end of a thread! With our compactWait algorithm, we always have only one thread running (unless a new buffer has been loaded). If that single thread ends, compactWait won’t be entered again, and the thread waiting for the next sync point will never be woken up. The program is deadlocked.
Something needs to be done when a thread ends. I don’t quite know what that is or how it can be done, though.
