I just wrote a test program, basically something like the A-B-C program in the previous post, and recorded the schedule with debugging information. An interesting part is this:
// give ForkJoinTest$B (a Runnable) instance unique object ID -478 0 8 0 sample.schedule.ForkJoinTest$B.
0 6 0 sample.schedule.ForkJoinTest$B. 0 7 -478 sample.schedule.ForkJoinTest$B. // give Thread instance unique object ID -479 0 8 0 java.lang.Thread. 0 6 0 java.lang.Thread. 0 7 -479 java.lang.Thread. // give thread unique thread ID 9 0 11 0 java.lang.Thread. 0 9 0 java.lang.Thread. 0 10 9 java.lang.Thread. ... // increment thread and object IDs 0 3 13249998 java.lang.Thread.nextThreadNum 0 1 13249998 java.lang.Thread.nextThreadNum 0 2 13249998 java.lang.Thread.nextThreadNum 0 3 13249998 java.lang.Thread.nextThreadID 0 1 13249998 java.lang.Thread.nextThreadID 0 2 13249998 java.lang.Thread.nextThreadID // start thread with unique object ID -479 0 3 -479 java.lang.Thread.start 0 1 -479 java.lang.Thread.start 9 4 0 java.lang.Thread.start() // user thread with id 9 started; 2 remaining ... 0 2 -479 java.lang.Thread.start
0 10 9 synchronization point, I can tell that an instance a thread with thread ID 10 has been created. Later, the
0 3 -479 tells me that the thread with object ID -479 is being started. Right after that, there is the first synchronization point in then newly started thread,
9 4 0, a special synchronization point that I insert. I can treat anything before that point as prefix where thread 9 should not be scheduled.
I should make it easier to correlate thread ID 9 and object ID -479, although I think the object ID may not strictly be necessary; the
9 4 0 specifically marks
Thread.start. I also definitely need a special synchronization point for
Thread.join. Right now, the log does not indicate what thread is being joined (dying), only which one is doing the joining (waiting):
9 3 -1 java.lang.Thread.join 9 1 -1 java.lang.Thread.join 9 2 -1 java.lang.Thread.join
The part of the schedule above also illustrates the three-point nature of synchronized blocks right now. I added the
TRYMONITORENTER synchronization point (3) so the scheduler can halt before the
monitorenter opcode is executed, potentially blocking the thread, and to allow the deadlock monitor to detect cycles before they actually occur. However, as Corky has already pointed out once, splitting up
MONITORENTER in the schedule is problematic.
If I have two threads that both try to lock the same object, a naive schedule generator could easily generate the following schedule:
0 1 -100 ThreadA.run // thread 0 locks object 0 3 -100 ThreadA.run // thread 0 tries to lock object
TRYMONITORENTER just doesn’t make sense; acquiring the lock implies trying to acquire it. This suggests that as part of the schedule, I should omit
TRYMONITORENTER. (@About an hour after I had gone to sleep, I realized that the above is utter garbage, of course, since the synchronization points within a thread are not permuted; therefore, a
MONITORENTER never occurs before the
TRYMONITORENTER.@) Furthermore, even splitting up a synchronized block into
MONITOREXIT has its problems. Again, a naive scheduler might generate the following invalid schedule in which both threads 0 and 9 hold the lock at the same time.
0 1 -100 ThreadA.run // thread 0 locks object 9 1 -100 ThreadB.run // thread 9 locks object ... 0 2 -100 ThreadA.run // thread 0 unlocks object 9 2 -100 ThreadB.run // thread 9 unlocks object
For a monent I thought that releasing a lock wasn’t such an important operation after all and that I could just let the thread that released the lock continue, but that’s not true. The scheduler should afford the other thread the opportunity to execute, but not always; whether that happens or not is part of the schedule and therefore needs to be stored in the schedule. My schedule generator should ideally not generate schedules like the above, but in the worst case, the schedule above is behaviorally identical with a schedule that just makes thread 9 wait until thread 0 has released the lock:
0 1 -100 ThreadA.run // thread 0 locks object ... 0 2 -100 ThreadA.run // thread 0 unlocks object 9 1 -100 ThreadB.run // thread 9 locks object ... 9 2 -100 ThreadB.run // thread 9 unlocks object
The problem are the ellipses in this example… There might be a great number of synchronization points between the points where thread 0 acquires and releases the lock, and if I don’t eliminate schedules with invalid concurrent lock ownership, then the number of generated schedules is unnecessarily increased.
I also believed at first that my strategy to assign object IDs had a bug. My intention was to assign unique object IDs to direct subclasses of
Object, but it seemed like the same instance was assigned both object IDs -478 and -479, and I assumed that -479 was residing in a shadowed field in the
Thread class, and -478 in a field in the
ForkJoinTest$B class that extended
Thread. However, I made a mistake in interpreting the log:
ForkJoinTest$B does not extend
Thread but instead just implements a
Runnable, so we do have two separate objects.