na
Final Project Write a Java or C/C++ (the choice is yours) program for a Demand Paging Simulator according to the following rules. The program will implement two Demand Paging algorithms: the classical OPT algorithm (described in the module 5 readings) and a NEW algorithm, described below. The application must simulate the execution the OPT and NEW algorithms on a hypothetical computer having only N physical frames (numbered from 0 to N-1; the maximum value for the parameter N is 8), assuming that the single process that is running has a virtual memory of ten pages (numbered from 0 to 9). The number N should be a number provided as an input for the algorithms, using the program menu. To clarify, the user should be able to run the OPT algorithm (for example) using the same reference string for a scenario where N is 4, then change N to 5 and run again, then change N to 6 and run again and in the end compare the results for each scenario. In other words, the number of physical frames should not be fixed (hardcoded) in the program, but rather considered as an input variable (parameter) for the implemented algorithms. The program requested for this project must have a text menu like this: 0 – Exit 1 – Input N 2 – Input the reference string 3 – Simulate the OPT algorithm 4 – Simulate the NEW algorithm Select option: The menu is displayed and the user must select an option (a number between 0 and 4). The action corresponding to the selection is performed, then the menu is displayed again and the user can choose another option. This cycle is repeated until the user selects 0, which exits the loop and ends the program execution. The options are: 0 – Exit This options ends the program execution. This option should always work. 1 – Input N The user is prompted for a [positive integer] number N. This is normally one of the first options that must be selected by the user. The number N must be at least 2 (otherwise the algorithms don’t make any sense) but should not be larger than 8; the program must verify these constraints and issue an error message whenever necessary. After performing several operations from the menu, the user should be able to select another N and work with the new N just as easily as before. 2 – Input the reference string The user is prompted for a series of [positive integer] numbers that will constitute the reference string. The maximum length of the reference string should be 20. This is normally one of the first options that must be selected by the user. The number of elements in the reference string must be at least N (otherwise the algorithms don’t make any sense) but should not be larger than 20; each element of the reference string must be an integer number between 0 and 9 (there are 10 virtual pages). The program must verify these constraints and issue an error message whenever necessary. After performing several operations from the menu, the user should be able to select another reference string and work with the new reference string just as easily as before. 3 – Simulate the OPT algorithm This option must first verify that a correct N and a correct reference string were already provided by the user; otherwise an error message should be issued and the program returns to the menu. If all the input data (N and the reference string) is available and correct, the simulation begins by printing the initial (empty) simulation table, for example: Reference String 3 1 6 2 1 3 7 3 2 1 5 4 2 3 7 2 1 Physical frame 0 Physical frame 1 Physical frame 2 Physical frame 3 Page Faults Victim pages Hint 1: Instead of the above reference string, the table will contain the ACTUAL reference string that was entered by the user; of course, everyone can use their reference strings for testing the correctness of the implementation. Using the reference strings from the readings to test your code is a great idea. Hint 2: Instead of having 4 physical frames in the simulation table, we must actually have N physical frames. So if the user has entered the value 6 for N using option 1 of the menu, then the simulation table should look like this: Reference String 3 1 6 2 1 3 7 3 2 1 5 4 2 3 7 2 1 Physical frame 0 Physical frame 1 Physical frame 2 Physical frame 3 Physical frame 4 Physical frame 5 Page Faults Victim pages Hint 3: Being a text only interface, clearly we cannot display such a nice table, but rather an approximation of it; the table could instead look like this or similar: The user must proceed with the STEP by STEP simulation of the OPT algorithm by pressing a key after each step of the algorithm; just as in the examples from the module 5 readings, each step of the simulation will fill a new column of the simulation table (previous steps must also be visible) and the table is re-printed on the screen after each step. This way, the user has an overview of all the previous steps and also of the current step. In the end, the table will be completely filled with information, and the user will have the complete view of the simulation. The total number of faults must also be displayed. In other words, the simulation must follow very closely the examples of Demand Paging algorithms from Module 5 of this course. Printing the explanations is optional. 4 – Simulate the NEW algorithm The simulation proceeds just like it did in option 4, but this time the algorithm is no longer the well known OPT algorithm, but a NEW algorithm. This NEW algorithm is a modified version of the LRU algorithm (LRU algorithm was discussed in Module 5 of this course). So how exactly does the NEW algorithm work? The NEW algorithm works just like the LRU algorithm with just one small change, regarding the policy for page replacement, when such an event occurs, and a page must be evicted and replaced with another page. In case of the LRU algorithm, the victim page is the one that has not been accessed, or used, for the longest period of time. Instead, in the NEW algorithm, the victim page is going to be the one that has not been accessed, or used, for the SECOND longest period of time. Consider the following example from the Module 5 LRU example, step 17: - Page 4: was referenced 5 steps ago - Page 3: was referenced 3 steps ago - Page 7: was referenced 2 steps ago - Page 2: was referenced 1 step ago The victim page for LRU is therefore page 4, because it was not accessed for the longest time. However, the victim page for NEW is page 3, because it was not accessed for the SECOND longest time. Testing procedure for one set of input parameters (N, reference string): 0. Option 0 requires just one screenshot, for successful exit. 1. Option 1 requires one screenshot for a correct input of N and one screenshot for an incorrect N. 2. Option 2 requires one screenshot for a correct input of a reference string and several screenshots for an incorrect reference string, as several errors are possible (incorrect element smaller than 0, incorrect element greater than 9, incorrect sequence length). 3. Option 3 requires screenshots showing the simulation of the OPT algorithm. Two screenshots will suffice: one showing the “middle” of the simulation (approximately) and another showing the end of the simulation (simulation table must be full with information). 4. Option 4 requires screenshots showing the simulation of the NEW algorithm. Two screenshots will suffice: one showing the “middle” of the simulation (approximately) and another showing the end of the simulation (simulation table must be full with information). Deliverables: 1. Source code (zipped) 2. A Test Report (called Test1.docx/Test1.pdf) showing the program performing each of the menu actions correctly (use the testing procedure described above, include all the required screenshots) for N=4 and the reference string from Homework 5. 3. A Test Report (called Test2.docx/Test2.pdf) showing the program performing each of the menu actions correctly (use the testing procedure described above, include all the required screenshots) for N=5 and the reference string from Homework 5. 2. A Test Report (called Test3.docx/Test3.pdf) showing the program performing each of the menu actions correctly (use the testing procedure described above, include all the required screenshots) for N=6 and the reference string from Homework 5.