### 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

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?

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?

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.

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.

6. Consider the following code to implement a simple pager like more(1):
```
// ... miscellaneous #include's here ...
#define SIZE 256
#define WRITE 1
#define TRUE 1
#define FALSE 0
main()
{
int lines=0; int p[2]; char buf[SIZE];
pipe(p);
if (fork()) {
close(p[WRITE]); // here
fgets(buf, SIZE, reader); printf("%s", buf); lines++;
if (lines==20) {
printf("more?\n"); fgets(buf, SIZE, stdin); lines=0;
}
}
} else {
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?

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?

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?