Programming Assignment Lab 3: Virtual Memory Management

You are to implement a Virtual Memory Manager in C or C++ and submit the source code, which we will compile and run. Please provide a Makefile to compile your code and submit as a single tar, tar.Z, tar.bz2, zip file through NYU classes. The name of the file should be your N_OS_lab3.

In this lab/programming assignment you will implement/simulate the virtual memory operations that map a virtual address space comprised of virtual pages onto physical page frames. As the size of the virtual address space may exceed the number of physical pages of the simulated system (#frames will be an input parameter) paging needs to be implemented. Only one virtual address space will be considered in this assignment. The size of the virtual space is 64 virtual pages. The number of physical page frames varies and is specified by an option, but assume you have to support 64 frames (but no more).

The input to your program will be a sequence of "instructions" and optional comment line (shown in Listing 1). A comment line anywhere in the input file starts with '#' and should be completely ignored by your program and not count towards the instruction count. An instruction line is comprised of two integers, where the first number indicates whether the instruction is a read (value=0) or a write (value=1) operation and which virtual page is touched by that operation. You can assume that the input files are well formed as shown below, so fancy parsing is not required (but verify the virtual page index falls within [0..63]).

You need to represent the virtual address space as a single level pagetable. There is only one process, hence only one address space, hence pagetable (just to make your life easiers).

Each page table entry (pte) is comprised of the PRESENT, MODIFIED, REFERENCED and PAGEDOUT bits and an index to the physical frame (in case the pte is present). This information can and should be implemented as a single 32Gbit value or as a bit structures (likely easier), but can not be a structure of multiple integer values that collectively are larger than 32Gbit. (see  http://www.cs.cf.ac.uk/Dave/C/node13.html (BitFields) or 

http://www.catonmat.net/blog/bitGhacksGheaderGfile/ as an example).

During each instruction you simulate the behavior of the hardware and hence you must check that the page is present and if not locate a free frame, pageGin the page if the PAGEDOUT flag is set to the frame or zero the frame. Then the virtual page of the instruction needs to be mapped to the frame. You must maintain the PRESENT (aka valid), MODIFIED, REFERENCED and PAGEDOUT bits and the frame index in the pagetable's pte. The frame table is NOT updated by the simulated hardware. Only the pagetable entry (pte) is updated just as in real operating systems and hardware.

Initially all page frames are maintained in a free list with frameG0 being the first frame in the list and all pte's of the pagetable are zero'd (i.e. NOT PRESENT and NOT PAGEDOUT).

The page replacement should be generic and the algorithms should be special instances of the page replacement class to avoid "switch/case statements" in the simulation of instructions. Think of using object oriented programming and inheritance.

When a virtual page is replaced it must be first unmapped and then optionally paged out. While you are not effectively implementing these operations you still need to track them and create entries in the output (see below).

In "Physical" you base your decision on the status of the physical frames. Since you need access to the pteGs (access to the ref and modify bits which are only maintained in the pagetable) you should keep track of the inverse mapping (frame G> pte). This structure is known as the operating system's frametable, namely one entry per physical frame.  In "Virtual", you base the replacement decision on the virtual pages.

Assignment link - https://www.dropbox.com/s/hbren2rsxehnofr/Lab%20Assignment.rar?dl=0