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.