[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, its the frame number
If the page is not in memory, its 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