Virtual memory system
Mapping of the logical address space
In a virtual memory system, the logical address space of a process and its physical address space are totally dissociated.
The logical address space is sliced in different blocks.
The different blocks are allocated independently of each other.
So they can spread along the physical address space.
A process can be only partially resident in main memory.
So some of its blocks may be only in the swapping area.
Some features
Non-contiguity of the physical address space
The address spaces of the processes, divided into blocks of fixed or variable size, are dispersed throughout the memory, trying to guarantee a more efficient occupation of the available space.
No limitation of the address space of a process
Methodologies allowing the execution of processes whose address spaces are greater than the size of the available main memory can be established.
Swapping area as an extension of the main memory
Its role is to maintain an updated image of the address spaces of the processes that currently coexist, namely their variable part (static and dynamic definition areas and stack).
Logical address to physical address translation
How are dynamic mapping and dynamic protection accomplished?
A logical address is composed of two parts:
nblk – that identifies a specific logical block.
offset – that identifies a position within the block, as an offset from its beginning.
A block table, stored in memory, maps every logical block to its physical counterpart.
The MMU must deal with this structure.
The MMU must contain two pairs of base and limit registers.
one pair (BT) is related to the beginning and size of the block table, data structure describing the several blocks the logical address space is divided in.
the other pair (B) describes a specific block, the one that is being accessed.
On context switching, the dispatch operation loads those related to the block table, with the values stored in the PCT entry of the process scheduled for execution.
the BT base register represents the start address of the process block table.
the BT limit register represents the number of table entries (number of blocks).
Memory access unfolds into three steps.
Step 1
field nblk of the logical address is compared with BT limit register.
if it is valid (≤), the BT base register plus nblk points to the block table entry, which is loaded into the MMU.
if not (>), a null memory access (dummy cycle) is set in motion and an exception is generated due to address error.
Step 2
flag M/AS is evaluated.
if it is M (the block being referenced is in memory), the operation may proceed.
if not (the block being referenced is swapped out), a null memory access (dummy cycle) is set in motion and an exception is generated due to block fault.
Step 3
field offset of the logical address is compared with B limit register.
if it is valid (≤), the B base register plus offset points to the physical address.
if not (>), null memory access is set in motion and an exception is generated due to address error.
Analysis
The increase in versatility, introduced by the virtual memory system, has the cost of transforming each memory access into two accesses.
in the first, the process’ block table is accessed, to obtain the address of the beginning of the block in memory.
only in the second the specific memory position is accessed.
Conceptually, the virtual memory system results in a partitioning of the logical address space of the process in blocks that are dynamically treated as autonomous address sub-spaces in a contiguous memory allocation.
of fixed partitions, if the blocks are all the same size.
of variable partitions, if they can have different sizes.
What’s new is the possibility to access a block currently not resident in main memory.
with the consequent need to cancel the access and repeat it later, when the block is already loaded.
Role of the TLB
The need for this double access to memory can be minimized by taking advantage of the principle of locality of reference.
As the accesses will tend to be concentrated in a well-defined set of blocks during extended process execution time intervals, the memory management unit (MMU) usually keeps the content of the block table entries stored in an internal associative memory, called the translation lookaside buffer (TLB).
Thus, the first access can be a:
hit – when the entry is stored in the TLB, in which case the access is internal to the MMU.
miss – when the entry is not stored in the TLB, in which case there is access to the main memory.
The average access time to an instruction or operand tends to approximate the lowest value.
access to the TLB plus access to the main memory.
Long-term scheduling
When a process is created, the data structures to manage it is initialized.
Its logical address space is constructed, at least its variable part is put in the swapping area and its block table is organized.
Some blocks can be shared with other processes.
If there is space in main memory, at least its block table, first block of code and block of the its stack are loaded there, the corresponding entries in the block table are updated and the process is placed in the READY queue.
Otherwise, the process is placed in the SUSPENDED-READY queue.
Short-term scheduling
During its execution, on block fault, a process is placed in the BLOCKED state, while the faulty block is swapped in.
When the block is in memory, the process is placed in the READY state.
Medium-term scheduling
While READY or BLOCKED, all blocks of a process may be swapped out, if memory space is required.
While SUSPENDED-READY (or SUSPENDED-BLOCKED), if memory space becomes available, the block table and a selection of blocks of a process may be swapped in, and the process transitions to READY or BLOCKED.
the corresponding entries of the block table are updated.
A SUSPENDED-BLOCK process is only selected if no SUSPENDED-READY one exists.
When a process terminates, it may be swapped out (if not already there), waiting for the end of operations.
Block fault exception
A relevant property of the virtual memory system is the capacity of the computer system for executing processes whose address space is not in its entirety, and simultaneously, residing in main memory.
The operating system has to provide means to solve the problem of referencing an address located in a block that is not currently present in memory.
The MMU generates an exception in these circumstances and its service routine must start actions to swap in the block and, after its completion, repeat the execution of the instruction that produced the fault.
All these operations are carried out in a completely transparent way to the user who is not aware of the interruptions introduced in the execution of the process.
Block fault exception – service procedure
The context of the process is saved in the corresponding entry of the process control table, its state changes to BLOCKED, and the program counter is updated to the address that produced the block fault.
If memory space is available, a region is selected to swap in the missing block.
If not, an occupied block is selected to be replaced.
if this block was modified, it is transferred to the swapping area.
its entry in the block table is updated to indicate it is no longer in memory.
The swapping in of the missing block is started (to the selected region).
The dispatch function of the processor scheduler is called to put in execution one of the READY process.
When the transfer is concluded, the block table entry is updated and the process is put in the READY state.
Block fault exception – analysis
If, during its execution, a process was continuously generating block fault exceptions, the processing rate would be very slow and, in general, the throughput of the computer system would also be very low, jeopardizing the usefulness of an organization of virtual memory in multiprogramming.
In practice, this is not the case, because of the principle of locality of reference.
A process, whatever the stage of its execution, accesses during relatively extended periods of time only a small fraction of its logical address space.
This fraction naturally changes over time, but in each interval considered there are typically thousands of accesses that are made on well-defined fractions of its address space.
As long as the corresponding blocks are in memory, the rhythm of execution can proceed without the occurrence of block faults.
Last updated
