CSE 120: Homework #3

Spring 2025

Due: Tuesday, May 20th at 11:59pm

  1. Nachos VM Worksheet   (We strongly recommend doing this worksheet before you start to work on part 2 of project 2.)

  2. When using physical addresses directly, there is no virtual to physical translation overhead. Assume it takes 100 nanoseconds to make a memory reference. If we used physical addresses directly, then all memory references will take 100 nanoseconds each.

    1. If we use virtual addresses with page tables to do the translation, then without a TLB we must first access the page table to get the approprate page table entry (PTE) for translating an address, do the translation, and then make a memory reference. Assume it also takes 100 nanoseconds to access the page table and do the translation. In this scheme, what is the effective memory reference time (time to access the page table + time to make the memory reference)?
    2. If we use a TLB, PTEs will be cached so that translation can happen as part of referencing memory. But, TLBs are very limited in size and cannot hold all PTEs, so not all memory references will hit in the TLB. Assume translation using the TLB adds no extra time and the TLB hit rate is 75%. What is the effective average memory reference time with this TLB?
    3. If we use a TLB that has a 99.5% hit rate, what is the effective average memory reference time now? (This hit rate is close to what TLBs typically achieve in practice.)

  3. Consider a 32-bit system (both virtual and physical addresses are 32 bits) with 1K pages (pages of size 1024 bytes) and simple single-level paging.
    1. With 1K pages (pages of size 1K), the offset is 10 bits. How many bits are in the virtual page number (VPN)?
    2. For a virtual address of 0xFFFF, what is the virtual page number?
    3. For a virtual address of 0xFFFF, what is the value of the offset?
    4. What is the physical address of the base of physical page number 0x4?
    5. If the virtual page for 0xFFFF is mapped to physical page number 0x4, what is the physical address corresponding to the virtual address 0xFFFF?

  4. [Crowley] Suppose we have a computer system with a 44-bit virtual address, page size of 64K, and 4 bytes per page table entry.
    1. How many pages are in a virtual address space? (Express using exponentiation.)
    2. Every process has its own page table, and every page table has a root page and many secondary pages. Suppose we arrange for each kind of page table page (root and secondary) to have the size of a single page frame. How will the bits of the address be divided up among the offset, index into a secondary page, and index into the root page?
    3. Suppose we have a 4 GB program such that the entire program and all necessary page tables (using two-level pages from above) are in memory. (Note: It will be a lot of memory.) How much memory, in page frames, is used by the program, including its page tables?

  5. [Crowley] Suppose we have an average of one page fault every 20,000,000 instructions, a normal instruction takes 2 nanoseconds, and a page fault causes the instruction to take an additional 10 milliseconds. What is the average instruction time, taking page faults into account? Redo the calculation assuming that a normal instruction takes 1 nanosecond instead of 2 nanoseconds.

  6. [Tanenbaum] If FIFO page replacement is used with four page frames and eight pages (numbered 0–7), how many page faults will occur with the reference pattern 427253323126 if the four frames are initially empty? Which pages are in memory at the end of the references? Repeat this problem for LRU.

  7. For each of the following actions, explain whether it will trigger a fault or not. If it will trigger a fault, briefly describe what kind of fault will occur (e.g., page fault, protection fault) and how the OS will handle it.

       a. A process accesses memory in a page that is currently swapped out to disk
       b. A process tries to dereference a NULL pointer (i.e., access memory at address 0x00)
       c. A process calls malloc
       d. A process calls a function, which pushes new variables onto the stack, extending beyond the current bounds of the stack
       e. A child process reads from a page that is shared with its parent using copy on write
       f. A child process writes to a page that is currently set to read-only due to copy on write

  8. [Silberschatz] Consider a demand-paging system with the following utilizations:

        CPU utilization: 20%
        Paging disk: 97.7% (demand, not storage)
        Other I/O devices: 5%

    For each of the following, say whether it will (or is likely to) improve CPU utilization. Briefly explain your answers.

       a. Install a faster CPU
       b. Install a bigger paging disk
       c. Increase the degree of multiprogramming
       d. Decrease the degree of multiprogramming
       e. Install more main memory
       f. Install a faster hard disk, or multiple controllers with multiple hard disks
       g. Add prefetching to the page replacement algorithms
       h. Increase the page size

    For (g), prefetching is an optimization that tries to anticipate near-future page accesses by loading pages from disk that the page replacement algorithm predicts will be accessed soon, but before those pages are actually accessed.