CS 3733 Operating Systems Assignment 3

Overview
This assignment is on 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.



At the end of this page, I have sample outputs and links for extra help videos, please watch them first!



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. So we can run it as

> part1 infile outfile

Each logical address in infile is saved as 8 bytes (unsigned long) in binary format. So don't open it with a text editor because the content will look like garbage. Instead, your program should open the file in binary format and read each logical address into an unsigned int variable. To verify that you read the correct sequence of memory accesses, you can first print out the logical address that you have read. You can test your program with the given simple part1testsequence, where the first logical address should be 0x0000000000000044 and the second one should be 0x0000000000000224. When printing it use "%lx" format specifier. But the leading 0's will not be seen, so you may see 44 and 224 in HEX format. But 0's are in the memory (see the help videos at the end for more explanation)!


For each logical address in the input sequence file, you will use the pagetable given in the above figure to perform the address translation and generate a corresponding physical address that will be printed out into the file specified as the 2nd cmd-line parameter to part1.c.

 Your program need to translate each logical address in the intput file to a corresponding physical address using the static page table (PT) given in the above figure, and print out each phsical address into the file specified as the 2nd cmd-line parameter. The outfile must have the same format as the given part1testsequence file. So, each physical address must be written in binary as an 8 byte (unsigned long) value into the output file. Note: you need to hard code the above page table with the given frame numbers as int PT[8]={2, 4, 1, 7, 3, 5, 6, -1}; Then you can use this table to translate a given logical address into a  physical addresses and print it into the outfile using the same binary format of input file (i.e., represent each physical address as  unsigned int, too).

 

Once you test your program with the part1testsequence, and you are sure the program performs correct address translation (see the sample output at the end), use the following sequence file as the input file for logical addresses sequence to generate the translated physical addresses and put them into a file called part1-output. Then, compute the md5sum checksum on part1-output. Type the checksum for part1-output into REPORT.txt. Then you can delete  part1-output. Note: the md5sum checksum program computes a magic number whihc we can use to determine if you genarated the same output file or not without actually receiving your output file. Please google md5sum to learn more about it.

Note: to simplify Part 1, we asked you to hardcode page table so you can easily map page numbers to frame numbers when  performing any address translation. In the next part, you will dynamically fill the page table!



Part 2: Virtual Memory (40 points)
In this part, you will dynamically manage the page table and perform logical to physical memory translations along with a page replacement algorithm. For this part, create a new source file part2.c.

Now your page table should be an array of page table entry (PTE) structure with at least two fields: a valid-bit and frame-number. Initially all valid-bit fields should be set to 0. Also all frames are initially free except frame 0, which is allocated for OS. So you may also need an array to keep track of which frame is free and  which frame is allocated. Then the program reads a logical address and finds the page number. It then checks the valid-bit of the corresponding PTE. If it is 1, we can easily utilize the same functions from part 1 to map this logical (virtual) addresses into a physical address. If not, the program needs to find an available frame for this page and update its PTE (i.e., set valid-bit to 1 and store the frame numer of the allocated frame into frame-number field). 

 

You will initially use the following frame allocation scheme:  allocate the physical frames in the order of 1, 2, 3, ....

But,  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 removed and the frame holding it will be allocated for the new page.

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 allocated frame. You should also set up a reverse mapping on the frame to the PTE for quick PTE modifications in the future when a frame is re-allocated.

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).

Watch the help videos at the and for more information about implementation details.

The run your program for translating part2sequence into the output for part2-output.

As in part 1, type the md5sum of part2-output into REPORT.txt along with the number of pagefaults encountered when part 2 is translating logical addresses to 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. 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 compliable into executables with the single make command.
(2) All executables must be named as: part1, part2, part3. 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

EXTRA HELP VIDEOS

Assign03-part1-help: Watch tk07-assign03-help-for-part1-15min

In the help video (13:00), I wrote PA = fnum << d + dnum; Actually, I should have written  PA = (fnum << d) + dnum; or PA = fnum << d | dnum;

In the help video, I used printf("%lx ", PA);  Actually you should also use printf("%lx", LA); to see what you read from the input file: the first two values of LA are 44 and 224 in HEX. I got some questions that even though unsigned long is 8 bytes you don't see leading 0's. Actually, in computer's memory, LA and PA oocupy 8-byte space and hold all the leadign 0's. So, you don't need to do anything. Just look at LA and PA as a 64-bit binary numbers! Also we read/write them from/to files in binary format, so all 8 bytes will be in the files as well. However, printf ignores these leading 0's; but don't worry about that because we just use it to show the values for us. If you like to see all leading 0's then use the following printfs: printf("%016lx\n", LA); ... printf("%016lx\n", PA);

Also I did not include error checkings. You should check what the I/O functions return.. For example, it is a good idea to use  if(fread(&LA, sizeof(unsigned long), 1, fp) != 1) break; instead of just fread(&LA, sizeof(unsigned long), 1, fp);

Assign03-part2-help: Watch tk08-assign03-help-for-part2-26min

Clarification: you need to initially set all valid/invalid values in page table to 0 as I described in the video. But, when writing the code (12:50), I did not write this initialization step and just started with fopen... I was expecting you to take care of initialization step! So simply set all valid/invalid values to 0 before fopen...