Abstract:
In scheduling shared processing that has a higher priority than LPAR processing, giving precedence to physical CPUs running idle LPARs prevents prolonged hold-up of LPAR processing. In a system is comprised of multiple physical CPUs, multiple LPARs to which these physical CPUs are allocated and which execute programs under their guest OSes, and a management program managing these LPARs, a few additional units are introduced: a guest OS monitoring unit that can grasp the states of guest OSes running on these LPARs and a dispatcher unit that allocates one of these physical CPUs to shared processing requested by the management program, which has a higher priority than LPAR processing. When a request for shared processing arises, the dispatcher unit interrogates the guest OS monitoring unit and, based on the information obtained from it, gives priority of allocation to the physical CPU processing an idle LPAR.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates generally to computer systems, and in particular, to the scheduling of shared processing in a computer system whose physical resources are split into a plurality of logical partitions (hereinafter abbreviated to “LPARs”). 
         [0003]    2. Description of the Related Art 
         [0004]    In recent years, a scheme called “server partitioning” has been put to practical use, whereby the hardware resources of a high-performance computer system are partitioned into a number of parts called LPARs, each of which in turn serves as a server. Server partitioning is classified into two types depending on the operating environments of the LPARs: hypervisor type and host operating system (hereinafter abbreviated to OS) type. In a hypervisor type environment, LPARs are operated under a special management program called a hypervisor that resides on the bare machine. In a host OS type environment, LPARs are operated under a management program that runs as an application under an ordinary OS (host OS). In either case, the key elements of server partitioning are a control mechanism called Virtual Machine Monitor (VMM) and a number of LPARs operated under it. An LPAR is also called a “virtual machine”; the OS operating on it is called the “guest OS.” In terms of function, the guest OS operates in the same manner on the LPAR as it does on an ordinary server which is not partitioned. 
         [0005]    The hypervisor primarily carries out instruction emulation, memory management, I/O processing, and scheduling. Since several LPARs may share some of the resources of the hosts, the hypervisor includes the function of “shared processing,” which is demanded by all the LPARs from time to time. In general, this processing should be given a higher priority than the processing of individual LPARs. Unfortunately, shared processing may, if no CPU is allocated to it, take up the entire CPU resources allocated to an LPAR, thereby holding up all the processing on that LPAR. 
         [0006]    There exist several known schemes that are designed to solve such a problem, namely the problem where certain processing prevents physical CPU resources from being allocated to other processing. An example is time-sharing, which is a scheduling algorithm designed to guarantee impartial treatment of various pieces of processing. Time-sharing allows physical CPUs to be allocated to each individual piece of processing, without holding up shared processing for an extended period of time. With time-sharing, however, it is impossible to determine whether the physical CPU that is given resources is one that is processing an LPAR in busy state or one that is processing an LPAR that is internally in idle state. 
         [0007]    On the other hand, as a scheme for preventing prolonged hold-up of the processing of certain jobs, a “job class” method is known, which allocates resources based on priority. This method predefines a priority scheme consisting of multiple levels called job classes; each piece of processing is assigned one of the job classes when executed. This approach thus realizes priority-based allocation of CPU resources. 
         [0008]    The job class method, however, is effective only within a closed environment inside one computer (OS); it is difficult to apply this method to an environment encompassing multiple LPARs and a hypervisor. The reason is that whereas the hypervisor statically treats all the LPARs equally with the same priority level, the internal state of each LPAR dynamically switches from “busy” to “idle” and vice versa. 
         [0009]    Further, Japanese Unexamined Patent Application Publication No. 2006-244483 discloses a method for detecting processes that consume large amounts of CPU resources and allocating them to an “isolated LPAR” for which allocation of less resources is defined than for other LPARs, thereby preventing these other LPARs from being impacted. This scheme, however, cannot be applied to shared processing requested by the hypervisor, which should be given a higher priority during execution than the processing of LPARs. 
       SUMMARY OF THE INVENTION 
       [0010]    A more detailed description of the problem to be solved by the invention is due, with reference to  FIGS. 1 through 3 .  FIG. 1  illustrates the way in which shared processing is dispatched in a time-sharing system. Three physical CPUs are allocated to three LPARs in a dedicated manner, namely, CPU 0  to LPAR 0 , CPU 1  to LPAR 1 , and CPU 2  to LPAR 2 . The guest OSes running on LPAR 0  and LPAR 2  are always in busy state, whereas the guest OS running on LPAR 1  is in idle state. 
         [0011]    When a request for shared processing arises at a certain point in time  100 , it is dispatched piecemeal to the three physical CPUs (in other words, the three physical CPUs are allocated to it one after another) as indicated by the three time slices  101 - 103 . Since the load of shared processing is borne by the three physical CPUs in a time-shared manner, the prolonged hold-up of the processing of a particular LPAR is prevented. 
         [0012]    This arrangement, however, has a disadvantage that, assuming equal priority among all the LPARs, all the physical CPUs are uniformly deprived of resources, regardless of the states (busy or idle) of the guest OSes running on them. For example, physical CPU 0 , which is kept busy processing an LPAR even without the allocated load of shared processing as indicated by a time slice  104 , is deprived of its resources for that load, while there is a physical CPU that processes an LPAR in idle state as indicated by another time slice  105 . 
         [0013]      FIG. 2  illustrates a solution to the above-mentioned problem, which, instead of using a time-sharing method, allocates, to shared processing, multiple physical CPUs in a distributed manner, based on the detection of LPARs in idle state and the number of allocations, or dispatches, each physical CPU has been given. When a request from the hypervisor for shared processing arises at a certain point in time  200 , a physical CPU processing an LPAR in idle state is allocated to it. However, when a request for processing arises in the guest OS or an application on that LPAR at a later point in time  201 , it is held pending until a point in time  202  when the shared processing on that LPAR completes, because the latter is given a higher priority than the former. Thus, this method is also not free from the possibility that the guest OS on one of the LPARs is held up for an extended period of time, as indicated by  203 . 
         [0014]    As shown in  FIG. 3 , this problem can be solved by introducing a certain modification such that physical CPU 1 , whose guest OS is allocated to LPAR 1  that is in idle state, moves from idle state to busy state at a point in time  301  when it has completed the execution of multiple pieces of processing that originated at a point in time  300 . As a result, shared processing is considered to have been quickly carried over to one of the physical CPUs that are processing busy LPARs. 
         [0015]    The count-based scheduling method as described above, however, is also not free from the possibility that although load is generally balanced on the whole, a large amount of load of shared processing is put on one of the physical CPUs processing LPARs. In such a case, shared processing remains put on one physical CPU until load balancing is achieved at a point in time  302 , and the LPAR running on this physical CPU is held up for an extended period of time. This problem happens because after the physical CPU processing an LPAR in idle state moves into busy state, no processing is assigned to that physical CPU in consideration of maintaining load balancing, since the accumulated count for that physical CPU is high. 
         [0016]    It is a general object of the invention to provide a computer system that prevents prolonged hold-up of the processing of LPARs because of shared processing. It is a more specific object of the invention to provide a system for efficiently scheduling shared processing that has a higher priority than LPAR processing, by preventing prolonged hold-up of the processing of LPARs in busy state through effective use of CPUs allocated to LPARs in idle state. 
         [0017]    The computer system according to the present invention is preferably configured as a computer system composed of a plurality of physical CPUs, a plurality of LPARs to each of which one of these physical CPUs is allocated and which execute programs under the guest OSes running on them, a management program that manages these LPARs, a guest OS monitoring unit capable of grasping the states of the guest OSes running on these LPARs, and a dispatcher unit that allocates one of these physical CPUs to the management program&#39;s shared processing that has a higher priority than LPAR processing, all configured so that the dispatcher unit gives priority, based on the information obtained from the guest OS monitoring unit, to the physical CPUs processing LPARs in idle state in dispatching shared processing. 
         [0018]    A preferred embodiment of the present invention is a computer system equipped with a set of dispatch priority tables that manage priority assignment among the management program&#39;s shared processing and all other processing, so configured that the dispatch priority tables are updated upon completion of execution of a certain number of pieces of shared processing. 
         [0019]    Another preferred embodiment of the present invention is a computer system of a similar composition further equipped with a table updating unit that updates the contents of the dispatch priority tables, so configured that the table updating unit gives shared processing a higher priority, at the initial point, than the processing of LPARs in idle state and later gives it a lower priority upon completion of execution of a certain number of pieces of shared processing. Thus, shared processing, which ordinarily has a higher priority, is prevented from monopolizing a particular physical CPU and, as a result, the processing of an LPAR by that physical CPU is prevented from being held up for an extended period of time. 
         [0020]    A further preferred embodiment of the present invention is a computer system of a similar composition further equipped with a counter belonging to the dispatcher unit that manages the number of times each physical CPU is allocated to shared processing. Each time a decision is to be made on whether or not to update the value of the counter, the dispatcher unit obtains, from the guest OS monitoring unit, the state of the LPAR running on the physical CPU which has been allocated to shared processing and, if that LPAR is in idle state, does not update the value of the counter. In a still further preferred embodiment of the present invention, at least one of the plurality of LPARs is set aside as one that primarily executes shared processing. When a request for shared processing arises, the dispatcher unit gives priority of allocation to the physical CPU processing the LPAR thus set aside or an LPAR in idle state. 
         [0021]    A preferred embodiment of the present invention also relates to a scheduling method involving a hypervisor that allocates a plurality of physical CPUs to a plurality of LPARs and that manages the scheduling of shared processing which pertains to all the LPARs. In particular, the scheduling method monitors, using the guest OS monitoring unit, the states of the guest OSes running on the LPARs and when a request for shared processing arises, gives priority of allocation, based on the information obtained from the guest OS monitoring unit, to the physical CPU(s) processing an LPAR or LPARs in idle state. 
         [0022]    As described above, in a system composed of a plurality of physical CPUs and a plurality of LPARs to which they are allocated, the present invention allows, in allocating resources to shared processing, the effective use of physical CPUs allocated to LPARs in idle state. Further, even if there are no LPARs in idle state, it achieves balanced scheduling, by equally utilizing the physical CPUs allocated to all the LPARs, so that preference is given to shared processing with a higher priority than LPARs, while preventing prolonged hold-up of the processing of a particular LPAR. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0023]      FIG. 1  is a diagram explaining how shared processing is dispatched in a time-sharing system. 
           [0024]      FIG. 2  is a diagram explaining how shared processing with a higher priority holds up the processing of a particular LPAR. 
           [0025]      FIG. 3  is a diagram explaining how uniform allocation causes prolonged hold-up of the processing of a particular LPAR. 
           [0026]      FIG. 4  is an exemplary diagram showing the configuration of a computer system according to an implementation consistent with the principles of the invention. 
           [0027]      FIG. 5  shows the configuration of the Scheduling Unit  423  contained in  FIG. 4 . 
           [0028]      FIG. 6  shows the configuration of the Dispatch Priority Tables  54 . 
           [0029]      FIG. 7  illustrates the processing sequence of the Dispatch Table Updating Unit  53  contained in  FIG. 5 . 
           [0030]      FIG. 8  is a flowchart showing the scheduling in a computer system according to an implementation consistent with the principles of the invention. 
           [0031]      FIG. 9  shows how scheduling is managed in accordance with an embodiment of the invention. 
           [0032]      FIG. 10  is an exemplary diagram showing the configuration of a computer system according to another embodiment of the invention. 
       
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0033]    Referring now to the drawings, preferred embodiments are described herein. 
       Embodiment 1 
       [0034]      FIG. 4  is an exemplary diagram showing the configuration of a computer system according to an embodiment of the invention. 
         [0035]    Server partitioning is applied to this computer system, which comprises four physical CPUs  411 - 414  (generically numbered  41 ), so that they are allocated to four LPARs  430 - 433  (generically numbered  43 ). There is a Hypervisor  420  managing the LPARs, which is run on a plurality of physical CPUs in a collaborative manner instead of a single physical CPU in a dedicated manner (there are no hidden CPUs). The I/O processing that pertains to the devices shared in the system constitutes shared processing. 
         [0036]    A set of physical (hardware) resources  410  of the system includes a plurality of physical CPUs  411 - 414 , a main storage  415 , an external storage  416 , and a network interface card  417 . 
         [0037]    The Hypervisor  420  operates using the hardware resources  410  and manages and controls a plurality of LPARs  430 - 433  that run on them. In terms of function, the Hypervisor  420  comprises an Instruction Emulation Unit  421 , a Memory Management Unit  422 , a Scheduling Unit  423 , and an I/O Processing Unit  424 . 
         [0038]    The LPARs  43  comprise guest OSes  440 - 443  (generically numbered  44 ) and application programs  450 - 453  (generically numbered  45 ) that run under them. The application programs operate in this configuration in the same manner as on hardware to which server partitioning is not applied. 
         [0039]      FIG. 5  shows the configuration of the Scheduling Unit  423 , which comprises a Guest OS Monitoring Unit  51 , a Dispatcher Unit  52 , and a Dispatch Priority Table Updating Unit  53 . The Guest OS Monitoring Unit  51  monitors and grasps not only shared processing but also, in a real-time manner, the states of the OSes running on the LPARs  43  and of the LPARs that execute shared processing. 
         [0040]    The Dispatcher Unit  52  allocates C-PU resources to the Hypervisor  420  and the LPARs  43 , using a scheduling algorithm. The Dispatcher Unit  52  is equipped with a Dispatch Counter Table  521 . To maintain a balance of load in allocating the physical CPUs  41  to the LPARs  43 , the Dispatcher Unit  52  counts the number of times each one of the physical CPUs  41  is allocated to shared processing, and keeps all such counts in the Dispatch Counter Table  521 . In allocating a physical CPU, it chooses the one with the least count; for example, if the Dispatch Counter Table  521  holds the values “2,” “3,” “4,” and “1” for the physical CPUs  411  through  414 , respectively, the Dispatcher Unit  52  chooses the physical CPU  414 , which has the smallest value of “1,” as the physical CPU to be allocated next to shared processing. 
         [0041]    The Dispatch Priority Table Updating Unit  53  is equipped with Dispatch Priority Tables  541  through  544  (generically numbered  54 ) corresponding to the physical CPUs  411  through  414 , respectively, so as to dynamically manage the priority of allocation. 
         [0042]    As shown in  FIG. 6 , the Dispatch Priority Tables  54  hold the priority levels assigned to various types of processing such as Hypervisor processing (for example, shared processing), processing of an LPAR in busy state, and processing of an LPAR in idle state. Each of the Dispatch Priority Tables  54  has two states: a regular state  61  and an exclusive state  62 . Initially, the regular state  61  is assumed. In regular state  61 , Hypervisor processing, including shared processing, is given the highest priority so that it takes precedence over processing of LPARs. 
         [0043]    In order to prevent shared processing from holding up processing of LPARs for an extended period of time, the Dispatcher Unit  52  changes, upon completion of a series of pieces of shared processing on any of the physical CPUs  411  through  414 , the state of the Dispatch Priority Table  54   n  (any of  511  through  514  as appropriate) for that physical CPU from regular  61  to exclusive  62 , by lowering its priority for shared processing. The physical CPU that has thus been moved into the exclusive state  62  releases its CPU resources if there exists LPAR processing with a higher priority than shared processing. As a result, a physical CPU can be allocated to LPAR processing, which prevents a prolonged hold-up of LPAR processing. Thereafter, upon completion of LPAR processing, the Scheduling Unit  423  puts the contents of the Dispatch Priority Table corresponding to that physical CPU back to the original values, thereby placing it in regular state. 
         [0044]      FIG. 7  illustrates the sequence of updating the Dispatch Priority Tables  54 . In the description of the embodiments of the invention contained hereinafter, the mnemonic names “physical CPU 0 ,” “physical CPU 1 ,” “physical CPU 2 ,” and “physical CPU 3 ” are each used to represent any of the physical CPUs  411  through  414 . Similarly, the mnemonic names “LPAR 0 ,” “LPAR 1 ,” “LPAR 2 ,” and “LPAR 3 ” are each used to represent any of the LPARs  430  through  433 . It should also be noted that whereas  FIG. 7  shows a case with only three physical CPUs, namely CPU 0 , CPU 1 , and CPU 2 , it is not intended to limit the number of physical CPUs to three. Operation of computer systems consisting of more than three physical CPUs is essentially the same. 
         [0045]    At the initial point, all the physical CPUs (CPU 0  through CPU 2 ) are in regular state ( 701  through  703 , respectively). When a request for shared processing arises in the Hypervisor ( 704 ), a physical CPU (CPU 0  in this case) is allocated to it immediately ( 705 ) since shared processing has the highest priority on all the physical CPUs because they are all in regular state. Upon completion of the series of pieces of shared processing given for the time slice, the physical CPU (CPU 0 ) that has been executing it is switched to exclusive state ( 706 ). In the allocation of a physical CPU in exclusive state, LPAR processing (in this case processing of LPAR 0 ) takes precedence of shared processing ( 707 ). 
         [0046]    At this point, CPU 1  is allocated to shared processing, which has a higher priority than the processing of LPAR 1  because CPU 1  is in regular state ( 708 ); as a result, shared processing is carried over without interruption. Upon completion of the series of pieces of shared processing given for the time slice, CPU 1 , which has been executing it, is switched to exclusive state ( 710 ), whereas CPU 0 , which has been in exclusive state, is put back to regular state ( 709 ). In this manner, shared processing is carried over from one physical CPU to another among a group of physical CPUs executing the processing of LPARs. 
         [0047]      FIG. 8  is a flowchart showing the processing sequence for the Scheduling Unit  423 . When a request for shared processing arises (step  801 ), the Scheduling Unit  423  checks to see if there are any free physical CPUs that are not allocated to an LPAR (step  802 ). If there is one, the Scheduling Unit  423  allocates it; if there are none, the Scheduling Unit  423  interrogates the Guest OS Monitoring Unit  52  (step  803 ) to see if there are any physical CPUs that are allocated to LPARs in idle state (step  804 ). If there is one, the Scheduling Unit  423  allocates it; if there are none, the Scheduling Unit  423  checks the Dispatch Counter Table  521  (step  805 ) and picks, as a candidate for allocation to shared processing, the physical CPU with the least allocation count, i.e., the smallest number of times it has been allocated (step  806 ). 
         [0048]    Before making the selection final, the Scheduling Unit  423  interrogates the Dispatch Priority Tables  54  (step  807 ) to see if, judging from the current priority status, it is possible to allocate the selected physical CPU to shared processing (step  808 ). If the selected physical CPU is in exclusive state and hence cannot be allocated, the Scheduling Unit  423  takes it off the candidate list (step  809 ) and checks again the Dispatch Counter Table  521 . If the selected physical CPU can indeed be allocated, the Scheduling Unit  423  finally allocates it to shared processing (step  810 ). 
         [0049]    Shared processing is executed for a predetermined duration of time called a “time slice” (step  811 ) at a time. After the lapse of the time slice during the execution of shared processing, the Scheduling Unit  423  updates the Dispatch Priority Table  54   n  corresponding to the physical CPU that has been executing shared processing (step  812 ). It also interrogates the Guest OS Monitoring Unit  51  to find out whether the physical CPU that has been executing the shared processing was running an LPAR in idle state at the start of the time slice (step  813 ). If this physical CPU was indeed running an LPAR in idle state at the start of the time slice (step  813 Y), the Scheduling Unit  423  does not update the Dispatch Counter Table  521 . If this physical CPU was running an LPAR in busy state (step  813 N), it updates the Dispatch Counter Table  521  (step  814 ). 
         [0050]    Subsequently, the Scheduling Unit  423  checks whether shared processing has been completed (step  815 ), and if so, terminates the scheduling process (step  816 ). If shared processing has not been completed, it proceeds to determine the suitability of continuing to use the current physical CPU for shared processing for the next time slice, by checking whether the LPAR to which the current physical CPU is allocated is still in idle state (step  817 ). If it is still in idle state, the Scheduling Unit  423  is going to use the same physical CPU; if it has come out of idle state in the meantime and is now in busy state, the Scheduling Unit  423  releases this physical CPU (step  818 ). The Scheduling Unit  423  then proceeds to interrogate the Dispatch Counter Table  521  to see if a predetermined length of refreshing interval, at which it is regularly refreshed (step  820 ), has elapsed (step  819 ), and if the length of refreshing interval has not elapsed, goes back to step  803  to repeat the foregoing process. 
         [0051]      FIG. 9  illustrates an example of how shared processing is scheduled. The mnemonic names “OS 0 ,” “OS 1 ,” “OS 2 ,” and “OS 3 ” represent the guest OSes running on LPAR 0 , LPAR 1 , LPAR 2 , and LPAR 3 , respectively. At the initial point, OS 1  is in idle state. When, at a certain point in time  901 , a request for shared processing arises, it is dispatched to physical CPU 1  that is processing LPAR 1 . As long as OS 1  (running on physical CPU 1 ) is in idle state, shared processing is executed on physical CPU 1  with a view to making the most of it, while the other OSes, i.e., OS 0 , OS 2 , and OS 3  concentrate on LPAR processing without being bothered by shared processing. If a request for processing on OS 1  arises at a later point in time  902 , the physical CPU 1  is released at the next timing for scheduling and is put in the state of processing LPAR 1 , to which it is originally allocated. In this manner, the Scheduling Unit  423  ensures, by allocating all the physical CPUs uniformly, that shared processing is brought to completion without using any particular physical CPU exclusively ( 903 ). 
       Embodiment 2 
       [0052]      FIG. 10  is an exemplary diagram showing the configuration of a computer system according to another embodiment of the invention. According to this embodiment, shared processing, which in this case is I/O processing requested by any of the guest OSes, is not executed by any of the LPARs on which guest OSes run. Instead, a dedicated LPAR  1001 , designated as LPARA in  FIG. 10 , is provided upon which the driver OS for executing I/O processing for all the LPARs runs. This configuration allows more than one I/O device to be shared by a plurality of LPARs, thereby increasing the efficiency of I/O processing, especially by introducing an intermediary buffer area. Since the driver OS executes more than one instance of I/O processing  1002 , it is generally necessary to allocate a physical CPU longer than in ordinary instruction processing. The configuration according to this embodiment, however, allows shared processing to be executed even in such situations without holding up the resources of any particular one of the physical CPUs running LPARs  430  through  433  for an extensive period of time, while keeping the priority of the driver OS (which runs on a particular LPAR) high. 
         [0053]    Although only two embodiments of the invention have been disclosed and described, it is apparent that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, it is to be understood that the invention is not to be limited by the specific illustrated embodiments but only by the scope of the appended claims.