2. (Paging virtual memory.) Justify briefly your answer, a formula and/or numeric answer will not be enough! The different parts of the problem are independent of each other.
(a) If there are four initially empty page frames and eight pages, how many page faults will occur with the reference string 017 232 710 3 if the page replacement algorithm used is
FIFO? How about LRU? (Count the loading of a page to an empty frame also as a page fault.) (4p)
(b) If an instruction takes 1 microsec on average and a page fault takes additional n microsec
on average, give a formula for the expected instruction time if page faults occur every k
instructions on average. (2p)
Suppose that a 32-bit virtual address is broken up into four fields of sizes a, b, c, and d
bits, with the first three being used for a three-level page table system, respectively, and
the fourth being the offset. How does the number of pages depend on each of the size
parameters? (2p)
3. Describe the users' view of the principles of the operation of the NFS. How has NFS been implemented? (6p)
4. (Nachos) You've just been hired by Mother Nature to help her out with the chemical reaction to form water, which she doesn't seem to be able to get right due to synchronization problems. The trick is to get two H atoms and one O atom all together at the same time. The atoms are threads. Each H atom invokes a procedure hReady when it's ready to react, and each O atom invokes a procedure oReady when it's ready.
You are to write the code for hReady and oReady using semaphores for synchronization. The procedures must delay until there are at least two H atoms and one O atom present, and then one of the procedures must call the procedure makeWater (which you need not write); if there are enough atoms to make water, water should be made. After the makeWater call, two instances of hReady and one instance of oReady should return. Your solution should avoid deadlocks, starvation and busy-waiting. Do not read the value of a semaphore! (6p)
5. Briefly describe
(a) the logical clock algorithm of Lamport. What properties do the time stamps it produces have? Of what use are the time stamps in a distributed system? (4p)
(b) the wait-die and wound-wait algorithms for deadlock prevention in a distributed system. What must be assumed about the system in order to implement these algorithms?(4p)
(c) the voting algorithm to update a replicated file system. How must the read and write quorums be determined for the algorithm to be correct? (4p)