• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Tim Cooke
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Frank Carver
  • Henry Wong
  • Ron McLeod
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Himai Minh

Threads taking turns

 
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Marshal
Posts: 27364
88
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author
Posts: 23928
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Ranch Hand
Posts: 417
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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,
 
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 23928
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Additionally, when you control everything, there is no such things as spurious Threads ;-)
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 23928
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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];
 
Marshal
Posts: 76393
364
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 76393
364
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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,


 
Saloon Keeper
Posts: 26011
186
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?"
 
Bartender
Posts: 2236
63
IntelliJ IDE Firefox Browser Spring Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Saloon Keeper
Posts: 26011
186
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.... ;-)
 
I'm still in control here. LOOK at this tiny ad!
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic