Memory management-worst fit algorithm

[prashantgolu]

let us suppose we use the worst fit algorithm for allocating memory...initaially when whole of the memory is available...then it allocates full memory to one single process...hence no multiprogramming possible...hence what are the advantages of this algorithm...over first fit and best fit...
Thanks

 

[chiro]

As you pointed out there is a trade-off with allocating full memory against fast allocation.

Typically we can use a bin analogy to demonstrate speed vs allocated memory. Ultimately the algorithm that allocates all the memory is one that has a region of RAM and allocates every byte to a particular memory handle for a process. Now this is insane because you would need to have other memory to say what process and handle is associated with each byte and all of that overhead would be ridiculous.

So the next thing to do is to say that we have so many bins and these bins hold all of the memory for a process. You might have more than one bin that is set aside for a process.

Now pretend your pieces of "garbage" (ie the chunks of memory allocated to the process) are to be packed into your bins. This is a well known problem that is called the N-D bin packing problem, where N in this case is 1.

From this you start to get an idea about how to analyze fragmentation.

Now on top of this you have to use domain specific knowledge about memory allocation. Although good programmers will write routines that don't abuse memory allocation where its not needed, there are cases where you will not know in the future how much memory you need.

So essentially you need to take into account not only the bin packing problem, but also the issue that memory will be freed and allocated dynamically and that adds a whole new dimension to your problem.

Thankfully since memory is plentiful (in comparison to the past), we can use fairly large bin sizes and many programs will allocate memory that is far less than the available memory (that is RAM - kernel memory - other allocated memory).

Also in the above case, you have enough bins that if a small chunk of memory is freed from one bin and a new allocation is bigger than what's available, then due to the amount of memory, you can easily use another bin.

 

[prashantgolu]

thanks...

 

[rcgldr]

I'm not sure about bin sizes, but in wintel environments, you're dealing with a 4k page size for virtual memory. These are allocated in groups, but if there is a lot of allocation and freeing of memory, you end up with a lot of empty space in partially filled 4k pages. .net has a garbage collection scheme to help with this.

 

[LudusRex]

for your question. The worst fit algorithm for memory management is a method for allocating memory to processes in a computer system. This algorithm works by allocating the largest block of available memory to a process, which can result in a more fragmented memory space.

One of the main advantages of the worst fit algorithm is that it can help reduce external fragmentation, as larger blocks of memory are allocated to processes. This can be beneficial for systems with a large number of processes requiring varying amounts of memory.

In comparison, the first fit algorithm allocates the first available block of memory that is large enough for a process, which can result in smaller blocks of unused memory scattered throughout the system. The best fit algorithm allocates the smallest block of memory that is sufficient for a process, which can also lead to external fragmentation.

Another advantage of the worst fit algorithm is that it can help improve memory utilization. By allocating larger blocks of memory, there is a higher chance of fitting in more processes and reducing the number of processes waiting for memory.

However, as mentioned in the question, the worst fit algorithm can also lead to a lack of multiprogramming, as it may allocate all available memory to a single process. This can result in slower system performance and longer wait times for other processes trying to access memory.

In conclusion, the worst fit algorithm has its advantages in reducing external fragmentation and improving memory utilization. However, it is important to consider the trade-offs and potential limitations of this algorithm, such as reduced multiprogramming capabilities. Ultimately, the choice of memory management algorithm should depend on the specific needs and constraints of the system.