What if the aggregate memory requirements of the system plus applications excede the available main memory. If there is auxiliary memory available, for example, on disk, there are at least three ways of solving the problem:
A common form of overlay is the load-on-call procedure. The only part of the procedure initially loaded in main memory is a small stub, the load-on-call stub, that is responsible for loading the procedure into main memory and then transferring control to it. Thus, the act of calling the procedure causes it to be loaded.
Swapping involves the process scheduler. When swapping is used, memory assigned to ready processes is considered preemptable. If memory is needed, a ready process is selected to be swapped out. Swapping a process out of main memory involves copying the data segments of that process to a swapping device, usually a disk. When a process is selected to be run, if that process is swapped out, the system must first find or make space in main memory, then swap that process in, before running it.
This leads to a process state diagram such as the following:
preempt
or swap
relinquish out
---->-- ---->-
/ \ / \
RUNNING READY SWAPPED
\ / \ /
--<---- -<----
schedule swap
in
Virtual memory based on Paging and the related technique of Segmenting involves hardware address translation mechanisms that allow individual pages of the main memory being used by a program to be preemptively claimed by the system on behalf of other programs.
The subject of Virtual memory is on the interface between operating systems and computer architecture
CPU <---> MMU <---> Memory
/
Address
translation
hardware
Addresses issued by the CPU are considered to be virtual addresses.
The memory management unit translates these to physical addresses
or it complains (with a trap request) that the translation is
impossible or that the proposed access is not allowed.
Pages are typically used without regard to the logical arrangement of memory -- that is, data structures are not typically arranged in any particular way with respect to page boundaries. Programmers on paged systems do not usually pay any attention to the presence of pages.
In a segmented system, each data structure is typically assigned to a particular segment. Thus, a segments might be dedicated to each procedure or to each activation record on the stack in a fine- grained segmented system. In a coarse-grained use of segmenting, one segment might be reserved for the stack, another for the code, and a third for the global data of a program.
On some systems, large segments are divided into pages.
On paged systems, the virtual address is viewed as a single integer that indexes a word (or byte) in a single linear virtual address space.
On segmented systems, the virtual address space may be a single linear space, or it may be divided into separate spaces. The 8086 is an example of the latter, where the segment being addressed is determined by the context. PUSH and POP reference the stack segment. Most loads and stores reference the data segment, and instruction fetches reference the code segment. (This default behavior may be overridden by special instruction prefixes).
Here is a diagram of the data flow through the hardware used to translate a virtual address to a physical address in a simple paged virtual address translation memory management unit.
Virtual Address from CPU
______________________
|__________|___________|
| Page |______________________
| ___ _________ Word in Page |
| | | | |
|__| | Page | __________|
| | Table | |
V | | |
-->| | | |
|_|_______| |
| |Frame |
__| |__ |
| | |
v _____v_________v______
Access |__________|___________|
Control
Physical Address to Memory
The picture shown here shows the logical function of the
memory management unit, but there are many possible physical
organizations -- if the page table is large, it is not practical
to store it in the MMU!
The format of one entry in the page table will typically be something similar to the following:
_ _ _ _______ ______________________
| _ _ _ |_______|______________________|
| | |
| | Frame -- where is the
| | page stored.
| Access
| Control -- what actions are allowed,
| by hardware on this page.
Soft || invalid
fields -- used by software || read-only
to record other || read-write
attributes of the || execute-only
page. || dirty
Some hardware leaves space for software use in each page-table
entry. This allows the system software to maintain additional
attributes of pages that are not known to the hardware.
On other systems, the sofware may have to allocate space for
any such fields in a parallel array. In any case, the
hardware does not interpret the soft fields in any way, and on
some systems, the software may not need such fields.
On systems with a small virtual address space, the page table can be stored in hardware registers within the memory management unit.
Consider a machine with: 16 bits per virtual address, 8 bits to indicate which word in page, 8 bits to indicate which page.
This requires 256 registers in the MMU to hold one page table.
Thus, Even with special hardware, context switching may be quite slow compared to a machine where only the registers in the CPU are saved and restored.
The above example is based on the MODCOMP Classic series of computers first sold in around 1973. This were extensively used by NASA (in the space shuttle ground support system) and the oil industry (in real-time control of oil refineries and drilling operations). The machine had 16 registers of 16 bits each in the CPU.
The table can be stored in main memory. In this case, the MMU takes 2 memory cycles per memory reference, unless the table is store in main memory with a cache located in the MMU to speed access.
This scheme was used by the Feranti Atlas computer in 1960 -- the very first virtual memory computer.
Cache-based paging systems are simplest if the cache size is the same as the number of page frames in main memory.
Cache Entry _______________________________ |____________|__________________| | Page | Table | Number | Entry | | Subject to Returned by Associative Successful Search SearchIn its simplest form, the associative search involved in searching the cache involves a simple parallel comparison of the page number in each cache entry with the page number issued by the CPU. This can be done very quickly with appropriate hardware. Cache hardware to support fully associative searches is expensive, but the alternatives are the subject of an architecture course and are will not be discussed here.
If the cache size is the same as the number of page frames in main memory, a cache miss signals a page fault, and the software can be put in charge of replacing the cache entry as it replaces the page in the page frame. This approach results in the simplest possible cache hardware, since the hardware need not manage cache misses and replacement.
The page fault trap service routine gains control when the MMU detects access to a page that is not in main memory.
A trap is very similar to an interrupt. The traditional distinction is that interrupts are caused by asynchronous events, while traps are caused by the actions of the CPU. Other traps include such things as arithmetic exception traps (caused by the values of operands to arithmetic instructions), and bus-fault traps (caused by attempts to access physical addresses to which no physical memory is attached).
On some machines, there is an additional convention -- When an interrupt is requested, the current instruction is allowed to complete before the PC is saved and the interrupt service routine is entered. When a trap occurs, the current instruction is aborted and the trap service routine is entered directly.
For it to be possible to serve a page fault, the instruction must be aborted before it has any side effects, or (as on the PDP-11) all side effects must be recorded so that they can be undone by the trap service routine prior to any attempt to restart the instruction.
The exception to the above rule is on machines such as the Intel 8086 family, where some instructions are designed to be interruptable -- typically, this applies to block copy instructions. These instructions, if interrupted, save their state in CPU registers in such a way that they can be restarted from the point of interruption instead of restarting from the beginning.
On entry to the trap service routine, the saved PC is the address of the instruction that caused the trap
Before return, the trap service routine must adjust the page table so that re-executing the instruction that caused the trap will not cause the same page fault.
On the PDP-11, the saved PC was not the correct one, but sufficient information was saved about the partial exectuion of the instruction the the correct PC could be reconstructed by the trap service routine.
A single instruction can cause many page faults. Consider a memory to memory move double word instruction. The instruction itself will typically be more than one word long, and it may span a page boundary. Both the source and destination addresses may span page boundaries. Thus, an attempt to execute this single instruction might cause as many as 6 page faults.
Clearly, if there are fewer than 6 page frames on the machine, this instruction cannot be executed. In general, the instruction set of a virtual machine must be examined to determine the maximum number of pages a single instruction can execute, and then that number of page frames must be guaranteed.
Each entry to the page fault trap service routine must bring in one of the pages needed to complete an instruction. It need not bring in all of the required pages, since it is frequently faster to simply retry the instruction to cause the next fault than it is to use software to try to determine what other pages the instruction might need.