Writing a memory manager: Difference between revisions

 

What I'm going to talk about assumes you know where the chunk of free memory is you can play with. For a flat memory model, this can be from the end of your kernel code (say the 1/2MB mark) to the end of the system memory (GRUB can give you this info). For a paging kernel, this can be the beginning of the page to the end of the page.

=== malloc() ===

Okay, the first step is to get out a pen and paper - I don't mean a keyboard and text editor since you can't draw diagrams (a stylus/tablet is okay with your favorite-graphics-program/OneNote/Windows-Journal).

 

# Mark it as used

# Return its address

Then break it up.

 

** No

*** Point to the next block and go back to step 2

Once you have found one, set it's used bit to used. If the space found is significantly larger than the space needed, then it is generally a good idea to split it up (cut it in half, then half again, or add another header right after the used space and update the pointers. use your imagination!) ;] Then return the address!

=== free() ===

in your bitmap or which header is associated with the address you're given. With a header it's simply address - size of header. Set it's bit to free.

 

 

Just keep breaking it into smaller, and smaller blocks. Make sure you understand 100% how each process works. The key is to understand it fully before you start coding! Write down every equation for everything. It is essential you know how your code works, and have it in readable form on paper, so when an error occurs it's easy to debug.

=== Testing ===

Only then, you can start coding. Once it's written, you should try it out in a simple sandbox environment. Such as allocate around about 5 random sizes, deallocate a few from the middle, re allocate them, and get them to print out all their memory addresses at each step, then take the time to work it out on paper to see if it's doing it correctly. The main problem I've had is with the freeing (combining free blocks together) which I had to print out every step to the screen to find the bug (I forget what it was, a = instead of a == I think).

 

Good luck with your MM. :]

== Best fit MM ==

A basic idea of a best fit memory manager is same as a first fit one. Having blocks in memory. But the problem with first fit is the fragmentation which occurs when splitting blocks way bigger than we need, when there are smaller fitting blocks.

=== Keeping track of free blocks ===

You need to know where each free block is in memory, and how big it is. You can store this in an array, or binary tree, or whatever.

The way you sort the list is important. If we sort the list on size, small to big, we can look for free block starting at first entry, and as long as the current node is not big enough, going to next node. This way you will find the best fitting block. If no block is found, you need to ask the virtual memory manager for more memory.

 

=== Merging and splitting blocks ===

Merging and splitting free blocks becomes a bit more work because you have to keep your free block list updated.

 

Good luck making a best fit memory allocator!

[[Category:Memory management]]

[[Category:Tutorials]]