Thread Implementation Question asked at an interview

[anuj guptaa]

Hi

Have a question on Thread. Have three thread T1 , T2 , T3 and 3 Arrays a1[1,4,7] , a2[2,5,8] ,a3[3,6,9]
now the thread T1 will have array a1
and T2 --> a2 and T3 --> a3

We will start all 3 threads in the main thread and they should run in such a way that the output is
1,2,3,4,5,6,7,8,9.


I tried implementing this by using CyclicBarrier but it didnt worked , i got the output as .

1
3
2
4
6
5
7
9
8
DONE

Thanks
Anuj

[Matthew Brown]

That looks like exactly what you need, except that it's cycling (a1, a3, a2) instead of (a1, a2, a3). Just swap the order.

[anuj guptaa]

No actually that is just one snapshot....i also got the following output , if you see here the first Barrier sequence is correct.
By using cyclic barrier i am able to control that T1 ,T2 and T3 prints the value for a1 ,a2 and a3 by Barrier 1 and then they print for barrier 2 and so on.
but within that i am not able to control the sequence ...Sometime T2 run before T1 and then T3.

1
2
3

4
6
5

8
7
9
DONE

[Chan Ag]

Have you tried the Condition variables? I think that should work.

Chan

Edit : I think with barriers you cannot provide the order in which the threads will reach the checkpoint. The barrier just ensures that all threads reach the checkpoint before proceeding further. Scheduling is dependent on the scheduler and since you don't have a wait/notify mechanism in place, you can't have an ordered processing ( note - it's not scheduling).

[anuj guptaa]

Chan

I agree with you Barrier cannot be used for managing the sequence of the threads ...so thats why i was wondering what would be the other solution for this problem.

What other datastructure i can use here ? i really cannot think of any solution where i can control the sequence of the thread...

Thanks
Anuj

[anuj guptaa]

Chan,

ok i missed that you mentioned to use condition variable...are you referring to the condition that we get from a LOCK interface...

If so i will try that ..i am still learning the Lock interface ..

Thanks
Anuj

[Chan Ag]

Yes, I meant the condition variable of the Lock interface. Did you try it and did it work when you tried?
As per Matthew's hint, we need to change the ordering here. But from your posts, it looked like you had created a simple CyclicBarrier without any inter-thread communication/order.
I think through condition variables or through some other inter-thread communication mechanism ( flags ), we can create the order.

I am not saying it WILL work. I'm just saying you could try it and see if it works.
I will try it too and respond with whatever I find.

Thanks,
Chan.

[Chan Ag]

Update - This is working fine with the help of ReentrantLock and Condition interfaces. I just tried it. I didn't require a barrier.

Chan.

[anuj guptaa]

Hi Chan,

Can you give me a hint on the implementation. How did you implement it.

I am still learning Lock interface. Till now i didnt see any big difference between ReEntrant lock and Monitor. (Not talking about the ReentrantReadWriteLock which is more flexible and scalable).

Thanks
Anuj

[Chan Ag]

I am still learning Lock interface. Till now i didnt see any big difference between ReEntrant lock and Monitor. (Not talking about the ReentrantReadWriteLock which is more flexible and scalable).

It's ReentrantLock. I'm not sure what you mean by Monitor as this term is used with some ambiguity many times ( actually I can't recall what this term means ). If by monitor you mean the implicit object lock ( the kind we get with synchronized methods ), there are quite a few very significant differences between explicit locking using the Lock interface and the implicit locking with synchronized methods ( and also with the kind of locking you get with synchronized blocks). You can read about them from the Oracle docs.

Though the decision to choose one of them is a design consideration, the differences are a criteria to prefer one design to other, even more so if you require a wait/notify kind of mechanism.
The Condition objects that you get with Lock interface provide a one to one correspondence between the condition( english ) a thread is waiting on and the notification. If you use synchronized methods, the thread gets a notification for a 'god knows what' condition. But with locks and conditions, the thread knows that it is becoming active for the right condition.

You could read Henry's response in the following thread where he explains about this difference.
http://www.coderanch.com/t/615692/threads/java/wait-notify-method-declared-Object

Also there are quite a few other notable differences, like for example- the way exceptions are handled and the release of the lock when there is an exception. With synchronized methods, when a method exits, the lock is released by default regardless of whether there was an exception. This may make the data inconsistent for any thread that is going to read this data later.

You can actually read about it. Then if you have specific questions, may be we can discuss about them and try to find the answers?

Can you give me a hint on the implementation. How did you implement it.

Since you haven't read about the Condition interface, I don't know if a hint will help before you read and practice with a few demo programs. Oh but you can do this. You could for now assume that you only have two arrays and two threads need to print the results in some order. Write a program to do this using the synchronized methods/blocks and wait/notify and then write another program to do the same thing using Lock/Condition and await/signal.
Once you have done that, you will have a rough idea of the differences.
Then work on the current problem using synchronized methods/blocks and wait/notify. You will realize what are the problems when you use synchronized methods/blocks and wait/notify when you require a one-one relation between a condition ( english ) and its notification.
You will realize that when you use Lock/Condition and await/signal, it becomes easy. Then you'll be able to appreciate the flexibility of this design and you will realize the problem it fixes.

Try writing the code yourself. If you come across an issue, let us know.

Thanks,
Chan.

[anuj guptaa]

Hi Chan,

I tried a program with Lock but i am only more confused now...Here is my implementation

package com.anuj.Locks;

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public class LocksTrial implements Runnable {

int flag;

int count = 0;
ReentrantLock lock = new ReentrantLock();
Condition condition = lock.newCondition();

public LocksTrial(int flag) {
this.flag = flag;
}

@Override
public void run() {

if (flag == 1) {
testLock1();
} else {
testLock2();
}

}

public void testLock1() {

System.out.println("TESTLOCK 1");

lock.lock();

try {
while (count == 0) {
System.out.println("Count now await:" + count);
condition.await();
System.out.println("Count now after await:" + count);

}
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} finally {
lock.unlock();
System.out.println("Lock1 released");

}
}

public void testLock2() {

System.out.println("TESTLOCK 2");

lock.lock();

try {
count++;
condition.signal();
System.out.println("Count now signal:" + count);

} finally {

lock.unlock();

System.out.println("Lock2 released");
}
}

}



Caller Main Method

public class TestLocks {

public static void main(String[] args) {
LocksTrial locksTrial1 = new LocksTrial(1);
LocksTrial locksTrial2 = new LocksTrial(2);


new Thread(locksTrial1).start();
new Thread(locksTrial2).start();
}

}

So now my question is that i defined a ReentrantLock Instance Variable lock ....and then using this lock i defined the instance variable Condition.

Now i am trying to synchronize two methods testLock1 and testLock2 using lock.lock() in both..... I have two threads one call the testlock1 and other testlock2......testlock goes into wait
and testlock2 increament count and then call signal...

Now i want to know the lock.lock in both the method refer to same LOCK ???

I am getting the output as and prog does not stop....

TESTLOCK 1
Count now await:0
TESTLOCK 2
Count now signal:1
Lock2 released


I am confused. whats wrong with the implementaion

Thanks
Anuj

[anuj guptaa]

Also why the condition.signal() not working..

[Chan Ag]

Would you want to edit your post and use code tags to make it more readable.

I actually tried going through your program but I got lost quite soon cause your code is far from readable. Also please mention what you are trying to do in the code.

Chan.

[anuj guptaa]

Chan

Sorry didnt knew abt the java code tags as first time pasting the code here

What i did is -->I defined a ReentrantLock Instance Variable called lock ....and then using this lock i defined the instance variable Condition.

Now i am trying to synchronize two methods testLock1 and testLock2 using lock.lock() in both..... I have two threads one call the testlock1() and other testlock2()......testlock1() goes into wait
and testlock2() increament count and then call signal...

Now i want to know that if lock.lock in both the methods refer to the same LOCK ???

Also why the condition.signal() not working..

I am getting the output as and prog does not stop....

TESTLOCK 1
Count now await:0
TESTLOCK 2
Count now signal:1
Lock2 released


I am confused. whats wrong with the implementaion
-------------------------------------------------------------------------------------

public class LocksTrial implements Runnable { 

int flag; 

int count = 0; 
ReentrantLock lock = new ReentrantLock(); 
Condition condition = lock.newCondition(); 

public LocksTrial(int flag) { 
this.flag = flag; 
} 

@Override 
public void run() { 

if (flag == 1) { 
testLock1(); 
} else { 
testLock2(); 
} 

} 

public void testLock1() { 

System.out.println("TESTLOCK 1"); 

lock.lock(); 

try { 
while (count == 0) { 
System.out.println("Count now await:" + count); 
condition.await(); 
System.out.println("Count now after await:" + count); 

} 
} catch (InterruptedException e) { 
// TODO Auto-generated catch block 
e.printStackTrace(); 
} finally { 
lock.unlock(); 
System.out.println("Lock1 released"); 

} 
} 

public void testLock2() { 

System.out.println("TESTLOCK 2"); 

lock.lock(); 

try { 
count++; 
condition.signal(); 
System.out.println("Count now signal:" + count); 

} finally { 

lock.unlock(); 

System.out.println("Lock2 released"); 
} 
} 

} 

Main Class (Main Method)

public class TestLocks { 

public static void main(String[] args) { 
LocksTrial locksTrial1 = new LocksTrial(1); 
LocksTrial locksTrial2 = new LocksTrial(2); 


new Thread(locksTrial1).start(); 
new Thread(locksTrial2).start(); 
} 

} 

[Chan Ag]

First both your programs do not have proper indentation. Perhaps you'd like to fix that.

I doubt if your program should even complete execution. I believe it keeps waiting for a condition that is never signalled. At least the thread that executes testLock1 method would keep running.

You have two different objects, that have two different locks. So the two threads don't block each other.
If you require that one thread waits on a Condition, and the other thread signals the same Condition, it should be the same Condition object.
But you have two different locks, and two different Conditions. So there is no synchronization here, not even at the lock level.

This would definitely not work as intended.

Perhaps you could try passing the Lock and Condition as arguments to the constructor. And you'd want to make sure you are passing the same Lock and Condition values to both the objects and see if it works.
I have not reviewed the rest of your code.

Chan.

[anuj guptaa]

Hi Chan,

Thanks for pointing...it was a problem with the Calling method ..i had created two Runnable object and passed to the threads..what a mistake.... i corrected it to one Runnable object and 2 threads..

But i still have this question...

I have one lock variable defined as instance variable ReentrantLock lockVariable = new ReentrantLock();

now in Fucntion A() i do lockVariable.lock();

in other function B() in same class i do lockVariable.lock();
Thread1 call A() and Thread2 call B() on same object...

so the lock that i am getting here are 2 different locks or are they same ??

Thanks
Anuj

[anuj guptaa]

Hey Chan,

I got the answer to previous question....I just had to add a sleep in method A() after the lock... so the thread2 tried to enter B() but couldnt as it didnt had the lock...


Now i am getting confident ...now i will try the original problem for which i started this thread.

Thanks for your support Chan ....

Anuj

[anuj guptaa]

Hi Chan,

Now i understand Lock and condition a bit ...can you give me hint now ..as i tried but couldnt get the output...

So did you do it with 3 Locks and 3 different condition ....or 1 lock and 3 different conditions ??

Thanks
Anuj

[Chan Ag]

Now i understand Lock and condition a bit ...can you give me hint now ..as i tried but couldnt get the output...

So did you do it with 3 Locks and 3 different condition ....or 1 lock and 3 different conditions ??

What have you tried? In all your posts, you have forgotten to attach a working solution ( properly indented within code tags ) of whatever you have tried to accomplish.
In your first post, you mentioned using a CyclicBarrier, but you did not copy the source code.
In your other posts, you shared source code that was not indented properly and that was not even completing execution.
You have still not edited that post.

If you add details and share readable source code, you might get more participation and feedbacks. It is sometimes hard to imagine based on the description of the source code.
You could still be doing a mistake that people would otherwise want to correct ( this would result in better learning ).

Anyways ..
It's not exactly a hint, as what I have done may not be the only/correct way to solve this problem, but I have used one Lock and three Conditions.
Following is the constructor of my class.

DataClass1(int[] intArray, ReentrantLock lock, Condition awaitCondition,
            Condition signalCondition) {
        this.intArray = intArray.clone();
        this.lock = lock;
        this.awaitCondition = awaitCondition;
        this.signalCondition = signalCondition;
    }

If you deem that as a hint, it is one of the ways to solve the problem.
Also remember that after the threads have invoked await on the awaitCondition, somebody needs to signalAll the condition that will make the first thread wake up.
It is important that the three threads are in the wait queues when the first condition is signalled, otherwise a required notification may not reach its intended recipient.
The above can possibly be achieved in more than one way. I have tried two ways and preferred one way to the other way.
And I am not convinced yet that what I have tried is the ideal way to signalAll the first condition to be signalled. I can try the other ways not before Friday.
I'd wait to see what you come up with.

Chan.

[anuj guptaa]

Hi Chan,

Here is the CyclicBarrier code that i wrote ...i have a interview on Saturday and have to prepare on lot of topics like Spring , Hibernate so lost the track... but i will work on the Lock solution ...

Thanks for your suggestions...

public class MainRunnableJoin {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		CyclicBarrier cb = new CyclicBarrier(3, new Runnable() {

			@Override
			public void run() {
				System.out.println("DONE");

			}

		});

		MyRunnableJoin myRunnableJoin1 = new MyRunnableJoin(cb);

		MyRunnableJoin myRunnableJoin2 = new MyRunnableJoin(cb);

		MyRunnableJoin myRunnableJoin3 = new MyRunnableJoin(cb);

		int a[] = { 1, 4, 7 };
		int b[] = { 2, 5, 8 };

		int c[] = { 3, 6, 9 };

		myRunnableJoin1.setCount(a);

		myRunnableJoin2.setCount(b);

		myRunnableJoin3.setCount(c);

		Thread t1 = new Thread(myRunnableJoin1, "Thread1");

		Thread t2 = new Thread(myRunnableJoin2, "Thread2");

		Thread t3 = new Thread(myRunnableJoin3, "Thread3");

		

		// T1 --> T2 --> T3 --> Main Thread

		try {
			t1.start();
			
			t2.start();
			
			t3.start();
			
		} catch (Exception e) {
			
			e.printStackTrace();
		}

		

	}

}

public class MyRunnableJoin implements Runnable {

	CyclicBarrier cb;

	public MyRunnableJoin(CyclicBarrier cb) {
		this.cb = cb;
	}

	public CyclicBarrier getCb() {
		return cb;
	}

	public void setCb(CyclicBarrier cb) {
		this.cb = cb;
	}

	private int count[];

	public int[] getCount() {
		return count;
	}

	public void setCount(int[] count) {
		this.count = count;
	}

	@Override
	public void run() {

		System.out.println(count[0]);
		try {
			cb.await();
		} catch (Exception e) {

			e.printStackTrace();
		}

		System.out.println(count[1]);
		try {
			cb.await();
		} catch (Exception e) {

			e.printStackTrace();
		}

		System.out.println(count[2]);
		try {
			cb.await();
		} catch (Exception e) {

			e.printStackTrace();
		}

		// System.out.println("Runnable:" + Thread.currentThread().getName());

	}

}

Thanks
Anuj

[Salil Vverma]

Hey Anuj,

The problem can easily be solved using traditional wait and notify mechanism. Please have a look on following link for implementation code -

Link - http://jyotisalil.blogspot.in/2013/09/inter-thread-communication-using-wait_19.html

Just curious, in which company's interview, this question was asked ? All the best for your interview.

[anuj guptaa]

Hi Salil

Thanks for the response. I ran this program but the output is not consistent. I mean sometime it just hangs. But then i added a Sleep after T3.start() and it worked much better. I am on java version 1.6

I was asked a very similar question in Congnizant interview. It was not exactly the same.

Thanks
Anuj

[Salil Vverma]

Hey Anuj,

I tried the solution is quad code processor and found it working fine. But definitely the code is prone to dead lock if first signal from main to first thread gets missed. The chances of single getting missed will increase in a single core processor machine.
The problem can be solved using Semaphore. The complete code can be accessed from the below link -

http://jyotisalil.blogspot.in/2013/09/inter-thread-communication-using-wait_19.html#SemaphoreCode

[anuj guptaa]

Hi Salil

Very cool , this solution with Semphore work with charm. You really are good with Threads ...i am still trying to wrap my head around all these complex Thread logic.

Is it possible to implement this logic using Locks & Condition ?

Thanks
Anuj

[Chan Ag]

Is it possible to implement this logic using Locks & Condition ?

I remember you mentioned you were gonna try it yourself. So did you try it? Or you've given up on trying now.
I think you were getting close to the solution, and you were making good progress. But that's just my opinion.

Salil Vverma,

Please do not post complete solutions. The mods here might even delete such posts.

Thanks,
Chan.

[Salil Vverma]

Anuj : We can implement the solution with lock and condition but I think, we shall have to add unnecessary complexity to make sure that no signal gets missed in that solution. Alternatively, we can implement the solution of this problem using Exchanger. The solution can be accessed via below link -

http://jyotisalil.blogspot.in/2013/09/inter-thread-communication-using-wait_19.html#ExchangerCode

Chang: I think providing working code gives better perspective of approach, like we could understand Anuj's way of implementation well when he provided the code. I would request you to share your way of implementation as well. That would help us understanding your approach well.

[Chan Ag]

First, the first name is Chan.

I think providing working code gives better perspective of approach, like we could understand Anuj's way of implementation well when he provided the code. I would request you to share your way of implementation as well. That would help us understanding your approach well.

You have a view and I respect it. So I will not comment on it. My views differ.

Here's my opinion.
Providing ready made code is never a good thing. Sometimes the original poster could have come up with better solution than that of the helper. By not providing a full, working solution, we give people a chance to wow themselves and to wow those who tried to help. My disclaimer - I have not seen any of your solutions yet.
Providing ready made code is never a good thing also because there are often more than 1 way of achieving a desired result. Let people try them all, let people fail multiple times, let them come up with alternatives, let them ask specific questions .. this is how we learn ( again just an opinion ).
I've also done the mistake of posting a solution in the past; the lesson I learned in the process is, it may not be such a good thing to post an entire solution and curb the curiosity and learning capability of the original poster. - Again, just my opinion.

I would request you to share your way of implementation as well. That would help us understanding your approach well.

If you'd scroll up, you'd see I have already explained how I have implemented my solution. I have also explained that it is important the three threads are in the wait queue before the first notification is sent.

Also I understand there could be things about my implementation that could require a reconsideration ( I'd say that in general about anyone's code, yours too ), but I'm not working on it right now, nor do I want to work on it right now. I may post it later.

Chan.

Edit : Actually, I take my words back. It's actually working for both of you. The OP wants the code and you have it for him. Why should anybody suggest to go about it in some other way when both of you are quite okay with it. So it's working for both of you. Cheers.
Ignore what I said ..

[Chan Ag]

Since this has been going on for many days, here is what I had tried then.
Disclaimer - I have not re-reviewed this code. So treat this as rough code. You could always come up with something better than this.

import java.util.concurrent.locks.*;

public class DataClass1 implements Runnable {

    private int[] intArray;
    private final ReentrantLock lock;
    private Condition awaitCondition;
    private Condition signalCondition;

    DataClass1(int[] intArray, ReentrantLock lock, Condition awaitCondition,
            Condition signalCondition) {
        this.intArray = intArray.clone();
        this.lock = lock;
        this.awaitCondition = awaitCondition;
        this.signalCondition = signalCondition;
    }
    
    private final void printContent() {
       lock.lock();     
        try 
        {   
            for (int i = 0; i < intArray.length; i++) 
            {
                try 
                {
                    awaitCondition.await();
                } 
                catch (InterruptedException ex) {
                    ex.printStackTrace();
                }

                System.out.println(intArray[i]);
                signalCondition.signalAll();
            }
        } 
        finally 
        {
            lock.unlock();
        }
    }

    @Override
    public void run() 
    {
        printContent();
    }

    public static void main(String[] args) throws InterruptedException {
       final int[] array1 = {1, 4, 7};
       final int[] array2 = {2, 5, 8};
       final int[] array3 = {3, 6, 9};
       final ReentrantLock lock = new ReentrantLock();
       final Condition firstPrinted = lock.newCondition();
       final Condition secondPrinted = lock.newCondition();
       final Condition thirdPrinted = lock.newCondition();
       final DataClass1 object1 = new DataClass1(array1, lock,
                secondPrinted, firstPrinted);
       final DataClass1 object2 = new DataClass1(array2, lock,
                thirdPrinted, secondPrinted);
       final DataClass1 object3 = new DataClass1(array3, lock,
                firstPrinted, thirdPrinted);
        new Thread(object1).start();
        new Thread(object2).start();
        new Thread(object3).start();    
        lock.lock();
        while (( lock.getWaitQueueLength(firstPrinted) < 1 ) ||
            ( lock.getWaitQueueLength(secondPrinted) < 1 ) ||
            ( lock.getWaitQueueLength(thirdPrinted) < 1 )) 
        {
            lock.unlock();
            Thread.sleep(6000);
            lock.lock();
        }   
        try 
        {
            secondPrinted.signalAll();
        } 
        finally 
        {
            lock.unlock();
        }
    }
}

Here is the output.
1
3
2
4
6
5
7
9
8

It's open to suggestions and feedback...

I don't like the way of signalling the first signalAll. Let me know if you can think of something better.

Chan.

[Aaron Shawlington]

Here's how I did it quickly without using Lock interface, just using synchronize (for an interview I'd probably just use a semaphore with 1 permit instead of my Flag object. Ignore the funny names by the way, I didn't want to take time to think of good names):

public class Main {

    Flag flag = new Flag();

    public static void main(String[] args) throws InterruptedException {

        Main main = new Main();

        Runner runner1 = new Runner(new int[]{1,4,7}, 1, main.flag);
        Runner runner2 = new Runner(new int[]{2,5,8}, 2, main.flag);
        Runner runner3 = new Runner(new int[]{3,6,9}, 3, main.flag);

        ExecutorService service =Executors.newFixedThreadPool(3);
        service.submit(runner3);
        service.submit(runner2);
        service.submit(runner1);

        service.shutdown();
        service.awaitTermination(1, TimeUnit.DAYS);

        System.out.println("Done.");

    }

}

and ...

public class Runner implements Runnable {

    private final Flag flag;
    private final int[] numbers;
    private final int i;

    public Runner(int[] numbers, int i, Flag flag) {
        this.numbers = numbers;
        this.i = i;
        this.flag = flag;
    }

    @Override
    public void run() {

        for (int num : numbers) {
            flag.getFlag(i);
            System.out.println(">" + num);
            flag.flipFlag();
        }
    }

}


class Flag {

    private int flag = 1;

    public synchronized int getFlag(int i) {
        if(flag != i) {
            try {
                this.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
            }
        }
        return flag;
    }

    public synchronized void flipFlag() {
        flag++;
        if(flag == 4) {
            flag = 1;
        }
        this.notifyAll();
    }

}

And the output is:

/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/bin/java -Didea.launcher.port=7532 "-Didea.launcher.bin.path=/Applications/IntelliJ IDEA 12.app/bin" -Dfile.encoding=UTF-8 -classpath "/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/deploy.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/dt.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/javaws.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/jce.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/jconsole.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/management-agent.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/plugin.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/sa-jdi.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Classes/charsets.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Classes/classes.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Classes/jsse.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Classes/ui.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/ext/apple_provider.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/ext/dnsns.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/ext/localedata.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/ext/sunjce_provider.jar:/System/Library/Java/JavaVirtualMachines/1.6.0.jdk/Contents/Home/lib/ext/sunpkcs11.jar:/Users/aaronshaw/Downloads/Threads/out/production/Threads:/Applications/IntelliJ IDEA 12.app/lib/idea_rt.jar" com.intellij.rt.execution.application.AppMain Main
>1
>2
>3
>4
>5
>6
>7
>8
>9
Done.

Process finished with exit code 0

[Henry Wong]

Chan Ag wrote:
It's open to suggestions and feedback...

I don't like the way of signalling the first signalAll. Let me know if you can think of something better.

First, there is no reason to do a signal all. There is only one thread on each condition, and hence, you only need to do a signal.

Second, I don't like waits on condition variables to be "blind". I mentioned it before many times in these forums, so will do so again... ... Your code should have some sort of state. And check it to confirm that it should call the await() method call. It should also check it after the await() method call to make sure that it is correct before continuing.

Henry

[Henry Wong]

Aaron Shawlington wrote:Here's how I did it quickly without using Lock interface, just using synchronize (for an interview I'd probably just use a semaphore with 1 permit instead of my Flag object. Ignore the funny names by the way, I didn't want to take time to think of good names):

Your flag class is doing more than just a semaphore. It is keeping the state on which barrier to trigger -- basically, think of it as some sort of flagged barrier where only a specific thread is released.

Personally, I like this solution. While the java concurrent library does provide an arsenal of tools, there are times where the tools don't always fit right -- and it is a good idea to develop a special purpose tool. Which is what this is.

On the other hand, when you develop your own tools, you can run into bugs -- which I guess is a counter argument for ... unless the tools don't fit to the point of being difficult to use, it may be better to just use the highly tested tools instead.

Anyway ...

Aaron Shawlington wrote:

class Flag {

    private int flag = 1;

    public synchronized int getFlag(int i) {
        if(flag != i) {
            try {
                this.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
            }
        }
        return flag;
    }

    public synchronized void flipFlag() {
        flag++;
        if(flag == 4) {
            flag = 1;
        }
        this.notifyAll();
    }

}

The getFlag() method call isn't quite right. It is possible for the wait() method to return, and the flag isn't in the right state. So, that "if" statement should probably be changed to a "while" statement. Also, I don't like the need to use notifyAll() which probably won't scale with more threads -- but that is one of the unfortunately drawbacks of having only a single condition variable.

Henry

[Aaron Shawlington]

Henry Wong wrote:
The getFlag() method call isn't quite right. It is possible for the wait() method to return, and the flag isn't in the right state...

Oh yes. That's left over from when I initially had the getFlag() inside a while loop checking the flag returned (which is ignored now), before I decided i could move the logic inside the flag object itself.

I'm very surprised that I actually got the correct output from that code, as unless I'm missing something, at any time there could be 2 threads waiting on on the flag, and then when the third thread 'flips' it, it notifies all, so both of the previously mentioned 2 threads then return from getFlag() and output their next number. I think I must have gotten lucky in the order in which that happened.

[Aaron Shawlington]

Just for fun - here's a quick implementation that doesn't notifyAll(), so should scale well (although maintaining the linked list of lock objects would require more maintenance if threads were dynamically added to the pool):

public class Main {


    public static void main(String[] args) throws InterruptedException {

        Pass Pass1 = new Pass();
        Pass Pass2 = new Pass();
        Pass Pass3 = new Pass();

        Pass1.setNext(Pass2);
        Pass2.setNext(Pass3);
        Pass3.setNext(Pass1);

        Runner runner1 = new Runner(new int[]{1,4,7}, 1, Pass1);
        Runner runner2 = new Runner(new int[]{2,5,8}, 2, Pass2);
        Runner runner3 = new Runner(new int[]{3,6,9}, 3, Pass3);

        ExecutorService service =Executors.newFixedThreadPool(3);
        service.submit(runner2);
        service.submit(runner3);
        service.submit(runner1);

        synchronized (Pass1) {
            Pass1.setActive(true);
            Pass1.notify();
        }

        service.shutdown();
        service.awaitTermination(1, TimeUnit.DAYS);

        System.out.println("Done.");

    }

}

and:

public class Runner implements Runnable {

    private final Pass pass;
    private final int[] numbers;
    private final int i;

    public Runner(int[] numbers, int i, Pass pass) {
        this.numbers = numbers;
        this.i = i;
        this.pass = pass;
    }

    @Override
    public void run() {

        for (int n = 0; n < numbers.length; n++) {
            try {
                pass.get();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            System.out.println("Thread: "+i+" > " + numbers[n]);
            try {
                pass.rotate(n == numbers.length-1 ? false : true);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

}


class Pass {

    private Pass next;
    private boolean active;

    boolean isActive() {
        return active;
    }

    void setActive(boolean active) {
        this.active = active;
    }

    public void setNext(Pass existingPass) {
        this.next = existingPass;
    }


    public synchronized void get() throws InterruptedException {
        while (! this.isActive()) {
            this.wait();
        }
    }

    public synchronized void rotate(boolean keepAlive) throws InterruptedException {
        synchronized (this.next) {
            this.active = false;
            this.next.setActive(true);
            this.next.notify();
        }
        if(keepAlive == true) {
            this.wait();
        }
    }


}

[Chan Ag]

Thanks so much, Henry.

Oh yes, I should have used just signal instead of signalAll.

Second, I don't like waits on condition variables to be "blind". I mentioned it before many times in these forums, so will do so again... ... Your code should have some sort of state. And check it to confirm that it should call the await() method call. It should also check it after the await() method call to make sure that it is correct before continuing.

And this advice.. I will keep it in mind always. Not surprisingly ( and like it always doesn't occur to me ), it didn't even occur to me before you mentioned it. But now that I think of it, I realize it's such an important thing. This could be a system with many threads and the processing could be sort of complex, and in such cases blind waits could be disastrous.

By the way, I've made a note of it in my book, Java Threads, Edition 3.

Thank you,
Chan.

[Salil Vverma]

Hey,

We can implement the solution without using any synchronization construct, by creating threads using callable interface and manipulating them.

In case, you want to refer the code, it is accessible at the following link -
http://jyotisalil.blogspot.in/2013/09/inter-thread-communication-using-wait_19.html#CallableCode

Regards
Salil Verma

[Aaron Shawlington]

Salil Vverma wrote:Hey,

We can implement the solution without using any synchronization construct, by creating threads using callable interface and manipulating them.

In case, you want to refer the code, it is accessible at the following link -
http://jyotisalil.blogspot.in/2013/09/inter-thread-communication-using-wait_19.html#CallableCode

Regards
Salil Verma

The Op's explanation of the scenario isn't super explicit, but I don't think it was meant to be as you've indicated. What you've linked to, while the result is exactly the
same, the actual problem to be solved is a completely different scenario - i.e. the original scenario implied that the problem was inter-thread communication and synchronisation,
while the one you linked to seems kindof pointless because the method which kicks off the threads and merges the results has to have explicit knowledge of what each thread is
doing and what each will return. The code might as well print out the result of each callable, and not bother weaving them in the for loop. What's the point in doing that?

[Salil Vverma]

Hey Aron,

If we just need to perform similar task in sequence (not in parallel), I do no see any point of doing things using three threads.
But as it is an interview question, I think, interviewer might check any thing, ranging from inter-thread communication, signalling to passing execution result.

That is why I think, while answering,the option of this answer should also be kept open.

[Aaron Shawlington]

Salil Vverma wrote:Hey Aron,

If we just need to perform similar task in sequence (not in parallel), I do no see any point of doing things using three threads.
But as it is an interview question, I think, interviewer might check any thing, ranging from inter-thread communication, signalling to passing execution result.

That is why I think, while answering,the option of this answer should also be kept open.

I think it's worth bearing in mind, and thanks for that. But if the task was to split processing in parallel threads (to take advantage of multiple cores for example), and
then join the results afterwards, the question wouldn't deliberately arrange the data in a way which needed to be reordered afterwards. I'm pretty sure in a threading
interview question the interviewer is NOT trying to see if you're capable of using a for loop to sysout ints from 3 different arrays. That whole part would be pointless,
and I think if you solved the question in that way that the interviewer would consider it a fail.

In this case the scenario has clearly taken sequential data, and split it across different threads in such a way that no thread can individually process its data in the same
sequential order as it existed before being split. The implication being that the threads must communicate in order to output the data in sequential order. Simply returning
the exact same data that was input, and then manually ordering it afterwards is entirely pointless.

[Salil Vverma]

Hey,

I think it's worth bearing in mind, and thanks for that. But if the task was to split processing in parallel threads (to take advantage of multiple cores for example), and
then join the results afterwards, the question wouldn't deliberately arrange the data in a way which needed to be reordered afterwards

if the task was to split processing in parallel threads (to take advantage of multiple cores for example),, then definitely the solution would be different. But here the problem is not to execute sub tasks in parallel but in sequencial way so we should definitely prefer the KISS (Keep it simple silly) principal.

I'm pretty sure in a threading interview question the interviewer is NOT trying to see if you're capable of using a for loop to sysout ints from 3 different arrays. That whole part would be pointless,and I think if you solved the question in that way that the interviewer would consider it a fail.

I am pretty sure that callable solution needs more fundamentals that just for loop and sysout. These days executor framework, future task and callabes are pretty hot. we get multiple scenario based questions on it. This can be considered as one of those examples. If the interviewer would be looking for threads getting interacting with each other. He will not reject you but ask you to design in such a way as the task is performed by the idividual threads not a single main thread.

In this case the scenario has clearly taken sequential data, and split it across different threads in such a way that no thread can individually process its data in the same sequential order as it existed before being split. The implication being that the threads must communicate in order to output the data in sequential order. Simply returning the exact same data that was input, and then manually ordering it afterwards is entirely pointless.

I do not see the problem as sequencial data being split by main thread in such a way as therad needs to interact with each other. I see the problem as it is written in question. Where three threads aleady have data and we want data to be processed in specific sequence. The objective is data processing in specific sequence not implementing any specific appraoch.

[Aaron Shawlington]

Salil Vverma wrote:

I do not see the problem as sequencial data being split by main thread in such a way as therad needs to interact with each other. I see the problem as it is written in question. Where three threads aleady have data and we want data to be processed in specific sequence. The objective is data processing in specific sequence not implementing any specific appraoch.

Exactly my point - the solution you linked do doesn't do this. In the solution you linked to there is no guarantee at all with regards to sequence. All the solution that you linked to does, is to say "here you go threads - I've divided up the work into 3 parts (one each), and when you're all done let me know and i'll reassemble the data in the correct order".