Memory Management Questions and Answers

Answer: A

Correct answer: A smaller page table

A larger page size means fewer pages for a given address space, so the page table is smaller - which saves memory and improves TLB coverage, since each entry maps more of the address space. Larger pages also make disk transfers more efficient, because reading one large block costs little more than reading a small one once the seek is paid for. The costs run the other way. Internal fragmentation rises, since the waste is on average half a page per process, so the second option is precisely backwards. And more data is transferred that may never be used, since a fault brings in the whole page. Protection also becomes coarser: permissions apply per page, so a larger page is a blunter instrument. The trade-off has settled on 4 KB for most systems, with support for huge pages of 2 MB or 1 GB where a workload - a large database, a virtual machine host - benefits from the reduced TLB pressure. Page size is always a power of two, so that address division needs no arithmetic.

Answer: D

Correct answer: a program tends to access a small portion of its address space at any time

Locality of reference is the observed tendency of programs to concentrate their memory accesses in a small region of their address space over any short interval. It has two forms. Temporal locality: a location just referenced is likely to be referenced again soon - loop counters, frequently called routines. Spatial locality: locations near one just referenced are likely to be needed next - sequential instructions, elements of an array. It arises from how programs are written: loops, sequential execution, and data structures traversed in order. Its importance is that the entire memory hierarchy depends on it. Cache, the TLB and demand paging all work by keeping a small active portion in fast storage, and every one of them would be useless if accesses were uniformly random. The working set model is the formal expression of the same observation. It also explains why some algorithms are far faster than their instruction counts suggest - traversing an array beats traversing a linked list of the same length.

Answer: C

Correct answer: a page number and an offset within the page

A logical address in a paged system splits into a page number and an offset. The page number indexes the page table to yield a frame number; the offset is carried through unchanged and appended to it to give the physical address. The split is determined by the page size, which is a power of two. With a page size of \( 2^{n} \) bytes, the low \( n \) bits are the offset and the rest are the page number. That is precisely why page sizes are powers of two: the division needs no arithmetic at all, only a partition of the bits. A 32-bit address with 4 KB pages therefore gives a 12-bit offset and a 20-bit page number, allowing a million pages. The choice of page size is a trade-off. Larger pages mean smaller page tables and fewer faults for sequential access, but more internal fragmentation and more wasted transfer. Most systems settle on 4 KB, with support for larger pages where a workload benefits.

Answer: A

Correct answer: The process state, program counter and register contents

The Process Control Block is the data structure the operating system keeps for each process. It holds the process state - new, ready, running, waiting or terminated - the program counter, the contents of the CPU registers, scheduling information such as priority, memory management information including base and limit registers or page table pointers, accounting data, and the list of open files and allocated devices. Its purpose is to make a context switch possible. When the scheduler suspends a process, the entire CPU state is saved into its PCB; when it resumes, the state is restored and execution continues as though nothing had happened. Without that saved state, a process could never be interrupted. The PCB is also what a context switch costs: saving and restoring it is pure overhead, doing no useful work, which is why switching too often degrades throughput. It is sometimes called the task control block, and the collection of them is the process table.

Answer: D

Correct answer: a theoretical benchmark that cannot be implemented in practice

The optimal algorithm, sometimes called OPT or MIN, evicts the page that will not be used for the longest time in the future. It provably yields the lowest possible page-fault rate. It cannot be implemented, because it requires knowledge of the future reference string. Its value is as a benchmark: a trace of a real program can be replayed afterwards, when the future is known, to establish the best achievable fault rate, and a practical algorithm is then judged by how close it comes. That comparison is how LRU earns its reputation. LRU is the mirror image of optimal, looking backwards where optimal looks forwards, and on programs with good locality the past predicts the future well enough that it performs within a small margin. It is also a stack algorithm and so immune to Belady’s anomaly. FIFO, by contrast, is simple but performs poorly and can exhibit that anomaly - which is why real systems use clock or second-chance approximations of LRU instead.

Answer: C

Correct answer: pointers to the inner page tables

In a two-level scheme the outer table holds pointers to inner page tables, and the inner tables hold the frame numbers. The logical address splits into three parts: an index into the outer table, an index into the inner one, and an offset. The reason for the arrangement is size. A 32-bit address space with 4 KB pages needs a million page-table entries per process, which at four bytes each is 4 MB of contiguous memory - unacceptable for every process. Splitting the table means only the outer table and the inner tables actually in use need exist; the rest are simply absent, and most processes use a small part of their address space. The cost is another memory access per translation, which is why the TLB matters so much. 64-bit architectures need three or four levels for the same reason, and the alternative approaches are the hashed page table and the inverted page table, which keeps one entry per physical frame rather than per virtual page.

Answer: D

Correct answer: a file is mapped into the address space and accessed as if it were memory

Memory mapping associates a region of a process’s address space with a file on disk. Reading or writing that memory reads or writes the file, with the paging system doing the transfer as ordinary page faults. The advantage is that the usual read and write system calls disappear, and with them a copy: normally data moves from disk to a kernel buffer and then to the process’s buffer, whereas a mapped file is paged straight into the process’s own frames. For a file accessed repeatedly or randomly, that is substantially faster. It also provides shared memory between processes almost for free: two processes mapping the same file share the physical frames, and a write by one is visible to the other. Writes are not necessarily immediate - the operating system may defer them until the page is evicted or the file is closed - so an explicit synchronisation call exists where durability matters. Shared libraries are loaded this way, which is how one copy serves every process.

Answer: A

Correct answer: File server

A file server holds programs and data centrally so that every user on the LAN can reach the same copy. A print server shares a printer and a communication server shares a link, neither of which is about sharing programs and data.

Answer: D

Correct answer: brings pages into memory before they are referenced

Prepaging brings pages into memory in anticipation of their being needed, rather than waiting for a reference to fault them in. Pure demand paging loads nothing until it is actually referenced. The motivation is the burst of faults a process suffers at start-up or on resuming after being swapped out, when none of its pages are resident. Loading its whole working set at once is cheaper than faulting it in page by page, because a single large transfer costs little more than a small one once the disk seek is paid for. Whether it pays depends on the accuracy of the guess. If a fraction \( \alpha \) of the prepaged pages are actually used, prepaging is worthwhile only when the cost saved on \( \alpha \) faults exceeds the cost of loading the \( 1-\alpha \) that were not needed. Where \( \alpha \) is near zero it is pure waste. Real systems use it selectively - on process resumption, where the working set is already known - and rely on demand paging otherwise.

Answer: B

Correct answer: equal or proportional allocation according to process size

Frames are distributed among processes chiefly by equal allocation, dividing them evenly, or proportional allocation, giving each process a share according to its size. Equal allocation is simple but wasteful: a small process receives frames it cannot use while a large one starves. Proportional allocation is better, though it takes no account of priority - a variation weights the shares by priority as well as size. A second, orthogonal distinction is between local and global replacement. Under local replacement a process may only take a frame from its own allocation, so its performance is predictable and unaffected by others; under global replacement it may take a frame from any process, which uses memory better overall but means a process’s fault rate depends on the behaviour of its neighbours. Global is more common in practice. Neither scheme prevents thrashing by itself. That requires the working set model or page-fault frequency control, which adjust allocation according to what each process is actually referencing.