Subjects Subjects About Login

OS : Memory Management

Questions : 25


QID : 37GATE-2017, 1M

Consider a two-level cache hierarchy L1 and L2 caches. An application incurs 1.4 memory accesses per instruction on average. For this application, the miss rate of L1 cache is 0.1, the L2 cache experiences on average 7 misses per 1000 instructions. The miss rate of L2 expressed correct to two decimal places is ___

Ans : 0.05
Solution :

QID : 39GATE-2017, 2M

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:

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.

Options:
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 : Option B
Solution :
Random page replacement algorithm means it can behave like any page replacement algo including FIFO which suffers from Belady's anomaly.
QID : 46GATE-2016, 1M

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 processor is at least ____ bits.

Ans : 31
Solution :

QID : 50GATE-2016, 2M

Consider a computer system with ten physical page frames. The system is provided with an access sequence
(a1 ,a2, ..., a20 ,a1 ,a2 ,..., a20), where each ai 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 ____.

Ans : 1
Solution :

QID : 52GATE-2018, 1M

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.

Which one of the following is the correct expression for the page fault rate experienced by the process?

Options:
A) (D – M) / (X – M)
B) (X – M) / (D – M)
C) (D – X) / (D – M)
D) (X – M) / (D – X)
Ans : Option B
Solution :
let, Page Fault Rate = p

Avg Main Mem. Access Time
= X (Given) = (1-p)*M + p*D

Therefore,
X = M – pM + pD
X-M = p(D - M)
p = (X - M) / (D - M)
QID : 91GATE-2016, 1M

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?

Options:
A) LRU (Least Recently Used)
B) OPT (Optimal Page Replacement)
C) MRU (Most Recently Used)
D) FIFO (First In First Out)
Ans : Option D
Solution :
Belday's Anamoly may occur in FIFO only, which states that increase in number of frams may increase the page fault rate in some cases.

e.g:
Reference String: 1,2,3,4,1,2,5,1,2,3,4,5
With 3 frames, we get 9 Page Faults.
With 4 frames, we get 10 Page Faults.
.
QID : 123GATE-2015, 1M

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 _____

Ans : 4
Solution :

QID : 134GATE-2015, 2M

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)?

Options:
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 : Option A
Solution :

QID : 136GATE-2015, 2M

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?

Options:
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 : Option A
Solution :
A-200 KB,
B-400 KB,
C-600 KB,
D-500 KB,
E-300 KB and
F-250 KB

Processes:
P1-357 KB,
P2-210 KB,
P3-468 KB and
P4-491 KB

Allocation with best Fit algorithm:
P1-B
P2-F
P3-D
P4-C

Partitions Remaining: A and E i.e. 200KB and 300KB
QID : 142GATE-2015, 2M

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

Ans :
Solution :
From Diagram and given condition:

Size of Page table <= 24 MB
i.e. N * 3 Bytes <= 24 * 2^20 B
So, N = 2^23

Thus, P = log 2^23 = 23

So, LA = 23+13 = 36 bits long
QID : 151GATE-2014, 2M

Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is _____

Ans : 7
Solution :
QID : 155GATE-2014, 2M

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?

Options:
A) Least-recently-used
B) First-in-first-out
C) Last-in-first-out
D) Most-recently-used
Ans : Option D
Solution :
QID : 157GATE-2014, 1M

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

Ans : 6
Solution :
QID : 160GATE-2014, 2M

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 ____.

Ans : 122
Solution :
QID : 247GATE-2012, 2M

Consider the virtual page reference string

1, 2, 3, 2, 4, 1, 3, 2, 4, 1

On a demand paged virtual memory system running on a computer system that main memory size of 3 pages frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacements policy. Then

Options:
A) OPTIMAL < LRU < FIFO
B) OPTIMAL < FIFO < LRU
C) OPTIMAL = LRU
D) OPTIMAL = FIFO
Ans : Option B
Solution :
QID : 257GATE-2010, 1M

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?

Options:
A) 196
B) 192
C) 197
D) 195
Ans : Option A
Solution :
For first 100 pages (lets number from 1 to 100), page fault will occur.
Then in reverse order of access, for 4 pages (100, 99, 98 and 97), there will be no page fault because last 4 pages will already be in frames.

and for 96 to 1, page faults will occur.

Total Page faults: 196
QID : 261GATE-2009, 1M

The essential content(s) in each entry of a page table is / are

Options:
A) Virtual page number
B) Page frame number
C) Both virtual page number and page frame number
D) Access right information
Ans : Option B
Solution :
The main purpose of page table is to store the frame number.
Its not necessary to store the page number in page table because the index of each row in table itself indicates the page number.
QID : 265GATE-2009, 1M

A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because

Options:
A) It reduces the memory access time to read or write a memory location.
B) It helps to reduce the size of page table needed to implement the virtual address space of a process.
C) It is required by the translation lookaside buffer.
D) It helps to reduce the number of page faults in page replacement algorithms.
Ans : Option B
Solution :
Size of the first level page table may become too large which is OS can't afford to store in Main Memory. So multilevel paging is required to divide the fist level PT in multiple parts and then load only the required part using second level page table.

Consider a system with PAS = 2^20  bytes with segmented paging architecture. The PAS is divided into 8 equal size segments. Paging is applied on segments. Page tables of segments are stored in main memory. Page table entry size is 2 bytes. Page size is power of 2. What must be the page size in bytes, such that the page table of a segment exactly fits in 1 page.

Options:
A) 128
B) 256
C) 512
D) 1024
Ans : Option C
Solution :
Size of a segment = PAS / no of segments
= 2^20 bytes / 8
= 2^17 bytes


let page size = 2^k bytes
number of pages = 2^17 / 2^k
= 2^(17-k)

Size of page table = 2^(17-k) * 2 bytes
= 2^(18-k) bytes

As give, page table size = page size
2^(18-k) bytes = 2^k bytes

Thus, k=9
so, page size = 2^9 = 512 bytes.

Consider a process in Demand Page environment having a reference string of length 'L' in which 'K' unique pages occur. Calculate the lower bound and upper bound of the number of page faults for this process. Assume process is allocated 'Z' frames

Options:
A) Max page faults = L
Min page faults = K
B) Max page faults = L-1
Min page faults = K
C) Max page faults = L
Min page faults = K-1
D) Max page faults = L-1
Min page faults = K-1
Ans : Option A
Solution :
If Z=1, means only 1 frame, then, page faults = L (which is Max)
if Z > K, means we have enough frames to accommodate all unique pages, then page faults = K (which is min)

Consider a system with VAS = PAS = 2^16 Bytes.
Page Size = 512 Bytes
The size of page table entry is 32 bits
If the page table entry contains besides other information 1 V/I bit, 1 Reference bit, 1 Modified bit, 3 bits for page protection. How many bits can be assigned for storing other attributes of the page. Also compute the page table size in Bytes.

Options:
A) 20 bits, 1KB
B) 19 bits, 512B
C) 18 bits , 256B
D) 17 bits, 128B
Ans : Option B
Solution :


A process refers n unique pages numbered from 1 to n in the order and then it refers them back in the reverse order. Process is allocated 'k' frames. Calculate the number of page faults using FIFO replacement with pure demand paging.

Options:
A) n, if k >= n
2n - k, if k < n
B) n-1, if k >= n
2n - k, if k < n
C) n, if k >= n
2n - k -1, if k < n
D) n -1 , if k >= n
2n - k -1 , if k < n
Ans : Option A
Solution :
if we have n or more frames, then only n page faults,

if we have less than n frames, 2n-k page faults.
QID : 285GATE-2007, 2M

A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements:

P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.
Q: Some programs do not exhibit locality of reference.

Which one of the following is TRUE?

Options:
A) Both P and Q are true, and Q is the reason for P
B) Both P and Q are true, but Q is not the reason for P
C) P is false, but Q is true
D) Both P and Q are false
Ans : Option B
Solution :
QID : 290GATE-2006, 2M

A computer system supports 32-bit virtual addresses as well as 32-bit physical addresses. Since the virtual address space is of the same size as the physical address space, the operating system designers decide to get rid of the virtual memory entirely. Which one of the following is true?

Options:
A) Efficient implementation of multi-user support is no longer possible
B) The processor cache organization can be made more efficient now
C) Hardware support for memory management is no longer needed
D) CPU scheduling can be made more efficient now
Ans : Option C
Solution :
Since the logical address is same the physical address, there is no conversion address needed.
QID : 311GATE-2004, 2M

Consider a system with a two-level paging scheme in which a regular memory access takes 150 nanoseconds, and servicing a page fault takes 8 milliseconds. An average instruction takes 100 nanoseconds of CPU time, and two memory accesses. The TLB hit ratio is 90%, and the page fault rate is one in every 10,000 instructions. What is the effective average instruction execution time?

Options:
A) 645 nanoseconds
B) 1050 nanoseconds
C) 1215 nanoseconds
D) 1230 nanoseconds
Ans : Option D
Solution :
Main Memory Access Time = m = 150 ns

Time for One Instruction = i = 100 ns + 2 mem accesses
= 100ns + 2*150 ns
= 400 ns

TLB Hit Ratio = 90%
so, out of 10,000 instructions, TLB is missed 1000 times
TLB access time is not given, consider its ZERO

Page Fault Rate = 1/10000
So, out of 10,000 instructions, only for 1 instruction page fault occurs.
Page Fault Service time = 8ms = 8000,000 ns


Lets calculate Total Execution time for all 10,000 instructions including TLB and Page Fault overhead.

Total Time = Actual Instruction Time
+ Overhead when TLB is missed
+ Overhead when Page fault

= [10,000 * 400 ]
+ [1000 * 300] (because its 2 level paging, its TLB + 2m)
+ [1 * 8000000]

= 1230,0000 ns

So, Average = 1230,0000 / 10,000
= 1230 ns
 

Have a Question?


Submit Here

Previous GATE Papers


Year Key Organized by
2019 Key IIT Madras
2018 Key IIT Guwahati
2017(Set1) Key IIT Roorkee
2017(Set2) Key IIT Roorkee
2016(Set1) Key IISc
2016(Set2) Key IISc
Show All