Need join Synchronization Point

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

Using the 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 TRYMONITORENTER and 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

The sequence MONITORENTERTRYMONITORENTER 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 MONITORENTER and 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.

Share

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