With VM celebrating 45 years as an IBM product, it's a good time to look at the history of virtualization technology. Everyone seems to want to take credit for something IBM invented and brought to maturity about 50 years ago. In this two part article, we will chronical the key milestones in the development of virtualization technology on the IBM mainframe. Certainly, VM people will find this history interesting but even z/OS people should enjoy the evolution of technology that has led, not only to zVM, but also PR/SM which is integral to every mainframe system
The history of virtualization, in the sense of VMs, can be divided into two phases:
VM technology was brought to maturity in a “big bang” with the CP-67 hypervisor on the S/360 Model 67 processor
In the following 50 years, more of the simulation provided by CP-67 has been replaced with emulation by hardware and microcode/millicode
Necessity Is the Mother of Invention
In the early ‘60s, there grew the need for multiple user to have access to a computer at the same time. Since most programs spend most of the time waiting for data to be read or written, there was enough compute power for several simultaneous programs. However, memory was in short supply—it was insufficient to support a large number of concurrent users on a system. At the time, the memory technology was ferrite cores. Each bit was a ferrite "donut" with three wires threaded through it by hand. A bit of memory was not only big enough to see with the naked eye, but was actually large enough to hold between your fingers. Memory was astoundingly expensive. It was the time-sharing environment that really drove the demand to virtualize memory so that, in a sense, the real memory could be time-shared by many users.
At that time, IBM, wanting to get into the time-sharing market, started a research project that proved historically important: Creating a program called CP-40. CP-40 was developed on and for the IBM S/360 model 40. It supported up to 14 guest VMs, each with 256K of virtual memory. To accommodate memory virtualization, a model 40 was augmented with address translation hardware, called the Cambridge Address Translator (CAT) Box.
The CAT Box contained an array of 64 associative memory registers to translate from a virtual address known to the guest to an address within a 4K frame of real memory. If a translation wasn’t available, the CAT Box would raise an exception indicating that the 4K page containing the guest virtual address wasn’t currently backed by any real frame. In this case, the CP-40 software would read the 4K of data comprising the virtual page from auxiliary disk storage into an available real frame, update the array and resume the guest program. In this way, a multiplicity of guests, each believing they have 256K of memory, in fact were all sharing a single 256K of real memory.
The associate registers also contain reference and change bits maintained by the hardware. CP-40 used these bits to determine which pages to “steal” from real memory based on a least-recently-used (LRU) algorithm. It would also know if a stolen page needed to be written to auxiliary disk storage if it had been changed since the last time it were written out.
Virtual memory not only makes it appear that there’s more memory, but also eliminates the memory fragmentation problem faced by all multitasking real memory systems. For example, OS/MVT needed to provide a contiguous block of real memory for each running job, the amount being specified on a JCL statement. Even if there was enough total free memory to meet a jobs requirements, the job might still be unable to run because no single chunk of memory was large enough. Some of the advantages, from an application perspective of virtualizing memory, were the avoidance of complex overlay structures. It was believed that the cost of programming rises exponentially as the limit of available memory is approached. Providing abundant virtual memory could neutralize this trend. Also, it enabled the running of a single version of a program on configurations that had varying amounts of real memory. The less actual real memory on the system, the slower the program would run due to paging, but it could run unmodified.
Two Industry-Changing Ideas
In addition to providing a virtual memory mechanism, the researchers also came up with a unique and, in retrospect, wonderful design concept. This was “the bifurcation of computer resource management and user support,” according to “The Origin of the VM/370 Time-sharing System” Along with CP-40 they developed a single-user OS called the Cambridge Monitor System (CMS), which provided an environment for running applications and interacting with users. CMS was originally developed as a stand-alone OS that could run on real hardware or as a guest of CP-40. Later it was optimized for the virtual environment and can no longer run on bare hardware. Because it was a relatively simple, single-user OS, it can be viewed as the progenitor of the PC before technology enabled the production of reasonably priced personal computers or workstations.
Virtual Supervisor State
The S/360 architecture has an attribute that makes it amenable to the kind of virtualization embodied in CP-40 and all it progeny up to today’s z/VM and PR/SM. That is, there are two execution modes: supervisor state and problem program state, and the difference is that instructions that can change the state of the system require supervisor state. The instructions typically used by application could execute in problem state. No problem state instructions behaved differently in supervisor state. This clear differentiation made it possible for CP-40 to run its guests in problem state and gain control whenever the guest attempted an instruction requiring supervisor state. When such an interruption occurred, CP-40 would simulate the supervisor state instruction within the context of the guest VM. Most guest instructions executed at full speed, while an occasional supervisory instruction of the guest OS (e.g., CMS) experienced the overhead of simulation by CP-40.
CP-67 and the Model 67
CP-40 was updated to become CP-67, which was made available to customers basically as freeware. CP-67 took advantage of some enhanced features of the Model 67 which supported both 24-bit and 32-bit addressing. The Model 67 supported address translation tables that resided in memory, almost identical to the scheme used by current processors.
To reduce the overhead of accessing the translation tables for every translation, the Model 67 had an array of 8 associative registers to remember the most recent translations for data accesses. It also had an additional register to remember the translation for the current instruction address. They were called the Dynamic Look-aside Table but now we call it a Translation Lookaside Buffer (TLB). Today, TLBs—of which there are several in modern mainframes—can have as many as 1024 registers in a 4-way associative array of 256 rows.
The Model 67 also had hardware to reflect reference and/or change of a real memory frame. The Model 67 augmented the 5-bit storage key of the base S/360 architecture with two additional bits. They indicated whether a frame had been referenced or changed since the last time the bits were reset. This enabled CP-67 to implement a LRU page replacement algorithm and avoid rewriting pages that had not been changed. Modern OSes still use variants of LRU page replacement algorithms today.
The Model 67 also had a control register that was used to locate the translation tables used for translating the virtual addresses for a guest. This register provided a means to support a large number of guests compared to the mere 14 guest supported by the CP-40 prototype. CP-67 would loaded this control register with the address of a guest’s translation tables in memory whenever that guest was dispatched on the CPU. As more real memory became available, the number of guest VMs wasn’t limited by an architectural constraint.
The enhanced architecture of the Model 67 also enable CP-67 to implement a capability not provided by CP-40. Although CP-40 provided an S/360 VM to its guests, it didn't support guests which themselves defined virtual memory. CP-67 did support guest use of virtual storage. In fact, CP-67 could itself run on top of CP-67 in a VM. The hardware supported only one level of translation so that CP-67 had to use the trick of “shadow translation tables.” These tables were built by CP-67 to provide the composite translation of guest virtual address to guest real address and then to host real addresses. CP-67 built shadow translation tables “on the fly” as the guest accessed and later invalidated guest virtual memory.
Virtual I/O
Performing guest I/O operations in a virtual environment presents both challenges and opportunities. For a CP-67 guest to perform I/O, some simulation was required. The original S/360 architecture required that all the memory addressed used by the I/O channels needed to be real addresses. The channels, unlike the CPUs, didn’t translate guest addresses to actual hardware real addresses. CP-67 needed to do these translations before commands could be sent to the I/O channels. The device address as known to the guest could also be translated to an actual real device address and the location of data on a disk could also be translated.
This latter translation allowed for the creation of what was called minidisks. A minidisk is only part of a physical disk but appears to be a separate disk to the guest. For example, a disk with 1,000 cylinders could be carved up into 100 minidisks of 10 cylinders each and could be used by 100 CMS interactive users to store various types of data specific to themselves.
Virtualization Expands
In this short space, we can’t cover all aspect of processor virtualization, yet we see that most of the fundamental concepts of virtual systems already had appeared in the Model 67 and CP-67, a sort of Cambrian Explosion for virtualization.
Without a great deal of fundamental change, CP-67 was transformed into VM/370 as an IBM program product to run on the then new S/370 line of processors. From that descended both the current z/VM and PR/SM. In a subsequent article, we will cover the following 50 years of innovative optimization that has made virtualization not yet commonplace but mandatory on the IBM mainframe.