Outline
- Relocation and relocation registers.
- Overlays and segments.
- Segments and pages.
- Segments and protection.
Relocation
- Relocation turns an relatively-addressed program into an absolutely
addressed one.
- Relocation involves adding a base address to every offset in a
program.
- Relocation is an O(n) operation, where n is the number of
offsets.
- Re-relocation is difficult, because the offsets have to be recovered
from the addresses.
- And it can be tricky to figure out where the addresses are.
Relocation Registers
- Relocation registers provide a more flexible way to relocate relative
code.
- The CPU has a relocation (or base) register holding a
base address.
- Program addresses are kept as offsets.
- On address issue, the CPU adds an offset to the relocation register to
produce the absolute physical address.
Relocation Registers
- Relocation registers add cost to the system:
- CPU real estate for the relocation register.
- An extra addition in each address issue.
- Loading and saving the relocation register.
- However, relocation registers can relocate (and re-relocate) a process
in constant time.
- They can also provide increased protection.
Overlays
- Relocation registers work well with overlays.
- The overlay region is indicated by the relocation register.
- The compiler can produce relative addresses with no further
information (no more overlay map).
Segmented Memory
- Segmented memory is a generalization of overlays with relocation
registers.
- Fitting segments in physical storage isn't as important as it is for
overlays.
- A program consists of one or more segments.
- The CPU has a bank of n relocation registers, usually
rechristened segment (or segmentation) registers.
Typed Segments
- A process's segments can be typed by the information it contains.
- A code segment contains only program code.
- A data segment contains only data.
- Further typing based on the data is also possible: stack or heap
segments, for example.
Typed Segment Registers
- The CPU keeps separate relocation registers for segments of each type.
- A code-relocation register, a data-relocation register, a
stack-relocation register, and so on.
- Sometimes the compiler has to simulate this with untyped relocation
registers.
Typed Security
- Typed segments add security to the system.
- Only code segments are executable, only data segments are writable.
- It's not possible to execute out of a smashed stack segment.
- Data can be isolated in separate segments, eliminating
potential cross-contamination.
Segment Fragmentation
- Segments trade internal fragmentation for external fragmentation.
- Each segment fits its contents exactly (to the nearest storage unit).
- Segments may be placed in physical storage to block out other
segments.
- Segment relocation is possible (and easier with relocation registers)
but expensive.
Paged Segments
- External fragmentation can be traded-off for internal fragmentation by
paging segments.
- Each segment may waste almost a page of storage.
- Segment pages can be placed in arbitrarily page frames.
- The paging mechanism is as it was for straight VM.
Delimited Segments
- A pair of segment registers can be used to delimit a segment.
- The second register contains the top address or segment size.
- Accesses outside the delimited range are illegal.
- The compiler can exploit this by allocating each array in its own
segment.
- The segment-register manipulations get tricky.
Segmented Memory History
- Early machines provided segmented memory.
- Segmentation hardware is cheaper than paging hardware.
- It helped overcome small physical memories.
Segmented Memory Currently
- Paging won.
- Simpler compilers and run-time management.
- Intel still supports segmented memory.
- Flat, flat paged, segmented, and segmented paged.
- Early choices by Intel made segmented memory excruciatingly hard to
use.
This page last modified on 19 November 2004.