Win a copy of Practical SVG this week in the HTML/CSS/JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Humm Interesting!! Interleaving problems on Threads

 
Roshini Chandrasekar
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Guys,

I just started some exercises on threads and I came upon this example. Can you guys tell me if I am thinking threads proper?

Question goes like this:

The following programs are executed concurrently on three processors:
int a,b,c=0;

P1:

1). a=1;
2). output(bc);

P2:

3). b=1;
4). output(ac)

P3:

5). c=1;
6). output(ab);

Function output() automatically reads and displays the values of the variables passed as arguments. For example, if the statements are executed in the order 1,2,3,4,5,6, the program displays 001011

Now:
a). Assume that the processors execute the statements in program order [i.e.,1 before 2, 3 before 4, 5 before 6]. How many possible interleavings of the statements are there?

My Guess is, Since interleaving instructions are actions which we cannot see, I am assuming that he's talking about the read operations here and the ans is 6.

What do U guys say?


b). Is there any interleaving that preserves program order and that produces the output 111111? If so, show an Interleaving. You can assume that only single copy of shared variables a,b,c exists (i.e., that shared variables are not cached)

My Guess?? Nothing

Can anybody help me with these?

Thanks.

[ September 26, 2007: Message edited by: Roshini Chandrasekar ]
[ September 26, 2007: Message edited by: Roshini Chandrasekar ]
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24213
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There are many more than six possible orderings (assuming it makes sense to talk about "ordering" when, as you say, there are three processors; it actually doesn't.) All instructions count. For the first instruction, you have three choices. For the second, you have three choices. For the third, you have either three or two, depending on whether the first two were on the same processor or not. Off the top of my head, I'm not sure what the formula for this would be, but you see already that there are more than 3x3x2=18 orderings

The ordering 135246 (and all similar variations) produces 111111.
 
Roshini Chandrasekar
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Ernest,

Thanks for the reply. I have a question from my own question . Could you tell me what "How many possible interleavings of the statements are there" means?

Thanks.

[ September 26, 2007: Message edited by: Roshini Chandrasekar ]
[ September 26, 2007: Message edited by: Roshini Chandrasekar ]
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24213
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How many possible orderings -- i.e., how many different lists of numbers

123456
123546
123564
...

there are that represent the possible sequence in which the instructions might execute. The only constraint is that for each pair 1,2/3,4/5,6 the second member of a pair must execute after the first.
 
Roshini Chandrasekar
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Ernest
 
Don't touch me. And dont' touch this tiny ad:
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/Thread-Boost-feature
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!