--- title: "Segmentation; page table size; TLB" subject: "Operating System" chapter: 4 key: "semester_6/operating_system:segmentation-address-bits-tlb" source: https://www.bctengineer.com/q/semester_6/operating_system/segmentation-address-bits-tlb site: BCT Engineering --- # Segmentation; page table size; TLB Operating System · Chapter 4: Memory Management - Asked in: 2068 Bhadra, 3+5 marks - Video: [Virtual Memory: 5 Page Tables](https://www.youtube.com/watch?v=KNUJhZCQZ9c) — David Black-Schaffer - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/segmentation-address-bits-tlb - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-4 ## Question 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? ## 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. ## Answer #### 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. ```text (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.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is a physical address obtained in segmentation? A. Check d < limit, then base + d B. Add the page number to the offset C. Divide the address by segment size D. Look up a frame number and append offset Answer: A. The segment table gives base and limit; out-of-range offsets trap. (Key point: Segment address translation) 2. With 48-bit virtual addresses and 4 KB pages, how many page table entries? A. 2^48 B. 2^32 C. 2^36 D. 2^12 Answer: C. Offset is 12 bits, so page number is 48 - 12 = 36 bits. (Key point: Page table entries) 3. Why is the TLB effective for sequential array reads? A. The 32 entries are all used B. Spatial locality: 512 long elements per page give about 1 miss per 512 accesses C. Temporal reuse of array pages D. Array pages stay in the TLB forever Answer: B. 4096/8 = 512 elements per page, so hit rate is about 99.8%. (Key point: TLB effectiveness) 4. Which fragmentation does segmentation suffer from? A. None B. External fragmentation C. Internal fragmentation only D. Page-table fragmentation only Answer: B. Variable-sized segments leave external holes. (Key point: Segmentation fragmentation) ## Related in Operating System - [Page fault; virtual to physical address](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-64k-virtual-32k-physical) — Operating System, chapter 4 - [Page fault, demand paging, address translation](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-demand-paging-address) — Operating System, chapter 4 - [Logical and physical address bits](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Aresidence-monitor-address-bits) — Operating System, chapter 4 - [Page size impact; internal, external fragmentation](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-size-impact-fragmentation) — Operating System, chapter 4 - [Virtual machine structure and benefits](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Avirtual-machine-structure) — Operating System, chapter 1, asked 2× - [OS as virtual machine; functions](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Aos-virtual-machine-functions) — Operating System, chapter 1 ## Related in other subjects - [Poisson: error pages in 400-page novel](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Apublisher-typo-pages-400) — Probability and Statistics, chapter 2 - [Why n-type has many conduction electrons](https://www.bctengineer.com/question.md?key=semester_3%2Felectrical_engineering_material%3Antype-electrons-conduction-band) — Electrical Engineering Material, chapter 6 - [Machine translation and challenges](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Amachine-translation-challenges) — Artificial Intelligence, chapter 7 - [8255A at 80H: addresses, mode 0/1 words, BSR](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Appi-80h-addresses-control) — Instrumentation II, chapter 2