Partition Allocation Method in Operating System

January 20, 2023

Partition Allocation Method in Operating System

The memory systems developed in early 1990 had a contiguous(continuous) memory available for storing different files one example of such traditional OSes is MS-Dos. But, in Partition Allocation Method in Operating System that have been developed that do not have a contiguous memory space available for files. In fact they are divided into blocks of different sizes.

Partition Allocation Methods in OS

The memory systems developed in early 1990 had a contiguous(continuous) memory available for storing different files one example of such traditional OSes is MS-Dos.

But, new systems that have been developed do not have a contiguous memory space available for files. In fact they are divided into blocks of different sizes.

This was done to avoid complete memory corruption if a file is infected. If memory is divided into blocks corrupted file will only infect that memory block in which its stored.

Priority Scheduling

CPU Scheduling

FCFS Scheduling

Preemptive Scheduling

Example of Memory Partitioning

For example, a 500Mb memory may be (equally or unequally) divided to blocks 5 blocks of 100Mb each.

Or unequally as in 5 blocks of 125mb, 75mb, 125mb, 75mb, 125mb respectively.

The main memory must accommodate –

Operating system
User processes
Operating System Processes

For a partitioned memory available in modern systems, we need different algorithms to decide most which processes must use which memory block while maintaining the most efficient use of these memory block.

We therefore need to allocate different parts of the main memory in the most efficient way possible.

Memory Partitioning Algorithms

The main four partition allocation schemes are listed below:-

First Fit
Best Fit
Worst Fit
Next Fit

Overview

There are two major divisions one for operating system residing and other for allocating processes.

OS memory can’t be altered in a direct by way by user.
Process memory is managed by OS to perform processes.

One of the simplest methods for memory allocation

Divide memory into several fixed-sized partitions.
Each partition may contain exactly one process.
When a partition is free, a process is selected from the input queue and is loaded into the free partition.
When the process terminates, the partition becomes available for another process.
The operating system keeps a table indicating which parts of memory are available and which are occupied using a table.
Finally, when a process arrives and needs memory, a memory section large enough for this process is provided.

The following are used to choose process memory allocation –

First Fit
Best Fit
Worst Fit
Next Fit

We will use the following memory block to demonstrate each process –

[table id=366 /]

First Fit

For a process P1, whichever first partition (starting from the top) is large enough to fit the current process, gets the process allocated to itself.

See Example at –

Partitioned Blocks –

[table id=366 /]

Jobs –

[table id=367 /]

Job 1 (size – 100k)

1. Can’t fit in block 1 as 50k(block size) <100k (job size)
2. Goes to block 2 as can fit in block 2 as 200K > 100K (Size of block more than size of process)
  1. 100K remains empty in this block now.

Job 2 (size 10K)

1. Goes to block 1 as 10K < 100k

Job 3 (size 35 K)

1. Can fit Block 1 but block 1 is not empty(used by job2)
2. Can’t fit and also Block 2 not empty
3. Can fit in block 3 Goes to block 3

Job 4

1. Goes to block 4

Job 5

1. All blocks 1 to 4 are occupied
2. Can’t fit in block 5 as size is more than block

So block 5 remains unused. and Job5 has to wait until other processes finish.

[table id=368 /]

Facts

First-fit memory allocation is faster in making allocation but leads to memory waste.

If the chosen block is significantly larger than that requested, then it is usually split, and the remainder added to the list as another free block.

The first fit algorithm performs reasonably well, as it ensures that allocations are quick. When recycling free blocks, there is a choice as to where to add the blocks to the free list—effectively in what order the free list is kept

Best Fit

Best-fit memory allocation makes the best use of memory space but slower in making the allocation.

For example let us suppose that we have 4 partitions of size 16,12,8, 4 available with us. The list of available partitions is in the order of their availability . Thus if we get an incoming request for the memory size of 6.

Although the first available block that is of size 16 can accommodate the request greedily then also it won’t. Block size of 16 would have been allocated if the algorithm would have been the first fit which we will discuss later.

In this case block of 8 which is best fit for the incoming process request is allocated.

Thus, in short words – Allocate the process to the partition which is first smallest sufficient partition among the free available partition.

Example

Job 1 (size – 100k)

1. Block 1 size(50k) – 100k = Negative value
2. Block 2 size(200k) – 100k = 100k
3. Block 3 size(70k) – 100k = Negative value
4. Block 4 size(115k) – 100k = 15k
5. Block 5 size(15k) – 100k = Negative value
6. Goes to block 4 as 15K is best case

Job 2 (size – 10k)

1. Block 1 size(50k) – 10k = 40k
2. Block 2 size(200k) – 10k = 190k
3. Block 3 size(70k) – 10k = 60k
4. Block 4 occupied by job 1
5. Block 5 size(15k) – 10k = 5K
6. Goes to block 5 as 5K is best case

Job 3 (size – 35k)

1. Block 1 size(50k) – 35k = 15k
2. Block 2 size(200k) – 35k = 165k
3. Block 3 size(70k) – 35k = 35k
4. Block 4 occupied by job 1
5. Block 5 occupied by job 2
6. Goes to block 1 as 15K is best case

Job 4 (size – 15k)

1. Block 1 occupied by job 3
2. Block 2 size(200k) – 15k = 185k
3. Block 3 size(70k) – 15k = 55k
4. Block 4 occupied by job 1
5. Block 5 occupied by job 2
6. Goes to block 3 as 55k is best case

Job 5 (size – 23k)

1. Block 1 occupied by job 3
2. Only option. size of block (200k) > size of job(23k)
3. Block 3 occupied by job 4
4. Block 4 occupied by job 1
5. Block 5 occupied by job 2
6. Goes to block 2 as 100K is worst case

[table id=371 /]

Worst Fit

Worst-fit memory allocation is opposite to best-fit. It allocates free available block to the new job and it is not the best choice for an actual system It selects the largest available hole in memory that can fit a needed segment, so as to leave a large hole for other segments.

Basically look for the largest value –

Size of block – size of job

Whichever, gives the highest value job goes to that block

Example –

Job 1 (size – 100k)
- Block 1 size(50k) – 100k = negative value => Can’t fit
- Block 2 size(200k) – 100k = 100k
- Block 3 size(70k) – 100k =negative value => Can’t fit
- Block 4 size(115k) – 100k = 15k
- Block 5 size(15k) – 100k = negative value => Can’t fit
- Goes to block 2 as 100K is worst case
Job 2 (size – 10k)
- Block 1 size(50k) – 10k = 40k
- Block 2 already used by job 1. So not possible
- Block 3 size(70k) – 10k = 60k
- Block 4 size(115k) – 10k = 105k
- Block 5 size(15k) – 10k = 5k
- goes to block 4 as 105k is worst case.
Job 3(size – 35k)
- Block 1 size(50k) – 35k = 15k
- Block 2 already used by job 1. So not possible
- Block 3 size(70k) – 35k = 35k
- Block 4 already used by job 2. So not possible
- Block 5 size(15k) – 35k = negative value => Can’t fit
- goes to block 3 as 35k is worst case.
Job 4(size -15k)
- Block 1 size(50k) – 15k = 35k
- Block 2 already used by job 1. So not possible
- Block 3 already used by job 3. So not possible
- Block 4 already used by job 2. So not possible
- Block 5 size(15k) – 15k = 0
- Goes to block 1 as 35k is the worst
Job 5(size – 23k)
- Block 1 already used by job 4. So not possible
- Block 2 already used by job 1. So not possible
- Block 3 already used by job 3. So not possible
- Block 4 already used by job 2. So not possible
- Block 5 size(15k) – 23k = negative value
- Goes no where has to wait indefinitely for other blocks free up.

[table id=370 /]

Next Fit

Next fit is a modified version of ‘first fit’. It begins as first fit to find a free partition but when called next time it starts searching from where it left off, not from the beginning next fit is a very fast searching algorithm and is also comparatively faster than First Fit and Best Fit Memory Management Algorithms

Example –

Job 1 (size – 100k)

1. Can’t fit in block 1 as 50k(block size) <100k(job size)
2. Can fit in block 2 as 200K > 100K (Size of block more than size of process)
  1. 100K remains empty in this block now.

Job 2 (size 10k)

1. Last job entered in block 2 so will start from block 3 now
2. Goes to block 3 as block size(70k) > job size(10k)

Job 3(size 35K)
1. Last job entered in block 3 so will start from block 4 now
2. Goes to block 4 as block size(115k) > job size(10k)
Job 4(size 15k)
1. Last job entered in block 4 so will start from block 5 now
2. Goes to block 5 as block size(10k) = job size(10k)
Job 5(23k)
1. Last job entered in block 5 and there no further blocks, so goes back to block 1
2. Goes to block 1 as block size(50k) > job size(23k)

Finally it looks like –

[table id=369 /]

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Partition Allocation Method in Operating System