Popek and Goldberg virtualization requirements

Last updated

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". [1] 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.

Contents

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 called 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: [2]

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. [3]

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 some instructions of an ISA into 3 different groups:

Privileged instructions
Those that trap if the processor is in user mode and do not trap if it is in system mode (supervisor 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 the sensitive instructions. [4] [5]

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:

  1. it is virtualizable and
  2. 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, [4] which are sometimes called critical instructions. This additional processing however makes the VMM less efficient in theory, [5] but hardware traps have non-negligible performance cost as well.[ citation needed ] 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. [6] Effectively this gives a theorem with different sufficiency conditions.[ citation needed ]

Theorem 3. A hybrid VMM may be constructed for any third generation machine in which the set of user sensitive instructions are a subset of the set of privileged instructions:

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: 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.

Instruction sets of common architectures

This section presents some relevant architectures and how they relate to the virtualization requirements.

PDP-10

The PDP-10 architecture has a few instructions which are sensitive (alter or query the processor's mode) but not privileged. [7] These instructions save or restore the condition codes containing USER or IOT bits:

System/370

All sensitive instructions in the System/370 are privileged: it satisfies the virtualization requirements. [8]

Motorola MC68000

The Motorola MC68000 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. [9] [10]

IA-32 (x86)

The IA-32 instruction set of the Pentium processor contains 18 sensitive, unprivileged instructions. [11] They can be categorized in two groups:

The introduction of the AMD-V and Intel VT-x instruction sets in 2005 allows x86 processors to meet the Popek and Goldberg virtualization requirements.

IA-64

The effort needed to support virtualization on the IA-64 architecture is described in a 2000 article by Magenheimer and Christian. [12]

SPARC

A "hyperprivileged" mode for the UltraSPARC architecture was specified in UltraSPARC Architecture 2005.' [13] It defines a sun4v platform [14] which is a super-set of the sun4u platform, but is still compliant to the SPARC v9 Level-1 [15] specification.

PowerPC

All sensitive instructions in the PowerPC instruction set are privileged. [16] [17]

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 emulation 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. [18] Assists were added in several stages. In the end, there were over 100 assists on the late models System/370. [19]

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). [20]

Related Research Articles

<span class="mw-page-title-main">Motorola 68000</span> Microprocessor

The Motorola 68000 is a 16/32-bit complex instruction set computer (CISC) microprocessor, introduced in 1979 by Motorola Semiconductor Products Sector.

In computing, a virtual machine (VM) is the virtualization or emulation of a computer system. Virtual machines are based on computer architectures and provide the functionality of a physical computer. Their implementations may involve specialized hardware, software, or a combination of the two. Virtual machines differ and are organized by their function, shown here:

x86 Family of instruction set architectures

x86 is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was introduced in 1978 as a fully 16-bit extension of Intel's 8-bit 8080 microprocessor, with memory segmentation as a solution for addressing more memory than can be covered by a plain 16-bit address. The term "x86" came into being because the names of several successors to Intel's 8086 processor end in "86", including the 80186, 80286, 80386 and 80486 processors. Colloquially, their names were "186", "286", "386" and "486".

In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an implementation.

The Motorola 68000 series is a family of 32-bit complex instruction set computer (CISC) microprocessors. During the 1980s and early 1990s, they were popular in personal computers and workstations and were the primary competitors of Intel's x86 microprocessors. They were best known as the processors used in the early Apple Macintosh, the Sharp X68000, the Commodore Amiga, the Sinclair QL, the Atari ST and Falcon, the Atari Jaguar, the Sega Genesis, the Phillips CD-i, the Capcom System I (Arcade), the AT&T UNIX PC, the Tandy Model 16/16B/6000, the Sun Microsystems Sun-1, Sun-2 and Sun-3, the NeXT Computer, NeXTcube, NeXTstation, and NeXTcube Turbo, early Silicon Graphics IRIS workstations, computers from MASSCOMP, the Texas Instruments TI-89/TI-92 calculators, the Palm Pilot, the Control Data Corporation CDCNET Device Interface, and the Space Shuttle. Although no modern desktop computers are based on processors in the 680x0 series, derivative processors are still widely used in embedded systems.

A modern computer operating system usually segregates virtual memory into user space and kernel space. Primarily, this separation serves to provide memory protection and hardware protection from malicious or errant software behaviour.

Memory protection is a way to control memory access rights on a computer, and is a part of most modern instruction set architectures and operating systems. The main purpose of memory protection is to prevent a process from accessing memory that has not been allocated to it. This prevents a bug or malware within a process from affecting other processes, or the operating system itself. Protection may encompass all accesses to a specified area of memory, write accesses, or attempts to execute the contents of the area. An attempt to access unauthorized memory results in a hardware fault, e.g., a segmentation fault, storage violation exception, generally causing abnormal termination of the offending process. Memory protection for computer security includes additional techniques such as address space layout randomization and executable space protection.

A translation lookaside buffer (TLB) is a memory cache that stores the recent translations of virtual memory to physical memory. It is used to reduce the time taken to access a user memory location. It can be called an address-translation cache. It is a part of the chip's memory-management unit (MMU). A TLB may reside between the CPU and the CPU cache, between CPU cache and the main memory or between the different levels of the multi-level cache. The majority of desktop, laptop, and server processors include one or more TLBs in the memory-management hardware, and it is nearly always present in any processor that utilizes paged or segmented virtual memory.

In the 80386 microprocessor and later, virtual 8086 mode allows the execution of real mode applications that are incapable of running directly in protected mode while the processor is running a protected mode operating system. It is a hardware virtualization technique that allowed multiple 8086 processors to be emulated by the 386 chip. It emerged from the painful experiences with the 80286 protected mode, which by itself was not suitable to run concurrent real-mode applications well. John Crawford developed the Virtual Mode bit at the register set, paving the way to this environment.

x86 virtualization is the use of hardware-assisted virtualization capabilities on an x86/x86-64 CPU.

A hypervisor is a type of computer software, firmware or hardware that creates and runs virtual machines. A computer on which a hypervisor runs one or more virtual machines is called a host machine, and each virtual machine is called a guest machine. The hypervisor presents the guest operating systems with a virtual operating platform and manages the execution of the guest operating systems. Unlike an emulator, the guest executes most instructions on the native hardware. Multiple instances of a variety of operating systems may share the virtualized hardware resources: for example, Linux, Windows, and macOS instances can all run on a single physical x86 machine. This contrasts with operating-system–level virtualization, where all instances must share a single kernel, though the guest operating systems can differ in user space, such as different Linux distributions with the same kernel.

<span class="mw-page-title-main">Protection ring</span> Layer of protection in computer systems

In computer science, hierarchical protection domains, often called protection rings, are mechanisms to protect data and functionality from faults and malicious behavior.

CPU modes are operating modes for the central processing unit of some computer architectures that place restrictions on the type and scope of operations that can be performed by certain processes being run by the CPU. This design allows the operating system to run with more privileges than application software.

In computing, hardware-assisted virtualization is a platform virtualization approach that enables efficient full virtualization using help from hardware capabilities, primarily from the host processors. A full virtualization is used to emulate a complete hardware environment, or virtual machine, in which an unmodified guest operating system effectively executes in complete isolation. Hardware-assisted virtualization was added to x86 processors in 2005, 2006 and 2010 (respectively).

<span class="mw-page-title-main">Full virtualization</span> Computing technique involving instances of an environment

In computer science, full virtualization (fv) is a modern virtualization technique developed in late 1990s. It is different from simulation and emulation. Virtualization employs techniques that can create instances of a virtual environment, as opposed to simulation, which models the environment; and emulation, which replicates the target environment with certain kinds of virtual environments called emulation environments for virtual machines. Full virtualization requires that every salient feature of the hardware be reflected into one of several virtual machines – including the full instruction set, input/output operations, interrupts, memory access, and whatever other elements are used by the software that runs on the bare machine, and that is intended to run in a virtual machine. In such an environment, any software capable of execution on the raw hardware can be run in the virtual machine and, in particular, any operating systems. The obvious test of full virtualization is whether an operating system intended for stand-alone use can successfully run inside a virtual machine.

The Interrupt flag (IF) is a flag bit in the CPU's FLAGS register, which determines whether or not the (CPU) will respond immediately to maskable hardware interrupts. If the flag is set to 1 maskable interrupts are enabled. If reset such interrupts will be disabled until interrupts are enabled. The Interrupt flag does not affect the handling of non-maskable interrupts (NMIs) or software interrupts generated by the INT instruction.

Hardware virtualization is the virtualization of computers as complete hardware platforms, certain logical abstractions of their componentry, or only the functionality required to run various operating systems. Virtualization hides the physical characteristics of a computing platform from the users, presenting instead an abstract computing platform. At its origins, the software that controlled virtualization was called a "control program", but the terms "hypervisor" or "virtual machine monitor" became preferred over time.

Cross-platform virtualization is a form of computer virtualization that allows software compiled for a specific instruction set and operating system to run unmodified on computers with different CPUs and/or operating systems, through a combination of dynamic binary translation and operating system call mapping.

Robert P. Goldberg was an American computer scientist, known for his research on operating systems and virtualization.

In computing, a system virtual machine is a virtual machine (VM) that provides a complete system platform and supports the execution of a complete operating system (OS). These usually emulate an existing architecture, and are built with the purpose of either providing a platform to run programs where the real hardware is not available for use, or of having multiple instances of virtual machines leading to more efficient use of computing resources, both in terms of energy consumption and cost effectiveness, or both. A VM was originally defined by Popek and Goldberg as "an efficient, isolated duplicate of a real machine".

References

  1. Popek, G. J.; Goldberg, R. P. (July 1974). "Formal requirements for virtualizable third generation architectures". Communications of the ACM . 17 (7): 412–421. doi: 10.1145/361011.361073 . S2CID   12680060.
  2. Rogier Dittner, David Rule, The best damn server virtualization book period, Syngress, 2007, ISBN   1-59749-217-5, p. 19
  3. Smith and Nair, p. 387
  4. 1 2 Adams and Agesen, 2006, pp. 2-3
  5. 1 2 Smith and Nair, p. 391
  6. Adams and Agesen, p. 1 and 5
  7. S. W. Galley (1969). "PDP-10 Virtual machines". Proc. ACM SIGARCH-SIGOPS Workshop on Virtual Computer Systems. pp. 30–34.
  8. Smith and Nair, p. 395
  9. M68000 8-/16-32-Bit Microprocessor User's Manual, Ninth Edition. Phoenix, AZ, USA: Motorola, Inc. 1993.
  10. Motorola M68000 Family Programmer's Reference Manual. Phoenix, AZ, USA: Motorola, Inc. 1992.
  11. John Scott Robin and Cynthia E. Irvine (2000). "Analysis of the Intel Pentium's Ability to Support a Secure Virtual Machine Monitor". Proc. 9th USENIX Security Symposium.
  12. Daniel J. Magenheimer and Thomas W. Christian (2000). "vBlades: Optimized Paravirtualization for the Itanium Processor Family". Proc. 3rd Virtual Machine Research & Technology Symposium. USENIX. pp. 73–82.
  13. Weaver, David (2007-05-17). UltraSPARC Architecture 2005: One Architecture.... Multiple Innovative Implementations (DraftD0.9) (PDF). Santa Clara, CA, USA: Sun Microsystems, Inc. Archived from the original (PDF) on 2009-02-19.
  14. Sun Microsystems, Inc. (2006-01-24). UltraSPARC Virtual Machine Specification (PDF). Santa Clara, CA, USA. Archived from the original (PDF) on 2007-09-27.{{cite book}}: CS1 maint: location missing publisher (link)
  15. Weaver, David L.; Tom Germond (1994). The SPARC Architecture Manual: Version 9 . San Jose, CA, USA: SPARC International, Inc. ISBN   0-13-825001-4.
  16. "Virtualization: The elegant way and the x86 way – pagetable.com".
  17. Virtualization cs.cmu.edu
  18. Smith and Nair, p. 415-416 and 426
  19. Gum, p. 535
  20. Gum, p. 533
Notes