• Post Reply Bookmark Topic Watch Topic
  • New Topic

Threads taking turns

 
Varun Gokulnath
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I was recently asked a Java multi-threading question in an interview. The questions is : Write a program that creates 3 Threads. The first Thread prints 1, the second Thread prints 2 and the third 3. The Threads should run in such a way that they print the sequence 1 2 3 1 2 3 .... forever



I wrote code similar to what I have above and it works. However, I got the impression that the interviewer wasn't very happy with this solution. Any suggestions on how I can improve this program is greatly appreciated.

Thanks
Varun
 
Paul Clapham
Sheriff
Posts: 21876
36
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To me, since in real life you would never want to write a threaded application which did that, I think that any solution which works is a good enough solution. In other words, if it isn't worth doing, it isn't worth doing well.

However I'm sure there are other ways to satisfy that requirement. Don't let me deter others from posting them -- you might learn something from other solutions even though the requirement is worthless.
 
Henry Wong
author
Sheriff
Posts: 22526
109
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think it is fair to say that the purpose of the interview question is to test your knowledge of synchronization (mutexes), and the use of wait/notify (condition variables). And you did not show knowledge of either in your solution.

Paul Clapham wrote:To me, since in real life you would never want to write a threaded application which did that, I think that any solution which works is a good enough solution. In other words, if it isn't worth doing, it isn't worth doing well.


I disagree. This "works" because all JVMs behaves a certain way with method calls, but there is nothing in the spec that says that it can't inline the method calls, then reuse the variables between calls (because it can optimize the usage), and then keep them cached in registers (due to no synchronization). Also, without the use of wait/notify, it is constantly spinning for its turn.

In other words, this is not a solution that "works". At best, this solution burns three processor cores (to do the task). And worse, it may not work at all, in a future version of the JVM.

Henry
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

Well I understand he might not have been happy. Your Threads just print random numbers in each loop while he asked for each Thread to print a specific number.

Also, the line:


isn't Thread safe so it should eventually fail at giving the correct output:

The interviewer might have been looking for something like this:



Overall, it is a petty good Thread exercise.

I hope this helps.

Cheers,
 
Stephan van Hulst
Bartender
Posts: 6583
84
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm afraid that code is incorrect. Threads may wake up spuriously, so it's never guaranteed that wait() will return at the exact moment you want it to. Thread.yield() also shouldn't be used, because it makes no guarantees; you should always assume it does nothing.

This is how I would do it without using the concurrency API:
 
Henry Wong
author
Sheriff
Posts: 22526
109
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:I'm afraid that code is incorrect. Threads may wake up spuriously, so it's never guaranteed that wait() will return at the exact moment you want it to. Thread.yield() also shouldn't be used, because it makes no guarantees; you should always assume it does nothing.


I think both issues are related to the same thing. The threading code has no state -- it is doing signalling (and waiting) blindly. There is no way to detect if the state is correct after the wait() method call. Also, the yield() calls are likely there to make sure the threads run to the first wait() method call, because again, there is no way to detect if the thread should wait.

Agreed, the yield() method should not be expected to do anything. I have also seen cases of the sleep() method being used instead. This works better since it will take a very overload scheduler to fail (especially for longer sleep periods)... but of course, if the code had state, neither yield() nor sleep() would be needed.


On the bright side, I like the solution in that it uses notify() instead of notifyAll(). Very often, I see notifyAll() being used because the waiting conditions are different.

Having said that, I think it would have been better to use one mutex lock (to protect the state) and three condition variables -- versus the three lock and three condition variables in the implementation. Of course, this means that the ReentrantLock and Condition classes will need to be used instead of the synchronization keyword and wait/notify, as sync/wait/notify can't do a three condition variable on one lock.

Henry
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can assure that the code I posted is spotless if ran into its own jvm. I just used Thread.yield with tons of comments to simplify the exercise. In a jvm where several other threads are running, I would have used yet another semaphore. Please remember the interview context of the OP ;-)

Stephan, what is the code you posted supposed to do anyway?
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
oh, you have to synchronize before the while (true) loop in the code I posted otherwise it doesn't work. This is contrary to the code Stephan posted which sometimes constitute a common mistake depending on the use case.

Oh, and when you know your apis and use them correctly, wait() guarantees everything.

P.S. I wrote the code myself.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
by locking the whole while (true) loop into a synchronized block, failure is impossible.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Additionally, when you control everything, there is no such things as spurious Threads ;-)
 
Stephan van Hulst
Bartender
Posts: 6583
84
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A.J. Côté wrote:I can assure that the code I posted is spotless if ran into its own jvm. I just used Thread.yield with tons of comments to simplify the exercise. In a jvm where several other threads are running, I would have used yet another semaphore. Please remember the interview context of the OP ;-)

What does this even mean? What does the JVM have to do with the correctness of the code?

oh, you have to synchronize before the while (true) loop in the code I posted otherwise it doesn't work. This is contrary to the code Stephan posted which sometimes constitute a common mistake depending on the use case.

Pray tell, what would that common mistake be?


Oh, and when you know your apis and use them correctly, wait() guarantees everything.

Java™ Platform, Standard Edition 8 API Specification wrote:As in the one argument version, interrupts and spurious wakeups are possible

Any of the three threads in your program could print its value out of order if it woke up prematurely. In an extreme case, if all three threads woke up at the same time, your program would deadlock.
 
Henry Wong
author
Sheriff
Posts: 22526
109
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
Oh, and when you know your apis and use them correctly, wait() guarantees everything.

Java™ Platform, Standard Edition 8 API Specification wrote:As in the one argument version, interrupts and spurious wakeups are possible

Any of the three threads in your program could print its value out of order if it woke up prematurely. In an extreme case, if all three threads woke up at the same time, your program would deadlock.


As an added note... the Java Specification actually doesn't specify when spurious wakeups will occur. The reason for this is because most JVMs wait/notify mechanism is implemented on top of the operating systems condition variables. And many OSes condition variables have spurious wakeup requirements ... and the reason for that will vary from OS to OS.

As an example, for many versions of Unix -- the spurious wakeup is caused by a complex interaction between the condition variable and the OS signal handling system. Ideally, it is possible to make those mechanisms interact correctly (my speculation). However, it is very complex, and most OSes simply choose to document that condition variables can have spurious wakeups.

Henry
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the spurious wakeup advice. I guess one is better safe than sorry.

I have updated the code.
1) The code autotest itself by reading its own output and exits if wrong output occurs. It writes read count to standard output
2) The code detects and handles spurious wakeups and logs them to standard error.
3) The code makes really sure all Thread are in waiting state before notifying the first thread to start printing.

Code reviews/comments are welcome! As well, feel free to use on your own machines to see if you manage to detect any spurious wakeups ;-)))

So far, still no spurious wakeups detected. I will leave running and update if it detects any. The code is currently running on 3 machines:

Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz (4 cpu in /proc/cpuinfo)
AMD Athlon(tm) 64 X2 Dual Core Processor 4200+ (2 cpu in /proc/cpuinfo)
Intel(R) Pentium(R) 4 CPU 3.20GHz (2 cpu in /proc/cpuinfo)

Generates output: (e.g. 1\n 2\n 3\n 1\n 2\n 3\n



Reads the output:






 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hehe, I just detected a spurious wakeup on:

Intel(R) Pentium(R) 4 CPU 3.20GHz (2 cpu in /proc/cpuinfo)

I will post more when it has ran for a few days on the 3 machines...


 
Stephan van Hulst
Bartender
Posts: 6583
84
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A.J. Côté wrote:Hehe, I just detected a spurious wakeup [...]


Hah, neat. I didn't actually expect they would happen.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

Here is a brief update. So far, only our production grade hardware seems immunized to spurious wakeups after ~3,000,000,000 waits. I will leave running on that hardware only for days, weeks, months etc. to see if I can detect one:


Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz (4 cpu in /proc/cpuinfo)
production grade hardware. 64 bits cpu running slackware 14.0x64:



Intel(R) Pentium(R) 4 CPU 3.20GHz (2 cpu in /proc/cpuinfo)
very old IBM PC 32bit cpu running slackware 14.0



AMD Athlon(tm) 64 X2 Dual Core Processor 4200+ (2 cpu in /proc/cpuinfo)
HP media center PC, pretty old hardware too, 64 bits cpu running slackware 14.0x64



 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

I finally detected 1 spurious wakeup in ~12,520,000,000 waits on the last machine:

Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz (4 cpu in /proc/cpuinfo)
production grade hardware. 64 bits cpu running slackware 14.0x64:

 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you try the code with more (or less) than 3 printing threads, please fix line 61 in Thread123v2:

Thread123v2[] threads = new Thread123v2[3];

should be:

Thread123v2[] threads = new Thread123v2[threadNumbers];
 
Campbell Ritchie
Marshal
Posts: 52555
119
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Since you are using that variable as a constant it should be declared final and written in CAPITAL_LETTERS.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Since you are using that variable as a constant it should be declared final and written in CAPITAL_LETTERS.


Nah, it was never meant to be final by design. Here you go, I fixed it for you:
 
Campbell Ritchie
Marshal
Posts: 52555
119
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's more like it.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks again everybody for the spurious wakeups advice. I found in CVS and reviewed the multi-threaded code I wrote some 15 years ago (I wrote a jsp like server before jsps existed ;) and I now wonder if I had read somewhere that you needed to check a condition on waits or if I was just doing it intuitively because it made sense. In that case, I guess I was just lucky. I could swear I have never heard of spurious wakeups before although. I wonder if the term existed back then or maybe I am just getting old ;-)

anyway some old code example from back then:

Example from a thread pool I wrote (didn't exist in java back then).


Edit: I used to test critical things like thread pools with testers code and leave it running for days, maybe I just noticed waits() were waking up by themselves and decided to add a while(! notified) condition to fix things without knowing anything about spurious wakeups. That puzzles me ;-)

Edit 2: Hmm... jdk 1.1 didn't mention anything about spurious wakeups so it must be the same for jdk 1.0: https://www.cs.princeton.edu/courses/archive/fall97/cs461/jdkdocs/api/java.lang.Object.html#wait%28%29

Thanks again,


 
Tim Holloway
Bartender
Posts: 18412
58
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Varun Gokulnath wrote:Hi,

I was recently asked a Java multi-threading question in an interview. The questions is : Write a program that creates 3 Threads. The first Thread prints 1, the second Thread prints 2 and the third 3. The Threads should run in such a way that they print the sequence 1 2 3 1 2 3 .... forever



Aaargh.

Do this:



Apologies for whatever incorrect syntax I'm using. I don't manually spawn threads often these days.

Now you can spawn as many threads as you want (including 1!), they can run and intermingle in any order you want and you're guaranteed the results will always go 1 2 3 1 2 3 1 2 3 1 2 3

You see why I tend to flunk "programming tests?"
 
Paweł Baczyński
Saloon Keeper
Posts: 1951
38
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But this doesn't guarantee that each thread prints the number that is associated to it (which is a requirement).
 
Stephan van Hulst
Bartender
Posts: 6583
84
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, that's why it's a silly test, because threads are NEVER used this way. Tasks should not care about threads.
 
Tim Holloway
Bartender
Posts: 18412
58
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paweł Baczyński wrote:But this doesn't guarantee that each thread prints the number that is associated to it (which is a requirement).


Ah, Sorry, I missed the part where it said the thread prints 1, 2, or 3. Was just reading it as 3 threads and the output had to be 1, 2, 3.

Of course, the whole point of multi-threading is the antithesis of strict serial execution - otherwise it's needless overhead - so this "test", like so many others is not only contrived, but has no apparent practical use or adaptability for real-life (on-the-job) use.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
A.J. Côté wrote:Hehe, I just detected a spurious wakeup [...]


Hah, neat. I didn't actually expect they would happen.


Well, I just had it running on the server for 5 days and ~79,980,000,000 waits without a single spurious wakeup. The strange thing is that spurious wakeups seem more likely to happen when I run the test with 3 threads instead of 20. I ran the five day test with 20 threads. It seems that when a given thread is woke up more often in a really short time interval, spurious wakeups are more likely but this could be completely false ;-)

Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz (4 cpu in /proc/cpuinfo)
production grade hardware. 64 bits cpu running slackware 14.0x64:

 
Stephan van Hulst
Bartender
Posts: 6583
84
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It may also have to do with the number of green threads over cores ratio. Alas, all of this is mostly a result of the vagaries of the hardware and the OS. Nothing we should really concern ourselves with, other than keeping in mind it can happen.
 
A.J. Côté
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:It may also have to do with the number of green threads over cores ratio. Alas, all of this is mostly a result of the vagaries of the hardware and the OS. Nothing we should really concern ourselves with, other than keeping in mind it can happen.


I agree, Here's the link.... ;-)
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!