Contiguous memory allocation is one of the most efficient and the easiest way of allocating memory to the processes. Each process gets a single contiguous section of memory. The operating system gets either the lower or the higher memory address. While the other processes get the remaining memory.
Question-How the OS ensures memory protection?
Answer- By using relocation and limit registers where the limit register is the size of the process and relocation register is the starting physical address of the process. The limit register contains the total number of addresses of a process. Whereas the relocation register contains the starting address.
The CPU generates a logical address. If it is less than the value of limit register this means it belongs to the process. Finally, the OS adds the logical address with the value of relocation register to generate the physical address.
Question?
Q1. Suppose that the value of relocation register is 1000 and the limit register is 7000. Then, what is the physical address for the following logical addresses 500?
Ans: The logical address is less than the limit register value. Therefore, the physical address is 1000 + 500 i.e., 1500.
Fixed Partition and Variable Partition
Two common methods for allocating memory in contiguous memory allocation are:
1. Fixed-Partition
2. Variable-Partition.
In the fixed-partition method, memory is divided into several fixed-size partitions. Each partition contains exactly one process. In this case, the degree of multiprogramming is equal to the number of partitions. In the variable-partition method, the whole memory is a big hole. Initially, it is all empty. Whenever a process arrives it is allocated memory from the hole. The OS maintains a table indicating which part of the memory is free.
Fixed Partition 
Variable Partition
Refer the PPT and video below to understand the above concepts with animation.
PPT on Contiguous Memory Allocation
Note: Clicking on the “next” slide button will not display any animation. Hence, Click within the slide area for animations.
Video on Contiguous Memory Allocation
Drawback of Contiguous Memory Allocation
Contiguous memory allocation suffers from a problem known as External Fragmentation. External fragmentation means there is enough total memory space to satisfy a request, but the available space is not contiguous.
Hence, the process does not get any space in memory. The Variable-partition method usually suffers from external fragmentation. The solution to this problem is Compaction or Defragmentation.
Memory Allocation Methods
When a new process arrives and multiple memory blocks are available then which block should be allocated to a process? There are three methods – first fit, best fit and worst fit.
- First Fit– In this method the system allocates the first block big enough to accommodate the process. For example, if process size is 5Mb and two free block 10MB and 15Mb are available in-order. Then, the 10MB block is allocated to the process.
- Best Fit– The memory management unit first searches all the free blocks. Then it selects the block that creates the smallest new block. For example, if process size is 5Mb and two free block 10MB and 7Mb are available. 7Mb block is selected because it creates a new block of only 2MB.
- Worst Fit– The memory management unit first searches all the free blocks. Then it selects the block that creates the larget new block. For example, if process size is 5Mb and two free block 10MB and 7Mb are available. This time the OS selects 10MB block because it creates a new block of 5MB.
PPT on Block Allocation
Note: Clicking on the “next” slide button will not display any animation. Hence, Click within the slide area for animations.
Video on Block Allocation
Question
Q2. Given three free memory partitions of 10 KB, 20 KB and 15 KB(in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 15 KB, 10 KB, 20 KB and 5 KB (in order)?
Ans: First of all let’s consider first fit method.
Let the blocks be numbered B1(10KB), B2(20KB) and B3(15KB). Firstly the 15KB process gets the block B2. Thereby, creating a new block B4 of 5KB before B3. Next, 10KB process gets block B1. Then, 20KB process can not be allocated any block. This is because no block of this size is available. Lastly, the 5 KB process gets block B4.
The next method is best-fit.
Firstly the 15KB process gets the block B3. Next, the 10KB process gets block B1. Then, 20KB process gets block B2. Finally, as no free space is left so process 5 KB remains unalloted.
Now, try the worst-fit method and share your answers in the comments section.
Previous Next Memory Management Basics Paging
Let
First partition be from 0KB to 150KB
From 150KB to 200KB, let there be no partition.
Second partition from 200KB to 400KB
Then, from 400KB to 500 KB, let there be no partition.
Third partition from 500KB to 600KB.
And the last partition from 700KB to 750 KB.
First fit
1. Put 150KB in the first partition i.e. in 0KB to 150KB
2. Put 100 KB in the second partition i.e. in 200KB to 400KB partition. Since we need only 100KB of space therefore, 200KB-100KB=100KB, which means in the second partition, we have 100KB space left.
3. Since now we have to put 200KB process in the memory, but we do not have enough space, so 200KB is not possible to be allocated.
4. Put 50KB in the second partition’s half part i.e. in 300KB to 400KB. But we need only 50KB space, therefore 100KB-50KB=50KB.
Hence, 50KB space is still left in the second partition.
Best fit
1. Put 150KB in the first partition i.e. in 0KB to 150KB.
2. Put 100KB in the third partition i.e. from 500KB to 600KB.
3. Put 200KB in the second partition i.e. from 200KB to 400KB.
4. Put 50KB in the fourth partition i.e. from 700KB to 750KB.
Worst fit
1. Put 150KB in the second partition i.e. from 200KB to 400KB. Since we need only 150KB of space, therefore, 200KB-150KB=50KB.
2. Put 100KB in the first partition i.e. from 0KB to 150KB. But since we need only 100KB space, hence 150KB-100KB=50KB.
3. 200KB cannot be allocated since there is no contiguous free space available.
4. Put 50KB in the third partition i.e. from 500KB to 600KB. But since we need only 50KB space, hence, 100KB-50KB=50KB.
Suppose P1 : 150 KB process, P2 : 100 KB process, P3 : 200 KB process, P4: 50 KB process.
FIRST FIT :
P1 -> 150 KB partition, leaving 0 KB partition (no partition)
P2 -> 200 KB partition, leaving 100 KB partition. Let us name this partition A1.
P3 -> cannot be accommodated, since there is no available partition large enough.
P4 -> 100 KB remaining partition (A1), leaving 50 KB partition.
BEST FIT :
P1 -> 150 KB partition, leaving 0 KB partition (no partition)
P2 -> 100 KB partition, leaving 0 KB partition (no partition)
P3 -> 200 KB partition, leaving 0 KB partition (no partition)
P4 – 50 KB partition, leaving 0 KB partition (no partition)
WORST FIT :
P1 -> 200 KB partition, leaving 50 KB partition (let us name this partition A1)
P2 -> 150 KB partition, leaving 50 KB partition (let us name this partition A2)
P3 -> cannot be accommodated, since there is no available partition large enough.
P4 -> 100 KB partition, leaving 50 KB partition
Since Best-Fit accommodates all four processes, it gives the best performance.
Memory Partition: — (0 to 150 KB), (200 to 400 KB), (600 to 800 KB), (900 to 1000 KB)
Order of Processes:- 150 KB, 100 KB, 200 KB, 50 KB
FIRST FIT:–
Process of 150 KB memory takes first partition of size (0 to 150 KB)
Process of 100 KB memory takes second partition of size (200 to 400 KB) , left 100 KB (300 to 400 KB)
Process of 200 KB memory arise, it takes memory block of size (600 to 800 KB) as (300 to 400 KB) has space less than needed for Process 200 KB.
Now, process of size 50 KB arise, it takes first available space of (300 to 400 KB) and use till 350 KB only.
Total space left ->> (350 to 400 KB) and (900 to 1000 KB) which means 150 KB.
BEST FIT:–
Process of 150 KB came, it chooses the available space so it takes (0 to 150 KB).
Process of 100 KB arise, it takes memory block of size (900 to 1000 KB) space as it fully fit for it, although memory block of size (200 to 400 KB) and (600 to 800 KB) are available for it.
Process of 200 KB arise, it takes block of size (200 to 400 KB).
And last process of 50 KB came it takes memory block of (600 to 800 KB) and use till 650 KB.
Total space left ->> (650 KB to 800 KB) which means 150 KB.
WORST FIT:–
Process of 150 KB arise and take largest block, since block of size (200 to 400 KB) and (600 to 800 KB) are of same size so it takes first block of size (200 to 400 KB) and (350 to 400 KB) left.
Process of 100 KB came and occupy (600 to 800 KB) and use only (600 to 700 KB).
Process of 200 KB arise, now available spaces are (0 to 150 KB), (350 to 400 KB), (700 to 800 KB), (900 to 1000 KB)
So, this process unable to use any memory block .
Process of 50 KB arise, and use and largest size block i.e (0 to 150 KB) and left (50 to 150 KB).
Total space left ->> (50 to 150 KB), (350 KB to 400 KB), (700 to 800 KB) and (900 to 1000 KB) which means 350 KB.
Since in First Fit and Best Fit, all the processes able to fit the memory and left only 150 KB space. But in case of Worst Fit, process of 200 KB is not able to use any memory block and wastage of memory is more (350 KB). Hence worst fit is not suitable and we can choose first fit or best fit if we are choosing memory of this type of partition.
I have choosen the partition of this type 150 KB, 100KB, 200 KB, 200KB by mistake.
Sorry for inconvenience.
Memory Partition: — (0 to 150 KB), (200 to 400 KB), (500 to 600 KB), (700 to 750 KB)
Order of Processes:- 150 KB, 100 KB, 200 KB, 50 KB
FIRST FIT:–
Process of 150 KB memory takes first partition of size (0 to 150 KB)
Process of 100 KB memory takes second partition of size (200 to 400 KB) , left 100 KB (300 to 400 KB)
Process of 200 KB memory arise, available spaces are (300 to 400 KB), (500 to 600 KB), (700 to 750 KB). So it can not take any of the available spaces as it needs large space.
Now, process of size 50 KB arise, it takes first available space of (300 to 400 KB) and use till 350 KB only.
–> 200 KB process left.
BEST FIT:–
Process of 150 KB came, it chooses the available space so it takes (0 to 150 KB).
Process of 100 KB arise, it takes memory block of size (500 to 600 KB).
Process of 200 KB arise, it takes block of size (200 to 400 KB).
And last process of 50 KB came it takes memory block of (700 to 750 KB).
–>> No process left.
WORST FIT:–
Process of 150 KB arise and take largest block, since block of size (200 to 400 KB) and left (350 to 400 KB).
Process of 100 KB came and occupy (0 to 150 KB) and space left is (100 to 150 KB).
Process of 200 KB arise, now available spaces are (100 to 150 KB), (350 to 400 KB), (500 to 600 KB), (700 to 750 KB)
So, this process unable to use any of the memory block .
Process of 50 KB arise, and use and largest size block i.e (500 to 600 KB) and left (550 to 600 KB).
–> 200 KB process left.
Since in Worst Fit and First Fit, all processes are not able to use the memory. So, Best Fit gives best performance as all processes able to use the memory space efficiently.
Memory Partitions : 0-150 , 200-400 , 450 -550 , 600-650.
P1 : 150KB, P2: 100KB , P3: 200KB , P4:50KB.
FIRST FIT:
In the case of First Fit: The Process will be placed in the block if it is sufficient size.
P1 ->process of 150KB takes the 0-150KB block and there will be no further partition.
P2 ->process of 100KB takes the 200-400 block and the process will be allocated the memory from (200-300) and the rest amount of memory is available for further processes.
P3 -> now there is no particular block of memory which is having 200KB continuously so for P3 there will be no memory allocation.
p4-> Memory block from 300-400 will be allocated to this.
BEST FIT:
P1 -> For P1 (0-150)block will be allocated.
P2-> For P2 (450-550) memory block will be allocated.
P3 -> For P3 (200-400) memory block will be allocated.
P4 -> For P4 (600-650) memory block will be allocated.
In this algorithm each and every process got the memory.
WORST FIT:
P1 -> For P1 (200-400) Memory Block will be allocated. (Here another 50KB has remained .which can be used for further allocation.)
P2 -> For P2 (0-100) Memory block will be allocated.
P3 -> For P3 There will be no allocation of memory that takes place as there is no contiguous memory block of 200KB.
P4 -> For P4 (350-400) Memory block will be allocated, which remained after the allocation of P1.
By using this algorithm we cannot allocate memory for P3.
BEST FIT is the best algorithm to solve this problem as it allocates required memory to all the processes.