Homework Assignment #5 [50 points]

Overview

This is an assignment in which you reason about the use of condition variables. Specifically, you must find bugs in a series of broken implementations of a Thread-safe bounded stack of integers written by a “co-worker.” All code is written in pseudo-code and the specific syntax does not matter.

How/What to turn in

You should turn in a PDF or plain text README file with your answers in Laulima.

Question #1 [20 pts]: Finding concurrency bugs

Your co-worker has produced the following code, with the semantic that the application simply terminates if there is a pop on an empty stack or a push on a full stack. These are not great semantics, but before you can voice your discontent your co-worker says: “I have added two functions to check on the empty/full status of the stack, isEmpty() and isFull(), and users can avoid program termination without using any locks themselves by calling these functions to check that the stack isn’t full/empty before pushing/popping”.

Explain why your co-worker’s statement above is wrong by giving a simple sequence of events when more than one thread manipulates the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Stack {
  int size;
  int items[SIZE];
  Lock mutex;
}

void push(Stack stack, int value) {
  lock(stack.mutex);
  if (stack.size == SIZE) {
    print "Stack full";
    exit;
  } 
  stack.items[stack.size] = value;
  stack.size ++;
  unlock(stack.mutex);
}

int pop(Stack stack) {
  lock(stack.mutex);
  if (stack.size == 0) {
    print "Stack empty";
    exit;
  }
  int value = stack.items[stack.size - 1];
  stack.size --;
  unlock(stack.mutex);
  return value;
}

int isEmpty(Stack stack) {
  return (stack.size == 0);
}

int isFull(Stack stack) {
  return (stack.size == SIZE);
}

Question #2 [15 pts]: Finding more concurrency bugs

Convinced by your argument, your co-worker goes back to the drawing board and produces a new implementation. The new semantic is that push() and pop() return a success code, a failure code, or an integer value. However, the code he shows you below is broken. Explain why and refer to problematic line numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Stack {
  int size;
  int items[SIZE];
  Lock mutex;
}

int push(Stack stack, int value) {
  lock(stack.mutex);
  if (stack.size == SIZE) {
    return STACK_ERROR;
  } 
  stack.items[stack.size] = value;
  stack.size ++;
  unlock(stack.mutex);
  return STACK_SUCCESS;
}

int pop(Stack stack) {
  lock(stack.mutex);
  if (stack.size == 0) {
    return STACK_ERROR;
  }
  int value = stack.items[stack.size - 1];
  stack.size --;
  unlock(stack.mutex);
  return value;
}

Question #3 [15 pts]: Yet more bugs!

You’re tired of this “do everything with locks” vibe, and of the lame semantics. You have taken ICS432 and thus proceed to teach your co-worker about condition variables, realizing in the process that teaching concurrency is harder than it looks. Your co-worker then produces the code below.

Before you even being to look at the code, from the basement comes Frank with his bushy beard, his FreeBSD t-shirt from 1993, and his rainbow suspenders. He looks at the code for .1 sec from 10 feet away and says: “It’s broken! I’ve been doing threads since the 80’s, before it was cool.” After rambling for 10 minutes about some concurrency research he did at Xerox Park, he condescends to show everybody 3 big problems with the code.

What are these problems? (the “same problem” in pop() and push() counts only as one).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Stack {
  int size;
  int items[SIZE];
  Lock mutex;
  Cond cond;
}

void push(Stack stack, int value) {
  if (stack.size == SIZE) {
    lock(stack.mutex);
    wait(stack.cond, stack.mutex);
  }
  stack.items[stack.size] = value;
  stack.size ++;
  unlock(stack.mutex);
  return;
}

int pop(Stack stack) {
  if (stack.size == 0) {
    lock(stack.mutex);
    wait(stack.cond, stack.mutex);
  }
  int value = stack.items[stack.size - 1];
  stack.size --;
  unlock(stack.mutex);
  return value;
}