Variable Size Partitioning

Introduction

Memory management can be addressed using variable(dynamic) partitioning as an alternative to fixed Partitioning. We do not declare the size of the partition at the beginning of dynamic Partitioning. We do so at the load time instead. Using fixed partitions, we have to determine the number and size of partitions to minimize Internal and External Fragmentation. In this case, the partition size may vary dynamically. Hence, we use variable size partitioning.

Also see, Memory Hierarchy, Multiprogramming vs Multitasking

What is Variable Size partitioning?

Memory is partitioned into various blocks of similar or varying sizes in variable-sized memory partitioning. At run-time, processes request blocks of main memory from variable-sized memory partitions. If enough main memory is available, the process will be allotted a block of the main memory of the same size as the process requires.

Here is an example to help you understand with a diagram:

Assume that the main memory of the computer has 32 Mbytes. At first, only the operating system will be in the memory. A process is assigned to a single block of memory that is large enough to be stored by the operating system. This means that the operating system will find a block whose size is equal to or greater than the size of the process.

Step1- Suppose the operating system takes up 6MB of the main memory, as illustrated in figure (i).

Step 2- Next, we bring process 1 off the hard disk and onto the main memory of 8MB (see figure (ii)).

Step 3- Process 2 now proceeds to the main memory (10MB in size, see fig. iii).

Step 4- In fig(iv), the 4MB process 3 comes into the main memory after which process 2 frees the memory block since it has completed its execution.

In cases where the block size is bigger than the process size, the block will be divided into two identical blocks. One block will be equal in size to the new process size of 6MB, the other block will be equal to the remaining size left of 4MB in figure(v).

Step 5- In fig(v) We have process 4 with a size of 6MB, which is allocated to the memory freed by process 2. The memory block was freed by process 1, as well.

Step 6: Now assume a process 5 with a size of 10 MB wants to enter the main memory, but we don't have enough contiguous memory space for it. We can see increasingly fragmented memory outside all partitions, and external fragmentation may occur.

External fragmentation can be overcome by moving processes so that they are contiguous and so that all free memory is gathered in one block. According to Figure h, compacting will generate a 16M-long free memory block. If necessary, an additional process can be loaded in. A downside of compaction is that it takes a long time and wastes processor time. 

See, Contiguous Memory Allocation and Open Source Operating System

How does this work?

We keep a physical table (linked list) that indicates the used/accessible memory areas in the variable partitioning method. When the process starts, all the memory is free and allocated in one large block. The OS finds free memory when a new process arrives by searching for a large block to accommodate it. The remaining memory is kept available (free) for future processes. A block becomes free when its neighbors also become free. Therefore, the OS will try to merge them. 

For finding memory blocks of a specific size, there are three algorithms.

• First Fit: A new process must be allocated to the first free block that is large enough. It's a speedy process.

• Best Fit: It is best to select the smallest block from large enough to handle the new process. As a result, the OS either has to search the entire list or keep it sorted and stop when an entry with a size bigger than a new process is encountered. As a result, the OS creates the smallest leftover block. In addition, searching or sorting all the lists takes more time.
   
• Worst Fit: Allocate the largest block dealing with the new process. The entire list will need to be searched or sorted again. It produces the largest leftover block.

Advantages

1. Internal Fragmentation is absent:
   Partitions are created dynamically based on the needs of the process with Variable Partitioning. Therefore, internal fragmentation cannot occur in Variable Partitioning because there is no unused space in the partition.
    
2. No restriction on process size:
   The process cannot be loaded or put into memory if the process size is greater than the partition size in fixed Partitioning. Variable Partitioning allows the size of a process to be flexible, and the size of the partition can be adapted to the size of the process.
    
3. The degree of Multiprogramming is dynamic.
   The Variable Partition method prevents internal fragmentation, so the partition does not have unused space. This means that more processes can run simultaneously.

Disadvantages

1. Complex memory allocation: When using Fixed Partitioning, we cannot change the partition list once it has been created. However, Variable Partitions present a challenge when allocating and relocating resources. Every time a partition is allocated to a new process, the size of the partition varies. The operating system must track each partition.
   Since dynamic memory allocation is difficult to deallocate and allocate, and we have to adjust the partition size every time, it is tough for the operating system to manage.
    
2. External fragmentation:
   Let's take an example of three processes, each weighing 5MB, processes P1, P2, and P3. Each process will have access to 20MB of RAM divided among 10MB blocks.
   In our example, processes 2 and 3 have freed up memory blocks after executing. Now, assume that we are taking away processes 2 and 3. Then the main memory will become like Fig 2.

Consider that we load a new process, P4, of 8MB into the memory. The process cannot be loaded into memory, even though there is 10MB of free memory. To load P4, we need a contiguous block of 8MB.

You can also read about the interleave memory.

Must Read Evolution of Operating System