Memory Fragmentation
This section deals with memory fragmentation. When free memory for use by programs becomes fragmented, programs will experience slowdown and might even stop working altogether. This is obviously a serious problem, especially where programs are concerned which should run for longer periods of time.
What Exactly Is Memory Fragmentation?
Memory is said to be fragmented when the blocks of memory that are not in use—free memory—are interspersed with blocks of memory that are in use—used memory. Strictly speaking, memory is almost always fragmented; however, fragmentation becomes a problem only when the levels of fragmentation are high. This is the case when the average size of the blocks of free memory becomes increasingly small. For instance, a system might have over 5MB of free memory for programs to use during runtime, but still be unable to allocate a continuous block of 1MB. This could happen when memory is so badly fragmented that there are hundreds of small blocks of free memory every one of which is no larger than 500KB.
When Is Memory Fragmentation Likely to Occur?
Memory fragmentation occurs when programs use memory dynamically. When blocks of memory are allocated and released during runtime, it is unlikely that this will be done in such a manner that released blocks of memory will again form continuous, larger, memory blocks. This is true not only because of the way memory is used within a single program, but also because of the way that different programs use the same memory resources simultaneously, as shown in Figures 9.1 and 9.2.
Let's say we have an application that allocates three blocks of memory (blocks A, B, and C) in close succession. After these allocations, memory usage could appear as shown in Figure 9.1.
At some point, block B is no longer needed and is released while blocks A and C are still in use. When new memory is requested, block B can be used only to satisfy claims for memory with a size equal to, or smaller than, the size of block B. The situation described here can occur recursively, creating continuously smaller blocks of memory. Figure 9.2 shows what memory usage could look like after a new block of memory is allocated (block D), which is smaller than block B.
Figure 9.1. Memory before fragmentation.
Figure 9.2. Memory after fragmentation.
Released blocks of memory can become increasingly small in this manner, making them less and less useful in the process.
Memory fragmentation is sped up when programs allocate and release memory at a high rate, especially when different block sizes are used. The chances of a released block being used up completely for a new memory claim is smaller when blocks of varying sizes are being used. Think of linked lists and trees used for storing data; most of the time, a large number of small objects is used for containing links and temporary information.
Characteristics of Memory Fragmentation
With what has been discussed about memory fragmentation so far, the following list of characteristics can be compiled:
Memory fragmentation is often hidden; although the total amount of free memory might be sufficiently large to accommodate a certain program, fragmentation can cause the blocks that the free memory consists of to be too small to be usable.
Memory fragmentation gets worse over time; as released blocks are often split into smaller pieces to satisfy further memory requests, fragmentation can easily become problematic.
Memory fragmentation can slow down or even halt programs; depending on the OS used, different scenarios are executed when the OS is unable to allocate blocks of memory of sufficient size. OS responses can range from invoking some kind of garbage collecting, to swapping memory to and from the hard drive, to simply placing programs into holding patterns until memory becomes available.
Memory fragmentation can happen when you least expect it; when using memory blocks that are as small as possible and releasing these blocks as soon as they are no longer needed, memory fragmentation can still occur. This is simply because not only is the total amount of memory used important, but also the dynamic behavior of the programs using it.
To guarantee a certain typical performance, it is important to consider memory fragmentation issues during the different phases of software engineering (requirements, design, and implementation), especially when a program will use relatively large parts of the memory resources available, or when a program is meant to run over extended periods of time. Early in development, it should therefore become clear whether special efforts will be needed to combat fragmentation. When fragmentation forms an immediate danger and the target OS does not implement a memory management scheme that suits the program or system requirements, it is likely that a dedicated memory manager needs to be incorporated into the software. The following section discusses theories and techniques that can be used by memory management software.