A 16-bit value associated with every process is the memory map ID. The memory map ID, in conjunction with the ring, identifies a process to the memory management unit, enabling it to determine the mapping of virtual addresses to physical addresses currently in effect. The memory map ID is not intended to uniquely identify an executing thread; it merely identifies which memory mapping is in use. The ring then identifies the available memory space within a given memory mapping.
As will be seen below, the memory map ID refers to the Process Memory Map; there is also a Global Memory Map which applies to all running processes on the computer.
Interrupts and software interrupts can change the memory map ID to any value, as they can change the ring to any value.
When a process returns from an interrupt, it may increase the ring, just as it may also exit from supervisor mode or subordinate virtual supervisor mode. It will also need to be able to restore the memory map ID. It must also only be able to set the memory map ID to values that permit access only to areas of memory to which it has access itself.
This is achieved in the following manner:
Thus, the level 3 process
1010110100000000
can create the level 5 process
1010110100110000
to which it alone has access, or the level 5 process
1010110101010000
to which the level 4 process
1010110101000000
which it could also create also has access.
Note that it can arrange for the level 5 process to have access to memory which the level 4 process that can change to its memory map ID does not directly have access; there may be useful reasons for doing this intentionally.
Note that processes whose memory map ID is nonzero, but the first two bits of which are zero, can be created; such processes simply do not have an ancestry that can be traced back to a level 0 process.
Also, the all-zeroes memory map ID can also be used; normally, it would only be used for ring 0 supervisor processes; a process with this memory map ID has its process virtual address space directly mapped to global virtual address space. A process with the all-zeroes memory map ID can consistently be termed a level -1 process.
In addition, supervisor processes can turn off the mapping from global virtual address space to physical address space; this will be required, for example, when the computer is actually engaged in copying the data from the swap file on disk into random-access memory when a page is being swapped into memory, leading to a change in the Global Memory Map once the copy is complete. This is done using the Direct Physical Addressing bit in the Program Status Block; when that bit is set, the mapping from process virtual addresses to global virtual addresses is also ignored, irrespective of the value of the memory map ID. As the contents of the process page tables refer to global virtual addresses, and not to physical addresses, they are invalid for use when the mapping from global virtual addresses to physical addresses is turned off.
To avoid either having to resort to the diagnostic mode of operation during normal functioning of the computer, or having to make extensive use of interrupt vectors which use the all-zeroes memory map ID, there is an exception to the rules given above: a process that is both in supervisor mode and in ring zero can set the memory map ID to any value even if its own memory map ID is not zero; such processes also have unrestricted access to the memory management unit to specify which areas of physical and virtual memory are accessible by means of a given memory map ID.
Because the computer can be doing anything when an external hardware interrupt signal arrives, service routines for hardware interrupts will normally have to be ring 0 supervisor processes.
A process that is in supervisor mode but neither in ring 0 nor having the all-zeroes memory map ID can therfore perform input-output, but only to input-output devices whose addresses are mapped within space it can access. Such a process has unrestricted access to the CPU and its registers, but limited access to the resources in the computer's address space, such as memory. Some portions of the operating system may run in this fashion for safety from program bugs.
Device drivers will normally run without being in supervisor mode; although they cannot execute input-output instructions in user mode, they can still perform input and output if input-output ports are mapped into virtual memory while they operate. It is intended that the memory bus will be used for input-output, with a supplemental address bit indicating an input-output instruction; input-output instructions simply ensure that the portion of address space in which input-output devices reside is always available to supervisor-mode processes.
When processes create subordinate processes with new memory map IDs, they also assign to them a memory space lying entirely within their own available memory space. For each memory map ID of any level, areas within the defined memory space available to processes with that memory map ID when in rings 0 through 7 are also defined.
When a new process is created, all memory map IDs corresponding to possible child processes of that process are marked as undefined, to prevent a process from switching to a memory map ID subordinate to it that was previously defined, perhaps a considerable time previously, as having access to memory to which it should not have access.
The instructions for creating new processes and altering the Memory Map ID are described in another section.
The diagram at the right shows how addresses as used by programs are converted to physical addresses.
The top half of the diagram, in which the process virtual address is converted to the global virtual address, illustrates the portion of the address translation unit that contains the information to which a Memory Map ID refers; the information itself is called the Process Memory Map, and the internal memory within the address translation unit into which it is loaded is called the Process Page Tables.
The bottom half of the diagram, in which the global virtual address is converted to the physical address, illustrates the portion of the address translation unit that contains the mapping of global virtual memory to physical memory, which is the same for all processes, changing as the data in a particular portion of the overall virtual address space is transferred between physical memory and swap space on disk. This information is the Global Memory Map, and the portion of the address translation unit that contains it is called the Global Page Tables.
In some architectures, page tables involve multiple levels of translation, requiring elaborate logic, such as a translation look-aside buffer, to allow most memory references to be made at high speed.
It is proposed that for this architecture, the number of levels in memory mapping will be kept to a minimum, by including inbuilt flexibility in the structure of memory maps. Even this minimum still involves four levels, however, so the use of additional logic to maintain the speed of memory access will remain helpful.
One master table, and one set of page tables, is used for each of the two levels of address translation. Translation from the internal virtual address of a given process to the global virtual address of the computer, and translation from the global virtual address of the computer to a physical address both proceed in the same manner. The first level of translation indicates what portion of virtual memory is allocated to a given process; the second level of translation indicates which portions of virtual memory are currently in RAM, and which are in a paging file on disk.
Each level of address translation proceeds as follows:
At the top level, the length of a virtual address is set: this can be any number of bits, from 64 bits down to 16 bits. (It is envisaged that values below about 20 bits will only find use in specialized applications with non-full-featured implementations of the architecture.) And the number of the most significant bits in a virtual address that are used as an index into the top-level page table is also determined.
The entries in the top-level page table consist of two parts. The first part is an indication of how many bits in an address are used to select an entry from the second-level page table. The second part is a pointer to the second-level page table to use.
The second-level page table is a collection of memory offsets, intended to give the starting location of each page in memory.
The illustration shows the effective result of memory mapping. Implementation steps would normally be used to reduce the amount of carry propagation taking place during address calculation. For example, the base registers may be shadowed by registers which contain the physical address corresponding to the process virtual address to which they point, allowing only a single addition to take place; of course, this could only work when the entire possible range of displacements to which that base register's contents could be applied is mapped in the same fashion. If the range is divided neatly into halves or quarters, a base register could be shadowed by two or four registers; as well, if displacements were 16 bits long, but after memory mapping, only the last 14 bits of the value in the shadowed base register were zero, using the first two bits of the displacement to select one of four shadow registers would be a method of avoiding carry propagation.
Note that it is important to set the length of a virtual address to the minimum required value for a given process to avoid excessively long page tables; this length can be revised upwards by the operating system while a process is executing, if a request for more memory by the process makes a longer virtual address required.
In normal operation, a virtual address is divided into exactly three parts during one level of address translation: the pointer to the entry in the top-level page table (the Table Pointer Index), the pointer to the entry in the second-level page table (the Displacement Index), and the displacement within the page.
When the desired location in virtual memory is not found in physical memory, since disk I/O is then called for, it is not necessary that the memory map include the location outside of physical memory of the page; a supervisor-mode interrupt service routine, having access both to the memory maps and to all physical memory will be called.
The bottom level page-table entries also include flags showing if a page is in memory, and if its contents have been altered since it was loaded into memory, not shown in the diagram. If not, the page can be swapped out of memory without being saved.
Note that for purposes of distinguishing between a virtual cache and a physical cache, a virtual cache would use the process virtual address, unique to a specific process, while a physical cache would use the global virtual address, common to all processes, and representing the state of the mapping between the virtual memory image on disk and physical RAM. Since the global virtual address is common to all processes, nothing would be gained by including the second level of address translation to the production of cache addresses.
There is only one tree of page tables which connects the global address space to physical memory, the Global Memory Map. But each task can have its own Process Memory Map, which is the tree of page tables that connect the internal virtual address space of the task to the global address space. The process memory map controls the access a given process has to areas in memory. Thus, for a program, the path from a virtual address to a physical address normally involves translating the program virtual address to a first-level virtual address using the two-level tree of page tables containing the Process Memory Map, and then translating it to a physical address using the two-level tree of page tables containing the Global Memory Map.
The process memory map also has the same two-level structure as the global memory map. But it is not constantly updated as pages are swapped in and out of memory. Instead, it indicates what portion of the total virtual memory a specific process finds within its own address space. Each entry in the lowest-level map table indicates if the process has read access, write access, or both to the area to which it refers, again with flags not shown in the diagram. As well, flags are present that allow a page in memory to be reserved for program code only or data only.
If a task is running with 32-bit addresses, only the input to the process memory map is 32 bits long; the length of global virtual addresses and the length of global physical addresses remain unchanged at 64 bits, even if individual processes may receive only a 32-bit virtual address space.