1.
First-fit:
It is simplest algorithm.
Memory manager scans list of holes and allocate first
hole that is big enough.
Searching
always starts at beginning of set of holes and stop as soon as it finds a free
hole this is large enough to satisfy memory requirement of current process.
Hole
is broken into 2 parts. One for process and one create a hole except it is
exact fit.
Advantage:
it
is fast because it searches as little as possible.
2.
Next-fit:
It is a minor variation in first-fit.
It
works same as first fit except, it keep track of its position in list of holes.
Means it keeps track that where it stopped when it find a suitable hole in
next-fit search.
When
next-fit is called again, it starts searching from place in list of holes where
it stopped in previous next-fit search. Not like first-fit, which always start
searching form first hole in list?
Disadvantage:
experiment shows next-fit gives slightly worse performance than first-fit.
3.
Best-fit:
It
searches entire list and takes smallest hole that is big enough to satisfy
memory requirement.
Instead
of breaking a big hole (that might be needed later), best-fit tries to find a
hole that is close to actual required size.
It produces smallest
leftover hole.
Disadvantage:
it is slower than first-fit because it must search entire list every time.
Also,
it results in more wasted memory than first-fit or next-fit because it creates
tiny useless holes.
4. worst-fit:
There
is a problem of tiny hole when we are searching nearly exact match for a
process.
Allocate
the largest hole. We search in entire list and find the largest available hole.
So that the broken hole will be large enough and can be used to satisfy
requirement of other process.
Disadvantage: Experiment shows that worse
fit is not a good idea.
5. Quick-fit:
It maintains separate list
for some common size of requested memory.
For
example, tables with n entered are maintained. First entry is a pointer to head
of list of 4k holes. Second entry is a pointer to head of list of 8k holes.
Third entry is a pointer to head of list of 12k holes and so on.
Odd
sized holes like 21k can be put in 20k hole list or we can put it in a special
list of odd-sized holes.
Whenever
there is a request comes form new process, we find it in the hole list of the
size requested by process.
If
there is no list of requested size hole than we can search entire in list of
odd-sized hole in a list which contain bigger hole than the requested size.
Advantage: finding hole of requested
size is extremely fast.
Disadvantage:
when a process is terminated or swapped out, we need to find its neighbors to check whether merging of holes are possible or not.
Here
due to separate list of holes, the process of finding neighbors for merging
will be expensive.
And
if merging is not done, memory will contain large number of small holes that
can not be utilized by any process.