[Solved]: Best Fit Memory Allocation Algorithm Statistical Analysis

Problem Detail: 

I've been reading book on Operating System, in which author writes :

Somewhat surprisingly, it(Best fit) also results in more wasted memory than first fit or next fit because it tends to fill up memory with tiny, useless holes. First fit generates larger holes on average.

I want to understand how generating larger holes would be better. It would be helpful if someone can share a link of article about statistical analysis of best fit, first fit.

Asked By : user148865

Answered By : Wandering Logic

You want your "holes" to be bigger because a big hole is more likely to be useful for an allocation in the future. For example, if you have 2 128-byte holes that are not adjacent then you can't satisfy a request for 160 bytes. If the 2 128-byte holes are adjacent and coallesced into a single 256-byte hole, then you could satisfy a future request for 160 bytes with that hole.

Here's the best article I know of on memory allocation policies:

Paul R. Wilson, Mark S Johnstone, Michael Neely, David Boles: Dynamic Storage Allocation: A Survey and Critical Review, Int'l Workshop on Memory Mgt, 1995.

They followed up with a more detailed experimental study a few years later:

Mark S Johnstone, Paul R Wilson: The Memory Fragmentation Problem: Solved?, First Int'l Symposium on Memory Mgt, 1998.

In the papers they find that best fit works quite well in practice. Another lesson of both papers is that statistical analyses don't work (usually). You need to run experiments on real traces of the alloc/free calls from real workloads.

A very good public domain malloc implementation was written in the mid '90's by Doug Lea: http://g.oswego.edu/dl/html/malloc.html. It's essentially an approximation of best fit.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48260

 Ask a Question

 Download Related Notes/Documents