CS 3733 Operating Systems Assignment 3

Overview This assignment is on memory memory management, where we design a simulator that implements the OS's address translation mechanisms. Although an OS can usually support many processes, we only need to design a simulator that handles one process. The reference computing system for this assignment has the following properties: 1K physical memory, 4K virtual memory, and 128 bytes per page and frame. Before designing the simulator, you should understand the answers to the following questions: (1) What is the maximum number of pages a process can access? ( Answer: 32 pages ) (2) What is the total number of frames? ( Answer: 8 frames ) (3) How many entries does the pagetable contain? ( Answer: 32 entries ) You will practice the management of pagetable and physical memory allocation by emulating what happens inside the OS kernel. This assignment includes two parts, with a total of 60 points. There is an additional third part, worth 10 points, that is extra-credit. Part 1: Address Translation and I/O (20 points) Assume a process has the following page table: Create a directory called assign3 for this assignment. Under this directory, write a main program called part1.c that takes in only two parameter, infile, which is the name of a sequence file containing logical memory accesses, and outfile, which is the name of the file to which output is written to. Each logical address in infile is saved as 8 bytes (unsigned long) in binary format. Your program should read each logical address and then translate it into a corresponding physical address based on the pagetable given above. The physical addresses must be printed to the outfile, in the same binary format that the sequence file is in. The logical memory address is saved in a binary format. To verify that you can read in the correct sequence of memory accesses, you can first print out the address that you have analyzed. You can test your program with the given simple part1testsequence, where the first address should be 0x0000000000000044 and the second one should be 0x0000000000000224. For each logical address in the sequence file, you will use the pagetable given above to perform the address translation and generate a corresponding physical address that will be printed out to the file specified as the 2nd cmd-line parameter to part1.c. The outfile must have the same format as the given part1testsequence file. Each physical address must be written in binary as an 8 byte (unsigned long) value. Once you test your program with the part1testsequence, and you are sure the program performs correct address translation, use the following sequence file as the input file for logical addresses sequence to generate the translated physical addresses and put them in a file called part1-output. Then, compute the md5sum checksum on part1-output. Type the checksum for part1-output into REPORT.txt. note: to simplify Part 1, you can hardcode the mapping from page to frame into an array before performing any address translation. Part 2: Virtual Memory (40 points) In this part, you will design a page table and perform physical memory management. You will create two new source files for this part: phypages.c and pagetable.c, and a new main program named as part2.c, plus any necessary header files. Here, phypages.c is used to manage the physical pages and pagetable.c will manage the page table for the process. As implicitly assumed earlier, the first physical frame is reserved for the OS; the other frames are initially free. You will initially use the following frame allocation scheme: (1) allocate the physical page in order of frame number, starting from 1, 2, 3, .... (2) when there are no free physical frames, you will need to use the LRU policy for page replacement. That means, the page that is least recently used (accessed) will be allocated to the new request. Note that, once a frame is selected to be freed, you need to do two things: (1) First, you should invalidate the old entry of page table so that we don't have two virtual pages pointing to the same physical frame. (2) Second, you need to initialize a new pagetable entry (PTE) to point to the new frame. You may also want to set up a reverse mapping on the frame to the PTE for quick PTE modifications in the future. If a page is accessed, you must update its placement in the frame list so that it will not be evicted soon (based on the LRU policy). You should be able to utilize the same function in part 1 to map virtual addresses into physical addresses. Use this function for translating part2sequence into the output for part2-output. Similar to part 1, type the md5sum of part2-output into REPORT.txt along with the number of pagefaults encountered when translating part 2's logical addresses in physical addresses. Part 3: Making the design adaptive to any situation (10 points, extra credits) To get the bonus points, you should list whether you have implemented part 3 in your REPORT.txt file. Also, you should briefly explain how implementation of this part differs from previous two parts and why you think your implementation is correct. You need a main program named part3.c that must accept the following parameters: ./part3 BytesPerPage SizeOfVirtualMemory SizeOfPhysicalMemory SequenceFile OutputFile where the first parameter BytesPerPage specifies the number of bytes in each physical frame and virtual page. The second parameter SizeOfVirtualMemory is the size of virtual memory in bytes. The third one SizeOfPhysicalMemory is the size of physical memory in bytes. The fourth one SequenceFile is the name of the file that contains the sequence of logical addresses that need to be translated. The fifth one OutputFile is where the translated physical addresses are written. To test your program's Part 3 functions, you can use the parameters specified in "Part 2". Your program should generate the same output file as that in part2-output. In REPORT.txt, type why you think your implementation is correct. SUBMISSION: (1) All source files must be compilable into executables with the single make command. (2) All executables must be named as: part1, part2, etc. The names are, by convention, similar to the main program names except without the .c. (3) The code must be compressed as follows: go into your cs3733 and zip the directory assign3 into abc123-assign3.zip, where abc123 should be replaced with your abc123 ID. (4) You need to submit this single zip file through UTSA Learn. note: not following the submission requirements will result in a severe point deduction. GRADING: This assignment is worth 60 points +10 bonus. To receive full credit for this assignment, you must follow the submission guidelines above and submit it through BB. REPORT: Create a REPORT.txt file to answer the following questions: (1) List all of the people that you have collaborated with on this assignment. For each person indicate the level of collaboration (small, medium, large). Also write a few sentences describing what was discussed. Indicate whether you were mainly giving help or receiving help. (2) Do you think everything you did is correct? ..... (3) If not, give a brief description of what is working and what progress was made on the part that is not working. (4) Comments (e.g., what were the challenges, how to make this assignment more interesting etc.) (5) Program output: (if you print anything on the screen, then copy/paste it here. don't copy/paste output files here) Expected Output: The following are correct results. > ./part1 part1testsequence part1-out-test The LA is 44 and Translated PA is 144 The LA is 224 and Translated PA is 1a4 The LA is 168 and Translated PA is e8 The LA is 28c and Translated PA is 28c The LA is dc and Translated PA is 25c The LA is 234 and Translated PA is 1b4 The LA is 98 and Translated PA is 218 The LA is d0 and Translated PA is 250 total number of pages = 8 Part 1: > ./part1 part1sequence part1-output > md5sum part1-output ceabc02825a5b908e474b053074ab53c part1-output Part 2: > ./part2 part2sequence part2-output Part 2 page faults: 3210 > md5sum part2-out c95b27848ae8d4354d87678d075001f7 part2-output Part 3 : > ./part3 256 4096 1024 part2sequence part3-output Page faults: 3324 d34ec1b7d6aaa8d6eb093b9b95c8e094 part3-output > ./part3 128 4096 2048 part2sequence part3-output Page faults: 2132 eae769fd560d5e7940b9e0e5f593e7f8 part3-output

- pid fd - - - 6 9 8 7 6 5 4 3 2 5 3 7 7 6 5 4. 3 2 1 0 1 1 4 2 0 OS Page Table Physical Frames - pid fd - - - 6 9 8 7 6 5 4 3 2 5 3 7 7 6 5 4. 3 2 1 0 1 1 4 2 0 OS Page Table Physical Frames