In this project, you will write a code that simulates the operation of the virtual memory. The code simulates the Page Table, the TLB and the Frame Table. To keep the project simple, well assume there is only one process running and, therefore, theres one page table in the simulation. Below are the parameters of the virtual memory system were considering. Virtual address space Virtual address Physical address space Physical address Page size Number of virtual pages Number of physical pages 1 MB = 2^20 Bytes = 1,048,576 Bytes 20-bit 256 KB = 2^18 Bytes = 262,144 Bytes 18-bit 1 KB = 2^10 bytes = 1024 Bytes 2^20 / 2^10 = 2^10 = 1024 virtual pages 2^18 / 2^10 = 2^8 = 256 physical pages (frames) In the simulation, were using all the design criteria weve studied. Pages are placed in a fully associative way in the memory. We use the write-back scheme with the dirty-bit optimization. The replacement scheme is the approximation of the Least Recently Used (LRU) scheme using the reference bit. Below are the criteria of the TLB that caches the recently used translations. Size Fully associative Block size Write policy 8 translations Any translation can go anywhere in the TLB 1 translation (copy one translation at a time to/from the page table) write-back (update D,R bits in the TLB only; update the page table upon Eviction of the translation) The three data structures shown below represent the main data of the simulation. #define VPAGES #define TLB_SIZE #define FRAMES 1024 8 256 // number of virtual pages // TLB size // number of frames unsigned int PageTable[VPAGES][4]; unsigned int TLB [TLB_SIZE][5]; unsigned int FrameTable[FRAMES]; - 1 -Main Data Structures of the Simulation This is the format of the main data structures of the simulation. The simulation keeps track of 8 translation entries in the TLB, 1024 virtual pages in the Page Table and 256 frames in the Frame Table. A frame is a page in the RAM. The frame table keeps track of our RAM space and indicates whether each frame is currently allocated or available. Format of the TLB Entry Valid bit Dirty bit Reference bit Tag (full virtual page number) Frame number (physical page number) 0 ... 7 Format of the Page Table Page # Valid bit Dirty bit Reference bit Frame number (physical page number) 0 ... 1023 Format of the Frame Table Frame # 0 1 2 3 ... 256 Allocated (y/n) 1 0 1 1 ... 0 - 2 -Measurements The simulation should measure the following metrics. TLB hit Translation found in TLB TLB miss Translation not found in TLB; we attempt the page table next TLB hit rate TLB hit / (TLB hit + TLB miss) Page table hit The page is found to be in RAM Page fault The page is not in the RAM; therefore on the hard disk Page table hit rate Page table hit / (Page table hit + Page fault) TLB shootdown A translation is evicted from the TLB; because the TLB is full Page eviction A page is evicted from the RAM; because the frames are all used up Hard disk read A new page is brought from the hard disk Hard disk write The page evicted from the RAM is dirty; its written to the hard disk Guidelines This project is an individual assignment. The code can be written in any language. The attached functions layout can be modified to suit your preference. If you plan to use a completely different functions setup, please discuss your approach with the instructor. Submit all the source files (with instructions for compilation if needed) Submit a report showing the case studies results and your new case study Grading Criteria All the functions are written; code style and readability are graded All the case studies listed below are reproduced and explained Perform a new case study not listed below; for example, investigate the frequency of clearing the reference bits (e.g: every 3000 accesses) and show the results; alternatively, investigate a new pattern of temporal and spatial locality. - 3 - (2 pts) (2 pts) (1 pt)Case Study #1 Access 5 addresses from the same page Five random addresses from the same virtual page number (VPN=0) are accessed. ----------------------------------------- VIRTUAL MEMORY SIMULATION ----------------------------------------- T: 1 Address: w 51 T: 2 Address: r 374 T: 3 Address: w 846 T: 4 Address: w 219 T: 5 Address: w 433 VPN: VPN: VPN: VPN: VPN: 0 0 0 0 0 ----------------------------------------------------------------------------- SIMULATION RESULTS ----------------------------------------------------------------------------- TLB hits: 4 TLB misses: 1 TLB hit rate: 80.00% TLB Shootdowns: 0 TLB Writes: 1 Pg Table accesses: 1 Pg Table hits: 0 Pg evictions: 0 Pg faults: 1 Pg Table writes: 1 Pg Table hit rate: 0.00% Hard disk reads: 1 Hard disk writes: 0 ----------------------------------------------------------------------------- The first access results in a TLB miss while the subsequent accesses result in TLB hits. There are no TLB shootdowns since the TLB didnt fill up. Only one translation went into the TLB. The page table is accessed only for the first access which resulted in a page fault. On subsequent accesses, since we get TLB hits, the page table is not accessed. The hard disk is read only once when the page (used for all accesses) was read from the disk. - 4 -Case Study #2 Access 5 addresses from different pages Five random addresses are accessed. They belong to five difference pages. ----------------------------------------- VIRTUAL MEMORY SIMULATION ----------------------------------------- T: 1 Address: w 178406 T: 2 Address: r 442630 T: 3 Address: w 507896 T: 4 Address: r 212346 T: 5 Address: r 439947 VPN: VPN: VPN: VPN: VPN: 174 432 495 207 429 ----------------------------------------------------------------------------- SIMULATION RESULTS ----------------------------------------------------------------------------- TLB hits: 0 TLB misses: 5 TLB hit rate: 0.00% TLB Shootdowns: 0 TLB Writes: 5 Pg Table accesses: 5 Pg Table hits: 0 Pg evictions: 0 Pg faults: 5 Pg Table writes: 5 Pg Table hit rate: 0.00% Hard disk reads: 5 Hard disk writes: 0 ----------------------------------------------------------------------------- Five translations were brought to the TLB, all resulting in TLB misses. No TLB shootdowns performed since the TLB can fit all five translations. The page table is accessed five times, all page faults. The hard disk was read five times to read the pages. - 5 -Case Study #3 Access 20 addresses from different pages Twenty random addresses from different pages are accessed. We selected the pages sequentially. ----------------------------------------- VIRTUAL MEMORY SIMULATION ----------------------------------------- T: 1 Address: r 845 T: 2 Address: w 1857 T: 3 Address: w 2103 T: 4 Address: w 4081 T: 5 Address: w 5068 T: 6 Address: w 5535 T: 7 Address: w 6345 T: 8 Address: r 7304 T: 9 Address: w 8704 T: 10 Address: w 9315 T: 11 Address: r 10374 T: 12 Address: r 12160 T: 13 Address: w 12961 T: 14 Address: r 13553 T: 15 Address: w 14405 T: 16 Address: r 15578 T: 17 Address: w 16960 T: 18 Address: r 18067 T: 19 Address: w 18734 T: 20 Address: r 20470 VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: VPN: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ----------------------------------------------------------------------------- SIMULATION RESULTS ----------------------------------------------------------------------------- TLB hits: 0 TLB misses: 20 TLB hit rate: 0.00% TLB Shootdowns: 12 TLB Writes: 20 Pg Table accesses: 20 Pg Table hits: 0 Pg evictions: 0 Pg faults: 20 Pg Table writes: 20 Pg Table hit rate: 0.00% Hard disk reads: 20 Hard disk writes: 0 ----------------------------------------------------------------------------- All accesses resulted in TLB misses since the pages are unique. Twenty different translations went through the TLB (of size 8), hence, there are 12 TLB shootdowns. Twenty pages were read from the hard disk. - 6 -Case Study #4 Access 500 random addresses 500 random addresses are accessed. ----------------------------------------------------------------------------- SIMULATION RESULTS ----------------------------------------------------------------------------- TLB hits: 4 TLB misses: 496 TLB hit rate: 0.80% TLB Shootdowns: 488 TLB Writes: 496 Pg Table accesses: 496 Pg Table hits: 99 Pg evictions: 141 Pg faults: 397 Pg Table writes: 397 Pg Table hit rate: 19.96% Hard disk reads: 397 Hard disk writes: 0 ----------------------------------------------------------------------------- First, we notice how the TLB hit rate is very small since were accessing random addresses and hopping between pages (little locality). Bringing a new translation for each access overwhelms our small TLB. In the earlier case studies (#1 to #3), we had zero page evictions. The RAM has 256 frames and we accessed 500 random pages in this case study. Accordingly, the RAM space will be used up and some pages need to be evicted. Interestingly, there were no disk writes. The system was able to find a clean page to evict each time. In our simulation, each access is read or write with the same probability of 50%. - 7 -Case Study #5 Access 500 random addresses, all accesses are writes 500 random addresses are accessed with write operations. ----------------------------------------------------------------------------- SIMULATION RESULTS ----------------------------------------------------------------------------- TLB hits: 4 TLB misses: 496 TLB hit rate: 0.80% TLB Shootdowns: 488 TLB Writes: 496 Pg Table accesses: 496 Pg Table hits: 83 Pg evictions: 157 Pg faults: 413 Pg Table writes: 413 Pg Table hit rate: 16.73% Hard disk reads: 413 Hard disk writes: 157 ----------------------------------------------------------------------------- This scenario is similar to the previous case study. The TLB hit rate is small since were accessing random pages. There are page evictions since were accessing 500 pages and we have 256 frames in the RAM. However, all the accesses are writes. This means all the pages are marked with dirty-bit=1 in the TLB and in the page table. Any page that is evicted is written to the hard disk. Thus, we see that the page evictions is equal to the hard disk writes. - 8 -Case Study #6 1000 memory accesses; each 40 consecutive addresses from the same page 40 random addresses from page 0 are accessed, then 40 random addresses from page 1 are accessed, then, 40 random addresses from page 2 are accessed, etc. In total, 25 pages are accessed. Each access is either read or write with 50% probability. ----------------------------------------------------------------------------- SIMULATION RESULTS ----------------------------------------------------------------------------- TLB hits: 975 TLB misses: 25 TLB hit rate: 97.50% TLB Shootdowns: 17 TLB Writes: 25 Pg Table accesses: 25 Pg Table hits: 0 Pg evictions: 0 Pg faults: 25 Pg Table writes: 25 Pg Table hit rate: 0.00% Hard disk reads: 25 Hard disk writes: 0 ----------------------------------------------------------------------------- For each page, the first access out of 40 is a miss followed by 39 hits, hence the TLB hit rate of 39/40 = 97.5%. In most of the earlier case studies, the TLB hit rate was small due to page hopping. On the other hand, this case study shows that the small TLB size of eight translations can perform very well when there is page locality, which is typical of programs. Since we accessed 25 pages in total, they can all resides in the frames and there was no page evictions. - 9 -Case Study #7 3000 memory accesses; each 10 consecutive addresses from the same page 10 random addresses from page 0 are accessed, then 10 random addresses from page 1 are accessed, etc. In total, 300 pages are accessed. Each access is either read or write with 50% probability. ----------------------------------------------------------------------------- SIMULATION RESULTS ----------------------------------------------------------------------------- TLB hits: 2700 TLB misses: 300 TLB hit rate: 90.00% TLB Shootdowns: 292 TLB Writes: 300 Pg Table accesses: 300 Pg Table hits: 0 Pg evictions: 44 Pg faults: 300 Pg Table writes: 300 Pg Table hit rate: 0.00% Hard disk reads: 300 Hard disk writes: 44 ----------------------------------------------------------------------------- This case study is similar to the previous one. We get a TLB hit followed by 9 TLB misses, hence the TLB hit rate is 90%. The difference here is we access 300 unique pages and the RAM space is 256 frames, therefore, we observe (300-256) = 44 page evictions. Each page was accessed 10 times with 50% probability of write. Therefore, there is a high chance at least one access is a write and the page is marked dirty. Accordingly, we observe that all of the 44 page evictions resulted in hard disk writes.