BEST代写-线上编程学术专家

Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

C++代写 | CSCI-GA.2250-001 Virtual Memory Management

C++代写 | CSCI-GA.2250-001 Virtual Memory Management

这个作业是用C++实现/模拟操作系统的虚拟内存的操作
Programming Assignment #3 (Lab 3): Virtual Memory Management  
Class CSCI-GA.2250-001 Summer2020  
process/vma/page reference generator  
procs=2 #vmas=2 #inst=100 pages=64 %read=75.000000 lambda=1.000000  
holes=1 wprot=1 mmap=1 seed=19200  
### process 0  
42 0 0  
3 63 1 0  
### process 1  
17 0 1  
0 63 1 0  
Since it is required that the VMAs of a single address space do not overlap, this property is guaranteed for all provided input  
files. However, there can potentially be holes between VMAs, which means that not all virtual pages of an address space are  
valid (i.e. assigned to a VMA). Each VMA is comprised of 4 numbers.  
start_vpage:  
end_vpage:  
write_protected: binary whether the VMA is write protected or not  
file_mapped: binary to indicated whether the VMA is mapped to a file or not  
(note the VMA has (end_vpage start_vpage + 1) virtual pages )  
The process specification is followed by a sequence of “instructions” and optional comment lines (see following example).  
An instruction line is comprised of a character (‘c’, ‘r’, ‘w’ or ‘e’) followed by a number.  
c <procid>: specifies that a context switch to process #<procid> is to be performed. It is guaranteed that the first  
instruction will always be a context switch instruction, since you must have an active pagetable in the MMU (in real systems).  
r <vpage>: implies that a load/read operation is performed on virtual page <vpage> of the currently running process.  
w <vpage>: implies that a store/write operation is performed on virtual page <vpage> of the currently running process.  
e <procid>”: current process exits, we guarantee that <procid> is the current running proc, so you can ignore it.  
#
#### example of an instruction sequence ######  
c 0  
r 32  
w 9  
r 0  
r 20  
r 12  
You can assume that the input files are well formed as shown above, so fancy parsing is not required. Just make sure you take  
care of the ‘#’ comment lines. E.g. you can use sscanf(buf, “%d %d %d %d”,…) or stream >> var1 >> var2 >> var3.  
SIMULATION and IMPLEMENTATION:  
During each instruction you simulate the behavior of the hardware 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.  
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 !!!!  
typedef struct { … } frame_t;  
frame_t frame_table[MAX_FRAMES];  
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];// in reality this is done by hardware  
if ( ! pte->present) {  
// this in reality generates the page fault exception and now you execute  
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  
/ see whether and how to bring in the content of the access page.  
}
// check write protection  
// simulate instruction execution by hardware by updating the R/M PTE bits  
update_pte(read/modify) bits based on operations.  
}
Classes for every paging algorithm should derive from a base Pager class and there should be no replication of the simulation  
code. This will allow adding new classes.  
When accessing a page (ror 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  
subclass of a general Pager class with one virtual functionframe_t* select_victim_frame(); that returns a  
victim frame. Once a victim frame has been determined, the victim frame must be unmapped from its user ( <address  
space:vpage>), i.e. its entry in the owning process’s page_table must be removed (“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 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.  
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  
Random  
f
r
Clock  
Enhanced Second Chance / NRU  
Aging  
Working Set  
c
e
a
w
The page replacement 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 <proc-id,vpage>) inside each frame’s frame table entry.  
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. Instead, on the first page  
Programming Assignment #3 (Lab 3): Virtual Memory Management  
Class CSCI-GA.2250-001 Summer2020  
Professor Hubertus Franke  
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).  
You are to create the following output if requested by an option (see at options description and set of options we grade with):  
4
9: ==> r 4  
UNMAP 1:42  
OUT  
69: ==> r 37  
UNMAP 0:35  
FIN  
75: ==> w 57  
UNMAP 2:58  
ZERO  
IN  
MAP 18  
MAP 17  
MAP 26  
Output 1  
Output 2  
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 <curprocid : vpage> 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 instructions, segv, segprot, unmap, map, pageins (IN, FIN), pageouts (OUT,  
FOUT), and zero operations for each process. In addition you should compute the overall execution time in cycles, where  
maps and unmaps each cost 400 cycles, page-in/outs each cost 3000 cycles, file in/outs cost 2500 cycles, zeroing a page costs  
1
50 cycles, a segv costs 240 cycles, a segprot costs 300 cycles and each access (read or write) costs 1 cycles and a context  
switch costs 121 cycles and process exit costs 175 cycles.  
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\n”, inst_count, ctx_switches, process_exits, cost);  
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  
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. Add 32-bit numbers  
incrementally to the 64-bit counters.
.
/mmu f<num_frames> -a<algo> [-o<options>] inputfile randomfile  
(optional arguments in any order).  
e.g. ./mmu -f4acoOPFS 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. 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 from the input file.  
bestdaixie