• 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
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Doubt regarding Threads found in K&B OCP Java 6 Practice Exams Book

 
Greenhorn
Posts: 27
Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello everyone, this is the question 25 from Practice Exam 3 of the wonderful (and really though) K&B OCP Java 6 Practice Exams book.



According to the book the correct answers are:


I understand perfectly why they are correct, but I think that there's one more correct answer:


Again, according to the book D is incorrect because:

"The line id = 1 - id; swaps of id between 0 and 1. There is no chance for the same method to be executed twice."


My reasoning is as follows: the first thread can execute "id = 1 - id;" so that id == 0 now, AND BEFORE it executes the next line (if (id == 0) { pick(); }) the second thread could execute "id = 1 - id;" so id would be id == 1 again (remember almost nothing in Java threads is guaranteed, and so is the order of execution of threads). Therefore BOTH threads would execute the method pick() (of course not at the same time, because it is synchronized in the class Stone's lock).

Share your thoughts please
 
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Wouldnt this mean, that RSRS is printed?
 
Francisco J. Bermejo
Greenhorn
Posts: 27
Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

micha koern wrote:Wouldnt this mean, that RSRS is printed?


Hi Micha! Yes, you're right, as id turns out to be id == 1, the invoked method would be release(), and therefore, the output would be "RSRS". But even though we know now that answer D is incorrect, K&B still say:

"The line id = 1 - id; swaps of id between 0 and 1. There is no chance for the same method to be executed twice."

That would be wrong if my theory is correct.
 
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

My reasoning is as follows: the first thread can execute "id = 1 - id;" so that id == 0 now, AND BEFORE it executes the next line (if (id == 0) { pick(); }) the second thread could execute "id = 1 - id;" so id would be id == 1 again



i think that

by the time second thread executes id=1-id the first thread would move to the next line (if (id == 0) { pick(); })
as the methods are not synchronised the threads would execute simultaneously and not wait for other thread .....

May this would help
 
Francisco J. Bermejo
Greenhorn
Posts: 27
Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

anirudh jagithyala wrote:

My reasoning is as follows: the first thread can execute "id = 1 - id;" so that id == 0 now, AND BEFORE it executes the next line (if (id == 0) { pick(); }) the second thread could execute "id = 1 - id;" so id would be id == 1 again



i think that

by the time second thread executes id=1-id the first thread would move to the next line (if (id == 0) { pick(); })
as the methods are not synchronised the threads would execute simultaneously and not wait for other thread .....

May this would help



But as long as I know you can't guarantee anything about the order of thread execution (if no synchronized block is involved). So in some program executions the first thread is able to execute this line if (id == 0) { pick(); }) before the other thread changes the value of id. But other program executions may perfectly behave as the one I described (1st thread changes the value of id, and 2nd thread changes it just before that). You just can't tell.
 
micha koern
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think you are right.
RSRS is possible!
Simply put a sleep into and you have your Result



There is no chance for the same method to be executed twice


This refers to the synchronized methods that are not responsible for your problem.
 
Ranch Hand
Posts: 173
Firefox Browser Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello all,

so id would be id == 1 again (remember almost nothing in Java threads is guaranteed, and so is the order of execution of threads). Therefore both threads would execute the method pick() .


Your reasoning is right but when the value of id is 1 then the else block is executed printing "RSRS".I feel that P Q P Q is not possible because id can't be made to zero for both the threads.
 
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have run this code several times. I never got RSRS, but a few times I did get RSPQ, and once RPQS. I do not think P Q P Q or RSRS are possible.
 
Francisco J. Bermejo
Greenhorn
Posts: 27
Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

micha koern wrote:

There is no chance for the same method to be executed twice


This refers to the synchronized methods that are not responsible for your problem.


Mmmm, I don't think so, I believe the authors symply mean that no method will be executed twice. It has anything to do with the fact that they are synchronized (on different locks by the way).
 
Francisco J. Bermejo
Greenhorn
Posts: 27
Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dennis Deems wrote:I have run this code several times. I never got RSRS, but a few times I did get RSPQ, and once RPQS. I do not think P Q P Q or RSRS are possible.


Yes, I'm quite sure that the situation that I mentioned is nearly impossible to occur in today's computers, but the fact is that in theory it could be... So the correct answer to why D. is wrong should be because id variable NEVER equals 0 in both threads, and therefore you'll never get printed PQPQ as result of invoking pick() twice.
But I insist, the book says that answer D is wrong because:

The line id = 1 - id; swaps of id between 0 and 1. There is no chance for the same method to be executed twice.

That explanation is simply wrong according to my reasoning.
 
Francisco J. Bermejo
Greenhorn
Posts: 27
Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Hareendra Reddy wrote:Hello all,

so id would be id == 1 again (remember almost nothing in Java threads is guaranteed, and so is the order of execution of threads). Therefore both threads would execute the method pick() .


Your reasoning is right but when the value of id is 1 then the else block is executed printing "RSRS".I feel that P Q P Q is not possible because id can't be made to zero for both the threads.


Hi Hareendra, you're right, I was wrong about pick() being executed two times. It is release() which could be (in theory) executed twice. I cannot update my first post any longer. But as I said just above in my previous response, what it is wrong is the reasoning shown in the book about why answer D is incorrect.
 
Francisco J. Bermejo
Greenhorn
Posts: 27
Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
By the way, I'd like to know the authors' opinion to know if in the real exam I should be so picky . Bert?
 
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think it should be theoretically possible for id == 0 to hold true twice, because id = 1 - id is not an atomic operation, and id is also not volatile. I guess in theory P Q P Q should be a possible outcome. Let's see if someone else can comment on this.
 
ranger
Posts: 17347
11
Mac IntelliJ IDE Spring
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Francisco J. Bermejo wrote:By the way, I'd like to know the authors' opinion to know if in the real exam I should be so picky . Bert?



As someone who wrote questions for the 5.0 exam. Yes, the Thread questions are just like this one. And you really have to be picky and make sure you check everything that could possibly happen. Or you could do what I did and just guess on those darn Thread questions. ;)

Mark
 
Francisco J. Bermejo
Greenhorn
Posts: 27
Eclipse IDE Java Ubuntu
  • 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 think it should be theoretically possible for id == 0 to hold true twice, because id = 1 - id is not an atomic operation, and id is also not volatile. I guess in theory P Q P Q should be a possible outcome. Let's see if someone else can comment on this.


Yes I think you're right too!

Mark Spritzler wrote:As someone who wrote questions for the 5.0 exam. Yes, the Thread questions are just like this one. And you really have to be picky and make sure you check everything that could possibly happen. Or you could do what I did and just guess on those darn Thread questions. ;)


Thanks for the tip Mark!
 
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I agree with Stephan and Francisco - it is definitely theoretically possible to for both threads to see id == 0 and thus print PQPQ. whether or not we are actually able to observe this ourselves is another matter, as it may be quite rare, and it may even be impossible for some JVM/OS/hardware implementations. But it's definitely possible in terms of the Java memory model.

In order to execute "i = 1 - i;", a single thread must

1. read the value of i from main memory into a CPU register
2. calculate the result of 1 - i
3. store the result back in main memory

If two threads A and B are executing this sequence simultaneously, the results can intertwine in many ways. Here's one:

A1: thread A reads i = 1
A2: thread A computes 1 - i = 0
B1: thread B reads i = 1
B2: thread B computes 1 - i = 0
B3: thread B stores i = 0
A3: thread A stores i = 0

Thus, both threads could get i = 0.
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Mike, that's the clearest explanation yet.
 
author
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Great discussion you guys!

This one is gonna cause me to go find my "threads" hat to put on...

I'm leaning towards thinking that there's a problem with the question, but I haven't looked at it closely yet.

Thanks for spotting this one!

Bert
 
Stephan van Hulst
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think these are all the possible outcomes:

 
Ranch Hand
Posts: 249
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Bert Bates wrote:Great discussion you guys!

This one is gonna cause me to go find my "threads" hat to put on...

I'm leaning towards thinking that there's a problem with the question, but I haven't looked at it closely yet.

Thanks for spotting this one!



Bert, what is the last word on this question? I just led a SCJP study group, and this problem (number 25 of Practice Exam 3) was one of the problems we went over. I've heard different stories on it depending on who I talk to; most think D should have been a right answer (in addition to A, B, and C), but a few think D couldn't happen. I personally agree with Mike Simmons that "P Q P Q " is a legal output, and that therefore D is a correct answer, but it would be nice to get your opinion on it before next week so I can tell the study group attenders what you said.

Kevin Simonson
 
Kevin Simonson
Ranch Hand
Posts: 249
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I modified the code from Problem 25 somewhat to come up with two files that I named "MyStone.java" and "Media.java" with contents as follows:

---Media.java-------------------------------------------------------------------
enum MediaStatus { EMPTY, INTERMEDIATE, FULL };

public class Media implements Runnable
{
private static class Found
{
private String quadruple;
private long count;

private Found ( char[] toStore)
{
quadruple = new String( toStore);
count = 1L;
}

private void increment ()
{
count++;
}

private boolean matches ( char[] candidate)
{
return quadruple.equals( new String( candidate));
}

private void summarize ()
{ System.out.println( '"' + quadruple + "\": " + count + '.');
}
}

private char[] buffer;
private int nextToRead;
private int nextToWrite;
private MediaStatus status;

Media ( int mdaSze)
{
buffer = new char[ mdaSze];
nextToRead = 0;
nextToWrite = 0;
status = MediaStatus.EMPTY;
}

synchronized void send ( char message)
{
while (status == MediaStatus.FULL)
{ try
{ wait();
}
catch (InterruptedException excptn) {}
}
buffer[ nextToWrite] = message;
nextToWrite = (nextToWrite + 1) % buffer.length;
status
= nextToRead == nextToWrite
? MediaStatus.FULL
: MediaStatus.INTERMEDIATE;
notify();
}

public void run ()
{
char message;
int searcher;
Found[] copy;
Found[] stored = new Found[ 8];
char[] quadruple = new char[ 4];
int quadCount = 0;
int matchCount = 0;
long tooLong = 0L;
long tooShort = 0L;
do
{ synchronized (this)
{ while (status == MediaStatus.EMPTY)
{ try
{ wait();
}
catch (InterruptedException excptn) {}
}
message = buffer[ nextToRead];
nextToRead = (nextToRead + 1) % buffer.length;
status
= nextToRead == nextToWrite
? MediaStatus.EMPTY
: MediaStatus.INTERMEDIATE;
notify();
}
if (message == '/' || message == 'X')
{ if (matchCount < 4)
{ if (0 < matchCount || message == '/')
{ tooShort++;
}
}
else if (matchCount == 4)
{ searcher = -1;
for (;;)
{ if (++searcher == quadCount)
{ if (quadCount == stored.length)
{ copy = new Found[ stored.length << 1];
for (searcher = 0; searcher < quadCount; searcher++)
{ copy[ searcher] = stored[ searcher];
}
stored = copy;
}
stored[ quadCount++] = new Found( quadruple);
break;
}
if (stored[ searcher].matches( quadruple))
{ stored[ searcher].increment();
break;
}
}
}
matchCount = 0;
}
else if (matchCount < 4)
{ quadruple[ matchCount++] = message;
}
else if (matchCount++ == 4)
{ tooLong++;
}
}
while (message != 'X');
System.out.println();
System.out.println( "Too short: " + tooShort + '.');
System.out.println( "Too long: " + tooLong + '.');
for (searcher = 0; searcher < quadCount; searcher++)
{ stored[ searcher].summarize();
}
}
}
---MyStone.java-----------------------------------------------------------------
public class MyStone implements Runnable
{
static int id = 1;

Media media;

private MyStone ( Media mda)
{
media = mda;
}

public void run ()
{
try
{ id = 1 - id;
if (id == 0)
{ pick( media);
}
else
{ release();
}
}
catch (Exception excptn) {}
}

private static synchronized void pick ( Media mda)
throws Exception
{
mda.send( 'P');
mda.send( 'Q');
}

private synchronized void release ()
throws Exception
{
media.send( 'R');
media.send( 'S');
}

public static void main ( String[] arguments)
{
if (arguments.length == 2 || arguments.length == 3)
{ int arg = 0;
try
{ long ite;
Thread th0;
Thread th1;
Thread mTh;
int mdaSize = Integer.parseInt( arguments[ 0]);
arg = 1;
long limit = Long.parseLong( arguments[ 1]);
int notifyInterval;
if (arguments.length == 2)
{ notifyInterval = 0;
}
else
{ arg = 2;
notifyInterval = Integer.parseInt( arguments[ 2]);
}
Media mda = new Media( mdaSize);
MyStone st = new MyStone( mda);
mTh = new Thread( mda);
mTh.start();
for (ite = 0L; ite < limit; ite++)
{ if (0 < notifyInterval && ite % notifyInterval == 0)
{ System.out.println( "At iteration " + ite + '.');
}
th0 = new Thread( st);
th1 = new Thread( st);
th0.start();
th1.start();
th0.join();
th1.join();
mda.send( '/');
}
mda.send( 'X');
mTh.join();
}
catch (NumberFormatException excptn)
{ System.err.println
( "Couldn't convert argument \"" + arguments[ arg]
+ "\" to a number!");
}
catch (InterruptedException excptn)
{ System.err.println( "Some thread got interrupted!");
}
}
else
{ System.out.println( "Usage is");
System.out.println
( " java MyStone <media-size> <#-iterations> [<ntfy-intrvl>]");
}
}
}
--------------------------------------------------------------------------------

I ran this with "java MyStone 4096 100000000 1000000", and the results were:

Too short: 0.
Too long: 0.
"PRQS": 90170.
"PQRS": 72691273.
"PRSQ": 279657.
"RSPQ": 26810261.
"RPSQ": 31954.
"PQPQ": 76.
"RPQS": 96533.
"RSRS": 76.

So it looks like my Java application supports answer D, although the output it mentions is certainly pretty rare, 76 times out of 100 million loops.

Kevin Simonson
 
Just let me do the talking. Ahem ... so ... you see ... we have this tiny ad...
Smokeless wood heat with a rocket mass heater
https://woodheat.net
reply
    Bookmark Topic Watch Topic
  • New Topic