Formal Requirements for Virtualizable Third Generation Architectures – Popek & Goldberg 1974.
With thanks to Alfred Bratterud for pointing me at this paper.
What exactly is a virtual machine? What does a virtual machine monitor do? And how do we now whether a given piece of hardware can support virtualization or not? In today’s paper choice, Popek and Goldberg set out the answers for us – and by the way, they had all this figured out way back in 1974!
What is a Virtual Machine?
There are currently (1974) a number of viewpoints suggesting what a virtual machine is, how it ought to be constructed, and what hardware and operating system implications result…
Here’s a very simple definition of a virtual machine:
A virtual machine is taken to be an efficient, isolated duplicate of the real machine.
Though of course we need to dig further and understand what is implied by the three words efficient, isolated, and duplicate. To explain these, the authors introduce the notion of a virtual machine monitor…
What is a Virtual Machine Monitor?
A virtual machine monitor (VMM) does three things:
- It provides a duplicate, or essentially identical to the original machine, environment for programs. “Any program run under the VMM should exhibit an effect identical with that demonstrated if the program had been run on the original machine directly, with the possible exception of differences caused by the availability of system resources and differences caused by timing dependencies.”
- It does so efficiently, requiring “a statistically dominant subset of the virtual processor’s instructions be executed directly by the real processor, with no software intervention by the VMM. This statement rules out traditional emulators and complete software interpreters (simulators) from the virtual machine umbrella.” Thus programs that run in this environment show only minor decreases in speed.
- It is in complete control of system resources (memory, peripherals, and the like). This requires two conditions: (i) it must not be possible for a program running in the created environment to access any resource not allocated to it (isolation), and (ii) it is possible under certain circumstances to regain control of resources already allocated.
A virtual machine is the environment created by the virtual machine monitor.
Does my Hardware Support Virtualization?
This is the question the vast majority of the paper is dedicated to. Before we can get to the answer (which is actually a very simple and easy test), we need to understand what the authors mean by a ‘third generation architecture’ (per the paper title).
Examples of a third generation architecture machine are the IBM 360, Honeywell 6000, or DEC PDP-10. Such machines have a processor, and linear uniformly addressable memory. The processor can operate in supervisor mode, or in user mode. Some instructions are only available in supervisor mode. Memory addressing is done relative to a relocation register R=(l,b) which is always active. The location parameter l gives the absolute address that corresponds to the apparent address zero, and the bounds parameter b gives the absolute size of the virtual memory. Suppose an instruction produces some address a, we check and then find the true address as follows:
if a + l >= total-real-memory-size then
// out of real memory bounds
memorytrap
else if a >= b then
// out of virtual memory bounds
memorytrap
else
use address a+l
The program status word PSW is a triplet (mode – user/supervisor, program counter, relocation register), and the overall state S of the machine can be modeled as (E,PSW) where E is the executable storage. E[0] and E[1] are used to store an old-PSW and fetch a new PSW respectively. Instructions are simply modeled as a function from State -> State.
In this model, for simplicity, we have departed slightly from most common relocation systems by assuming it to be active in the supervisor as well as user mode. This difference will not be important to the proof of our result. Note also that all references made by the processor to memory are assumed to be relocated.
A trap, such as the memorytrap above, automatically saves the current state of the machine and passes control to a pre-specified control routine by changing the PSW to the values specified in E[1].
Key to understand whether or not it is possible to virtualize a given piece of hardware is to divide the instructions into groups. In particular, privileged instructions are those that do not trap when the processor is in supervisor mode, but do trap (a privileged instruction trap) when in user mode.
Privileged instructions are independent of the virtualization process. They are merely characteristics of the machine which may be determined from reading the principles of operation. Note, however, that the way we have defined privileged instructions requires them to trap. Merely NOPing the instruction without trapping is insufficient. The latter case should not be called a privileged instruction; maybe “user mode NOP” would be more accurate.
Sensitive instructions may be either control sensitive, or behaviour sensitive. Control sensitive instructions are those that affect or can affect control over system resources – in our simplified model the only such resource is memory. A control sensitive instruction attempts to change the amount of resource (memory) available, or change processor mode, without going through a memory trap. A behaviour sensitive instruction is one whereby the effect of its execution is dependent on the value of the relocation bounds register (location in real memory) or processor mode. An instruction that is not sensitive is innocuous.
A virtual machine monitor is a control program comprising a dispatcher, an allocator, and a set of interpreters, one per privileged instruction. The location of the control program (dispatcher) is placed in the program counter at E[1], it directs execution to the allocator or interpreters as needed. The allocator decides what system resources are to be provided (e.g. keeping the VMM and VM memory separate).
The allocator will be invoked by the dispatcher whenever an attempted execution of a privileged instruction in a virtual machine environment occurs which would have the effect of changing the machine resources associated with that environment. Attempting to reset the R (relocation-bounds) register is the primary example in our skeletal model. If the processor were to be treated as a resource, a halt would be another.
The job of the interpreters is to simulate the instruction that trapped.
A virtual machine monitor [that satisfies the three properties of efficiency, resource control, and equivalence] may be constructed if the set of sensitive instructions for that computer is a subset of the privileged instructions.
The proof of this statement is given in the paper and the appendices – it rests on showing a one-one homomorphism f between real machine states and virtual machine states, and that if the real machine halts in state S, then the virtual machine halts in state f(S). The final step is an existence argument (i.e. there is at least one way) to build the privileged instruction interpreters – using a lookup table.
Furthermore, recursive virtualization (a VM that runs a copy of itself under the VMM) is possible if (a) a VMM can be constructed for the hardware as above, and (b) the VMM does not have any timing dependencies.
The theorem provides a fairly simple condition sufficient to guarantee virtualizability, assuming, of course, that the requisite features of “conventional third generation machines” are present. However, those features which have been assumed are fairly standard ones, so the relationship between the sets of sensitive and privileged instructions is the only constraint. It is a very modest one, easy to check. Further, it is also a simple matter for hardware designers to use as a design requirement.