FACTOID # 20: Statistically, Delaware bears more cost of the US Military than any other state.
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 


FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:



(* = Graphable)



Encyclopedia > Fragmentation (computer)

In computer storage, there are three related uses of the term fragmentation: external fragmentation, internal fragmentation, and data fragmentation, all related to storage. To meet Wikipedias quality standards, this article or section may require cleanup. ...


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 deallocating ("freeing") pieces of the storage space of many different sizes. The result is that, although one may have plenty of free space, one may not be able to use it all, or at least use it as efficiently as one would like to.

For example, in dynamic memory allocation, a block of 1000 bytes might be requested, but the largest contiguous block of free space, or memory hole, has only 300. Even if there are ten blocks of 300 bytes of free space, separated by allocated regions, one still cannot allocate the requested block of 1000 bytes. To meet Wikipedias quality standards, this article or section may require cleanup. ... In computer science, memory hole refers to a block of contiguous available memory. ...

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.

Data fragmentation

Data fragmentation occurs when a piece of data in memory is broken up into many pieces that are not close together. It is typically the result of attempting to insert a large object into storage that 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 in which to place new data. When a new file is written, or when an existing file is extended, the new data blocks will be scattered out across the disk, slowing access due to seek time and rotational delay of the read/write head. In computing, a file system is a method for storing and organizing computer files and the data they contain to make it easy to find and access them. ... Seek time is one of the several delays associated with reading or writing data on a computers disk drive. ... Rotational delay is a term from computing applicable to rotating storage devices (such as a typical hard disk or floppy disk drive but also the older drum memory systems). ...

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. In computer science, a linked list is one of the fundamental data structures used in computer programming. ... In computer science, locality of reference, sometimes also called the principle of locality, is a concept which deals with the process of accessing a single resource multiple times. ... Diagram of a CPU memory cache A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. ... This article is about the computer term. ...

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. In the context of administering computer systems, defragmentation (or defragging) is a process that eliminates fragmentation in file systems. ...

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. For other uses, see ASCII (disambiguation). ...

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. In computer networking, an IP address (internet protocol address) is a unique number that devices use in order to identify and communicate with each other on a network utilizing the Internet Protocol standard. ... As the number of Internet-connected devices increases, the address space of the current IPv4 version of the TCP/IP protocol suite is rapidly being consumed by allocations for new devices. ...

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. Memory pools allow dynamic memory allocation comparable to malloc or the Operator new in C++. As those implementations suffer from fragmentation because of variable block sizes, it can be impossible to use them in a real time system due to performance. ...

See also



Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m