Homework/Lab 2 Sample Solutions
Solutions here gathered from submissions where possible
Graded out of 20 points.
1. Andrews, Exercise 2.5 (5 points)
A sequential program can be clever and take advantage of the fact that
the arrays are sorted. This makes parallelization more difficult,
however. The naive solution:
int a[m], b[n];
int i, j, intersection = 0;
/* Compute a and b */
for (i=1; i <= m; i++) {
for (j=1; j <= n; j++) {
if (a[i] == b[j]) {
intersection++;
}
}
}
can be parallelized fully:
co (i=1; i <= m; i++) {
co (j=1; j <= n; j++) {
if (a[i] == b[j]) {
intersection++;
}
}
}
The only synchronization needed is a mutual exclusion on the update of
"intersection".
That's probably the best we can do, if we are going to try to have m*n
processes. Let's try for just two processes, one to traverse each
array. This is based on a student submission:
int ai=1, bi=1;
int intersection=0;
co {
while (ai <= m) {
= b[bi]);>
if (a[ai] == b[bi]) {
intersection++;
}
ai++;
}
// {
while (bi <= n) {
a[ai]);>
if (a[ai] == b[bi]) {
intersection++;
}
bi++;
}
}
}
An advantage here is that we traverse each array only once.
Lots of other ideas are possible here.
2. Andrews, Exercise 2.8 (5 points)
A queue is often represented using a linked list. Assume that two
variables, head and tail, point to the first and last elements of the
list. Each element contains a data field and a link to the next element.
Assume that a null link is represented by the constant null.
(a) Write routines to (1) search the list for the first element (if any)
that contains data value d, (2) insert a new element at the end of the
list, and (3) delete the element from the front of the list. The search
and delete routines should return null if they cannot succeed.
node_t* search(queue *q, value d) {
node_t *node = q->head;
while(node != NULL) {
if (node->value = d) {
break;
}
else {
node = node->next;
}
}
return node;
}
void insert_end(queue *q, value new_val) {
node_t *node;
node = (node_t *) malloc( sizeof(node_t));
node->value = new_val;
node->next = NULL;
if (q->tail != NULL) {
q->tail->next = node;
q->tail = node;
}
else {
/* Empty queue */
q->tail = node;
q->head = node;
}
}
void delete_front(queue *q) {
node_t *node = q->head;
if (q->head != NULL) {
q->head=q->head->next;
node->next = null;
free(node);
}
}
(b) Now assume that several processes access the linked list. Identify
the read and write sets of each routine, as defined in (2.1). Which
combinations of routines can be executed in parallel? Which combinations
of routines must execute one at a time (i.e., atomically)?
Search routine: read set is every element in queue, write set is empty
insert_end: write set is the last element and the new element, read
set is the last element
delete_front: write set is the first element of the queue, read set
is also first element
Both insert_end and delete_front can be executed in parallel because
the intersections of their write sets and read sets is empty. Since both
of the above routines change the queue, they cannot be run in parallel
with search.
(c) Add synchronization code to the three routines to enforce the
synchronization you identified in your answer to (b). Make your atomic
actions as small as possible, and do not delay a routine unneccesarily.
Use the await statement to program the synchronization code.
boolean safe_head = true, safe_tail = true;
node_t* search(queue *q, value d) {
node_t *node = q->head;
safe_head = true;
while(node != NULL) {
if (node->value = d) {
break;
}
else {
if (node->next = q->tail) await(safe_tail);
node = node->next;
}
}
return node;
}
void insert_end(queue *q, value new_val) {
node_t *node;
node = (node_t *) malloc( sizeof(node_t));
node->value = new_val;
node->next = NULL;
if (q->tail != NULL) {
q->tail->next = node;
q->tail = node;
}
else {
/* Empty queue */
q->tail = node;
q->head = node;
}
safe_tail = true;
}
void delete_front(queue *q) {
node_t *node = q->head;
if (q->head != NULL) {
q->head=q->head->next;
safe_head = true;
node->next = null;
free(node);
}
}
3. Andrews, Exercise 2.10 (3 points)
Consider the following program:
int x = 0, y = 0;
co x = x + 1; x = x + 2;
// x = x + 2; y = y - x;
oc
(a) Suppose each assignment statement is implemented by a single machine
instruction and hence is atomic. How many possible histories are there?
What are the possible final values of x and y?
6 histories are possible. x will be 5, and y will be -2, -3, or -5.
(b) Suppose each assignment statement is implemented by three atomic
actions that load a register, add or subtract a value from that register,
then store the result. How many possible histories are there now? What
are the possible final values of x and y?
There are 924 possible histories.
x will be one of 1, 2, 3, 4, or 5. y will be one of 0, -1, -2, -3, -4, or
-5.
4. Andrews, Exercise 2.13 (3 points)
Consider the following three statements:
S1: x = x + y;
S2: y = x - y;
S3: x = x - y;
Assume that x is initially 2 and that y is initially 5. For each of the
following, what are the possible final values or x and y? Explain your
answers.
(a) S1; S2; S3;
The final values of x and y are 5 and 2 respectively. Because
the statements run sequentially, there is only one possible set of
outcomes.
(b) co // // oc
Since each statement runs concurrently, they can execute in
any order. However, since each statement is atomic, the do not interfere
with one another. Thus, there are six possible final answers
corresponding to the six possible sequences of statements: S1,S2,S3: x=5,
y=2; S1,S3,S2: x=2, y=-3; S2,S1,S3: x=2, y=-1; S2,S3,S1: x=2, y=-3;
S3,S1,S2: x=2,y=-3; S3,S2,S1: x=-11, y=-8.
(c) co y) S1; S2;> // oc
This statement can never finish because it gets stuck waiting
for x>y. However, statement S3 does not make x>y; it actually makes x
smaller. Since the await condition is never satisfied, the segement never
finishes. Therefore, no final answers.
5. Andrews, Exercise 2.18 (4 points)
Consider the following program:
co 0) x = x - 1;>
//
//
oc
For what initial values of x does the program terminate, assuming
scheduling is weakly fair? What are the corresponding final values?
Explain your answer.
The program will terminate when x starts with 1, 0, or -1. If x>1
to start, the first action should run, decrementing x. However, x is
still positive and not 0, so neither of the other actions will run and
will wait indefinitely. If x < -2 to start, the second action runs and
increments x by 2. However, x is still less than 0 and not 0, so neither
action will run. If x = -2, then the second action runs, incrementing x
by 2. Now x = 0 so the third action runs, decrementing x. Since x is not
positive, the first action hangs indefinitely. When x starts as 1, the
first action executes, then the third and finally the second with finally
x=1. When x starts as 0, the third, then second, then first action runs
with finally x=0. When x starts as -1, the second, then the first, then
the third actions run with finally x=-1.