Memory fragmentation
In computer storage, memory fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and consequently reducing the performance. The term generally denotes the wastage in space (memory). There are two different forms of fragmentation: internal fragmentation and external fragmentation. Various memory allocator schemes exhibit both these weaknesses.
Basic Principle
"Fragmented memory" denotes all of the system's unusable free memory. Memory fragmentation usually occurs when memory is allocated dynamically (using calls like malloc).Generally, memory allocation performed during runtime is not in the form of stacks. The memory allocator wastes memory in the following ways: 1.Overhead 2.Internal Fragmentation 3.External Fragmentation. When blocks of memory are alloted during runtime, it is highly unlikely that these released blocks of memory will again form continuos large memory blocks. Hence, the free memory gets interspersed with the blocks of memory in use. The average size of blocks of memory consequently becomes quite small. This problem coupled with incomplete usage of the allocated memory results in memory fragmentation.
For example, consider a system having 5MB total memory. Let the total free memory be 2MB which the programs could use at runtime. However, due to intersperced free and used memory blocks the user is not able to allocate even 1MB of free space for a new program as all the free memory blocks are not larger than 500KB. Also, if in the 3MB allocated memory only 2MB is used then the remaining 1MB memory goes unused. This wastage of space is the major problem of internal and external memory fragmentation.
Types Of Memory Fragmentation
Overhead
The memory allocator needs to store all the information related to all memory allocations. This information includes the location, size and ownership of any free blocks, as well as other internal status details. Overhead comprises of all the additional system resources that the programming algorithm requires. A dynamic memory allocator typically stores this overhead information in the memory it manages. This leads to wastage of memory. Hence, it is considered as a part of memory fragmentation.
Internal Fragmentation
When the memory allocated is larger than required, the rest is wasted. The term "internal" points to the fact that the memory which remained unused was declared at the time of allocation. It can have certain reasons -1. Allocator policy - involves architectural constraints, 2. Client asking for excess memory than what is required.
1.There are some basic memory allocation rules involved. All memory allocators must adhere to it. According to the "segregated free list" allocator policy , all memory allocations must start at an address divisible by 4, 8, or 16. The memory allocator may assign blocks of only certain predefined sizes to clients. It depends upon the processor architecture. Also , extra bytes are assigned to a program for alignment and metadata.
For example, when a client requests a block of 23 bytes, it may well get 24, 28 or even more bytes.
Another example would be, when a client initially asks for 8 bytes, memory is allocated in 8 byte blocks but the program only needs 6 bytes then the remaining 2 bytes remain unused.The wastage of extra space that results from improper memory allocation is called internal fragmentation.
External Fragmentation
External fragmentation is the inability to use free memory as the free memory is divided into small blocks of memory and these blocks are interspersed with the allocated memory.
For example, consider a situation wherein a program allocates 3 continuous blocks of memory and then frees the middle block. The memory allocator can use this free block of memory for future allocations. However it cannot use this block if memory to be allocated is larger in size than this free block.
As compared to external fragmentation , overhead and internal fragmentation account for little loss in terms of wastage of memory and reduced performance. External fragmentation does the most damage to the system. It is defined as:
External fragmentation is the factor between 0 to 1. A 100% fragmentation (factor = 1) suggest that the system is completely out of usable free memory. While a 0 factor (0% fragmentation) denotes that all the free memory is in a single large block.
For example, fragmentation is 90% when 100 MB free memory is present but largest free block of memory for allocation is just 10 MB.
Performance Degradation Due To Memory Fragmentation
Memory Fragmentation is one of the most severe problem faced by the System Manager. After a considerable amount of time , it leads to degradation of System performance. The System becomes very slow. Eventually, constant memory fragmentation , even in small proportion , leads to complete loss of free memory.
Memory fragmentation is a kernel programming level problem. It becomes a critical issue when it reaches alarming levels. A real life example is of 99% fragmentation which frequently occurs during Real-time computing of applications. This fragmentation occurs just seconds before the System crashes. It is difficult to avert this System crash as it is impossible to anticipate the critical rise in levels of memory fragmentation.
According to a research conducted by International Data Corporation, the performance degradation is largely due to external fragmentation . The life-time of server is shortened by 33% by external fragmentation alone . This leads to a direct increase of 33% in the yearly budget for hardware upgrades. Thus it can be concluded that memory fragmentation has an undesirable effect not only on memory usage and processing speed of the System but also on hardware components and cost of project.
See Also
References
- http://www.edn.com/article/478952-Handling_memory_fragmentation.php
- http://www.sqlservercentral.com/articles/performance+tuning/performancemonitoringbyinternalfragmentationmeasur/2014/
- C++ Footprint and Performance Optimization, R. Alexander; G. Bensley, Sams Publisher, First edition, Page no:128, ISBN no:9780672319044
- Ibid, Page no:129