Tuesday, October 11, 2005

Memory Management

My keyboard driver is complete now and I have started learning about Memory Management. Normally, any 32-bit protected mode operating systems will have atleast two memory managers. One running in the lower level that allocates the actual physical memory and the next that works in the virtual memory layer that interacts with the physical memory manager to actually allocate physical memory. An operating system should efficiently manage memory. There are various techniques available to manage memory efficiently, stack-based approach, bitmap approach and linux's buddy system algorithm. You are not restricted to used only these algorithms. You can very well implement your own idea or the combination of any of those mentioned. Now, let us see the stack-based approach and the bitmap approach to manage the memory. I will let you all know the buddy system algorithm sooner or later :).

* Stack-based approach:
In the stack-based approach, the starting address of the physical pages are pushed into the stack initially. Then, when one or more pages are requested, they will be popped out from the stack as appropriate and the address will be passed to the virtuall mm. The advantage of using stack-based approach is that the speed of alloting pages. But, the main downfall of the stack-based approach is the fragmentation. Fragmentation arises when the free pages in the memory are not contiguous. Although you can run a daemon to reduce fragmentation when the system is free and the memory is considered to be more fragmented. Also, the space this approach takes for storing the free page addresses is also huge. Because, the size of a pointer in a 32-bit environment will be 32 bits. So, to keep track of 128 MB of memory (32768 pages), you need 128 KB of memory. You need not allocate memory pages to maintain these free page information.
You are going to return the actual physical memory to the virtual memory manager. How will the DMA controller manage when you send the physical address > 16 MB? Because, the DMA controller is not going to convert the address into physical address. Rather, it will just send the address through its address line. Well, now, you need to maintain two different stacks, one that will contain page addresses < 16 MB (for DMA) and the other will contain page addresses > 16 MB. Freeing page is as easy as allocating page. Just push the address of the page into the stack, which will used by the physical memory manager.

* Bitmap approach:
The bitmap approach is the alternative approach available to you, if you think that the Stack-based approach eats up more memory. Here, you use only one bit to store the status of the free page. 1 for available, 0 for occupied. So, in a single byte, you can store the status of 8 pages, which uses very less amount when compared with the previous stack-based approach. You can also use the bitmap to effectively allocate the best-fit and first-fit approach, which is not possible in the stack based approach. But, you need to start scanning the bitmap from the beginning, which may consume more time to allocate in best-fit approach. Some macros can be written to substitute the status of page by giving the page address.

I will explain the buddy system that is used in Linux later. I have not yet decided which algorithm to use in my physical memory manager. Recently, I have read some articles that use binary trees to track the free pages, instead of using linked list.


No comments: