Problem with some Java Homegrown Semaphore Code

[hardnett]

Hi Everyone,

This is an interesting problem that I am not able to find documentation for why this may be the case. I am teaching a course in Operating Systems (a typical junior-level course in CS departments). I asked by students to implement a semaphore class in Java using Peterson's algorithm for synchronization. I was toying around with a solution that I wrote, and noticed that if I take out one of the printf calls that I was using to demonstrate what is happening that sometimes a thread will hang in the P() method of the MySemaphore class. When the printf is in there is no problem, it works properly each time. My first thought was that the printf caused an i/o interrupt that provides an opportunity for the thread to yield and the other thread is able to execute. However, this does not ring true to me. So I am thinking that I missed something, and need another set of eyes on this. Take a look and let me know what you see.

I uploaded all of the source files here, but this is a copy of the MySemaphore class and someone may be able to spot my problem here. There is a comment before the printf in the while (value < 0) loop of the P(int) method that shows you which line can be commented out to reproduce the hanging, if that line is not commented out it seems to work fine.

Thanks for your help

public class MySemaphore {
 
	private int value;
	private int favoredThread;
	private boolean tWantsToEnter[] = new boolean[2];
	private String name;
 
 
	public MySemaphore(int v, String n) {
		value = v;
 
		// initial state
		favoredThread = 1;
		tWantsToEnter[0] = false;
		tWantsToEnter[1] = false;
		name = n;
	}
 
 
	public void V(int thread) {
		value++;
		System.out.printf("Thread %d is in %s.V() value = %d\n", thread, name, value);
		// signal to waiting threads
		tWantsToEnter[thread] = false;
	}
 
 
	public void P(int thread) {
		int otherThread = (thread == 0) ? 1 : 0;
 
		value--;
 
		System.out.printf("Thread %d is in %s.P() value = %d\n", thread, name, value);
		tWantsToEnter[thread] = true;
		favoredThread = otherThread;
 
		while (tWantsToEnter[otherThread] && favoredThread == otherThread)
			System.out.printf("Thread %d is busy-waiting\n",thread);
 
		while (value < 0) { // wait
 
[B][COLOR="Red"]			// when this line is in, all is well. When it's out. One of the threads hangs here forever!
[/COLOR][/B]			System.out.printf("Thread %d is busy-waiting value:%d < 0\n",thread, value);
 
 
			while (tWantsToEnter[otherThread] && favoredThread == otherThread)
				System.out.printf("Thread %d is busy-waiting\n",thread);
 
		}
 
 
 
	}
 
 
}

[helloworld922]

It looks like you forgot the line of code at the end of your "critical section" that resets the tWantsToEnter for your current thread. See Wikipedia: Peterson's Algorithm.

Why having that printf statement can cause it to fail/succeed is a mystery to me, but I think it's just some quirk with the timing and not because of any interrupts.

As a side note, it might be better to perform any extra calculations after the first while comparison check. I did some testing and it doesn't cause the threads to hang after you've made the above fix, but it can potentially lead to the threads running in the wrong order, especially if the amount of stuff before who's turn it is to execute critical stuff takes different amounts of time to execute.

[hardnett]

Thanks for the reply. However, that setting is done in the V() operation that performs the "signal". So if you look at the attachment, you will see that in the SynchronizedBufferPeterson.java file that there is a get() and put() method. These methods use the semaphore:

So the producer would be:
valueConsumed.P()
buffer = nextVal
valueProduced.V()

The speed of the threads should not affect the way this works. When the printf is in there the output is different each because the context switching between the threads changes. However, the sum is always equal to 10.

The "fix" you propose means that the buffer is no longer synchronized, which defeats the purpose and makes the code incorrect in another way.

[helloworld922]

Ah.. I didn't see the zip I'll give it another look possible some time tonight.

[helloworld922]

hmm... I ran your code (with the zipped java files this time) with that line commented out and left in. Neither case resulted in a thread left hanging indefinately, but only temporarily as it should be. I also looped the program ~1000 times, and everytime it succeeded in stopping both threads.

One other change I did make was to decrease the amount of time Producer and Consumer slept before trying to put/get another value (otherwise I'd be waiting for such a long time for the program to finish).

I'll run the same test again later when I get access to a computer with dual cores (this one only has a single core ).

[hardnett]

Thanks HelloWorld... Thats interesting. What version of Java JVM do you have running?

I am on a Snow Leopard duocore running:

java version "1.6.0_17"
Java(TM) SE Runtime Environment (build 1.6.0_17-b04-248-10M3025)
Java HotSpot(TM) 64-Bit Server VM (build 14.3-b01-101, mixed mode)

I am just wondering if different versions of java jvm give different results, because I let the code run for hours (while I taught classes LOL) and it was still hanging.

I appreciate the experiments you have run. I am think i will try it on some of our leopard machines and a linux box also.

This is very curious

[helloworld922]

I am running a Windows dual core system (ran it earlier with a single core windows system, too) with:
Java SE Runtime Environment (build 1.6.0_18-b07)
Java Hotspot Client VM (build 16.0-b13, mixed mode, sharing)

I know there are some discrepancies between running/compiling Java on Mac systems, but I kind of doubt that something like this could be caused by these discrepancies.