Fragmentation
|
|
Fragmentation is a term that occurs in several fields and describes a process of something breaking or being divided into pieces (fragments).
| Contents |
Fragmentation in computer storage
In computer storage, there are three related uses of the term fragmentation, external fragmentation, internal fragmentation, and data fragmentation, all related to storage.
External fragmentation
External fragmentation is the phenomenon where the free space, the space still available for use, in a piece of storage becomes divided into many small pieces. It is caused over time by allocating and freeing pieces of the storage space of many different sizes. The result is that, although we may have plenty of free space, we may not be able to use it at all, or at least to use it as efficiently as we would like to.
For example, in dynamic memory allocation, we might request a block of a 1000 bytes, but the largest contiguous block of free space has only 300. Even if there are ten blocks of 300 bytes of free space, separated by allocated regions, we still can't allocate our block of 1000 bytes.
External fragmentation also occurs in file systems as many files of different sizes are created, change size, and are deleted. The effect is even worse if a file which is divided into many small pieces is deleted, because this leaves similarly small regions of free space.
External fragmentation can be eliminated through a process called compaction, where existing objects are all moved into one large adjacent block, leaving all the remaining free space in one large block. Moving garbage collectors use compaction to improve dynamic memory allocation performance, and tools which defragment disk drives also perform a compaction step.
Data fragmentation
Data fragmentation occurs when a piece of data in memory is broken up into many pieces which are not close together. It is typically the result of attempting to insert a large object into storage which has already suffered external fragmentation.
For example, files in a file system are often broken up into pieces called blocks. When a disk is new, there is space to store the blocks of a file all together in one place. This allows for rapid sequential file reads and writes. However, as files are added, removed, and changed in size, the disk becomes externally fragmented, leaving only small holes to place new data in. When a new file is written, its data blocks must be scattered out across the disk, slowing access due to seek time and rotational delay of the read/write head.
As another example, if the nodes of a linked list are allocated consecutively in memory, this improves locality of reference and enhances data cache performance during traversal of the list. If the memory pool's free space has become fragmented, however, the linked list nodes will be spread throughout memory, increasing the number of cache misses. One goal of intelligent garbage collectors is to keep related pieces of data together, but this can't be done if it can't find large enough regions of free space.
Just as compaction can eliminate external fragmentation, data fragmentation can be eliminated by rearranging pieces of data so that related pieces are close together. For example, the primary job of a defragmentation tool is to rearrange blocks on disk so that the blocks of each file are contiguous and in order. Some moving garbage collectors will also move related objects close together to improve cache performance.
Internal fragmentation
Internal fragmentation refers to the result of reserving a piece of space without ever intending to use it. This space is wasted. While this seems foolish, it is often accepted in return for increased efficiency or simplicity.
For example, in many file systems, files always start at the beginning of a sector, because this simplifies organization and makes it easier to grow files. Any space left over between the last byte of the file and the first byte of the next sector is internal fragmentation. Similarly, a program which allocates a single byte of data is often allocated many additional bytes for metadata and alignment. This extra space is also internal fragmentation.
Another common example: Letters are often stored in 8-bit bytes even though in standard ASCII strings the 8th bit of each byte is always zero. The "wasted" bits are internal fragmentation.
Similar problems with leaving reserved resources unused appear in many other areas. For example, IP addresses can only be reserved in blocks of certain sizes, resulting in many IPs that are reserved but not actively used. This is contributing to the IPv4 address shortage.
Unlike other types of fragmentation, internal fragmentation is difficult to reclaim; usually the best way to remove it is with a design change. For example, in dynamic memory allocation, memory pools drastically cut internal fragmentation by spreading the space overhead over a larger number of objects.
Mass Communications
In a mass communication, fragmentation is how audiences and the content of media are divided up into pieces, according to the interests of media (as business) and audiences.
Music
In music fragmentation is the use of fragments or the "division of a musical idea (gesture, motive, theme, etc.) into segments." It is used in tonal and atonal music and is used in musical development and closure. Called liquidation by Arnold Schoenberg, it is a common musical technique used by composers including Bela Bartok.
Sources
- Caplin, William. Classical Form: A Theory of Formal Functions, p. 10-11. Further reading
- Stein, Deborah (2005). Engaging Music: Essays in Music Analysis, "Introduction to Musical Ambiguity", p.87. New York: Oxford University Press. ISBN 0195170105.
Weaponry
A fragmentation weapon is a high explosive designed to produce shrapnel, such as a hand grenade.
Urban sociology
The absence or the underdevelopment of connections between the society and the groupings of some members of that society on the lines of a common culture, nationality, race, language, occupation, religion, income level, or other common interests. This gap between the concerned group and the rest might be social, indicating poor interrelationships among each other; economical based on structural inequalities; institutional in terms of formal and specific political, occupational, educative or associative organisations and/or geographic implying regional or residential concentration.ja:フラグメンテーション