So I've tried to emulate a memory management in Java, mainly for educational purposes. This program should contain a malloc(int capacity) and a free(int address) method. But as it turns out, doing so without either completely fragmenting the memory or using too many CPU instructions is not that easy. One of my previous attempts included having like 20 extra bytes occupied for every object, and adding another one would require to cycle through the entire ram. I couldn't find any explanation on how exactly the right algorithm for this works. The only thing I could find out is, that there is a pointer, to where the last memory segment ends, and that the length of each segment is stored right before it. So a visual representation of this would look like this:
[0, 0, 0, 0, 0, 0, 0, 0] (in this representation one number is 4 bytes as an integer)
pointer to free memory = 0;
If an object with the length of 4 bytes is added:
[4, data, 0, 0, 0, 0, 0, 0]
pointer to free memory = 8;
let's add another object (Size 4):
[4, data, 4, data, 0, 0, 0, 0]
pointer to freememory = 16;
but if I freed the first object, it would not replace the data the next time I would add something because first of all, it doesn't even know that the location a 0 and 1 is free because it isn't saved anywhere, and second of all, even if it would save it, I could just add a 16-byte object, which wouldn't fit in a gab of 8 bytes. This would result in a scenario, where much of the ram would have to be occupied, just the save all the gaps in memory and their sizes. And the CPU would have to constantly cycle through the entire ram, just to find a gab that is big enough for the object I want to add. On Top of that, gaps would have to be combined if they are next to each other. And even if all of that would be done, it wouldn't even guarantee me to be 100% free of memory fragmentation. So I thought there has to be some clever algorithm to take care of this problem.