Memory Management: Allocation, Paging and Segmentation

Why memory management matters

Every program you run needs main memory (RAM): its code, its global variables, its heap and its stack all have to live somewhere the CPU can reach in a few nanoseconds. Several programs run at once, so the operating system has to decide which part of RAM each program gets, stop programs from touching each other's memory, and make the best use of a limited amount of RAM. That job is called memory management.

This lesson covers how the OS and the hardware cooperate to do it: how addresses are bound, how the memory management unit (MMU) translates addresses, the older contiguous schemes and the fragmentation problems they cause, and then paging and segmentation, which every modern system uses in some form. The next lesson, on virtual memory, builds directly on paging.

Interviewers love this topic because it mixes concepts with arithmetic. Expect questions like "what is the difference between internal and external fragmentation?", "how big is a page table for a 32-bit address space?", "why do we need a TLB?" and "split this address into page number and offset". By the end you should be able to answer all of them with numbers.

Address binding: when does an address become real?

A program refers to memory using addresses. In source code you write variable names; the compiler and linker turn those names into numbers. The question is: at what point does an address become the actual location in RAM? Mapping a program's addresses to physical locations is called address binding, and it can happen at three stages.

Compile-time binding survives only in tiny embedded systems and old MS-DOS .COM files. Load-time binding was common in early multiprogramming systems. Every general-purpose OS today uses execution-time binding, because it is the only one that allows swapping, paging and virtual memory. It needs hardware support, which is the MMU.

 source.c --> compiler --> object.o --> linker --> a.out
   names      symbolic      relocatable     relocatable or
              addresses     addresses       absolute addresses
                                                |
                                             loader
                                                |
                                         process in RAM
                       (run-time binding: MMU translates
                        every access while it runs)

Logical versus physical addresses

Two kinds of addresses appear once you have run-time binding:

• A logical address (also called a virtual address) is the address the CPU generates while running a program. It is what you see if you print a pointer in C.
• A physical address is the actual location in the RAM chips, the number that goes out on the memory bus.

The set of all logical addresses a program can generate is its logical address space; the set of real RAM locations is the physical address space. With compile-time or load-time binding the two are identical. With run-time binding they differ, and the hardware translates one into the other on every single memory access.

This separation is the reason two processes can both print the pointer 0x7ffd1000 and still be looking at completely different bytes of RAM.

The MMU and base/limit registers

The memory management unit (MMU) is a piece of hardware, part of the CPU today, that translates logical addresses into physical ones. The simplest MMU uses two registers per running process:

• The base register (also called the relocation register) holds the physical address where the process starts.
• The limit register holds the size of the process's logical address space.

On every memory access the hardware does two things:

1. Check that the logical address is less than the limit. If not, it raises a trap (an exception) and the OS usually kills the process with an addressing error.
2. Add the base to get the physical address.

            logical addr
 CPU ---------------------+
                          v
                  +---------------+   no
                  | addr < limit? |--------> trap: addressing error
                  +---------------+
                          | yes
                          v
                   +-------------+
                   |  + base     |
                   +-------------+
                          |
                          v
                   physical addr --> RAM

Worked example: base and limit

A process has base = 30000 and limit = 12000.

• Logical address 500: 500 is less than 12000, so it is legal. Physical address = 30000 + 500 = 30500.
• Logical address 11999: legal (the last byte). Physical address = 41999.
• Logical address 12000: not less than the limit, so the MMU traps. The process cannot touch byte 42000, which belongs to someone else.

Only the kernel can load the base and limit registers, using privileged instructions. On a context switch the OS saves the old values in the outgoing process's process control block (PCB) and loads the new process's values. That is the whole protection mechanism: a user program cannot change its own registers, so it cannot escape its region.

Contiguous memory allocation

The earliest multiprogramming systems gave each process one contiguous block of physical memory, described by a single base and limit. There are two flavours.

Fixed partitioning. RAM is divided into partitions at boot, for example four partitions of 8 MB each. A process goes into any free partition big enough to hold it. Simple, but a 1 MB process wastes 7 MB of its partition, and the number of partitions caps how many processes can run.

Variable (dynamic) partitioning. The OS carves out exactly as much memory as each process needs. Free memory is kept as a list of holes (free blocks). When a process arrives, the OS picks a hole that is big enough, gives the process the part it needs, and leaves the rest as a smaller hole. When a process exits, its block becomes a hole and is merged (coalesced) with neighbouring holes.

The interesting question is which hole to pick. Four classic strategies exist:

Simulation studies in operating-systems textbooks generally find first fit and best fit better than worst fit for storage use, and first fit is usually faster.

Worked example: first, next, best and worst fit

Memory has five holes, in address order: 150, 450, 250, 350 and 550 KB. Four processes arrive in this order: 220, 400, 130 and 420 KB. Label the holes H0 to H4.

First fit. Always scan from H0.

1. 220 KB: H0 (150) is too small; H1 (450) fits. H1 becomes 450 - 220 = 230.
2. 400 KB: H0 150, H1 230, H2 250, H3 350 are all too small; H4 (550) fits. H4 becomes 150.
3. 130 KB: H0 (150) fits. H0 becomes 20.
4. 420 KB: holes are now 20, 230, 250, 350, 150. None is 420 or larger. The process must wait.

Next fit. Start each search where the last one succeeded.

1. 220 KB: from H0, first fit is H1. H1 becomes 230. Pointer stays at H1.
2. 400 KB: from H1: 230, 250, 350 too small; H4 (550) fits. H4 becomes 150. Pointer at H4.
3. 130 KB: from H4: 150 fits. H4 becomes 20.
4. 420 KB: holes are 150, 230, 250, 350, 20. Must wait.

Best fit. Pick the smallest hole that fits.

1. 220 KB: candidates 450, 250, 350, 550. Smallest is H2 (250). H2 becomes 30.
2. 400 KB: candidates 450, 550. Smallest is H1 (450). H1 becomes 50.
3. 130 KB: candidates 150, 350, 550. Smallest is H0 (150). H0 becomes 20.
4. 420 KB: candidates 550 only. H4 becomes 130. All four processes fit.

Worst fit. Pick the largest hole.

1. 220 KB: largest is H4 (550). H4 becomes 330.
2. 400 KB: largest is now H1 (450). H1 becomes 50.
3. 130 KB: holes 150, 50, 250, 350, 330; largest is H3 (350). H3 becomes 220.
4. 420 KB: holes 150, 50, 250, 220, 330. Must wait.

 Final hole sizes (KB)        H0   H1   H2   H3   H4   420 KB?
 First fit                    20  230  250  350  150   waits
 Next fit                    150  230  250  350   20   waits
 Best fit                     20   50   30  350  130   placed
 Worst fit                   150   50  250  220  330   waits

Look at first fit's final state: there is 20 + 230 + 250 + 350 + 150 = 1000 KB free in total, yet a 420 KB process cannot run because no single hole is that big. That is external fragmentation, the next topic. Best fit wins on this particular input; on another input a different strategy could win, so never claim one is always best.

Fragmentation

Fragmentation is memory that is free or allocated but cannot be used productively. It comes in two kinds, and interviewers almost always ask you to tell them apart.

• External fragmentation: enough total free memory exists to satisfy a request, but it is split into non-adjacent holes, none of which is big enough. The waste is outside any allocated block. It happens with variable-size allocation: dynamic partitioning and segmentation.
• Internal fragmentation: a process is given a block larger than it asked for, and the unused part inside the block is wasted. It happens whenever memory is handed out in fixed-size units: fixed partitions and paging.

 External fragmentation          Internal fragmentation
 +--------+                      +------------------+
 | P1     |                      | P1 uses 13 KB    |
 +--------+                      |                  |
 | free 30|  <- too small        |..................|
 +--------+                      | 3 KB unused      | <- wasted inside
 | P2     |                      +------------------+   a 16 KB block
 +--------+
 | free 40|  <- too small
 +--------+   (need 60 KB contiguous)

Reducing external fragmentation: compaction

Compaction shuffles the allocated blocks so that all free memory forms one large hole. Using the first-fit result above, moving processes so the five holes merge would give a single 1000 KB hole and the 420 KB process would fit.

Compaction has costs:

• It is only possible with run-time binding, because processes move after they start. With load-time binding the addresses inside the program would become wrong.
• It is expensive: the OS must copy potentially gigabytes of memory, and the moved processes cannot run during the copy.
• I/O complicates it. If a device is doing direct memory access (DMA) into a process's buffer, that buffer cannot move until the transfer finishes.

The more fundamental fix is to stop requiring contiguous memory at all. That is exactly what paging does.

The 50-percent rule

For first fit, a statistical analysis in classic OS textbooks suggests that if N blocks are allocated, about 0.5N blocks are lost to fragmentation, so roughly one third of memory may be unusable. Treat it as a rule of thumb about how bad external fragmentation can get, not a law.

Paging

Paging lets a process's physical memory be non-contiguous. Here is the idea, step by step.

1. Divide physical memory into fixed-size blocks called frames (also page frames).
2. Divide each process's logical memory into blocks of the same size called pages.
3. Any page can go into any free frame. The pages of one process may be scattered all over RAM.
4. Each process has a page table: an array indexed by page number whose entry says which frame holds that page.

Page sizes are powers of two, typically 4 KB on x86-64 and ARM (with larger "huge" pages available, covered in the next lesson). Because any free frame works, there is never a "hole too small" problem: external fragmentation disappears.

  Logical memory      Page table        Physical memory
  (process A)        page -> frame      frame
  +---------+        +---+-----+        0 +---------+
  | page 0  |        | 0 |  5  |        1 | A pg 2  |
  +---------+        | 1 |  3  |        2 |         |
  | page 1  |        | 2 |  1  |        3 | A pg 1  |
  +---------+        | 3 |  6  |        4 |         |
  | page 2  |        +---+-----+        5 | A pg 0  |
  +---------+                           6 | A pg 3  |
  | page 3  |                           7 |         |
  +---------+                             +---------+

Splitting an address

Because the page size is a power of two, translation needs no division. If the page size is 2^d bytes and the logical address is m bits wide:

• The low d bits are the page offset: the position of the byte within its page.
• The high m - d bits are the page number: the index into the page table.

  m-bit logical address
  +---------------------------+---------------+
  |  page number p (m-d bits) | offset d bits |
  +---------------------------+---------------+
              |                       |
     page table[p] = frame f          |
              |                       |
  +---------------------------+---------------+
  |      frame number f       |    offset     |  physical address
  +---------------------------+---------------+

The offset is copied unchanged. Only the page number is replaced by a frame number.

Worked example 1: decimal arithmetic

Page size = 1 KB = 1024 bytes. A process's page table maps page 3 to frame 7. Translate logical address 3085.

1. Page number = 3085 div 1024 = 3 (because 3 x 1024 = 3072, and 4 x 1024 = 4096 is too big).
2. Offset = 3085 - 3072 = 13.
3. Page table lookup: page 3 is in frame 7.
4. Physical address = 7 x 1024 + 13 = 7168 + 13 = 7181.

Worked example 2: bit splitting in hex

A machine has 32-bit logical addresses and 4 KB pages. Translate 0x0001A3F4, given that page 0x1A is in frame 0x5C.

1. Page size 4 KB = 2^12, so the offset is 12 bits and the page number is 32 - 12 = 20 bits.
2. 12 bits is exactly three hex digits. So the last three hex digits are the offset: 0x3F4 (= 1012 decimal).
3. The remaining digits are the page number: 0x0001A = 26 decimal.
4. Page table says page 26 (0x1A) is in frame 0x5C.
5. Physical address = frame followed by offset = 0x5C then 3F4 = 0x5C3F4.

The trick of reading the offset straight off the hex digits works whenever the offset width is a multiple of 4 bits. Otherwise, write the address in binary and split it.

Here is the same logic in Python, which you can run to check your own answers:

PAGE_SIZE = 4096                     # 4 KB
OFFSET_BITS = PAGE_SIZE.bit_length() - 1   # 12

page_table = {0x1A: 0x5C}            # page -> frame

def translate(logical):
    page = logical >> OFFSET_BITS
    offset = logical & (PAGE_SIZE - 1)
    if page not in page_table:
        raise LookupError(f"page fault: page {page:#x} not mapped")
    frame = page_table[page]
    return (frame << OFFSET_BITS) | offset

print(hex(translate(0x0001A3F4)))    # 0x5c3f4

What is in a page table entry?

A page table entry (PTE) holds more than a frame number. Typical fields:

The valid bit plus protection bits give paging its memory protection: a process can only reach frames listed in its own page table, with the permissions listed there.

Where the page table lives

A page table for a real process has thousands to millions of entries, far too many for CPU registers. So it lives in RAM, and a register called the page-table base register (PTBR) points to it (on x86 this is CR3). A context switch just changes the PTBR.

The cost is obvious: every memory access now needs two memory accesses, one to read the PTE and one for the actual data. That would halve the speed of every program, which leads us to the TLB.

The TLB and effective access time

The translation lookaside buffer (TLB) is a small, very fast cache inside the CPU that stores recently used page-number-to-frame-number translations. It is an associative memory: the hardware compares the page number against all entries in parallel. Real TLBs hold from a few dozen entries (first level) to a few thousand (second level).

On each access:

1. The MMU looks up the page number in the TLB.
2. TLB hit: the frame number comes straight from the TLB. One memory access (for the data).
3. TLB miss: the MMU (or, on some architectures, the OS) walks the page table in RAM, gets the frame, stores the translation in the TLB, then accesses the data.

Because programs have locality of reference (they keep touching the same few pages), hit ratios are usually very high, often well above 99 percent.

  logical addr (p, d)
        |
        v
  +-----------+  hit   frame f
  |    TLB    |------------------------+
  +-----------+                        |
        | miss                         v
        v                      physical (f, d) --> RAM
  page table in RAM --> f ----> (also load into TLB)

Worked example: effective access time

The effective access time (EAT) is the average time for one memory reference, weighting hit and miss times by their probability.

Assume: TLB lookup = 20 ns, memory access = 100 ns, single-level page table, TLB looked up before memory (not overlapped).

• Hit time = 20 (TLB) + 100 (data) = 120 ns.
• Miss time = 20 (TLB) + 100 (page table) + 100 (data) = 220 ns.

With a hit ratio h, EAT = h x 120 + (1 - h) x 220.

Notice that even at 99 percent hits most of the overhead is the 20 ns TLB lookup on every access. Real CPUs overlap the TLB lookup with the cache lookup, so many textbook problems say "ignore TLB time" and the hit time becomes just 100 ns. Always read the question for which convention it uses, and state your assumption aloud.

With a four-level page table (as on x86-64), a miss costs four page-table reads plus the data read: 20 + 4 x 100 + 100 = 520 ns. At 98 percent hits: 0.98 x 120 + 0.02 x 520 = 117.6 + 10.4 = 128 ns. Multi-level tables make misses much more expensive, which is why TLB hit rate matters so much, and why CPUs also cache page-table entries in the normal data caches.

TLB and context switches

The TLB holds translations for one address space. After a context switch, the old entries are wrong for the new process. Two solutions:

• Flush the TLB on every switch. Simple, but the new process starts with a cold TLB and suffers a burst of misses.
• Tag each entry with an address-space identifier (ASID) (Intel calls its version PCID). Entries from different processes coexist and no flush is needed.

How big is a page table?

This is a favourite numerical question. The formula is:

page table size = (number of pages) x (size of one entry), where number of pages = 2^(address bits) / page size.

32-bit address, 4 KB pages, 4-byte entries.

1. Offset = 12 bits, page number = 20 bits.
2. Number of pages = 2^20 = 1,048,576.
3. Size = 2^20 x 4 B = 4 MB per process.

Four megabytes per process, in contiguous memory, mostly describing pages the process never uses, is too much. With 100 processes that is 400 MB just for page tables.

48-bit virtual address (x86-64), 4 KB pages, 8-byte entries.

1. Page number = 48 - 12 = 36 bits.
2. Size = 2^36 x 8 B = 2^39 B = 512 GB per process for a flat table.

That is impossible, so 64-bit systems never use a flat table. The rest of this section covers the alternatives.

Multi-level (hierarchical) page tables

The fix is to page the page table itself. Split the page number into pieces; the first piece indexes an outer table whose entries point to inner tables, and so on. The key benefit: an inner table that would describe only unused memory need not exist at all. The outer entry is simply marked invalid.

Two-level example: 32-bit, 4 KB pages

With 4-byte entries, one 4 KB page holds 1024 = 2^10 entries. So split the 20-bit page number into 10 + 10:

  +------------+------------+--------------+
  |  p1 (10)   |  p2 (10)   | offset (12)  |
  +------------+------------+--------------+
       |             |
       v             |
  outer table        |
  (1024 entries)     v
   entry p1 --> inner table (1024 entries)
                 entry p2 --> frame f

This is exactly the classic 32-bit x86 layout (page directory, then page table). A small process that uses a few megabytes of code and a stack at the top of the address space needs one outer table and perhaps three inner tables: 4 x 4 KB = 16 KB instead of 4 MB.

x86-64: four (or five) levels

x86-64 with 48-bit addresses uses four levels of 512 entries each (8-byte entries, 4 KB tables), giving 9 + 9 + 9 + 9 + 12 = 48 bits. Newer processors support five-level paging for 57-bit addresses.

  47     39 38     30 29     21 20     12 11         0
  +--------+---------+---------+---------+------------+
  | PML4 9 | PDPT  9 |  PD   9 |  PT   9 | offset 12  |
  +--------+---------+---------+---------+------------+

The trade-off: each extra level adds a memory access to a TLB miss (as the 520 ns example showed). Memory saved, time lost on misses.

Worked example: sizing levels

32-bit addresses, 8 KB pages, 4-byte PTEs. Design a two-level table where each inner table fits in one page.

1. Offset = log2(8192) = 13 bits. Page number = 32 - 13 = 19 bits.
2. Entries per page = 8192 / 4 = 2048 = 2^11. So the inner index is 11 bits.
3. Outer index = 19 - 11 = 8 bits (256 outer entries).
4. A flat table would have been 2^19 x 4 B = 2 MB.

Hashed page tables

For large, sparse address spaces another option is a hashed page table. The virtual page number is hashed into a table of buckets; each bucket holds a linked list of (virtual page, frame, next pointer) elements. To translate, hash the page number, walk the chain, and compare page numbers until one matches.

Its size depends on how many pages are actually mapped, not on the size of the address space. A variant called a clustered page table stores several consecutive pages per element, which suits sparse but clumpy address spaces.

Inverted page tables

Ordinary page tables have one entry per virtual page per process. An inverted page table flips this: it has one entry per physical frame in the whole system. Each entry records which process (by process ID or ASID) and which virtual page currently occupies that frame.

  Inverted table (index = frame number)
  frame | pid | virtual page
  ------+-----+-------------
    0   |  7  |   0x1A
    1   |  3  |   0x02
    2   |  7  |   0x40
   ...  | ... |   ...

• Benefit: a single table for the whole machine, sized by RAM. With 16 GB of RAM and 4 KB frames that is 16 GB / 4 KB = 4,194,304 entries, however many processes run.
• Cost: translation means searching for the entry that matches (pid, page). A linear search is far too slow, so real designs pair it with a hash table. It also makes shared memory awkward, because one frame can hold only one (pid, page) pair.

Inverted tables have been used on IBM POWER and older UltraSPARC and IA-64 systems. Mainstream x86 and ARM systems use multi-level tables.

Shared pages

Paging makes sharing easy. If ten users run the same editor, its code is reentrant (also called pure code: code that never modifies itself), so all ten processes can map the same physical frames for the code pages, while each has private frames for its own data and stack.

  Process A page table      Physical frames     Process B page table
  code 0 -> 3                 3 [editor code 0]   code 0 -> 3
  code 1 -> 4                 4 [editor code 1]   code 1 -> 4
  data   -> 6                 6 [A's data]        data   -> 8
                              8 [B's data]

Shared libraries (libc.so on Linux, DLLs on Windows) are shared exactly this way: one copy in RAM, mapped read-only and executable into every process. Shared memory for inter-process communication works the same way, but with writable pages. Copy-on-write after fork() is another use, covered in the virtual memory lesson.

Segmentation

Programmers do not think of memory as a flat array of 4 KB pages. They think in terms of logical units: the code, the global data, the heap, the stack, maybe one region per module or array. Segmentation is a memory scheme that matches this view.

• A logical address is a pair (segment number, offset).
• Each process has a segment table. Each entry holds a base (physical start) and a limit (length) for one segment, plus protection bits.
• Translation: check offset against the segment's limit; if it is within bounds, physical address = base + offset.

  (s, d)
    |
    v
  segment table[s] = (limit, base)
    |
    +-- d < limit ? --no--> trap (segmentation fault)
    |
   yes
    v
  physical = base + d

Segments can be shared and protected individually: mark the code segment read-and-execute and share it; mark the data segment read-write and keep it private. That is more natural than per-page protection.

Worked example: segment translation

• (2, 53): 53 < 1100, so legal. Physical = 4300 + 53 = 4353.
• (3, 852): 852 < 1000, so legal. Physical = 3200 + 852 = 4052.
• (0, 999): 999 < 1000, legal. Physical = 1400 + 999 = 2399 (last byte of segment 0).
• (1, 500): 500 is not less than 400. Trap: segmentation fault.

The term "segmentation fault" in Unix comes from this history, although on modern Linux it is raised by the paging hardware when you touch an unmapped or protected page.

The problem with pure segmentation

Segments have variable sizes, so placing them in RAM is the same problem as dynamic partitioning: first fit, best fit and external fragmentation. Large segments are also hard to swap. Pure segmentation therefore has the same weakness that paging was invented to fix.

Paging versus segmentation

Segmentation with paging

The two ideas can be combined to get the logical view of segmentation and the clean allocation of paging: each segment is itself paged. The segment table entry points not to a contiguous block of RAM but to a page table for that segment.

  logical (s, d)
     |
     v
  segment table[s] --> (limit, page table base)
     |
     | check d < limit, then split d into (p, d')
     v
  segment's page table[p] --> frame f
     |
     v
  physical (f, d')

Translation has three steps:

1. Use the segment number to find the segment's page table, and check the offset against the segment limit.
2. Split the offset into a page number and page offset.
3. Use the page table to find the frame, and append the page offset.

The Intel IA-32 architecture works like this: a logical address goes through segmentation to produce a linear address, and the linear address then goes through paging to produce a physical address. In 64-bit mode (x86-64), segmentation is almost entirely disabled: segment bases are forced to zero for code and data (the FS and GS registers remain usable for thread-local storage), so in practice Linux and Windows on x86-64 are pure paging systems. Unix-style "segments" such as text, data, heap and stack still exist, but as regions of a paged virtual address space, not as hardware segments.

Swapping

Before paging became universal, the OS could free memory by swapping: copying an entire process out to disk (the backing store) and bringing it back later, possibly to a different location (which needs run-time binding). Swapping whole processes is slow because the transfer time is proportional to the process size.

Modern systems swap pages, not whole processes. That is called paging to disk and is the subject of the virtual memory lesson. Mobile operating systems typically avoid swapping to flash storage altogether: iOS asks apps to free memory and terminates them if needed, and Android kills background processes, often combined with compressed memory in RAM (zram).

Interview questions

Q1. What is the difference between a logical and a physical address?

A logical (virtual) address is what the CPU generates while running a program, the value of a pointer. A physical address is the actual location in RAM placed on the memory bus. With run-time binding the MMU translates logical to physical on every access, so each process can have its own address space starting at zero while living anywhere in RAM.

Q2. What are the three stages of address binding, and which do modern systems use?

Compile time (absolute code; the program must load at a fixed address), load time (relocatable code fixed up by the loader; cannot move afterwards), and execution time (addresses are translated by hardware on every access; the process can move). Modern general-purpose systems use execution-time binding, because paging, swapping and virtual memory all need it.

Q3. Explain internal versus external fragmentation with an example.

External fragmentation is free memory split into scattered holes, none large enough for a request, even though the total is sufficient; for example 1000 KB free across five holes but none of 420 KB. Internal fragmentation is unused space inside an allocated block, such as a 13 KB process given four 4 KB pages, wasting 3 KB in the last page. Variable-size allocation suffers external fragmentation; fixed-size allocation suffers internal fragmentation.

Q4. Compare first fit, best fit, worst fit and next fit.

First fit takes the first big-enough hole and is fast. Next fit continues from where the last search stopped. Best fit takes the smallest adequate hole, preserving big holes but leaving tiny slivers, and needs a full scan. Worst fit takes the largest hole so leftovers stay usable, but it destroys big holes. Textbook simulations favour first and best fit over worst fit, with first fit usually faster.

Q5. What is compaction and what does it require?

Compaction moves allocated blocks together so that free memory forms one big hole, curing external fragmentation. It requires run-time (dynamic) relocation, because processes move after they have started. It is costly because large amounts of memory must be copied, and memory involved in ongoing DMA cannot be moved until the I/O completes.

Q6. How does paging eliminate external fragmentation?

Physical memory is divided into equal-size frames, and any page can go into any free frame, so a process never needs a contiguous region. Any free frame is useful, so there are no unusable holes between allocations. Internal fragmentation remains in the last page of each region.

Q7. A system has 32-bit addresses, 4 KB pages and 4-byte PTEs. How large is the page table?

The offset needs 12 bits, leaving 20 bits of page number, so there are 2^20 entries. At 4 bytes each, the table is 4 MB per process. This is why real systems use multi-level tables, which allocate only the inner tables that describe used memory.

Q8. What is a TLB and why is it needed?

A TLB is a small associative cache of recent page-to-frame translations inside the CPU. Without it every memory access would need an extra memory access (more with multi-level tables) to read the page table. Because of locality, hit ratios are typically very high, so most accesses translate in about a cycle.

Q9. Compute the EAT for a 90 percent TLB hit ratio, 10 ns TLB and 100 ns memory.

Hit = 10 + 100 = 110 ns. Miss = 10 + 100 + 100 = 210 ns. EAT = 0.9 x 110 + 0.1 x 210 = 99 + 21 = 120 ns. If the question says to ignore TLB time, hit = 100 and miss = 200, giving 110 ns.

Q10. What happens to the TLB on a context switch?

Its entries belong to the old address space, so either the TLB is flushed, or each entry is tagged with an address-space identifier (ASID, or PCID on Intel) so entries from different processes can coexist. ASIDs avoid the burst of misses after every switch.

Q11. Why use a multi-level page table?

A flat table must cover the whole virtual address space even though most of it is unused. A multi-level table only allocates inner tables for regions in use, marking other outer entries invalid. The price is one extra memory access per level on a TLB miss.

Q12. What is an inverted page table and what are its drawbacks?

It has one entry per physical frame recording which (process, virtual page) occupies it, so there is one table whose size depends on RAM, not on the number or size of address spaces. Lookups need a search, usually through a hash table, and sharing a frame between processes is awkward because each frame records only one owner.

Q13. What is segmentation, and how is it different from paging?

Segmentation divides a process into variable-size logical units such as code, stack and heap, addressed as (segment, offset) and translated with base and limit per segment. Paging uses fixed-size invisible units. Segmentation gives natural protection and sharing but suffers external fragmentation; paging avoids external fragmentation but has internal fragmentation and no logical structure.

Q14. How do shared libraries avoid using memory once per process?

Library code is reentrant (never modified at run time), so the OS maps the same physical frames into every process that uses it, read-only and executable. Each process has its own page table entries pointing at those frames. Writable library data gets private copies, often via copy-on-write.

Q15. Does x86-64 Linux use segmentation?

Essentially no. In 64-bit mode the hardware forces code and data segment bases to zero, so the linear address equals the logical address and paging does all the work. FS and GS still have usable bases, which Linux uses for thread-local storage and per-CPU data.

Key takeaways

• Modern systems bind addresses at execution time: the MMU translates every logical address into a physical one, which enables relocation, protection and virtual memory.
• Base and limit registers are the simplest MMU: check address < limit, then add the base.
• Contiguous allocation with variable partitions suffers external fragmentation; first, best, worst and next fit only change where the holes end up.
• Internal fragmentation is waste inside an allocated unit; external fragmentation is waste between allocations.
• Paging splits an address into page number and offset; the page table maps pages to frames, and the offset is copied unchanged.
• Page table size = (2^address bits / page size) x entry size; flat tables are too big, so real systems use multi-level tables.
• The TLB caches translations; compute EAT as h x hit time + (1 - h) x miss time, and state whether TLB time is included.
• Segmentation matches the programmer's view but fragments memory externally; segmentation with paging combines both, and x86-64 keeps only the paging half.

Next lesson

Continue with Virtual memory.