Chapter 16.

Segmentation
Operating System: Three Easy Pieces
 Inefficiency of the Base and Bound Approach
0KB
1KB Program Code  Each process address space must be allocated
2KB
3KB contiguously in physical memory.
4KB
5KB Heap  Big chunk of “free” space
6KB
 “free” space takes up physical memory.

 Dynamic relocation with a pair of base and bounds

registers to virtualize memory is wasteful.
(free)

14KB
15KB Stack
16KB
Segmentation
 How to support a large address space with a lot of free space between the stack and
the heap?

 Segment is just a contiguous portion of the address space of a particular length.

 Logically-different segment: code, stack, heap

 Each segment can be placed in different part of physical memory.

 Base and bounds exist per each segment.

 Each segment grow and shrink independently.

Placing Segments in Physical Memory

0KB

Operating System

16KB Segment Register

(not in use)
Segment Base Size
Stack Code 32K 2K
(not in use)
32KB Heap 34K 2K
Code
Heap Stack 28K 2K

48KB
(not in use)

64KB
Physical Memory
Address Translation on Segments
𝑝ℎ𝑦𝑠𝑖𝑐𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 = 𝑜𝑓𝑓𝑠𝑒𝑡 + 𝑏𝑎𝑠𝑒

 The offset of virtual address 100 is 100.

 The code segment starts at virtual address 0 in address space.

Segment Register
Segment Base Size 16KB
Code 32K 2K
(not in use)

0KB 32KB 𝟏𝟎𝟎 + 𝟑𝟐𝑲 𝒐𝒓 𝟑𝟐𝟖𝟔𝟖

100 instruction
Code
is the desired
Program Code physical address
2KB 34KB
Heap
4KB

(not in use)
Address Translation on Segment (Cont.)
𝑽𝒊𝒓𝒕𝒖𝒂𝒍 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 + 𝒃𝒂𝒔𝒆 is not the correct physical address.

 The offset of virtual address 4200 is 104 (4200 – 4K = 104).

 The heap segment starts at virtual address 4096 in address space.
Segment Register
Segment Base Size
Heap 34K 2K
(not in use)

32KB
Code
4KB 34KB 𝟏𝟎𝟒 + 𝟑𝟒𝑲 𝒐𝒓 𝟑𝟒𝟗𝟐𝟎
4200 data
Heap
is the desired
Heap physical address
6KB 36KB

(not in use)
Address Space

Physical Memory
Segmentation Fault or Violation
 If an illegal address such as 7KB which is beyond the end of heap is referenced, the
OS occurs segmentation fault.
 The hardware detects that address is out of bounds.

Segment Register
4KB Segment Base Size
Heap Code 32K 2K
6KB Heap 34K 2K
7KB Stack 28K 2K
(not in use)
8KB

Address Space
Referring to Segment
 Explicit approach
 Chop up the address space into segments based on the top few bits of virtual address.
13 12 11 10 9 8 7 6 5 4 3 2 1 0

Segment Offset

 Example: virtual address 4200 (01000001101000)

Segment bits 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Code 00 0 1 0 0 0 0 0 1 1 0 1 0 0 0
Heap 01
Stack 10
- 11 Segment Offset
Referring to Segment (Cont.)
1 // get top 2 bits of 14-bit VA
2 Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
3 // now get offset
4 Offset = VirtualAddress & OFFSET_MASK
5 if (Offset >= Bounds[Segment])
6 RaiseException(PROTECTION_FAULT)
7 else
8 PhysAddr = Base[Segment] + Offset
9 Register = AccessMemory(PhysAddr)

 SEG_MASK = 0x3000(11000000000000)

 SEG_SHIFT = 12

 OFFSET_MASK = 0xFFF (00111111111111)

Referring to Stack Segment
 Stack grows backward (towards lower address).

 Extra hardware support is need.

 The hardware checks which way the segment grows.

 1: positive direction, 0: negative direction

Segment Register(with Negative-Growth Support)

Segment Base Size (max 4K) Grows Positive?

(not in use)
Code 32K 2K 1
Heap 34K 2K 1
26KB
Stack 28K 2K 0
Stack
28KB
(not in use)

Physical Memory
Address Translation on Stack Segmentation
𝑝ℎ𝑦𝑠𝑖𝑐𝑎𝑙 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 = 𝑜𝑓𝑓𝑠𝑒𝑡 + 𝑏𝑎𝑠𝑒

 Example: virtual address 15KB (11 1100 0000 0000)

 The stack segment starts at virtual address 16KB in address space.

 The offset is -1KB.

Segment Register(with Negative-Growth Support)

Segment Base Size(max 4K) Grows Positive?

Stack 28K 2K 0

(not in use)

14KB 26KB
𝟐𝟖𝑲𝑩 − 𝟏𝑲𝑩 = 𝟐𝟕𝑲𝑩 is the
15 KB Stack Stack
desired physical address
16KB 28KB

(not in use)
Address Space
 Support for Sharing
 Segment can be shared between address space.
 Code sharing is still in use in systems today.

 by extra hardware support.

 Extra hardware support is need for form of Protection bits.

 A few more bits per segment to indicate permissions of read, write and execute.

 Hardware checks:
 Whether a virtual address is within bounds Segment Register Values(with Protection)
Segment Base Size Grows Positive? Protection
 A particular access is permissible?
Code 32K 2K 1 Read-Execute
o Write to a read-only segment Heap 34K 2K 1 Read-Write
Stack 28K 2K 0 Read-Write
o Execute from a non-executable segment

 Hardware raises an exception upon out-of-bounds, or authorized operations

 Fine-Grained vs. Coarse-Grained Segmentation
 Coarse-Grained means segmentation in a small number.
 e.g., code, heap, stack.

 Fine-Grained segmentation allows more flexibility for address space in some early system.
 To support many segments, hardware support with a segment table is required.
 OS Support: Fragmentation
 External Fragmentation: little holes of free space in physical memory that make difficulty to
allocate new segments.
 There is 24KB free, but not in one contiguous segment.
Not compacted Compacted
 The OS cannot satisfy the 20KB request.
0KB 0KB
 Compaction: rearranging exiting segments in physical memory.
8KB Operating System 8KB Operating System
 Compaction is costly.
 Stop running process. 16KB 16KB
 Copy data to somewhere. (not in use)
24KB 24KB
 Change segment register value.
Allocated Allocated
 Other approaches 32KB 32KB
 best-fit, worst-fit, first-fit, buddy algorithm, etc. (not in use)
40KB 40KB
 external fragmentation will still exist Allocated
 a good algorithm attempts to minimize it. 48KB 48KB
(not in use) (not in use)
56KB 56KB
Allocated
64KB 64KB