Memory allocation algorithms
There is more than one suitable partitions for the given job. Which should be used?
- First fit algorithm:- Fit the job into first fit p3 into suitable partition.
- Best fit algorithm:- Fit the job into smallest fit p3 into.
- Worst fit algorithm:- Fit the job into biggest fit p3 into.
First fit algorithm
Scan the memory from address zero upwards. As soon as a suitable partition in found, fit the job into it.
Free area table - It records the size and the starting add of the free area.
Normally, when a job goes out, the free area created is entered at the end of the free area table.
Job p1 goes out. The new free area table in
Allocation - i.e, finding a suitable partition takes O(n) time, where n is the no. of rows in the
free areas table.
Two partitions are adjacent if the sum of the starting address and the size of the partition in
equal to the starting address of the next free partition. i.e,
- Free areas adjacent in the main memory are adjacent in the free areas table also.
- or merging, examine one entry above/one entry below the new entry. So, merging in o(1)