File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Doubt regarding Threads found in K&B OCP Java 6 Practice Exams Book Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Doubt regarding Threads found in K&B OCP Java 6 Practice Exams Book" Watch "Doubt regarding Threads found in K&B OCP Java 6 Practice Exams Book" New topic
Author

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

Francisco J. Bermejo
Greenhorn

Joined: Mar 02, 2011
Posts: 27

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


OCPJP 6 96%
micha koern
Greenhorn

Joined: Mar 25, 2011
Posts: 23
Wouldnt this mean, that RSRS is printed?
Francisco J. Bermejo
Greenhorn

Joined: Mar 02, 2011
Posts: 27

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

Joined: Dec 07, 2010
Posts: 41
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

Joined: Mar 02, 2011
Posts: 27

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

Joined: Mar 25, 2011
Posts: 23
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

Joined: Jan 09, 2011
Posts: 173

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

Joined: Mar 12, 2011
Posts: 808
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

Joined: Mar 02, 2011
Posts: 27

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

Joined: Mar 02, 2011
Posts: 27

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

Joined: Mar 02, 2011
Posts: 27

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

Joined: Mar 02, 2011
Posts: 27

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

Joined: Sep 20, 2010
Posts: 3649
    
  17

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

Joined: Feb 05, 2001
Posts: 17260
    
    6

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


Perfect World Programming, LLC - Two Laptop Bag - Tube Organizer
How to Ask Questions the Smart Way FAQ
Francisco J. Bermejo
Greenhorn

Joined: Mar 02, 2011
Posts: 27

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

Joined: Mar 05, 2008
Posts: 3018
    
  10
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

Joined: Mar 12, 2011
Posts: 808
Thanks Mike, that's the clearest explanation yet.
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8883
    
    5
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


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3649
    
  17

I think these are all the possible outcomes:

Kevin Simonson
Ranch Hand

Joined: Oct 22, 2011
Posts: 114
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

Joined: Oct 22, 2011
Posts: 114
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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Doubt regarding Threads found in K&B OCP Java 6 Practice Exams Book