CSci 430: Introduction to Operating Systems

Assignment 4: Page Replacement Schemes, Clock AlgorithmCSci 430: Introduction to Operating SystemsFall 2019OverviewIn this assignment you will be implementing some pieces of a memory paging…

Assignment 4: Page Replacement Schemes, Clock AlgorithmCSci 430: Introduction to Operating SystemsFall 2019OverviewIn this assignment you will be implementing some pieces of a memory paging system simulator framework, and youwill be implementing a Clock page replacement algorithm. The simulator will allow you to take a stream of pagereferences, like we have done by had in our written assignments and in class, and simulate a physical memory of somenumber of frames, where placement and replacement decisions are made and the content of the physical memoryframes will change in response to the stream of page references being simulated.Questions• What are the basic steps an OS needs to perform in order to manage a paging memory system and makeplacement and replacement decisions?• What are the similarities in implementation between different page replacement algorithms? What are theirdifferences?• What information does a page replacement scheme need to keep track of to make a page replacement decision?• How does the clock page replacement scheme work? How is it implemented?• How does a clock scheme perform compared to a fifo scheme?Objectives• Implement a clock paging scheme by hand within a paging system simulator framework.• Look at use of C++ virtual classes and virtual class functions for defining an interface/API• Better understand how paging systems work, and in particular what information is needed to be tracked tomake page replacement decisions.DatesDue: Wednesday November 13, 2019IntroductionIn this assignment you will be implementing some pieces of a memory paging system simulator framework, and youwill be implementing a Clock page replacement algorithm. You will be given an implementation of the simple FIFOpage replacement scheme, described in chapter 8 of our textbook. You will be implementing a simple version of theClock page replacement scheme, using a normal frame pointer and a single use bit to approximate usage informationfor pages being used in the paging system.The paging system simulator framework consists of the following classes. There is a single class given in thePagingSystem.[hpp|cpp] source files that defines the framework of the paging system. This class handles the outlineof the algorithm needed for a paging system, and has methods to support loading files of page stream information, orto generate random page streams, to use in simulations. This class has a runSimulation() function that is the mainhook into the simulator. The basic algorithm of the paging simulator is to process each new page reference. For eachnew page reference, we first determine if the reference is a “hit” or a “fault”. If it is a hit, then nothing further needsto be done except to update any system usage statistics.For a page fault, the referenced page needs to be loaded into memory. When a page fault occurs, if memory is not yetfull, a simple placement decision is made (using the doPagePlacement() function). Page placement in this simulation1is simple, the first empty physical frame of memory will always be selected to place the new page reference into.When memory is full, a page replacement decision needs to be done first. The page replacement decision is handledby the doPageReplcement() and makeReplacementDecision() functions.However implementation of page replacement decisions are done by a separate helper class (called schemein the PagingSystem simulator). A abstract API/interface has been defined that describes how a page replacement scheme class is accessed and used. The abstract API/base class is defined in the files namedPageReplcementScheme.[hpp|cpp]. Most of the functions in this class are virtual functions, meaning that concretesubclasses must be created of this base class and implement those virtual functions. For the assignment you havebeen given a working FifoPageReplacementScheme.[hpp|cpp] concrete class that implements the simple FIFOpage replacement scheme. A class that can act as a PageReplacementScheme has the following interface. The mainfunction of such a class is the makeReplacementDecision() function. Whenever memory is full, the paging simulatorwill call this function to ask the page replacement scheme to select which frame of memory should be kicked out. Allsubclasses of the PageReplacementScheme base class need to implement an algorithm to be able to select the framefor page replacement when needed.The PageReplacementScheme API has a few other functions. The paging system simulator will call the schemewhenever a page hit occurs, because some page replacement schemes will update information about page usagebased on when or how often the page has been hit. Another major API function that the PageReplacementSchemesubclasses implement is the getSchemeStatus() function, which is called to get a snapshot of the current status ofthe replacement scheme, to get insight into its decision making process.There is a working FIFO page replacement implementation given already to you as part of the assignment. Yourmain task, after adding some functionality to the PagingSystem simulator class, will be to implement a basic Clockpage replacement scheme, which is a modification of the basic FIFO scheme.Unit Test TasksFor this assignment, you will first of all be completing some of the functions in the PagingSystem class to getthe basic simulator running. Then once the simulator is complete, you will be implementing the functions of theClockPageReplacmentScheme.[hpp|cpp] to create a Clock page replacement algorithm.So for this assignment, as usual, you should start by getting all of the unit tests to pass, and I strongly suggest youwork on implementing the functions and passing the tests in the given order. To get the simulator class completedyou will first need to complete the following tasks.1. The first test case of the unit tests this week simple tests the accessor methods of the PagingSystem class, andthe functions to load and generate simulated page streams. As a warmup exercise the get accessor methods ofthe PagingSystem class have been left unimplemented. You need to complete these functions to get the firsttest case working: getMemorySize(), getSystemTime() getNumPageReferences().2. The next function you need to implement, still used in the first test case, is the isMemoryFull() function. Thisfunction should return false if any of the frames of memory are an EMPTY_FRAME, and it will return true if allof the frames are non empty.3. The next function you need to implement is the isPageHit() information function. This function also returnsa boolean result. The current page being referenced in the simulation will be pageReference[systemTime],that is to say, given the current systemTime the page referenced at that time by the simulated page referencestream is found in the array pageReference[systemTime]. Given the current systemTime, the isPageHit()function should return true if the page being referenced is currently in memory (which is a page hit). Otherwiseit should return false.4. The final task you need to do to get the simulator working is to finish the doPagePlacement() function. Pageplacement happens whenever there are free frames of memory, so that we simply want to pick the next free frameto load the current referenced page into. The doPageReplacment() function has already been completed foryou, because it actually relies on calling the helper scheme instance to do the actual page replacement algorithm.For the doPagePlacement() function, you should first check if memory is full. Page placement should neverbe called if memory is full, so if memory is actually full you need to throw a SimulatorException(). But ifmemory is not full, you need to do the actual work of a page placement. For a page placement, you shouldsearch through memory and find the first frame that is an EMPTY_FRAME. Once found, this frame should bereplaced with the current page reference (e.g. pageReference[systemTime]).2Once these 4 tasks are complete, the first 5 test cases of this assignment should be passing. These test the simulator,load page streams, and test using the basic FIFO page replacement scheme to make page replacement decisions.However the final test Case 6 will not be working as it tests the Clock page replacement scheme class.So the next step is to implement a Clock page replacement policy. Most of the functions in the ClockPageReplacementScheme.[hpp|have been left for you to implement. However, many of the implementations of these functions will be similar to thesame functions given in the FifoPageReplacementScheme.[hpp|cpp] files.Perform the following tasks:1. You will need a framePointer for your clock scheme, just like the fifo page replacement scheme. But you willalso need to keep an array of use bits, 1 bit for each physical frame of memory. I recommend you use an arrayof int or an array of bool types for your use bits.2. You have been given the implementation of the constructor for your class. It works the same as the fifoclass, it simply calls the base class constructor, then calls the resetScheme() member function. As yoursecond task you should implement the resetScheme() class. You should initialize the framePointer like thefifo class does. But in addition, you need to dynamically create your array of use bits here. Subclasses ofthe PageReplacementScheme have a member variable named sys which is a pointer to an instance of thePagingSystem class that the scheme is working with. You can query the sys object for needed information.For example you can do sys->getMemorySize() to find out what the size of the simulated memory is. Thismay be useful because in addition to initialize the framePointer, you should dynamically allocate your array ofuse bits here to hold memorySize bits. And you should initialize all of the use bits to be 1 or true at this point,because after initial page placement, all of the use bits should initially be 1.3. Next implement the pageHit() member function. The fifo class doesn’t need to do anything for a page hit, butfor the Clock scheme, you should set the use bit to 1 for a page hit. When the pageHit() function is called, theframe number of the page that was hit is provided as the parameter, so you simply need to set the use bit ofthat corresponding frame to 1 to handle a page hit.4. Implement the makeReplacementDecision() function next. The replacement decision for clock is more complexthan for fifo. You have a framePointer, but you first need to scan memory until you find the next frame thathas a use bit set to 0. So if the frame that the frame pointer has a use bit of 1, you need to flip it to 0 andmove to the next frame. Thus you need to implement a loop here that keeps checking the use bit, and flippingit to 0 until it finds a use bit of 0. Once a frame is found with a use bit of 0 that should be the frame that isselected to be replaced. That frame number should be returned from this function. But before you return, youshould make sure that the framePointer points to the frame after the one that will be replaced. You shouldalso set the use bit of the frame that will be replaced to be 1, because whenever a new page is loaded its use bitshould initially be set to 1.5. If you get these 4 steps working correctly, you should now be able to pass all of the unit tests. However, thesystem tests will not pass yet until you implement the getSchemeStatus() function. This function is prettysimilar to the implementation of the fifo class, so you can start by copying the code from the fifo class for thisfunction to your clock class. The only difference is that the clock get scheme status function should display theuse bits for each frame of its output. So you will need to add code to show the use bit associated with eachframe to the output string returned. Once you get this output correct, your system tests should then passsuccessfully as well.System Tests: Putting it all TogetherOnce all of the unit tests are passing, you can begin working on the system tests.As with the previous assignment, the assg04-sim.cpp creates a sim program that uses command line argument to setup and run a simulation. The paging system simulator is invoked like this:$ ./simUsage: sim scheme memorySize pageref.simRun page replacement simulation on the given page referencestream file. Output shows the state of memory (loaded pagesin each memory frame) after each page reference as well assummary information about hit/miss performance. You canselect from different page replacement schemes by specifyingthe scheme parameter.3Options:scheme The page replacement scheme to use, current ‘fifo’and ‘clock’ are supportedmemorySize The number of physical frames of memory to simulatepageref.sim Filename with page references, one per line,that represent references to pages of a running(simulated) process or set of processesThe simulator requires 3 command line arguments to run. You first specify the page replacement scheme to use. Onlyfifo and clock will be supported at this point in implementing the assignment. The next parameter specifies the sizeof the memory that will be used in the simulation (in terms of the number of frames of physical memory available).The last parameter is the name of a file that contains a page reference stream that should be used for the simulation.As mentioned, if you correctly modify the getSchemeStatus() function to display the use bits for each frame inaddition to the other information, then you should be able to pass the given system tests for this assignment as well.Just add the use bit information you are keeping track for each frame of the system in the output.Extra Credit OpportunityIn this assignment you have been given a FIFO implementation, and if you were successful, you implemented aClock page replacement scheme. The other two page replacment schemes we study in this course are the leastrecently used (LRU) and optimal (OPT) schemes. If you are interested in this paging system simulation, and/orwould like an opportunity to make up some points for the class for previous assignments or tests, I will give upto 10 points each for a LRU and/or an OPT page replacement scheme implementation. You should start bysimply copying the FifoPageReplacementScheme.[hpp|cpp] files and renaming the class from that to for exampleLruPageReplacementScheme and OptPageReplacementScheme. Both of these schemes need to look at the history(or future references) of the page reference stream. So if you need to you can add an accessor method to return thepageReference array from the PagingSystem simulator so that these classes can access the page reference stream.For LRU, another approach is to use time stamps. You can just use the system time, and any time a page is loadedor is referenced (a hit) you update the time stamp. Then for LRU you would want to search your time stamps to findthe oldest time reference, which will be the least recently used page/frame, and select it for replacement.To get the full 10 points, make sure you also update PagingSystem so that the new scheme can be specified as apotential page replacement scheme. Also you need to add unit tests for your scheme, and most importantly, youshould add at least 1 or 2 system tests giving correct output/working of your replacement scheme. For example thepageref-01.sim page reference stream is the same as the one used for the examples in our book. So if you implementOPT or LRU you should get the same final result shown in the text if you use a simulation with 3 physical frames ofmemory.Assignment SubmissionIn order to document your work and have a definitive version you would like to grade, a MyLeoOnline submissionfolder has been created named Assignment-04 for this assignment. There is a target in your Makefile for theseassignments named submit. When your code is at a point that you think it is ready to submit, run the submit target:$ make submittar cvfz assg04.tar.gz PagingSystem.hpp PagingSystem.cpp ClockPageReplacementScheme.hpp ClockPageReplacemenPagingSystem.hppPagingSystem.cppClockPageReplacementScheme.hppClockPageReplacementScheme.cppThe result of this target is a tared and gziped (compressed) archive, named assg04.tar.gz for this assignment. Youshould upload this file archive to the submission folder to complete this assignment. I will probably be also directlylogging into your development server, to check out your work. But the submission of the files serves as documentationof your work, and as a checkpoint in case you keep making changes that might break something from when you had itworking initially.4Requirements and Grading RubricsProgram Execution, Output and Functional Requirements1. Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied.2. 20 pts all accessor methods implemented and first test case passes.3. 10 pts isMemoryFull() function works and passes test cases.4. 10 pts isPageHit() function is working and passing test cases.5. 10 pts doPagePlacement() function implemented as asked for. Function correctly selects first empty page andreplaces it when asked.6. 10 pts Have a good representation of the use bit defined for the clock page replacement class.7. 10 pts resetScheme() is implemented and correctly creates and initialize needed data structures for the clockalgorithm.8. 10 pts pageHit() function implemented and correctly updates use bit for frame when a page hit occurs.9. 15 pts makeReplacementDecision() implemented and working as asked for. Correctly uses use bit and clockalgorithm to select page and return it for replacement.10. 5 pts getSchemeStatus() added and working correctly, all system tests passing for the assignment.11. 10 bonus pts for a working LruPageReplacementScheme class.12. 10 bonus pts for a working OptPageReplacementScheme class.Program Style and DocumentationYour program must conform to the style and formatting guidelines given for this class. This semester things havebeen simplified to help you meet this requirement. Each assignment there are two make targets that help you checkthat you are meeting the coding style guidelines. You should run these tests periodically, and before you submit yourprogram for grading. The two targets are named style and dox. You would invoke them in this manner:$ make style# class style guidelines

# # # # # # # –style=allman –indent-spaces=2 –align-pointer=type –add-braces –convert-tabs Allman brace style, all opening { on line of their ownreplace all tabs with spaces, use 2 spaces for indentationAlign pointer and reference symbol with type declarationRequire that all one line block/conditionals have enclosing bracesConvert all tabs to spaces usiing current tab/space settings–max-code-length=100 Enforce max line length, we prefer no longer than 80 characters,but enforce <100

astyle –style=allman –indent=spaces=2 –align-pointer=type –add-braces –convert-tabs –max-code-length=100 –break-after-logical –recursive ./*.cpp,*.hpp,*.c,*.h————————————————————Directory ./*.cpp,*.hpp,*.c,*.h————————————————————Formatted ClockPageReplacementScheme.cppFormatted ClockPageReplacementScheme.hppFormatted FifoPageReplacementScheme.cppFormatted FifoPageReplacementScheme.hppFormatted PageReplacementScheme.cppFormatted PageReplacementScheme.hppFormatted PagingSystem.cppFormatted PagingSystem.hppFormatted assg04-sim.cppFormatted assg04-tests.cpp5$ make doxdoxygen Doxyfile 2>&1 | grep warning | grep -v “file statement” | grep -v “pagebreak” |sort -t: -k2 -n | sed -e “s|/home/dash/repos/os-sims/assgs/assg02/assg02/||g”The first target named style checks some general things about your code formatting and indentation. If it reportsthat all of your files remain unchanged, it means that your settings for your editor are in general correct, and yourcode indentation and spacing are ok. The style checker will not catch everything, you will still need to make sure youfollow guidelines for whitespace in your program, and laying out particular code elements. But at a minimum thestyle check should help you to conform to indentation and brace rules for the class projects.The second target check that you are documenting your code correctly. You need to provide documentation for reachof your functions. For this first assignment this was mostly already done for you, but in future assignment you mayneed to add new functions, and then you would need to document them correctly. If no information is reported fromthe make dox command, it means that your code probably has all of the necessary functions and other informationdocuments. If however it reports warnings about items not being documented:$ make doxdoxygen Doxyfile 2>&1 | grep warning | grep -v “file statement” | grep -v “pagebreak” |sort -t: -k2 -n | sed -e “s|/home/dash/repos/os-sims/assgs/assg02/assg02/||g”ProcessSimulator.cpp:32: warning: return type of member operator<< is not documentedProcessSimulator.hpp:39: warning: return type of member operator<< is not documentedthen you are missing documentation for some items. For all functions, at a minimum you need to document thefunction with a short description, document any input parameters into the function, and document the return valuefrom the function if it has one. In the above example, the @returns documentation for the operator<<() functionwas missing.6

Let’s block ads! (Why?)

Do you need any assistance with this question?
Send us your paper details now
We’ll find the best professional writer for you!

 



error: Content is protected !!