Patent Publication Number: US-5835767-A

Title: Method and apparatus for controlling available processor capacity

Description:
FIELD OF THE INVENTION 
     The present invention generally relates to controlling a processor and, more particularly, it relates to controlling the available capacity of a processor in a system. 
     BACKGROUND OF THE INVENTION 
     Although seemingly unusual, there are situations in practice where it is important that the available capacity of a processor (e.g. CPU) be limited within a system. This situation occurs, for example, when a user, purchasing processing capacity per unit processor, desires processing capability less than the full capacity of a single processor (i.e., some fraction of a unit) due to perhaps cost concerns. 
     One technique for controlling processor capacity within a system includes varying the frequency of the system clock. (Generally, system clocks can be decreased in frequency but not increased as systems are designed with worse case propagation delays in mind.) Decreasing clock frequency, however, changes not only total system capacity but also the processor time to do a fixed amount of work. A significant drawback of this technique is that changing the system clock frequency changes the capacity of all processors in the system and often adversely impacts the input/output capacity of the system. 
     Another technique for controlling processor capacity is to use processor microcode to control instruction rate. This will also change processor time. Different microcode can be used in each processor in the system but this compounds the processor time problem. 
     Still another technique uses physically different processors configured in one system, but, practically speaking, this is essentially the same as using different microcode. 
     SUMMARY OF THE INVENTION 
     The present invention involves limiting the available capacity of a processor (e.g., CPU) by alternately making it available and unavailable for tasks. The invention includes a process for wasting time and a process for managing and scheduling tasks such that, when a CPU is to be made unavailable for tasks, the scheduling process causes the time wasting process to execute on the CPU. 
     BRIEF DESCRIPTION OF THE FIGURES 
    
    
     The aspects, features and advantages of the present invention will be more readily understood from the following detailed description when read in conjunction with the accompanying drawings, in which: 
     FIG. 1 shows a timeline generally indicating the available and unavailable time periods of a reduced capacity processor. 
     FIG. 2 shows a high level functional block diagram of an exemplary system on which the present invention is implemented. 
     FIG. 3 shows a flowchart illustrating the high-level functional steps performed when controlling the capacity of one of the processors in FIG. 2. 
     FIG. 4 shows the flowchart of FIG. 3 with additional detail for handling special cases. 
     FIG. 5 shows the timeline of FIG. 1 compared to a timeline illustrating an inter-processor communication (IPC) during the available time period. 
     FIG. 6 shows a timeline illustrating two complete cycles of the time periods shown in FIG. 1. 
     FIG. 7 shows a timeline illustrating an IPC during an unavailable time period shown in FIG. 6. 
     FIG. 8 shows a timeline illustrating a variation of the timeline shown in FIG. 7 where an IPC starts during an unavailable interval. 
     FIG. 9 shows the timeline of FIG. 6 compare to a timeline illustrating a memory dump extending from an unavailable period to an available period. 
     FIG. 10 shows the timeline of FIG. 6 compared with a timeline illustrating an additional example of an IPC. 
     FIG. 11 shows the timeline of FIG. 6 compared with a timeline illustrating an additional example of a memory dump which extends from an available interval to an unavailable interval. 
    
    
     DETAILED DESCRIPTION OF THE DRAWINGS 
     Overview 
     The present invention involves intentionally limiting the available capacity of a processor within a system by controlling the amount of time the processor is available for performing tasks (e.g., system or user stacks). As shown in FIG. 1, a complete cycle of time is the interval (or time period) from time T0 to time T2. In the exemplary embodiment of the present invention, the time duration from T0 to T2 is approximately 10 to 200 milliseconds. 
     The time from T0 to T1 is an available time interval and the time T1 to T2 is an unavailable time interval. The available time interval is when the processor can be used. When the available time interval is 50% of the complete cycle interval, the processor can be used 50% of the time. In the example of FIG. 1, the effective or usable capacity of the processor is 50% of its full capacity. 
     In the exemplary embodiment of the present invention, the ability to control individual processor availability is derived from a scheduling process which is executing continuously. The scheduling process, which implements a basic priority scheme, directs processors, designated as reduced capacity processors, to execute a high priority task which, at least in part, is essentially for wasting time. This high priority task for wasting time is designed to execute for predetermined amounts of time in order to effectively control the percentage by which the available capacity of a processor is reduced. 
     If more than one processor is configured in the system, the present invention allows for the capacity of each processor to be controlled separately. For example, if system specifications call for processing capability equivalent to 11/2 processors, with the present invention, two processors can be configured such that one is at full capacity and the other at half capacity or both can be configured to operate at 3/4 capacity. 
     Exemplary Embodiment 
     FIG. 2 shows a high level functional block diagram of a system on which an exemplary embodiment of the present invention is implemented. In FIG. 2, there is at least one central processor unit (CPU) 210a. In the exemplary embodiment of the present invention, the CPU 210a is the unit on which user and operating system tasks are executed. CPU 210a is coupled to a main memory 212. 
     In addition, as shown in FIG. 2, a task control processor (TCP) 214 is also coupled to main memory 212. In the exemplary embodiment of the present invention, the TCP 214 is responsible for task and processor scheduling. The CPU 210a and TCP 214 can communicate by way of messages passed via main memory 212. 
     In the exemplary embodiment, certain functions such as inter-processor communication (IPC) and memory dumps are handled by a special process running on a CPU 210a. In the exemplary embodiment of the present invention, this process is known as the answering service process. 
     Each CPU 210a-210n has an individual answering service process associated with it. Although normally processes or tasks can execute on any available processor, the answering service process only executes on its respective CPU 210a. The scheduling process, in the exemplary embodiment, executes on the TCP 214. 
     In the exemplary embodiment of the present invention, as mentioned, TCP 214 is the processor on which the scheduling process executes. Although some details of TCP 214 and its scheduling functions are described herein, U.S. Pat. Nos. 4,779,194, 4,796,178 and 5,010,482 describe additional detail and are herein incorporated by reference. 
     When a particular answering service process is ready to execute, the scheduling process running on TCP 214 starts it executing on its associated processor. As the answering service process is high priority, it preempts most any task that may be executing on the processor at that time. 
     When the answering service process first starts, it determines if it is running on a full capacity processor or on a reduced capacity processor. On a full capacity processor, a first branch of the answering service process is used. On a reduced capacity processor, a second branch of the answering service process is used. It is within this second branch of the answering service process where the individual processor CPU 210a is effectively taken off-line for a predetermined amount of time. The second branch of the answering service process is also referred to as the &#34;soaker&#34; process. 
     In the exemplary embodiment of the present invention, a procedure called CPUHOBBLED is called to determine which branch of the answering service process to use and at what percentage of full capacity a processor is designated to operate. 
     The psuedo-code for the answering service process is as follows: 
     
         __________________________________________________________________________
IF NOT CPUHOBBLED (EMODE.sub.-- MACHINEINFO2, HOBBLE.sub.-- FACTOR)       
THEN                                                                      
&lt;Regular Process&gt;                                                         
ELSE                                                                      
&lt;&#34;Soaker&#34; Process&gt;                                                        
__________________________________________________________________________
 
    
     As shown below, several initialization calculations are performed in preparation for executing the second branch of the answering service process. 
     1. CPUHOBBLED determines if the CPU is a reduced capacity processor via EMODE --  MACHINEINFO2 and if so, returns available capacity, as a percentage, in HOBBLE --  FACTOR. This is converted to the ratio of the complete cycle interval and the available interval which simplifies the other calculations. 
     
         HOBBLE.sub.-- FACTOR:=100/MAX(HOBBLE.sub.-- FACTOR,1); 
    
     2. The end of the first available interval (T1) is calculated as CLOCK+5 SECONDS and stored in AVAIL --  END. A long first available interval allows full processor capacity during early initialization or just after the processor has been acquired into the partition. 
     3. The end of the first unavailable interval (T2), which is also the end of the first cycle, is made the same as the end of the first available interval and is stored in CYCLE --  END. 
     After the above initialization calculations, the &#34;soaker&#34; aspect can now function. 
     Referring back to normal operation, the first branch of the answering service process, represented below, is a loop which responds to memory dump requests and IPC requests. 
     
         ______________________________________                                    
WHILE BOOLEAN (MYUSAGE.WRONGNUMBER) DO                                    
BEGIN                                                                     
WAITANDRESET (LISTEN.sub.-- EVENT CPMNO!);                                
CHECKANDHANDLEDUMPS;                                                      
LISTEN;                                                                   
END;                                                                      
______________________________________                                    
 
    
     This loop continues to use the full capacity of enabled processors. The answering service process, once started, waits (via a WAITANDRESET) on a LISTEN --  EVENT of its respective processor. When awakened, ANSWERINGSERVICE first checks to see if the processor is needed for a memory dump. ANSWERINGSERVICE next calls the LISTEN procedure to handle inter-processor communication. ANSWERINGSERVICE loops by doing the wait, the memory dump check, and the call on LISTEN until it is informed that its processor is no longer in the partition. This general implementation of ANSWERINGSERVICE is referred to as the first branch of the answering service process. The processor time consumed by this process is accumulated in a system wide account &#34;listen&#34; (LISTENCLOCKX). 
     As mentioned, in the exemplary embodiment of the present invention, a second branch of the answering service process has been developed to control processors that are designated to run at a reduced capacity. 
     The second branch has two major functions. First, it performs the same functions as the first branch of the answering service process of answering memory dump requests and inter-processor communication (IPC) requests. Second, it has the added responsibility of providing reduced capacity by making a specified percentage of processor time unavailable to other processes. Although, it should be noted that, in the exemplary embodiment of the present invention, even while the processor is so-called &#34;unavailable&#34;, memory dump and IPC requests are responded to as described below. 
     In general, the method employed by the second branch of the answering service process for limiting processor capacity is to alternately make the processor available for processing and not available for processing as illustrated in FIG. 1. In the exemplary embodiment of the present invention, this technique is applied on a per processor basis. Therefore, in a multiple processor environment, all processors can be operating with different effective capacities. 
     FIG. 3 is a flowchart illustrating a high level flow for the capacity control process illustrated in the time line of FIG. 1. As shown, at step 310, times T1 and T2 are calculated and the processor is marked as available. At step 312, the process waits until T1 then marks the processor as unavailable at step 314. When the processor is marked as unavailable, it executes a set of predetermined instructions to waste time, step 316. Finally, at step 318, the time is checked: if it is T2, the the process loops back to step 310, otherwise the process loops back to step 316 to waste more time. 
     By definition, processor time spent performing answering service functions (IPCs and memory dumps) is considered available time. However, in the exemplary embodiment of the present invention, requests to perform answering service functions can occur at any time. That is to say, a request can start or end during what otherwise would be unavailable time. For example, when the processor time needed for inter-processor communication over extended periods of time exceeds the time available on a reduced capacity processor, inter-processor communication receives all the time that it needs. On balance, in the exemplary embodiment, it was determined that it is better to delay the enforcement of capacity reduction rather than delay inter-processor communication. 
     In the exemplary embodiment, processor time spent performing answering service functions during what should be unavailable time is borrowed from the next available interval. This is done, for example, by extending the end point (time T2) of the current unavailable interval and shortening the next available interval by the same amount. To handle this situation, special case handling of this type of situation is built into the second branch of the answering service process. 
     FIG. 4 shows the flowchart of FIG. 3 modified to include the special case where available time is borrowed from subsequent intervals. As shown in FIG. 4, after step 310, the process waits for either T1 (like step 312 of FIG. 3) or an answering service request, step 410. If there is an answering service request, step 412, then the process performs the request and calculates the available time error, steps 414 and 416. After performing the request, the process branches back to step 410. 
     The available time error shown in FIG. 4 is the amount of time beyond time T1 spent performing an answering service function. The unavailable error in FIG. 4 is the amount of time during an unavailable interval (the time before time T2) spent performing an answering service function. The next available interval is shortened by the sum of the available time error and the unavailable time error. 
     The general outline of the second branch of the answering service process is represented below: 
     
         ______________________________________                                    
WHILE BOOLEAN (MYUSAGE.WRONGNUMBER) DO                                    
IF WAITANDRESET (((AVAIL.sub.-- END - CLOCK)/ONESECOND),                  
            LISTEN.sub.-- EVENT CPMNO!) EQL 1 THEN                        
BEGIN % TIME WAKE UP                                                      
&lt;Unavailable time process&gt;                                                
END                                                                       
ELSE                                                                      
BEGIN % EVENT WAKE UP                                                     
&lt;IPC or Memory dump during available time&gt;                                
END                                                                       
______________________________________                                    
 
    
     As seen, the second branch also has branches which allow the process to wake up on time or to wake up on an event. In the exemplary embodiment, the TCP 214 wakes up the answering service process and informs it whether the wake up is due to time or an event. The WAITANDRESET portion is essentially the available time period. The wake up on time is essentially the unavailable time period where the wake up on event is, for example, an IPC request during an available time period. When this branch wakes up on an event, checks for a memory dump and/or IPC requests are made. There are also some additional steps. 
     In the exemplary embodiment of the present invention, because ANSWERINGSERVICE initially sets a utilization class to LISTENCLOCKX, one of the first steps performed by the second branch is to change the utilization class to BLACKHOLECLOCKX and the last thing it does is change the utilization class back to LISTENCLOCKX. It should be noted that the utilization class, however, is changed to LISTENCLOCKX for the IPC request processing and then back to BLACKHOLECLOCKX. 
     As described above with reference to FIG. 4, answering service requests may occur or extend into an otherwise unavailable time period. For example, if an IPC request extends into an unavailable interval, the amount of the intrusion is calculated and stored in AVAIL --  ERR. The store of CLOCK into CLK establishes the end of the IPC period (Ty). 
     An exemplary psuedo-code for the wake up on event branch is shown below. 
     
         ______________________________________                                    
BEGIN % EVENT WAKE UP                                                     
CHECKANDHANDLEDUMPS;                                                      
AVAIL.sub.-- ERR:=-MAX (AVAIL.sub.-- END, CLOCK);                         
SET.sub.-- TCP.sub.-- CLASS (SNR, PIB, LISTENCLOCKX, 0);                  
LISTEN;                                                                   
SET.sub.-- TCP.sub.-- CLASS (SNR, PIB, BLACKHOLECLOCKX, 0);               
AVAIL.sub.-- ERR:=*+MAX (AVAIL.sub.-- END, CLK);                          
END                                                                       
______________________________________                                    
 
    
     Waking up on time, signals the end of an available interval and the start of an unavailable interval (e.g., T1). The unavailable time process has three parts. 
     1. Initialization involves any needed adjustment to the end of the unavailable interval (T2). The adjustment is the result of intrusion into the unavailable interval by the preceding available interval. The adjustment is limited to a maximum value of the length of an available interval. 
     2. The process loops checking for the end of the unavailable interval, a memory dump request, and an IPC request. The time consumed by IPC that occurs before the original end of the unavailable interval will extend the unavailable interval. This time is borrowed from the next available interval. 
     3. The end of the unavailable interval is the end of a cycle. New values for the length of an available interval, the end of the next available interval, and the end of the next unavailable interval are calculated. 
     An exemplary psuedo-code for the wake up on time branch is shown below. 
     
         __________________________________________________________________________
BEGIN % TIME WAKE UP                                                      
CLK:=CLOCK;                                                               
IF AVAIL.sub.-- ERR EOL 0 THEN                                            
CYCLE.sub.-- END:=*+MAX(MIN((CLK-                                         
AVAIL.sub.-- END) ,NOMINAL.sub.-- AVAIL) ,0);                             
AVAIL.sub.-- ERR:=MIN (AVAIL.sub.-- ERR, NOMINAL.sub.-- AVAIL);           
CYCLE.sub.-- END:=*+AVAIL.sub.-- ERR;                                     
WHILE CLK LSS CYCLE.sub.-- END + LISTEN.sub.-- ERR DO                     
BEGIN                                                                     
THRU 600 DO                                                               
BEGIN                                                                     
PURGE.sub.-- ACAM;                                                        
CHECKANDHANDLEDUMPS;                                                      
IF COMWORD CPMNO! ISNT 0 THEN                                             
        BEGIN                                                             
        LISTEN.sub.-- ERR:=-MIN (CLOCK, CYCLE.sub.-- END);                
        SET.sub.-- TCP.sub.-- CLASS (SNR, PIB, LISTENCLOCKX, 0);          
        LISTEN;                                                           
        SET.sub.-- TCP.sub.-- CLASS (SNR, PIB, BLACKHOLECLOCKX, 0);       
        LISTEN.sub.-- ERR:=*+MIN (CLOCK, CYCLE.sub.-- END);               
        END;                                                              
END;                                                                      
CLK:=CLOCK;                                                               
END;                                                                      
NOMINAL.sub.-- AVAIL:=ONESECOND DIV SBPSLICERATE;                         
AVAIL.sub.-- END:=MIN ((CLK-(CYCLE.sub.-- END+LISTEN.sub.-- ERR)),        
NOMINAL.sub.-- AVAIL)+NOMINAL.sub.-- AVAIL - AVAIL.sub.-- ERR             
- LISTEN.sub.-- ERR;                                                      
CYCLE.sub.-- END:=CLK + NOMINAL.sub.-- AVAIL * HOBBLE.sub.-- FACTOR;      
AVAIL.sub.-- ERR:=0;                                                      
LISTEN.sub.-- ERR:=0;                                                     
AVAIL.sub.-- END:=AVAIL.sub.-- END + CLOCK;                               
END                                                                       
__________________________________________________________________________
 
    
     Several statements in the code are described below. 
     1. The &#34;THRU 600 DO&#34; reduces the frequency of clock fetches which are messages to the input/output module (IOM). The value 600 was obtained experimentally. Larger values cause the reduced capacity to be greater than the specified percentage. 
     2. The &#34;PURGE --  ACAM&#34; purges an associative memory (not shown) used in the exemplary embodiment of the CPU. 
     As described above, the technique used for reducing capacity is to alternately make the processor available for use by other processes and then make the processor unavailable. 
     Referring to FIGS. 5-11 examples illustrating possible scenarios are described. 
     The time line of FIG. 5 shows an IPC occurring entirely during available time. The interval T0 to T1 is considered available time. Point T1 does not change just because part of the available time was used for IPC. At point T0, a &#34;soaker&#34; process waits on both time and its processor&#39;s listen event with the time value being the difference between T1 and T0. 
     At point Tx, the &#34;soaker&#34; process wakes up on the listen event and checks for a memory dump request and for an IPC request. At point Ty, all requests have been completed so the soaker process returns and continues to wait on time and listen event. The time value for this wait period is the difference between T1 and Ty. 
     The following examples require consideration of more than one cycle. 
     The time line of FIG. 6 shows two complete cycles. The intervals T0 to T1 and T2 to T3 are available time. The intervals T1 to T2 and T3 to T4 are unavailable time. 
     As shown in FIG. 7, if an IPC request occurs during an unavailable period, the unavailable period is suspended and restarted after the IPC completes. The IPC time is considered available time which is borrowed from the next available interval. 
     If, as shown in FIG. 8, the IPC starts during an unavailable interval but ends after the unavailable interval would have ended, only the time from when IPC starts until when the unavailable interval would have ended is borrowed. In this case, as shown in FIG. 8, point T2 is shifted to the right on the time line but never goes beyond point T3. 
     In the exemplary embodiment of the present invention, memory dump requests do not borrow from the next available time interval. If a memory dump request starts during an unavailable interval and completes before time T2, the unavailable period continues. 
     If, however, as shown in FIG. 9, the memory dump request completes after time T2, points T2 and T3 are shifted to the right such that T2 coincides with the completion of the dump. 
     As shown in FIG. 10, an IPC request which starts during an available interval at time Tx, continues until time Ty. As seen, time Ty is after what should have been the end of the available interval. The unavailable interval starts when the IPC request ends and extends into what should have been the start of the next available interval. The amount borrowed from the T2 to T3 available interval is equivalent to the amount added to the T0 to T1 available interval. 
     As shown in FIG. 11, a memory dump request starts during an available interval and effectively ends the available interval. At the completion of the memory dump, the next unavailable interval starts. Time is not borrowed from the available interval T2 to T3. 
     It should be noted that, in the above examples, the description of each scenario is examined in isolation. In practice, however, multiple IPC requests are generally handled during each complete cycle. 
     It should also be noted that cycle time (i.e., available time versus unavailable time) has a direct impact on system performance. If the cycle time is too long, an interactive application might exhibit very choppy response times. If the cycle time is too short, the overhead of stack switching for CPUs 210 can become significant since a process switch occurs at points T0, T1 and T2. 
     In addition to cycle time, slice rate can have a similar impact on system performance as the cycle time. TCP 214, in the exemplary embodiment, switches between tasks of equal priority based on the slice rate. Presently, the slice rate is limited to the range of 10 to 200 slices per second with a default of 60. The available time will be the same as the slice time, which will fall in the range of 5 to 100 milliseconds. 
     In the exemplary embodiment of the present invention, processor time is accounted for. For the regular answering service process, processor time is accumulated in a &#34;listen&#34; utilization account. For, the &#34;soaker&#34; process, processor time is accumulated in a &#34;reduce capacity&#34; utilization class. In the exemplary embodiment, the accounting for processor utilization by class is done by the TCP 214. It should be noted that, to accurately track how much time a processor is available, the soaker process changes the utilization class to &#34;listen&#34; before calling LISTEN and changes the utilization class back to &#34;reduce capacity&#34; after returning from LISTEN. 
     Processor resource utilization can be reported in many ways. It can be reported through an operator interface. It can also be retrieved programmatically through operating system interfaces (e.g., GETSTATUS and SYSTEMSTATUS). 
     It should be noted that, in the exemplary embodiment of the present invention, each processor in the system of FIG. 2 has associated with it a style PROM on a state access module (SAM) card (not shown). Among the many items contained in the style PROM is an indicator that designates the associated processor as full capacity or reduced capacity. When the processor is initialized, the capacity indicator is moved into a processor identification state which is accessed when the determination is needed. 
     The present invention, in its exemplary form, although employed on the Unisys A series computer systems (e.g., A19 series), has applicability to many other computer systems. 
     Although illustrated and described herein with reference to certain specific embodiments, the present invention is nevertheless not intended to be limited to the details shown. Rather, various modifications may be made in the details within the scope and range of equivalents of the claims and without departing from the spirit of the invention.