Skip to main content

Segmentation; page table size; TLB

Short answer

Segmentation divides logical address space into variable-sized segments matching program structure, each with base and limit. For 48-bit virtual with 4KB pages, page table has 2^36 entries. TLB is very effective: one miss per 512 array accesses (99.8% hit rate) due to spatial locality, with most 32 entries unused.

What is segmentation? Suppose a machine has 48 bit virtual addresses and 32 bit physical address. a) If pages are 4KB, how many entries are in the page table? b) Suppose the same system has a TLB (Translation Look aside Buffer) with 32 entries. Furthermore suppose that a program contains instructions that fit into one page and it sequentially reads long integer elements from an array that spans thousands of pages. How effective will the TLB be for this case?

Segmentation

Segmentation is a memory-management scheme that divides a program's logical address space into variable-sized logical units called segments (main program, procedures, stack, data, symbol table), matching the programmer's view. A logical address is a pair (segment number s, offset d). A segment table has for each segment a base (starting physical address) and a limit (length). The hardware checks d < limit, then physical address = base + d; otherwise it traps.

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

Advantages: supports sharing and protection per segment, no internal fragmentation, grows dynamically. Disadvantage: external fragmentation.

a) Page table entries

  • Virtual address = 48 bits; page size 4 KB = 2¹² bytes, so offset = 12 bits.
  • Page number bits = 48 − 12 = 36.
  • Entries = 2³⁶ = 68,719,476,736 (about 6.9 × 10¹⁰).

Answer: 2³⁶ entries in the page table. (A single-level table is impractical, so multi-level or inverted tables are used.)

b) Effectiveness of the TLB

  • Instructions occupy one page, so one TLB entry holds its translation and stays there: all instruction fetches hit after the first.
  • The array is read sequentially. With 8-byte (long) elements, a 4 KB page holds 4096/8 = 512 elements. The first access to each new page is a TLB miss; the next 511 accesses to that page hit.
  • Data hit ratio = 511/512 ≈ 99.8% (about 99.9% for 4-byte integers). Including instruction fetches the overall hit ratio is even higher.
  • The array pages are never reused, so the 32 entries bring no temporal-locality benefit; only about 2 entries are really used (one for code, one for the current array page). The TLB is effective only because of spatial locality (sequential access), not because of its size.

Answer: very effective, about one miss per 512 data accesses (about 99.8% hit rate), although most of the 32 entries are not needed.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Operating System chapter 4 questions →