Previous Year Questions: Memory Management | Operating System - Computer Science Engineering (CSE) PDF Download

Q1: Consider a 32-bit system with 4 K B  page size and page table entries of size 4 bytes each. Assume 1 K B = 2¹⁰ bytes. The OS uses a 2 - level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry. An active process in this system accesses 2000 unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let X denote the minimum and Y  denote the maximum number of pages across the two levels of the page table of the process. The value of X + Y  is _____  (2024 SET 2)
(a) 512
(b) 1028
(c) 2048
(d) 4096
Ans: (b)
Sol: Given: 

•  System address space ( V A ) = 32 b i t s 
• Page size ( P S ) = 4 K B
• Total pages used by a process ( N ) = 2000 p a g e s
•  Page table entry size (PTE) = 4 B

It is given in the question that OS allocates a page(means single page) for the outer page directory upon process creation.
So, total number of bits needed to represent entries in outer page table = log ( PS / PTE) = log (2¹²  / 2²) = 10 bits
And total number of bits needed to represent entries in inner page table =32 − 10 − 12 = 10 bits
For X:
In each inner page table we can store 2 ¹⁰ entries. So, minimum number of page tables ( P T ) needed to store 2000 pages will be
[2000 / 2¹⁰] = 2 PT
∴ X = 2 + 1 ( for outer PT ) = 3
For occupying maximum pages in 2-level page table, we need to place at least one P T E from 2000 pages in every page of the inner page table equating to 2 ¹⁰ P T .
∴ X = 2¹⁰ + 1 ( for outer PT ) = 1025
The value of X + Y = 1028
 
Q2: Which of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?  (2024 SET 2)
(a) Allocate a new page table for a newly created process
(b) Translate a virtual address to a physical address using the page table
(c) Raise a trap when a virtual address is not found in the page table
(d) Raise a trap when a process tries to write to a page marked with read-only permission in the page
Ans: (b, c, d)
Sol: The Memory Management Unit (MMU) is a critical component in computer systems that use paging for memory management. Its responsibilities are as follows:
Option A
Allocate a new page table for a newly created process
This task is generally handled by the operating system's memory manager, not the MMU itself. The MMU primarily deals with the translation and protection aspects, whereas the allocation of page tables lies outside its typical responsibilities.
Option B
Translate a virtual address to a physical address using the page table
This is one of the primary responsibilities of the MMU. When a program accesses memory, it uses virtual addresses, which the MMU translates into physical addresses using the page table.
Option C
Raise a trap when a virtual address is not found in the page table
The MMU is responsible for detecting page faults, which occur when a virtual address does not have a corresponding physical address in the page table. When this happens, the MMU raises a trap (interrupt) that signals the operating system to handle the fault.
Option D
Raise a trap when a process tries to write to a page marked with read-only permission in the page table
The MMU ensures that memory access permissions are enforced. If a process tries to write to a page marked as read-only, the MMU will raise a trap, indicating a protection fault.
Therefore, the correct answers are:
Option B: Translate a virtual address to a physical address using the page table
Option C: Raise a trap when a virtual address is not found in the page table
Option D: Raise a trap when a process tries to write to a page marked with read-only permission in the page table
These tasks fall directly within the domain of the MMU. Therefore, the correct answers are:

Q3: Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0 , 1 , 2 , and 3  are stored in the page frames 1 , 3 , 2  and 0 , respectively. The physical address (in decimal format) corresponding to the virtual address 2500  (in decimal format) is ____  (2024 SET 1)
(a) 6254
(b) 6385
(c) 6596
(d) 6872
Ans: (c)
Sol: To convert  VA to PA replace Page number with Frame Number.
2KB ~ 11 bit Offset.
(2500)₁₀ = (100111000100)₂
VA = Page Number  + Offset
Page Number | Offset

Replace Page number with 3 for Physical Address. ( Given in the Question )
(3)₁₀ = (11)₂
Frame Number |  Offset

(1100111000100)₂ = (6596)₁₀
Correct :  (C)  6596

Q4: Consider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with L levels for virtual to physical address translation. The page size is 4 KB (1 KB = 1024 B) and a page table entry at any of the levels occupies 8 bytes. The
The value of L is ______.  (2023)
(a) 4
(b) 5
(c) 6
(d) 7
Ans: (b)
Sol: Given,
Virtual Address Space = 57 bits
Page size = 4 KB = 12 bits
Page number= ( 57 − 12 ) = 45 bits
 Page table entry= 8 bytes.
Each page can contain =page table entries. So, we need 9 bits to index the page table .
So, Number of levels = [45 / 9 ] = 5.

So ,Value of L is 5 .

Q5: Consider the following two-dimensional array D in the C programming language, which is stored in row-major order:  (2023)
int D[128][128];
Demand paging is used for allocating memory and each physical page frame holds 512 elements of the array D. The Least Recently Used (LRU) page-replacement policy is used by the operating system. A total of 30 physical page frames are allocated to a process which executes the following code snippet:

The number of page faults generated during the execution of this code snippet is _____.
(a) 128
(b) 4096
(c) 1024
(d) 2048
Ans: (b)
Sol: We are given an array D[128][128] and it is stored in Row-Major order.
Number of physical frames available = 30.
Number of elements in 1 frames = 512.
Number of pages required to accommodate array D[128][128] = (Number of elements in Array D) / (Number of elements in 1 Page frame)
= (128 * 128) / 512 = 32.
If we have total 32 frames instead of 30 frames then there will be no problem at all but here we are only provided with 30 frames.
Now, coming to the loop : 

i → 0 – 127 & j → 0 – 127.
With D[j][i] we are accessing the array matrix in Vertical Manner like shown in below Image :

Number of rows occupied in 1 frame will be : 512 / 128 = 4.
So, Page Frame 1 will contain data from row D[0]…. D[3].
Page Frame 2 will contain data from row D[4]…. D[7]…. and so on up to..
Page Frame 32 will contain data from row D[124]… D[127].

Now it is saying that for page-replacement we have to use LRU policy with 30 Page frames.
As the loop start executing it will move from Frame 1 to Frame 32 in vertical manner as shown in 1st image. But, we have only 30 page frames and since we are using LRU policy so at the end of 1st iteration we will have Page frame 3 to page frame 32. Page 1 & Page 2 will be moved out due to LRU replacement. During this 1st iteration all 32 pages will give us page fault.
So, number of page fault after 1 iteration = 32.
Similarly this loop iterate 128 times and each time it will give 32 page faults.
So, total number of page faults will be 32 * 128 = 4096.

Q6: Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string  (2022)
7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7,1, 5, 6,1
the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is
(a) 0.4
(b) 0.5
(c) 0.6
(d) 0.7
Ans: (c)
Sol: Reference string : 7,2,7,3,2,5,3,4,6,7,7,1,5,6,1
Given that 4 page Frames and LRU page replacement policy.
Access 7 which leads Miss  --- 7, empty, empty, empty ------ Hits =0 , Miss = 1
Access 2 which leads Miss  --- 7, 2, empty, empty ------ Hits =0 , Miss = 2
Access 7 which leads Hit  --- 7, 2, empty, empty ------ Hits =1 , Miss = 2
Access 3 which leads Miss  --- 7, 2, 3, empty ------ Hits =1 , Miss = 3
Access 2 which leads Hit  --- 7, 2, 3, empty ------ Hits =2 , Miss = 3
Access 5 which leads Miss  --- 7, 2, 3, 5 ------ Hits =2 , Miss = 4
Access 3 which leads Hit  --- 7, 2, 3, 5 ------ Hits =3 , Miss = 4
Access 4 which leads Miss  --- 4, 2, 3, 5 ------ Hits =3 , Miss = 5 ( 7 is replaced with 4 by LRU algorithm )
Access 6 which leads Miss  --- 4, 6, 3, 5 ------ Hits =3 , Miss = 6 ( 2 is replaced with 6 by LRU algorithm )
Access 7 which leads Miss  --- 4, 6, 3, 7 ------ Hits =3 , Miss = 7 ( 5 is replaced with 7 by LRU algorithm )
Access 7 which leads Hit  --- 4, 6, 3, 7 ------ Hits =4 , Miss = 7
Access 1 which leads Miss  --- 4, 6, 1, 7 ------ Hits =4, Miss = 8 ( 3 is replaced with 1 by LRU algorithm )
Access 5 which leads Miss  --- 5, 6, 1, 7 ------ Hits =4 , Miss = 9 ( 4 is replaced with 5 by LRU algorithm )
Access 6 which leads Hit  ---  5, 6, 1, 7 ------ Hits =5 , Miss = 9
Access 1 which leads Hit  ---  5, 6, 1, 7 ------ Hits =6 , Miss = 9

Q7: Which one of the following statements is FALSE?  (2022)
(a) The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address.
(b) If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory.
(c) The memory access time using a given inverted page table is always same for all incoming virtual addresses.
(d) In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same.
Ans: (c)
Sol: 
A. According to Galvin, “The TLB is associative, high-speed memory. Each entry in the TLB consists of two parts: a key (or tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously. If the item is found, the corresponding value field is returned.” Hence option A is TRUE.
B. The TLB contains only a few of the page-table entries. If the virtual address of a word given by CPU has a TLB hit it means the the page number is found, so its frame number is immediately available and is used to access memory. Therefore even if the subsequent search for the word results in a cache miss, it does not matter. Its just not in cache memory but the word will always be present in the main memory as we already know the frame number due to the TLB Hit. Hence option B is also TRUE.
C. An Inverted Page Table has frame numbers as indexes unlike a Page Table where page number is used as index to it. Therefore for any given virtual address we need to search the exact < page no . , process no . > in the frames of MM. In worst case we might have to search all the frames of the MM in order to get the exact < page no . , process number > . (This is because we may find the required p g . n o . , but it might be of a different process. So Bad Luck!) This increases main memory access time. This is the reason why the Inverted Page table uses less space but searching time is more. Therefore, the memory access time using a given inverted page table is not always same for all incoming virtual addresses. Hence option C is FALSE and is the ans.
D. In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, it means they will be present as a linked list of items having same hashed values. Then the memory access time of these addresses will not be the same as in a Linked List the best case T.C = Omega(1) for the first element and worst case T.C. = O(N) for the last element in chained LL. Hence option D is also TRUE.
Ans: Option C

Q8: Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below:  (2021 SET 2)

The page size is 4 KB = (1KB = 2 ¹⁰ bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2 GB (1 GB =  2 ³⁰ bytes) virtual memory which os mapped to 2 GB of physical memory. The minimum amount of memory required for the page table of P across all levels is _________ KB
(a) 1024
(b) 4096
(c) 4108
(d) 1864
Ans: (c)
Sol: Given :

• Virtual address (VA) = 39 bits
• Page size = 4 KB
• Physical address (PA) = 2 GB
• Page table entry size (PTE) = 8 B
• Three level pages tables with address division ( 9 , 9 , 9 , 12 )

Three level pages tables with address division ( 9 , 9 , 9 , 12 ) means

• 9 most significant bits for indexing into the level-1(outer level),
• 9 bits for the level-2 index,
• 9 bits for the level-3 index, and
• 12 bits for the offset within a page.

The entries of the level-1 page table are pointers to a level-2page table, the entries of the level-2 page table are pointers to a level-3 page table, and the entries of the level-3 page table are PTEs that contain actual frame number where our desired word resides.
9 bits for a level means 2⁹ entries in one-page table of that level.
For our process P :
P is using 2GB of its VM. The rest of its VM is unused.
2 GB VM will have 2 GB / 4 KB = 2 ¹⁹ Pages .
But level 3 page table has only 2⁹ entries. So, one-page table of level 3 can point to 2⁹ pages of VM only, So, we need 2¹⁰ level- 3 page tables of process P .
So, at level- 3 , we have 2¹⁰ page tables, So, we need 2 ¹⁰ entries in Level- 2 But level 2 page table has only 2⁹ entries, so, one-page table of level 2 can only point to 2⁹ page tables of level- 3 , So, we need 2 level- 2 page tables.
So, we need 1 Level -1 page table to point to level - 2  page tables.
So, for process P , we need only 1 Level- 1 page table, 2 level- 2 page tables, and 2 ¹⁰ level- 3 page tables.
Note that All the page tables, at every level, have same size which is 2⁹ × 8 B = 2¹² B = 4 KB
(Because every page table at every level has 2⁹ entries and Page table entry size at every level is 8B)
So, in total, we need 1 + 2 + 2 ¹⁰ page tables ( 1 Level- 1 , 2 Level- 2 , 2 ¹⁰ level- 3 ) , and each page table size is 4KB
So, total page tables size  = 1027 X 4 KB  = 4108 KB
So, the answer is  4108.

Q9: In the context of operating systems, which of the following statements is/are correct with respect to paging?  (2021 SET 1)
[MSQ]
(a) Paging helps solve the issue of external fragmentation
(b) Page size has no impact on internal fragmentation
(c) Paging incurs memory overheads
(d) Multi-level paging is necessary to support pages of different sizes
Ans: (a, c)
Sol: Pages are divided into fixed size slots , so no external fragmentation
But applications smaller than page size cause internal fragmentation
Page tables take extra pages in memory. Therefore incur extra cost
Correct ans A and C

Q10: Consider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is ___________  (2020)
(a) 725
(b) 155
(c) 715
(d) 125
Ans: (b)
Sol: Given,

1. Main Memory access time: 100 ns
2. TLB lookup time: 20 ns
3. Time to transfer one page to/from disk: 5000 ns
4. TLB hit ratio: 0.95
5. Page fault rate: 0.10
6. 20 % of page faults needs to be written back to disk

Hence, effective memory access time =
 0.95(20 +100) + 0.050 {90 (20 + 100 + 100) + 0.10 [0.80 (20 +100 + 5000 +100) + 0.20 (20 +100 + 5000+5000 + 100)]}
 = 155.0 ns
If there is a TLB hit, you just need to access the memory. If there is a miss 1 TLB lookup was wasted,

1.  You need to lookup the page table for the entry and then access the required location, requiring 2 memory accesses - Assuming No Page fault occurs.
2.  If there is a page fault, Then 1 memory access was wasted (you can only know that the page is not present in memory by  checking the corresponding page entry in the page table). 80 % of the time, you'll only be fetching a page from secondary storage which takes 5000 ns, 20 % of the time, you'll need to write a dirty page back to disk and bring the page (which caused the page fault) back to main memory, requiring 5000 + 5000 ns
   
   

Q11: Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process's memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statement is TRUE?  (2020) 
(a) The hole created by first fit is always larger than the hole created by next fit.
(b) The hole created by worst fit is always larger than the hole created by first fit.
(c) The hole created by best fit is never larger than the hole created by first fit.
(d) The hole created by next fit is never larger than the hole created by best fit.
Ans: (c)
Sol: Best fit will search for the smallest block which is able to accommodate the request. So, the hole created by the Best Fit is always less than or equal to the hole created using any other method.
Worst fit search for the biggest possible block which is able to accommodate the request. It might be the case that block biggest possible block may be in the first block and both worst and first fit select the same block.
So, we can't say that hole formed by worst fit is always greater than first. The size of the hole can be same too. (B) is false
Ans: (C) Hole created by the best fit is never larger than the hole created by first fit,
The hole created by the Best Fit is equal to the hole created by first fit when the first fit happens to select the smallest block which can accommodate the required size.

Q12: Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?  (2019)
(a) 16 × 2¹⁰
(b) 256 ×2¹⁰
(c) 4 × 2²⁰
(d) 8 × 2²⁰
Ans: (b)
Sol: TLB Entry:
Memory is word  addressable
Word size = 4 Bytes
Page size = 8 KB = 2¹¹ words
Virtual Memory size = 2 ⁶⁴ words
Number of pages possible = 2⁵³
Number of bits required for Page number = 53 bits
Number of bits required for Page offset = 64 − 53 = 11 bits
At a time TLB contains 128 = 2⁷ distinct page numbers.
If a page number is found in TLB then there will be a hit for all the words (Word addresses) of that Page.
1 - page hit implies 2¹¹ distinct virtual address hits.
So 2⁷ page hit implies 2⁷ ∗ 2 ¹¹ = 2 ⁸ ∗ 2 ¹⁰ = 256 ∗ 2 ¹⁰ virtual  address hits
Option B. At most, 256 ∗ 2¹⁰ distinct virtual addresses can be translated without any TLB miss.

Q13: Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units.  (2018)
Which one of the following is the correct expression for the page fault rate experienced by the process?
(a) (D - M) / (X - M)
(b) (X - M) / (D - M)
(c) (D - X) / (D - M)
(d) (X - M) / (D - X)
Ans: (b)
Sol: Let P be the page fault rate.
Average memory access time =(1− page fault rate)×memory access time when no page fault  +  Page fault rate  × Memory access time when page fault.
X = (1 − P) M + PD
X = M + P(D −M)
P = (X - M ) / ( D - M )
(B) is the answer.

Q14: Recall that Belady's anomaly is that the pages-fault rate may increase as the number of allocated frames increases. Now consider the following statements:  (2017 SET 1)
S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady's anomaly
S2: LRU page replacement algorithm suffers from Belady's anomaly
Which of the following is CORRECT ?
(a) S1 is true, S2 is true
(b) S1 is true, S2 is false
(c) S1 is false , S2 is true
(d) S1 is false, S2 is false
Ans: (b)
Sol: 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 example, if we consider reference string 3 2 1 0 3 2 4 3 2 1 0 4 and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10 page faults.
S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady’s anomaly. -> Random page replacement algorithm can be any including FIFO so its true
S2: LRU page replacement algorithm suffers from Belady’s anomaly . -> LRU does\'nt suffer from Belady’s anomaly .
Therefore, option B is correct

Q15: In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?  (2016 SET 2)
(a) LRU(Least Recently Used)
(b) OPT (Optimal Page Replacement)
(c) MRU(Most Recently Used)
(d) FIFO(First In First Out)
Ans: (d)
Sol:  Belady’s anomaly is the phenomenon in which increasing the number of page frame results in  increase in the number of page faults.
FIFO replacement algorithm results in page faults by increasing the number of page frames.
Consider the example:
Frame = 3
String = 0 1 5 3 0 1 4 0 1 5 3 4

Number of page faults = 9
Take number of frames = 4
Number of page faults = 10

Q16: Consider a computer system with ten physical page frames. The system is provided with an accessse  quence ( a ₁ , a ₂ , . . . , a ₂₀ , a ₁ , a ₂ , . . . , a ₂₀ ) , where each a i a i  is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is ______.  (2016 SET 1)
(a) 0
(b) 1
(c) 2
(d) 3
Ans: (b)
Sol: Access sequence is  ( a ₁ , a ₂ , . . . , a ₂₀ , a ₁ , a ₂ , . . . , a ₂₀ )
a₁ to a₁₀ will result in page faults. Total 10 page faults in this.
Then a₁₁ comes, it replaces a₁₀, a₁₂ replaces a₁₁, a₁₃ replaces a₁₂ and so on,….10 page faults from a₁₁ to a₂₀.
Now when a₁ to a₉ occurs again, it will result in 0 page fault because these are already present in the page frame. Again a₁₀ will replace a₂₀, a₁₁ replaces a₁₀ and so on. So, in this way total 11 page faults from a₁₀ to a₂₀­.
Total page faults = 10 + 10 + 11 = 31
Using optimal page replacement:
a₁ to a₁₀ will result in page faults. Total 10 page faults in this.
Then a₁₁ will replace a₁₀ because from a₁ to a₁₀, a₁₀ will be used later, a₁₂ replaces a₁₁ and so on. 10 page faults from a₁₁ to a₂₀.
Again a₁ to a₉, 0 page faults. a10 will replace a₁, a₁₀ to a₁₉ will have 10 page faults.
Total page faults in this = 10 + 10 + 10 = 30
So, difference in number of page faults = 31 – 30 = 1

Q17: Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one level page table per process and each page table entry requires 48 bits, then the size of the per-process page table is _________ mega bytes.  (2016 SET 1)
(a) 384
(b) 3072
(c) 192
(d) 1536
Ans: (a)
Sol: No. of pages (N) = 2²⁶ = No. of entries in Page Table
Page Table Entry Size (E) =  6 bytes
So, Page Table Size = n x e 2²⁶ x 6 bytes =  384 MB

Q18: A processor can support a maximum memory of 4GB, where the memory is word-addressable (a word consists of two bytes). The size of the address bus of the process or is at least bits________.   (2016 SET 1)
(a) 32
(b) 31
(c) 16
(d) 15
Ans: (b)
Sol: Size of Memory = No of words (Addresses) × No of bits per word
2 ³² B = No of words (Addresses) × 2 B
No of words (Addresses) = 2 31
Number of Address lines = 31

Q19: A computer system implements 8 kilobyte pages and a 32-bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum size of the page table of a process is 24 megabytes, the length of the virtual address supported by the system is _____ bits.  (2015 SET 2) 
(a) 32
(b) 34
(c) 36
(d) 40
Ans: (c)
Sol: 8 KB pages means 13 offset bits.
For 32 bit physical address, 32 − 13 = 19 page frame bits must be there in each PTE (Page Table Entry).
We also have 1 valid bit, 1 dirty bit and 3 permission bits.
So, total size of a PTE (Page Table Entry) = 19 + 5 = 24 bits = 3 bytes.
Given in question, maximum page table size = 24 MB
Page table size = No. of PTEs × size of an entry
So, no. of PTEs = 24 MB / 3 B = 8M
Virtual address supported = No. of PTEs ∗ Page size (As we need a PTE for each page and assuming single-level paging)
= 8M ∗ 8KB
= 64 GB = 2³⁶ Bytes
So, length of virtual address supported = 36 bits (assuming byte addressing)

Q20: Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB, 210 KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are NOT allotted to any process?  (2015 SET 2)
(a) 200 KB and 300 KB
(b) 200 KB and 250 KB
(c) 250 KB and 300 KB
(d) 300 KB and 400 KB
Ans: (a)
Sol:  Option (A) is correct because we have 6 memory partitions of sizes
200 K B , 400 K B , 600 K B , 500 K B , 300 K B and 250 K B and the partition allotted to the process
using best fit is given below:
357 K B process allotted at partition 400 K B .
210 K B process allotted at partition 250 K B
468 K B process allotted at partition 500 K B
491 K B process allotted at partition
So, we have left only two partitions 200 KB and 300KB

Q21: A computer system implements a 40-bit virtual address, page size of 8 kilobytes, and a 128-entry translation look-aside buffer (TLB) organized into 32 sets each having four ways. Assume that the TLB tag does not store any process id. The minimum length of the TLB tag in bits is _________.  (2015 SET 2)
(a) 27
(b) 5
(c) 22
(d) 7
Ans: (c)
Sol:  40 − (5 + 13) = 22bits
TLB maps a virtual address to the physical address of the page. (The lower bits of page address (page offset bits) are not used in TLB as they are the same for virtual as well as physical addresses). Here, for 8KB page size we require 13 page offset bits.
In TLB we have 32 sets and so virtual address space is divided into 32 using 5 set bits. (Associativity doesn't affect the set bits as they just adds extra slots in each set).
So,  = 40 - 5 - 13 = 22
Following diagram shows how TLB and Cache works:

Q22: Consider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page replacement policies First In First Out (FIFO) and Least Recently Used (LRU)?  (2015 SET 1)
(a) Both incur the same number of page faults
(b) FIFO incurs 2 more page faults than LRU
(c) LRU incurs 2 more page faults than FIFO
(d) FIFO incurs 1 more page faults than LRU
Ans: (a)
Sol: Requested Page references are 3 , 8 , 2 , 3 , 9 , 1 , 6 , 3 , 8 , 9 , 3 , 6 , 2 , 1 , 3 and number of page frames is 5 .
In FIFO Page replacement will take place  in sequence in pattern First In first Out, as following

Number of Faults = 9.Number of Hits =6
Using Least Recently Used (LRU) page replacement will be the page which is visited least recently (which is not used for the longest time), as following:

Number of Faults =9. Number of Hits =6
So, both incur the same number of page faults.
Correct Answer:  A

Q23: Consider a system with byte-addressable memory, 32-bit logical addresses, 4 kilobyte page size and page table entries of 4 bytes each. The size of the page table in the system in megabytes is ________ .  (2015 SET 1)
(a) 1
(b) 2
(c) 4
(d) 8
Ans: (c)
Sol: Total no of pages =  2 ³² / 2 ²⁰
We need a PTE for each page and an entry is 4 bytes.
So, page table size  = 4 X 2 ²⁰ = 2²² B = 4MB .

Q24: Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is _________.  (2014 SET 3)
(a) 122
(b) 38
(c) 138
(d) 146
Ans: (a)
Sol: EMAT=TLB hit × (TLB access time + memory access time) + TLB miss(TLB access time + page table access time + memory access time)
= 0.6(10 + 80) + 0.4(10 + 80 + 80)
= 54 + 68
= 122 msec

Q25:  A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below? 4, 7, 6, 1, 7, 6, 1, 2, 7, 2  (2014 SET 3)
(a) 5
(b) 6
(c) 7
(d) 8
Ans: (b)
Sol: Total page faults = 6.

Another way of answering the same.

OR

Q26:  A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, ..., 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?  (2014 SET 2) 
(a) Least-recently-used
(b) First-in-first-out
(c) Last-in-first-out
Ans: (d) 
Sol:  It will be (D) i.e Most-recently-used.
To be clear "repeats the access sequence THRICE" means totally the sequence of page numbers are accessed 4 times though this is not important for the answer here.
If we go optimal page replacement algorithm it replaces the page which will be least used in near future.
Now we have frame size 20 and reference string is
1, 2,..., 100, 1, 2, ..., 100, 1, 2,..., 100, 1, 2, ..., 100
First 20 accesses will cause page faults - the initial pages are no longer used and hence optimal page replacement replaces them first. Now, for page 21 , according  to reference string page 1 will be used again after 100 and similarly 2 will be used after 1 so, on and so the least likely to be used page in future is page 20 . So, for 21 ^st reference page 20 will be replaced and then for 22 ^nd page reference, page 21 will be replaced and so on which is MOST RECENTLY USED page replacement policy.
PS: Even for Most Recently Used page replacement at first all empty (invalid) pages frames are replaced and then only most recently used ones are replaced.

Q27: Assume that there are 3 page frames which are initially empty. If the page reference string 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is ______  (2014 SET 1)
(a) 6
(b) 7
(c) 8
(d) 9
Ans: (b)
Sol: In Optimal page replacement a page which will be farthest accessed in future  will be replaced first.
Here, we have 3 page frames. Since, initially they are empty the first 3 distinct page references will cause page faults.
After 3 distinct page accesses we have
Based on the Next Use Order, the next replacement will be 3. Proceeding like this we get
(When multiple pages are not going to be accessed again in future, replacing any of them is allowed in Optimal page replacement algorithm)
Now, counting the misses which includes the 3 initial ones we get number of page faults as 3 + 4 =7.
Correct Answer:  7

Q28: A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table (T1) ,which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2 ) Each entry of T2 stores the base address of a page of the third-level table (T3 ) Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16 way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.
What is the minimum number of page colure needed to guarantee that no two synonyms map to different sets in the processor cache of this computer?  (2013)
(a) 2
(b) 4
(c) 8
(d) 16
Ans: (c)
Sol: Let the page size be x .
Since virtual address is 46  bits, we have total number of pages =
We should have an entry for each page in last level page table which here is T3. So,
Number of entries in T3  (sum of entries across all possible T3  tables)  
Each entry takes 32 bits = 4 bytes. So, total size of T3  tables = X 4 =  bytes
Now, no. of T2  tables will be Total size of T3  tables/page table size  and for each of these page tables, we must have a T2
 entry. Taking T3  size as page size, no. of entries across all T2  tables
=
Now, no. of T2 tables (assuming  T2 size as page size)  =
Now, for each of these page table, we must have an entry in T1 . So, number of entries in T1
=
And size of  T1 =  
Given in question, size of  T1  is page size which we took as  x. So,
x =
⇒x ⁴ = 2 ⁵² 
⇒x = 2 ¹³ = 8 KB
Min. no. of page color bits = No. of set index bits + no. of offset bits  -  no. of page index bits (This ensures no synonym maps to different sets in the cache)
We have 1 MB cache and 64 MB cache block size. So,
number of sets  = 1 MB / (64 B X Number of blocks in each set way set ) = 16 K / 16 (16  associative)
= 1 K = 2 ¹⁰.
So, we need10  index bits. Now, each block being 64 (2 ⁶)  bytes means we need 6offset bits.
And we already found page size = KB = 2 ¹³ , so  13 bits to index a page
Thus, no. of page color bits = 10 + 6 - 13 = 3.
With  3page color bits we need to have  2³ = 8 different page colors
A synonym is a physical page having multiple virtual addresses referring to it. So, what we want is no two synonym virtual addresses to map to two different sets, which would mean a physical page could be in two different cache sets. This problem never occurs in a physically indexed cache as indexing happens via physical address bits and so one physical page can never go to two different sets in cache. In virtually indexed cache, we can avoid this problem by ensuring that the bits used for locating a cache block (index + offset) of the virtual and physical addresses are the same.
In our case we have6  offset bits bits + 10 for indexing. So, we want to make these 16 bits same for both physical and virtual address. One thing is that the page offset bits - 13 bits for 8 KB page, is always the same for physical and virtual addresses as they are never translated. So, we don't need to make these 13  bits same. We have to only make the remaining 10 + 6 - 13 = 3 bits same. Page coloring is a way to do this. Here, all the physical pages are colored and a physical page of one color is mapped to a virtual address by OS in such a way that a set in cache always gets pages of the same color. So, in order to make the bits same, we take all combinations of it  (2 ³ = 8) and colors the physical pages with colors and a cache set always gets a page of one color only. (In page coloring, it is the job of OS to ensure that the3 bits are the same).

Q29: Consider the virtual page reference string  (2021)
1, 2, 3, 2, 4, 1, 3, 2, 4, 1
on a demand paged virtual memory system running on a computer system that has main memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement policy. Then
(a) O P T I M A L < L R U < F I F O
(b) OPTIMAL< LRU < FIFO
(c) OPTIMAL = LRU
(d) OPTIMAL = FIFO
Ans: (b)
Sol: Page reference string is

In FIFO, when a new page comes and there is no space left, the oldest page which came in is replaced. So, we get 6 page faults here as shown above.

In LRU, when a page comes and there is no space left, the oldest referenced page (unlike the oldest incoming one as in FIFO) gets replaced. So, we get 9page replacements as shown above. (The boxed digits shows the LRU number with 1 being the least recently used one followed by 2 and so on)

In optimal page replacement when a new page comes and there is no space, the page which is going to be referenced the latest in future will be replaced. So, we get 5 page replacements as shown above (In the last part of the page replacement, future references are simply assumed and the boxed digits shows the future replacement order with 1 being the one to get replaced first).
So we get
OPTIMAL< LRU < FIFO
Option B.

Q30: Let the page fault service time be 10ms in a computer with average memory access time being  20ns. If one page fault is generated for every 1 0 ⁶ memory accesses, what is the effective access time for the memory?  (2011)
(a) 21ns
(b) 30ns
(c) 23ns
(d) 35ns
Ans: (b)
Sol: The correct option is b 30 ns
Effective access time = [(1 - p)* access time when no page fault +p* access time during page fault]
=* 20 ns + 
=* 20 ns + ∗ 10 ∗ 10⁶ns ≈ 30 ns

Q30: A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur?  (2010)
(a) 196
(b) 192
(c) 197
(d) 195
Ans: (a)
Sol: When we access 100 distinct page in some order (for example 1 , 2 , 3 … 100 ) then total number of page faults = 100 . At last, the 4 page frames will contain the pages 100 , 99 , 98 and 97 . When we reverse the string ( 100 , 99 , 98 , … , 1 ) then first four page accesses will not cause the page fault because they are already present in page frames. But the remaining 96 page accesses will cause 96 page faults. So, total number of page faults = 100 + 96 = 196 .