Memory Management

The computer's central processing unit generates the address of an instruction or data and this address corresponds to the actual location of the data in memory. For example, if a computer executes an instruction such as MOVE $1234,D0, the source operand is found in location number $1234 in the computer's random access memory. Although this statement is true of simple microprocessor systems, it's not true of computers with operating systems such as Unix and Windows. An address generated by the CPU doesn't necessarily correspond to the actual location of the data in memory.

Memory management is a general term that covers all the various techniques by which an address generated by a CPU is translated into the actual address of the data in memory. Memory management plays several roles in a computer system. First, memory management permits computers with small main stores to execute programs that are far larger than the main store. Second, memory management is used in multitasking operating systems to make it look as if each task has sole control of the CPU. Third, memory management can be employed to protect one task from being corrupted by another task. Finally, memory management, in conjunction with the operating system, deals with the allocation of memory to variables.

If all computers had an infinite amount of random access memory, life would be much easier for the operating system designer. When a new program is loaded from disk, you can place it immediately after the last program you loaded into memory. Moreover, with an infinitely large memory you never have to worry about loading programs that are too large for the available memory. In practice, real computers often have too little memory. In this section we are going to look at how the operating system manages the available memory.

Figure 1a demonstrates a multitasking system in which three processes are initially loaded into memory—task A, task B, and task C. This diagram shows the physical memory or main store where the programs are located. In figure 1b task B has been executed to completion and deleted from memory to leave a hole in the memory. In figure 1c a new process, task D, is loaded in part of the unused memory and task A deleted. Finally, in figure 1d a new process, task E, is loaded in memory in two parts because it can’t fit in any single free block of memory space.

Figure 1 Memory fragmentation in a multitasking environment

A multitasking system rapidly runs into the memory allocation and memory fragmentation problems described by figure 1. Operating systems solve these problems by means of memory management that maps the computer’s programs onto the available memory space. Memory management is carried out by means of special purpose hardware called a memory management unit, MMU (see Figure 2). Some microprocessors include a MMU on the same chip as the CPU and some microprocessors use external MMUs.

Whenever the CPU generates the address of an operand or an instruction, it places the address on its address bus. This address is called a logical address—it’s the address that the programmer sees. The MMU translates the logical address into the location or physical address of the operand in memory. In figure 2 part of the address from the CPU goes to the memory management unit where it is changed or mapped into a new address; for example, the logical address $12345678 might get mapped onto the physical address $ABC678.

Figure 2 The memory management unit

The logical address consists of two parts, a word address and a page address. Figure 3 illustrates the relationship between word address and page address for a very simple computer system with four pages of eight words (i.e., 4 x 8 = 32 locations).

The address from the CPU in figure 3 consists of a 2-bit page address that selects one of 2² = 4 pages, and a 3-bit word address that provides an offset (or index) into the currently selected page. A 3-bit offset can access 2³ = 8 words within a page. If, for example, the CPU generates the address 10110₂, location 6 on logical page 2 is accessed.

Figure 3 The structure of paged memory

In a system with memory management the 3-bit word address from the CPU goes directly to the memory, but the 2-bit page address is sent to the memory management unit (see figure 4). The logical page address from the CPU selects an entry in a table of pages in the MMU as figure 4 demonstrates. Suppose the processor accesses logical page 2 and the corresponding page table entry contains the value 3. This value (i.e., 3) corresponds to the physical page address of the location being accessed in memory; that is the MMU has translated logical page 2 into physical page 3. The physical address corresponds to the location of the actual operand in memory. If you compare figures 3 and 4 you can see that the same logical address has been used to access two different physical addresses.

Figure 4 Mapping logical onto physical pages

Why should the operating system go to the trouble of taking an address from the processor and using an MMU to convert it into a new address in order to access memory? To answer this question we have to look at how programs are arranged in memory. Figure 5 shows the structure of both logical memory and physical memory at some point during the execution of tasks A, B, C, and D. As far as the processor is concerned, the tasks all occupy single blocks of address space that are located consecutively in logical memory—figure 5a.

If you examine the physical memory, figure 5b, the actual tasks are distributed in real memory in an almost random fashion. Both tasks B and C are split into non-consecutive regions and two regions of physical memory are currently unallocated. Note also that the logical address space seen by the processor is larger than the physical address space—task D is currently located on the hard disk and is not in the computer’s RAM.

A processor’s logical address space is composed of all the addresses that the processor can specify. If the processor has a 32-bit address, its logical address space consists of 2³² bytes. The physical address space is composed of the actual memory and its size depends on how much memory the computer user can afford. We will soon see how the operating system deals with situations in which the processor wishes to run programs that are larger than the available physical address space. The function of the MMU is to map the addresses generated by the CPU onto the actual memory and to keep track of where data is stored as new tasks are created and old ones removed. With an MMU, the processor doesn’t have to worry about where programs and data are actually located.

Figure 5 Logical and physical address space

Consider a system with 4 Kbyte logical and physical pages and suppose the processor generates the logical address 881234₁₆. This 24-bit address is made up of a 12-bit logical page address 881₁₆ and a 12-bit word address 234₁₆. The 12 low-order bits, 234₁₆, define the same relative location within both logical and physical address pages. The logical page address is sent to the MMU which looks up the corresponding physical page address in entry number 881 in the page table. The physical page address found in this location is passed to memory.

Let’s look at the way in which the MMU carries out the mapping process. Figure 6 demonstrates how the pages or frames of logical address space are mapped onto the frames of physical address space. The corresponding address mapping table is described in table 1. Notice that logical page 3 and logical page 8 are both mapped onto physical page 6. This situation might arise when two programs share a common resource (e.g., a compiler or an editor). Although each program thinks that it has a unique copy of the resource, both programs access a shared copy of the resource.

Figure 6 Mapping logical address space onto physical address space

Table 1 Logical to physical address mapping table corresponding to figure 6

Virtual Memory

We’ve already said that a computer can execute programs larger than its physical memory. In a virtual memory system the programmer sees a large array of physical memory (the virtual memory) which appears to be entirely composed of high-speed main store. In reality, the physical memory is composed of a small high-speed RAM and a much slower disk store. Virtual memory has two advantages. It allows the execution of programs larger than the physical memory would normally permit, and frees the programmer from worrying about choosing logical addresses falling within the range of available physical addresses. Programmers are at liberty to choose any logical address they desire for their program and its variables. The actual addresses selected by a programmer do not matter, since the logical addresses are automatically mapped into the available physical memory space as the operating system sees fit.

The means of accomplishing such an apparently impossible task is called Virtual memory and was first used in the Atlas computer at the University of Manchester, England in 1960. Figure 7 illustrates a system with ten logical address pages but only five physical address pages. Consequently, only 50% of the logical address space can be mapped onto physical address space at any instant. Table 2 provides a logical page to physical page mapping table for this situation. Each entry in the logical address page table has two entries: one is the present bit that indicates whether the corresponding page is available in physical memory; the other is the logical page to physical page mapping.

Figure 7 A system with a smaller physical address space than a logical address space

Part of a program that's not being used resides on disk. When this code is to be executed, it is copied from disk to the computer's immediate access memory. Sometimes it’s impossible to fit the all the program (and any data required by the program) in main memory at any instant. Consequently, only part of the program can be loaded into random access memory. The operating system divides the program into pages and loads some of these pages into its random access memory. As pages are loaded, the operating system updates the page table in the MMU so that each logical page can be mapped onto the corresponding physical page in RAM.

Table 2 Logical to physical address mapping table corresponding to figure 7

Consider what happens when such a program that resides partially in memory and partially on disk is executed. When the processor generates a logical address, the memory management unit reads its mapping table to look up the corresponding physical page address. If the page is present in RAM, a logical to physical address translation takes place and the information is accessed. However, if the logical page is currently not in RAM, an address translation cannot take place. In this case, the MMU sends a special type of interrupt to the processor called a page-fault.

When the processor detects a page-fault from the MMU, the operating system intervenes and copies a page of data from the disk to the random access memory. Finally, the operating system updates the page-mapping table in the MMU, and reruns the faulted memory access. This arrangement is called virtual memory because the processor appears to have a physical memory as large as its logical address space.

Virtual memory works effectively only if, for most of the time, the data being accessed is in physical memory. Fortunately, accesses to programs and their data are highly clustered. Operating systems designers speak of the 80:20 rule—for 80% of the time the processor accesses only 20% of a program. Note that the principles governing the operation of virtual memory are, essentially, the same as those governing the operation of cache memory (described later).

When a page-fault is detected, the operating system transfers a new page from disk to physical memory and overwrites a page in physical memory. So, which page gets the chop when a new page is loaded in memory? The most sensible way of selecting an old page for removal is to take the page that is not going to be required in the near future. Unfortunately, this algorithm is impossible to implement. A simple page replacement algorithm is called the not-recently-used algorithm, NRU. The NRU algorithm is not optimum, but it is very easy to implement.

When a new page replaces an old page, any data in the old page frame that has been modified since it was created must be written back to disk. A typical virtual memory system clears a dirty bit in the page table when the page is first created. Whenever the processor performs a write operation to an operand on this page, the dirty bit is set. When this page is swapped out (i.e., overwritten by a new page), the operating system looks at its dirty bit. If this bit is clear, nothing need be done; if it is set, the page must be copied to disk.

Virtual memory allows the programmer to write programs without having to know anything about the characteristics of real memory and where the program is to be located.

Virtual Memory and the 68K Family

Members of Motorola's 68K family (e.g., 68010, 68020, 68060, etc) are well suited to virtual memory technology. We should point out here that the 68000 was the first member of the 68K family and lacks some of the facilities required to support virtual memory efficiently. The 68020 and later members of this family are much better suited to virtual memory systems than the plain vanilla 68000.

We've already stated that the architecture of the 68K family provides several mechanisms to support operating systems. The 68K's protected state when S = 1 separates operating system and application level programs (aided by the dual stack pointer mechanism). Members of the 68K family have a function control output that tells an external system such as a memory management unit whether the CPU is executing an instruction in the user or supervisor state.

Figure 8 illustrates the dialogue that takes place between the CPU, the memory management unit (MMU), and the memory system during a read or a write cycle. The MMU is configured by the operating system when the computer is first powered up. The operating system sets up logical address to physical address translation tables and defines the type of access that each page may take part in (we'll see the reason for this shortly).

 Figure 8 Dialogue between the CPU, MMU, and memory

At the start of a memory access the CPU generates a logical address and sends it to the MMU together with the control signals that define the type of the access (i.e., read or write, program or data, user or supervisor mode). If the location being accessed is not currently in the main store or is an illegal access, the MMU sends an error message to the CPU to abort the current access and to begin exception processing (and error recovery). An illegal access occurs when a task attempts to write to a page that has been designated read-only, or when a user program is attempting to access a page assigned to supervisor space and the operating system.

By dividing memory space into regions of different characteristics, you can provide a considerable measure of security. A user program cannot access memory space belonging to the operating system, because an attempt to access this memory space would result in the MMU generating an interrupt. Not only does the 68K protect the supervisor stack pointer from illegal access by a user program, the 68K and MMU combination protects the supervisor stack (and any other address space allocated to the supervisor) from illegal access.

Figure 9 illustrates the structure of a memory management system in a 68K-based computer that checks whether the address space currently being accessed is legal. The 68010 and 68020 use external MMUs. Later members of the 68K family (e.g., 68030) have on-chip MMUs. Each entry in the MMU's page translation table contains the details about the page's access rights. Whenever the 68K performs a memory access, it indicates the type of access on its function code output pins (e.g., user/supervisor, code/data). For example, the 68020 may say "I'm operating in the user state performing a read access to data with a logical address $12345678". The MMU compares the function code (and the read/write signal) with the information in the currently accessed page in its mapping table. If the access is legal, a memory access takes place. If either the corresponding physical page is not in memory or the access is illegal, a page fault is generated and a signal returned to the 68K's bus error input. In terms of the previous example, the logical address $12345678 might generate a page address $12345. If this page is in the MMU and it can be accessed by a user-mode write, a logical-to-physical page translation can take place.

Figure 9 Memory space matching hardware

A bus error is a special type of exception and the 68K calls the appropriate handler in the operating system to deal with it. A missing physical page results in the operating system copying a page from disk to main store and then updating the MMU. An illegal access would probably run in the offending task being suspended.

The 68K’s user/supervisor modes, exception handling facilities, and memory management make it a very robust processor. Errors in a user program that would otherwise bring the system to a halt, force a switch to the 68K’s supervisor state and allow the operating system to either repair the damage or to terminate the faulty program. The memory management mechanism protects the operating system from illegal access by applications programs and even protects one user program from access by another.