CS 537 - Quiz #1

	UNIVERSITY OF WISCONSIN Computer Sciences Department

CS 537 Fall 2012		Barton Miller
	Quiz #1 Tuesday, September 25

Concurrent and Cooperating Processes

For the following two example programs, you are to describe what will be the output when each program is run. If there is more than one possible output, describe all the possibilities. Here are some general important facts:

Each program is made up of two concurrent processes. You don't know in what order they will run, nor do you know when the dispatcher will switch between processes. However the dispatcher will eventually and continually switch back and forth between processes (i.e., no process will starve).
The initialization code (setting the initial values for the shared variables), is completed before either of the two processes run.
Both the variables (X and Y) are shared between the two processes.
Every time a variable is referenced (appears in an expression), it is read from memory.
Every time a variable is set (appears on the left-hand size of an assignment operator), it is written to memory.
Reading and writing single words (ints) is atomic.

Problem 1

Initialization
int X = 0; int Y = 0;

Process A
for (; X < 4; X++) { Y = 0; printf ("%d", X); Y = 1; }
Process B
while (X < 4) { if (Y == 1) printf ("a"); }

Describe the output here:

The most concise way to write the answer would be:
0 a^* 1 a^* 2 a^* 3 a^*
A slightly more verbose description is:
0 {0 or more a's} 1 {0 or more a's} 2 {0 or more a's} 3 {0 or more a's}

Problem 2

Initialization
int X = 0; int Y = 0;

Process A
while (X == 0) { // do nothing } printf ("a"); Y = 1; Y = 0; printf ("d"); Y = 1;
Process B
printf ("b"); X = 1; while (Y == 0) { // do nothing } printf ("c");

Describe the output here:
The output will be either:
badc
or:
bacd
The difference depends on whether the dispatcher switches processes between first time Y is set to 1 and the time that Y is set to 0

Problem 1
Initialization int X = 0; int Y = 0;
Process A for (; X < 4; X++) { Y = 0; printf ("%d", X); Y = 1; }	Process B while (X < 4) { if (Y == 1) printf ("a"); }
Describe the output here: The most concise way to write the answer would be: 0 a^* 1 a^* 2 a^* 3 a^* A slightly more verbose description is: 0 {0 or more a's} 1 {0 or more a's} 2 {0 or more a's} 3 {0 or more a's}

Problem 2
Initialization int X = 0; int Y = 0;
Process A while (X == 0) { // do nothing } printf ("a"); Y = 1; Y = 0; printf ("d"); Y = 1;	Process B printf ("b"); X = 1; while (Y == 0) { // do nothing } printf ("c");
Describe the output here: The output will be either: badc or: bacd The difference depends on whether the dispatcher switches processes between first time Y is set to 1 and the time that Y is set to 0