CS 414 Homework 4: Due in class on Oct. 28.
Note: Late homeworks not accepted this time due to Nov. 2 prelim

1. Suppose that we run the LRU paging algorithm with some fixed partition size D on a reference string, and then run the Working Set (WS) algorithm on the identical reference string, with a working set size equal to D (the same value). You may assume that the actual working set of the program fits into memory.

a) True or false (explain why): "t, S_WS(t) Í S_LRU(t)

b) True or false (explain why): WS and LRU have the same hit ratio.

c) Suppose that your computer will be used to run a single program – no multitasking or sharing, and that it lets you pick the paging algorithm it will use. If you care only about maximum performance would you tell the O/S to use the LRU or the WS algorithm? Explain.

2. Suppose that a computer is to be dedicated to running a single, non threaded program continuously. The true working set of the program is slightly larger than physical memory. For example, perhaps the program really needs 100 pages but the physical memory only has 95 pages available. You must chose between the LRU fixed memory partition algorithm and the working set algorithm. In both cases, you would set the memory partition size equal to the total number of available physical pages. How would you expect the runtime paging behavior of the two alternatives to differ?

3. Suppose that a program has been running on a computer for several years without problems, using a virtual memory policy with a fixed partition of k memory pages. You move it to a much faster computer but keep the same fixed partition size. On the new machine, however, the program appears to be thrashing! Explain how this could happen.

4. Suppose that a factory builds widgets. Each widget is built from sub-widgets, and so forth, in a sort of tree structure. The nodes are machines that produce things. The ones at the leaves consume raw materials and output sub-assemblies. The root node is the machine that makes the widget itself. Now, suppose that you are designing a producer-consumer structure to interconnect the various stages of the factory. You’ll put a separate instance of the buffer on each “edge” of the tree. For example, a conveyor belt that can hold a maximum of 3 sub-widgets of type A is like a bounded buffer with capacity 3. Once it fills up, the producer has to wait (if this is confusing, think of the check-out system at the supermarket).

For example, perhaps two sub-widgets, one of type A and one of type B, are required to construct a widget. The sub-widget generator for type A will produce A’s and put them in the buffer between A and the root. And the sub-widget generator for type B will produce B’s and put them in a different buffer to the root. The widget assembly machine at the root will take one A and then one B, assemble one widget, put it in a box for shipment, and then repeat. (This example is for a factory with just 3 “nodes” and 2 “edges” but in general, the factory may be much more complex – an arbitrary tree, but with a single root node).

Do you need to worry about deadlock? Explain why.