Paging and Segmentation Questions and Answers

Answer: A

The maximum number of page table entries is \(2^{21}\).

A single-level page table needs one entry for each page of the logical address space. The page size is \(2048 = 2^{11}\) bytes, so 11 of the 32 logical address bits are the offset within a page:

\[ \text{entries} = \frac{2^{32}}{2^{11}} = 2^{21} \]

The 20-bit physical address decides the number of frames, \(2^{20}/2^{11} = 2^{9}\), and the width of each entry, but not how many entries there are. \(2^{20}\) wrongly takes the physical address width, and \(2^{22}\) and \(2^{24}\) assume smaller pages.

Answer: B

The operating system keeps a page table for each process.

Each process has its own logical address space, so each needs its own mapping from page numbers to frame numbers. The page table's location is saved in the process control block, and on a context switch the operating system loads the new process's page table base register.

Threads of one process share its address space and therefore its page table. A table per instruction or per address would make no sense, since the page table itself is what maps addresses.

Answer: C

The list that causes no page fault is 1020, 3012, 6120, 8100.

With 1K = 1024 words per page, the page number of an address is the integer part of address / 1024. The pages in memory are 0, 2, 5 and 7.

• 1020 → page 0; 3012 → page 2; 6120 → page 5; 8100 → page 7. All four are resident.
• A: 1024 is the first word of page 1, which is not resident.
• B: 1234 is on page 1, a fault.
• D: 2021 is on page 1 as well (page 2 starts at 2048).

Only option C keeps every reference inside a resident page.

Answer: C

The logical and physical addresses need 15 and 14 bits.

\[ \begin{aligned} \text{logical space} &= 64 \times 512 = 2^{6} \times 2^{9} = 2^{15} \\ \text{physical space} &= 32 \times 512 = 2^{5} \times 2^{9} = 2^{14} \end{aligned} \]

So a logical address needs 15 bits (6 for the page number and 9 for the offset) and a physical address 14 bits (5 for the frame number and 9 for the offset).

Option A reverses the two. 29 and 32 come from multiplying or adding the wrong quantities rather than taking logarithms.

Answer: A

The true statement is that segmentation allows different segments to grow independently.

Segmentation divides a program into logical units of variable length, such as code, data, heap and stack, each with its own base and size. Because each segment is separate, a growing stack or table can be enlarged on its own without disturbing the others, which suits the programmer's view of memory.

The segment table stores both a base and a limit for each segment, and the limit is checked on every access, so option B is false. Only some systems combine segmentation with paging, so 'in all systems' is wrong. And because segments have variable sizes, segmentation suffers from external fragmentation rather than eliminating it; paging is what removes it.

Answer: B

The pages are 4 KB.

The virtual address is split into the top-level index, the second-level index and the offset within the page. The offset bits fix the page size.

\[ \begin{aligned} \text{offset} &= 32 - 9 - 11 = 12\ \text{bits} \\ \text{page} &= 2^{12} = 4096\ \text{bytes} \\ &= 4\ \text{KB} \end{aligned} \]

2 KB would need an 11-bit offset and 8 KB a 13-bit offset. The trap is to use one of the table fields as the offset; 11 bits gives 2 KB.

Answer: C

If the virtual address space is the same size as the physical address space, programs never need more memory than there is, so virtual memory can be dropped. Then the hardware that translates virtual addresses into physical ones, the memory management unit with its page tables, would not be needed for translation; this is the key's choice, option (C). Multiuser support can still be efficient, the cache does not become more efficient for this reason, and CPU scheduling is not affected by the absence of virtual memory.