08
`(11) Patent Number:
`5,553,291
`United States Patent
`Tanakaet al.
`[45] Date of Patent:
`Sep. 3, 1996
`
`
`[54] VIRTUAL MACHINE CONTROL METHOD
`AND VIRTUAL MACHINE SYSTEM
`
`[75]
`
`Inventors: Shunji Tanaka, Sagamihara; Hidenori
`Umeno, Hadano; Nobuyoshi Sugama,
`Chigasaki; Masaru Sato, Izumi-ku,all
`of Japan
`.
`.
`.
`[73] Assignee: Hitachi, Ltd., Tokyo, Japan
`
`4,964,035 10/1990 Aoyama et dl. oes 364/200
`..
`... 395/400
`5,088,031
`2/1992 Takasaki et al.
`
`7/1992 Yamagata et ab. owe 395/400
`5,129,071
`FOREIGN PATENT DOCUMENTS
`
`Japan .
`57-212680 12/1982
`Japan .
`64-54542
`3/1989
`Primary Examiner—Kevin A. Kriess
`Attorney, Agent, or Firm—Fay, Sharpe, Beall, Fagan, Min-
`nich & McKee
`ABSTRACT
`[57]
`[21] Appl. No.: 120,472
`A virtual machine control method for a supercomputer
`[22]
`Filed:
`Sep. 14, 1993
`enables a plurality of virtual machines to use a vector
`[30]
`Foreign Application Priority Data
`processor. Control of the use of the vector processor is
`through the scalar processor. When a virtual machine
`Sep. 16,1992
`[JP]
`Japan acsestsseeneneenses 4-246730
`
`(51D Tint, Co anneeeassscaseesscntnneesanseeensene GO6F 9/44—requires use of the vector processor, il is first determined
`[52] US. C1. acccccccsscsssscseeussssssseessen 395/700; 364/DIG. 1;|whether oneofthe other virtual machines operating systems
`364/280; 364/232.1; 364/232.21; 395/406;
`is using the vector processor. If not, the scalar processoris
`395/800
`dispatched to the operating system requesting use of the
`[58] Field of Search ....sncssensnnensneen 395/700, 800,|Vector processor. If another virtual machine operating sys-
`395/325
`tem is using the vector processor, then the operating system
`requesting use of the vector processor is placed in a wait
`state until the vector processor becomes free, whereupon the
`scalar processor is dispatched to the operating system that
`had been in the wait state. The condition of the vector
`Processor being free can be communicated directly to the
`scalar processor without the intervention of the virtual
`machine monitor.
`
`[56]
`
`References Cited
`
`U.S, PATENT DOCUMENTS
`7/1984 Kaneda ct al. caermmneenrneee 364/200
`4,459,661
`9/1988 Miyadera etal.
`.. 364/200
`4,769,770
`4,787,026 11/1988 Barneset al.
`.....
`... 364/200
`4,812,967
`3/1989 Hirosawaetal.
`.. 364/200
`4,912,628
`3/1990 Briggs ......csescsescseesesescesness 364/200
`
`
`
`33 Claims, 12 Drawing Sheets
`
`100
`
`INSTRUCTION!
`
`VECTOR
`ADDRESS
`EXECUTION
`
`
`
`INSTRUCTION
`TRANS-
`UNIT
`
`
`
`
`EXECUTION
`LATION
`
`
`
`UNIT
`UNIT
`INTER-
`
`
`
`
`RUPTION
`
`EXECUTION
`UNIT
`
`
`
`
`
`
`
`
`400
`
`VIRTUAL MACHINE
`MONITOR
`
`
`MAIN
`MEMORY
`
`
`440
`
`450
`
`VM-1
`
`VIRTUAL
`
`SPACE
`
`
`VM-2
`VIRTUAL
`SPACE
`
`\
`
`\
`
`\
`
`
`
`
`Google Exhibit 1035
`Google Exhibit 1035
`Google v. Valtrus
`Google v. Valtrus
`
`

`

`U.S. Patent
`
`Sep. 3, 1996
`
`Sheet 1 of 12
`
`5,553,291
`
`100
`
`220
`
`200,
`
`VECTOR PROCESSOR
`
`
`ADDRESS
`EXECUTION
`UNIT
`TRANS-
`
`LATION
`
`EXECUTION
`UNIT
`
`4o0<
`
`GAA
`
`MAIN
`MEMORY
`
`VIRTUAL MACHINE
`MONITOR
`
`410
`
`SPACE
`
`450
`
`\
`
`\N
`
`VM-2
`VIRTUAL
`
`UNIT
`
`
`
`440
`
`GLA
`
`VM-1
`VIRTUAL
`SPACE
`
`

`

`U.S. Patent
`
`Sep.3, 1996
`
`Sheet 2 of 12
`
`5,553,291
`
`FIG. 2
`
`FROM 210
`
`I
`
`221 ADDRESS CROSS
`MAPPING TABLE
`
`9990 ADDRESS
`
`—=
`
`229
`
`S TRANSLATION 225
`
`TO 210
`
`

`

`U.S. Patent
`
`Sep. 3, 1996
`
`Sheet 3 of 12
`
`5,553,291
`
`SET WAIT STATE
`
`DISPATCH
`
`
`
`
`
`
`STATE
`
`
`TIME SLICE
`
`
`
`
`
`VPUNUSED: VPBUSY
`
`VP WAIT
`STATE
`
`

`

`U.S. Patent
`
`Sep. 3, 1996
`
`Sheet 4 of 12.
`
`5,553,291
`
`FIG. 4(A)
`
`sooa
`
`IS THERE A VIRTUAL MACHINE INA
`READY STATE?
`
`SELECT READY STATE VIRTUAL
`MACHINE
`
`TO FIG 4(B)
`
`4020
`
`DOES SELECTED VIRTUAL MACHINE
`USE VECTOR PROCESSOR?
`
`
`STEP 4050
`
`
`
`
`
`
`IS ANOTHER VIRTUAL MACHINE
`USING VECTOR PROCESSOR?
`
`YES
`
`NO
`
`-
`
`4040
`
`GIVE SP TO SELECTED VIRTUAL
`MACHINE AND START IT
`
`CONTINUE RUNNING
`
`4042
`
`—-<TRoFtesu=
`
`4046
`
`YES
`
`4048
`
`RETURN SELECTED VIRTUAL MACHINE
`TO READY STATE
`
`END
`
`

`

`U.S. Patent
`
`Sep. 3, 1996
`
`Sheet 5 of 12
`
`5,553,291
`
`FIG. 4(B)
`
`FROMFIG 4(A)
`
`STEP 4030
`
`4050
`
`PUT SELECTED VIRTUAL MACHINE INTO
`VP WAIT STATE
`
`
`
`4060
`
`READY STATE DETERMINATION MADE
`FOR ALL VIRTUAL MACHINES?
`
`
`
`
`PUT SCALAR PROCESSOR INTO WAIT
`STATE
`
`
`
`INTERRUPTION GENERATED TO VMM
`
`
`IF VIRTUAL MACHINE IN SP WAIT STATE
`
`HAS BEEN RELEASED,PUT INTO READY
`STATE
`
`
`VECTOR PROCESSOR
`FREE?
`
`
`PUT VIRTUAL MACHINE IN VP WAIT
`STATE INTO READY STATE
`
`

`

`U.S. Patent
`
`Sep. 3, 1996
`
`Sheet 6 of 12
`
`5,553,291
`
`FIG. 5
`
`SIE
`INSTRUCTION
`
`STATE DESCRIPTION
`VIRTUAL MACHINE
`START-UP INFORMATION
`VIRTUAL MACHINE
`UNLOAD INFORMATION
`
`VIRTUAL MACHINE MONITOR
`
`412
`
`
`
`MOPrmyoxdaiwn2-PE
`
`REGISTER
`
`INSTRUCTION
`EXECUTION
`UNIT
`
`EXECUTION
`CIRCUIT
`
`L~
`
`VP BUSY VM
`
`IDENTIFICATION
`
`TO VECTOR
`PROCESSOR 200
`
`FROM VECTOR
`PROCESSOR 200
`
`

`

`US. Patent
`
`Sep. 3, 1996
`
`Sheet 7 of 12
`
`5,553,291
`
`FIG. 6
`
`SP WAIT
`STATE
`
`
`
`SET WAIT STATE
`
`
`
`
`
`
` DISPATCH
`
`RELEASE WAIT
`STATE
`
`STATE
`
`VP WAIT
`STATE
`
`
`
`VP BUSY
`
`

`

`U.S. Patent
`
`Sep. 3, 1996
`
`Sheet 8 of 12
`
`5,553,291
`
`rnou ster
`
`FIG. 7(A)
`7000
`
`
`
`IS THERE A VIRTUAL MACHINE IN A
`
`READY STATE?
`
`
`7010
`YES
`GIVE SP TO READY STATE VIRTUAL
`MACHINE AND START IT ON SP
`
`
`
` 7020
`NO
`OS REQUEST TO USE VECTOR
`
`PROCESSOR (EXVP INSTRUCTION)?
`
`
`
`
`YES
`
`
`OTHER VIRTUAL MACHINE USIN
`VECTOR PROCESSOR?
`
`NO
`7040
`
`7030
`
`YES
`
`SET VMID OF RUNNING VM IN VP BUSY
`VM IDENTIFICATION REGISTER
`
`
`
`CONTINUE VIRTUAL MACHINE
`OPERATION
`.
`
`7050
`
`
`7052
`
`NO
`
`YES
`
`7054
`
`RETURN TO READY STATE
`
`END
`
`PASS CONTROL TO VIRTUAL MACHINE|4129
`MONITOR
`
`7130
`
`PUT VIRTUAL MACHINE THAT WAS
`RUNNING INTO VP WAIT STATE
`
`TO STEP
`7000
`
`

`

`USS. Patent
`
`Sep. 3, 1996
`
`Sheet 9 of 12
`
`5,553,291
`
`FIG. 7(B)
`
`
`
`FROM FIG 7(A)
`STEP 7000
`
`IF THERE IS INTERRUPTION FROM
`VECTOR PROCESSOR, RESET VP BUSY
`VM IDENTIFICATION REGISTER
`
`
`
`
`IF VIRTUAL MACHINE IN SP WAIT STATE
`
`HAS BEEN RELEASED, PUT INTO READY
`STATE
`
`
`
`
`
`
`IS VECTOR PROCESSOR FREE?
`
`PUT VIRTUAL MACHINE IN VP WAIT
`STATE INTO READY STATE
`
`TO FIG 7(A)
`STEP7000
`
`

`

`U.S. Patent
`
`Sep. 3, 1996
`
`Sheet 10 of 12
`
`5,553,291
`
`FIG. 8
`
`SP WAIT
`STATE
`
`EXVP INSTRUCTION
`
`VPUNUSED| | Grave
`
`
`
`
` SET WAIT STATE
`
` DISPATCH
`
`END
`INTERRUPTION
`
`VP WAIT
`STATE
`
` VP FREE
`
`STATE
`
`TIME SLICE
`
`EXECUTE STATE
`
`

`

`U.S. Patent
`
`Sep. 3, 1996
`
`Sheet 11 of 12
`
`5,553,291
`
`
`
`FROM STEP
`9120
`
`FIG. 9(B)
`
`FIG. 9(A) 9000
`
` IS THERE A VIRTUAL MACHINE INA
`
`READY STATE?
`
`
`YES
`
`GIVE SP TO READY STATE VIRTUAL
`MACHINE AND STARTIT ON SP
`
`NO
`
`9020
`
`OS REQUEST TO USE VECTOR
`PROCESSOR (EXVP INSTRUCTION)?
`
`
`
`
`
`
`
`YES
`
`IS ANOTHER VIRTUAL MACHINE
`USING VECTOR PROCESSOR?
`
`NO
`
`SET VMID OF RUNNING VM IN VP BUSY
`VM IDENTIFICATION REGISTER
`
`START USING VECTOR PROCESSOR
`
`9050
`
`,
`CONTINUEVIRTUALMACHINE
`
`
`OFMMESU9062
`9130
`
`OPERATION
`
`NO
`
`RETURN TO READY STATE
`
`9060
`
`9064
`
`FROM FIG
`9(B) STEP
`
`9030
`
`
`
`YES
`
` 9040
`
`

`

`U.S. Patent
`
`Sep. 3, 1996
`
`Sheet 12 of 12
`
`5,553,291
`
`FIG. 9(B)
`
`
`
` FROMFIG 9(A)
`
`STEP 9000
`
`
`
`
`IF THERE IS INTERRUPTION FROM
`
`
`
`VECTOR PROCESSOR, RESET VP BUSY
`VM IDENTIFICATION REGISTER
`
`
`
`IF VIRTUAL MACHINE IN SP WAIT STATE
`
`HAS BEEN RELEASED, PUT INTO READY
`
`IS VECTOR PROCESSOR FREE?
`
`STATE
`
`
`
`
`INFORM VIRTUAL MACHINES THAT
`
`
`RECEIVED A BUSY STATUS REPORT
`THAT VECTOR PROCESSOR IS FREE
`
`FROM FIG
`
`9030
`9(A) STEP
`
`
`
`INFORM OS THAT VECTOR PROCESSOR
`IS BUSY
`
`
`
`TO FIG 9(A)
`STEP9060
`
`
`
`

`

`5,953,291
`
`1
`VIRTUAL MACHINE CONTROL METHOD
`AND VIRTUAL MACHINE SYSTEM
`
`FIELD OF THE INVENTION
`
`The present invention relates to a virtual machine control
`method, and moreparticularly to a virtual machine control
`method for enabling a plurality of virtual machines to use a
`second processor of a supercomputer.
`
`BACKGROUND OF THE INVENTION
`
`Asdescribed in published Japanese patent application no.
`JP-A-57-212680,a virtual machine system (VMS) generates
`multiple virtual machines (VM), which are logical comput-
`ers, On a real computer and enables one operating system
`(OS) to be run for each virtual machine. In this virtual
`machine system, functions such as virtual machine sched-
`uling and simulation processing of those instructions issued
`by a virtual machine operating system that cannotbe directly
`executed by a real computer (hereinafter referred to simply
`as a “computer”) are carried out by a virtual machine
`monitor (VMM). A virtual machine system is utilized
`mainly for running multiple operating systems used for
`different purposes on one computer. For example, both an
`old and a new operating system can be run on one computer
`by using a virtual machine system, which may occur during
`a transition from the old operating system to the new
`operating system. As another example, a virtual machine
`system can be used as a tool for implementing operating
`system tests in parallel] on one computer.
`Supercomputers constituted by scalar and second proces-
`sors are used for high-speed scientific and technical calcu-
`lations. The scalar processor activates the second processor
`and then performs other processing. When the second pro-
`cessor is activated it receives, and executes, a second job
`from the scalar processor. The second processor uses an
`interruption to communicate the termination of this second
`job to the scalar processor. Japanese published patent appli-
`cation no. JP-A-64-54542 discloses a virtual machine sys-
`tem in which one virtual machine (VM) has exclusive
`possession of a second processor(called a second unit, in the
`disclosure) and multiple virtual machines are able to share
`the scalar processor (called a scalar unit, in the disclosure),
`
`SUMMARYOF THE INVENTION
`
`There are the following problems in running a virtual
`machine system on a supercomputer and enablinga plurality
`of virtual machines to use the second processor.
`(1) The first problem that arises when multiple virtual
`machines share a second processor concernsthe scheduling
`of the virtual machines. In the prior art the second processor
`was used exclusively by one virtual machine so there was no
`particular problem with scheduling use of the second pro-
`cessor by the virtual machines. However,
`the following
`problem arises when multiple virtual machines attempt to
`share a second processor. Once a virtual machine has been
`created it is run for an extended period, and the virtual
`machine that wants to use the second processor next has to
`wait for an extended period of time until the termination of
`the virtual machine using the second processor.
`(2) The second problem relates to processing the inter-
`ruption used to communicate to the scalar processor that
`execution by the second processor has ended. One waythis
`can be done is by having a virtual machine monitor (VMM)
`intervene to simulate the interruption, but this imposes an
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`overhead that degrades the overall performance of the
`system.
`(3) The third problem relates to the address translation
`process in the second processor. In the virtual machine
`system disclosed in JP-A-64-54542, a virtual machine that
`uses the second processoris assigned an exclusive region of
`main storage extending from a designated address to the
`highest address, The numberof virtual machinesthat can use
`the second processoris therefore limited to one. Moreover,
`with a supercomputerthat has a plurality of second proces-
`sors, the method according to the above disclosure does not
`allow each of a plurality of operating systems to have
`exclusive use of a second processor.
`Anobject of the present inventionis to efficiently control
`a virtual machine system on a supercomputer having second
`and scalar processors.
`Another object of the present invention is to provide a
`virtual machine scheduling method that enables multiple
`virtual machines to share a second processor.
`A further object of the present invention is to provide an
`interruption execution method whereby an instruction
`execution termination interruption can be executed directly
`on the operating system of the virtual machinethat activated
`the second processor, without the intervention of a virtual
`machine monitor.
`
`A further object of the present invention is to provide an
`address translation method in a second processor which
`enables a virtual machine having an arbitrary continuous
`region in main storage to use a second processor.
`These and other objects of the invention are achieved in
`accordance with a method and system representcd by the
`following arrangement, for example.
`The virtual machine system of the present invention runs
`multiple operating systems under the supervisionofa virtual
`machine monitor on a computerhavinga first processor, and
`a second processor which starts instruction execution in
`accordance with an indication from thefirst processor and
`uses an interruption to communicate an end-of-execution to
`the first processor. The virtual machine control method of
`the present invention includes the steps of, when the virtual
`machine monitor starts the running of a first operating
`system, determining whether or not a second operating
`system is using the second processor. If so, the running of
`the first operating system is put on hold,andif not, the first
`operating system is providedwith the first processor and the
`second processor for starting the running thereof.
`The virtual machine system according to the present
`invention runs multiple operating systems under the super-
`vision of a virtual machine monitor on a computer having a
`first processor, and a second processor whichstarts instruc-
`tion execution in accordance with an indication from thefirst
`processor and uses an interruption to communicate an end-
`of-execution to the first. processor. The virtual machine
`system in one embodiment includes scheduling means for
`determining how to allocate the first and second processors
`to the multiple operating systems, means provided in the
`second processor for storing mapping information that
`defines the memory address correspondence between main
`memory of the multiple operating systems and main storage
`of the computer, means for transferring to the second pro-
`cessor an identification of an operating system running on
`the first processor in accordance with the scheduling by the
`scheduling means, selection means that, when there is a
`request from the second processor to access the main
`memory of an operating system, uses operating system
`identification information sent from the first processor to
`
`

`

`5,553,291
`
`3
`select the main memory mapping information of the oper-
`ating system concerned,and translation meansthat in accor-
`dance with the selected mapping information translates the
`address of the operating system main memory to which
`access is requested for a corresponding main storage
`address.
`
`Implementation of the present invention on a computer
`having a scalar processorasthe first processor and a second
`processor as the second processor is as follows.
`(1) In a virtual machine system running multiple operat-
`ing systems on a supercomputer having scalar and second
`processors, the virtual machine monitor schedulesthe virtual
`machinesas follows.First it is determined whether ornotthe
`second processor is being used by a second operating system
`that is other than the first operating system which is to be
`run. If the second processor is being used by a second
`operating system, the operation ofthe first operating system
`is put on hold. When the second operating system finishes
`using the second processor the virtual machine monitor
`reschedules the first operating system. Also, when the sec-
`ond processoris not being used by any operating system or
`is being used bythefirst operating system itself, the scalar
`processor and second processor are both given to the first
`operating system and the first operating system is started.
`Thus, at the point at which the first operating system is
`started the second processoris either free or is being used by
`the first operating system itself. Also, the second processor
`is only activated by an instruction issued by the scalar
`processor. As such, there is no activation of the second
`processor by another operating system while the first oper-
`ating system is running on the scalar processor.
`Also provided is another method in accordance with
`which the scalar processor is given to the first operating
`system regardless of whether the second processoris busy or
`not, and whenthere is a request to use the second processor
`FIGS. 9(A) and 9(B)taken together are a flow chart of the
`it is determined whetheror not the second processoris busy.
`third embodiment scheduling method.
`Thus, as described above, a virtual machine scheduling
`1. Supercomputer configuration
`method can be provided that enables multiple virtual
`FIG. 1 is a block diagram of a virtual machine system
`40
`machine operating systems to share the second processor.
`(VMS)ofthe present invention implemented with a super-
`(2) Inavirtual machine system running multiple operat-
`computer. In the drawing, 100 is a scalar processor (SP) that
`ing systems on a supercomputer having scalar and second
`performsscalar processing, 200 is a second processor (VP)
`processors, when the second processor finishes instruction
`that performs second processing, and 300 is a storage
`execution,an interruption for the operating system that used
`controller (SC) that references or refreshes main storage
`the second processor is put on hold. The interruption is
`(MS) 400 in accordance with instructions from the scalar
`exccuted latcr at a point at which the operating system
`processor 100 or second processor 200.
`_
`running on the scalar processor can be interrupted. By thus
`Thescalar processor 100 is provided with a scalar instruc-
`holding an interruption for each operating system, the sec-
`tion execution circuit 110 and an interruption execution
`ondprocessor end of execution interruption can be executed
`circuit 120. Also, the second processor 200 is provided with
`without the intervention of the virtual machine monitor. This
`a second instruction execution circuit 210 and an address
`translation circuit 220. When the scalar instruction execu-
`makesit possible to decrease the overhead that accompanies
`the intervention of the virtual machine monitor.
`tion circuit 110 in the scalar processor 100 executes an
`EXVP (Execute Second Processor) instruction, the second
`instruction execution circuit 210 starts executing second
`instructions in the main storage 400. Also, termination of the
`execution of the second instructions by the second instruc-
`tion execution circuit 210 is intercepted by the interruption
`execution circuit 120 in the scalar processor 100. For
`controlling the second processor 200, in addition to the
`EXVPinstruction the scalar processor 100 is also provided
`with a TVP (Test Sccond Processor) instruction to determine
`whether or not the second processor 200 is busy.
`Arranged on the main storage 400 is a virtual machine
`monitor (VMM) 410 that performs virtual machine (VM)
`scheduling and the like. The main memory 420 of virtual
`machine (VM-1) resides in a region of the main storage 400
`extending from address 0 upto, but not including, address o,
`
`(3) In a virtual machine system running multiple operat-
`ing systems on a supercomputer having scalar and second
`processors, the virtual machine monitor provides each of the
`virtual machines beforehand with a continuous region in the
`main storage of a real computer. First, memory address
`mapping information between the main memory of multiple
`operating systems and main storage on a real computer is
`registered in the second processor by the virtual machine
`monitor. When a virtual machine operating system in the
`scalar processor requests the second processor, the identifi-
`cation of that operating system is sent from the scalar
`processorto the second processor. When there is a request by
`the second processor to access operating system main
`memory, the memory address mapping information of the
`operating system concerned is selected from the said oper-
`
`4
`ating system identification. The second processor then uses
`the selected memory address mapping information to trans-
`late the main memory address of the operating system to
`which access has been requested, to an address in the main
`storage of the real computer. The address obtained by this
`translation is then used to access the real computer main
`storage area corresponding to the main memory areaof that
`operating system.
`In accordance with the above, virtual machines that have
`been allocated an arbitrary continuous region of the main
`storage of a real computer are able to utilize a second
`processor.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a schematic diagram of a system embodimentof
`the present invention implemented on a supercomputer.
`FIG. 2 is a schematic diagram of the addresstranslation
`circuit shown in FIG. 1.
`
`FIG.3 is an explanatory diagram ofstate transitions in a
`scheduling method of a first embodiment of the invention.
`FIGS. 4(A) and 4(B)taken togetherare a flow chart of the
`first embodiment scheduling method.
`FIG. 5 is a schematic diagram of the scalar processor
`shownin FIG. 1.
`
`FIG.6 is an explanatory diagram of state transitions in a
`scheduling method of a second embodimentof the inven-
`tion.
`
`FIGS. 7(A) and 7(B) taken togetherare a flow chart of the
`scheduling method according to the second embodiment.
`FIG.8 is an explanatory diagram of state transitions in a
`scheduling method according to a third embodimentof the
`invention.
`
`20
`
`25
`
`30
`
`35
`
`45
`
`30
`
`55
`
`60
`
`65
`
`

`

`5,553,291
`
`5
`while the main memory 430 of virtual machine (VM-2)
`resides in a region extending from address & up to, but not
`including, address B. To differentiate the virtual machine
`main memories 420 and 430, main storage 400 is referred to
`as real computer main storage. The address translation
`circuit 220 translates a logical address
`(guest
`logical
`address: GLA) designated by second instructions in virtual
`spaces 440 and 450 (indicated in the drawing as Multiple
`Virtual Space), created by the operating systems on the
`virtual machines,
`to an absolute address (guest absolute
`address: GAA)in virtual machine main memory, and, fur-
`thermore, translates this guest absolute address to an abso-
`lute address (host absolute address: HAA) in the main
`storage 400. The virtual machine monitor 410 performs
`virtual machine scheduling to enable multiple virtual
`machines to use the second processor 200. Also, the end of
`execution interruption of the second processor 200 can be
`directly executed on the operating system that activated the
`second processor 200, by the interruption execution circuit
`120, without the intervention of the virtual machine monitor
`410.
`When virtual machines are created, each is given an
`attribute indicating whether or-not it uses the second pro-
`cessor 200. That is, a virtual machine that has an attribute
`indicating that it uses the second processor 200 will have a
`virtual machine configuration with a second processor, and
`a supercomputer operating system will operate under that
`virtual machine. Also, a virtual machinethat has an attribute
`indicating non-use of the second processor 200 will have a
`virtual machine configuration that does not have a second
`processor, and a general-purpose computer operating system
`will operate under that virtual machine.
`One example of address translation processing in the
`second processor 200, three examples relating to virtual
`machine scheduling methods and one example of a method
`of processing an end-of-executioninterruption by the second
`processor 200 will now be described in detail with reference
`to the respective drawings.
`2. Address translation in the second processor
`FIG. 2 showsdetails of the configuration of the address
`translation unit 220 shown in FIG. 1. In FIG. 2, an address
`cross-mapping table 221 provided in accordance with the
`present invention holds the starting address and end address
`of the virtual machine main memory in the main storage
`400. For example,
`the first entry in the address cross-
`mapping table 221 showsthat the region from address 0 to
`address a (not including address «) in the main storage 400
`is the main memory 420 of VM-1, and the second entry
`shows that the region from address a to address B (not
`including address B) in the main storage 400 is the main
`memory 430 of VM-2. The address cross-mapping table 221
`may be established with the scalar instructions used when
`the virtual machine monitor 410 creates a virtual machine.
`A logical address (guest logical address) 226 in the virtual
`space of a virtual machine, designated by second instruc-
`tions, is translated to an absolute address (guest absolute
`address) 229 in virtual machine main memory by a VP
`address translation circuit of unit 222. The addresstransla-
`tion unit 220 is also provided with an adder (ADD) 223 and
`comparator (COMP) 224.
`The secondinstruction execution circuit 210 inputs to the
`address translation unit 220 a VMID signal 225 that indi-
`cates the identification of the virtual machine that issued the
`instruction to execute the secondinstructions. This VMIDis
`the VMIDof the virtual machine that was running on the
`scalar processor 100 when the EXVPinstructionto activate
`the second processor 200 was executedby the scalar instruc-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`40
`
`45
`
`50
`
`35
`
`60
`
`65
`
`6
`tion execution unit 110. Based on this VMID, the address
`translation unit 220 selects a starting address 231 and end
`address 232.in the main storage 400 main memory of the
`virtual machine that issued the instruction to execute the
`second instructions from the address cross-mapping table
`221. In the VP address translation circuit 222 the guest
`logical address 226 input from the second instruction execu-
`tion circuit 210 is converted to a guest absolute address 229.
`This guest absolute address 229 is then output as host
`absolute address 227 to which the starting address 231 has
`been added by the adder (ADD) 223. The secondinstruction
`execution circuit 210 uses this output to execute the second
`instruction.
`However, when the result of the determination by the
`comparator 224 is that the guest absolute address 229 is
`larger than the end address 232 (indicating that guest abso-
`lute address 229 is outside the main memory area of the
`virtual machine), an interruption signal 228 is output to the
`secondinstruction execution circuit 210. This forms a check
`mechanism to ensure that the main memory contents of the
`other virtual machine are not destroyed. When the second
`instruction execution circuit 210 receives the interruption
`signal 228, the second instruction execution circuit 210 halts
`execution of the second instructions and sends an interrup-
`tion signal to the interruption execution circuit 120 in the
`scalar processor 100.
`in accordance with the above procedure, address transla-
`tion in the second processor 200 enables virtual machines
`having an arbitrary continuous region of the main storage
`400 to use the second processor 200.
`3. Embodiments of virtual machine scheduling method
`3.1 First embodiment scheduling method
`Virtual machine scheduling state transitions will now be
`described, first with reference to FIG. 3, In accordance with
`the first scheduling method, under the virtual machine
`monitor 410 there are four virtual machine scheduling states,
`which are a scalar processor wait state (SP wait state), a
`ready state, an execute state, and a second processor wait
`state (VP wait state). Only a virtual machine in an execute
`state can start executing second processor 200 instructions in
`accordance with an EXVP instruction ofthe scalar processor
`100.
`When an SP wait state is released by the virtual machine
`monitor 410 as a result of an interruption or suchlike
`simulation performed with respect to a virtual machine, the
`virtual machine assumes a ready state. In accordance with
`sequence dispatching by the virtual machine monitor 410, a
`ready state virtual machine assumes an execute state. Dis-
`patching means giving the scalar processor to the operating
`system of the designated virtual machine. In the execute
`state, when the operating system running on the virtual
`machine issues a wait state set
`instruction the virtual
`machine assumes an SP wait state. On the other hand, when
`in the execute state a time slice (a predetermined small time
`period) elapses the virtual machine reverts to a ready state.
`This is to implement sequential operation of multiple virtual
`machines on a time sharing basis. Moreover, when the
`virtual machine monitor 410 detects that the second proces-
`sor 200 is busy, a virtual machine VM that has a second
`processor 200 use attribute and is not presently using the
`second processor 200 is changed to a VP ready state to avoid
`conflict over use of second processor 200. When the second
`processor 200 assumes a free state these wait state virtual
`machines VM revert to a ready state. However, virtual
`machines that are in a ready state and have a second
`processor 200 non-use attribute do not shift to a VP wait
`state. This is to ensure that even when dispatching is used to
`
`

`

`5,553,291
`
`7
`put this virtual machine into an execute state, a virtual
`machine that is using the second processor 200 will not be
`affected and, also, a virtual machine that is not able to use
`the second processor 200 will not be affected by a virtual
`machine that is using the second processor 200.
`A first virtual machine scheduling method by the virtual
`machine monitor 410 will now be described with reference
`to the flow chart of FIG. 4.
`The virtual machine monitor 410 first determines whether
`or notthere is a virtual machine in a ready state (Step 4000),
`and if there is not puts the scalar processor 100 into a wait
`state (Step 4070). If there is a virtual machine in a ready
`state, ready state virtual machine selection is carried out in
`accordance with a dispatching cue (Step 4010), and it is
`determined whether or not the selected virtual machine has
`a second processor 200 use attribute (Step 4020). In the
`absence of a use attribute the selected virtual machine is
`started on the scalar processor 100 (Step 4040). If during the
`running of the virtual machine (Step 4042)a time slice ends
`(Step 4046),the virtual machine concernedis returnedto the
`ready state (Step 4048).
`In Step 4020, when the selected virtual machine has a
`second processor 200 use attribute the virtual machine
`monitor 410 executes the TVP (Test Second Processor)
`instruction and determines whether or not second processor
`200 is being used by another virtual machine (Step 4030),
`andif it is not, the selected virtual machineis started on the
`scalar processor 100 (Step 4040).
`With this scheduling method dispatching is implemented
`to give the scalar processor 100 and second processor 200 to
`the same virtual machine. Therefore if the TVP instruction
`is executed and second processor 200 is busy, it is estab-
`lished that of the virtual machines that have been given a
`second processor 200 useattribute, the virtual machine most
`recently dispatched by the virtual machine monitor 410 is
`using the second processor 200.
`Virtual machine operation on the scalar processor 100 is
`effected in accordance with the SIE (Start Interpretive
`Exccution) instruction described below. The operating sys-
`tem on this virtual machine is able to use the second
`processor 200 and scalar instruction execution circuit 110
`and can directly cxecute an EXVPinstruction issued by the
`operating system without applying an interruption (simu-
`lated by the virtual machine monitor 410) to the virtual
`machine monitor 410.
`When in Step 4030 it is determined that the second
`processor 200 is being used by another virtual machine,the
`virtual machine monitor 410 holds the operation of the
`selected virtual machine on the scalar processor 100 as a VP
`wait state (Step 4050). It is checked whether the above
`determination has been made with respect to all virtual
`machines (Step 4060), and if some remain, process execu-
`tion returns to Step 4010 and the virtual machine to be run
`is again selected. When the determination of the ready state
`has been completed for all virtual machines, the virtual
`machine monitor 410 puts scalar processor 100 into an SP
`wait state (Step 4070). Followingthis, if a designated virtual
`machineis released from the SP wait state by the generation
`of an interruption (Step 4080) from an input/output device or
`the like to the virtual machine monitor 410,
`the virtual
`machine goes from an SP wait state to a ready state (Step
`4090). Then, the virtual machine monitor 410 uses the TVP
`instruction to determine whether, owing to the aboveinter-
`ruption, second processor 200 has assumeda free state (Step
`4100). If it has not, the execution again goes to Step 4010
`and the virtual machine to be run is selected. If it has
`assumed a free state, the virtual machine monitor 410 puts
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`30
`
`55
`
`60
`
`65
`
`8
`virtual machines in a VP wait state into a ready state, moves
`execution to Step 4010 and selects the virtual machine to be
`run.
`
`Th