Define Fragmentation, variable partitioning, Compaction in os

Define Fragmentation:

  • If a whole partition is currently not being used, then it is called an external fragmentation.

  • And if a partition is being used by a process requiring some memory smaller than the partition size, then it is called an internal fragmentation.

Variable Partitioning:


With fixed partitions we have to deal with the problem of determining the number and 

sizes of partitions to minimize internal and external fragmentation. If we use variable 

partitioning instead, then partition sizes may vary dynamically.
In the variable partitioning method, we keep a table (linked list) indicating used/free areas in memory. Initially, the whole memory is free and it is considered as one large block. When a new process arrives, the OS searches for a block of free memory large enough for that process. We keep the rest available (free) for the future processes. If a block becomes free, then the OS tries to merge it with its neighbors if they are also free.

Three algorithms for searching the list of free blocks for a specific amount of memory. DYNAMIC STORAGE ALLOCATION PROBLEM
a) First Fit : Allocate the first free block that is large enough for the new process. This is a fast algorithm.
b) Best Fit : Allocate the smallest block among those that are large enough for the new process. In this method, the OS has to search the entire list, or it can keep it sorted and stop when it hits an entry which has a size larger than the size of new process. This algorithm produces the smallest left over block. However, it requires more time for searching all the list or sorting it.
c) Worst Fit: Allocate the largest block among those that are large enough for the new process. Again a search of the entire list or sorting it is needed. This algorithm produces the largest over block.

Compaction: Compaction is a method to overcome the external fragmentation problem. All free blocks are brought together as one large block of free space. Compaction requires dynamic relocation. Certainly, compaction has a cost and selection of an optimal compaction strategy is difficult. One method for compaction is swapping out those processes that are to be moved within the memory, and swapping them into different memory locations.


Leave a Comment

error: Content is protected !!