Minotaur Memory Management ========================== Minotaur uses a paging scheme, which is the most commonly found memory management scheme in modern operating systems. All the physical memory is broken into fixed-sized blocks called frames. All the logical memory (code + data + stack + any other memory a processes needs (e.g heap, although Minotaur does not support dynamic allocation of memory, so processes do not have a heap) ) is broken into blocks of the same size called pages. The pages of a processes are loaded into physical frames for execution by a CPU. A paging scheme has no external fragmentation because every frame can be used. Internal fragmentation is also significantly reduced because at most one frame per process is not fully utilized. Note the distinction between pages and frames. In physical (primary) memory, i.e. RAM, they are called frames, whereas pages can be either on disk or in memory. In general, they refer to the same thing, just the current location is different. The Minotaur virtual machine has 128*1024 bytes of physical memory. The physical memory is broken down into 128 frames of 1024 bytes. Don't change the size of anything. Lots of things are dependent on their sizes being divisible by 2, 4, 512, 1024 or the size of some other component. In reality, this is implemented as an array of nat4, so a physical memory reference is actually just an offset into this array. (See Hardware/RAM) Virtual Memory and Address Translation -------------------------------------- (show diagram of virtual and physical pages. ) Every process, plus the kernel, has a virtual address space of 256K, which is 256 pages since each page is 1024 bytes. The virtual address used by an executing process will not correspond to the actual location of the page in physical memory, so it must be translated. For this, each process has a page table that tells it where to find the physical page that corresponds to a virtual page owned by the process. These page tables are only one page long themselves, creating the 256K limit on the size of the process' virtual address space, since the page table can only have 256 entries of 4 bytes each. Bits 17-10 of the virtual address are used as the offset into the process' page table. Since the page table consists of 4-byte entries, there will be 256 entries, and these 8 bits will be enough to address the entire table. The remaining 10 low-order bits are the offset of the address from the start of the page. The page is 2^10=1024 bytes, so this are sufficient to address the entire page by byte. (Although accesses to bytes that are not multiples of 4 or 2 are not allowed, and will generate a bus error.) Once the correct page table entry has been found, bits 17-10 of the virtual address are replaced by the physical frame address in the page table entry, and this will give a physical address. (Actually just an index into the RAM array.) Now the process can access the physical memory. (See LoadMem in Hardware\CPU_mem.b) (see page table translation diagram - p.4 in Minotaur Virtual Machine document /u/csc468h/include/documents/virt_mach.ps) Paging ------ Obviously, since there are only 128 pages of physical memory, and each process can address up to 256 pages, it won't take long before Minotaur will run out of pages. For this reason, some pages that are not needed are stored on the disk until they are needed. Minotaur has a page daemon that periodically wakes up and takes a look around to see how many pages are in physical memory, and how may are on the disk. (See Kernel/PgDaemon) This is a separate process that will free up frames by copying them to the disk, when the number of free frames is below MinFree (25%), until it reaches LotsFree (50%). Page Faults ----------- If the CPU attempts to access a page which is not present in physical memory, a page fault is generated. The presence or absence of the page in physical memory is indicated by status bits in the process' page table. Take a look in Hardware/CPU_mem.b to see when the hardware generates page faults (there are about 8 cases). The procedure PageFault in CPU_mem.b packs the fault data into cpu registers. Then it causes a trap. The IDT catches the trap and calls PageFault in Kernel/Memory.b Look in the procedure PageFault in Kernel/Memory.b to see how to unpack the page fault data and handle it. In the case of the page being in the swap file, it is reloaded into a free frame, the page table entry of the process is updated to point to this frame, and the CPU attempts to execute the instruction over again. If the page does not exist, the program will exit, since there is no way to continue execution. (This is the source of the infamous Windows acronym IPF, for Invalid Page Fault). Memory Organization ------------------- % % The Kernel's virtual memory is initialized as follows: % % Virtual Page maps to Physical Frame Contents % ------------ -------------- -------- % % Page 0 ----> Frame 0 GPT % Page 253 ----> Frame 1 System stacks % Page 254 ----> Frame 2 Kernel buffer % Page 255 ----> Frame 3 Kernel page % These 4 system pages are always at frames 0 to 3. In particular, these 4 pages are never swapped out so the kernel can access them without turning off paging (or locking them). The Global Page Table (GPT) is the page table for the kernel. Although there is no kernel process, it is conceptually a different execution context, and for this reason has its own stack and virtual memory and so on. All processes have a Local Page Table (LPT) which is stored as a page in the kernel's virtual memory. See the Minotaur docs section 3.2 and 3.3 on memory layout. Expand on that by indicating the process LPT is stored in the kernel virtual memory (shaded area). The kernel and buffer page are in the same location in both the kernel and the user virtual memory. This allows the kernel to use routines as user processes by setting the LPT to point to the GPT. A nil user pointer means the process is the kernel. The core map keeps track of user frames. There is one core map entry per user frame (frames 4 to 128, or FirstFree to MaxFree). This is somewhat like an inverse of the page tables, i.e. given a frame, who owns it?, instead of, where is this frame that I own? The term is an ancient reference to core memories. The core map has the following structure: var coreMap : array FirstFree .. MaxFree of record next : nat1 % Next entry in free-list text : boolean % Page is a text page index : nat1 % Index of owner procedure or text table entry page : nat1 % Page number in process/text segment locked : boolean % Page cannot be paged out iswap : nat2 % Index of page swap space on disk end record var firstFree : nat1 % Index of the first free frame var lastFree : nat1 % Index of the last free frame var numFree : nat1 % Number of free frames In a real OS, the core map has to use up frames in the physical memory. In Minotaur, this info is in oot2 variables instead. If the frame contains a shared text page then the core map entry has: 1) text = true 2) index = index of the text class (more on shared text later) 3) iswap = unused (Minotaur doesn't page out text frames!) Otherwise, the core map entry has: 1) text = false 2) index = owner 3) iswap = index of the swap page In either case: 1) page = page number of the frame 2) locked = true when the frame cannot be paged out % The SwapMap is a bitmap of free pages in the swap file. 1 = free. % The 2^k bit of the ith array element corresponds to the swap page % 32 * i + k. % var swapMap : array 0 .. SwapMapSize - 1 of nat4 The swap map is an array (0 to 31) which represents a bitmap of free swap pages used to allocate non-text pages. Again, this info is stored in oot2 variables instead of real memory. See GetSwapPage in Memory.b for details on bit handling. % % A TextClass structure stores information about the origin of the text % page along with a mapping of the text pages to physical frames. % type TextClass : record fileName : string % name of file that text is from disk : nat1 % disk number that text is from diskInode : nat1 % source inode of text on disk invalid : boolean % has the disk file changed? dataStart : nat4 % dataStart field of file header dataLength : nat4 % dataLength field of file header numUsers : nat1 % number of processes sharing text frame : array 0 .. MaxNumTextPages - 1 of nat1 % physical frames end record Whenever some code is loaded up from the disk, it becomes a text page. As more users access the same code, numUsers increases. When a process terminates, numUsers for its code decreases. When numUsers = 0, the pages are freed. If the disk file changes then the invalid bit is set. The next time that page of text is loaded, instead of incrementing numUsers, a new text page is allocated for the changed text. Thus existing processes will have the old text and new processes will have the new text.