Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
Francisco J. Bermejo
Greenhorn
Posts: 27
Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
  • 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
 
micha koern
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • 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
  • 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.
 
anirudh jagithyala
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • 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
  • 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
  • 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.
 
Hareendra Reddy
Ranch Hand
Posts: 173
Fedora Firefox Browser Java
  • Mark post as helpful
  • send pies
  • 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.
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • 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
  • 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
  • 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
  • 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
  • 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?
 
Stephan van Hulst
Bartender
Pie
Posts: 6113
72
  • Mark post as helpful
  • send pies
  • 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.
 
Mark Spritzler
ranger
Sheriff
Posts: 17278
6
IntelliJ IDE Mac Spring
  • Mark post as helpful
  • send pies
  • 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
  • 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!
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • 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
  • Quote
  • Report post to moderator
Thanks Mike, that's the clearest explanation yet.
 
Bert Bates
author
Sheriff
Posts: 8900
5
  • Mark post as helpful
  • send pies
  • 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
Pie
Posts: 6113
72
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think these are all the possible outcomes:

 
Kevin Simonson
Ranch Hand
Posts: 137
  • Mark post as helpful
  • send pies
  • 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: 137
  • Mark post as helpful
  • send pies
  • 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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic