Name: ________________________________ Login: _____________

Comp111 Midterm Exam
Nov 10, 2015 - 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.

problemscoretotal
1a 10
1b 10
2 10
3 10
4 10
5 10
6a 10
6b 10
7 10
8 10
9 (extra) 10
total 100

    Name: ________________________________ Login: _____________

  1. Consider the following Banker's Algorithm tableau:
    Requested Granted Deficit
    R1R2 R1R2 R1R2
    P142 - P100 = P142
    P221 P201 P220
    P341 P341 P300
    Total available
    R1R2
    5 2
    1. (10 points) Suppose that P3 requests one more unit of R1. Is the resulting situation safe? Why or why not?














    2. (10 points) Is it possible for P2 to request one more unit of R1 in this tableau situation? Why or why not?

    Name: ________________________________ Login: _____________

  2. (10 points) When malloc is implemented using the buddy system described in class, what does the following code print? Why?
     
    int *p = (int *) malloc(sizeof(int)); *p=1;
    int *q = (int *) malloc(sizeof(int)); *q=2;
    int *r = (int *) malloc(sizeof(int)); *r=3;
    free(p); free(q); free(r); 
    p = (int *) malloc(sizeof(int)); 
    q = (int *) malloc(sizeof(int)); 
    r = (int *) malloc(sizeof(int)); 
    printf("p=%d, q=%d, r=%d\n", *p, *q, *r); 
    














  3. (10 points) malloc abandons the buddy system for memory blocks greater than one page in size, and keeps all of the larger blocks in one linked list. Why does it stop using separate linked lists for each size?

    Name: ________________________________ Login: _____________

  4. (10 points) In assignment 3, I claim that the code fragment:
     
    sem_init(&anthill_semaphore, 0, 3); // # of spaces for aardvarke on hill "hill" 
    sem_init(&ants_semaphore, 0, 100);  // # of ants inside hill "hill" 
    // ... and then, later ... 
    if (sem_trywait(&anthill_semaphore)==0) {
      if (sem_trywait(&ants_semaphore)==0) { 
        slurp(hill, aname) 
      } 
      sem_post(&anthill_semaphore); 
    } 
    
    works properly, but that the code fragment
     
    int anthill_count=3; // # of spaces for aardvarks on hill "hill"
    int ant_count=100;   // # of ants inside hill "hill" 
    // ... and then, later ...
    if (anthill_count > 0) { 
      --anthill_count; 
      if (ant_count > 0) { 
        --ant_count;
        slurp(hill, aname); 
      } 
      ++anthill_count; 
    } 
    
    does not work properly. Give an example in which the second code fragment does not work properly, and then explain how the first code fragment prevents the situation you describe.

    Name: ________________________________ Login: _____________

  5. (10 points) There are many cases in which my examples do not clean up after themselves before process exit like the examples of programming you might have seen in COMP15. Give a few examples of this, and in each case, explain why cleanup is unnecessary just before process exit.

    Name: ________________________________ Login: _____________

  6. Consider the following code to implement a simple pager like more(1):
     
    // ... miscellaneous #include's here ...
    #define SIZE 256
    #define READ 0
    #define WRITE 1
    #define TRUE 1
    #define FALSE 0 
    main()
    {
        int lines=0; int p[2]; char buf[SIZE];  
        pipe(p); 
        if (fork()) {
    	FILE *reader = fdopen(p[READ], "r"); 
            close(p[WRITE]); // here 
    	while (! feof(reader)) { 
    	    fgets(buf, SIZE, reader); printf("%s", buf); lines++; 
    	    if (lines==20) { 
    	       printf("more?\n"); fgets(buf, SIZE, stdin); lines=0; 
                } 
            } 
        } else {
            close(fileno(stdout)); dup(p[WRITE]);  close(p[WRITE]); close(p[READ]); 
            execl("/bin/cat", "/bin/cat", "some_big_text_file", NULL);
        }  
    }
    
    1. (10 points) How much of "some_big_text_file" is read into the pipe at a time? Why?











    2. (10 points; advanced) If you comment out the line marked "// here", the parent hangs forever even after the child "cat" exits. Why?

    Name: ________________________________ Login: _____________

  7. (10 points) Give an example of a process or set of processes for which the Least-Recently-Used algorithm for memory frame recovery performs poorly, and explain why.



















  8. (10 points) When a process "thrashes" due to swapping, due to unavailability of enough physical memory, is the time spent swapping counted toward process user time, process system time, or operating system time? Why?

    Name: ________________________________ Login: _____________

  9. (10 points extra credit: advanced) sbrk always zeros each allocated frame before re-allocating it as a new page. This is an apparent violation of the unwritten rule to do everything as quickly as possible. Why is the new frame not just passed to the process as is, without initialization?