Project 2 Solution

The goal of this project is to develop a memory management simulation. It must read files representing the process images of various processes, and simulate a set of virtual address references to those processes using one of two replacement strategies. It will then display various statistics, including number of memory accesses, page faults, and free frames remaining in the system.




Your project must be implemented in C++, and it must execute correctly on the Linux machines in the Alamode lab (BB136) that runs an Arch Linux or Ubuntu OS.




1 Simulation Constraints




The program will simulate memory management on a hypothetical computer system with the following attributes:




Pages and frames are both 64 bytes in size.



Main memory consists of 512 frames for a total of 32 kilobytes of storage.



Addresses are 16 bits long, with the ten most-significant bits representing the page or frame and the six least-significant bits representing the offset.



The maximum number of frames allocated to a process is static. Processes may be allocated frames until either reaching this limit or until the system runs out of free frames to allocate.



All frames in main memory are available for use by user processes; the OS does not occupy any memory (unlike in a real computer).



Page tables do not occupy main memory, and reading from a page table does not constitute a memory access (unlike in a real computer).



No TLB (translation lookaside buffer) exists (so you don't need to simulate one).



Processes exist for the entire duration of the simulation; if you've done the last memory access for a given process as specified in the file, it continues to occupy its current frames for the remainder of the simulation.



Segfaults (memory access faults) are fatal and should cause the simulation to exit immediately.
CSCI 442 Operating Systems, Assigned:







2 Simulation File Format




The simulation file specifies both the set of processes that are currently active in the system and the sequence of virtual addresses that should be accessed. Its format is as follows:




num_processes




process_id process_file




process_id process_file







// the process ID and its image file // another ID and image file, etc.



process_id virtual_address process_id virtual_address …




// PID of process, address being accessed // PID of process, address being accessed // etc.



Here's an example. Note that the files will not contain comments.




2


// 2 processes active in the system
10
process_1.txt
// process with PID
10
and file containing its image
42
process_2.txt
// process with PID
42
and file containing its image



10 0010000110011001
// process 10 accesses 0010000110011001
10 0010000110011010
// process 10 accesses 0010000110011010
10 0010000110011011
// process 10
accesses 0010000110011011
42 0110000110011001
// process 42
accesses 0110000110011001
42 0100000110011010
// process 42
accesses 0100000110011010
10 0010000110011001
// process 10
accesses 0010000110011001
…
// keep reading until EOF



The first line specifies the number of active processes in the system. You can use this value to control how many subsequent values you interpret as processes.




Each process contains both a process ID and a file that contains the data that should be used as its process image. The file should be assumed to be in binary format, though you can read each byte into a char​array.




The Canvas directory for Project 2 contains an example simulation file as well as a few dummy process images under the ​inputs/​directory.




3 Command Line Flags




Your simulation must support invocation in the format specified below, including the following command line flags:




./mem-sim [flags] simulation_file.txt
CSCI 442 Operating Systems, Assigned:










-v, --verbose




Output information about every memory access.




-s, --strategy (FIFO|LRU)




The replacement strategy to use, either FIFO or LRU.




-f, --max-frames <positive integer




The maximum number of frames a process may be allocated.




-h, --help




Display a help message about these flags and exit.




You may (but are not required to) use the ​get_opt_long(3)​method for parsing these flags. As always, check the ​man​page for additional information.




--verbose




The output required for the ​--verbose​flag is described in the next section, along with output expected when it's not set.




--strategy (FIFO|LRU)




This flag determines the replacement strategy that your simulation must use when either a process has been allocated the maximum number of frames (determined by ​--max-frames​)or the system has no free frames available. If the flag is not provided, default to FIFO.




--max-frames <positive integer




This flag requires a positive integer argument and specifies the maximum number of frames that can be allocated to a single process, assuming the system still has free frames available. If a process already has this number of frames, or the system has no more free frames to spare, you must replace one of the process' other pages using the replacement strategy specified by ​--strategy​to bring in a new page. You will also need to vary this parameter to correctly demonstrate Belady's anomaly. If the flag is not provided, it should default to 10.




--help




Finally, the ​--help​flag must cause your program to print out instructions for how to run your program and about the flags it accepts and then immediately exit.

CSCI 442 Operating Systems, Assigned:







4 Required Output and Format




Regardless of the flags a user passes, your simulation must output the following information:




The total number of memory accesses



The total number of page faults



The number of free frames remaining



For each process:



Total number of memory accesses



Total number of page faults



The percent of memory accesses that caused a page fault



The resident set size of the process at the end of the simulation



If the ​-v​or ​--verbose​flag is set, your program must also output information about each memory reference. The required information is as follows:




The ID of the process making the memory reference



The virtual address being referenced



Whether the memory access resulted in a page fault or not



The physical address corresponding to the virtual address



The process' current resident set size (RSS)






5 Replacement Strategies




Your memory management simulation must support two different page-replacement strategies: FIFO and LRU. Which strategy to use should be provided as a command-line flag, as follows:




First-In, First-Out (​--strategy FIFO​)
Least Recently Used (​--strategy LRU​)



If the flag is not provided, your simulation should default to using FIFO.




Both of these strategies should be implemented as they are described in your textbook. While LRU is not feasible to implement in real operating systems, your simulation has no such problem! You are free to keep track of whatever data you need to implement the two required strategies, regardless of how feasible the collection of that data would be in a real OS.

CSCI 442 Operating Systems, Assigned:







6 Getting Started




Related materials, including example inputs and starter code/unit tests, are posted on the course Canvas. Please attend lecture on 04/04 for an overview of the project and suggestions on getting started from the TAs.




You may opt not to use the provided starter code, but if you choose not to, you must implement a comparable set of unit tests that can be run using ​make test​and ensure they all pass. In addition, the starter code has been tested on Linux machines only; if you want to use the starter code on another OS, it is your responsibility to modify and run the code accordingly.




The starter code already has a makefile that builds everything under the ​src/​directory, placing temporary files in a ​bin/​and the program itself (named ​mem-sim​by default) in the root of the repository. It also includes a ​make test​target that will automatically build all ​*_tests.cpp​files placed anywhere under the ​src/​directory.




It has numerous classes declared that attempt to model the various concepts in memory management you'll need. Most are located in subdirectories of the ​src/​directory. Your first task should be to skim through these files to get a handle on what is provided for you.




Your next step should be implementing the lowest-level classes, since the implementation of the other classes typically depends on these. Both ​PhysicalAddress​and ​VirtualAddress​are good places to start.




All methods that are declared in a header file have a stub implementation in their corresponding .​cpp files. Most of these have unit tests already written for them, and you will be required to implement the function stubs such that all the tests pass. You are free to add additional methods and unit tests however you see fit.




To run the tests, run the following from within your repository:




make test




Most of them will fail until you implement the corresponding functionality.




7 Requirements and Reference




Use good design. Do not code monolithic functions. You should avoid coding practices that make for fragile, rigid, and redundant code.



Use good formatting skills. A well-formatted project will not only be easier to work in and debug, but it will also make for a happier grader and a happier grader gives higher grades.
CSCI 442 Operating Systems, Assigned:







You can develop your project anywhere you want, but it must execute correctly on the machines in the Alamode lab (BB136).



Your final submission must contain a README file with the following information:



Your name



A list of all the files in your submission and what each does



Any unusual/interesting features in your program



Approximate number of hours you spent on the project



A couple of paragraphs that explain what Belady's anomaly is and how to use your example input file to demonstrate its effects. Be sure to:



Define Belady's anomaly.



Give the command line invocations that should be used to demonstrate the anomaly with your program.



Attempt to explain why the anomaly occurs



To compile your code, the grader should be able to ​cd​into your code directory and simply type make​.



8 Deliverables




You are required to submit each deliverable by 11:59pm on the due date. The submission port will be automatically closed at 12:05am.




All deliverables must be submitted to Canvas. Any requirements not mentioned in an intermediate deliverable are due as part of the final deliverable.




8.1 Intermediate Deliverable 1: Due April 17, 2019 @ 11:59pm




You must submit a version of your code where:




All unit tests in the starter code pass when running ​make test​.
Your program reads a simulation file in the required format and prints:



The size of each specified process in bytes



Each of the virtual addresses the file contains



Zip or tar all your files into a single file with the name:




CanvasUserName-D1.zip​(or .​tar​)




Replace CanvasUserName with your real username. Submit this single file to Canvas.

CSCI 442 Operating Systems, Assigned:







8.2 Final Deliverable: Due April 26/May 1, 2019 @ 11:59pm




You are encouraged to submit by ​Friday April 26​,but if you need the additional time, submissions will remain open until 11:59pm May 1 and there will be no penalty for "late" submissions. Consider this a preemptive extension; be aware that ​no additional extensions will be granted​.




You must submit a completed version of your program where:




The replacement strategy can be specified using the ​--strategy​flag (either FIFO or LRU).
The maximum number of frames a process may use is configurable using the ​--max-frames flag.



All required information is present in your output.



Details about individual memory accesses are correctly displayed when the ​--verbose​flag is set.



An input file that clearly demonstrates Belady's anomaly when using FIFO is present.



The README file contains all requested information.



Zip or tar all your files into a single file with the name:




CanvasUserName-Final.zip​(or .​tar​)




Replace CanvasUserName with your real username. Submit this single file to Canvas.