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?
(D-M)/(X-M) | |
(X-M)/(D-M) | |
(D-X)/(D-M) | |
(X-M)/(D-X) |
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)
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 _________.
22 | |
23 | |
24 | |
25 |
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.
36 | |
37 | |
38 | |
39 |
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
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.
|
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 |
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
20, 20 and 20
| |
24, 24 and 24
| |
24, 24 and 20
| |
25, 25 and 24
|
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
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?
54 | |
60 | |
65 | |
75 |
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
= 10 + 0.1 × 50 + 50
= 10 + 5 + 50
= 65
Question 8 |
Match the following flag bits used in the context of virtual memory management on the left side with the different purposes on the right side of the table below.
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 |
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).
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 |
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
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 |
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.
→ 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
|
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.
→ 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 |
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
= 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
|
Question 13 Explanation:
Page size = 1KB
Virtual address = 32 bit = 232
No. of page level entries = 232 / 210
= 222
= 4M (Too large size)
Virtual address = 32 bit = 232
No. of page level entries = 232 / 210
= 222
= 4M (Too large size)
Question 14 |
A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns. Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest 0.5 ns)
1.5 ns | |
2 ns | |
3 ns
| |
4 ns |
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)
(0.04*0.9*2)+(0.04*0.1*32)
= 3.8
= 4 (approximately)
(TLB Miss * Cache Hit) + (TLB Miss * Cache Miss)
= (0.96*0.9*2)+(0.96*0.1+12)
(0.04*0.9*2)+(0.04*0.1*32)
= 3.8
= 4 (approximately)
Question 15 |
A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns. Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address 0x00000000, two contiguous data pages starting at virtual address 0×00400000, and a stack page starting at virtual address 0×FFFFF000. The amount of memory required for storing the page tables of this process is:
8 KB | |
12 KB
| |
16 KB | |
20 KB |
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.
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 |
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
= (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 |
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 |
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.
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:
 | |
 | |
 | |
 |
Question 19 Explanation:
Effective memory access time
= service time + page fault rate * page fault service time
= i + 1/k * j
= i + j/k
= 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 |
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
151 | |
181 | |
231 | |
541 |
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.
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 |
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 |
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 |
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.
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 |
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.
(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.