Popek and Goldberg virtualization requirements
Encyclopedia
The Popek and Goldberg virtualization requirements are a set of conditions sufficient for a computer architecture to support system virtualization
efficiently. They were introduced by Gerald J. Popek
and Robert P. Goldberg in their 1974 article "Formal Requirements for Virtualizable Third Generation Architectures". Even though the requirements are derived under simplifying assumptions, they still represent a convenient way of determining whether a computer architecture supports efficient virtualization and provide guidelines for the design of virtualized computer architectures.
A virtual machine monitor (VMM, also sometimes called a hypervisor
) is the piece of software that provides the abstraction of a virtual machine. There are three properties of interest when analyzing the environment created by a VMM:
Equivalence / Fidelity : A program running under the VMM should exhibit a behavior essentially identical to that demonstrated when running on an equivalent machine directly.
Resource control / Safety : The VMM must be in complete control of the virtualized resources.
Efficiency / Performance: A statistically dominant fraction of machine instructions must be executed without VMM intervention.
In the terminology of Popek and Goldberg, a VMM must present all three properties. In the terminology used in the reference book of Smith and Nair (2005), VMMs are typically assumed to satisfy the equivalence and resource control properties, and those additionally meeting the performance property are called efficient VMMs.
Popek and Goldberg describe the characteristics that the Instruction Set Architecture (ISA) of the physical machine must possess in order to run VMMs which possess the above properties.
Their analysis derives such characteristics using a model of "third generation architectures" (e.g., IBM 360, Honeywell 6000, DEC PDP-10) that is nevertheless general enough to be extended to modern machines. This model includes a processor that operates in either system or user mode, and has access to linear, uniformly addressable memory. It is assumed that a subset of the instruction set is available only when in system mode and that memory is addressed relative to a relocation register. I/O and interrupts are not modelled.
Privileged instructions : Those that trap
if the processor is in user mode and do not trap if it is in system mode.
Control sensitive instructions : Those that attempt to change the configuration of resources in the system.
Behavior sensitive instructions : Those whose behavior or result depends on the configuration of resources (the content of the relocation register or the processor's mode).
The main result of Popek and Goldberg's analysis can then be expressed as follows.
Theorem 1. For any conventional third-generation computer, an effective VMM may be constructed if the set of sensitive instructions for that computer is a subset of the set of privileged instructions.
Intuitively, the theorem states that to build a VMM it is sufficient that all instructions that could affect the correct functioning of the VMM (sensitive instructions) always trap and pass control to the VMM. This guarantees the resource control property. Non-privileged instructions must instead be executed natively (i.e., efficiently). The holding of the equivalence property also follows.
This theorem also provides a simple technique for implementing a VMM, called trap-and-emulate virtualization, more recently called classic virtualization: because all sensitive instructions behave nicely, all the VMM has to do is trap and emulate every one of them.
A related problem is that of deriving sufficient conditions for recursive virtualization, that is, the conditions under which a VMM that can run on a copy of itself can be built. Popek and Goldberg present the following (sufficient) conditions.
Theorem 2. A conventional third-generation computer is recursively virtualizable if
Some architectures, like the non-hardware-assisted x86, do not meet these conditions, so they cannot be virtualized in the classic way. But architectures can still be fully virtualized (in the x86 case meaning at the CPU and MMU level) by using different techniques like binary translation, which replaces the sensitive instructions that do not generate traps, which are sometimes called critical instructions. This additional processing however makes the VMM less efficient in theory, but hardware traps have non-negligible performance cost as well, and a well-tuned caching binary translation system may achieve comparable performance, and it does in the case of x86 binary translation relative to first generation x86 hardware assist, which merely made sensitive instructions trappable. Effectively this gives a theorem with different sufficiency conditions.
The virtualization of such architectures requires correct handling of critical instructions, i.e., sensitive but unprivileged instructions. One approach, known as patching, adopts techniques commonly used in dynamic recompilation
: critical instructions are discovered at run-time and replaced with a trap into the VMM. Various mechanisms, such as the caching of emulation code or hardware assists, have been proposed to make the patching process more efficient. A different approach is that of paravirtualization
, which requires guest operating systems to be modified (ported) before running in the virtual environment.
architecture has a few instructions which are sensitive (alter or query the processor's mode) but not privileged. These instructions save or restore the condition codes containing USER or IOT bits:
are privileged: it satisfies the virtualization requirements.
has a single unprivileged sensitive instruction:
This instruction is sensitive because it allows access to the entire status register, which includes not only the condition codes
but also the user/supervisor bit, interrupt level, and trace control. In most later family members, starting with the MC68010
, the MOVE from SR instruction was made privileged, and a new MOVE from CCR instruction was provided to allow access to the condition code register only.
instruction set of the Pentium processor contains 17 sensitive, unprivileged instructions. They can be categorized in two groups:
In 2005, some x86 manufacturers made some x86 processors that meet the Popek and Goldberg virtualization requirements—processors with the AMD-V or Intel VT-x extensions.
architecture was specified in UltraSPARC Architecture 2005.' It defines a sun4v platform which is a super-set of the sun4u platform, but is still compliant to the SPARC v9 Level-1 specification.
software. Unfortunately, even on an architecture that meets Popek and Goldberg's requirements, the performance of a virtual machine can differ significantly from the actual hardware. Early experiments performed on the System/370 (which meets the formal requirements of Theorem 1) showed that performance of a virtual machine could be as low as 21% of the native machine in some benchmarks. The cost of trapping and emulating privileged instructions in the VMM can be significant. This led the IBM engineers to introduce a number of hardware assists, which roughly doubled the performance of the System/370 virtual machines. Assists were added in several stages. In the end, there were over 100 assists on the late models System/370.
One of the main driving factors for the development of hardware assists for the System/370 was virtual memory itself. When the guest was an operating system that itself implemented virtual memory, even non-privileged instructions could experience longer execution times - a penalty imposed by the requirement to access translation tables not used in native execution (see shadow page tables).
Full virtualization
In computer science, full virtualization is a virtualization technique used to provide a certain kind of virtual machine environment, namely, one that is a complete simulation of the underlying hardware...
efficiently. They were introduced by Gerald J. Popek
Gerald J. Popek
Gerald John "Jerry" Popek was an American computer scientist, known for his research on operating systems and virtualization.With Robert P...
and Robert P. Goldberg in their 1974 article "Formal Requirements for Virtualizable Third Generation Architectures". Even though the requirements are derived under simplifying assumptions, they still represent a convenient way of determining whether a computer architecture supports efficient virtualization and provide guidelines for the design of virtualized computer architectures.
VMM definition
System virtual machines are capable of virtualizing a full set of hardware resources, including a processor (or processors), memory and storage resources and peripheral devices.A virtual machine monitor (VMM, also sometimes called a hypervisor
Hypervisor
In computing, a hypervisor, also called virtual machine manager , is one of many hardware virtualization techniques that allow multiple operating systems, termed guests, to run concurrently on a host computer. It is so named because it is conceptually one level higher than a supervisory program...
) is the piece of software that provides the abstraction of a virtual machine. There are three properties of interest when analyzing the environment created by a VMM:
Equivalence / Fidelity : A program running under the VMM should exhibit a behavior essentially identical to that demonstrated when running on an equivalent machine directly.
Resource control / Safety : The VMM must be in complete control of the virtualized resources.
Efficiency / Performance: A statistically dominant fraction of machine instructions must be executed without VMM intervention.
In the terminology of Popek and Goldberg, a VMM must present all three properties. In the terminology used in the reference book of Smith and Nair (2005), VMMs are typically assumed to satisfy the equivalence and resource control properties, and those additionally meeting the performance property are called efficient VMMs.
Popek and Goldberg describe the characteristics that the Instruction Set Architecture (ISA) of the physical machine must possess in order to run VMMs which possess the above properties.
Their analysis derives such characteristics using a model of "third generation architectures" (e.g., IBM 360, Honeywell 6000, DEC PDP-10) that is nevertheless general enough to be extended to modern machines. This model includes a processor that operates in either system or user mode, and has access to linear, uniformly addressable memory. It is assumed that a subset of the instruction set is available only when in system mode and that memory is addressed relative to a relocation register. I/O and interrupts are not modelled.
Virtualization theorems
To derive their virtualization theorems, which give sufficient (but not necessary) conditions for virtualization, Popek and Goldberg introduce a classification of instructions of an ISA into 3 different groups:Privileged instructions : Those that trap
Trap (computing)
In computing and operating systems, a trap, also known as an exception or a fault, is typicallyThere is a wide variation in the nomenclature...
if the processor is in user mode and do not trap if it is in system mode.
Control sensitive instructions : Those that attempt to change the configuration of resources in the system.
Behavior sensitive instructions : Those whose behavior or result depends on the configuration of resources (the content of the relocation register or the processor's mode).
The main result of Popek and Goldberg's analysis can then be expressed as follows.
Theorem 1. For any conventional third-generation computer, an effective VMM may be constructed if the set of sensitive instructions for that computer is a subset of the set of privileged instructions.
Intuitively, the theorem states that to build a VMM it is sufficient that all instructions that could affect the correct functioning of the VMM (sensitive instructions) always trap and pass control to the VMM. This guarantees the resource control property. Non-privileged instructions must instead be executed natively (i.e., efficiently). The holding of the equivalence property also follows.
This theorem also provides a simple technique for implementing a VMM, called trap-and-emulate virtualization, more recently called classic virtualization: because all sensitive instructions behave nicely, all the VMM has to do is trap and emulate every one of them.
A related problem is that of deriving sufficient conditions for recursive virtualization, that is, the conditions under which a VMM that can run on a copy of itself can be built. Popek and Goldberg present the following (sufficient) conditions.
Theorem 2. A conventional third-generation computer is recursively virtualizable if
- it is virtualizable and
- a VMM without any timing dependencies can be constructed for it.
Some architectures, like the non-hardware-assisted x86, do not meet these conditions, so they cannot be virtualized in the classic way. But architectures can still be fully virtualized (in the x86 case meaning at the CPU and MMU level) by using different techniques like binary translation, which replaces the sensitive instructions that do not generate traps, which are sometimes called critical instructions. This additional processing however makes the VMM less efficient in theory, but hardware traps have non-negligible performance cost as well, and a well-tuned caching binary translation system may achieve comparable performance, and it does in the case of x86 binary translation relative to first generation x86 hardware assist, which merely made sensitive instructions trappable. Effectively this gives a theorem with different sufficiency conditions.
Handling critical instructions
The conditions for ISA virtualization expressed in Theorem 1 may be relaxed at the expense of the efficiency property. VMMs for non-virtualizable ISAs (in the Popek and Goldberg's sense) have routinely been built.The virtualization of such architectures requires correct handling of critical instructions, i.e., sensitive but unprivileged instructions. One approach, known as patching, adopts techniques commonly used in dynamic recompilation
Dynamic recompilation
In computer science, dynamic recompilation is a feature of some emulators and virtual machines, where the system may recompile some part of a program during execution...
: critical instructions are discovered at run-time and replaced with a trap into the VMM. Various mechanisms, such as the caching of emulation code or hardware assists, have been proposed to make the patching process more efficient. A different approach is that of paravirtualization
Paravirtualization
In computing, paravirtualization is a virtualization technique that presents a software interface to virtual machines that is similar but not identical to that of the underlying hardware....
, which requires guest operating systems to be modified (ported) before running in the virtual environment.
Instruction sets of common architectures
This section presents some relevant architectures and how they relate to the virtualization requirements.PDP-10
The PDP-10PDP-10
The PDP-10 was a mainframe computer family manufactured by Digital Equipment Corporation from the late 1960s on; the name stands for "Programmed Data Processor model 10". The first model was delivered in 1966...
architecture has a few instructions which are sensitive (alter or query the processor's mode) but not privileged. These instructions save or restore the condition codes containing USER or IOT bits:
- JSR: jump to subroutine
- JSP: jump and save program counter
- PUSHJ: push down and jump
- JRST: jump and restore
System/370
All sensitive instructions in the System/370System/370
The IBM System/370 was a model range of IBM mainframes announced on June 30, 1970 as the successors to the System/360 family. The series maintained backward compatibility with the S/360, allowing an easy migration path for customers; this, plus improved performance, were the dominant themes of the...
are privileged: it satisfies the virtualization requirements.
Motorola MC68000
The Motorola MC68000Motorola 68000
The Motorola 68000 is a 16/32-bit CISC microprocessor core designed and marketed by Freescale Semiconductor...
has a single unprivileged sensitive instruction:
- MOVE from SR
This instruction is sensitive because it allows access to the entire status register, which includes not only the condition codes
Status register
A status register or flag register is a collection of flag bits for a processor. An example is the FLAGS register of the x86 architecture....
but also the user/supervisor bit, interrupt level, and trace control. In most later family members, starting with the MC68010
Motorola 68010
The Motorola MC68010 processor is a 16/32-bit microprocessor from Motorola, released in 1982. In line with the Motorola 68000 naming convention, it is usually just referred to as the 010 ....
, the MOVE from SR instruction was made privileged, and a new MOVE from CCR instruction was provided to allow access to the condition code register only.
IA-32 (x86)
The IA-32IA-32
IA-32 , also known as x86-32, i386 or x86, is the CISC instruction-set architecture of Intel's most commercially successful microprocessors, and was first implemented in the Intel 80386 as a 32-bit extension of x86 architecture...
instruction set of the Pentium processor contains 17 sensitive, unprivileged instructions. They can be categorized in two groups:
- Sensitive register instructions: read or change sensitive registers and/or memory locations such as a clock register or interrupt registers:
- SGDT, SIDT, SLDT
- SMSW
- PUSHF, POPF
- Protection system instructions: reference the storage protection system, memory or address relocation system:
- LAR, LSL, VERR, VERW
- POP
- PUSH
- CALL, JMP, INT n, RET
- STR
- MOV
In 2005, some x86 manufacturers made some x86 processors that meet the Popek and Goldberg virtualization requirements—processors with the AMD-V or Intel VT-x extensions.
IA-64
The effort needed to support virtualization on the IA-64 architecture is described in a 2000 article by Magenheimer and Christian.SPARC
A "hyperprivileged" mode for the UltraSPARCUltraSPARC
The UltraSPARC is a microprocessor developed by Sun Microsystems who is now a part of Oracle Corporation and fabricated by Texas Instruments that implements the SPARC V9 instruction set architecture . It was introduced in mid-1995. It was the first microprocessor from Sun Microsystems to implement...
architecture was specified in UltraSPARC Architecture 2005.' It defines a sun4v platform which is a super-set of the sun4u platform, but is still compliant to the SPARC v9 Level-1 specification.
Performance in practice
The efficiency requirement in Popek and Goldberg's definition of a VMM concerns only the execution of non-privileged instructions, which must execute natively. This is what distinguishes a VMM from the more general class of hardware emulationEmulator
In computing, an emulator is hardware or software or both that duplicates the functions of a first computer system in a different second computer system, so that the behavior of the second system closely resembles the behavior of the first system...
software. Unfortunately, even on an architecture that meets Popek and Goldberg's requirements, the performance of a virtual machine can differ significantly from the actual hardware. Early experiments performed on the System/370 (which meets the formal requirements of Theorem 1) showed that performance of a virtual machine could be as low as 21% of the native machine in some benchmarks. The cost of trapping and emulating privileged instructions in the VMM can be significant. This led the IBM engineers to introduce a number of hardware assists, which roughly doubled the performance of the System/370 virtual machines. Assists were added in several stages. In the end, there were over 100 assists on the late models System/370.
One of the main driving factors for the development of hardware assists for the System/370 was virtual memory itself. When the guest was an operating system that itself implemented virtual memory, even non-privileged instructions could experience longer execution times - a penalty imposed by the requirement to access translation tables not used in native execution (see shadow page tables).