The two programs included in this repository simulate the Buddy System, First Fit, Next Fit, Best Fit and Worst Fit memory allocation algorithms used in numerous operating systems. Tree data structure was used for the implementation of buddy system where as two separate doubly link lists have been used to keep the record of the holes and the memory allocated to the processes in case of First Fit, Next Fit, Best Fit and Worst Fit algorithms simulation.
The buddy system is a memory allocation and management algorithm that manages memory in power of two increments. In the first fit, the approach is to allocate the first free partition or hole large enough which can accommodate the request. It finishes after finding the first suitable free partition. The best fit deals with allocating the smallest free partition which meets the requirement. This algorithm first searches the entire list of free partitions and considers the smallest hole that is adequate. Next fit is a modified version of first fit. It begins as first fit to find a free partition. When called the next time it starts searching from where it left off instead of the beginning. In case of worst fit, the approach is to locate largest available free partition so that the left over portion will be big enough to be useful again.
- Buddy System
Implementation Details
I. Tree data structure was used for the implementation of buddy system.
II. First of all create a single tree node of size 64 K, and then enter into a loop which will run 10,100 times.
III. Start random allocation and de-allocation in this loop by calling respective functions based on the remainder of rand function.
IV. When ever the allocation function is called a process of random size is generated and the nearest value in power of 2 is calculated which helps in the splitting of the tree if required.
V. Based on the computed value a block of required size is first searched in the free list of that power of 2 only.
VI. If the block is found then the process is inserted into that block, free space left after the allocation of process in that block is computed for later use.
VII. If the block of required size is not found in the free list then a block of larger size is split into two, and the process of splitting continues until a match with the nearest power of 2 occurs.
VIII. When the de-allocation function is called a block which has been allocated to a process is selected randomly while parsing the tree.
IX. The space allocated to the process is freed and a recursive function is called which checks if merging of buddies is possible or not.
X. The recursive function moves from the leaves to the root and tries to merge two buddies if they are free. Free list is also kept updated for each level of the power of 2
- First Fit, Next Fit, Best Fit, Worst Fit Algorithms
Implementation Details
I. Two Separate doubly link list have been used to keep the record of the holes and the memory allocated to the processes.
II. The algorithm begins by partitioning the 64 k memory in the form of alternative holes and processes to depict a realistic scenario.
III. Then the program enters a loop in which 10,000 + allocations and de-allocations alternate depending on the remainder on a value generated by rand function.
IV. In the allocate memory function a process of random size is generated and then a respective hole is searched in the holes list.
V. If a match is found depending on the selected algorithm used the hole is removed or shrunk from the holes list and a new process is inserted into the process link list.
VI. And when the de-allocate memory function is called a process is deleted from the holes list based on a random selection and the memory freed is inserted into the holes list.
VII. If two holes are found to be consecutive then they are merged together.