Memory Management

This article will shed some light on various ways of keeping track of memory. Since I'm not totally "into" this stuff myself, I will use this text to "experiment" with various techniques. First I'll start by describing ways of keeping track of the 1st MB of memory in the range 00000000-000FFFFF. Then I will try to implement a scheme of keeping track of memory in the 1MB-4GB range.

Note that this page is very colorful, this because this topic is rather gray and boring...

When talking about the 1st MB of memory, I'm talking about real-mode, a segmented memory model, with no 32-bit addressing and memory paging.

Certain areas of low memory are reserved for specific purposes and this must be handled in the proper way. In order to explain this I will show you a sample memory map of the 1st MB of memory:

00000	003FF	IVT	Interrupt Vector Table
00400	004FF	BDA	BIOS Data Area.
00500	00501	PRTSCR	1st byte is Print Screen Status BYTE.
00501	9xxxx	OS	OS specific.
07C00	07CFF	BOOT	Where Boot Sectors are loaded by the BIOS.
9xxxx	9FFFF	EBDA	Extended BIOS Data Area, varies in size (at least 1KB).
A0000	AFFFF	VIDEO	Used by the Video Adapter (Graphics Mode).
B0000	B7FFF	VIDEO	Used by the Video Adapter (Monochrome).
B8000	BFFFF	VIDEO	Used by the Video Adapter (Textmode).
C0000	C7FFF	VIDEO	Used by the Video BIOS.
C8000	EFFFF	ROM	May be used by adapter ROMs or as memory mapped I/O.
F0000	FFFFF	BIOS	System BIOS, 32K (starts at F8000) or 64K.

The memory map will vary from system to system, but most likely it will look similar to the one above. Probably the most varying memory is in the range C0000-FFFFF.

The size of the EBDA, if it is present, will be specified in kilobytes by a WORD at offset 13H within the BIOS Data Area. The OS can use all memory up to the point specified here, but must provide a method of sharing this memory with programs it wishes to load, otherwise the system will be useless. There are some other programs that might use this memory, such as viruses and other resident software loaded before the OS. Either via a ROM or by the boot sector.

Keep a pointer similar to the one at BDA[13] somewhere. Initially set it to point to the segment above the last space you need for your OS' kernel and resident drivers. Then whenever you need to load a new program/driver/module/whatever, you just increase this pointer with the amount of memory you need. You then give the program the previous and current values of this pointer so it knows which range it can use.

Split the memory range into blocks as needed, and keep a small structure at the start of each blocks with information about the status of the block. This is the DOS method of memory management. The advantage of this is that you can free up memory in any order. The disadvantage is memory fragmentation and a bit of complexity to newbies.

Store a bitmap somewhere in memory with each bit representing the status of a chunk of memory. You can choose between "big chunks and a small bitmap" or "small chunks and a big bitmap". A good choice would be 1KB chunks. With this size the bitmap would use 640 bits, or 80 bytes. When memory is needed just find a range which is large enough. Obviously using a chunk size of 16 bytes would be more flexible, but it would give you a larger bitmap - 5KB or 5120 bytes. This method requires the OS or each program to "remember" what memory ranges it uses, so it would properly free it up when not needed anymore.

Similar to the method above, but with 2 bits for each memory chunk. With 2 bits per chunk, you could indicate more than just used/unused. You could for instance use the following values:

0 - Free (simply unused, available memory)
1 - System Memory (OS and drivers).
2 - Program Memory (Code and Data for application programs).
3 - Reserved Memory (Can be used to specify ROMs and adapter memory).

This method is an extension of method 3a or 3b. In addition to a bitmap, let the OS keep a small table with starting/ending memory chunk pairs or similar. Whenever a program needs memory, just check this table for an unused pair (zero).

As you can see, it's only your imagination that can stop you from designing your memory manager.

With many memory managers you are given a "handle" when you successfully allocate memory, and pass this "handle" when you deallocate memory. This "handle" can be the starting address of a memory area/block (method 1 or 2 - DOS method). For methods 3a/3b the program itself must store this information. The "handle" is often used as an index into a table of memory info (suitable for method 4).

If you decided to go with the bitmap/handle method you could let the bitmap cover the entire 1MB memory range and initially just set the bits representing the IVT, BDA, OS, VIDEO and ROM areas. This would stop the memory manager from using these ranges.

That's about all that can be said about memory management for real-mode. Simple stuff. Let's then move on to memory management for memory above 1MB, with 386+ protected mode.

As you probably have noticed, I've beautifully skipped the odd 286, with it's semi-implementation of protected mode. The reason for this is that the 286 uses the same 64K segments as the 8086, but includes the selector scheme of the 386 which allows you to specify a 24-bit base address for segment selectors. The most useful memory management technique for this processor would be the bitmap/handle scheme I mentioned earlier, though with a slightly bigger handle table. Enough about the 286 processor...

With the 386 you have a special mode where you can use a function called "paging". With paging enabled the processor puts and extra layer between the logical linear address and the physical address placed on the memory bus during MemR/MemW cycles. The processor divides the memory space into 4KB chunks called simply pages. Newer Pentiums can also enable the use of 2MB/4MB pages, but I will ignore this feature right now, because I'm not very familiar with it.

With paging the system can have one or more "Page Directories" each containing pointers to "Page Tables" which in turn points to a single page of 4KB. The address of the page directory page, is specified in Control Register 3, if you want to know more about this, get one of the Intel manuals.

If you forget about paging and think you do not need or want to implement virtual memory, you can use any of the methods used in my real-mode section. The method of keeping a single "last used address" pointer, is a very stupid and cheap solution. Also there are some problem with this solution called "memory holes" and "memory mapped I/O". Most BIOS's have an option to enable a so-called memory hole at 15MB-16MB for use with adapters (most likely PCI). Also most video cards today support a "linear frame buffer".

This leads us to the bitmap/handle method, once again. If you keep a bitmap with one or two bits for each 4KB page, you can initially simply set the bits where memory holes, adapters, etc. resides. Then you will need a big table of some kind to store the address pairs used when keeping track of allocated memory. OK, here are the methods I can think of:

Keep a bitmap with one bit for each 4KB page. If you have 128MB of memory, the memory will be divided into 32768 pages, each using one bit in the bitmap. The bitmap will then neatly fit into one page! In addition to this include a table with several 2 DWORD address pairs describing a starting/ending memory address. All the bits covered by the range will then be set in the bitmap, and cleared when memory chunk is deallocated.

Same as above, but with two bits per page. This allows a more detailed status information about memory to be stored. As I suggest above, these three values could be used:

Keep our well known bitmap, any version, 1-bit or 2-bit version, but drop the handle table. Instead use the global descriptor table to keep track of which memory ranges belongs to which application. Use the base address as starting page, and the descriptor limit as count of pages. When a program needs to allocate memory, it will get a descriptor value, similar to a memory handle.

There's really not much more to say about memory management,
have fun, and write a great OS!!