Name: ________________________________ Login: _____________

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.

    Name: ________________________________ Login: _____________

  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?

    Name: ________________________________ Login: _____________

  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?

    Name: ________________________________ Login: _____________

  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?

    Name: ________________________________ Login: _____________

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




















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

    Name: ________________________________ Login: _____________

  6. (10 points) Since an IA64 processor doesn't represent a segment table in 64-bit mode, why does the IA64 version of linux still represent segments of processes inside the kernel?

    Name: ________________________________ Login: _____________

  7. (10 points extra credit: advanced) The "docker" utility in linux allows one to run a whole instance of linux as a user process. How does docker handle memory mapping, given that it is literally running its "processes" inside one actual linux process?