Test: Paging - Computer Science Engineering (CSE) MCQ

Concept:
Free space management:
For the purpose of assigning space to newly generated files, the system maintains track of the free disc blocks. Additionally, managing free space becomes essential in order to utilize the space made available by removing the files. The disc blocks that are not assigned to any files or directories are tracked by the system in a list called free space.

Free space management is implemented mainly as:

• Bitmap or Bit vector
• Linked List
• Grouping
• Counting
• Space Maps

Paging is a memory management strategy that avoids the necessity for contiguous physical memory allocation. This approach allows a process's physical address space to be non-contiguous.
Hence the correct answer is Paging.

Concept:
Contiguous memory management:
A traditional memory allocation model is contiguous memory allocation. In this case, a system gives a process access to successive memory blocks, or memory blocks with consecutive addresses. One of the earliest types of memory allocation is contiguous memory allocation.

There are three types of contiguous memory management:

• Over lays
• Partition
• Buddy system

Paging is a non-contiguous memory allocation technique that divides secondary and main memory into equal-size divisions. Secondary memory partitions are referred to as pages, whilst major memory partitions are referred to as frames.
Hence the correct answer is Paging.

Concept:
The given data,
Number of pages = 4 K
Page size PS = 512 B = 2⁹ Bytes
Number of pages = Logical address space / Page size
Logical address space = Number of pages X  Page size
Logical address space = 4 K X 2⁹ Bytes
Logical address space = 2¹² X 2⁹ Bytes
Logical address space = 2²¹ Bytes
Logical address bits  or Virtual address bits = 21
Hence the correct answer is 21.

Concept:
Paging is a memory management scheme. Paging reduces the external fragmentation. Size of the page table depends upon the number of entries in the table and bytes stored in one entry.

S1: A small page size causes large page tables.
This statement is correct. Smaller page size means more pages required per process. It means large page tables are needed.

S2: internal fragmentation is increased with small pages.
Internal fragmentation means when process size is smaller than the available space. When pages are small, then available space becomes less and there will be less chances of internal fragmentation.

S3: I/O transfers are more efficient with large pages.
An I/O system is required to take an application I/O request and send it to the physical device. Transferring of I/O requests are more efficient with large pages. So, given statement is correct.

Data
page table entries = 64
page table entry size = 11 bit
page size = 512 bytes

Formula:
Size of physical address = pagging bits + offset bits

Calculation:
paging bits = 11 - 1 = 10(as 1 valid bit is also included)
offset bits = log₂ (512) = 9 bits
size of physical address = 10 + 9 = 19 bits
Hence the correct answer is 2¹⁹.

Page size = 2¹³ Bytes = Frame size

Hence in the page table:

= 8 × 2²⁰ = 2²³
Hence all entries can be addressed by 23 bits.
Thus total size of virtual address = 23 + 13
= 36 bits.

Concept:
To minimize the need for contiguous allocation of physical memory, paging is used.
Logical address space or virtual address space is the set of all logical addresses generated by the program.
Physical addresses are the actual addresses available in memory.
Physical address space is the set of all physical addresses generated by the program.
Mapping of the virtual address to physical address is done by hardware device i.e. Memory Management Unit (MMU) & is called paging technique.
Physical Address space is divided into fixed-size no. of blocks called frames.
The logical address space is divided into fixed-size no. of blocks called pages.

Calculation:
Page table entry size = 32 bits or 4 Bytes
No. of entries in one page = 2^p/4  
VAS = 46 bits
Consider size of page = 2^p Bytes
Virtual address space (VAS) = No. of entries x page size
No. of entries for one level Page table (PT) = 2^p ×4
Therefore, for 3 levels PT  

2⁴⁶ x 2⁶ = 24p
2⁵² = 2⁴p
52 = 4p
P = 13
So, the page size is 2¹³ or 8KB.
Hence, the correct answer is “option 3”.

Data
1 word (W) = 1 byte (B)
Logical address = 232 B
page size = 4 KB = 212 B
page table entry (PTE) = y B

Formula:
Page table size (PTS) = number of pages × y

Calculation:
number of pages = 2³²/2¹²  = 2²⁰   
Page table size (PTS) = number of pages × y
PTS = 2²⁰ × 4B
∴ PTS = 4 MB
Important points
1 MB = 2²⁰ B
where B stands for byte

Concept:
Internal fragmentation:
Internal fragmentation occurs when memory is divided into fixed-sized blocks. Internal fragmentation occurs when the memory assigned to the process is somewhat larger than the memory requested.

The given data,
Size of page = 4 KB
Size of process = 38 KB
The number of pages required by process = (38 KB)/(4 KB) = 9.5 
So, the number of pages required by the process is 10.
But required = 38 KB
Here 10 x 4 = 40 KB 
40 – 38 = 2 KB is the internal fragmentation.
Hence the correct answer is 2.

Concept:
The given data,
Logical address space = 2⁶⁴ Bytes.
Physical address space = 2⁴⁸ Bytes.
Page size PS = 16 K = 2⁴ x 2¹⁰ B = 2¹⁴ Bytes.
Number of pages = Logical address space / Page size 
Number of pages = 2⁶⁴ / 2¹⁴ 
Number of pages = 2⁵⁰

The page table entry is the number number of bits required to get any frame number.
Number of frames = Physical address space / Page size 
Number of frames = 2⁴⁸ /  2¹⁴ 
Number of frames = 2³⁴
Hence the correct answer is 2³⁴.