Contiguous Allocation

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

Multiple-partition allocation

  ✦ 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.

Fragmentation

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.