Problem 1

Define the utilization of a resource (over some period of time) to be the percentage of time that the resource is being used. When you measure the utilizations of different resources in the system, you find that the utilization of the CPU is 20%, the utilization of the backing store disk is at 99%, and the utilizations of the other devices (such as the other disks and the network adaptor) are 5% or lower.

1. What phenomenon would most likely result in these characteristics?


The system is thrashing: a majority of the time is being spent waiting for pages to be transfered between backing store and main memory.
 

2. What effect would each of the following actions have on the CPU utilization?
1. Increasing the speed of the CPU. This would decrease the utilization, since the time between page faults would correspondingly decrease.
2. Increasing the capacity of the paging disk. This should have no effect on CPU utilization unless, for some odd reason, a larger disk had different effective data transfer performance.
3. Increasing the page size. The effect of this is hard to predict. It might decrease CPU utilization for a demand paging system, since in doing so the virtual memory system would be reducing the number of read requests. On the other hand, a larger page size reduces the number of page frames making it harder to share what physical memory there is among the processes.
4. Increasing the amount of physical memory. If the mix of processes is left unchanged, then this should increase the CPU utilization.
5. Decreasing the degree of multiprogramming. This will increase the CPU utilization (assuming that there is more than one process running originally!).

Problem 2

• If you double the size of a page, then the number of page faults is reduced;
• If you halve the size of a page, then the number of page faults is reduced.

Let there be 400 bytes of physical memory.

If the page size is 100 bytes, then there are four page frames and the page reference string is 0 1 2 3 4 5 0 1 2 3 4 5 ... Each page reference will result in a page fault: starting with the fifth reference, a reference to page i forces page (i + 4) mod 6 to be discarded. In particular, for any positive integer k after 6k references there will be 6k page faults.

If we double the page size to 200 bytes, then there are two page frames, and the page reference string is 0 0 1 1 2 2 0 0 1 1 2 2  ... There are stuttered references in this string, and each stuttered sequence results in only one page fault. Hence, for any positive integer k after 6k references there will be 3k page faults: the page fault rate is halved.

If we halve the page size to 50 bytes, then there are eight page frames, and the page reference string is 0 2 4 6 8 10 0 2 4 6 8 10 ... There are only five distinct pages in this string, and so there will be only five page faults for any prefix of this string whose length is at least five.

Problem 3

• The word size is 32 bits.
• The page and segment table entries each occupy one word.
• The page size is 512 words.
• A page table occupies at most one page.
• A virtual address is n bits long and is a reference to a word. It has the form (s₁, s₂, p, w).

1. What is the value of |w|? 9, since the page size is 2⁹.
2. What is the maximum number of pages per segment and what is the corresponding value of |p|?

 

 

The limit on this value comes from the requirement that a page table consume no more than one page. Since a page table entry consumes one word (there's a lot of wasted bits here!), a page table can cover up to 512 pages. Hence, |p| is also 9.
 

3. Using the determined values of |w| and |p|, which of the following is choices for |s₁| and |s₂| is preferable?
|s₁| = |w| and |s₂| = n - |p| - |w|
or |s₂| = |w| and |s₁| = n - |p| - |w|


Substituting, we have either |s₁| = 9 and |s₂| = n - 18 or |s₁| = n - 18 and |s₂| = 9. Thus, n must be at least 19. If n = 27 then the question is trivial: both fields have length 9, and so neither is preferable. If n != 18 then the question reduces to is it better to have |s₁| larger than |s₂| or not? and we instantiate the choice of rules above depending on the answer to this question and whether n is at least 20 or not.

In either case, there will be one segment table with a maximum size of 2^|s1|words and 2^|s1| second level segment tables, each of a maximum size of 2^|s2| words. Hence, the maximum space that can be consumed by segment tables is 2^|s1| + 2^{|s1| + |s2|}. With no other information to go on, choosing a smaller |s₁| results in less physical memory being devoted to segment tables.

One can imagine, however, a management scheme in which one had more first level segments, each devoted to a process. If a process never requires more than 2^|s2|+|p|+|w| words of virtual memory, this scheme simplifies page and segment table management.

Would either choice result in a larger virtual address space? Explain.

Neither choice, of course, will result in a larger virtual address space: in either case, there are 2ⁿ addressable words.

Problem 4

Are these two arguments correct? Which policy, if either, should be preferred? Why?

Both arguments are correct to a point, and neither should be preferred because each doesn't address the issue of thrashing. The degree of multiprogramming should be adjusted to ensure that each process can obtain its working set of page frames.