Date: Mon, 11 Nov 1996 17:24:33 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Mon, 18 Mar 1996 14:36:23 GMT Content-length: 2837 CS 537 - Problem Set #2
UNIVERSITY OF WISCONSIN-MADISON
Computer Sciences Department
CS 537
Spring 1996
Bart Miller
Problem Set #2

Problem 1

You are designing the memory mapping hardware for a new machine. The memory addressing will have segments that are paged. The machine has a 64-bit virtual address. Each process can have up to 64K (65536) segments, and page size is 64K bytes.

The segment tables (ST) and page tables (PT) are stored in main memory. ST's and PT's can start at any byte address. Each segment table entry (STE) points to a page table.

Each page table entry (PTE) points to a page in real memory. Each PTE will also have: a "read-enable" bit, a "write-enable" bit, and a bit that is set on each reference to the page.

This machine will support physical memories up to 64 gigabytes.

  1. Draw a diagram of this memory map. Show how the pieces of the virtual address are used to reference each of the tables, and to generate the physical address. Indicate the size of each field, where it comes from, and where it is used. Also indicate where page faults or memory protection traps will be indicated.
  2. How large (in bytes) is a full-sized ST?
  3. Is it a good idea to have a "bounds" field in your STE's? Why or why not? Should this bounds field be in units of bytes or pages?
  4. What happens if we double the page size (while still keeping a 64 bit virtual address)?

Problem 2

  1. Add a TLB to the memory mapping architecture that you described in Problem 1. This cache should be 4-way set associative and will have 256 rows. Draw a diagram of the TLB, showing the size of each field in the TLB. Indicate how bits of the VA are used for input to the TLB, and describe the outputs from the TLB.
  2. How often do you need to flush (clear) the TLB? Why? What change could you make to the TLB to avoid clearing it?

Problem 3

For each of the following page replacement algorithms, describe a case where the algorithm does a poor job in scheduling memory: LRU, LFU, FIFO.

Problem 4

Consider a demand paging system. We measure the various resource utilizations and see:
CPU utilization20%
Paging disk99%

Which of these (if any) should improve the CPU utilization? Why?

  1. Get a faster CPU.
  2. Get a bigger disk.
  3. Get a faster disk.
  4. Increase the degree of multiprogramming.
  5. Decrease the degree of multiprogramming.