[SOLVED] 代写 R data structure algorithm Assignment

Assignment
• Implementation, in simulation, of a virtual memory system based on demand paging
• It accepts virtual addresses along with access type (read or write) and outputs the content of corresponding physical addresses or an error
• Features:
• Physical memory is simulated by an array of bytes (char data type)
• Page table resides within the simulated main memory
• Translation look-aside buffer (TLB) is simulated using a separate
buffer and uses LRU replacement on misses
• Page faults are serviced from a backing store (disk swap partition) that is simulated by a file
• Second chance algorithm is used for page replacement
2

Paging parameters
• A virtual address is a 12-bit integer
• The system has 1 KB of physical memory divided into 64
bytes frames
• There is only a single process and hence a single page table
• The page table is always resident in the (few) first frame(s) of the physical memory and never paged out.
• Resides at address 0
• The backing store maximum size is 4 KB divided into blocks
of 64 bytes blocks; each block holds 1 page.
Note: memory sizes are kept small for ease of debug. However, simulator has to be as generic as possible => use constants
3

The page table
• The binary representation of an entry of the page table is as follows:
• The MSB or left-most bit is the valid bit indicating whether the page is in memory or in disk
• The next bit to the left is the reference bit used for implementing the Second chance algorithm
• The number indicating the location of the page is in the LSB (right-most bits): • If the page is in memory, it’s the frame number
• If the page is not in memory, it’s the location of the page in the backing store file
• 0 if the page does not exist
• One page table entry might require many bytes:
• Enough bits are needed to store all the above data
• The page table needs to fit in the minimum number of pages possible • The number of bytes per entry is preferably a power of 2: 1, 2, 4…
• See example next
4

Illustrative example (different system)
• The physical memory consists of 32 frames
• The backing store consists of 64 blocks each able to store one page
5 bits are needed to encode the physical memory frame number
6 bits are needed to encode the backing store block number
• If only a valid bit and a dirty bit are needed (no reference bit)
The total number of bits needed to store one page table entry is max(5,6)+2=8 i.e. one byte is enough
• If the page table contains 1024 entries (one byte each) and each page/frame/block is 512 bytes
Assuming that the page table is resident in the first few frames of the memory, then 2 consecutive pages are required to store the page table.
• Without the assumption, a two levels page table would be required.
• If two bytes per page table entry are used, then 4 pages will be need to store the page table

Illustrative example: page table entries
76543210
Bit 7: Page is resident.
Bit 6: Has not been accessed since the last replacement Bits 5-0: frame number = 3
76543210
Bit 7: Page is swapped out.
Bit 6: Not relevant but preferably set to 0 Bits 5-0: block number = 5
76543210
Bit 7: Page does not exist
Bit 6: Not relevant but preferably set to 0 Bits 5-0: 0 value
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0

Frame and block allocation
• To swap a page in the physical main memory, a free frame must be found
• To swap out a page into the backing store, a free block must be found
• Bitmaps are used to keep track of the physical memory and backing store occupancy
• Bitmaps are to be kept in main memory. Similarly to the page table, they should occupy a minimum number of pages i.e. one page per bitmap at best
• The page(s) containing the bitmaps is(are) always resident, never to be swapped out, located right next to that(those) occupied by the page table
• Example (the number of pages for each data structure is arbitrary here): …………….
Page table
Physical memory bitmap
Backing store bitmap
Process pages
7

Bitmap layout
• Bitmaps should be stored starting at the first bit of the bitmap page
• Bit i of the page corresponds to frame (or block) i
• Note that the first bit of the page is the MSB of byte 0 i.e. • frame (or block) 0 corresponds to MSB of byte 0 of the page
• frame (or block) 7 corresponds to the LSB of byte 0 of the page • frame (or block) 8 corresponds to MSB of byte 1 of the page
• frame (or block) 15 corresponds to LSB of byte 1 of the page •…

The TLB
• The TLB has 4 entries storing the results of the most recent translations, thus servicing most translations
• At a miss, translation goes through the page table and the LRU entry of the TLB needs to be replaced
• To implement the LRU replacement, one integer, called LRU, is associated with each entry
• If a page reference is found in the TLB (hit) at entry k, then • For all entries i such that LRU[i] < LRU[k], increment LRU[i]• Set LRU[k] = 1• If a page reference it is not found in the TLB (miss), then • Find the entry k with the max LRU value and set LRU[k]=1• Increment all other LRU values Program input• The program reads 3 input files:1. A file containing a snapshot of the physical memory and used to initialize the array simulating it. The value of each byte is written in base 10. Byte values are separated by spaces. 2. A file simulating the backing store and consisting in a sequence of page contents each preceded by the corresponding block number. Page contents are laid out similarly to the above input file.
3. A file containing a sequence of virtual addresses (in base 10), each is followed by the access mode requested (r or w)
e.g. 3420 R 201 W 569 W 9000 R
To simplify, we assume that all write requests will write the value of the physical address obtained from translation (modulo 256) and thus no write- value is provided

Program output
• The program writes its output to a file

• For each memory access request, the program writes to the file two pieces of information:
• The event that happened during translation: • H: TLB hit
• M: TLB miss, but page was resident in memory
• PF: a page fault happened and the page was swapped in • E: error, the page does not exist
• The content of (the byte) residing at the physical address resulting from the translation
• In case of error, the content returned should be N/A
• Input and output file names should be passed as program arguments:
./

Address translation algorithm
After initialization, the simulator:
• reads, from the 3rd input file, one memory access requests consisting each of a virtual address and an access mode: read or write
• extracts the page number and the offset value
• Searches the TLB for a corresponding frame number:
• If found, it constructs the physical address
• If not found, it uses the page number to read the corresponding page table entry from main memory and extracts the valid bit and the page location information …
• After finishing the translation update the TLB

Address translation algorithm
• If the valid bit is set, the page location is a frame number used to immediately construct the physical address
• If not set, and the location information is not 0 then it services the page fault (see algorithm in next slide) then uses the resulting frame number to construct the physical address
• If not set, and the location information is 0:
• If the access request is a READ, then output an error
• If the access request is a WRITE, allocate a new frame and use its number to construct the physical address
• Using the obtained physical address, read the content of the corresponding byte in memory
• If the access mode is WRITE, write the physical address modulo 256 in the corresponding byte in memory
• Write the appropriate event and the (original) byte content to the output file.

Page fault servicing
When a page fault is detected:
• Scan the physical memory bitmap to find an empty frame
• If not found, run second chance algorithm, using the reference bit in the page table, to select a page to swap out / frame to free
• Use the backing store bitmap to find a free block.
• Append to the backing store file, the bock number and the content of the
victim page
• Use the page location information to identify the block number in the backing store file
• Lookup the backing store file for the block number
• Copy the content of the block into the selected / freed frame
• Update the page table with the appropriate information for both the swapped-in and swapped-out pages
• Return the frame number of the swapped-in page

Programming hints
• Getting and setting the value of a bit (from some byte) could be done via bitwise operations, if any are available in your programming language
• Or it could be done via integer division and remainder operation on the decimal value of the whole byte. E.g.:
• to extract MSB (bit 7), divide by 27 the byte value
• To extract LSB (bit 0), take the remainder of division of the byte value by 2 • To extract second LSB (bit 1), divide by 2 then remainder of division by 2
• To extract second MSB (bit 6), divide by 26 then remainder of division by 2 •…
• All values manipulated here are positive integers: use unsigned integer data type if available
• In C/C++, fixed size integer types are defined in