CSE Roadmap

Common tier · about 3 hours · 8 parts

Part 5 of 8 · 3 min read

Memory questions

Think of a library that gives each reader a private catalogue with its own shelf numbers, while the librarian keeps the real map from catalogue numbers to shelves. Readers cannot see each other's books. The analogy stops in one place: a library catalogue is on paper, and the translation here is done by hardware on every access.

In plain words: Model answers:

  1. What is virtual memory? Each process sees its own address space, and the kernel with the hardware maps its pages to physical frames. It gives isolation, a large flat address space, sharing and loading on demand (Levels 6 and 7).
  2. What is a page fault? An access to a page that has no valid mapping. The kernel either brings the page in (a minor fault if the data is in memory, a major fault if it must come from disk) or ends the process with SIGSEGV if the access is illegal (Level 6, page 5 of this level).
  3. What does the TLB do? It caches recent translations, so that most accesses need no page-table walk (Level 6).
  4. What is thrashing? The system spends its time swapping pages in and out because the working sets of the processes exceed memory (Level 6).
  5. What does the OOM killer do? When memory is exhausted, the kernel ends a process (a chosen victim) with SIGKILL to free memory (Level 7).

A worked example. Two classic calculations.

Page-table size. A 32-bit address space with 4 KiB pages has 2^32 / 2^12 = 2^20 = 1,048,576 pages. With 4 bytes per entry, one flat table is 1,048,576 x 4 = 4 MiB for each process. With 4-level tables (9 bits per level and a 12-bit offset, 48 bits in all), a process that uses little memory needs only the table pages for the areas it touches: each table page holds 512 entries of 8 bytes, which is 4,096 bytes.

Effective access time. The TLB takes 1 ns, memory 100 ns, and the hit rate is 98 per cent (made up to show the idea). A hit costs 1 + 100 = 101 ns (look up, then access). A miss costs 1 + 100 + 100 = 201 ns (look up, walk a one-level table, then access). The effective access time is 0.98 x 101 + 0.02 x 201 = 98.98 + 4.02 = 103.0 ns, only 3 per cent above the 100 ns of a memory access with no translation.

The key lines. The answer is strong when it includes the cost: a translation is nearly free only because the TLB hits, and a higher miss rate or a deeper table (page 2 of Level 11 showed 24 references for a nested walk) makes it visible.

Effective access time

The effective access time (EAT) of memory is the average time of an access, weighted by how often each case happens: a TLB hit or a miss with a table walk. EAT = hit rate x hit time + miss rate x miss time.

Example: 0.98 x 101 ns + 0.02 x 201 ns = 103.0 ns.

Check yourself: 1. What is the difference between a minor and a major fault? 2. How big is a flat page table for a 32-bit space with 4 KiB pages and 4-byte entries? 3. What is the EAT if the hit rate falls to 90 per cent?