Memory fragmentation is a crucial concept when it comes to efficient memory allocation. In this article, we will delve into the two types of fragmentation – external and internal – and explore their impact on data storage efficiency.
Table of Contents
What is External Fragmentation?
External fragmentation occurs when free space in memory is divided into noncontiguous chunks, making it challenging to allocate large amounts of contiguous memory even if the total free space is sufficient. This fragmentation can cause allocation failures and inefficient memory utilization.
To illustrate, let’s consider a scenario where a 32MB heap is divided into 32-byte chunks. To keep track of free chunks, a 1MB free bitmap is used. Each byte in the bitmap represents a chunk in the heap. If the byte is 1, the chunk is in use; if it’s 0, the chunk is free.
However, when the heap becomes fragmented, allocation failures can occur. For instance, if 22MB of free space is split into a 21MB chunk and a 1MB chunk, the allocation of a 22MB chunk would fail, even though sufficient free space exists. This fragmentation is known as external fragmentation.
What is Internal Fragmentation?
Internal fragmentation refers to the waste of memory within allocated chunks due to differences between requested and allocated sizes. For example, if a process requests a chunk of 3 bytes and is instead allocated an 8-byte chunk, 5 bytes are lost to internal fragmentation.
While external fragmentation affects the allocation of large chunks, internal fragmentation impacts the efficient utilization of memory within each allocated chunk.
Solving External Fragmentation
One potential solution to external fragmentation is compaction, where the free space is rearranged to form contiguous chunks. However, compaction is costly as it involves copying large amounts of data and updating pointer variables correctly. As a result, modern operating systems rarely use compaction.
Memory Allocation with Paging
To overcome the limitations of variable-sized allocation, memory allocation with paging is employed. This approach allows the operating system to use fixed-size allocation, benefiting from its efficiency, while still providing applications with variable-sized allocation.
In memory allocation with paging, contiguous virtual pages are separated from contiguity in the physical address space. This technique reduces external fragmentation and provides isolation between processes by allocating each process its own virtual address space.
Advantages of Memory Mapping
Memory mapping is a technique that can enhance file I/O performance. By marking a portion of a process’s memory as corresponding to a file, the process can read and write directly to memory instead of using system calls like open(), read(), and write(). This approach eliminates the need for copying data and facilitates file sharing between processes.
Hardware Support for Memory Management
Hardware manufacturers have also played a significant role in improving memory management. Hardware enhancements, such as the addition of an accessed bit and a dirty bit in the page table entry, aid in efficient writes and reduce disk traffic. The accessed bit tracks whether a portion of memory has been read or written, while the dirty bit indicates whether the portion of memory has been written to.
To address the issue of unwanted sharing between processes, a copy-on-write algorithm can be employed. This mechanism enables sharing of pages between processes until one process decides to write to a shared page. When a write occurs, the page is copied, allowing each process to have its own version of that page.
By employing copy-on-write, the operating system marks the pages as copy-on-write and sets the virtual address mapping to non-writable. When a process attempts to write to a page, a fault occurs. The operating system then copies the page, changes the virtual address mapping to the new copy, and sets it to writable.
This technique ensures that each process has its own copy of the page and can write to its copy independently, avoiding unwanted sharing.
Understanding memory fragmentation is essential for efficient memory allocation and utilization. External fragmentation can hinder the allocation of large contiguous chunks, while internal fragmentation leads to wasted memory within allocated chunks. Employing techniques like memory allocation with paging, memory mapping, hardware support, and copy-on-write can mitigate the impact of fragmentation, enhancing data storage efficiency.
To explore more topics related to memory management and other tech concepts, visit 5 WS.