Hardware Reference
In-Depth Information
Fig. 6-10(d). After the system has been running for a while, memory will be divid-
ed up into a number of chunks, some containing segments and some containing
holes. This phenomenon is called external fragmentation (because space is
wasted external to the segments, in the holes between them). Sometimes external
fragmentation is called checkerboarding .
(3K)
(3K)
Segment 4
(7K)
Segment 4
(7K)
Segment 5
(4K)
Segment 5
(4K)
10K
(4K)
Segment 3
(8K)
Segment 3
(8K)
Segment 3
(8K)
Segment 5
(4K)
Segment 6
(4K)
Segment 6
(4K)
Segment 2
(5K)
Segment 2
(5K)
Segment 2
(5K)
Segment 2
(5K)
Segment 2
(5K)
(3K)
(3K)
(3K)
Segment 1
(8K)
Segment 7
(5K)
Segment 7
(5K)
Segment 7
(5K)
Segment 7
(5K)
Segment 0
(4K)
Segment 0
(4K)
Segment 0
(4K)
Segment 0
(4K)
Segment 0
(4K)
(a)
(b)
(c)
(d)
(e)
Figure 6-10. (a)-(d) Development of external fragmentation. (e) Removal of the
external fragmentation by compaction.
Consider what would happen if the program referenced segment 3 at the time
memory was suffering from external fragmentation, as in Fig. 6-10(d). The total
space in the holes is 10K, more than enough for segment 3, but because the space
is distributed in small, useless pieces, segment 3 cannot simply be loaded. Instead,
another segment must be removed first.
One way to avoid external fragmentation is as follows: every time a hole ap-
pears, move the segments following the hole closer to memory location 0, thereby
eliminating that hole but leaving a big hole at the end. Alternatively, one could
wait until the external fragmentation became quite serious (e.g., more than a cer-
tain percentage of the total memory wasted in holes) before performing the
compaction (squeezing out the holes). Figure 6-10(e) shows how the memory of
Fig. 6-10(d) would look after compaction. The intention of compacting memory is
to collect all the small useless holes into one big hole, into which one or more seg-
ments can be placed. Compacting has the obvious drawback that some time is
wasted doing the compacting. Compacting after every hole is created is usually
too time consuming.
 
Search WWH ::




Custom Search