Practice Exercise 12
  1. A computer has 24-bit virtual addresses.
  1. What is the size of its virtual address space?
  2. How many 2K pages would there be in such an address space?
  3. How many page table entries would there need to be?
  1. Suppose each entry in a page table takes 45 bytes. The virtual address space is 1024 pages.
  1. How many bytes would there be in the virtual address space?
  2. How many bytes would a page table occupy?
  3. Suppose each page is 4K long. How many pages long would the page table be in memory?
  1. Suppose there are 31 bits in a virtual address. How big would the pages have to be to keep a process's page table under 1 million entries long?
  1. Why is LRU a reasonable assumption for victim selection when an empty frame is needed? When might it not be a good assumption?
  1. Suppose you are working with a small computer that has 8 pages of 1K each in its virtual address space, and only 4 frames (also of 1K each) in its physical memory, as shown in Fig. 12.2.1. Below is a history of memory accesses, where R=read and W=write and the address is shown. Write down at each point in time which page contains the memory address that is used. Also write into the frame columns which page is currently found in that frame. If the frame has been modified, put an x next to the page number. Use LRU for victim selection, which means find the oldest page that has not been used recently as the victim. Do not take into account whether the page is dirty or not when finding a victim. 
                                                  Frame #
        Time  Instruction   Page       0          1         2          3
        ----+------------+--------+---------+----------+----------+---------+
          1 | R 1000     |        |         |          |          |         |
          2 | R 5092     |        |         |          |          |         |
          3 | W 513      |        |         |          |          |         |
          4 | R 6144     |        |         |          |          |         |
          5 | R 8000     |        |         |          |          |         |
          6 | W 2099     |        |         |          |          |         |
          7 | R 57       |        |         |          |          |         |
          8 | R 3199     |        |         |          |          |         |
          9 | R 6100     |        |         |          |          |         |
         10 | W 3099     |        |         |          |          |         |
         11 | R 1000     |        |         |          |          |         |
         12 | R 5000     |        |         |          |          |         |
         13 | R 3000     |        |         |          |          |         |
Count the number of times a page on disk had to be read as it was being put into a frame. This is a miss count because the page was missed in the TLB. Subtract this from the total number of memory accesses (which is 13 in this example) and get the hit count. Divide the hit count by the total number of memory accesses to get the hit ratio. (Your system will be much more efficient and faster running if the hit ratio is close to 100%.)
  1. A computer has 32-bit virtual addresses. Pages are 8K long. How many bits are devoted to the page offset and how many bits are devoted to the page number?
  1. A computer has 2Kbyte pages and 4,194,304 bytes (4 megabytes) of real memory. Virtual addresses are 28 bits long. If the page table does not include disk addresses in its in-memory copy, how many bytes would the page table take? Each page table entry must start on a byte -- it cannot start in the middle of a byte. Don't forget any bits in the page table.
  1. On average, each job leaves half of its last page unused, and there are a maximum of 20 jobs in memory at any given time. Jobs have 40 pages in their working set. Pages are 2Kbytes long and virtual addresses are 24 bits long. What percentage of the memory is wasted due to internal fragmentation?
  1. Nowadays a memory read on a personal computer may takes 60 nsec. Suppose it takes 10 nsec to examine the TLB and extract the frame number if the desired page number is there. How long would a virtual memory system take to read a word from memory assuming that every page number were in the TLB?
  1. Continuing question 9 above, how long would a virtual memory system take to read a word on average if 90% of the time, the desired page number was already in the TLB? Take into account that if the desired page number is missed from the cache, another memory access must be done (at 60 nsec per access) to get the frame number out of the page table. Assume that the TLB is always searched first, not in parallel with the page table in memory.
  1. Redo question 10 above, using 95% instead of 90%. How much faster is the average access time?