Fragmentation - aryanjoshi0823/5143-Operating-System GitHub Wiki

Fragmentation: An unwanted problem with operating systems is fragmentation, which occurs when processes load and unload from memory and divide available memory. Because memory blocks are so small, they cannot be assigned to processes, and thus remain idle. It’s also important to realize that programs create free space or holes in memory when they are loaded and unloaded. Because additional processes cannot be assigned to these little pieces, memory is used inefficiently.

• The memory allocation scheme determines the fragmentation circumstances. These regions of memory become fragmented when the process loads and unloads from it, making it unusable for incoming processes. We refer to it as fragmentation.

• This can happen when a file is too large to fit into a single contiguous block of free space on the storage medium, or when the blocks of free space on the medium are insufficient to hold the file. Because the system must search for and retrieve individual fragments from different locations in order to open the file, fragmentation can cause problems when reading or accessing the file.

Internal Fragmentation is a memory management issue that occurs when allocated memory blocks are larger than what processes require, leading to unused memory within the allocated block. This problem arises due to inefficient memory allocation strategies, resulting in wasted memory and performance degradation.

---

• Operating systems often allocate memory in fixed-sized blocks (e.g., multiples of 4KB).
• When a process requests memory that is smaller than the block size, the excess space in the block remains unused, causing internal fragmentation.
• In some systems, a constant amount of memory is allocated to every process.
• Processes requiring less memory than the fixed allocation leave portions of their allocated memory unused.
• Memory tracking systems use additional memory to manage allocation.
• This overhead contributes to internal fragmentation, as part of the allocated memory is used for bookkeeping rather than the process itself.

---

Let’s assume that the system that is being used assigns the memory in blocks of sizes being multiples of 4(like 12, 24, 32,..). In this system when a process P1 requests an amount of memory that is not a multiple of 4, it is assigned a memory block of value of the nearest higher multiple.

For example, in this system if a process P1 requests a memory of 29kb, as it is not a multiple of 4 the process is assigned a memory of size 32kb as this is a multiple of 4. Now, the process will only use 29kb of memory, and the rest of the memory goes wasted. This wasted memory results in internal fragmentation.

---

1. Variable-Sized Allocation Blocks: Use blocks of varying sizes instead of fixed sizes to better fit the requested memory, minimizing wasted space.
2. Dynamic Memory Allocation: Allocate memory dynamically to match the exact requirements of processes, reducing or eliminating wastage.

---

External Fragmentation occurs when available memory is divided into numerous small, non-contiguous blocks, making it difficult to allocate larger continuous blocks of memory to processes. This fragmentation arises from the dynamic allocation and deallocation of memory over time, leaving gaps between allocated memory blocks.

---

1. Dynamic Allocation and Deallocation:

   • As processes are loaded into and removed from memory, gaps are created between memory blocks.
   • These gaps, though individually small, may collectively add up to a significant amount of unused memory.

2. Memory Request Challenges:

   • When a process requests a specific amount of memory, the system may struggle to find a single contiguous block of the requested size, even if the total free memory is sufficient.

3. Fragmentation Accumulation:

   • Over time, as more processes are loaded and unloaded, the gaps become more scattered, increasing fragmentation.

---

1. Compaction:

   • Rearrange memory to combine scattered free spaces into a single contiguous block.
   • However, this process is computationally expensive.

2. Paging and Segmentation:

   • Use paging to divide memory into fixed-sized blocks or segmentation for variable-sized blocks, reducing the need for contiguous memory.

3. Buddy System:

   • Allocate memory in blocks of sizes that are powers of two, ensuring that free blocks can be merged efficiently.

• Lets consider a memory space having 4 processes, process 1 (40kb), process 2(60kb), process3(10kb), process 4(20kb) .

• Now suppose Process 1 and Process 2 have been completed, so now there are free places available, as shown in Figure 1.

• Now, if we want to run another process (Process 5) requiring memory 50 KB, we will not be able to do it, although there is enough memory to run Process 5 as the memory is not contiguous, as shown in Figure 2.