List and describe the four memory allocation algorithms covered in lectures. Which two
of the four are more commonly used in practice?
Answer:
The four memory allocation algorithms (in the scheme of dynamic partitioning placement) are:
First-Fit – in the linked list of available memory addresses, we place the data in the first entry that will fit its data. Its aim is to minimise the amount of searching, but leads to external fragmentation later on.
Next-Fit – similar to first fit, but instead of searching from the beginning each time, it searches from the last successful allocation. Greatly reduces the amount of searching but leaves external fragmentation at the beginning of memory.
Worst-Fit – traverses the memory and gives the partitions as large spaces as possible – to leave usable fragments left over. Needs to search the complete list and such is a poor performer.
Best-Fit – carefully scours the memory for spaces that perfectly fit the RAM we want. However, the search is likely to take a very long time.
We most commonly use first-fit and next-fit in practise. They're easier to implement and are faster to boot.