Name: ________________________________ Login: _____________

Comp111 Midterm Exam
Nov 5, 2014 - open books and notes

Any and all printed and written materials are allowed, including books, course notes, and handwritten notes.

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

Please show all work on these pages. Feel free to use the back of each page as needed. Make sure that your work for each problem is clearly marked, especially on the backs of pages. These pages will be graded and returned electronically, like exercises, and the results will be made available online.

Please note that point values have no correspondence with difficulty. We suggest that you solve the problems that you best understand first.

Please also note that the space I gave you to answer is the space I might need, and not necessarily the space you will need. There is no deduction for more verbose answers (though succinct and comprehensive answers are very much appreciated by your instructor!).
1       of 10
2       of 10
3       of 10
4       of 10
5a       of 10
5b       of 10
6a       of 10
6b       of 10
6c       of 10
7       of 10
8       of 10
Total       of 100

    Name: ________________________________ Login: _____________

  1. Can you register a signal handler that will continue to function after a successful execl? Why or why not?

  2. Suppose that you open a file and dup the descriptor. Does closing the dup'd descriptor close the original? Why or why not?

  3. Why is it typically wasteful to make copies of all process memory when forking?

  4. The buddy system for memory allocation does not handle very large chunks, e.g., more than a page in size. Instead, available blocks are handled via a simple free list and the descriptor remembers the size. Why is this preferable to using the buddy system for large chunks?

    Name: ________________________________ Login: _____________

  5. Consider the code:
    #define SIZE 20
    int begin=0, end=0; char queue[SIZE]; 		
    int empty() { return begin==end; } 		
    int full() { return ((end+1)%SIZE)==begin; }
    void enqueue(char c) {
        pthread_mutex_lock(&can_enqueue); //1 
        int empty_before=empty(); 
        queue[end]=c; end=(end+1)%SIZE;
        int full_after=full(); 
        if (empty_before) {
        if (!full_after) {
    char dequeue() {
        char out; 
        int full_before = full(); 
        out = queue[begin]; begin=(begin+1)%SIZE; 
        int empty_after = empty(); 
        if (full_before) {
        if (!empty_after) {
        return out; 
    1. What would happen if I deleted or commented out the line marked '//1'? Why?

    2. What would happen if I locked (and unlocked) can_modify inside the subroutines empty() and full()?

    Name: ________________________________ Login: _____________

  6. Consider the Banker's algorithm tableau:

    Requested (and approved) Granted (and held) Deficit
    R1R2R3R4 R1R2R3R4 R1R2R3R4
    P11 0 0 0 - P11 0 0 0 = P10 0 0 0
    P23 0 0 0 P21 0 0 0 P22 0 0 0
    P30 2 0 0 P30 2 0 0 P30 0 0 0
    P43 2 2 0 P41 2 2 0 P42 0 0 0
    R1 R2 R3 R4
    4 4 4 4

    1. Give a completion schedule for the above tableau and explain why.

    2. If P1 requests 1 more unit of R1, is the resulting tableau safe? Why?

    3. If P1 requests 2 more units of R1, is the resulting tableau safe? Why?

    Name: ________________________________ Login: _____________

  7. Write a version of sem_wait(void) that has the exact behavior of sem_wait, but uses mutexes to turn a regular integer global variable
    int sem;
    into a semaphore.

  8. (Extra credit; advanced) We mentioned in class that there is a method whereby one can avoid mutex locks by crafting each critical section to be logically atomic. What are the limits of this method? What kinds of atomicity could one use?