Tag: Dynamic Partitioning

Contiguous Memory Allocation | Practice Problems

Contiguous Memory Allocation-

 

Before you go through this article, make sure that you have gone through the previous articles on Static Partitioning and Dynamic Partitioning.

 

There are two popular techniques used for contiguous memory allocation-

 

 

In this article, we will discuss practice problems based on Contiguous Memory Allocation.

 

PRACTICE PROBLEMS BASED ON CONTIGUOUS MEMORY ALLOCATION-

 

Problem-01:

 

Consider six memory partitions of size 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB. These partitions need to be allocated to four processes of sizes 357 KB, 210 KB, 468 KB and 491 KB in that order.

Perform the allocation of processes using-

  1. First Fit Algorithm
  2. Best Fit Algorithm
  3. Worst Fit Algorithm

 

Solution-

 

According to question,

The main memory has been divided into fixed size partitions as-

 

 

Let us say the given processes are-

  • Process P1 = 357 KB
  • Process P2 = 210 KB
  • Process P3 = 468 KB
  • Process P4 = 491 KB

 

Allocation Using First Fit Algorithm-

 

In First Fit Algorithm,

  • Algorithm starts scanning the partitions serially.
  • When a partition big enough to store the process is found, it allocates that partition to the process.

 

The allocation of partitions to the given processes is shown below-

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

 

Step-04:

 

  • Process P4 can not be allocated the memory.
  • This is because no partition of size greater than or equal to the size of process P4 is available.

 

Allocation Using Best Fit Algorithm-

 

In Best Fit Algorithm,

  • Algorithm first scans all the partitions.
  • It then allocates the partition of smallest size that can store the process.

 

The allocation of partitions to the given processes is shown below-

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

 

Step-04:

 

 

Allocation Using Worst Fit Algorithm-

 

In Worst Fit Algorithm,

  • Algorithm first scans all the partitions.
  • It then allocates the partition of largest size to the process.

 

The allocation of partitions to the given processes is shown below-

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

  • Process P3 and Process P4 can not be allocated the memory.
  • This is because no partition of size greater than or equal to the size of process P3 and process P4 is available.

 

To watch video solution, click here.

 

Problem-02:

 

Consider the following heap (figure) in which blank regions are not in use and hatched regions are in use-

 

 

The sequence of requests for blocks of size 300, 25, 125, 50 can be satisfied if we use-

  1. Either first fit or best fit policy (any one)
  2. First fit but not best fit policy
  3. Best fit but not first fit policy
  4. None of the above

 

Solution-

 

The allocation follows variable size partitioning scheme.

 

Let us say the given processes are-

  • Process P1 = 300 units
  • Process P2 = 25 units
  • Process P3 = 125 units
  • Process P4 = 50 units

 

Allocation Using First Fit Algorithm-

 

The allocation of partitions to the given processes is shown below-

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

 

Step-04:

 

 

Allocation Using Best Fit Algorithm-

 

The allocation of partitions to the given processes is shown below-

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

 

Step-04:

 

  • Process P4 can not be allocated the memory.
  • This is because no partition of size greater than or equal to the size of process P4 is available.

 

Thus,

  • Only first fit allocation policy succeeds in allocating memory to all the processes.
  • Option (B) is correct.

 

To watch video solution, click here.

 

Next Article-Introduction to Paging

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Contiguous Memory Allocation | Dynamic Partitioning

Contiguous Memory Allocation-

 

Before you go through this article, make sure that you have gone through the previous article on Contiguous Memory Allocation.

 

We have discussed-

  • In contiguous memory allocation, a process can be stored only in a contiguous fashion.
  • There are two popular techniques used for contiguous memory allocation-

 

 

In this article, we will discuss about Dynamic Partitioning.

 

Dynamic Partitioning-

 

  • Dynamic partitioning is a variable size partitioning scheme.
  • It performs the allocation dynamically.
  • When a process arrives, a partition of size equal to the size of process is created.
  • Then, that partition is allocated to the process.

 

Partition Allocation Algorithms-

 

  • The processes arrive and leave the main memory.
  • As a result, holes of different size are created in the main memory.
  • These holes are allocated to the processes that arrive in future.

 

Partition allocation algorithms are used to decide which hole should be allocated to the arrived process.

 

Popular partition allocation algorithms are-

 

 

  1. First Fit Algorithm
  2. Best Fit Algorithm
  3. Worst Fit Algorithm

 

We have already discussed these algorithms in our previous article.

 

Important Points-

 

Point-01:

 

For dynamic partitioning,

  • Worst Fit Algorithm works best.
  • This is because space left after allocation inside the partition is of large size.
  • There is a high probability that this space might suit the requirement of arriving processes.

 

Point-02:

 

For dynamic partitioning,

  • Best Fit Algorithm works worst.
  • This is because space left after allocation inside the partition is of very small size.
  • There is a low probability that this space might suit the requirement of arriving processes.

 

Translating Logical Address into Physical Address-

 

The following diagram illustrates the steps of translating logical address into physical address-

 

 

The steps are same as we have discussed in our previous article.

 

Advantages-

 

The advantages of dynamic partitioning are-

  • It does not suffer from internal fragmentation.
  • Degree of multiprogramming is dynamic.
  • There is no limitation on the size of processes.

 

Disadvantages-

 

The disadvantages of dynamic partitioning are-

  • It suffers from external fragmentation.
  • Allocation and deallocation of memory is complex.

 

To gain better understanding about Contiguous Memory Allocation,

Watch this Video Lecture

 

Next Article-Practice Problems On Contiguous Memory Allocation

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.