Non-Contiguous Memory Allocation
Tom Kelliher, CS42
Oct. 28, 1996
Problems with contiguous allocation:
- Problems with fixed partitions:
- Limited degree of multiprogramming.
- Internal fragmentation.
- Placement policies.
- Problems with variable partitions:
- External fragmentation, compaction.
- Swapping is difficult, if not impossible (address binding).
Alternative: non-contiguous allocation.
- Entire process in memory.
- Partition memory into frames of size .
- Typical frame sizes: 512 to 8K bytes.
- Frame size constrained by MMU design.
- Logical address space is broken into pages.
- Page size = frame size.
- Pages can be arbitrarily mapped onto frames.
- However, process ``sees'' a contiguous, flat address space.
- MMU splits logical address:
- Assume logical address is n bits.
- Page number field is n - m most significant bits.
- Page offset field is m least significant bits.
- Using table look-up, convert logical page number to physical frame
- Frame offset = page offset.
Why is frame, page size a power of two?
- Page size:
- Internal fragmentation.
- Maximizing I/O transfer rate.
- I/O --- process passes logical address to kernel.
- Implementation of the page table.
- Small register file.
- Array in memory.
- Issues for memory implementation:
- Page table must be in contiguous memory.
- Page table base register.
- ``Logical memory access'' requires two physical accesses.
- Translation look-aside buffer.
- TLB entries contain: Page number, frame number pairs.
- Issue: Context switches.
- Only a few entries needed.
- Problem: huge page tables. How did this happen?
- Valid/invalid bit.
- Page table limit register.
- Multi-level paging.
Why not just use the limit register?
A two-level paging scheme for a 32-bit logical address:
Is the page table really any smaller?
What does this solve?
- Non-contiguous (paged) page table.
- ``Holes'' in page table (valid bit) shrink it.
Sun SPARC: 3 level paging.
64-, 128-bit logical addresses?
- Is it possible for a process to access an arbitrary memory location?
- Using valid bit to introduce ``holes'' into logical address space.
- What can be shared?
- Read-only pages.
- Page alignment --- segment the logical address space.
- Page de-allocation.
- ``Object oriented'' approach:
- User views program as a set of objects:
- Each object stored in a segment.
- Generalization of paging.
- Logical address is a segment ``name'' and an offset.
- Variable-sized ``page'' having a base and length.
- Frames start on memory boundaries. Segments start anywhere.
Therefore, must add a segment base and offset.
- Straight paging: external fragmentation.
- Solution: Paged segmentation (x86 architecture).
Thomas P. Kelliher
Fri Oct 25 16:55:29 EDT 1996