### Comp111 Midterm Exam Nov 15, 2017 - open books and notes

No electronic devices of any kind allowed, including cellphones, calculators, pagers, etc. Please turn these off before beginning the exam.

Please show all work on these pages. Feel free to use the backs of pages as appropriate. Make sure that your work for each problem is clearly marked. Please place your name on each sheet.

Please note that the amount of space after each question does not indicate length requirements for an answer! If an answer is short, write it succinctly.

These pages will be graded and returned electronically, like exercises.

1. Consider the following Banker's Algorithm tableau:
Requested Granted Deficit
R1R2R3 R1R2R3 R1R2R3
P1110- P1000= P1110
P2220 P2210 P2010
P3002 P3000 P3002
Total available
R1R2R3
222
1. (10 points) Prove that this situation is safe by giving a schedule for completing all processes.

2. (10 points) Suppose that P3 requests one more unit of R2. Is the resulting situation safe? Why or why not?

3. (10 points) What is unusual about this tableau -- compared to the others you have seen in class -- and what did processes have to do to cause this situation?

2. Consider the following unusual implementation of bounded buffer:
```
#define SIZE 50
int begin=0; int end=0; char queue[SIZE];
sem_t notempty;  // initialized to 0
sem_t notfull;   // initialized to SIZE-1
void enqueue(char c) {
sem_wait(&notfull);
queue[end]=c; end=(end+1)%SIZE;
sem_post(&notempty);
}
char dequeue() {
sem_wait(&notempty);
char out = queue[begin]; begin=(begin+1)%SIZE;
sem_post(&notfull);
return out;
}
```
1. (10 points) If enqueue and dequeue are each called by unique "producer" and "consumer" threads, does this code contain a damaging race condition? If so, what can happen and what would you do to eliminate the race condition?

2. (10 points) If enqueue is instead called by multiple producer threads, does this code contain a damaging race condition? If so, what can happen, and what would you do to eliminate the race condition?

3. Consider the following two fragments of code:
process 1 process 2
```lock(A)
lock(B)
lock(C)
lock(D)
lock(E)
lock(F)
lock(G)```
```lock(A)
lock(B)
lock(D)
lock(E)
lock(F)
lock(C)
lock(G)```
1. (10 points) Can concurrent executions of process 1 and process 2 deadlock? Why or why not?

2. (10 points) Now remove the first two lock statements from each fragment and answer the first question again. Can the new schedule deadlock? Why or why not?

4. (10 points) One program `malloc`s a million structs in the heap and then exits without freeing them. Is this a problem? Why?

5. (10 points) Another program `malloc`s a million structs, frees them, and then keeps running. Is this a problem? Why?