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       Video-Explanation
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       GATE 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

A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows

    • Bits 30-31 are used to index into the first level page table
    • Bits 21-29 are used to index into the second level page table
    • Bits 12-20 are used to index into the third level page table, and
    • Bits 0-11 are used as offset within the page

The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively.

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 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 7 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 8

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 8 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 9

he 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 9 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 10

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 10 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
There are 10 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact to get access