CS计算机代考程序代写 data structure c/c++ compiler algorithm Programming Assignment #3 (Lab 3): Virtual Memory Management Professor Hubertus Franke

(“UNMAP”), however you must inspect the state of the R and M bits. If the page was modified, then the page frame must be

paged out to the swap device (“OUT”) or in case it was file mapped it has to be written back to the file (“FOUT”). Now the

frame can be reused for the faulting instruction. First the PTE must be reset (note once the PAGEDOUT flag is set it will

never be reset as it indicates there is content on the swap device) and then the PTE’s frame must be set and the valid bit can

be set.

At this point it is guaranteed, that the vpage is backed by a frame and the instruction can proceed in hardware (with the

exception of the SEGV case above) and you have to set the REFERENCED and MODIFIED bits based on the operation. In

case the instruction is a write operation and the PTE’s write protect bit is set (which it inherited from the VMA it belongs to)

then a SEGPROT output line is to be generated. The page is considered referenced but not modified in this case.

Your code must actively maintain the PRESENT (aka valid), MODIFIED, REFERENCED, and PAGEDOUT bits and the

frame index in the pagetable’s pte. The frame table is NOT updated by the simulated hardware as hardware has no access to

the frame table. Only the pagetable entry (pte) is updated just as in real operating systems and hardware. The frame table can

only be accessed as part of the “simulated page fault handler” ( see code above ).

The following page replacement algorithms are to be implemented (letter indicates program option (see below)):

Algorithm Based on

Physical Frames

FIFO F

Random R

Clock C

Enhanced Second Chance / NRU E

Aging A

Working Set W

The page replacement code should be generic and the algorithms should be special instances of the page replacement class to

avoid “switch/case statements” in the simulation of instructions. Use object oriented programming and inheritance.

Since all replacement algorithms are based on frames, i.e. you are looping through the entire or parts of the frame table, and

the reference and modified bits are only maintained in the page tables of processes, you need access to the PTEs. To be able

to do that you should keep track of the reverse mapping from frame to PTE that is using it. Provide this reverse mapping

(frame ⇛ ) inside each frame’s frame table entry. Each time you do a MAP from vpage->frame also create
the reverse mapping from frame->vpage and similar break them when you do an UNMAP.

Note (again): you MUST NOT set any bits in the PTE before instruction simulation start, i.e. the pte (i.e. all bits) should be

initialized to “0” before the instruction simulation starts. This is also true for assigning FILE or WRITEPROTECT bits from

the VMA. This is to ensure that in real OSs the full page table (hierarchical) is created on demand; on the first page fault on

a particular pte, you have to search the vaddr in the VMA list. At that point you can store bits in the pte based on what you

found in the VMA and what bits are not occupied by the mandatory bits (remember you have ~20 bits free here).

Programming Assignment #3 (Lab 3): Virtual Memory Management Professor Hubertus Franke
Class CSCI-GA.2250-001 Summer 2021 Page 4

You are to create the following output if requested by an option (see at options description and set of options we grade with):

49: ==> r 4

UNMAP 1:42

OUT

IN

MAP 26

Output 1

69: ==> r 37

UNMAP 0:35

FIN

MAP 18

Output 2

75: ==> w 57

UNMAP 2:58

ZERO

MAP 17

Output 3

For instance, in Output 1 instruction 49 is a read operation on virtual page 4 of the current process. The replacement

algorithms selected physical frame 26 that was used by virtual page 42 of process 1 (1:42) and hence first has to UNMAP the

virtual page 42 of process 1 to avoid further access. Then because the page was dirty (modified) (this would have been

tracked in the PTE) it pages the page OUT to a swap device with the (1:26) tag so the Operating system can find it later when

process 1 references vpage 42 again (note you don’t implement the lookup). Then it pages IN the previously swapped out

content of virtual page 4 of the current process (note this is where the OS would use tag to find the

swapped out page) into the physical frame 26, and finally maps it which makes the PTE_4 a valid/present entry and allows

the access. Similarly, in output 2 a read operation is performed on virtual page 37. The replacement selects frame 18 that was

mapped by process_0’s vpage=35. The page is not paged out, which indicates that it was not dirty/modified since the last

mapping. The virtual page 37 is read from file (FIN) into physical frame 18 (implies it is file mapped) and finally mapped

(MAP). In output 3 you see that frame 17 was selected forcing the unmapping of its current user process_2, vpage 58, the

frame is zeroed, which indicates that the page was never paged out or written back to file (though it might have been

unmapped previously see output 2). An operating system must zero pages on first access (unless filemapped) to guarantee

consistent behavior. For filemapped virtual pages (i.e. part of filemapped VMA)\ even the initial content must be loaded from

file.

In addition, your program needs to compute and print the summary statistics related to the VMM if requested by an option.

This means it needs to track the number of segv, segprot, unmap, map, pageins (IN, FIN), pageouts (OUT, FOUT), and zero

operations for each process and instructions, process exits, context switches globally. You have to compute the overall

execution time in cycles, where the cost of operations (in terms of cycles) are as follows:

read/write (load/store) instructions count as 1, context_switches instructions=130, process exits instructions=1250.

In addition if the following operations counts as follows:

maps=300, unmaps=400, ins=3100, outs=2700, fins=2800, fouts=2400, zeros=140, segv=340, segprot=420

Per process output:
printf(“PROC[%d]: U=%lu M=%lu I=%lu O=%lu FI=%lu FO=%lu Z=%lu SV=%lu SP=%lu\n”,

proc->pid,

pstats->unmaps, pstats->maps, pstats->ins, pstats->outs,

pstats->fins, pstats->fouts, pstats->zeros,

pstats->segv, pstats->segprot);

Summary output:
printf(“TOTALCOST %lu %lu %lu %llu %lu\n”,

inst_count, ctx_switches, process_exits, cost, sizeof(pte_t));

If requested by an option you have to print the relevant content of the page table of each process and the frame table.

PT[0]: * 1:RM- * * * 5:-M- * * 8:— * * # * * * * * * * * # * * * 24:— * * * # * * * * * *

* * * # * * * * * * * * * # * * # * * * # * * * * * * * *

FT: 0:1 0:5 0:24 0:8

PROC[0]: U=25 M=29 I=1 O=8 FI=0 FO=0 Z=28 SV=0 SP=0

TOTALCOST 31 1 0 52951 4

Note, the total cost calculation can overrun 2^32 and you must account for that, so use 64-bit counters (unsigned long

long). We will test your program with 1 million instructions. Also, the end calculations are tricky, so do them incrementally.

If you use individual 32-bit counters, don’t add up 32-bit numbers all at once and then assign to 64-bit, this will result in

overflows. Add 32-bit numbers incrementally to the 64-bit counters.

Programming Assignment #3 (Lab 3): Virtual Memory Management Professor Hubertus Franke
Class CSCI-GA.2250-001 Summer 2021 Page 5

Execution and Invocation Format:

Your program must follow the following invocation:

./mmu –f -a [-o] inputfile randomfile (arguments can be in any order → getopt()).

e.g. ./mmu -f4 -ac –oOPFS infile rfile selects the Clock Algorithm and creates output for operations, final page

table content and final frame table content and summary line (see above). The outputs should be generated in that order if

specified in the option string regardless how the order appears in the option string. We will grade the program with “–

oOPFS” options (see below), run with varying page frame numbers and “diff” compare it to the expected output.

Test input files and the file with random numbers are supplied (same as lab2). The random file is required for the Random

algorithm. Please reuse the code you have written for lab2, but note the difference in the modulo function which now indexes

into [ 0, size ) vs previously ( 0, size ]. In the Random replacement algorithm you compute the frame selected as with

(size==num_frames). As in the lab2 case, you increase the rofs and wrap around on overflow.

• The ‘O’ (ooooh nooooh) option shall generate the required output as shown in output-1/3.

• The ‘P’ (pagetable option) should print after the execution of all instructions the state of the pagetable:
As a single line for each process, you print the content of the pagetable pte entries as follows (shown for process 0).

PT[0]: 0:RMS 1:RMS 2:RMS 3:R-S 4:R-S 5:RMS 6:R-S 7:R-S 8:RMS 9:R-S 10:RMS

11:R-S 12:R– 13:RM- # # 16:R– 17:R-S # # 20:R– # 22:R-S 23:RM- 24:RMS # #

27:R-S 28:RMS # # # # # 34:R-S 35:R-S # 37:RM- 38:R-S * # 41:R– # 43:RMS

44:RMS # 46:R-S * * # * * * # 54:R-S # * * 58:RM- * * # * *

R (referenced), M (modified), S (swapped out) (note we don’t show the write protection bit as it is implied/inherited

from the specified VMA.

PTEs that are not valid are represented by a ‘#’ if they have been swapped out (note you don’t have to swap out a

page if it was only referenced but not modified), or a ‘*’ if it does not have a swap area associated with. Otherwise

(valid) indicates the virtual page index and RMS bits with ‘-‘ indicated that that bit is not set.

Note a virtual page, that was once referenced, but was not modified and then is selected by the replacement

algorithm, does not have to be paged out (by definition all content must still be ZERO) and can transition to ‘*’.

• The ‘F’ (frame table option) should print after the execution and should show which frame is mapped at the end to
which or ‘*’ if not currently mapped by any virtual page.

FT: 0:32 0:42 0:4 1:8 * 0:39 0:3 0:44 1:19 0:29 1:61 * 1:58 0:6 0:27 1:34

• The ‘S’ option prints the summary line (“TOTALCOST …”) described above.

• The ‘x’ option prints the current page table after each instructions (see example outputs) and this should help you
significantly to track down bugs and transitions (remember you write the print function only once)

• The ‘y’ option is like ‘x’ but prints the page table of all processes instead.

• The ‘f’ option prints the frame table after each instruction.

• The ‘a’ option prints additional “aging” information during victim_selection and after each instruction for complex
algorithms (not all algorithms have the details described in more detail below)

We will not test or use the ‘-f’ ,’-a’ or the ‘-x,-y’ options during the grading. It is purely for your benefit to add these

and compare with the reference program under ~frankeh/Public/mmu on any assigned cims machines.

(Note only a max of 10 processes and 8 VMAs per process are supported in the reference program which means

that is the max we test with).

All scanning replacement algorithm typically continue with the frame_index + 1 of the last selected victim frame.

Please note again: you have to provide a modular design which separates the simulation (instruction by instruction) from the

replacement policies. Use OO style of programming and think about what operations you need from a generic page

replacement (which will define the API). A lack of doing a modular design with separated replacement policies and

simulation will lead to a deduction of 5pts. Initializing the PTE before instruction simulation to anything but “0” will cost

another 5 pts, because it is so fundamentally different then OSs work. Another 3pts for not printing the real size of pte_t

from your program which must show “4” indicating your pte indeed is 32bit.

Programming Assignment #3 (Lab 3): Virtual Memory Management Professor Hubertus Franke
Class CSCI-GA.2250-001 Summer 2021 Page 6

FAQ: ( and lots of debugging help by the reference program )

FIFO we are not implementing a strict FIFO due to the intricacies of the free pool (see get_next_frame()) where on process

exit frames will be returned and have to be used first again before calling the select_victim_frame() function. So please

simply use a “hand” (read index into the frame table) that is incremented each time (don’t forget wraparound) you pick

another victim_frame. Then this can be also expanded to do the clock algorithm by simply dealing with referenced frames

and resetting the R bit. The option “-oa” will produce ASELECT: 5 where the number indicates where the hands starts.

CLOCK See above: implement as the derivative of the FIFO implementation.

The option “-oa” will produce ASELECT: 5 15 where the first number indicates where the hands starts and the 2nd

number indicates how many frames where inspected to finally find one where the reference bit = 0 .

ESC/NRU requires that the REFERENCED-bit be periodically reset for all valid page table entries. The book suggests on

every timer cycle which is way too often. Typically this is done at periodic times using a daemon. We simulate the periodic

time inside the select_victim_frame function. If 50 or more instructions have passed since the last time the reference bits

were reset, then the reference bit of the pte’s reached by the frame traversal should be cleared after you considered the class

of that frame/page. Also in the algorithm you only have to remember the first frame that falls into each class as it would be

the one picked for that class. Naturally, when a frame for class-0 (R=0,M=0) is encountered, you should stop the scan, unless

the reference bits need to be reset, at which point you continue to scan all frames. Once a victim frame is determined, the

hand is set to the next position after the victim frame for the next select_victim_frame() invocation. Try to walk the

frametable only once using Booleans.

The “-oa” option will produce the following output: ( | scan ):
ASELECT: 5 1 | 3 5 9

^ hand at beginning of select function

^ Boolean whether reference bit has to be reset (>= 50th instructions since last time)

^ Lowest class found [0-3]

^ Victim frame selected

^ Number of frames scanned

AGING requires to maintain the age-bit-vector. In this assignment please assume a 32-bit unsigned counter treated as a bit

vector. Note: “age = age >> 1” shifts the age to the right and “age = (age | 0x80000000)” sets the leading bit to

one. Aging is implemented on every page replacement request. Since only active pages can have an age, it is fine (read

recommended) to stick the age into the frame table entry. Once the victim frame is determined, the hand is set to the next

position after the victim frame for the next select_victim invocation. Note the age has to be reset to 0 on each MAP operation.

Use a virtual pager function at the top to reset its value, where others algos simply implement a default noop for that function.

The “-oa” option will produce the following output: ( | | scan ): ( age is hexadecimal )
ASELECT 2-1 | 2:40000000 3:10000000 0:20000000 1:80000000 | 3

^ scan from frame 2 to 1 (so there is a wrap around )

^ frame# and age (hexadecimal) after shift and ref-bit merge (while scanning the frames)

^ frame selected (3)

WORKING-SET: In the case of working set we also need to deal with time. Again we use the execution of a single

instruction as a time unit as we don’t have anything else in this simulation. We assume TAU=49, so if 50 or more instructions

have passed since the time of “last use” was recorded in the frame and the reference bit is not set, then this frame will be

selected (see algo). Note when you map a frame, you must set its time of last use to the current time (instruction count).

The “-oa” option will produce the following output: ( | | scan )
ASELECT 3-2 | 3(0 3:7 5198) 2(0 3:31 5196) 1(0 0:34 5199) 0(1 0:10 0) | 2

^ scan from frame 3 to 2 (so there is a wrap around )

^ frame# (refbit, proc:vpage, timelastuse) (while scanning the frames)

frame selected (2) ^
ASELECT 44-43 | 44(1 2:18 2340) 45(0 1:33 5140) STOP(2) | 45

the scan stops if a frame is found with condition ^

Programming Assignment #3 (Lab 3): Virtual Memory Management Professor Hubertus Franke
Class CSCI-GA.2250-001 Summer 2021 Page 7

and that frame will be selected, (2) is number of frames scanned and 45 is the frame selected.

if no frame matches the time condition the one with the oldest “time_last_used” will be selected.

What to do on Process Exit:

On process exit (instruction), you have to traverse the active process’s page table starting from 0..63 and for each valid entry

UNMAP the page and FOUT modified filemapped pages. Note that dirty non-fmapped (anonymous) pages are not written

back (OUT) as the process exits. The used frame has to be returned to the free pool and made available to the get_frame()

function again. The frames then should be used again in the order they were released.

OTHER STUFF

The pagetable and frametable output is generated AFTER the instruction is executed, so the output becomes the state seen

prior to executing the next instruction.

Optional arguments in arbitrary order ? This was shown in the sample programs ~frankeh/Public/ProgExamples.tz

Please read: http://www.gnu.org/software/libc/manual/html_node/Example-of-Getopt.html ( very useful and trivial to use)

Provided Inputs
The submission comes with a few generated inputs that you can use to address the implementation in an incremental step.

Each input is characterized by how many processes, how many maximum vmas per process, how many maximum write

protected vmas per process, whether there is a filemapped vma and maximum numbers of vma holes might exist for a process.

Input

File

#inst #procs #vmas

(max)

Write-

protect

File-

mapped

Holes Proc

Exits

in1 30 1 1 0

in2 30 1 1 0

in3 100 1 4 0

in4 100 1 5 2

in5 100 1 5 0 1

in6 100 1 5 2 2

in7 200 2 2

in8 200 2 3 1 1

in9 1000 3 4 1 1 2

in10 5000 4 6 2 1 2

in11 5000 4 6 3 1 2 2

Sample output files are provided as a *.tar.Z for each input and each algorithm for two frame number scenarios –f16 and –f32

→ 11 * 2 * 6 → 132 files. If you need more you can generate your own outputs using the reference program on the cims

account (under ~frankeh/Public/mmu) for different frame numbers.

I also provide a ./runit.sh and a ./gradeit.sh. (change INPUTS and ALGOS in both to limit what you want to test)
./runit.sh

./gradeit.sh # will generate a summary statement and /LOG file for

more details.

Look at the LOG file and it shows the “diff command” for those files that failed and even if the TOTALCOST are the same

there are differences elsewhere. Remove the ‘-q’ flag in the diff command of the LOG and run manually.

http://www.gnu.org/software/libc/manual/html_node/Example-of-Getopt.html

Programming Assignment #3 (Lab 3): Virtual Memory Management Professor Hubertus Franke
Class CSCI-GA.2250-001 Summer 2021 Page 8

If you runit and then gradeit you will get a matrix as follows .. any failing test will be marked as ‘x’.

$ ./gradeit.sh ../refout ../studentout/

input frames f r c e a w

1 16 . . . . . .

1 32 . . . . . .

2 16 . . . . . .

2 32 . . . . . .

3 16 . . . . . .

3 32 . . . . . .

4 16 . . . x . .

4 32 . . . . . .

5 16 . . . . . .

5 32 . . . . . .

6 16 . . . . . .

6 32 . . . . . .

7 16 . . . . . .

7 32 . . . . . .

8 16 . . . . . x

8 32 . . . . . .

9 16 . . . . . .

9 32 . . . . . .

10 16 . . . . . .

10 32 . . . . . .

SUM 20 20 20 19 20 19

How to approach this lab

I suggest that you follow this approach:

a) read the input creating your processes and their respective vmas and print them out again, to ensure you read properly and

generate the desired output.

b) implement the page table and frame table output, you need these for debugging and final printout anyway.

c) implement the features for a single process first (in1..in6) and implement one algorithm (e.g. fifo).

d) add the basic features for context switching (in7..in8) and then expand to other algorithms.

e) try the more complex input files (in9..in10).

f) finally handle the process exit instructions (in11) as discussed above.

You can modify “runit.sh” and “gradeit.sh” so to only run specific input files and algorithms.

INPUTS=`seq 1 11`

ALGOS=”f r c e a w”

FRAMES=”16 32″

you run the program slightly different then lab1/lab2

cd scripts

./runit.sh ../inputs

./gradeit.sh ../refout