Contiguous Memory Allocation
Contiguous memory allocation is a memory allocation scheme where a process is allocated a continuous block of memory. This approach helps manage memory efficiently but can lead to various fragmentation issues.
In this article, we'll explore different types of contiguous memory allocation, issues like internal and external fragmentation, and common allocation methods used by operating systems.
Fixed Partitioning​
Fixed partitioning divides the main memory into fixed-sized partitions at system initialization. Each partition can hold exactly one process. For example, memory might be divided into 4 MB partitions, with each partition allocated to a single process. While this approach is straightforward, it can cause several issues.
Fragmentation​
Fragmentation occurs when memory is divided into small, non-contiguous blocks, making it difficult to use the memory efficiently.
Internal Fragmentation​
Internal fragmentation happens when a process does not fully utilize its assigned partition. For instance, if a partition is 4 MB and a process only uses 3 MB, the remaining 1 MB is wasted because it cannot be used by another process.
Example: Process P1 (3 MB) is placed into a 4 MB partition, leaving 1 MB unused. This leftover space is internal fragmentation since it cannot be allocated to other processes.
External Fragmentation​
External fragmentation occurs when there is enough total free memory to satisfy a process's requirements, but the available memory is scattered in non-contiguous blocks.
Example: Suppose there are four partitions, each with 1 MB of free space, totaling 4 MB. If a process requires 4 MB of contiguous memory, it cannot be executed because the available memory is not contiguous, leading to external fragmentation.
Degree of Multiprogramming​
With fixed partitioning, the total number of processes in RAM equals the number of partitions. This limits the degree of multiprogramming (the number of concurrent processes in main memory) since only a limited number of partitions are available.
Limitation on Process Size​
Fixed partitioning restricts the size of processes. If all partitions are 4 MB, a process requiring 5 MB will not fit into any partition and cannot be executed.
Dynamic Partitioning​
Dynamic partitioning allows partitions to be created dynamically as processes enter memory. For instance, if a 10 MB process arrives, a 10 MB partition is created. This partition is destroyed when the process leaves memory. Dynamic partitioning offers several advantages over fixed partitioning:
-
No Internal Fragmentation: Since partitions are created to fit the process size, there is no leftover memory within a partition.
-
No Size Limit: There is no fixed size constraint, so processes of varying sizes can be accommodated.
-
Higher Degree of Multiprogramming: More processes can be accommodated since partitions are not predefined.
External Fragmentation in Dynamic Partitioning​
Despite its advantages, dynamic partitioning can still lead to external fragmentation. For example, if a 5 MB and a 3 MB process complete their work, they free up 8 MB of memory. However, if a new process requiring 8 MB arrives, it might not fit because the free memory is not contiguous.
Compaction​
To overcome external fragmentation, the operating system can perform compaction, which rearranges memory to combine free space into a single contiguous block.
-
Identify Free and Allocated Blocks: The OS scans memory to identify all free and allocated blocks.
-
Move Allocated Blocks: Allocated memory blocks are moved to one end of the memory space to make them contiguous.
-
Update References: References and pointers are updated to reflect the new memory locations.
-
Merge Free Blocks: All free memory is combined into a single large block.
While compaction helps solve external fragmentation, it has drawbacks:
-
Overhead: Moving memory blocks and updating references is time-consuming and resource-intensive.
-
Interruptions: Processes must be paused during compaction, causing temporary execution delays.
Allocation Methods​
First-Fit Allocation​
The first-fit strategy allocates the first available memory block that is large enough to meet the request.
Example:
-
Free list: [10 KB, 20 KB, 5 KB, 30 KB]
-
Request: 15 KB
-
Allocation: The 20 KB block is allocated, leaving 5 KB free.
Advantages:
Fast and simple to implement, as it allocates the first available space.
Disadvantages:
Can lead to fragmentation over time, as small gaps may be left, which cannot be used efficiently.
Best-Fit Allocation​
The best-fit strategy allocates the smallest block of memory that is large enough to satisfy the request, aiming to minimize wasted space.
Example:
-
Free list: [10 KB, 30 KB, 5 KB, 20 KB]
-
Request: 15 KB
-
Allocation: The 20 KB block is used, leaving 5 KB free.
Advantages:
Minimizes wasted space and can reduce fragmentation.
Disadvantages:
-
Slower than first-fit because it searches the entire free list.
-
Can lead to many small, unusable fragments.
Worst-Fit Allocation​
The worst-fit strategy allocates the largest available block of memory, leaving the largest possible leftover block.
Example:
-
Free list: [10 KB, 20 KB, 5 KB, 30 KB]
-
Request: 15 KB
-
Allocation: The 30 KB block is used, leaving 15 KB free.
Advantages:
Tends to avoid creating small fragments, which might be reused later.
Disadvantages:
Can result in inefficient memory use, with large gaps being left unused.
Next-Fit Allocation​
Similar to first-fit, but instead of always starting from the beginning of the free list, it starts from where the last allocation was made.
Example:
-
Free list: [10 KB, 20 KB, 5 KB, 30 KB]
-
Request: 15 KB
-
If the last allocation was at the 20 KB block, it allocates the 30 KB block, leaving 15 KB free.
Advantages:
Can be faster than first-fit in some scenarios, as it doesn't always start from the beginning.
Disadvantages:
Susceptible to fragmentation and might be less efficient if the free list isn't well managed.