(The last two alternatives are kludges used for
machines with such small addresses that there is not room for both a segmentnumber and an offset)
Segment table holds the bases and bounds for all
the segments of a process.
Show memory mapping procedure, involving table
lookup + add + compare. Example: PDP-10 with high and low segments selected byhigh-order address bit.
Segmentation example: 8-bit segment number, 16-bit
offset.
- Segment table (use above picture -- all numbers in hexadecimal):
- Code in segment 0 (addresses are virtual):
- 0x00242:mov 0x60100,%r1
- 0x00246:st %r1,0x30107
- 0x0024A:b 0x20360
- Code in segment 2:
- 0x20360:ld [%r1+2],%r2
- 0x20364:ld [%r2],%r3
- ...
- 0x203C0:ret
Advantage of segmentation: segments can be swapped
and assigned to storage independently.
Problems:
- External fragmentation: segments of many different sizes.
- Segments may be large, have to be allocated contiguously.
- (These problems also apply to base and bound schemes)
Example: in PDP-10's when a segment gets larger, it
may have to be shuffled to make room. If things get really bad it may benecessary to compact memory.
Paging
Goal is to make allocation and swapping easier, and
to reduce memory fragmentation.
- Make all chunks of memory the same size, call them pages. Typical
sizes range from 512-8k bytes.
- For each process, a page table defines the base address of each of
that process' pages along with read/only and existence bits.
- Page number always comes directly from the address. Since page
size is a power of two, no comparison or addition is necessary. Just do tablelookup and bit substitution.
- Easy to allocate: keep a free list of available pages and grab the
first one. Easy to swap since everything is the same size, which is usually thesame size as disk blocks to and from which pages are swapped.
- Problems:
- Internal
fragmentation: page size does not match up with information size. The larger thepage, the worse this is.
- Table space: if pages are small, the table
space could be substantial. In fact, this is a problem even for normal pagesizes: consider a 32-bit address space with 1k pages. What if the whole table
has to be present at once? Partial solution: keep base and bounds for pagetable, so only large processes have to have large tables.
- Efficiency of access: it may take one overhead reference for every
real memory reference (page table is so big it has to be kept in memory).
Two-level (multi-level) paging
Use two levels of mapping to make tables
manageable.
Segmentation and paging
Use two levels of mapping, with logical sizes for
objects, to make tables manageable.
- Each segment contains one or more pages.
- Segment correspond to logical units: code, data, stack. Segments
vary in size and are often large. Pages are for the use of the OS; they arefixed size to make it easy to manage memory.
- Going from paging to P+S is like going from single segment to
multiple segments, except at a higher level. Instead of having a single pagetable, have many page tables with a base and bound for each. Call the material
associated with each page table a segment.
