Homework Assignment #7 [40 points]

Overview

This is an assignment in which you reason about the use of condition variables. It is a follow up to Homework Assignment #5, in which the implementation is moved to using semaphores. You may want to re-read Assignment #5 if it’s not longer fresh in your mind.

How/What to turn in

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

Question #1 [10 pts]: Finding semaphore bugs

Given what happened in the previous phase of development (i.e., Homework Assignment #5), your boss is frustrated and tasks you and Frank to work on this. Frank, insists that you use Semaphores for the implementation. You sit down with Frank and you start your IDE. At that point Frank makes some statement about using Emacs and writing Lisp macros, and quickly disappears in his office because he has to write a critical FreeBSD kernel patch. Left to your own devices you write the code below.

By looking at your ICS432 material, which you keep at hand at all times and will for the rest of your life, you quickly realize that this is not quite right. Explain why.

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
Stack {
  int size;
  int items[SIZE];
  Semaphore mutex = 1;
  Semaphore not_full = 1;
  Semaphore not_empty = 0;
}

void push(Stack stack, int value) {
  P(mutex);
  while (stack.size == SIZE) {
    P(not_full); 
  }
  stack.items[stack.size] = value;
  stack.size ++;
  V(not_empty);
  V(mutex);
  return;
}

int pop(Stack stack) {
  P(mutex);
  while (stack.size == 0) {
    P(not_empty);
  }
  int value = stack.items[stack.size - 1];
  stack.size --;
  V(not_full);
  V(mutex);
  return value;
}

Question #2 [30 pts]: Filling in the blanks

You fix your code and have a working version. Frank comes out of his office after radically changing the way in which FreeBSD does virtual memory. He looks at your code and says “This is Semaphore code written by somebody who likes locks and condition variables, I will have none of it! Back at Xerox Park in the 80’s .....”

Before you can throw something at him he says you can rewrite this without any if/while/for statement if you use two semaphores in addition to the mutex semaphore. He then writes the code below, but with cryptic semaphore names and missing statements “?????” that he says you can fill in yourself for your “training”, making some dated “wax on / wax off” reference as he walks away….

For each ???? below (reference line numbers for each), say what code you should insert. Some of these could be “nothing”.

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
Stack {
  int size;
  int items[SIZE];
  Semaphore mutex = 1;
  Semaphore SemA = ????;
  Semaphore SemB = ????;
}

void push(Stack stack, int value) {
  ?????
  P(mutex);
  ?????
  stack.items[stack.size] = value;
  stack.size ++;
  ????
  V(mutex)
  ????
  return;
}

int pop(Stack stack) {
  ?????
  P(mutex);
  ?????
  int value = stack.items[stack.size - 1];
  stack.size --;
  ??????
  V(mutex);
  ??????
  return value;
}