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.