L-5.4: Variable size Partitioning | Memory management | Operating System

Summary

This script delves into the concept of variable partitioning in memory management, contrasting it with fixed partitioning. It explains how variable partitioning avoids internal fragmentation by allocating memory at runtime based on process needs, allowing for greater flexibility in process sizes and enhancing the degree of multiprogramming. However, it introduces external fragmentation, where free memory is scattered and unusable for processes requiring contiguous space. The script also touches on the complexity of allocation and deallocation in variable partitioning and suggests compaction as a remedy, despite its drawbacks.

Takeaways

• 📚 **Variable Partitioning** is a memory allocation strategy where space in RAM is allocated to processes only when they require it, avoiding pre-allocation and thus reducing internal fragmentation.
• 🔄 **Fixed Partitioning** contrasts with Variable Partitioning by dividing RAM into fixed-size partitions in advance, which can lead to internal fragmentation when processes don't perfectly fit partition sizes.
• 🍕 **Pizza Analogy** for memory allocation illustrates the concept of pre-allocating (Fixed Partitioning) versus allocating based on demand (Variable Partitioning), like cutting pizza slices to order.
• 🚫 **Internal Fragmentation** is a waste of memory space that occurs in Fixed Partitioning when a process doesn't fully utilize its allocated partition.
• 🔑 **Dynamic Allocation** in Variable Partitioning allows for memory to be allocated at runtime based on a process's actual needs, potentially eliminating internal fragmentation.
• 🔝 **Degree of Multiprogramming** is enhanced in Variable Partitioning, as there's no fixed limit on the number of processes that can be loaded into RAM, unlike in Fixed Partitioning.
• 🚀 **No Size Limit** on processes in Variable Partitioning means that very large processes can be accommodated, unlike in Fixed Partitioning where the process size is limited by partition size.
• 🕳️ **External Fragmentation** can occur in Variable Partitioning when free memory exists but isn't contiguous, preventing the allocation of processes larger than the available contiguous space.
• 🔄 **Compaction** is a method to overcome external fragmentation by moving processes to consolidate free space, though it's resource-intensive and can interrupt process execution.
• 📈 **Allocation and De-allocation** in Variable Partitioning are more complex due to the dynamic nature of process and hole management, requiring strategies like bitmaps and linked lists.

Q & A

What is Variable Partitioning?

Variable Partitioning is a memory allocation strategy where space in RAM is allocated to processes only when they require it, as opposed to Fixed Partitioning where partitions are created in advance.

How does Fixed Partitioning differ from Variable Partitioning?

In Fixed Partitioning, the RAM is divided into fixed-size partitions before any process arrives, which can lead to internal fragmentation. Variable Partitioning, on the other hand, allocates memory dynamically at runtime based on the process's needs, reducing the chance of internal fragmentation.

What is meant by 'Internal Fragmentation' in the context of memory management?

Internal Fragmentation occurs when a process occupies a partition that is larger than its actual memory requirement, resulting in unused space within the partition.

Why does Fixed Partitioning always result in internal fragmentation?

Fixed Partitioning results in internal fragmentation because the partitions are predefined in size, and when a process occupies a partition, the remaining space in that partition cannot be utilized by other processes, leading to wasted space.

Can you explain the analogy of ordering a pizza in relation to memory partitioning?

The analogy compares Fixed Partitioning to ordering a pizza that is already sliced into fixed pieces, which may not perfectly match the appetite of the eaters, leading to waste. Variable Partitioning is likened to ordering a whole pizza and cutting it according to the needs of the eaters, minimizing waste.

What advantage does Variable Partitioning have over Fixed Partitioning in terms of memory utilization?

Variable Partitioning allows for dynamic allocation of memory, which can prevent internal fragmentation and make more efficient use of available memory by allocating exactly the amount needed by each process.

What is the concept of 'Degree of Multiprogramming' mentioned in the script?

Degree of Multiprogramming refers to the number of processes that can be executed simultaneously in the RAM. Variable Partitioning allows for a higher degree of multiprogramming since it does not limit the number of processes based on fixed partition sizes.

How does Variable Partitioning address the limitation on process size in Fixed Partitioning?

Variable Partitioning does not impose a maximum size limit on processes as it allocates memory dynamically. This means that even very large processes can be accommodated, unlike in Fixed Partitioning where the maximum process size is limited by the largest partition.

What is External Fragmentation, and how does it occur in Variable Partitioning?

External Fragmentation occurs when there is enough free memory collectively but not in contiguous blocks to accommodate a process. In Variable Partitioning, this can happen when processes exit and leave behind non-contiguous free spaces or 'holes' that cannot be combined to satisfy the memory requirement of a new process.

What is the solution to External Fragmentation as discussed in the script?

The script suggests Compaction as a solution to External Fragmentation, which involves moving processes to consolidate free space, although it is an undesirable method due to the need to stop processes and the time-consuming nature of copying process data to new memory locations.

How does Variable Partitioning handle the complexity of allocation and deallocation of memory?

Variable Partitioning manages the complexity of allocation and deallocation through the use of data structures like bitmaps and linked lists, which help track the availability of memory and the placement of processes in the RAM.

Outlines

00:00

💡 Variable Partitioning vs Fixed Partitioning

This paragraph explains the concept of variable partitioning in memory management, where memory is allocated to processes only when they require it, thus avoiding the waste of space. In contrast, fixed partitioning involves pre-allocating memory into fixed-sized partitions, which can lead to internal fragmentation when a process does not fully utilize its partition. The analogy of ordering a pizza is used to illustrate the difference, where variable partitioning is like cutting the pizza into pieces according to the needs of the guests, whereas fixed partitioning is like having pre-cut pieces that may not perfectly match the guests' appetites. The advantages of variable partitioning include the elimination of internal fragmentation and the flexibility to accommodate processes of varying sizes.

05:06

🔄 Advantages and Disadvantages of Variable Partitioning

The second paragraph delves into the advantages of variable partitioning, such as the ability to maximize the degree of multiprogramming by not limiting the number of processes that can be loaded into RAM, and the lack of a predefined limit on process size, allowing for the accommodation of large processes. However, it also introduces the concept of external fragmentation, which occurs when there are multiple small holes of free memory that cannot be used to satisfy the memory request of a larger process due to the requirement for contiguous memory allocation. The paragraph concludes by discussing the challenges of allocation and deallocation in variable partitioning, which are more complex than in fixed partitioning due to the dynamic nature of memory requests and the creation of holes.

10:11

🛠 Managing External Fragmentation and Allocation

The final paragraph addresses the issue of external fragmentation in variable partitioning, where free memory is scattered and cannot be used effectively. It introduces compaction as a potential solution, which involves moving processes to consolidate free memory, although this method is undesirable due to the need to stop running processes and the time-consuming nature of copying memory. The paragraph also discusses the complexity of allocation and deallocation in variable partitioning, where the dynamic nature of process and hole creation makes management more challenging. It concludes by mentioning the use of bitmaps and linked lists as tools to manage the allocation of memory and to keep track of where holes and processes are located within the memory.

Keywords

💡Variable Partitioning

Variable Partitioning is a memory management technique where the allocation of memory to processes is done dynamically at runtime, based on the actual space required by the process. This is in contrast to Fixed Partitioning, where memory is divided into fixed-size partitions in advance. In the context of the video, Variable Partitioning is highlighted as a method that eliminates the need for pre-allocating memory, allowing for more efficient use of RAM by matching the exact size needed by each process, thus reducing internal fragmentation. However, it introduces the possibility of external fragmentation, as free memory may not be contiguous.

💡Fixed Partitioning

Fixed Partitioning is another memory management strategy where the RAM is divided into fixed-size partitions before any process arrives. Each partition has a predetermined size, and processes are allocated to these partitions as they come. The video script uses the analogy of a pizza that is pre-cut into pieces to illustrate Fixed Partitioning. This method can lead to internal fragmentation, where a process might not fully utilize its allocated partition, leaving some space wasted. The script contrasts this with Variable Partitioning, emphasizing the inflexibility and inefficiency of Fixed Partitioning.

💡Internal Fragmentation

Internal Fragmentation occurs when a process occupies a partition that is larger than its actual memory requirement, resulting in unused space within that partition. The video script explains this concept using the example of a 1KB process being allocated a 2KB partition in Fixed Partitioning, where the remaining 1KB is wasted. This type of fragmentation is inevitable in Fixed Partitioning due to the fixed sizes of partitions, which do not always match the exact needs of the processes.

💡External Fragmentation

External Fragmentation is a type of memory fragmentation that occurs when there are multiple small free memory blocks (holes) that are too small to satisfy the memory request of a process, even though the total amount of free memory might be sufficient. The video script describes this scenario using the example of having two 4MB holes that cannot accommodate an 8MB process, despite having 8MB of free memory in total. External Fragmentation is a challenge in Variable Partitioning, where memory is allocated dynamically and processes may leave non-contiguous free spaces upon termination.

💡Dynamic Programming

Although not explicitly detailed in the script, the concept of Dynamic Programming is related to the theme of the video as it refers to making decisions or solving problems based on the current state, which is analogous to Variable Partitioning where memory allocation is decided at runtime based on the current needs of the processes. The video emphasizes the dynamic nature of memory allocation in Variable Partitioning, where the system adapts to the varying sizes of incoming processes, as opposed to the static allocation in Fixed Partitioning.

💡Degree of Multiprogramming

The Degree of Multiprogramming refers to the number of processes that can be executed simultaneously in the RAM. The video script points out that in Fixed Partitioning, this number is limited by the number of partitions created, whereas in Variable Partitioning, there is no such limitation, allowing for a potentially higher degree of multiprogramming. This flexibility is one of the advantages of Variable Partitioning, as it can accommodate more processes by dynamically allocating memory as needed.

💡Contiguous Allocation

Contiguous Allocation is a memory allocation strategy where a process must be located in a single, continuous block of memory. The video script mentions that both Fixed and Variable Partitioning operate under this strategy, which means that a process cannot span across multiple non-contiguous memory blocks. This requirement can lead to external fragmentation, as seen in the example where an 8MB process cannot be accommodated in two separate 4MB holes.

💡Compaction

Compaction is a technique used to reduce external fragmentation by moving processes around in memory to bring all free memory blocks together, thus creating a larger contiguous block. The video script describes compaction as a method to overcome external fragmentation, although it is noted as undesirable due to the need to stop running processes and the time-consuming nature of copying process data to new memory locations.

💡Allocation and De-allocation

Allocation and De-allocation refer to the processes of assigning memory to a process and freeing up memory when a process no longer needs it, respectively. The video script discusses the complexity of these operations in Variable Partitioning due to the dynamic nature of memory allocation and the creation of holes. The script contrasts this with Fixed Partitioning, where the number of partitions and processes are predetermined, making allocation and de-allocation simpler.

💡Bitmap and Linklist

Bitmap and Linklist are data structures used to manage memory allocation and keep track of which parts of memory are occupied and which are free. The video script mentions these concepts as tools to handle the complexity of allocation and de-allocation in Variable Partitioning, where the number of processes and holes can vary dynamically. Bitmaps and linklists help in efficiently organizing and accessing information about memory usage, which is crucial for the dynamic allocation strategy.

Highlights

Variable Partitioning allows allocation of memory only when processes enter the RAM, avoiding pre-allocation.

Fixed Partitioning involves pre-partitioning RAM into fixed sizes, leading to internal fragmentation.

Internal Fragmentation is the wasted space in a partition when a process uses less than the partition's size.

Dynamic Partitioning, like ordering a pizza, allocates memory based on runtime needs without pre-cutting.

Variable Partitioning eliminates the chance of Internal Fragmentation by matching process size to allocated memory.

Degree of Multiprogramming is maximized in Variable Partitioning as there's no fixed limit on the number of processes.

There's no limitation on process size in Variable Partitioning, accommodating large processes unlike Fixed Partitioning.

External Fragmentation occurs in Variable Partitioning when free memory is scattered and not contiguous.

Compaction is a method to reduce External Fragmentation by moving processes to consolidate free space.

Compaction can be undesirable due to the need to stop running processes and the time-consuming copying process.

Allocation and deallocation in Variable Partitioning are complex due to the dynamic nature of process and hole creation.

Bitmap and linked list concepts are used to manage allocation and deallocation in Variable Partitioning.

Variable Partitioning offers flexibility in memory allocation but requires careful management of fragmentation and allocation strategies.

The analogy of pizza ordering illustrates the dynamic nature of memory allocation in Variable Partitioning.

Fixed Partitioning's pre-defined sizes can lead to inefficiencies in memory usage, contrasting with Variable Partitioning's flexibility.

The concept of holes in memory allocation is introduced as a result of process termination in Variable Partitioning.

Transcripts

Variable Partitioning. In Variable Partitioning whenever the processes are coming into the RAM

only then we are allocating space to the processes. Means we keep the RAM empty for now,

when processes come in the RAM then at run time the capacity they need, the space they need,

according to that space I will allocate them. But in Fixed Partitioning what was the concept?

Whatever was the total size of our RAM, in the RAM, first of all Operating System is there,

in the RAM we did partitions beforehand. Before the process comes we did the partitioning.

Let's say size of one partition is 2KB, one is 4KB, one is 8KB, one is 16KB,

we have made partitions of different sizes beforehand. Now a process comes P1 of size 1KB,

So whichever free slot I get first let's say this slot is free, so I put P1 here.

Now P1 comes here, what is the size of P1? 1KB. So it used 1KB but remaining 1KB

of that partition is getting wasted. This is called the Internal Fragmentation.

And always in Fixed Partitioning Internal Fragmentation will definitely occur.

Because we have already decided the size of partition that these many partitions are to be made.

And after that the process comes which is of smaller size

some space will always remain at last which we cannot use for any process.

So this is called Internal Fragmentation. But in Dynamic Programing we keep the entire space empty,

when process comes, at run time how much space it needs, according to that I will allocate.

Its like a pizza, when we order a pizza there are already partitions made in it.

Means there are already pieces made.

Let's say this is the pizza. Now what can happen there is that

let's say a friend is there who won't be satisfied with one piece, he wants 2 to 3 pieces.

And one friend can be such that he cannot even finish 1 piece, so maybe he eats half a piece and

wastes the remaining half. But what we will do? If we allocate one-one piece then

there can be someone's demand that he wants 2 or more than 2 pieces.

So what can we do for this? What solution can we provide?

We can ask the waiter beforehand to bring the whole pizza, there is no need to cut the pizza.

So after asking for cutter from him, according to the need means some friend wants that

I want a bigger piece, so beforehand according to the need I will cut.

And if someone wants a small piece then I will cut according to that.

So the same concept we use here in memory, we are not making partitions beforehand,

we will do partitions at run time.

Now, let's examine this, let's say a process comes P1, P1 size is 2MB.

So what I will do? I will simply allocate 2MB space to P1.

So size of P1 was 2MB and how much space it took in the memory? Exactly 2MB.

So means there is no chance of Internal Fragmentation in this.

If let's say one more process comes P2, P2 size is 4MB. So already we know that

size of process is 4MB, how much is the demand of process? 4MB.

So how much will I allocate it? 4MB. Because we have all this space free. So when that process

makes a demand of 4MB, according to the need, I will fulfil the need.

So how much space I allocate for it? 4MB. So means is there any wasteage happening?

There is no wastage.

Similarly let's say there is one more process P3 comes, let's take size of P3 as 8MB,

so a process of 8MB comes here, P3,

so you can easily put the process. So we are not doing any fixed partition here.

When process comes, at run time we allocate the memory to it.

So what is the first point I can write here? There is no chance for Internal Fragmentation.

This is a very important point.

Second, what more advantage can we get in this

which was not there in fixed partitioning? The concept of Degree of Multiprogramming.

Means we have to bring maximum process inside the RAM. But in fixed partitioning,

we already divided in partitions. So if number of partitions I made,

it can occupy as many number of processes as partitions, we can put as many number of processes.

But here all my space is free. So let's say that one more process comes P4, its size is 1MB,

I will allocate, P5 comes, I will allocate, P6 comes, I will allocate.

So although there will be a constraint on RAM size but we are not talking about RAM size here,

if I say the RAM size is enough, if the RAM size I have is enough, then we

can put as much as possible number of processes in the RAM. So means there is no limitation

on the Degree of Multi Programing.

No limitation on number of processes.

This is the second advantage.

Third one is process size. If I talk about fixed partitioning here,

what can be maximum size of process which can come in the RAM? 16KB.

Because how much is the partition? 16KB. But here my entire space is free.

If a process comes here of 64MB, let's say of 64MB, then if I want to put 64MB here

I will simply allocate the memory, the space to that process. So the third point is that

there is no limitation on the process size also.

There is no limitation on the process size also.

If now one more process comes P4, we take size of P4 let's say, P3 size was 8MB,

let's say a process is of 4MB, then I put 4MB process in here.

Now let's say, one more process comes P5, size of P5 is let's say 8MB.

So according to that, whenever the process will come I will simply allocate the memory to them.

These 3 points, these three you can say advantages in the variable partitioning.

But now there is one problem in this, the problem is, let's say process P2 exits from here.

P2 process gets executed or maybe blocked so it exits from here. If P2 process exits from here,

then here I have 4MB space available. A 4MB space is empty here.

In technical terms we call it hole. This is called a hole is created because 4MB space

which was allocated here to a process, when that process exits from here it made a hole of 4MB.

Now if another process of 4MB comes then I will allocate this space to that. But if

scenario becomes such that this process of 4MB exits from here, there is a hole of 4MB and

one more process P4 also gets executed, it is also terminated and exits form here.

So it also created a hole here, its size is also what? 4MB.

Now at this time if a process comes P4.

P4 was already there, let's say P6.

A new process comes P6 and the size of P6 is 8MB.

P6 is of size 8MB. So where do I put it?

There is one hole whose size is 4MB, another hole whose size is 4MB,

but as we already know that in the contiguous allocation,

a process cannot span between 2 different different locations. Means I cannot do this to P6

that divide half and half, put half here and put half here because both partitioning,

this dynamic partitioning and fixed partitioning are under the contiguous allocation.

So whenever it goes it will go entirely as one contiguous partition.

So means when an 8MB process comes to me although I have 8MB available, 4MB here, 4MB here,

so total empty space is how much? 8MB. But can I accommodate this 8MB process here? I cannot.

So this P6 will wait. So we call this thing external fragmentation.

Yes, this is the external fragmentation. So what is external fragmentation?

Although we are having available size, although we are having available space collectively,

not at the same area, it is collectively we are having that memory available.

But still we are not able to put the process in that memory because that is not contiguous.

So although we had 8MB space available, but because of contiguous I cannot put 8MB here.

So we call this thing External Fragmentation.

So variable partitioning suffers with external fragmentation.

And how can we remove this? To remove there is a simple concept, here we can use compaction.

Compaction means to make compact. Means we take empty space to one side and

remaining processes space to one side. Means we, let's say P1, this is the Operating System,

P1, P3, P5,

P1, P3, P5, we take up together and the remaining empty space,

all the empty space we bring down. So it is like copy, paste. Means we copy a process

and paste it in some other address. We copy a process and paste it in some other place,

this method, although we can use this method, but this is undesirable because

what can be first problem in this that first of all I will have to stop the processes.

Means if any of these processes is in running state, means CPU is executing it,

then at that time I will have to stop it because it will disturb running process in running time.

And second, one process is present at any address let's say present at 1000 to 2000 address,

then I will have to copy it from here and move at some other address.

So this will already take a lot of time because it is like copy-pasting,

means we are copying one bit at some other location. So here it is 8MB.

There are 8 million bytes, if we copy so many bits at some other location

and paste there in that place, then it will take a lot of time.

So compaction is one of the methods which can be used to remove the external fragmentation

but although it is undesirable, but still we can use that method.

Second point that comes here is allocation and de-allocation means

one process which was at this place exits from here and what it creates here? Hole.

Here also what is created? Hole. So now one process which is coming new,

at which place to allocate or deallocate it, from where to remove it,

so allocation and deallocation here is a little bit complex.

Why it is complex? Because what we do in fixed partitioning is we have already decided

that number of partitions is 5. When my number of partitions is 5,

then how many maximum processes can come? 5. So P1 or P2 comes in one, one is empty,

or some other process comes in one, we can easily manage the number of partitions

if it is fixed. But here there is no fixed, many processes can come.

So here number of holes are also created dynamically and

number of processes that are coming are also dynamically coming.

Means we are allocating memory to processes. When we allocate? When process reaches the RAM.

Means the process comes to RAM and knocks that yes, I need some memory. So at that time

dynamically at run time I will have to allocate memory. And second,

when that process exits from here and although many processes can come here,

because we did not do any partition, so here number of processes can be more.

So number of processes can be more, then the number of holes can be more.

So the number of holes is more, so in which hole what process will come or not,

to remove that I will have to do allocation and de-allocation here which is complex

as compared to the fixed partition. So we can say that these two are disadvantages

of variable partitioning and these three are advantages of variable partitioning.

Now how we manage allocation and de-allocation, we use the concept of bitmap and linklist

so to manage the place where is hole and where is process filled we use the concept.

So this is all about the Variable Partitioning.

If you like the video then please like it, share it and please subscribe my channel, thank you.