DATA STRUCTURES:

To approach this assignment, read in the specification and create process objects, each with its array/vector/list of vmas and a page_table that represents the translations from virtual pages to physical frames for that process.

A page table naturally must contain exactly 64 page table entries (PTE). Please use constants rather than hardcoding “64” . A PTE is comprised of the PRESENT/VALID, REFERENCED, MODIFIED, WRITE_PROTECT, and PAGEDOUT bits and the number of the physical frame (in case the pte is present). This information can and must be implemented as a single 32- bit value or as a bit structure (easier). It cannot be a structure of multiple integer values that collectively is larger than 32-bits. See http://www.cs.cf.ac.uk/Dave/C/node13.html (BitFields)  or http://www.catonmat.net/blog/bit-hacks-header-file/ as  an

example, I highly encourage you to use the first technique, let the compiler do the hard work for you.

Assuming that the maximum number of frames is 128, which equals 7 bits and the mentioned 5 bits above, you effectively have 32- 12 = 20 bits for your own usage in the pagetable entry. You can use these bits at will (e.g. remembering whether a PTE is file mapped or not). What you can NOT do is run at the beginning of the program through the page table and mark each PTE with bits based on filemap or writeprotect. This is NOT how OSes do this due to hierarchical pagetable structures (not implemented in this lab though). You can only set those bits on the first page fault to that virtual page.

You must define a global frame_table that each operating system maintains to describe the usage of each of its physical frames and where you maintain reverse mappings to the process and the vpage that maps a particular frame. Note, that in this assignment a frame can only be mapped by at most one PTE at a time, which simplifies things significantly.

SIMULATION and IMPLEMENTATION:

During each instruction you simulate the behavior of the hardware (shown below in blue) and hence you must check that the page is present. A special case are the ‘c’ (context switch) instruction which simply changes the current process and current page table pointer and the ‘e’ (process exit) instruction which exits a process.

Structure of the simulation

The basic structure of the simulation should be something like the following:

typedef struct { … } pte_t;          // can only be total of 32-bit size and will check on this

typedef struct { … } frame_t;

frame_t frame_table[MAX_FRAMES];

pte_t   page_table[MAX_VPAGES];  // a per process array of fixed size=64 of pte_t  not pte_t pointers !

class Pager {

virtual frame_t* select_victim_frame() = 0;   // virtual base class

};

frame_t *get_frame() {

frame_t *frame = allocate_frame_from_free_list();

if (frame == NULL) frame = THE_PAGER->select_victim_frame();

return frame;

}

while (get_next_instruction(&operation, &vpage)) {

// handle special case of “c” and “e” instruction

// now the real instructions for read and write

pte_t *pte = &current_process->page_table[vpage];

if ( ! pte->present) {

// this in reality generates the page fault exception and now you execute        // verify this is actually a valid page in a vma if not raise error and next inst frame_t *newframe = get_frame();

//-> figure out if/what to do with old frame if it was mapped

//   see general outline in MM-slides under Lab3 header and writeup below

//   see whether and how to bring in the content of the access page.

}

// now the page is definitely present

// check write protection

// simulate instruction execution by hardware by updating the R/M PTE bits

update_pte(read/modify) bits based on operations.

}

When accessing a page (“r” or “w”) and the page is not present, as indicated by the associated PTE’s valid/present bit, the hardware would raise a page fault exception. Here you just simulate this by calling your (operating system’s) pagefault handler. In the pgfault handler you first determine that the vpage can be accessed, i.e. it is part of one of the VMAs. Maybe you can  find a  faster way then  searching each time the VMA list  as long as it does not involve doing that before the instruction simulation (see above, hint you have free bits in the PTE). If not, a SEGV output line must be created and you move on to the next instruction. If it is part of a VMA then the page must be instantiated, i.e. a frame must be allocated, assigned to the PTE belonging to the vpage of this instruction (i.e. currentproc->pagetable[vpage].frame = allocated_frame ) and then populated with the proper content. The population depends whether this page was previously paged out (in which case the page must be brought back from the swap space (“IN”) or (“FIN” in case it is a memory mapped file). If the vpage was never swapped out and is not file mapped, then by definition it still has a zero filled content and you issue the “ZERO” output.

That leaves the allocation of frames. All frames initially are in a free pool (use deque to get desired semantics). Once you run out of free frames, you must implement paging. We explore the implementation of several page replacement algorithms. Page replacement implies the identification of a victim frame according to the algorithm’s policy. This should be implemented as a derived class of a general Pager class with at least one virtual function “frame_t* select_victim_frame ();” that returns a victim frame (or returns int for the frame number). Once a victim frame has been determined, the victim frame must be unmapped from its user (

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:42) 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=1230. In addition if the following operations counts as follows:

maps=350, unmaps=410, ins=3200, outs=2750, fins=2350, fouts=2800, zeros=150, segv=440, segprot=410

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.

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 per process statistics “PROC[i]” and 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/lab3/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.

DEDUCTIONS: 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. The right way is to set required flags on the pte during the page fault and then only on that faulting page. Another 2pts for not printing the real size of pte_t from your program which  must  show “4” indicating  your  pte  indeed  is  32bit. Another 2 pts each  for  wrong  pagetable  and  frame  table organizations.  They are both arrays/vectors of PTEs and FRAMES, not of pointers to PTE or Frames.

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.

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