Virtual Memory

Question 1

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?

       Operating-Systems       Virtual Memory       Gate 2018
Question 1 Explanation: 
Let ‘P’ be page fault rate then, average memory access time
X = (1 - P)M + D × P
X = M ∙ PM + DP
(X - M) = P(D - M)
⇒ P = (X - M) / (D - M)
Question 2
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 _________.
       Operating-Systems       Virtual Memory       GATE 2015 -(Set-2)
Question 2 Explanation: 
22 bits
Question 3
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.  
       Operating-Systems       Virtual Memory       GATE 2015 -(Set-2)
Question 3 Explanation: 
Given page size = 8KB = 213B
PAS = 32 bit
∴ No. of frames =PA/Page size = 232 / 213 = 219
Also, it is given that each page table entry contains a valid bit, a dirty bit, 3 permission bits:
= 5 bits reserved
So one Page table entry size is
= 19+5 = 24 bits = 3 bytes
Now, Page table size = No. of entries × Entry size
24 × 220 = No. of entries × 3
No. of entries = 8 × 220 = 2 23
∴ Virtual Address size = No. of entries × Page size = 223 × 213 = 236
∴ Virtual Address Space = 36 bits
Question 4
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because
It reduces the memory access time to read or write a memory location.
It helps to reduce the size of page table needed to implement the virtual address space of a process.
It is required by the translation lookaside buffer.
It helps to reduce the number of page faults in page replacement algorithms.
       Operating-Systems       Virtual Memory       2009
Question 4 Explanation: 
In multilevel page table size is too big to fit in contiguous space then page tables are to be divided into different levels.
Question 5
In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is
Before effective address calculation has started
During effective address calculation
After effective address calculation has completed
After data cache lookup has completed
       Computer-Organization       Virtual Memory       Gate-2008
Question 5 Explanation: 
TLB is a mini page table and it contains the frequently accessed page table entries. Because logical address is effective address, only after we calculate what is the effective address we can access the TLB. Hence option C is the correct answer.
Question 6
20, 20 and 20
24, 24 and 24
24, 24 and 20
25, 25 and 24
       Operating-Systems       Virtual Memory       Gate-2008
Question 6 Explanation: 
Virtual address size = 32 bits
From the question we can see the below info:
Physical address size = 36 bits
Physical memory size = 236 bytes
Page frame size = 4K bytes = 212 bytes
No. of bits for offset = 12
No. of bits required to access physical memory frame = 36 – 12 = 24
So in third level of page table, 24 bits are required to access an entry.
In second level page table entry -- 9 bits of virtual address are used to access second level page table entry and size of pages in second level is 4 bytes.
So size of second level page table is (29)*4 = 211 bytes. It means there are (236)/(211) possible locations to store this page table. Therefore the second page table requires 25 bits to address it. the first page table needs 25 bits.
Answer - D
First level
Question 7
A paging scheme uses a Translation Look-aside Buffer (TLB). A TLB-access takes 10 ns and a main memory access takes 50 ns. What is the effective access time(in ns) if the TLB hit ratio is 90% and there is no page-fault?
       Operating-Systems        Virtual Memory       Gate 2008-IT
Question 7 Explanation: 
EMAT = TLB access time + Miss ratio × Main memory access time + Main memory access time
= 10 + 0.1 × 50 + 50
= 10 + 5 + 50
= 65
Question 8
I-d, II-a, III-b, IV-c
I-b, II-c, III-a, IV-d
I-c, II-d, III-a, IV-b
I-b, II-c, III-d, IV-a
       Operating-Systems       Virtual Memory       Gate 2008-IT
Question 8 Explanation: 
Dirty bit:
The bit indicates that its associated block of memory has been modified and has not been saved to storage yet. Dirty bits are used by the CPU cache and in the page replacement algorithms of an operating system.
R/W bit:
If the bit is set, the page is read/ write. Otherwise when it is not set, the page is read only.
Reference bit:
Reference bit is used in a version of FIFO called second chance policy, in order to avoid replacement of heavily used page.
Valid bit:
Valid bit is not used for page replacement. It is not used in any page replacement policy. It tells the page in the memory is valid or not. If it is valid it is directly used and if it is not then a fresh page is loaded. So, basically it is page initialization, because we are not replacing, it is initializing, we not knocking out somebody, we are filling empty space. So initialization and so option (D).
Question 9
A CPU generates 32-bit virtual addresses. The page size is 4 KB. The processor has a translation look-aside buffer (TLB) which can hold a total of 128 page table entries and is 4-way set associative. The minimum size of the TLB tag is:
11 bits
13 bits
15 bits
20 bits
       Operating-Systems       Virtual Memory       Gate-2006
Question 9 Explanation: 
Page size = 4 KB = 4 × 210 Bytes = 212 Bytes
Virtual Address = 32 bit
No. of bits needed to address the page frame = 32 - 12 = 20
TLB can hold 128 page table entries with 4-way set associative
⇒ 128/4=32=25
→ 5 bits are needed to address a set.
→ The size of TLB tag = 20 - 5 = 15 bits
Question 10
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?
Efficient implementation of multi-user support is no longer possible
The processor cache organization can be made more efficient now
Hardware support for memory management is no longer needed
CPU scheduling can be made more efficient now
       Operating-Systems       Virtual Memory       Gate-2006
Question 10 Explanation: 
→ When designer decides to get rid of virtual memory entirely then hardware support is no longer needed.
→ Because special hardware support needed only for virtual memory.
Question 11
The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by
the instruction set architecture
page size
physical memory size
number of processes in memory
       Operating-Systems       Virtual Memory       Gate-2004
Question 11 Explanation: 
→ Based on Instruction Set Architecture each process can be need minimum no. of pages.
→ An ISA permits multiple implementations that may vary in performance, physical size and monetary cost.
Question 12

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?

645 nanoseconds
1050 nanoseconds
1215 nanoseconds
2060 nanoseconds
       Operating-Systems       Virtual Memory       Gate-2004
Question 12 Explanation: 
Effective average instruction time = CPU time + 2 EMAT
= 100ns + 2EMAT
Now lets calculate EMAT,
EMAT = TLB + miss rate × 2 × 150ns + 150ns + 1/10000 × 8ms
= 0 + 0.1 × 300ns + 150ns + 800ns
= 980ns
∴ Effective average instruction time,
= 100ns + 2 × 980ns
= 2060ns
Question 13
In a system with 32 bit virtual addresses and 1KB page size, use of one-level page tables for virtual to physical address translation is not practical because of  
the large amount of internal fragmentation
the large amount of external fragmentation
the large memory overhead in maintaining page tables
the large computation overhead in the translation process
       Operating-Systems       Virtual Memory       Gate-2003
Question 13 Explanation: 
Page size = 1KB
Virtual address = 32 bit = 232
No. of page level entries = 232 / 210
= 222
= 4M (Too large size)
Question 14

1.5 ns
2 ns
3 ns
4 ns
       Operating-Systems       Virtual Memory       Gate-2003
Question 14 Explanation: 
The possibilities are = (TLB Hit * Cache Hit) + (TLB Hit * Cache Miss)
(TLB Miss * Cache Hit) + (TLB Miss * Cache Miss)
= (0.96*0.9*2)+(0.96*0.1+12)
= 3.8
= 4 (approximately)
Question 15

8 KB
12 KB
16 KB
20 KB
       Operating-Systems       Virtual Memory       Gate-2003
Question 15 Explanation: 
Breakup of given addresses into bit form:-
32bits are broken up as 10bits (L2) | 10bits (L1) | 12bits (offset)
First code page:
0x00000000 = 0000 0000 00 | 00 0000 0000 | 0000 0000 0000
So next code page will start from
0x00001000 = 0000 0000 00 | 00 0000 0001 | 0000 0000 0000
First data page:
0x00400000 = 0000 0000 01 | 00 0000 0000 | 0000 0000 0000
So next data page will start from
0x00401000 = 0000 0000 01 | 00 0000 0001 | 0000 0000 0000
Only one stack page:
0xFFFFF000 = 1111 1111 11 | 11 1111 1111 | 0000 0000 0000
Now, for second level page table, we will just require 1 Page
which will contain following 3 distinct entries i.e. 0000 0000 00, 0000 0000 01, 1111 1111 11.
Now, for each of these distinct entries, we will have 1-1 page in Level-1.
Hence, we will have in total 4 pages and page size = 212 = 4KB.
Therefore, Memory required to store page table = 4*4KB = 16KB.
Question 16

Suppose the time to service a page fault is on the average 10 milliseconds, while a memory access takes 1 microsecond. Then a 99.99% hit ratio results in average memory access time of

1.9999 milliseconds
1 millisecond
9.999 microseconds
1.9999 microseconds
       Operating-Systems       Virtual Memory       Gate-2000
Question 16 Explanation: 
Average memory access time = (P*t1) + [(1-P)t2]
= (0.9999*1) + [(1-0.9999) *10000]
= (0.9999) + (0.0001 * 10000)
= 0.9999 + 1
= 1.9999 microseconds
Question 17
A  multi-user,  multi-processing  operating  system  cannot  be  implemented  on hardware that does not support  
Address translation
DMA for disk transfer
At least two modes of CPU execution (privileged and non-privileged)
Demand paging
Both A and C
       Operating-Systems       Virtual Memory       Gate-1999
Question 17 Explanation: 
Address translation and atleast two modes of CPU execution (Privileged and non-privileged) are needed to implement multiuser and multiprocessing operating system, because address translation provides memory protection which ensures that a given process does not interfere with another, and we need privileged and non-privileged instruction, so that user and OS interconnects properly.
Question 18
Which of the following is/are advantage of virtual memory?
Faster access to memory on an average.
Processes can be given protected address spaces.
Linker can assign addresses independent of where the program will be loaded in physical memory.
Programs larger than the physical memory size can be run.
Both B and D
       Operating-Systems       Virtual Memory       Gate-1999
Question 18 Explanation: 
A) False. Because in virtual memory concept address translation is required due to which access is slow.
B) True. Because in virtual memory concept of address translation provides protected address space so that one process do not interfere the other process.
C) False.
D) True.
Question 19

If an instruction takes i microseconds and a page fault takes an additional j microseconds, the effective instruction time if on the average a page fault occurs every k instruction is:

       Operating-Systems       Virtual Memory       Gate-1998
Question 19 Explanation: 
Effective memory access time
= service time + page fault rate * page fault service time
= i + 1/k * j
= i + j/k
Question 20
Dirty bit for a page in a page table
helps avoid unnecessary writes on a paging device
helps maintain LRU information
allows only read on a page
None of the above
       Operating-Systems       Virtual memory       Gate-1997
Question 20 Explanation: 
The dirty bit allows for a performance optimization i.e., Dirty bit for a page in a page table helps to avoid unnecessary writes on a paging device.
Question 21
A 1000 Kbyte memory is managed using variable partitions but to compaction. It currently has two partitions of sizes 200 Kbytes and 260 Kbytes respectively. The smallest allocation request in Kbytes that could be denied is for
       Operating-Systems       Virtual Memory       Gate-1996
Question 21 Explanation: 
200 and 260 are already hold by some other processes. Now we have to model the partition in such a way so that smallest allocation request could be denied. So, we can do the division as,

So, smallest allocation request which can be denied is 181 KB.
Question 22
In a virtual memory system the address space specified by the address lines of the CUP must be __________ than the physical memory size and _______ than the secondary storage size.
smaller, smaller
smaller, larger
larger, smaller
larger, larger
       Operating-Systems       Virtual Memory       Gate-1995
Question 22 Explanation: 
Primary memory < Virtual memory < Secondary memory.
Question 23
Which of the following statements is false?
Virtual memory implements the translation of a program’s address space into physical memory address space
Virtual memory allows each program to exceed the size of the primary memory
Virtual memory increases the degree of multiprogramming
Virtual memory reduces the context switching overhead
       Operating-Systems       Virtual Memory       Gate-2001
Question 23 Explanation: 
In a system with virtual memory context switch includes extra overhead in switching of address spaces.
Question 24
the length of MAR
the available secondary storage
the available main memory
all of the above
none of the above
Both A and B
       Operating-Systems       Virtual Memory       Gate-1991
Question 24 Explanation: 
Virtual memory is independent of size of main memory and depends on available secondary storage.
MAR can hold the address that is generated from CPU and limits the total virtual memory address space.
Question 25
The amount of virtual memory available is limited by the availability of secondary storage.
Any implementation of a critical section requires the use of an indivisible machine-instruction, such as test-and-set.
The LRU page replacement policy may cause hashing for some type of programs.
The best fit techniques for memory allocation ensures the memory will never be fragmented.
B and D
       Operating-Systems       Virtual Memory       Gate-1991
Question 25 Explanation: 
(A) Is true.
(B) Is false, because one of the solution is Peterson's solution which is purely software based solution without use of hardware.
(C) Is true.
(D) False, memory can get fragmented with best fit technique.
There are 25 questions to complete.