CS414 Operating Systems - Homework 4

Due: (Tues) April 8, 10am. No late assignments will be accepted.

Submit your solution using CMS. Prepare your solution using Word (.doc) or some ascii editor (.txt), as follows:

• Use 10 point or larger font.
• Start each problem's solution on a new page.
• Use at most 1 page per problem.

1. A new page-replacement policy has been proposed. Known as the sordid policy, the policy is:

   Replace the page that has the smallest page name.

   Is this policy a "stack algorithm". If so, explain why; if not, give a counter-example.

   ---

2. You have been asked to assist in designing a new processor architecture that supports segmentation, where segments are paged and memory is byte-addressable. Two alternatives are being contemplated for the virtual address format. In both formats, the low-order 12 bits indicate an offset into a page.

   Format 1: The high order 8 bits define a segment; the next 12 bits define a page within that segment.

   Format 2: The high order 6 bits define a segment; the next 14 bits define a page within that segment.

   Assume a segment-table entry occupies 8 bytes and a page table entry occupies 4 bytes. An ordinary single-level, in-memory, page-table architecture is being adopted. (So the machine does not have an inverted page table or multi-level page tables.)

   1. How many distinct bytes can be addressed with Format 1 and with Format 2?
   2. How many distinct pages can be addressed with Format 1 and with Format 2?
   3. How many distinct segments can be addressed with Format 1 and with Format 2?
   4. Which format (1 or 2) sacrifices the least amount of memory to internal fragmentation. Justify your answer with the necessary calculations.
   5. Which format (1 or 2) sacrifices the least amount of memory to table fragmentation. Justify your answer with the necessary calculations.

   ---

3. Consider a computer that supports virtual memory, where a virtual address consists of a 12-bit segment name s, 10-bit page name p, and a 12 bit displacement d into the page. Due to a hardware-design mistake, virtual memory references work in a slightly unusual way and each virtual address is translated into a real address as follows.
   1. s is the left-most 12 bits (as would be expected).
   2. p is the right-most 10 bits (as would not be expected--one would expect p to be the 10 bits that immediately follow the 12 bits that form s).
   3. d is the 12 bits that immediately follow the 12 bits that form s (and thus it is also the 12 bits that immediately precede the 10 bits that form p, as would not be expected).

   In short, the p and d fields in a virtual address have been interchanged from what is usual.

   What, if any, effect will this hardware-design mistake have on (a) the correctness and (b) the performance of programs that use the virtual memory on this computer.