Problem 4: Virtual Memory

    (a) We are to design a simple (single level) page map
    (from virtual addresses to physical addresses) for a system
    with 32 bit address space and up to 2^24 bytes of physical memory.
    We are constrained to use no more than 2Mbyte of memory
    for the mapping table.  What is the smallest page size we
    can use in the design? (Assume that you can pack the bits
    into the mapping table memory without waste or padding).

    (b) To implement page replacement, we also need the inverse
    of the above table --- a mapping from physical addresses to
    virtual addresses.  How large is that table, based on the above
    design?

    (c) For the design above using the smallest possible page size,
    what is the largest physical memory we can handle using 2Mbyte
    of storage for the paging table?

    (d) A two-level page map for a system with a 32 bit address
    space uses pages of 1024 bytes.  The first level mapping table
    has to always be accessible. How large is it?

    (e) A paging system has space only for 4 user pages.
    Suppose that the user pages are accessed in the order
    0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, ...
    Using a FIFO replacement strategy, how many cache
    entries are replaced during each cycle of 8 page accessed,
    once steady state has been  reached?
    Repeat for the LRU replacement strategy.
    Does FIFO replacement or LRU replacement work better
    for this particular access pattern.

    (f) Repeat part (e) for the following access pattern:
    0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, ...