Fragmentation: Difference between revisions
pc>Yuron No edit summary |
 W81054ch [   PHRhYmxlIGNsYXNzPSJ0d3BvcHVwIj48dHI+PHRkIGNsYXNzPSJ0d3BvcHVwLWVudHJ5dGl0bGUiPkdyb3Vwczo8L3RkPjx0ZD51c2VyPGJyIC8+YnVyZWF1Y3JhdDxiciAvPmludGVyZmFjZS1hZG1pbjxiciAvPnN5c29wPGJyIC8+PC90ZD48L3RyPjwvdGFibGU+] (talk | contribs) m (1 revision imported) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 11: | Line 11: | ||
*(magnetic) disk filestore | *(magnetic) disk filestore | ||
In both these cases there is some concept of an ‘address | In both these cases there is some concept of an ‘address space’ (typically <em>bytes</em> in memory, <em>blocks</em> on disk) which is one dimensional. In both cases it is possible to imagine scenarios where some required <strong>amount</strong> of a resource is available, but there are already parts allocated which mean there is no single, available ‘hole’ which will accommodate a new request. | ||
space’ (typically <em>bytes</em> in memory, <em>blocks</em> on disk) which is | |||
one dimensional. In both cases it is possible to imagine scenarios | |||
where some required <strong>amount</strong> of a resource is available, but there | |||
are already parts allocated which mean there is no single, available | |||
‘hole’ which will accommodate a new request. | |||
[[Image:fragmentation.png|link=|alt=Fragmentation]] | [[Image:fragmentation.png|link=|alt=Fragmentation]] | ||
| Line 23: | Line 18: | ||
some of them later being removed. | some of them later being removed. | ||
Schemes exist in both these examples to overcome some of the resultant | Schemes exist in both these examples to overcome some of the resultant difficulties. In some cases these can result in <strong>fragmentation</strong>, where one big ‘thing’ is subdivided into more, smaller ‘things’. | ||
difficulties. In some cases these can result in <strong>fragmentation</strong>, | |||
where one big ‘thing’ is subdivided into more, smaller | |||
‘things’. | |||
==== Memory ==== | ==== Memory ==== | ||
In a [[Virtual_Memory|virtual memory]] system the <em>physical</em> RAM can be | In a [[Virtual_Memory|virtual memory]] system the <em>physical</em> RAM can be [[Memory Mapping|remapped]] arbitrarily at the page level. | ||
[[ | |||
However, within a process’ <em>virtual</em> space, [[Memory_Management|dynamic | However, within a process’ <em>virtual</em> space, [[Memory_Management|dynamic allocation]] and deallocation can fragment the | ||
allocation]] and deallocation can fragment the | |||
memory at an arbitrary scale. | memory at an arbitrary scale. | ||
Too much fragmentation can result in a failure to allocate some | Too much fragmentation can result in a failure to allocate some desired space, even if the space is, in principle, available because there is no <em>single</em> large-enough area. | ||
desired space, even if the space is, in principle, available because | |||
there is no <em>single</em> large-enough area. | |||
==== Filestore ==== | ==== Filestore ==== | ||
It is usual for a [[ | It is usual for a [[Filing System Implementation|filing system]] to allocate space on a block-by-block basis and these can be mapped arbitrarily. (An illustration can be seen in the [[FAT|FAT description]].) | ||
allocate space on a block-by-block basis and these can be mapped | |||
arbitrarily. (An illustration can be seen in the [[FAT|FAT description]].) | |||
All the disk blocks can be used, but if they become dispersed it can | All the disk blocks can be used, but if they become dispersed it can slow down access. This is because (unlike RAM) the disk is not truly ‘random access’ and will normally be formatted such that, having read block 1205 (say) the most accessible block will be 1206. | ||
slow down access. This is because (unlike RAM) the disk is not truly | |||
‘random access’ and will normally be formatted such that, | |||
having read block 1205 (say) the most accessible block will be 1206. | |||
== Defragmentation == | == Defragmentation == | ||
Because fragmentation causes inefficiency, at least, effort may be put | Because fragmentation causes inefficiency, at least, effort may be put into defragmentation. | ||
into defragmentation. | |||
==== Memory ==== | ==== Memory ==== | ||
When virtual memory is freed it can be worth the (extra) effort to try | When virtual memory is freed it can be worth the (extra) effort to try to amalgamate the free block(s) with the existing free space. This can be done as part of the <code>free()</code> process (at an immediate cost) or as a background task. Garbage collectors will probably do this, for example. | ||
to amalgamate the free block(s) with the existing free space. This | |||
can be done as part of the <code>free()</code> process (at an immediate cost) or | |||
as a background task. Garbage collectors will probably do this, for | |||
example. | |||
==== Filestore ==== | ==== Filestore ==== | ||
This can take significant effort. Periodic, offline defragmentation | This can take significant effort. Periodic, offline defragmentation may be done as trying to move file blocks whilst they may be in use can prove tricky. | ||
may be done as trying to move file blocks whilst they may be in use | |||
can prove tricky. | |||
<blockquote> | <blockquote> | ||
There’s a little [https://en.wikipedia.org/wiki/Defragmentation animated demonstration] on | There’s a little [https://en.wikipedia.org/wiki/Defragmentation animated demonstration] on Wikipedia. | ||
Wikipedia. | |||
</blockquote> | </blockquote> | ||
A common countermeasure is to [[Disk_Partition|<strong>partition</strong>]] the disk such that files such as system software – which tend to be read-only – are kept in an undisturbed (tidy?!) state whereas user files – which change a lot – are kept in a different area. The frequently used utilities will then load at peak speeds. | A common countermeasure is to [[Disk_Partition|<strong>partition</strong>]] the disk such that files such as system software – which tend to be read-only – are kept in an undisturbed (tidy?!) state whereas user files – which change a lot – are kept in a different area. The frequently used utilities will then load at peak speeds. | ||
| Line 73: | Line 48: | ||
=== Another example? === | === Another example? === | ||
Historically, memory [[Memory Segmentation|segments]] sometimes had to be | Historically, memory [[Memory Segmentation|segments]] sometimes had to be contiguous areas of physical (as well as virtual) address space. Segments are, of course, different sizes … just like files. | ||
contiguous areas of physical (as well as virtual) address space. | |||
Segments are, of course, different sizes … just like files. | |||
Most modern systems will support segmentation using | Most modern systems will support segmentation using [[Memory Pages|pages]] so they can divide a segment into scattered | ||
[[ | blocks. In this case, fragmentation is not a penalty because RAM access is more truly ‘random’; i.e. the performance is | ||
blocks. In this case, fragmentation is not a penalty because RAM | |||
access is more truly ‘random’; i.e. the performance is | |||
independent of the address. | independent of the address. | ||
---- | ---- | ||
{{BookChapter|9.2.3, 14.4.1|359-360, 570-573}} | |||
{{PageGraph}} | {{PageGraph}} | ||
{{Category|Concepts}} | {{Category|Concepts}} | ||
{{Category|Filing System}} | {{Category|Filing System}} | ||
Latest revision as of 10:03, 5 August 2019
| Depends on | Filing System Implementation |
|---|
Some computer resources are indivisible items (e.g. keyboard); some can be timeshared (e.g. processor); some can be ‘physically’ divided to satisfy different requirements at the same time.
(Okay – not literally “physically”…)
In this latter category, two important resources are:
- memory (i.e. RAM)
- (magnetic) disk filestore
In both these cases there is some concept of an ‘address space’ (typically bytes in memory, blocks on disk) which is one dimensional. In both cases it is possible to imagine scenarios where some required amount of a resource is available, but there are already parts allocated which mean there is no single, available ‘hole’ which will accommodate a new request.
This typically results from different sized items being allocated and some of them later being removed.
Schemes exist in both these examples to overcome some of the resultant difficulties. In some cases these can result in fragmentation, where one big ‘thing’ is subdivided into more, smaller ‘things’.
Memory
In a virtual memory system the physical RAM can be remapped arbitrarily at the page level.
However, within a process’ virtual space, dynamic allocation and deallocation can fragment the memory at an arbitrary scale.
Too much fragmentation can result in a failure to allocate some desired space, even if the space is, in principle, available because there is no single large-enough area.
Filestore
It is usual for a filing system to allocate space on a block-by-block basis and these can be mapped arbitrarily. (An illustration can be seen in the FAT description.)
All the disk blocks can be used, but if they become dispersed it can slow down access. This is because (unlike RAM) the disk is not truly ‘random access’ and will normally be formatted such that, having read block 1205 (say) the most accessible block will be 1206.
Defragmentation
Because fragmentation causes inefficiency, at least, effort may be put into defragmentation.
Memory
When virtual memory is freed it can be worth the (extra) effort to try to amalgamate the free block(s) with the existing free space. This can be done as part of the free() process (at an immediate cost) or as a background task. Garbage collectors will probably do this, for example.
Filestore
This can take significant effort. Periodic, offline defragmentation may be done as trying to move file blocks whilst they may be in use can prove tricky.
There’s a little animated demonstration on Wikipedia.
A common countermeasure is to partition the disk such that files such as system software – which tend to be read-only – are kept in an undisturbed (tidy?!) state whereas user files – which change a lot – are kept in a different area. The frequently used utilities will then load at peak speeds.
Another example?
Historically, memory segments sometimes had to be contiguous areas of physical (as well as virtual) address space. Segments are, of course, different sizes … just like files.
Most modern systems will support segmentation using pages so they can divide a segment into scattered blocks. In this case, fragmentation is not a penalty because RAM access is more truly ‘random’; i.e. the performance is independent of the address.
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 9.2.3, 14.4.1, pages 359-360, 570-573 |
|---|
