Current Pentium CPUs are capable of addressing more than 4GiB of memory. However, systems are often not configured with that quantity of actual memory.
And many users keep favorite applications resident in background windows ready to provide quick activation.
Virtual memory provides a mechanism by which a system can use limited amounts of non-contiguous real memory to represent a much larger virtual contiguous address space as long as this larger address space is addressable by the cpu.
The virtual memory mechanism divides the virtual memory address space into evenly sized pages and the real physical memory into frames of the same size. When a memory address mapped to one of the pages in virtual memory is accessed, a physical memory frame also linked or mapped to the virtual memory page providing actual memory.
The primary feature of virtual memory is the use of a table, called the page table, to track which physical page frame "contains" or is linked to a particular virtual page.
The page table contains 1 entry for each virtual address page. The number of entries in the page table is equal to the number of virtual pages in the address range of the system, size of virtual memory range divided by the size of a page.
Each page table entry has a 1 to 1 relation with a particular virtual address page, eg. page table slot 0 always handles the status of virtual page 0. Each page table entry has at least two fields, a present/absent flag indicating whether there is phyiscal memory present for that virtual page and the page frame id of physical memory where the virtual page resides if present.
The page frame id field must be large enough to specify any physical frame index or id.
A particular virtual page may be loaded into any one of the physical page frames and will function correctly.
For this assignment, you are working with a system that has 1K page frames, 4K of physical memory and 9K of virtual memory.
There is a program consisting of a driver block of code (Main), 5 subroutines, and 3 blocks of memory containing arrays of numbers. All are described below. Each of these units making up the program will be assigned to a specific virtual page. Each subroutine or array is 1K or 1 page in size. The virtual address of each part of the program and of each data array is provided.
You are to fill in the VM table contents and the real memory frame contents at various points during the execution of the program. A form containing blank VM tables and frames can be printed from a link below.
The following shows the layout of virtual memory when the program is running.
| Data | VM Page |
| net[] | 7K |
| activity[] | 6K |
| holding[] | 5K |
| Print() | 4K |
| Update() | 3K |
| Tax() | 2K |
| Load() | 1K |
| Main() | 0K |
Assume the following program is loaded and run. When 1st started, it will load the Main routine into a page frame in real memory. Assume the array references are pointers to the array data and the actual arrays do not need to be in real memory until they are acted on by an instruction.
Local variables in any module are part of that module's memory allocation and do not need additional page frames.
Description of what program does.
Pseudocode for each code module of program.
The numbered lines indicate when to describe the contents of the page table for the assignment. Work though the program three times.
You will simulate the virtual memory system once for each of the 3 following algorithms:
1st time, use First In First Out (FIFO) for selecting which page to page out when all physical page frames are full.
2nd time, use Least Recently Used (LRU) for selecting which page to page out when all physical page frames are full.
Assume the frames fill from 0 up as the program executes.
3th time, use "Smart Selection" - using your ability to look ahead to the next step, select which page to page out that will cause the least page faults later in the program. There may be cases where two equal candidates can be paged out, use fifo to select page. I was able to this in 13 faults.
Web pages with blank table tables and memory frames are provided below. For simplicity, our page table has one field per row. Use the area under the Faults column to record the index of the physical (real) page frame. For the assignment, recording a frame id will imply that it is present. Also, note the total number of page faults on the blank line at top of table.
When showing the state of the page table in the subroutines, show it after the subroutine is fully running (the pseudo-code indicates when a "snapshot" should be drawn). This guarantees all memory access in the routine to have occurred. At the top of each page instantiation, incude the number of faults that occured for that instance. Assume the swap out of the old page and the swap in of the new page is a single fault. If a second page needs to be swapped out, it is a separate fault.
Treat the transition from main to a subroutine (and visa versa) as immediate and a perfect fit. In other words, if you find that main is the most likely candidate to be paged out to make room for the subroutine, assume the system can remember what it is doing and let it page main out.
The declaration line defining the arrays will not cause them to exist. There existance in memory first occurs with the getmem calls in Allocate.
When an array is passed to a subroutine, assume that only its address is passed. The actual array does not have to be in physical memory until a command accesses it.
For example :
TArray[i] = Array1[i] + Array2[i]
The first time the statement is invoked, Array1[i] is referenced first, then Array2[i], and then, after they are added, TArray is referenced in order to store the result. So, if they are not already in physical memory, they will be paged in in that order. Keep in mind that the page of code containing this statement must also be in an actual frame to run.
After the 1st itteration, assuming there are enough physical frames, all three arrays and the block of code containing the calculation instruction (the loop) are now loaded in memory. In other words, this line of code requires 4 frames for all the information to be in real memory at the same time.
Depending on the current status of the frames and the swap algorithm, it is possible that the VM system could swap out TArray[] to make room for Array1[] or Array2[] and then have to swap TArray[] back in to record total.
Print out these web page for the table and frame templates. Print additional pages of the "Real memory frames" if needed.
VM Table 1.
VM Table 2.
Real memory frames.
Any time there is a change in the physical frame contents, write down the new list of virtual pages in the real memory frames.
Assume the VM system will initially fill the frames from the bottom (lowest address) first (even for the random swap selection).
You may use these abbreviations for the functions and data arrays on the frame page. M = main L = Load T = Tax U = Upate P = Print h = holding a = activity n = netEntries must be hand written. A printout will not be accepted. Also, number the tables, so that frame zero appears at the bottom of the table.
Hand in both the "VM Table" page and "Real memory frames" page or pages. Be sure to put your name and zid at top of all pages.