The contiguous memory allocation uses memory partitions to allocate memory. These partitions could be fixed or variable size partitions allocated according to first fit, best fit, or wort fit method. The memory fragmentation is a common problem that affects these partition memory allocation system.
Contiguous Memory
Contiguous memory allocation is a method of allocating memory to OS and user processes. The memory is divided
into two partitions
1. For resident OS.
2. For user processes.
The OS can be placed in lower memory or higher memory, it is usually in the lower memory because the interrupt vector
is placed in lower memory. We want to allocate memory to several processes at the same time, therefore, each
process is allocated a single contiguous section of memory.
Contiguous Memory Allocation Methods
The simplest method of memory allocation is to divide memory into fixed-sized partition. Each partition may or may
not contain exactly one process. When a partition is free, a process is selected from the input queue and loaded into
the fixed partition. The memory is available again when the process terminates.
Example:
IBM OS/360 called MFT used this method.
There is another way of allocating memory is using variable partitions. The OS keeps a table of occupied memory
and free memory. Initially, when no process is running in userspace, it is one large block of free memory called ahole.
In this scheme, the process scheduler selects a process from the input queue and consider the following:
- The memory requirements of the process.
- Compute the available memory for user processes.
- Allocate memory and load the process for execution.
- If there is not enough memory to accommodate the process, OS waits for memory to be available, or swap the
process with a smaller one from the queue with smaller memory requirements. - There are a lot of smaller adjacent holes of various sizes, OS can combine those to form a bigger hole to allocate memory to process.
- The OS can split a larger hole to create smaller holes for processes.
Strategies To Allocate Free Memory Holes
The operating system search for a free hole for the process of size n from available free memory. The first-fit, best-
fit and the worst-fit strategies are used to select a free hole.
First Fit Method:
Allocate the first hole that is big enough for the process. Either start looking from the beginning of a memory or start where previous first-fit allocation ended. Stop the search as soon as a match is found.
Best Fit Method:
Find the smallest hole that is big enough to fit the process.
Worst Fit Method:
Find the largest hole for the input process.
Memory Fragmentation
The memory fragmentation is a problem of little pieces of memory that cannot be used and wasted during dynamic memory allocation.
Internal Fragmentation:
The internal fragmentation is caused due to unused leftover space within a partition. For example, if a process requests for a hole size of 15340 bytes and the hole size of 15344 bytes is available. The leftover would be 4 bytes which are completely wasted.
A solution to this problem is to split physical memory into blocks of equal size and allocate block sized memory to process slightly larger than the requested memory. This will reduce the unused memory internal to the block partition.
External Fragmentation:
The external fragmentation happens when processes are allocated memory using best fit or first fit methods. The memory becomes non-contiguous and broken into smaller pieces. The problem of external fragmentation could be severe such that there is a lot of fragmented pieces of memory between two processes.
A solution to external fragmentation is compaction which brings all free memory together making one large block of a free hole. This solution is possible at run-time only. If possible then we could relocate all running process to one direction and free holes in other direction.
The other solution to external fragmentation is to allow virtual memory to be non-contiguous and allocate physical memory when available. This scheme is called paging.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edn., Wiley.
- Ramez Elmasri, A Carrick, David Levine (February 11, 2009) Operating Systems: A Spiral Approach, 1st edn., McGraw-Hill Education.
- Tanenbaum, Andrew S. (March 3, 2001) Modern Operating Systems, 2nd edn., Prentice Hall.
