INTERNAL FRAGMENTATION (Fixed Size Blocks)
O.S O.S
8MB 8MB
4MB
8MB
6MB
8MB 8MB
8MB
16MB
8MB
8MB 8MB
8MB 14MB
(a) Equal size Partition (b) Unequal size Partition
Effect of Internal Fragmentation
• Inefficient Memory Utilization
• Performance lag
• I/O operations increase in number.
• results in an increase in data access times and increased lagging in performance.
• Disintegration of Memory
• When the two types of fragmentations internal and external mix up it leads to
memory scattering.
• makes it fairly tough for the system to allocate contiguously.
• Trouble in Virtual Memory Management
• Memory paging and memory swapping is the most important operation that helps
to operate and manage virtual memory.
• Partially filled pages lead to page faults during the memory paging which
ultimately affects the operations with the virtual memory.
Why Internal Fragmentation is Allowed?
• allocation always occurs in a fixed size only, so the allocation becomes fast and simple.
• overhead calculation is accurate because the overhead caused by the internal
fragmentation is already well known.
Ways to Avoid Internal Fragmentation
• Variable-Sized Allocation Blocks
• Dynamic Memory Allocation
Dynamic Allocation: an example
▪ A hole of 64K is left after loading 3 processes: not enough room
for another process
▪ Eventually each process is blocked. The OS swaps out process 2
to bring in process 4
6
Dynamic Allocation: an example
▪ another hole of 96K is created
▪ Eventually each process is blocked. The OS swaps out process
1 to bring in again process 2 and another hole of 96K is
created...
7
FRAGMENTATION USING ALLOCATION ALGORITHMS
FIRST – FIT
This algorithm begins to scan memory from the beginning and choose the first
available block that is large enough to fit in a process or program.
BEST – FIT
This algorithm scans through the memory from the beginning to the end and
choose the block that is closest in size to the request.
Worst Fit
It allocates the process to the partition, which is the largest sufficient freely
available partition in the main memory.
NEXT FIT
This algorithm begins to scan the memory from the location of last placement
and choose the next available block that is large enough.
Similar to the First Fit
Searches for the first sufficient partition from the last allocation point
In satisfying a 16MB allocation request in the following figure
First – fit scans the memory and fit in a 22MB space leaving a 6MB hole.
Best – fit results in a 2MB fragment or hole in main memory.
Next – fit result in a 20MB fragment in main memory.
8MB 8MB
12MB 12MB
First - fit
22MB
6MB
Best - fit
18MB
2MB
Allocated Block
16MB Block
Possible New Allocation
8MB Free Block 8MB
6MB 6MB
14MB 14MB
Next - fit (b) After a number of
36MB
placement and
(a) After a number of placement 20MB swapping out.
and swapping out.
EXTERNAL FRAGMENTATION
▪ happens when there’s a sufficient
quantity of area within the memory to
satisfy the memory request of a
method.
• there is enough space (55 KB)
to run a process-07 (required
50 KB) but the memory
(fragment) is not contiguous.
• Here, we use compaction,
paging, or segmentation to use
the free space to run a
process.
Advantages of Compaction
• Reduces external fragmentation.
• Make memory usage efficient.
• Memory becomes contiguous.
• Since memory becomes contiguous more processes can be loaded to memory,
thereby increasing scalability of OS.
• Fragmentation of file system can be temporarily removed by compaction.
• Improves memory utilization as their is less gap between memory blocks.
Disadvantages of Compaction
• System efficiency reduces and latency is increased.
• A huge amount of time is wasted in performing compaction.
• CPU sits idle for a long time.
• Not always easy to perform compaction.
• It may cause deadlocks since it disturbs the memory allocation process.
