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)
Under this scheme the memory is divided into allocation units and each allocation
unit has a corresponding bit in a bit map. If the bit is zero, the memory is
free. If the bit in the bit map is one, then the memory is currently being used.
This scheme can be shown as follows.
|
The main decision with this scheme is the size of the allocation unit. The smaller the allocation unit, the larger the bit map has to be. But, if we choose a larger allocation unit, we could waste memory as we may not use all the space allocated in each allocation unit.
The other problem with a bit map memory scheme is when we need to allocate memory to a process. Assume the allocation size is 4 bytes. If a process requests 256 bytes of memory, we must search the bit map for 64 consecutive zeroes. This is a slow operation and for this reason bit maps are not often used.
Free and allocated memory can be represented as a linked list. The memory shown above as a bit map can be represented as a linked list as follows.
 |
Each entry in the list holds the following data
· P or H : for Process or Hole
· Starting segment address
· The length of the memory segment
· The next pointer is not shown but assumed to be present
In the list above, processes follow holes and vice versa (with the exception
of the start and the end of the list). But, it does not have to be this way.
It is possible that two processes can be next to each other and we need to keep
them as separate elements in the list so that if one process ends we only return
the memory for that process.
Consecutive holes, on the other hand, can always be merged into a single list entry.
This leads to the following observations when a process terminates and returns its memory.
A terminating process can have four combinations of neighbours (we'll ignore
the start and the end of the list to simplify the discussion).
If X is the terminating process the four combinations are
 |
· In the first option we simply have to replace the P by an H, other than that the list remains the same.
· In the second option we merge two list entries into one and make the list one entry shorter.
· Option three is effectively the same as option 2.
· For the last option we merge three entries into one and the list becomes two entries shorter.
In order to implement this scheme it is normally better to have a doubly linked
list so that we have access to the previous entry.
| Last Page | Back to Main Index | Next Page |
Last Updated : 23/01/2002