I've read Modern Operating Systems 4th Edition, Andrew Tanenbaum in which are presented some ways to handle the memory management (with bitmaps, with linked lists) and some of the algorithms that can be used to allocate memory (first fit, next fit, best fit, worst fit, quick fit), which are different but there is not one that is the best.
I'm trying to make my own memory allocator which will prioritize to have as low as possible external fragmentation (blocks of memory that are too small to be used) and the speed of allocation/deallocation (the first thing being the low fragmentation than the speed). I implemented the worst fit (thinking this will produce as little as possible external fragmentation because it always chooses the biggest contiguous space of memory when allocating and the remaining of that memory is enough to be used later for another allocation. I implemented it using a sorted list descending for free spaces and a set for allocated spaced sorted by address. The complexity for allocation is O(1) + the cost of maintaining the list sorted and for deallocation O(log n1) - for finding the address + O(n2) - for parsing the list of the free spaces and inserting the address found. n1= elements of the set, n2 = elements of the list.
I have multiple questions. First is how can I improve the algorithm? Second, what other algorithms used for memory allocation exists that will prioritize the fragmentation of memory? Third, are there any improved versions of the algorithms that I listed that will prioritize the fragmentation of memory? I want to know as many algorithms/methods of improving the algorithms that I know, that will reduce the external fragmentation.