Operating systems

Segmentation

Prashanth L.A.

2023-09-05

Lecture 15

So far

OS illusion: memory virtualization
Dynamic relocation via base and bounds

An address space

Why isn’t base and bounds optimal

Wastes free space
May not be able to fit many processes in main memory

Solution: Segmentation

Segmentation

Segment: a contiguous portion of the address space of a particular length
- Examples: code, stack, heap

Place each segment in a different part of physical memory .
- Need base and bounds for each segment

Handling segments

Need three base+bounds register pairs;

Segment Base Size

Code 32K 2K

Heap 34K 2K

Stack 28K 2K

Segment	Base	Size
Code	32K	2K
Heap	34K	2K
Stack	28K	2K

Segment Base Size: (Code, 32K, 2K), (Heap, 34K, 2K), (Stack, 28K, 2K)

Code translation
- Virtual address \(= 100\)
- This refers to code segment
- Physical address \(= 32768 + 100 = 32868\)
Heap translation
- Virtual address \(= 4200\)
- Physical address is not \(34KB+4200\)
- Heap starts at virtual address \(4KB\)
- Virtual offset is \(4200-4KB=104\)
- Phy addr \(= 34KB + 104 = 34920\)

Segmentation Fault

arises from a memory access on a segmented machine to an illegal address
E.g. virtual address beyond heap
- hardware generates out of bounds
- OS usually terminates the process

Which segment am I referring to?

Use top few bits of virtual address to identify the segment

\(00 \rightarrow\) code, \(01 \rightarrow\) heap and so on

Address translation

\(01 \rightarrow\) heap, \(0000 0110 1000\), or hex \(0x068\), or decimal \(104\) is the offset

Implementation

// get top 2 bits of 14-bit VA
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
// now get offset
Offset  = VirtualAddress & OFFSET_MASK
if (Offset >= Bounds[Segment])
    RaiseException(PROTECTION_FAULT)
else
    PhysAddr = Base[Segment] + Offset
    Register = AccessMemory(PhysAddr)

What about backwards-growing segments?

Segment	Base	Size (max \(4K\))	Grows positive?
Code	32K	2K	1
Heap	34K	2K	1
Stack	28K	2K	0

Stack translation
- Virtual address \(= 15KB = 1536010 = 111100000000002_2\)
- Top 2 bits say stack
- Remaining: \(1100000000002_2 = 3KB\)
- Negative offset = \(3KB\) minus max segment size \(= 3KB-4KB=-1KB\)
- Stack base is \(28KB\)
- Phy addr \(= 28KB - 1KB = 27KB\)

Lecture 16

Sharing segments

Code sharing is useful, so is data sharing
Need hardware support to implement sharing
Protection bits: indicate permissions (read/write/execute)

Example

Segment	Base	Size (max \(4K\))	Grows positive?	Permissions
Code	32K	2K	1	Read-execute
Heap	34K	2K	1	Read-write
Stack	28K	2K	0	Read-write

Non-compacted and Compacted Memory

Fragmentation

External Fragmentation

Physical memory is full of little holes of free space
- difficult to allocate new segments, or grow existing ones

Compaction

Rearrange physical memory so that segments are continuous
Costly to compact since processes have to be stopped, and segments copied

Last slide

Segmentation gets you part of the way there, but still leaves us short of a truly general VM
Next stop: paging.