Kernel Memory Management

Since Nachos/486 has no external environment managing resources for it, it becomes imperative that it take on certain responsibilities. Given the dynamic nature if the Nachos operating system, memory management becomes a very serious issue. Unlike a traditional monolithic UNIX kernel implementation with compile time bound constants governing the number and amount of resources available at run-time, Nachos/486 is completely dynamic. Initially the kernel has no per-thread data structures allocated. When it begins the main thread it must already be able to allocate memory for its stack!

On account of these needs, a KernelMemoryManager class was designed and implemented to allocate and deallocate regions of memory. Since we initially do not anticipate heavy demands, we chose a simple and direct implementation using two classes UsedMemoryList and FreeMemoryList which were derived from a single class MemoryList. This class is the only global object in the Nachos/486 operating system. This is necessary because it must always be in existance and it cannot be allocated without developing a ``chicken-and-egg'' ordering problem. Upon inspection of the start() routine it should be noted that the new operator is being applied to construct an instance of the KernelMemoryManager. The important point to notice is that it uses the placement version of the operator which does not request memory from any external memory management routines, but simply assumes the coder knows what he or she is doing by picking the site for the new object. In our case, we construct it into the statically allocated memory in the bss segment.

Following is a per-class and per-function summary of the features of the kernel memory management system:

• class MemoryBlockHeader: Instances of this class are used as nodes in the memory lists. Each instance is allocated directly before the memory block that it manages. It provides convenient operations to its private data members by means of the following methods: LinkTo(), MergeWithNext(), NextIsAdjacent() and SplitOff(). The first method is used to prepend it to some other instance to form the linked lists. The second merges a node in a list with the node following it. Since this can only be done when the following node is adjacent, the third method is used to test for this condition. These two methods are used to coalesce fragmented memory blocks. The last method is used to split the node yielding a new node with the requested number of bytes in it. Splitting a node has no effect on the list containing the node. Only the node is affected.

• class MemoryList: This is a standard singly linked list of MemoryBlockHeaders.

• class UsedMemoryList: This is a nominally specialized subclass of MemoryList. Its only specialization is to prepend its call names when printing its contents.

• class FreeMemoryList: This also is a subclass of MemoryList, but is more specialized and hides the interface of its superclass. This class provides the Merge() and Split() methods to either merge a new memory block into the list, i.e. deallocate a block, and to split a memory block one of the blocks in the list, i.e. allocate a block.

• class KernelMemoryManager: This class is used to encapsulate both memory lists and provides the interface to memory allocation and deallocation available at run-time. It has two private methods, _lock() and _unlock(), which are used to lock the memory lists by disabling the interrupts to acquire mutex. Since the run-time instance of Interrupt may not yet be created, these methods assume that Nachos/486 is not completely up and running and do nothing to ensure mutex. When constructing itself, it arbitrarily assumes that the manageable memory region is completely free and adds a node describing it to the free list.

  The Allocate() and Deallocate() methods perform simple operations upon the lists using their public interfaces. Generally this amounts to taking a node from one list and moving it to the other. It is at this layer that the MemoryBlockHeader's are obscured. Whereas the lists manipulate only memory blocks, these methods expect and return the address of the managed memory block which is the address of the MemoryBlockHeader plus the size of the header.

• operators new and delete: The full list of these functions appears above in section 2.3. With the KernelMemoryManager implemented, these become one and two line functions that simply pass the request on to the memory manager.