3.1.3 Compaction

Compaction is a solution to the problem of external fragmentation. The objective is to shuffle the contents of the memory in order to place all the free memory together in a single large block.
Compaction is not always possible. Note that once a process has been moved, its internal addresses must be translated. If the connection is static (when writing the program, during translation or separated) we cannot perform compaction. The latter is only possible if the connection is dynamic.

The simplest compaction algorithm involves moving all processes to one end of memory. All holes move in the other direction thus producing a large block of available memory, this scheme is very expensive.

Example of multiplicity of solutions:

The figure bellow depicts three possible ways with three different costs to compact the given memory case (most left sub-figure). 

3.2. Paging

Another possible solution to the problem of external fragmentation is to allow the logical address space of a process to be non-contiguous; thus allowing the allocation of physical memory to a process where it is available.

3.2.1 Simple paging

Physical memory is divided into blocks of fixed size called page frames. The logical memory of a process is also subdivided into blocks of the same size called pages.
When we need to execute a process we load its pages into the memory page frames available from the auxiliary memory.

The size of the page (like that of the frame) is defined by the hardware. It is typically a power of 2 varying between 512 bytes and 8192 bytes per page, depending on the architecture of the computer. The figure below shows the hardware support needed for paging as well as the translation of a logical address to a physical address.

Choosing a power of 2 as the page size makes it particularly easy to translate a logical address into a page frame number and move within the page frame.
If the size of the logical memory is 2^m and the size of the page is 2ⁿ addressing units (bytes or words) the most significant m-n bits of a logical address designate the page number and the n bits of low order designate the offset on the page. The figure below shows the shape of a logical address.

p: represents the index in the page table
d: offset in the page or page frame