operating system os

OS Memory Management with Linked Lists

« Previous Tutorial Next Tutorial »

There is also another way to keeping track of memory that is to maintain a linked list of allocated memory segments, and free memory segments, where a segment is either a process or a hole between the two processes.

When processes and holes are kept on a list that is sorted by address, several algorithms can be used to allocate memory for a newly created process or an existing process being swapped in from the disk. We assume here that memory manages knows how much memory to allocate. There are different types of algorithms to perform this.

The table given here describes those different types of algorithms:

Algorithm Description
First fit In first fit algorithm, the memory manager scans along the list of segments until it finds a hole that is big enough. The the hole is broken into two parts, that is, for process and for unused memory except in statistically unlikely case of an exact fit. This is a fast algorithm because it searches as little as possible.
Next fit The next fit algorithm works in the same way as the first fit algorithm works, except that it keeps track of where it is whenever it finds a suitable hole.
Best fit This algorithm searches the whole list and takes the smallest hole that is adequate. Rather than breaking up a big hole that might be needed later, this algorithm tries to find a hole that is close to the actual size that needed.
Worst fit This algorithm always take the largest available hole, so that the hole broken off will be big enough to be useful.
Quick fit This algorithm maintains separate lists for some of the more common sizes requested.

« Previous Tutorial Next Tutorial »


Quick Links
Signup - Login - Give Online Test