Memory management interview questions, with answers

The questions, with answers

1. 1.What is paging in memory management?

   In short: Dividing logical memory into fixed-size pages and physical memory into frames of the same size, mapped by a page table.

   Paging splits a process's logical address space into fixed-size blocks called pages and physical memory into blocks of the same size called frames. A page table, one per process, records which frame holds each page, so a process's pages can sit in any free frames, not necessarily next to each other. That removes the need to find one large contiguous hole, and with it external fragmentation. The memory management unit translates every address using the page table, and the page table entry also carries bits such as valid, dirty and protection flags.

2. 2.How is a logical address translated to a physical address in paging?

   In short: Split the address into page number and offset, look up the page's frame in the page table, then combine frame and offset.

   A logical address is split into a page number and an offset: dividing by the page size gives the page number as the quotient and the offset as the remainder, which in binary simply means taking the high and low bits. The page table gives the frame number for that page, and the physical address is frame number × page size + offset. The offset never changes, since a page and its frame have the same size. In the example, 8300 with 4096-byte pages is page 2, offset 108; if page 2 is in frame 6, the physical address is 24684.

   page size 4096
   8300 = 2 x 4096 + 108
   page 2 -> frame 6
   6 x 4096 + 108 = 24684

3. 3.What is the difference between paging and segmentation?

   In short: Paging uses fixed-size pages invisible to the programmer; segmentation uses variable-size logical segments such as code, data and stack.

   Paging divides memory into equal-sized pages that have no meaning to the program, which makes allocation simple and avoids external fragmentation. Segmentation divides a program into variable-sized segments that match its logical structure, such as code, data, heap and stack, each with a base and a limit, which suits protection and sharing, since a whole segment can be marked read-only or shared. Variable sizes, however, lead to external fragmentation. Some architectures combined them as segmented paging; modern x86-64 systems use a flat model with paging.

4. 4.What is the difference between internal and external fragmentation?

   In short: Internal fragmentation is wasted space inside allocated blocks; external fragmentation is free memory split into holes too small to use.

   Internal fragmentation is memory that has been allocated but is not used, because allocation happens in fixed units larger than the request: the allocated block is bigger than what was asked for. External fragmentation is free memory that exists in total but is scattered in small non-contiguous holes between allocated blocks, so a large request cannot be satisfied even though enough memory is free. Fixed-size allocation schemes tend to suffer the first, variable-size schemes the second. External fragmentation can be reduced by compaction, which moves allocations together, or avoided by paging.

5. 5.What is a TLB, and how do you calculate effective memory access time?

   In short: A small, fast cache of recent page-table entries; effective access time weights TLB hits and misses by their costs.

   Without help, paging doubles the cost of every memory access, one access to read the page table and one for the data. The translation lookaside buffer caches recent page-to-frame translations in fast hardware, so most translations need no page-table access. Effective access time weighs both cases: a hit costs the TLB lookup plus one memory access, and a miss costs the lookup plus two accesses. With a 90% hit ratio, a 10 ns TLB and 100 ns memory, it is 120 ns, only 20% above a plain access. TLB entries are flushed or tagged by address space on a context switch.

   hit:  0.9 x (10 + 100) = 99
   miss: 0.1 x (10 + 200) = 21
   EAT = 99 + 21 = 120 ns

6. 6.Why are multi-level page tables used?

   In short: A flat page table for a large address space is huge and mostly empty; splitting it into levels stores only the parts in use.

   A single-level page table needs one entry for every page in the address space, whether or not the page is used. With 48-bit virtual addresses and 4 KB pages, that is 2^36 entries per process, far too many to keep in memory. A multi-level table splits the page number into several indexes: the first indexes an outer table whose entries point to inner tables, and inner tables are allocated only for regions actually in use, so a sparse address space costs little. x86-64 uses four levels, or five on newer processors. The price is more memory accesses per translation on a TLB miss.

7. 7.What are first fit, best fit and worst fit?

   In short: Strategies for choosing a free hole for a variable-size request: the first large enough, the smallest large enough, or the largest.

   With variable-size allocation, the allocator keeps a list of free holes. First fit takes the first hole that is large enough, which is fast. Best fit searches for the smallest hole that is large enough, which leaves the smallest leftover but tends to create many tiny, useless fragments. Worst fit takes the largest hole, hoping the leftover remains usable, but it quickly uses up large holes. Simulations generally show first fit and best fit beating worst fit in storage utilisation, with first fit usually faster. All three suffer from external fragmentation.

How the diagnostic asks it

One question from the Operating Systems bank, exactly as a sitting would show it. The bank has 3 on memory management and 30 across Operating Systems.