Segmentation, and segmentation with paging

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. EAT with a TLB (one level)? from Lesson 5.2.2
2. Which kind of fragmentation does paging have? from Lesson 5.2.1
3. What check does the limit register perform? from Lesson 5.1.1

1 · The Hook

A programmer thinks of a program as parts: "the main code", "the array", "the stack", not as "page 17". Segmentation divides memory the way programmers think: each part is a segment with its own size. GATE asks you to translate (segment, offset) pairs and to say which ones trap.

3 · Core Concept

Predict First — the answer

(1, 120) → 5120. (1, 350): 350 ≥ 300 → trap.

In plain words

Each segment is like a small base-and-limit block of its own. A logical address names a segment and an offset inside it. The segment table stores each segment's start (base) and length (limit). The offset must be smaller than the limit.

1. Segmentation

• Logical address = (segment number s, offset d).
• Segment table entry s = (base, limit).
• If d < limit: physical = base + d; otherwise trap.

Example segment table:

• (0, 450) → 2450. (1, 350) → trap. (2, 100) → 1300. (3, 899) → 4399.

2. Paging vs segmentation

3. Segmentation with paging

Each segment is itself paged: logical address = (s, p, d). The segment table entry points to that segment's page table; the limit check uses the segment length. This keeps the logical view of segments and the no-external-fragmentation benefit of paging (used by Intel x86 in 32-bit mode).

4 · Visual

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

Table: seg 0 (2000, 600)  seg 1 (5000, 300)  seg 2 (1200, 500)  seg 3 (3500, 900)
(0,450) -> 2450   (1,350) -> trap   (2,100) -> 1300   (3,899) -> 4399

5 · Worked Examples

Example 1 Easy

Using the table above, translate (3, 100).

Solution

100 < 900 → 3500 + 100 = 3600.

Example 2 Medium

Using the table above, which of (0, 600), (2, 499), (1, 0) trap?

Solution

Only (0, 600): 600 is not < 600. (2, 499) → 1699; (1, 0) → 5000.

Example 3 GATE

A system uses segmentation with paging. A segment is 9 KB and pages are 4 KB. How many frames does the segment occupy, and how much is wasted inside them?

Solution

⌈9 / 4⌉ = 3 frames; 12 − 9 = 3 KB of internal fragmentation.

6 · GATE Traps

• The offset check is d < limit (strictly less).
• Segmentation has external fragmentation (variable sizes), paging internal.
• In segmentation the segment number is not taken from "high bits of a flat address"; it is a separate part of the address.
• With segmentation + paging, the final waste is internal (last page of each segment).

7 · Memory Hook

"Segment = base + limit per part. Offset under limit, or trap."

8 · Connect the Dots

Chapters 5.1 and 5.2 are complete: we can place, translate and protect a program that sits fully in memory. Chapter 5.3 removes the last requirement: with virtual memory only the pages actually in use need to be in RAM.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Translation

Segment 2 has base 1200 and limit 500. Physical address of (2, 340)?

Numerical answer: ________

Q2 · MCQ · 1 mark(s) — Trap

Segment 0 has base 2000 and limit 600. Logical address (0, 600) gives:

1. (A) 2000
2. (B) 600
3. (C) 2600
4. (D) a trap

Q3 · MCQ · 1 mark(s) — Fragmentation

Pure segmentation suffers from:

1. (A) no fragmentation
2. (B) external fragmentation
3. (C) internal fragmentation
4. (D) Belady's anomaly

Q4 · NAT · 2 mark(s) — Translation

Segment table: segment 3 has base 3500, limit 900. Physical address of (3, 899)?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Segmentation with paging

In segmentation with paging, a logical address consists of:

1. (A) (segment, offset) translated by base + offset only
2. (B) (page, offset)
3. (C) (segment, page, offset)
4. (D) (frame, offset)

10 · Rule Card

• Segment table entry (base, limit); (s, d) → base + d if d < limit, else trap.
• Paging: equal pieces, internal fragmentation. Segmentation: logical pieces, external fragmentation, natural sharing/protection.
• Segmentation with paging: (s, p, d); each segment paged.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

segmentsegment number and offsetsegment tablesegment base and limitsegmentation trappaging vs segmentationsegmentation with paging