Memory management: paging and segmentation

50 min · Advanced

Memory questions in placement tests are numericals: translate an address, find the page-table size, compute an access time. The interviewer is checking that you split an address correctly and know which fragmentation each scheme causes.

Contiguous allocation, internal and external fragmentation

External fragmentation is free memory split into many small holes, so a request fails even though the total free space is large enough.

The program below places four processes into five free holes with first fit, best fit and worst fit, and shows which method manages to place all four.

Example 1 · First fit, best fit and worst fit

Python

1def allocate(strategy, holes_start, requests):2    holes = holes_start[:]3    out = strategy + ":"4    for req in requests:5        fits = [i for i, h in enumerate(holes) if h >= req]6        if not fits:7            out += f" {req}K->wait"8            continue9        if strategy == "First fit":10            pick = fits[0]11        elif strategy == "Best fit":12            pick = min(fits, key=lambda i: holes[i])13        else:14            pick = max(fits, key=lambda i: holes[i])15        out += f" {req}K->hole{pick + 1}"16        holes[pick] -= req                 # the rest stays as a smaller hole17    print(out)18    print("  holes left:", holes)19
20
21holes = [100, 500, 200, 300, 600]   # KB22requests = [212, 417, 112, 426]     # KB, in arrival order23for strategy in ("First fit", "Best fit", "Worst fit"):24    allocate(strategy, holes, requests)

Output

First fit: 212K->hole2 417K->hole5 112K->hole2 426K->wait
  holes left: [100, 176, 200, 300, 183]
Best fit: 212K->hole4 417K->hole2 112K->hole3 426K->hole5
  holes left: [100, 83, 88, 88, 174]
Worst fit: 212K->hole5 417K->hole2 112K->hole5 426K->wait
  holes left: [100, 83, 200, 300, 276]

What this code does

Only best fit places all four processes here. First fit and worst fit split the big holes early, so 426 K finds no single hole large enough.
In first fit, 426 K waits even though 100 + 176 + 200 + 300 + 183 = 959 K is free in total: that is external fragmentation.

In contiguous allocation each process gets one continuous block, chosen from the free holes by first fit (the first hole big enough), best fit (the smallest hole big enough) or worst fit (the largest hole).

First fit: fast; usually good enough in practice.
Best fit: leaves the smallest leftover holes, which are often too small to use.
Worst fit: leaves big leftovers, but often performs worst in studies.
Fixed-size partitions cause internal fragmentation; variable-size ones cause external.

Internal fragmentation is wasted space inside an allocated block, because the block is bigger than the process asked for. Compaction (moving processes together) fixes external fragmentation but is slow; paging avoids it altogether.

Predict the output

Which hole is chosen?

Free holes are listed in memory order.

Round 1 of 2

A 300 KB request with first fit. Which hole index is chosen?

holes = [100, 500, 200]

request = 300

first = next((i for i, h in enumerate(holes) if h >= request), -1)

print(first)

Paging: pages, frames, page table, worked address translation

Paging divides logical memory into fixed-size pages and physical memory into frames of the same size, and a page table maps each page number to a frame number.

The program below translates logical addresses with the page table [5, 9, 7, 2] and a page size of 1024 bytes, and prints the page, offset, frame and physical address.

Translating logical address 2500 with page size 1024. 2500 splits into page 2 and offset 452. The page table maps page 2 to frame 7. The offset is copied unchanged, so the physical address is frame 7 times 1024 plus 452, which is 7620.

Example 2 · Translating a logical address with a page table

Python

1page_size = 1024                   # 1 KB = 2^10, so the offset is 10 bits2page_table = [5, 9, 7, 2]          # page -> frame3addresses = [2500, 100, 3071, 4096]4
5for logical in addresses:6    page, offset = divmod(logical, page_size)7    if page >= len(page_table):8        print(f"{logical}: page {page} is outside the table -> trap")9        continue10    physical = page_table[page] * page_size + offset11    print(f"{logical}: page {page}, offset {offset}, frame {page_table[page]} -> physical {physical}")12
13logical = 250014print(f"Same with bits: page {logical >> 10}, offset {logical & 1023}")

Output

2500: page 2, offset 452, frame 7 -> physical 7620
100: page 0, offset 100, frame 5 -> physical 5220
3071: page 2, offset 1023, frame 7 -> physical 8191
4096: page 4 is outside the table -> trap
Same with bits: page 2, offset 452

What this code does

Division gives the page and the remainder gives the offset; the offset is copied unchanged into the physical address.
Because the page size is a power of 2, hardware does this with bits: shift right by 10 for the page, mask the low 10 bits for the offset. Address 4096 is page 4, which this 4-page process does not have.

Any page can go into any free frame, so paging has no external fragmentation. A logical address splits into a page number p = address ÷ page size and an offset d = address mod page size; the physical address is frame × page size + d. For address 2500: page 2, offset 452, frame 7, so 7 × 1024 + 452 = 7620.

With a page size of 2ⁿ bytes the offset is the lowest n bits of the address and the page number is the rest: a 32-bit address with 4 KB (2¹²) pages has a 20-bit page number and a 12-bit offset.

Order of execution

Translate an address

Put the steps of one address translation in order.

TLB and effective access time

TLB (translation look-aside buffer) is a small, fast hardware cache of recent page-to-frame translations, so most accesses skip the page table in memory.

The program below computes the effective access time for a 20 ns TLB and 100 ns memory at three hit ratios, and compares it with having no TLB.

Example 3 · Effective access time with a TLB

Python

1def eat(hit, tlb, mem):2    return hit * (tlb + mem) + (1 - hit) * (tlb + 2 * mem)3
4
5tlb, mem = 20, 100   # nanoseconds6for hit in (0.80, 0.90, 0.98):7    t = eat(hit, tlb, mem)8    print(f"Hit ratio {hit * 100:.0f}%: EAT = {t:.1f} ns (slowdown {(t - mem) / mem * 100:.0f}%)")9print(f"Without a TLB: {2 * mem:.1f} ns")

Output

Hit ratio 80%: EAT = 140.0 ns (slowdown 40%)
Hit ratio 90%: EAT = 130.0 ns (slowdown 30%)
Hit ratio 98%: EAT = 122.0 ns (slowdown 22%)
Without a TLB: 200.0 ns

What this code does

A hit costs TLB + one memory read (120 ns); a miss costs TLB + page-table read + data read (220 ns).
Real TLBs often have hit ratios close to 99%, which is why paging is practical: the slowdown falls from 100% (no TLB) to around 20%.

Without a TLB every access needs two memory reads: one for the page-table entry and one for the data. On a TLB hit the translation is ready at once; on a TLB miss the page table is read from memory.

Effective access time (EAT) = hit ratio × (TLB time + memory time) + miss ratio × (TLB time + 2 × memory time). With an 80% hit ratio that is 0.8 × 120 + 0.2 × 220 = 140 ns. Some textbooks ignore the TLB time and get 120 ns: use the model the question states.

Predict the output

Effective access time

TLB time 10 ns, memory time 100 ns. Pick the EAT.

Round 1 of 2

The hit ratio is 90%.

hit, tlb, mem = 90, 10, 100

print((hit * (tlb + mem) + (100 - hit) * (tlb + 2 * mem)) / 100)

Segmentation and how it differs from paging

Segment is a logical, variable-size part of a program, such as code, stack or heap; a logical address is a pair (segment number, offset) checked against the segment's limit.

A segmented address is a pair (segment number, offset). The segment table below gives each segment its base and limit; the program after it translates five addresses and traps the bad ones.

Text

1Segment  Base  Limit2   0     1400   10003   2     4300    4004   3     3200   11005(2, 53)   -> 53 < 400   -> 4300 + 53  = 43536(3, 852)  -> 852 < 1100 -> 3200 + 852 = 40527(0, 1222) -> 1222 >= 1000 -> trap

Example 4 · Segment table translation with a limit check

Python

1base = [1400, 6300, 4300, 3200, 4700]2limit = [1000, 400, 400, 1100, 1000]3requests = [(2, 53), (3, 852), (0, 1222), (1, 399), (4, 1000)]4
5for seg, offset in requests:6    if offset < limit[seg]:7        result = f"physical {base[seg] + offset}"8    else:9        result = f"trap: offset {offset} >= limit {limit[seg]}"10    print(f"({seg}, {offset}) -> {result}")

Output

(2, 53) -> physical 4353
(3, 852) -> physical 4052
(0, 1222) -> trap: offset 1222 >= limit 1000
(1, 399) -> physical 6699
(4, 1000) -> trap: offset 1000 >= limit 1000

What this code does

Physical = base + offset, but only after checking offset < limit. The limit check is what protects one segment from overrunning into another.
(1, 399) is the last valid byte of a 400-byte segment; (4, 1000) is one byte past the end of a 1000-byte segment, so it traps.

Translation checks offset < limit; if not, the hardware raises a trap (addressing error). Otherwise physical address = base + offset. Segments match how programmers think and make protection and sharing per segment easy, but their variable sizes bring back external fragmentation.

Many systems combine the two ideas: segmentation with paging inside each segment.

Find the bug

Check the translation

Each translation has one wrong line. Click it.

Segment 1 has base 2000 and limit 500. Translate (1, 500).

Round 1 of 2

Interview questions with model answers

Multi-level page table is a page table split into levels, so only the parts of the address space that are in use need table memory.

The program below finds the page-table size for a 32-bit address space with 4 KB pages, and the internal fragmentation of a process that does not fill its last page.

Example 5 · Page-table size and internal fragmentation

Python

1address_space = 1 << 32        # 32-bit logical addresses2page_size = 4 * 1024           # 4 KB3entry_size = 4                 # bytes per page-table entry4pages = address_space // page_size5print(f"Pages: {pages} (2^{pages.bit_length() - 1})")6print(f"Page table: {pages * entry_size // (1024 * 1024)} MB per process")7
8process_size, page_2k = 72_766, 20489pages_needed = -(-process_size // page_2k)          # ceiling division10wasted = pages_needed * page_2k - process_size11print(f"72,766-byte process, 2 KB pages: {pages_needed} pages, {wasted} bytes of internal fragmentation")

Output

Pages: 1048576 (2^20)
Page table: 4 MB per process
72,766-byte process, 2 KB pages: 36 pages, 962 bytes of internal fragmentation

What this code does

2³² ÷ 2¹² = 2²⁰ pages, and 2²⁰ entries × 4 bytes = 4 MB of page table for every process. That cost is why real systems use multi-level page tables, which store only the parts in use.
The process needs 35 full pages plus 1,086 bytes, so the 36th page wastes 2,048 − 1,086 = 962 bytes. On average, internal fragmentation is about half a page per process.

Memory numericals in interviews are usually one of three: translate an address, find the page-table size, or compute internal fragmentation.

Number of pages = address space ÷ page size.
Page-table size = number of pages × entry size.
Waste in the last page = page size − (process size mod page size); on average about half a page per process.

Revise: Virtual memory and page replacement (opens in a new tab)

Predict the output

Memory numericals

Pick the output of each calculation.

Round 1 of 2

2^20 pages and 4-byte entries. How big is the page table?

pages = 1 << 20

entry_bytes = 4

print(pages * entry_bytes // 1024 // 1024, "MB")

Next step

Check your understanding

12 quick questions

1def allocate(strategy, holes_start, requests):2 holes = holes_start[:]3 out = strategy + ":"4 for req in requests:5 fits = [i for i, h in enumerate(holes) if h >= req]6 if not fits:7 out += f" {req}K->wait"8 continue9 if strategy == "First fit":10 pick = fits[0]11 elif strategy == "Best fit":12 pick = min(fits, key=lambda i: holes[i])13 else:14 pick = max(fits, key=lambda i: holes[i])15 out += f" {req}K->hole{pick + 1}"16 holes[pick] -= req # the rest stays as a smaller hole17 print(out)18 print(" holes left:", holes)19 20 21holes = [100, 500, 200, 300, 600] # KB22requests = [212, 417, 112, 426] # KB, in arrival order23for strategy in ("First fit", "Best fit", "Worst fit"):24 allocate(strategy, holes, requests)

First fit: 212K->hole2 417K->hole5 112K->hole2 426K->wait holes left: [100, 176, 200, 300, 183] Best fit: 212K->hole4 417K->hole2 112K->hole3 426K->hole5 holes left: [100, 83, 88, 88, 174] Worst fit: 212K->hole5 417K->hole2 112K->hole5 426K->wait holes left: [100, 83, 200, 300, 276]

Paging: pages, frames, page table, worked address translation

Paging divides logical memory into fixed-size pages and physical memory into frames of the same size, and a page table maps each page number to a frame number.

The program below translates logical addresses with the page table [5, 9, 7, 2] and a page size of 1024 bytes, and prints the page, offset, frame and physical address.

1page_size = 1024 # 1 KB = 2^10, so the offset is 10 bits2page_table = [5, 9, 7, 2] # page -> frame3addresses = [2500, 100, 3071, 4096]4 5for logical in addresses:6 page, offset = divmod(logical, page_size)7 if page >= len(page_table):8 print(f"{logical}: page {page} is outside the table -> trap")9 continue10 physical = page_table[page] * page_size + offset11 print(f"{logical}: page {page}, offset {offset}, frame {page_table[page]} -> physical {physical}")12 13logical = 250014print(f"Same with bits: page {logical >> 10}, offset {logical & 1023}")

2500: page 2, offset 452, frame 7 -> physical 7620 100: page 0, offset 100, frame 5 -> physical 5220 3071: page 2, offset 1023, frame 7 -> physical 8191 4096: page 4 is outside the table -> trap Same with bits: page 2, offset 452

1def eat(hit, tlb, mem):2 return hit * (tlb + mem) + (1 - hit) * (tlb + 2 * mem)3 4 5tlb, mem = 20, 100 # nanoseconds6for hit in (0.80, 0.90, 0.98):7 t = eat(hit, tlb, mem)8 print(f"Hit ratio {hit * 100:.0f}%: EAT = {t:.1f} ns (slowdown {(t - mem) / mem * 100:.0f}%)")9print(f"Without a TLB: {2 * mem:.1f} ns")

Segmentation and how it differs from paging

Segment is a logical, variable-size part of a program, such as code, stack or heap; a logical address is a pair (segment number, offset) checked against the segment's limit.

A segmented address is a pair (segment number, offset). The segment table below gives each segment its base and limit; the program after it translates five addresses and traps the bad ones.

1Segment Base Limit2 0 1400 10003 2 4300 4004 3 3200 11005(2, 53) -> 53 < 400 -> 4300 + 53 = 43536(3, 852) -> 852 < 1100 -> 3200 + 852 = 40527(0, 1222) -> 1222 >= 1000 -> trap

1base = [1400, 6300, 4300, 3200, 4700]2limit = [1000, 400, 400, 1100, 1000]3requests = [(2, 53), (3, 852), (0, 1222), (1, 399), (4, 1000)]4 5for seg, offset in requests:6 if offset < limit[seg]:7 result = f"physical {base[seg] + offset}"8 else:9 result = f"trap: offset {offset} >= limit {limit[seg]}"10 print(f"({seg}, {offset}) -> {result}")

1address_space = 1 << 32 # 32-bit logical addresses2page_size = 4 * 1024 # 4 KB3entry_size = 4 # bytes per page-table entry4pages = address_space // page_size5print(f"Pages: {pages} (2^{pages.bit_length() - 1})")6print(f"Page table: {pages * entry_size // (1024 * 1024)} MB per process")7 8process_size, page_2k = 72_766, 20489pages_needed = -(-process_size // page_2k) # ceiling division10wasted = pages_needed * page_2k - process_size11print(f"72,766-byte process, 2 KB pages: {pages_needed} pages, {wasted} bytes of internal fragmentation")