Difference Between Internal and External Fragmentation

Internal Fragmentation and External Fragmentation are two important types of memory fragmentation in operating systems. Both represent situations where memory is not utilized as efficiently as it could be, but the way the unused memory occurs is different.

In simple terms, internal fragmentation occurs inside an allocated memory block, while external fragmentation occurs between allocated memory blocks.

Table of Contents

• What is Memory Fragmentation?
• What is Internal Fragmentation?
• Example of Internal Fragmentation
• What is External Fragmentation?
• Example of External Fragmentation
• Internal vs External Fragmentation
• Fragmentation and Memory Allocation
• Fragmentation in Paging
• Fragmentation in Segmentation
• How to Reduce Fragmentation
• Advantages and Disadvantages
• Exam Points
• Frequently Asked Questions
• Conclusion

First Fit, Best Fit and Worst Fit Memory Allocation

Best fit Allocation: It is the Contiguous allocation technique in which file is saved on the blocks whose size is same to file size or little more than file size. E.g. if we want to save a 200 Kb file and one block of 250KB is available then it will be saved to this available block.

The advantage of using this technique is best disk utilization but has the disadvantage that it is slow. Every time we want to save a file, we have to find a space whose size is either similar to file size or is slightly more.

Another Problem Associated with this technique is that if we want to extend the file contents than it can’t be implemented.

Contiguous Allocation

It is the Memory allocation technique in which contiguous blocks of this are used to save files. Whenever a file is created its size is calculated and based upon its size contiguous blocks are allocated to it for store. This allocation can be Best Fit, Worst Fit or First Fit.

The Main Advantage of using this technique is that it provides fast file access since whole file is allocated contagious blocks.

The Problem associated with this technique is that every time we have to calculate the file size and then to allocate the contagious

Linked Allocation

It is a disk allocation technique in which files are stored in a linked fashion and scattered way. Directory entry is used that contains pointer to first disk block of file and each block contains pointer to next block.

These Pointers are not made visible to users. Each block has 512 bytes in size out of which 4 bytes are used to store pointer and rest 508 bytes is used by the user.

This Technique has the advantage that there is no external fragmentation and files can be stored anywhere. Another advantage is that there is no need to define the size of file and it can grow as long as free blocks are available.
 

Problems Associated:
1) Files can be accessed in a serial fashion. E.g. to access n^th   block of disk we have to start from beginning until n^th block comes.

2) Another problem is that extra 4 bytes are consumed from each block for the storage of pointers. This problem is resolved by the use of clusters. Cluster is a combination of blocks into multiples. e.g. 5 blocks of disk can be used as single cluster and only one pointer will be required for 5 blocks.

Index Allocation

It is the Disk allocation technique in which each file has its own index block which is an array of disk block addresses. The n^th entry in the index block points to n^th block of file.

Whenever a file is created its index block is initialized, free block is taken from the disk and its entry is made into index table. whenever  file uses a new block its entry is made into index table. Index table consist of the addresses of all disk blocks on which a particular file is written.

The main advantage of using this technique is that it support direct file access. Another advantage is there is no external fragmentation. There is no need to re define the file size.

Problem associated with this technique is that what should be the size of index blocks? If we use one block for per file index and file is too large than it will not be possible to maintain index on single disk block. To overcome this problem linked index scheme is used where index block are linked together to form a large file index.