US007228546B1
`
`a2) United States Patent
`US 7,228,546 B1
`(0) Patent No.:
`McCarthyet al.
`Jun. 5, 2007
`(45) Date of Patent:
`
`(54) DYNAMIC MANAGEMENT OF COMPUTER
`WORKLOADS THROUGH SERVICE LEVEL
`OPTIMIZATION
`
`(75)
`
`Inventors: Clifford A. McCarthy, Dallas, TX
`(US); Raja Daoud, Plano, TX (US)
`
`(73) Assignee: Hewlett-Packard Development
`Company, L.P., Houston, TX (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/493,753
`
`(22)
`
`Filed:
`
`Jan. 28, 2000
`
`(51)
`
`Int. Cl.
`(2006.01)
`GO6F 9/46
`(52) U.S. Ch cc eceecteeeteeneeeeees 718/104; 718/103
`(58) Field of Classification Search ........ 718/100-108,
`718/1
`
`See application file for complete search history.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,473,773 A * 12/1995 Aman et al... 718/104
`5,675,739 A * 10/1997 Eilert et al... 709/226
`
`6,424,873 B1*
`7/2002 Przybylski ...........00. 700/42
`
`2002/0129048 Al*
`9/2002 Qiu etal. we. 707/204
`OTHER PUBLICATIONS
`
`Steere, David C. et al. “A Feedback-driven Proportion Allocator for
`Real-Rate Scheduling”, Sep. 1998, OGI CSE Technical Report
`98-014, pp. 1-14.*
`
`Stankovic, John A. et al., “The Case for Feedback Control Real-
`Time Scheduling”, 1999, Dept. of Computer Science, University of
`Virginia, pp. 1-10.*
`Automatic Control Systems by Benjamin C. Kuo, 1982, pp. 471-
`483.
`
`* cited by examiner
`
`Primary Examiner—Lewis A. Bullock, Jr.
`Assistant Examiner—Kenneth Tang
`
`(57)
`
`ABSTRACT
`
`The inventive work load manager (WLM) dynamically
`responds to changes in workload characteristics. The WLM
`bases response on performance goals set by the administra-
`tor, and manipulates the resources to achieve these goals.
`The WLM receives performance information from perfor-
`mance monitors. The WLM examinesthe information from
`the performance monitors and compares the information
`with the goals using a Proportional Integral and Derivative
`controller. Based on the comparison,
`the WLM may
`increase, decrease, or
`leave unchanged,
`the resources
`devoted to an application. If the performance of an appli-
`cation is performance is lagging, e.g., if transactions are
`taking longer than the goal, then the WLM increases the
`entitlement. If an application is over-achieving, then the
`WLMwill decrease its entitlement andallocate it to another
`application. The WLM usesan arbiter which allocates the
`resources between the different applications, based on the
`priorities of the applications. Consequently, the WLM cre-
`ates a feedback loop between application performance and
`CPUentitlements.
`
`20 Claims, 7 Drawing Sheets
`
`TO PRM 10
`
`FROM PM 23
`
`20
`ia
`
`Google Exhibit 1006
`Google Exhibit 1006
`Google v. Valtrus
`Google v. Valtrus
`
`GOALS AND PRIORITIES
`
`PID
`CONTROLLER
`
`PERFORMANCE
`
`TUNINGS
`
`

`

`U.S. Patent
`
`Jun. 5, 2007
`
`Sheet 1 of 7
`
`US 7,228,546 B1
`
`1
`
`APPLICATION
`
`12
`
`PRIORITIES
`
`PERFORMANCE
`GOALS AND
`
`TUNINGS
`
`FIG. 2
`
`

`

`U.S. Patent
`
`Jun. 5, 2007
`
`Sheet 2 of 7
`
`US 7,228,546 B1
`
`TO PRM 10
`
`FROM PM 23
`
`ye
`
`
`
`ARBITER
`
`PD
`CONTROLLER
`
`cc
`
`FIG. 8
`
`530
`
`100
`
`200
`150
`FIG. 4
`
`250
`
`350
`300
`TIME/CYCLES
`
`CHARACTERISTIC
`MEASUREMENT 4
`
`3 2
`
`1 %
`
`GOAL”
`
`

`

`U.S. Patent
`
`Jun. 5, 2007
`
`Sheet 3 of 7
`
`US 7,228,546 B1
`
`CHARACTERISTIC 9 5
`MEASUREMENT
`~"
`
`2
`
`0
`
`50
`
`100
`
`150
`
`200
`250
`300
`FIG. 5
`
`350
`
`400
`450
`500
`TIME/CYCLES
`
`GOAL””
`GOAL”
`
`0
`
`20
`
`40
`
`60
`80
`100
`FIG. 6
`
`120
`
`140
`160
`TIME/CYCLES
`
`3 2
`
`CHARACTERISTIC
`MEASUREMENT
`
`

`

`U.S. Patent
`
`Jun. 5, 2007
`
`Sheet 4 of 7
`
`US 7,228,546 B1
`
`801
`
`802
`
`ASSIGN 1 TO ALL APPLICATIONS
`IN ALL PRIORITY GROUPS
`
`RECEIVE REQUESTS FROM PID
`
`800
`
`e
`
`
`803
`
`
`EXAMINE ALL APPLICATIONS IN
`HIGHEST UNEXAMINED PRIORITY GROUP
`
`804
`
`
`WITHIN
`
`THE PRIORITY
`
`
`GROUP, CAN EACH
`
`
`ALLOCATE
`APPLICATION BE ALLOCATED ITS
`
` | REQUESTED AMOUNTS
`
`
`
`REQUESTED AMOUNT,
`
`
`
`
`
`DESIGNATE CURRENT TARGET AS THE
`
`LOWEST OF
`
`PREVIOUSLY ALLOCATED AMOUNT
`NOT USED AS PREVIOUS TARGET)
`2) REQUESTED AMOUNT OF ONE
`
`
`UNALLOCATED
`
`
`APPLICATION AMOUNT OF THE GROUP
`AMOUNTS?
`
`(NOT USED AS A PREVIOUS. TARGET)
`
`WHEREIN BOTH 1) AND 2)
`
`IGNORE APPLICATIONS THAT
`
`
`
`
` EQUALLY DIVIDE
`REACHED THEIR REQUESTED AMOUNT
`
`
`UNALLOCATED AMOUNTS
`
`
`AMONG PRIORITY
`
`
`
`GROUP APPLICATIONS
`
`CAN EACH
`
`APPLICATION BE
`
`ALLOCATED AN AMOUNT OF
`
`ENTITLEMENT TO EQUAL (OR
`EXCEED) THE CURRENT
`TARGET?
`
`
`
`
`DIVIDE EQUALLY AMONG
`APPLICATIONS
`OF THE GROUP WHOSE
`ALLOCATED AMOUNT IS
`LESS THAN CURRENT
`TARGET (IGNORING
`APPLICATIONS THAT
`HAVE REACHED THEIR
`
`REQUESTED AMOUNT)
`
`ALLOCATE AN AMOUNT TO EQUAL
`THE CURRENT TARGET (IGNORING
`APPLICATIONS THAT HAVE REACHED
`THEIR REQUESTED AMOUNT)
`
`UNALLOCATED AMOUNT
`
`
`
`

`

`U.S. Patent
`
`Jun. 5, 2007
`
`Sheet 5 of 7
`
`US 7,228,546 B1
`
`700
`
`FIG. 7
`
`LL
`
`706
`
`i
`
`ADAPTER
`
`ot
`
`at INTERFACE
`
`ee
`
`USER
`
`ADAPTER
`
`4+h-712
`NETWORK
`
`COMMUNICATIONS
`710
`
`ADAPTER
`
`AapiER
`
`Wh‘
`
`
`
`
`eriemins[«[eT
`e[o[ETF
`Praca[+[2
`Freauesr[4029[20]20205
`Fawocaton[vof29fr0]
`10]of+
`
`
`
`
`
`
`
`
`—wercemos[aa[e[>
`
`
`
`
`rrerouserSNEfro]+[isp
`
`newerauoonen[9[vel«[or
`
`
`waefisafoos
`FIG.
`10A
`
`

`

`U.S. Patent
`
`Jun. 5, 2007
`
`Sheet 6 of 7
`
`US 7,228,546 B1
`
`31 LEFT +»=10 IS TARGET
`
`A
`
`10
`
`B
`
`1
`
`C
`
`15
`
`10
`
`10
`
`15
`
`22 LEFT ——»
`
`15 IS TARGET
`
`15
`
`15
`
`15
`
`12 LEFT —+» 20 IS TARGET
`
`19
`
`19
`
`19
`
`FIG. 10B
`
`rious
`
`ecco[a[a]e[o
`
`assed[10|20]|
`
`FIG.
`
`17A
`
`C
`A
`
`10
`
`20
`
`29 LEFT
`
`TARGET IS 12
`
`12
`
`23 LEFT
`
`a)
`
`17 LEFT
`
`20
`
`12 LEFT
`
`25
`
`20
`
`TARGET IS 15
`
`20
`
`TARGET IS 20
`
`20
`
`TARGET IS 25
`
`29
`
`~ 2 LEFT
`
`TARGET IS 30
`
`29
`
`15
`
`27
`
`FIG.
`
`17B
`
`

`

`U.S. Patent
`
`Jun. 5, 2007
`
`Sheet 7 of 7
`
`US 7,228,546 B1
`
`121
`
`122
`
`123
`
`27
`
`ROUNDED R-VALUES
`
`SUBTRACTION TO
`FORM
`
`ARBITRATED
`R-VALUES
`
`CUMULATIVE
`SUMMING
`
`FIG.
`
`12A
`
`R1=33.5
`
`R2=33.5
`
`R3=353.0
`
`S1=R1+0=33.5 —> 34
`
`S2=R1+R2=67.0 > 67
`
`R1'=S$1-0=34
`
`R2'=S2-S1=33
`
`S3=R1+R2+R3=100.0—~ 100
`
`R3’=S3-S2=33
`
`FIG. 12B
`
`R1=10.1
`
`R2=20.2
`
`R3=30.3
`
`R4=39.4
`
`$1=R1+0=10.1 —» 10
`
`$2=R1+R2=30.3—» 30
`
`Ri'=$1-0=10
`
`R2°=S2-S1=20
`
`S3=R1+R2+R3=60.6—> 61
`
`R3'=$3-S2=31
`
`S4=R1+R2+R3+R4=100.0 —» 100 R4’=S4-S3=39
`
`FIG. 12C
`
`

`

`US 7,228,546 B1
`
`1
`DYNAMIC MANAGEMENT OF COMPUTER
`WORKLOADS THROUGH SERVICE LEVEL
`OPTIMIZATION
`
`TECHNICAL FIELD
`
`This application relates in general to computer systems,
`and in specific to dynamic allocation of computer resources
`among applications.
`
`10
`
`BACKGROUND
`
`Computer systems inherently have limited resources, par-
`ticularly CPU resources. These limited resources must be
`allocated among the different applications operating within
`the system. A prior allocation mechanism for allocating
`system resources to applications is a system known as
`Process Resource Manager (PRM) 10 as shownin FIG. 1A.
`It is used to partition the CPU resource 11 and various other
`resources among the different applications 12, 13, 14. The
`PRMpartitions the resources into fractions of the whole,
`which are expressed as percentages in PRM configuration,
`as shown in FIG. 1B. The fractions or pieces are then
`assigned to groups of processes, which comprise applica-
`tions. Each application would then receive someportion of
`the available resources, particularly the CPU.
`The PRMis a static mechanism, meaning that the allo-
`cation configuration is fixed by an administrator, and can
`only be changed by an administrator. In other words, the
`administrator specifies where the partitions should lie, 1.e.,
`what percent of the machine goes to application 12, appli-
`cation 13, and application 14. This information is fixed, so
`whatit cannot do is respond to changes in the needs of the
`different applications. For example, one application may be
`mostly idle, but occasionally has a large amount of work to
`do. Underthe static mechanism with fixed entitlements, this
`application would be allocated a smaller fraction of the CPU
`resources, as a larger fraction can not be justified because of
`the large amountof idle time. Consequently, when the large
`amount of work is received, then the application’s perfor-
`mance will suffer because of its low entitlement. Therefore,
`the transactions will
`take longer
`to process. Another
`example is where a transaction requires large amounts of
`resources for extended periods of time, but also has periods
`of idle time. Under the static mechanism with fixed entitle-
`
`ments, this application would be allocated a larger fraction
`of the CPU resources. Consequently, when this application
`is idle, other applications’ performances will suffer, as this
`application is assigned a large amountof resources that are
`not being used, and thus are not available for other appli-
`cations. Therefore, the other transactions will take longer to
`process. Thus, this mechanism cannot handle changesin the
`requirements of the different applications.
`Another problem is the partitioning the resources by the
`administrator. The administrator has to think in terms of the
`
`actual machine resources and the requirements of the dif-
`ferent
`applications. This
`is problematic because the
`resources and applications are operating at a lowerlevel than
`whata person typically views. Moreover, the administrator
`has to have a great deal of knowledge of the application’s
`characteristics and its resource requirements in order to
`determine whereto set the partitions. Lack of knowledge is
`typically made up with guesswork. For example, an admin-
`istrator may chooseto set application 13 at 20% of the CPU
`resources. If the users of the system complain, the admin-
`istrator may change the value later on.
`
`30
`
`40
`
`45
`
`55
`
`2
`An alternative mechanism is taught in patent by IBM,
`USS. Pat. No. 5,675,739, which is hereby incorporated by
`reference. The IBM mechanism usesa priority-based model
`to process application. In other words, high priority appli-
`cations are serviced from a queue before lower priority
`application. This mechanism can change the priorities to
`adjust processing performance.
`Therefore, there is a need in the art for a non-static system
`that does not suffer from the problems discussed above, but
`allows for partitioning of the resources among the different
`applications.
`
`SUMMARY OF THE INVENTION
`
`These and other objects, features, and technical advan-
`tages are achieved by a system and methodthat dynamically
`responds to changes in workload characteristics. The inven-
`tive mechanism also allows the administrator to think in
`
`terms of performance goals rather than machine resources
`and requirements. Consequently, the administrator defines a
`variety of performance goals with different priorities
`between them, and the inventive mechanism will make any
`necessary adjustment of the resources. For example, a goal
`for a database could bethata retrieval transaction should not
`take more than 10 milliseconds. The inventive mechanism
`
`would then manipulate the resources to achieve this goal.
`The inventive mechanism includes a work load manager
`(WLM)that receives goal information and priority informa-
`tion from a user or administrator. The WLMalso receives
`performance
`information from performance monitors,
`which are processes that monitor the performance of the
`applications. The WLM examines the information from the
`performance monitors and compares the information with
`the goals. Based on the comparison, the WLM mayincrease,
`decrease, or leave unchanged, a partial application’s parti-
`tion. If the performance of an application is lagging, e.g., if
`transactions are taking longer than the goal, then the WLM
`increasesthe entitlement. If an application is over-achieving,
`then the WLM will decrease its entitlement and allocate it to
`
`another application.
`To perform the comparison between the goals and the
`performance information, the WLM uses a control system
`that is common in control theory known as a Proportional
`Integral and Derivative controller, or PID controller. For
`further information in PID controllers, please see the refer-
`ence by Benjamin C. Kuo entitled “Automatic Control
`Systems”, 4” ed., 1982, Prentice-Hall
`Inc., Englewood
`Cliffs, N.J., 07632, ISBN 0-13-054817-0, which is incorpo-
`rated herein by reference, particularly chapter 8.2. The
`proportional component will make large changes to the
`entitlements if there are large differences between the
`entitlements and the goals, and will make small changes to
`the entitlements if there are small differences between the
`entitlements and the goals. Tuning provides the proportion-
`ality between the change to the entitlement and the differ-
`ence between the goal and the entitlement. For example, if
`the tuning constantis 10, then a one seconddifference would
`result in a 10% change, while a two second difference would
`result in a 20% change. The derivative componentis used to
`detect and compensate for ‘ramping’ changes. For example,
`if a transaction is taking 6 seconds, then 7 seconds, and then
`8 seconds, the proportional controller will never catch up
`with the difference. The integral controller stabilizes the
`effects of the proportional controller and the derivative
`controller and eliminates any steady-state error.
`The invention applies PID control principles to workload
`management for discrete operations, e.g. intervals of time.
`
`

`

`US 7,228,546 B1
`
`3
`The invention creates a feedback loop between application
`performance and CPU entitlements. Based on the reported
`information, the invention makes changes to the entitle-
`ments of the application to meet
`the stated goals. The
`changes will modify the performance of the application to
`bring the performancecloser to the stated goals. The amount
`or magnitude of the changes is based on the tuning inputs.
`If the application’s needs are not changing, then the inven-
`tion will modify the entitlements to automatically settle in to
`the resource configuration that gives the application whatit
`needs to achieve the goal. If the application’s needs are
`changing, for example due to a change in its demand, system
`resources, or other factors, then the invention will react to
`any subsequent performance changes and bring the appli-
`cations performance in line with the stated goals.
`An arbiter allocates the resources between the different
`
`applications, based on the priorities of the applications.
`Applications of equal priority are treated equally. The
`requests of higher priority applications are satisfied before
`lowerpriority applications.
`It is a technical advantage of the invention that entitle-
`ments are no longer a fixed configuration. As the applica-
`tion’s needs change, the computer will automatically adjust
`entitlements based on what the user desired through the
`stated goals. This makes it into a dynamic system.
`It is another technical advantage of the invention that an
`administrator no longer has to estimate the initial entitle-
`ments as the invention will determine the correct resource
`
`allocation to achieve the stated goal, and the system will
`converge on a certain entitlement value that achieves the
`stated performance goal.
`It is a further technical advantage of the invention that
`priorities can be assigned to the different goals. Conse-
`quently, different goals can be met based on system
`resources, e.g., with a high amount of resources, all goals
`can be met, however, with a lesser amount of resources the
`higher priority goal will be met before the lower priority
`goals.
`Tt is a still further technical advantageof the invention that
`changes to the system can be made as soon as the WLM
`detects performance changes, and action by the system
`administrator is not required.
`The foregoing has outlined rather broadly the features and
`technical advantages of the present invention in order that
`the detailed description of the invention that follows may be
`better understood. Additional features and advantages of the
`invention will be described hereinafter which form the
`
`subject of the claims of the invention. It should be appre-
`ciated by those skilled in the art that the conception and
`specific embodiment disclosed may be readily utilized as a
`basis for modifying or designing other structures for carry-
`ing out the same purposesof the present invention.It should
`also be realized by those skilled in the art that such equiva-
`lent constructions do not depart from the spirit and scope of
`the invention as set forth in the appended claims.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`For a more complete understanding of the present inven-
`tion, and the advantages thereof, reference is now made to
`the following descriptions taken in conjunction with the
`accompanying drawing, in which:
`FIG. 1A depicts a prior art resource manager;
`FIG. 1B depicts the portioning of the applications;
`FIG. 2 depicts the inventive work load manager;
`FIG. 3 depicts the components of the inventive work load
`managerof FIG. 2;
`
`15
`
`20
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG.4 depicts the inventive work load manager converg-
`ing to a goal from low entitlement;
`FIG. 5 depicts the inventive work load manager converg-
`ing to a goal from high entitlement;
`FIG.6 depicts an instability from excessive tuning for the
`proportional controller;
`FIG. 7 depicts a block diagram of a computer system
`which is adapted to use the present invention;
`FIG.8 depicts a flow chart of the operations of the arbiter
`of the work load manager of FIG.3;
`FIG. 9 depicts an example ofallocation of entitlements by
`the work load managerof FIG. 2;
`FIGS. 10A and 10B depict another example of allocation
`of entitlements by the work load manager of FIG.2;
`FIGS. 11A and 11B depict a further example ofallocation
`of entitlements by the work load manager of FIG. 2; and
`FIGS. 12A, 12B, and 12C depict the operation of the
`rounder of the work load manager of FIG.3.
`
`DETAILED DESCRIPTION
`
`FIG. 2 depicts the various components of the inventive
`system, which includes performance goals 21. Goals 21
`comprise a configuration file, which is defined by a user or
`system administrator, that describes the users preferences
`with regards to what characteristic(s) of the application is of
`interest and is being measured, whatis the desired level of
`performanceofthe application in terms of the characteristic,
`and whatis the priority of achieving this goal. A user can
`also specify time periodsfor a particular goal to be in effect.
`For example, a first application may bea first database and
`the user will specify in the configuration file that
`the
`characteristic is for a particular type of transaction to be
`completed within two seconds, and havea high priority. The
`application may also have a second goal for the same
`characteristic, e.g. the same type of transactions are to be
`completed within one half of a second, and have a low
`priority. A second application may be a second database
`which hasa similar goal as that of the first database, namely
`for a particular type of transaction to be completed within
`two seconds, and have the samepriority as the first database.
`Thus, resources would be partitioned between the two
`applications, so that the high priority goals will be met, and
`any excess resources would be givento thefirst application
`so that it can meet the lowerpriority “stretch” goal.
`The WLM 20 also receives performance information
`which describes the status of a particular characteristic or
`characteristics of each application 12, 13, 14 that is being
`monitored. This information is supplied by performance
`monitor 23. As shown in FIG.2, a single monitor is capable
`of handling multiple applications, however, a different
`embodiment of the present invention may have multiple
`monitors, each monitoring one or more applications. The
`performance monitor 23 is a small program that gathers
`specific information about the application. For example, if
`the application is a database, then a performance monitor
`measures access times for the database. This information is
`being gathered continuously while the system is operating.
`The workload managerwill sample the information at some
`interval specified by the administrator.
`The output of the workload manager, derived from the
`ongoing performancereported by the monitor and given the
`goals the user, is periodically applied to the PRM 10. The
`output of the WLM 20 is the share or entitlement allocation
`to the different resources that is assigned to each application.
`Generally, each percentage approximately equates to Yioo of
`a CPU operating second. Thus, within a second, an appli-
`
`

`

`US 7,228,546 B1
`
`5
`cation having an entitlement of 10 will receive Yio of the
`second, providedthat the application has at least one runable
`process. Note that the time received may notbe consecutive,
`but rather may be distributed across the one second interval.
`The system may have multiple CPUs. Thus,the allocation
`can be placedall on one processor, one each processor, or on
`a portion of the processors. For example, a ten percent
`allocation in a four processor system could result in forty
`percent of one processor, ten percent of each processor,
`twenty percent of two processors, or someotherallocation.
`The allocation amongthe different processors is determined
`by the PRM 10. The PRM will movethe application around
`to various CPUs, as needed to attempt to ensure that it
`achieves ten percent. Therefore, if the application has only
`one runable thread, so that it can only execute on one CPU,
`then PRM will attempt to give it 20% of one CPU (on a two
`CPU system), so that is 10% of the total universe of CPU
`availability that is out there. Multi-threaded applications can
`be assigned to more than one CPU.Theallocation allows the
`application to perform its programmed tasks. How fast and
`efficient it performs its tasks is a reflection of how much
`CPUtime it was allocated. The less CPU it is allocated, the
`less it will perform in a time period. The more CPUit is
`allocated, the more it will perform in a time period. The
`performance monitor will measure its performance, which
`will be sampled by the WLM,thus completing the feedback
`of the system.
`The workload manager accomplishes its tasks by com-
`paring the information from the performance monitor with
`the goal the specified by the user. As stated before, there may
`be multiple goals for a single application. An easy goal and
`a stretch goal is one way of looking at this situation. There
`is one PID controller instance created within the workload
`
`manager for each goal that they are trying to achieve. Some
`instances maybe looking at the same stream of performance
`data and reacting to it in different ways, depending on what
`they are trying to achieve. For example, if you look at the
`database performanceas the characteristic being measured,
`then one PID controller may be trying to get that charac-
`teristic to two seconds, while the other controller is trying to
`reduce it one second.
`Each PID instance performs the proportional-integral-
`derivative calculation on the received data to determine an
`
`R-value. The PID instance calculates R,=(KPxP,')+(KDx
`D,)+(KIxI,)+R,old. KP, KD, KI, are tuning constants 22 set
`by the user or administrator of the system.
`The (KPxP,') factor of the R equation represents the
`proportional contribution to the R value. KP is a tuning
`constant 22. P,’ is a value for the difference between the goal
`and the measured result, and is calculated as follows. P, is
`the current value of the metric or characteristic for a par-
`ticular goal “i”, and V, is the desired value or goal for that
`metric. For example, using the database example, P=1.8
`sec/transaction, and V,=2 sec/transaction is the goal. P,'
`equals P,-V,. Note that this assumes that the comparison
`operator (the ‘=’ in V,=2) is “less than”, meaning that an
`increase in entitlement shares will decrease the service level,
`i.e. decrease the measurement(see FIGS. 4 and 5). This may
`be indicated by showing the ‘=’ sign of the goal, e.g. V,=2,
`be depicted as ‘=’ for an expression of V,=2. Howeverthe
`goal would still be to have the characteristic approximately
`equal 2. If the operator is “greater than”, meaning that an
`increase in entitlement shares will increase service level, i.e.
`increase the measurement, then P,' equals V,-P,. To indicate
`a “greater than” comparison operator a ‘2’ would be used.
`Note that another way of viewing “greater than” and “less
`than” is that “greater than” means good performance has
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`larger numbers, and “less than” means good performance
`has small numbers. Generally, time-based characteristics are
`“less than” meaning the shorter the time,
`the better the
`performance, whereas transactions per second characteris-
`tics are “greater than” wherethe larger the numberthe better
`the performance. The value of KPreflects the aggressiveness
`of the user or administrator in addressing a problem. Asthe
`service level deviates, a large value of KP (aggressive) will
`provide for a big changeto try to return to the goal quickly,
`while a small value of KP (conservative) will provide for a
`small change which causes a slower return to the goal. In
`other words, KP controls convergence. The choice of that
`value is based on some empirical
`information about the
`range of possible performance levels that we can get out of
`the performance monitor. For further information, please see
`the reference by Benjamin C. Kuo entitled “Automatic
`Control Systems”, 4” ed., 1982, Prentice-Hall Inc., Engle-
`wood Cliffs, N.J., 07632, ISBN 0-13-054817-0, which is
`incorporated herein by reference.
`The (KIxI,) factor of the R equation representsthe integral
`contribution to the R value. KI] is a tuning constant 22. I, is
`a value for that accumulates previous proportional results
`over time, and is calculated as follows. I=(T,oldxIH,)+P,.
`J,old is the stored, previous value for I,. IH, is an integral
`history constant, which is another tuning constant 22. The
`integral history term should be a value between 0 and 1,
`inclusive, and serves to make older values contribute less to
`the integral contribution as time passes. Note that each time
`it is being multiplied by another factor of IH,, so the value
`is exponentially shrinking each iteration’s contribution as
`time passes. This factor accumulates the P;' terms by adding
`old values with the new value. This integrates the difference
`between the service level and the goal over time. This factor
`is useful if the service level is a little bit off over a long
`amountoftime, as this factor will eventually add up to bring
`the service level up/downto the goal. KI should be selected
`to properly set the effects of the integration factor. For
`further information, please see the reference by Benjamin C.
`Kuoentitled “Automatic Control Systems”, 4” ed., 1982,
`Prentice-Hall Inc., Englewood Cliffs, N.J., 07632, ISBN
`0-13-054817-0, which is incorporated herein by reference.
`An analogyis in the frequency domain, KI and KD will form
`a bandpass filter. As the data comes in, noise (high-low
`fluctuations in the measurements) which should be disre-
`garded. The correct choice of KI and KD will provide a
`system that is more appropriately tuned for the nature of that
`data coming in, and is not necessarily responding to short
`impulse changes in the measurements.
`The (KDxD,) factor of the R equation represents the
`derivative contribution to the R value. KD is a tuning
`constant 22. D,
`is a value for that represents changes in
`proportional values over time, in other words, how fast the
`value is changing, and is calculated as follows. D=(P/-
`Pold)/t. Pold is a previous stored value for P,. t is time
`difference between the measurements used to calculation P;'
`and P,‘old, e.g. the interval sample time or the time between
`adjustment operations of the system. This factor is useful in
`adjusting the entitlements whenthe service level is changing
`over time. The factor determines how muchextra impulse to
`add to the proportional factor, when the curve is beginning
`to change. For example, if the application is increasingly
`being used over time (ramping up), then more CPU time(via
`entitlements) would need to be devoted to the application for
`goals to be satisfied. Using only proportionality, the system
`would lag behind demand, however the derivative factor
`would then provide the extra boost needed to catch up with
`demand. KDsets the value of the ‘extra boost’, depending
`
`

`

`US 7,228,546 B1
`
`7
`on the steepness in the changes in the curve. Note that there
`is an assumption that the curve is moving in a certain
`direction, and thus, the steeper the curve, the higher the next
`value. KD should be selected to properly set the effects of
`the derivative factor. For further information, please see the
`reference by Benjamin C. Kuo entitled “Automatic Control
`Systems”, 4” ed., 1982, Prentice-Hall
`Inc., Englewood
`Cliffs, N.J., 07632, ISBN 0-13-054817-0, which is incorpo-
`rated herein by reference.
`The values for the proportional, integral, and derivative
`components are then addedto the stored previous value for
`R, R,old. The result is the R value for the particular goal, R,.
`The PID controller would calculate one such value for each
`goal.
`After computations of the requirements or R values, R1,
`R2, R3, the PID controllers 24, 24, 25 pass the R values to
`the arbiter 26. In a system where the CPU resources out-
`weigh the needs of the applications running on the system,
`then an arbiter is not needed, as the R values can be directly
`provided to the PRM. However, in most systems, there are
`periods of time where the applications requirements out-
`weigh system CPUresources. Therefore, an arbiter is need
`to decide which applications are allocated the resources.
`Note that the arbiter does not actually makethe allocations,
`as this task is performed by the PRM.Instead, the arbiter
`receives the R-values from the PID controllers and then
`
`adjusts the R-values, if needed, to form adjusted R-values.
`These adjusted R-values are then provided to the PRM
`which makesthe allocations.
`
`The arbiter operates according to the flow chart 800 of
`FIG.8. Initially the arbiter assigns 801 all processes with the
`value 1 (hereinafter meaning 1% of CPU resources). The
`arbiter then samples 802 the requests or R values from the
`PID. The arbiter then examines 803 the requests associated
`with the applications in the highest priority group. It deter-
`mines 804 whether the requested amount for each applica-
`tion within the priority group can besatisfied. If so, then the
`arbiter facilitates allocation 805 of the requested entitlement
`for each application by setting the adjusted R-values equal
`to the PID R-values, and passing the adjusted R-valuesto the
`PRM,see step 809. If not, then the arbiter arbitrates between
`the different applications in a fair manner, as discussed in
`step 810. After satisfying each application in step 805, the
`arbiter then determines 806 whether there are any more
`priority groups. If so, then the arbiter returns to step 803 and
`repeats. If not, then arbiter determines 807 whether any
`unallocated resources remain. If not,
`then the arbiter is
`finished 809. The allocated values are sent to the PRM, and
`the WLMisfinishedfor this iteration. After a predetermined
`time period,
`the WLM will begin again, the WLM will
`sample values from the performance monitor, provide these
`values to the PID controllers, which in turn calculates the R
`values, which are then provided to the arbiter. If step 807
`determines that resources are available,
`then the arbiter
`divides 808 the remaining resources equally among the
`applications of the all of the priority groups that have been
`examined. Step 808 assumes that
`the arbiter is set
`to
`distribute-all. Alternatively, the arbiter can be set to hoard-
`all excess entitlements, in which case, all remaining alloca-
`tions would be assignedto an extra shares application which
`contains random processes not assigned priorities or in the
`priority groups. Note that hoarding mayallow the invention
`to operate more properly, as the assignmentof extra entitle-
`ments may cause the applications to over achieve their
`respective goals, and consequently cause the application to
`unnecessarily revise the R-values. Then the arbiter ends 809.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`If the arbiter determines in step 804 that the requested
`amountfor each application within the priority group cannot
`be satisfied, then the arbiter arbitrates between the different
`applications in a fair manner, by designating 810 a current
`target value as the lowest value of (1) the lowest of any
`previously allocated amounts (or adjusted values), wherein
`the previously allocated amounts have not been previously
`used a target value, or (2) the lowest requested amount (or
`R-value) of one application of the group, which has not been
`used for a previous current value. Note that criteria (1) and
`(2) do not
`include applications that have reached their
`requested amounts, as this will simplify the performance
`flow ofthe arbiter as depicted in FIG. 8 (namely, by reducing
`the numberof times that steps 810, 811, 812, and 813 are
`repeated). Then the arbiter determines whether the target
`amount f