In simple terms, internal fragmentation occurs inside an allocated memory block, while external fragmentation occurs between allocated memory blocks.
- 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
What is Memory Fragmentation?
Memory fragmentation is a condition in which available memory becomes divided into portions that are not utilized efficiently.
Fragmentation commonly occurs as processes are loaded into memory, removed from memory, and allocated different amounts of space during program execution.
Memory fragmentation is generally discussed in two major forms:
- Internal Fragmentation
- External Fragmentation
- Internal = unused space inside an allocated block
- External = unused space between allocated blocks
What is Internal Fragmentation?
Internal fragmentation occurs when a process is allocated a memory block that is larger than the memory it actually requires. The unused portion remains inside the allocated block and cannot normally be assigned separately to another process.
In other words, the memory has been allocated to a process, but some space within that allocation is unused.
Internal fragmentation is commonly associated with fixed-size memory allocation, including fixed-size partitions and paging.
How Internal Fragmentation Occurs
- A memory-management system divides memory into blocks of a particular size.
- A process requests a certain amount of memory.
- The system allocates a block large enough for the request.
- If the block is slightly larger than the requested amount, the remaining space is unused.
- This unused space inside the allocated block is internal fragmentation.
Suppose a system allocates memory in blocks of 10 KB.
A process requires only 7 KB.
The system allocates one 10 KB block.
Required memory = 7 KB
Unused space = 10 KB - 7 KB = 3 KB
The unused 3 KB inside the allocated block represents internal fragmentation.
Characteristics of Internal Fragmentation
- Unused memory exists inside an allocated block.
- It is commonly associated with fixed-size allocation.
- Paging can produce internal fragmentation, especially in the final page of a process.
- The unused portion generally cannot be allocated independently to another process.
- The amount depends on the allocation-unit size and requested memory sizes.
What is External Fragmentation?
External fragmentation occurs when free memory is available, but it is divided into multiple separated blocks rather than being available as one sufficiently large contiguous region.
The total amount of free memory may be enough for a new process, but the free memory is scattered between allocated regions.
External fragmentation is commonly associated with variable-size contiguous memory allocation.
How External Fragmentation Occurs
- Processes are allocated different-sized regions of memory.
- Some processes finish and release their memory.
- The released areas become free holes.
- New allocations may occupy other areas.
- Over time, free memory can become separated into multiple small regions.
Suppose memory contains the following arrangement:
Total free memory is:
Now suppose a process requires 8 KB of contiguous memory.
Although the total free memory is 12 KB, there is no single contiguous free block of 8 KB.
This is an example of external fragmentation.
Characteristics of External Fragmentation
- Free memory exists outside allocated blocks.
- The free memory is divided into separate holes.
- It is particularly associated with variable-size contiguous allocation.
- The total free memory can be sufficient but unusable for a particular contiguous request.
- Compaction can sometimes reduce external fragmentation when the memory-management system supports moving allocations.
Difference Between Internal and External Fragmentation
The fundamental difference is the location of unused memory. Internal fragmentation occurs within an allocated memory block, whereas external fragmentation occurs among separately allocated blocks.
| Parameter | Internal Fragmentation | External Fragmentation |
|---|---|---|
| Basic meaning | Unused memory exists inside an allocated block. | Free memory exists outside allocated blocks but is divided into separate regions. |
| Location of unused space | Inside an allocated memory block. | Between allocated memory blocks. |
| Type of waste | Unused space within allocated capacity. | Free space that may be unusable for a large contiguous allocation. |
| Typical cause | Allocation of fixed-size blocks larger than the requested memory. | Repeated allocation and deallocation of variable-sized memory regions. |
| Common allocation model | Fixed-size allocation. | Variable-size contiguous allocation. |
| Paging | Can occur, especially in the final page of a process. | Traditional paging does not suffer from external fragmentation in the same way contiguous allocation does. |
| Segmentation | Not the primary fragmentation problem. | Can suffer from external fragmentation because segments have variable sizes. |
| Fixed partitions | Commonly occurs. | Not the characteristic problem of fixed partitions. |
| Variable partitions | Can occur depending on allocation details. | Common problem. |
| Free memory | The unused space is already part of an allocated block. | The memory is free but separated into multiple holes. |
| Contiguous allocation requirement | Not the defining issue. | Usually important because a contiguous request may not fit into scattered holes. |
| Can total free space be enough? | Not the main issue. | Yes. Total free space can be sufficient while no individual hole is large enough. |
| Typical solution | Use an appropriate allocation-unit size or allocation strategy. | Compaction, better allocation strategies, or non-contiguous allocation methods can help. |
| Compaction | Does not normally solve internal fragmentation. | Can reduce external fragmentation when allocations can be moved. |
| Main disadvantage | Wastes part of allocated memory. | Makes available free memory difficult to use for large contiguous requests. |
| Simple example | 10 KB block allocated for a 7 KB request; 3 KB remains unused inside. | Several small free holes exist, but none is large enough for the requested allocation. |
| Easy identification | Look for unused space inside an allocated block. | Look for scattered free spaces between allocated blocks. |
Fragmentation and Memory Allocation
Memory allocation techniques determine how processes receive memory and therefore influence the type and amount of fragmentation that can occur.
Fixed-Size Allocation
In fixed-size allocation, memory is divided into blocks or partitions of predetermined sizes. If a process does not completely use its assigned block, the remaining portion can contribute to internal fragmentation.
Process requirement = 11 KB
Unused portion = 5 KB
The 5 KB is inside the allocated partition, so it represents internal fragmentation.
Variable-Size Allocation
Variable-size allocation attempts to give a process a region closer to its requested size. However, when processes are allocated and released at different times, free regions can become scattered.
This can lead to external fragmentation.
First Fit, Best Fit and Worst Fit
Allocation strategies such as First Fit, Best Fit and Worst Fit are used with variable-size memory allocation.
- First Fit: Allocates the first suitable free block found.
- Best Fit: Attempts to use the smallest suitable free block.
- Worst Fit: Allocates from the largest suitable free block.
These strategies can affect how free holes are distributed and therefore influence fragmentation. Their effectiveness depends on the workload and implementation; no single strategy eliminates fragmentation in every situation.
Fragmentation in Paging
Paging divides a process's logical memory into fixed-size pages and physical memory into frames of the same size.
Because pages can be placed in different physical frames, paging avoids the requirement that an entire process occupy one contiguous physical region.
Does Paging Have Internal Fragmentation?
Yes. Paging can have internal fragmentation.
Consider a page size of 4 KB and a process that needs 10 KB.
Page size = 4 KB
Pages required = 3
Allocated capacity = 3 × 4 KB = 12 KB
Potential unused space = 12 KB - 10 KB = 2 KB
The final page may not be completely filled. The unused portion is internal fragmentation.
Fragmentation in Segmentation
Segmentation divides a program's logical address space into variable-sized segments, such as code, data, stack, or other logically defined regions.
Because segments have different sizes, placing and removing them from memory can create separated free holes.
Therefore, segmentation can experience external fragmentation.
Total free memory is 11 MB, but a request for a contiguous 8 MB segment cannot be satisfied if no single free region is at least 8 MB.
This demonstrates external fragmentation.
Internal Fragmentation vs External Fragmentation in Paging and Segmentation
| Memory Management Technique | Typical Fragmentation Concern | Reason |
|---|---|---|
| Fixed Partitioning | Internal Fragmentation | A process may not completely use its assigned fixed-size partition. |
| Variable Partitioning | External Fragmentation | Free regions can become scattered between allocated regions. |
| Paging | Internal Fragmentation | The final page may only be partially occupied. |
| Segmentation | External Fragmentation | Segments have variable sizes and can create separated free holes. |
Internal Fragmentation Example vs External Fragmentation Example
| Situation | What Happens? | Fragmentation Type |
|---|---|---|
| 16 KB block allocated for an 11 KB process | 5 KB remains unused inside the allocated block. | Internal |
| 4 KB + 3 KB + 5 KB free holes | 12 KB is free, but an 8 KB contiguous request cannot fit. | External |
| 4 KB page size and 10 KB process | Three pages provide 12 KB capacity, leaving up to 2 KB unused in the final page. | Internal |
| Variable-size segments released at different times | Free holes become separated between allocated segments. | External |
How to Reduce Fragmentation
Reducing Internal Fragmentation
- Choose an appropriate allocation-unit size.
- Avoid unnecessarily large fixed-size blocks where practical.
- Use allocation techniques that better match requested sizes when appropriate.
- In paging systems, page-size selection involves trade-offs between page-table overhead, memory-management efficiency and potential internal fragmentation.
Reducing External Fragmentation
- Compaction: Move allocated blocks together to create a larger contiguous free region, when the system supports safe relocation.
- Better allocation strategies: Allocation policies can influence the distribution of free holes.
- Non-contiguous allocation: Techniques such as paging allow different parts of a process to occupy different physical frames.
- Memory management improvements: Modern systems use sophisticated allocation mechanisms to manage free memory efficiently.
What is Compaction?
Compaction is a memory-management technique in which allocated blocks are moved closer together so that separated free holes are combined into a larger contiguous free region.
Total free memory = 9 MB, but it is divided into three holes.
After compaction:
The separate holes have been combined into one larger contiguous region.
Advantages and Disadvantages
Internal Fragmentation
| Advantages / Characteristics | Disadvantages |
|---|---|
| Fixed-size allocation can simplify memory management. | Some allocated memory can remain unused. |
| Paging makes physical memory allocation flexible because pages can use different frames. | Fixed-size pages can leave unused space, particularly in the last page. |
| Allocation can be predictable with fixed-size units. | Larger allocation units can increase potential wasted space. |
External Fragmentation
| Advantages / Characteristics | Disadvantages |
|---|---|
| Variable-size allocation can allocate memory closer to the requested size. | Free memory can become scattered. |
| Free holes can sometimes be reused for later allocations. | A large contiguous request may fail even when total free memory is sufficient. |
| Allocation strategies can help manage free regions. | Compaction may require moving allocated data and can introduce overhead. |
Internal and External Fragmentation in Operating Systems
Fragmentation is an important concept in operating system memory management. The operating system must decide how physical and virtual memory is allocated to processes while balancing memory utilization, allocation overhead and performance.
Modern operating systems commonly use paging-based virtual memory. This reduces the need for large contiguous physical-memory allocations, while fixed-size pages can still produce some internal fragmentation.
Different memory allocators and subsystems can have their own allocation units and fragmentation characteristics, so the exact behavior depends on the implementation.
Internal vs External Fragmentation: Simple Difference
| Internal Fragmentation | External Fragmentation |
|---|---|
| Unused space is inside an allocated block. | Free space is outside allocated blocks. |
| Usually associated with fixed-size allocation. | Usually associated with variable-size contiguous allocation. |
| Paging can cause it. | Segmentation can cause it. |
| Compaction is not the normal solution. | Compaction can reduce it when relocation is possible. |
| Think: inside the block. | Think: between the blocks. |
Important Exam Points
- Internal fragmentation is unused memory within an allocated block.
- External fragmentation is free memory scattered among allocated blocks.
- Fixed-size allocation commonly causes internal fragmentation.
- Variable-size contiguous allocation commonly causes external fragmentation.
- Paging can produce internal fragmentation.
- Segmentation can produce external fragmentation.
- Compaction is primarily used to reduce external fragmentation.
- Paging avoids the need for a process's physical pages to occupy one contiguous region.
- External fragmentation can occur even when total free memory is greater than the requested amount.
- The easiest way to remember the difference is: internal = inside, external = outside.
Frequently Asked Questions
1. What is internal fragmentation?
Internal fragmentation is the unused portion of an allocated memory block. It occurs when the allocated block is larger than the memory actually required by the process.
2. What is external fragmentation?
External fragmentation occurs when free memory is divided into separate regions between allocated blocks, making it difficult to satisfy a large contiguous memory request.
3. What is the main difference between internal and external fragmentation?
Internal fragmentation is unused space inside an allocated block, while external fragmentation is free space between allocated blocks.
4. Does paging cause internal fragmentation?
Yes. Since paging uses fixed-size pages, the final page of a process may not be completely filled, resulting in internal fragmentation.
5. Does paging cause external fragmentation?
Traditional paging does not suffer from external fragmentation in the same way variable-size contiguous allocation does because pages can be placed in different physical frames.
6. Does segmentation cause external fragmentation?
Yes. Segments are variable-sized, so allocating and releasing segments can create separated free memory regions.
7. Which fragmentation is caused by fixed partitioning?
Fixed partitioning commonly causes internal fragmentation because a process may not use the entire partition assigned to it.
8. Which fragmentation is caused by variable partitioning?
Variable partitioning can lead to external fragmentation because free regions can become scattered as processes are allocated and released.
9. Can external fragmentation be removed?
It can sometimes be reduced using compaction or by using non-contiguous memory-allocation techniques. The appropriate solution depends on the memory-management system.
10. Can compaction solve internal fragmentation?
No. Compaction is intended to combine separate free regions and therefore addresses external fragmentation. It does not normally recover unused space inside an allocated fixed-size block.
11. Can external fragmentation cause allocation failure?
Yes. A contiguous allocation request can fail when no single free region is large enough, even though the total amount of free memory is sufficient.
12. Which fragmentation is easier to remember for paging?
For basic operating-system exam questions, remember that paging is associated with internal fragmentation, particularly because the final page may be only partially used.
13. Which fragmentation is associated with segmentation?
Segmentation is commonly associated with external fragmentation because segments have variable sizes.
14. Is fragmentation the same as memory leakage?
No. Fragmentation concerns inefficient distribution or utilization of memory. A memory leak occurs when allocated memory remains unreachable or unreleased even though the program no longer needs it.
Conclusion
Internal and external fragmentation are important memory-management concepts in operating systems.
Internal fragmentation occurs when unused space exists inside an allocated memory block. It is commonly associated with fixed-size allocation and can occur in paging.
External fragmentation occurs when available memory is divided into separate free regions. It is commonly associated with variable-size contiguous allocation and can occur with segmentation.
Internal Fragmentation → unused space inside an allocated block.
External Fragmentation → free space outside/between allocated blocks.
Understanding this distinction also makes it easier to understand related operating-system topics such as paging, segmentation, memory allocation, first fit, best fit, worst fit, compaction and virtual memory.
No comments:
Post a Comment