CSCI-GA.2250-001 Programming Assignment #3 (Lab 3): Virtual Memory Management

Description

In this lab/programming assignment you will implement/simulate the operation of an Operating System’s Virtual Memory Manager which maps the virtual address spaces of multiple processes onto physical frames using page table translation. The assignment will assume multiple processes, each with its own virtual address space of exactly 64 virtual pages (yes this is small compared to the 1M entries for a full 32-address architecture), but the principle counts. As the sum of all virtual pages in all virtual address spaces may exceed the number of physical frames of the simulated system, paging needs to be implemented. The number of physical page frames varies and is specified by a program option, you have to support up to 128 frames; tests will only use 128 or less. Implementation is to be done in C/C++. Please submit only your source and Makefile file via NYU classes. INPUT SPECIFICATION: The input to your program will be a comprised of: 1. the number of processes (processes are numbered starting from 0) 2. a specification for each process’ address space is comprised of i. the number of virtual memory areas / segments (aka VMAs) ii. specification for each said VMA comprised of 4 numbers: “starting_virtual_page ending_virtual_page write_protected[0/1] filemapped[0/1]” Following is a sample input with two processes. First line not starting with a ‘#’ is the number of processes. Processes in this sample have 2 and 3 VMAs, respectively. Note: ALL lines starting with ‘#’ must be ignored and are provided simply for documentation and readability. In particular, the first few lines are references that document how the input was created, though they are irrelevant to you. All provided inputs follow the format below, though number and location of lines with ‘#’ might vary. #process/vma/page reference generator # procs=2 #vmas=2 #inst=100 pages=64 %read=75.000000 lambda=1.000000 # holes=1 wprot=1 mmap=1 seed=19200 2 #### process 0 2 0 42 0 0 43 63 1 0 #### process 1 3 0 17 0 1 20 60 1 0 62 63 0 0 Since it is required that the VMAs of a single address space do not overlap, this property is guaranteed for all provided input files. However, there can potentially be holes between VMAs, which means that not all virtual pages of an address space are valid (i.e. assigned to a VMA). Each VMA is comprised of 4 numbers. start_vpage: end_vpage: (note the VMA has (end_vpage – start_vpage + 1) virtual pages ) write_protected: binary whether the VMA is write protected or not file_mapped: binary to indicate whether the VMA is mapped to a file or not The process specification is followed by a sequence of “instructions” and optional comment lines (see following example). An instruction line is comprised of a character (‘c’, ‘r’, ‘w’ or ‘e’) followed by a number. “c ”: specifies that a context switch to process # is to be performed. It is guaranteed that the first instruction will always be a context switch instruction, since you must have an active pagetable in the MMU (in real systems). “r ”: implies that a load/read operation is performed on virtual page of the currently running process. “w ”: implies that a store/write operation is performed on virtual page of the currently running process. “e ”: current process exits, we guarantee that is the current running proc, so you can ignore it. ##### example of an instruction sequence ###### c 0 r 32 w 9 r 0 r 20 r 12 You can assume that the input files are well formed as shown above, so fancy parsing is not required. Just make sure you take care of the ‘#’ comment lines. E.g. you can use sscanf(buf, “%d %d %d %d”,…) or stream >> var1 >> var2 >> var3. Programming Assignment #3 (Lab 3): Virtual Memory Management Professor Hubertus Franke Class CSCI-GA.2250-001 Spring 2021 Page 2 DATA STRUCTURES: To approach this assignment, read in the specification and create process objects, each with its array/vector/list of vmas and a page_table that represents the translations from virtual pages to physical frames for that process. A page table naturally must contain exactly 64 page table entries (PTE). Please use constants rather than hardcoding “64”. A PTE is comprised of the PRESENT/VALID, REFERENCED, MODIFIED, WRITE_PROTECT, and PAGEDOUT bits and the number of the physical frame (in case the pte is present). This information can and must be implemented as a single 32- bit value or as a bit structure (easier). It cannot be a structure of multiple integer values that collectively is larger than 32-bits. See http://www.cs.cf.ac.uk/Dave/C/node13.html (BitFields) or http://www.catonmat.net/blog/bit-hacks-header-file/ as an example, I highly encourage you to use the first technique, let the compiler do the hard work for you. Assuming that the maximum number of frames is 128, which equals 7 bits and the mentioned 5 bits above, you effectively have 32-12 = 20 bits for your own usage in the pagetable entry. You can use these bits at will (e.g. remembering whether a PTE is file mapped or not). What you can NOT do is run at the beginning of the program through the page table and mark each PTE with bits based on filemap or writeprotect. This is NOT how OSes do this due to hierarchical pagetable structures (not implemented in this lab though). You can only set those bits on the first page fault to that virtual page. You must define a global frame_table that each operating system maintains to describe the usage of each of its physical frames and where you maintain reverse mappings to the process and the vpage that maps a particular frame. Note, that in this assignment a frame can only be mapped by at most one PTE at a time, which simplifies things significantly. SIMULATION and IMPLEMENTATION: During each instruction you simulate the behavior of the hardware (shown below in blue) and hence you must check that the page is present. A special case are the ‘c’ (context switch) instruction which simply changes the current process and current page table pointer and the ‘e’ (process exit) instruction which exits a process. Structure of the simulation The basic structure of the simulation should be something like the following: typedef struct { … } pte_t; // can only be total of 32-bit size and will check on this typedef struct { … } frame_t; frame_t frame_table[MAX_FRAMES]; pte_t page_table[MAX_VPAGES]; // a per process array of fixed size=64 of pte_t not pte_t pointers ! class Pager { virtual frame_t* select_victim_frame() = 0; // virtual base class }; frame_t *get_frame() { frame_t *frame = allocate_frame_from_free_list(); if (frame == NULL) frame = THE_PAGER->select_victim_frame(); return frame; } while (get_next_instruction(&operation, &vpage)) { // handle special case of “c” and “e” instruction // now the real instructions for read and write pte_t *pte = &current_process.page_table[vpage];// in reality this is done by hardware if ( ! pte->present) { // this in reality generates the page fault exception and now you execute // verify this is actually a valid page in a vma if not raise error and next inst frame_t *newframe = get_frame(); //-> figure out if/what to do with old frame if it was mapped // see general outline in MM-slides under Lab3 header // see whether and how to bring in the content of the access page. } // check write protection // simulate instruction execution by hardware by updating the R/M PTE bits update_pte(read/modify) bits based on operations. } Programming Assignment #3 (Lab 3): Virtual Memory Management Professor Hubertus Franke Class CSCI-GA.2250-001 Spring 2021 Page 3 When accessing a page (“r” or “w”) and the page is not present, as indicated by the associated PTE’s valid/present bit, the hardware would raise a page fault exception. Here you just simulate this by calling your (operating system’s) pagefault handler. In the pgfault handler you first determine that the vpage can be accessed, i.e. it is part of one of the VMAs. Maybe you can find a faster way then searching each time the VMA list as long as it does not involve doing that before the instruction simulation (see above, hint you have free bits in the PTE). If not, a SEGV output line must be created and you move on to the next instruction. If it is part of a VMA then the page must be instantiated, i.e. a frame must be allocated, assigned to the PTE belonging to the vpage of this instruction (i.e. currentproc->pagetable[vpage].frame = allocated_frame ) and then populated with the proper content. The population depends whether this page was previously paged out (in which case the page must be brought back from the swap space (“IN”) or (“FIN” in case it is a memory mapped file). If the vpage was never swapped out and is not file mapped, then by definition it still has a zero filled content and you issue the “ZERO” output. That leaves the allocation of frames. All frames initially are in a free pool (use deque to get desired semantics). Once you run out of free frames, you must implement paging. We explore the implementation of several page replacement algorithms. Page replacement implies the identification of a victim frame according to the algorithm’s policy. This should be implemented as a derived class of a general Pager class with at least one virtual function “frame_t* select_victim_frame();” that returns a victim frame (or returns int for the frame number). Once a victim frame has been determined, the victim frame must be unmapped from its user (