Main memory usually into two partitions:
✦ Resident operating system, usually held in low memory with interrupt vector.
✦ User processes then held in high memory. Single-partition allocation
✦ Relocation-register scheme used to protect user processes from each other, and from changing
operating-system code and data.
✦ Relocation register contains value of smallest physical address; limit register
contains range of logical addresses – each logical address must be less than the limit register.
Hardware Support for Relocation and Limit Registers
✦ Hole – block of available memory; holes of various size are scattered throughout memory.
✦ When a process arrives, it is allocated memory from a hole large enough to accommodate it.
✦ Operating system maintains information about:
a) allocated partitions b) free partitions (hole)
Dynamic Storage-Allocation Problem
First-fit: Allocate the first hole that is big enough.
Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size.
Produces the smallest leftover hole.
Worst-fit: Allocate the largest hole; must also search entire list. Produces the largest leftover hole.
How to satisfy a request of size n from a list of free holes.
First-fit and best-fit better than worst-fit in terms of speed and storage utilization.
External Fragmentation – total memory space exists to satisfy a request, but it is not contiguous.
Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used.
Reduce external fragmentation by compaction
✦ Shuffle memory contents to place all free memory together in one large block.
✦ Compaction is possible only if relocation is dynamic, and is done at execution time.
✦ I/O problem
✔ Latch job in memory while it is involved in I/O.
✔ Do I/O only into OS buffers.