This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
First Fit : This algorithm searches along the list looking for the first
segment that is large enough to accommodate the process. The segment is then
split into a hole and a process. This method is fast as the first available
hole that is large enough to accommodate the process is used.
Best Fit : Best fit searches the entire list and uses the smallest hole
that is large enough to accommodate the process. The idea is that it is better
not to split up a larger hole that might be needed later. Best fit is slower
than first fit as it must search the entire list every time. It has also be
shown that best fit performs worse than first fit as it tends to leave lots
of small gaps.
Worst Fit : As best fit leaves many small, useless holes it might be a good idea to always use the largest hole available. The idea is that splitting a large hole into two will leave a large enough hole to be useful. It has been shown that this algorithm is not very good either.
These three algorithms can all be speeded up if we maintain two lists; one for processes and one for holes. This allows the allocation of memory to a process to be speeded up as we only have to search the hole list. The downside is that list maintenance is complicated. If we allocate a hole to a process we have to move the list entry from one list to another.
However, maintaining two lists allows us to introduce another optimisation. If we hold the hole list in size order (rather than segment address order) we can make the best fit algorithm stop as soon as it finds a hole that is large enough. In fact, first fit and best fit effectively become the same algorithm.
The Quick Fit algorithm takes a different approach to those we have considered
so far. Separate lists are maintained for some of the common memory sizes that
are requested. For example, we could have a list for holes of 4K, a list for
holes of size 8K etc. One list can be kept for large holes or holes which do
not fit into any of the other lists.
Quick fit allows a hole of the right size to be found very quickly, but it
suffers in that there is even more list maintenance.
| Last Page | Back to Main Index | Next Page |
Last Updated : 23/01/2002