Background
The Max IV operating system on the MODCOMP IV (and CLASSIC) computers
used virtual memory only for protection and simplified storage allocation.
Each user process had its own address space that was viewed by the user
as a linear array of pages. Each page of the address space could be either
mapped to a page of real memory or unmapped, in which case, any reference
to the page would cause a trap. System services equivalent to the following
were available for use in user programs:
- map( va, r )
- If the page referenced by the address address va is unmapped,
allocate a page to it. Whether or not the page was previously mapped,
set the access rights for the addressed page to r. This service will
return true if a page can be allocated; otherwise it will return false and
it will have no effect on the caller's virtual address space. The available
access rights are read_only and read_write.
- unmap( va, r )
- If the page referenced by the address address va is mapped, unmap it and
deallocate the associated physical memory. If it is already unmapped, do
nothing.
- on_trap( save, handler )
- If any action of the current process causes a trap, save the visible
part of the process state in the indicated save area, and transfer control
to a trap handler at the indicated address.
- return_trap( save )
- Restore the process state to the state at the time of the trap.
The default trap handler for a process simply terminates the process. User
trap handlers use a trap save area with the following fields:
- cause = addr_fault indicates a memory addressing trap.
- cause = access_fault indicates an access rights violation.
- cause = fpu_fault indicates a floating point trap.
- cause = ... many others
- pc -- the virtual address of the instruction that caused the trap.
- va -- for address and access faults, the address that caused the trap.
- registers -- all the other CPU registers.
Also assume that the constants bytes_per_word and words_per_page are
available.
Your goal is to allow a user program to request that some part of its address
space be made virtual, using a disk file to provide backing storage for that
part of the address space. All code required for this service is to be
part of the user program. The user program will initiate this with a call to:
- make_virtual( va1, va2, fd )
- The range of addresses in the user's virtual address space from va1 to va2,
inclusive, will be mapped to the previously opened file fd, where fd is a file
descriptor suitable for use with the systems read and write services. Any
pages currently mapped in this range of pages may be written to corresponding
parts of the file, and any pages currently unmapped will be read from the
corresponding parts of the file.
The Problem:
Give detailed pseudocode for a user-level implementation of demand paged
virtual memory. No, that's too hard, so we'll break it into pieces:
Part A:
Give definitions for the functions needed to break a virtual address into
the component fields relevant to this problem and to construct a virtual
address from these component fields.
Part B:
What is the best choice of page replacement policy for this system? LRU
would be nice, but the system services you have available do not give
sufficient information for that.
Part C:
Give a detailed description of any data structures your code must maintain.
These would be initialized by make-virtual, if you bothered to write the code
for it (you are not to do so).
Part D:
Give detailed pseudocode for your user-level page fault handler; it should
use the data structures you outlined, and it should implement the policy
you selected.
Part E:
Given the code you wrote, and given that there are multiple processes running
the same code competing for a fixed pool of page frames in main memory, does
your code allow processes to share in a controlled manner or does it allow
a process to take and keep an unfair fraction of the page frames even though
it has a much smaller working set. If the former, how, if the latter, what
prevents fair sharing of page frames?