Comp 374  final exam study guide solutions	Fall 2000	Dordal

1. Page sizes are a power of two so that the page number and page offsets
can be bit fields of the address. Any other calculation would be too
expensive to do; remember that address translation must be done on
*every* access. If the page offset is N bits, then the page size is 2^N.


2.

FIFO 	1    2    3    4    5    2    6    7    6    5    4    3    2    1
phys	                              F    F                        F    F
1	1    1    1    1    1    1    6    6    6    6    6    6    6    6
2	     2    2    2    2    2    2    7    7    7    7    7    7    7
3	          3    3    3    3    3    3    3    3    3    3    2    2
4	               4    4    4    4    4    4    4    4    4    4    1
5	                    5    5    5    5    5    5    5    5    5    5


LRU 	1    2    3    4    5    2    6    7    6    5    4    3    2    1
phys	                              F    F                   F    F    F
1	1    1    1    1    1    1    6    6    6    6    6    6    6    1     
2	     2    2    2    2    2    2    2    2    2    2    3    3    3
3	          3    3    3    3    3    7    7    7    7    7    2    2
4	               4    4    4    4    4    4    4    4    4    4    4
5	                    5    5    5    5    5    5    5    5    5    5

(error fixed in this column-----------^
 Frame 3 doesn't get virtual page 7 until the following column.)

CLOCK 	1    2    3    4    5    2    6    7    6    5    4    3    2    1
phys	                              F    F                        F    F
1	1*   1*   1*   1*  >1*  >1*   6*   6*   6*   6*   6*   6*   6    6
2	>    2*   2*   2*   2*   2*  >2    7*   7*   7*   7*   7*   7    7
3	    >     3*   3*   3*   3*   3   >3   >3   >3   >3   >3*   2*   2*
4	         >     4*   4*   4*   4    4    4    4    4*   4*  >4    1*
5	              >     5*   5*   5    5    5    5*   5*   5*   5   >5

For Clock, the * means that the use bit is set, and the > marks the 
"current" position.


3. Note there are two rows per page.
(a) row-by-row traversal: the matrix is 256 pages, and it is being
traversed sequentially. There would thus be 256 page faults.

(b). Traversing one column is 256 faults; each pair of consecutive rows
of a column is on the same page but there are 256 pairs.
Traversing every column is 256*512 = 131072 faults.

(c). Now there are enough free pages to hold the entire matrix.
After 256 faults the entire matrix is loaded, and there are no 
further faults.


4. Physical page numbers are allocated here in sequence:
A:1,2,6,11
B:3,4,5
C:7,8,9,10
Here is a picture of the physical layout, labeled by process to which
the page is allocated (a so-called inverted page table):
	A A B B B A C C C C A

Virtual memory is not fragmented (unless the process wants that).
Nonadjacent physical pages are still virtually adjacent.


5. P1() {
	print("thread1");
	A.signal();
   }

   P2() {
	A.wait();
	print("thread2");
	B.signal();
   }

   P3() {
	B.wait();
	print("thread2");
   }


6. The current *available* resources after the allocation would be
<r0,r1,r2,r3> = <1,1,2,0>; we get this by subtracting the column totals
of Figure 10.31 from the original available totals C = <6,4,4,2>.

Now we consider for each process how much *more* it might ask for;
this is the difference between the row in Fig 10.30 (max claims)
and the corresponding row in Fig 10.31 (current allocation).

   r0 r1 r2 r3
p0: 1  2  0  0
p1: 0  1  0  2
p2: 0  0  2  0
p3: 2  2  0  0
p4: 2  0  0  0

One of these processes can be run safely if its requirements are
all "within" the current-available list 1,1,2,0. 

p0: fails because it may need 2 r1's, and there is only 1
p1: fails because it may need 2 r3's, and there are none.
p2: ok to run safely
p3: fails because it may need two r0's and there is only one
p4: same as p3

So we let p2 run. When it does, it frees up its resources, listed in
its row of Fig 10.31, or <1,1,0,0>.  This means that the total
available is now <2,2,2,0>.

This, in turn, is enough to run *any* of the remaining p0,p1,p3,p4,
so we can run them all in any order and remain safe.

So, yes, the new state is a safe state.


7. (a). 10 direct and 256 single-indirect blocks, for a total of 266 blocks.
(b). 10+256+256^2 = 10+256+65536 = 65802
(c). 10 direct-pointers to data blocks
     single-indirect pointer points to an index block, which contains
     another 10 pointers to data blocks.


8. The directory is simply writable by everyone; however, this must
mean that one can create new files but not delete existing ones.
One approach is to make the directory world-writable, but to have
students create *directories* for their files, not just put their
files in. Most operating systems don't allow deletion of subdirectories
unless they are empty, which pretty much means that students can create
new directories but not delete them.

When students copy their directory, though, they need to be able to add
the instructor to the access control list, giving the instructor full access
(read and delete) to the files.

(b). Unix doesn't support the second half of part (a): having each student
give one named individual (the instructor) access to the files.


9. (a). If unix crashes between the link() and unlink(), the file
exists twice.
(b). If the unlink() were done first, and the system crashed between
them, the file would be lost. More precisely, it would not be 
linked but not be on the free list either.


10.


11. open() would read in the disk block containing the inode,
in order to verify the file permissions, if nothing else.
But no data blocks would be read in.

read() would read the appropriate data blocks, and any indirect
blocks as necessary. The inode itself would presumably remain cached
in memory.