At this point, we introduce the most complex portion of the Z502 simulator: the page translation hardware. Now you can (and must) implement virtual memory support in your operating system.
If users write programs with large address spaces, the availability of main memory can very quickly become the limiting factor keeping users from accessing the computer's resources. This is rather unfortunate, since programs rarely need access to all of their address space at the same time, and more effective use of the system could be made if processes could run with only part of their address space actually resident in physical memory. The technique that allows this to take place is called virtual memory. Under virtual memory, address spaces are divided into blocks called pages. Processes are allowed to run with only some of the pages in their address spaces actually resident in the physical computer memory. As long as they only reference the code and data that is resident, there is no problem. As soon as they reference a "virtual memory" location that is not resident in physical memory, the operating system must bring in the page that was referenced, replacing some other page if necessary. This operating system function is called paging, and a reference to a non-resident page is called a page fault.
Since physical memory is limited, we now begin using the paging mechanism to implement virtual address spaces that are larger than the physical memory they occupy. The mechanism used to accomplish this is called demand paging. Any page that is not resident in real memory is stored in auxiliary memory (disk) and the valid bit in the corresponding page table entry is cleared. If the process references this page in any way, a page, or invalid memory, fault occurs, with the virtual page number of the page that was referenced stored as the status.
In order to resolve a page fault, before allowing the process to re-execute the instruction, the operating system must:
Note: There are a number of subtle interactions between the demand paging mechanism and normal I/O. An I/O buffer may not have all of its pages memory resident. In this case, the operating system must simulate page faults in order to bring the pages into memory. Secondly, beware of stealing pages that are involved in a pending I/O operation. Remember that if the buffer spans a page boundary then the buffer may not be contiguous in physical memory, but must be if the I/O is to be performed in a single operation. Options include shuffling pages in memory or breaking the I/O operation up into several operations.
Numerous data structures are involved in supporting the demand paging mechanism. You should choose a reasonable page replacement policy and carefully design the data structures required to implement it efficiently.
The simplest page fetch algorithm is pure demand paging: a non-resident page is brought into memory only when a page fault occurs. Some operating systems use a prepaging algorithm; pages that are believed to be likely to be referenced are pre-fetched. Such a mechanism is not required for this project (but is an excellent extra-credit option).
A related issue arises with regard to the creation of new processes. At one extreme, it is possible to use an approach in which all pages are brought into memory at the time of process creation. This can be considered a crude form of prepaging. At the other extreme, it is possible to initiate a new process without any of its pages resident in memory. The process immediately begins to demand page the memory pages requested during execution. Intermediate approaches are also possible. You should discuss the advantages and disadvantages of whatever method you choose to implement.
You are free to implement any page replacement algorithm. However, you should be prepared to discuss the advantages and disadvantages of the method you choose.
The hardware mechanism that you have available to support your paging algorithm consists of the referenced bit and the changed bit in the page table entry. These bits are automatically set by the Z502 machine whenever a page is referenced or modified, respectively. You may also clear and set these bits within the operating system.
If your page replacement algorithm chooses a page that has not been modified in memory since it was last stored on auxiliary storage, it can be stolen by simply marking it as invalid in the corresponding page table entry. If it has been modified, then it must first be written out to auxiliary storage before it is available for the new page to be read in. This occurrence is not desirable, because it doubles the amount of time required to resolve a page fault. Some operating systems attempt to avoid this case by ensuring that a pool of unmodified pages always exists. Candidates for page stealing are taken preferably from this pool. The pool is maintained by periodically writing out modified pages to auxiliary storage, and then marking them as unmodified. Such a scheme is not required as part of the basic requirements.
Page tables are easy in our implementation. Allocate regular program memory for these, just as you've been allocating space all along. Remember, this structure has one element for each virtual page; each of these slots contains validity/modified information, as well as a pointer to physical memory. The OS502 reads and writes this structure, while the hardware only reads it. Thus both parties must agree on its contents; for this reason, the page table is a hardware-defined entity - see Appendix A, Section 8, for detailed information on this table.
There may also be a structure needed for "shadow page tables", known only to the Operating System. These structures are used to describe how to find a virtual page of memory when it's not in physical memory. Such a structure would hold disk information, for instance, indicating where to find the virtual contents should they need to be paged in.
The Page Tables we've just discussed are used to describe how the virtual memory for each process is assigned to physical memory. In a similar fashion, we need to provide descriptors for each of the physical pages on the machine; these are used only by the Operating System, and thus are not defined as part of the machine architecture.
The frame table indicates what pages are being shared among several processes, stores information about page usage, etc. Your implementation may survive without a Frame Table, or its equivalent, but it's not likely.
Generally, implementations of shared memory require some structures in addition to those necessary to hold page information. There needs to be some way of connecting the physical page to each of the virtual pages as seen by the number of processes that are sharing that page. The frame table is generally used as an anchor for a linked list of structures, each of which describes the physical to virtual mapping for an individual process.
You will need to write code to talk to the disk drives. Your goal in this project is very simple; move data back and forth between physical memory and the disk. To do this, you will need a number of structures to maintain the disk system.
You must maintain a record of what sectors on your disk are occupied; otherwise, you will try to allocate new information onto sectors that are already in use. Bit maps provide a simple what of doing this.
You may want to have a structure that defines for each sector, the data residing in that sector. However, this may be a duplication of what's in the Shadow Page Table.
There is no additional code provided for you beyond that in project 1. However, project 2 requires the use of the page table registers. These registers are named Z502_REG_PAGE_TBL_ADDR and Z502_REG_PAGE_TBL_LENGTH and are described in Appendix A.
In this project, you are required to implement a demand paging algorithm to support virtual memory and swapping. The minimum required implementation must include design, specification and implementation of:
As always, you are encouraged to choose a relatively simple method that works, and you need not feel obliged to resolve all issues in the best way.
Project Phase 2 also requires a fair amount of code. You could easily write several thousand lines of code. Naturally, we recommend an early start.