Test: Memory Management- 1 - Computer Science Engineering (CSE) MCQ

Swap space is typically used to store process data

Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm.

For supporting virtual memory, special hardware support is needed from Memory Management Unit. Since operating system designers decide to get rid of the virtual memory entirely, hardware support for memory management is no longer needed

When there is more RAM, there would be more mapped virtual pages in physical memory, hence fewer page faults. A page fault causes performance degradation as the page has to be loaded from secondary device.

Virtual memory is illusion of large main memory.

Size of a page = 4KB = 2^12 Total number of bits needed to address a page frame = 32 – 12 = 20 If there are ‘n’ cache lines in a set, the cache placement is called n-way set associative. Since TLB is 4 way set associative and can hold total 128 (2^7) page table entries, number of sets in cache = 2^7/4 = 2^5. So 5 bits are needed to address a set, and 15 (20 – 5) bits are needed for tag.

Thrashing occurs processes on system require more memory than it has. If processes do not have “enough” pages, the pagefault rate is very high. This leads to: – low CPU utilization – operating system spends most of its time swapping to disk The above situation is called thrashing

1 MB 16-way set associative virtually indexed physically tagged cache(VIPT). 
The cache block size is 64 bytes.

No of blocks is 2^20/2^6 = 2^14.

No of sets is 2^14/2^4 = 2^10.

VA(46)
+-------------------------------+
tag(30) , Set(10) , block offset(6)
+-------------------------------+

In VIPT if the no. of bits of page offset =  (Set+block offset) then only one page color is sufficient. but we need 8 colors because the number bits where the cache set index and  physical page number over lap is 3 so 2^3 page colors is required.(option 
c is ans). 

= 30 ns 

Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm. 

A page table entry must contain Page frame number. Virtual page number is typically used as index in page table to get the corresponding page frame number.

First In First Out Page Replacement Algorithms: This is the simplest page replacement algorithm. In this algorithm, operating system keeps track of all pages in the memory in a queue, oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal. FIFO Page replacement algorithms suffers from Belady’s anomaly : Belady’s anomaly states that it is possible to have more page faults when increasing the number of page frames.

Solution: Statement P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate. Correct, as FIFO page replacement algorithm suffers from belady’s anomaly which states above statement.

Statement Q: Some programs do not exhibit locality of reference. Correct, Locality often occurs because code contains loops that tend to reference arrays or other data structures by indices. So we can write a program does not contain loop and do not exhibit locality of reference. So, both statement P and Q are correct but Q is not the reason for P as Belady’s Anomaly occurs for some specific patterns of page references.

LRU replacement policy: The page that is least recently used is being Replaced. Given String: 1, 2, 1, 3, 7, 4, 5, 6, 3, 1 123  // 1 ,2, 3 //page faults 173→7 473→4 453→5 456→6 356→3 316 →1 Total 9 In optimal Replacement total page faults=7 Therefore 2 more page faults  Answer is C

The optimal page replacement algorithm swaps out the page whose next use will occur farthest in the future. In the given question, the computer has 20 page frames and initially page frames are filled with pages numbered from 101 to 120. Then program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. The first 20 accesses to pages from 1 to 20 would definitely cause page fault. When 21st is accessed, there is another page fault. The page swapped out would be 20 because 20 is going to be accessed farthest in future. When 22nd is accessed, 21st is going to go out as it is going to be the farthest in future. The above optimal page replacement algorithm actually works as most recently used in this case. Iteration 1: (1-100) Not present - all replaced 1-20 in 20 frames, 21-100 in 20th frame. hence, page faults = 100 Iteration 2: (1-19) present | (20-99) NOT present | (100) present - the replacements are done at the 19th frame hence, page faults = 100 - 19 - 1 = 80 Iteration 3: (1-18) present | (19-98) NOT present | (99-100) present - the replacements are done at the 18th frame hence page faults = 100 - 18 - 2 = 80 Iteration 4: (1-17) present | (17-97) NOT present | (98-100) present - the replacements are done at the 17th frame hence page faults = 100 - 17 - 3 = 80 Total page faults = 100 + 80 + 80 +80 = 340 Along with generating same number of page faults M.R.U also generates replacements at the same positions as in the Optimal algorithm.(Assuming the given 101-120 pages are INVALID (not belonging to the same process) or Empty). While the LIFO replacement does not behave like Optimal replacement algorithm as it generates 343 page faults. Because from 21st page all pages are placed in 20th frame, therefore hits per iteration reduces down to 19 from the 2nd iteration of pages. Whereby Total Page faults = 100 + 81 + 81 + 81 = 343

Virtual Memory would not be very effective if every memory address had to be translated by looking up the associated physical page in memory. The solution is to cache the recent translations in a Translation Lookaside Buffer (TLB). A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses.

Solution : Size of a page = 4KB = 2^12 means 12 offset bits CPU generates 32-bit virtual addresses Total number of bits needed to address a page frame = 32 – 12 = 20 If there are ‘n’ cache lines in a set, the cache placement is called n-way set associative. Since TLB is 4 way set associative and can hold total 128 (2^7) page table entries, number of sets in cache = 2^7/4 = 2^5. So 5 bits are needed to address a set, and 15 (20 – 5) bits are needed for tag. Option (C) is the correct answer.