115
`United States Patent
`6,148,324
`(11] Patent Number:
`
`[45] Date of Patent: Nov. 14, 2000
`Ransom etal.
`
`US006148324A
`
`
`
`54]
`
`PRIORITIZED LOAD BALANCING AMONG
`NON-COMMUNICATING PROCESSESIN A
`TIME-SHARING SYSTEM
`
`Inventors: Antonio Juan Ransom, Bolingbrook;
`Dennis James Wiest, Naperville, both
`of Ill.
`
`Assignee: Lucent Technologies, Inc., Murray
`Hill, NJ.
`
`Appl. No.: 09/002,982
`
`Filed:
`
`Jan. 5, 1998
`
`Tt, C17 eeccecccccsccescssseessssssesssssesesssssesesussessseee G06F9/00
`US. C1. eee ceecccesteseeesseeseseeseseaenes 709/105; 709/103
`Field of Search oo.eeeeeeeees 709/102, 103,
`709/104, 105
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,481,583
`5,309,501
`5,519,867
`5,530,860
`5,550,898
`5,615,249
`5,652,885
`5,655,120
`5,845,116
`
`11/1984 Muller oe ee ceceeeteeeeeeee 709/104
`5/1994 Kozik et al.
`.
`.
`5/1996 Moeller et al.
`6/1996 Matsuura 0... eeeeeeteeereeee 709/105
`8/1996 Abbasi et al.
`.
`3/1997 Solondz .
`.
`7/1997 Reed et al.
`8/1997 Witte et al. .
`12/1998 Saito et abe vee eeeeeeeeeeees 709/103
`
`OTHER PUBLICATIONS
`
`Armand et al., “Muti-threaded Processes in Chorus/Mix”,
`Chorus Systemes, Apr. 1990—pp. 1-15.
`Stevens, “UNIX Network Programming”, 1990 Prentice
`Hall P T R—pp. 72-75.
`
`Primary Examiner—Alvin E. Oberley
`Assistant Examiner—Van Nguyen
`
`[57]
`
`ABSTRACT
`
`A method and apparatus for prioritized load-balancing
`among non-communicating processes in a time-sharing sys-
`tem involves a Load Balancing Repository (LBR) which
`interfaces with each processthat is actively addressed by the
`CPU. A scheduler within each process provides the LBR
`with a load distribution for that process representing the
`ratio of high-priority sub-task load to low-priority sub-task
`load. The LBR determines a target ratio in the form of an
`aggregate load distribution ratio. The target ratio is reported
`back to each active process. For processes which are occu-
`pied with a relatively low proportion of high priority sub-
`tasks and which therefore exhibit a load distributionthat is
`below the target ratio, the process scheduler will give up a
`portion of the time slice allotted to that process by the
`operating system when the load distribution of that process
`reachesthe target ratio. Thus, CPU resources will be applied
`more frequently to processes which are occupied with a
`relatively high proportion of high priority sub-tasks.
`
`17 Claims, 5 Drawing Sheets
`
`100
`\
`
`
`LOAD BALANCE
`REPOSITORY
`122
`
`
`(LBR)
`
`APPLICATION PROCESS1
`
`
`
`APPLICATION
`APPLICATION
`PROCESS
`PROCESS
` SCHEDULER
`
`n
`2
`
`
`
`
`ie
`
`
`
`
`
`SAMSUNG 1043
`
`M
`
`120
`
`OPERATING SYSTEM
`
`1120
`
`444
`
`CPU
`
`
`
`110
`
`
`
`SAMSUNG 1043
`
`1
`
`

`

`U.S. Patent
`
`Nov. 14, 2000
`
`Sheet 1 of 5
`
`6,148,324
`
`100
`
`
`LOAD BALANCE
`422 REPOSITORY}_499
`
`(LBR)
`
`
`APPLICATION PROCESS1
`
`
`
`
`APPLICATION
`APPLICATION
`PROCESS
`
`
`
`
`PROCESS SCHEDULER
`
`2
`
`

`

`U.S. Patent
`
`Nov. 14, 2000
`
`Sheet 2 of 5
`
`6,148,324
`
`LOAD BALANCE
`REPOSITORY
`(LBR)
`
`
`
`
`
`
`
`
`FOR EACH PROCESS (i)
`AND EACH PRIORITY LEVEL
`(j), OBTAIN THE CPU LOAD
`L(i, j) FROM THE
`REPORTING SUB-TASK
`
`200
`
`210
`
`
`
`HAS THE REPORTING
`INTERVAL EXPIRED ?
`
`
`
`212
`
` DETERMINE THE
`AGGREGATE LOAD FOR
`EACH PRIORITY LEVEL (j)
`
`
`AGG(j) = L(1, j) +L(2, j) ... L(n, j)
`
`
`
`
`214
`
`COMPUTE THE TARGET RATIOS
`AGG(1) : AGG(2)
`AGG(1) : AGG(3)
`AGG(1) : AGG(n)
`
`
`
`
`SEND THE TARGET RATIOS
`TO THE REPORTING SUB-
`
`
`TASK OF EACH PROCESS(i)
`
`216
`
`FIG. 2
`
`3
`
`

`

`U.S. Patent
`
`Nov. 14, 2000
`
`Sheet 3 of 5
`
`6,148,324
`
`SCHEDULER
`
` PROCESS
`
`
`
`
`
`
`OBTAIN AGGREGATE
`SCHEDULE AND EXECUTE
`LOAD DISTRIBUTION
`
`ALL HIGHEST PRIORITY
`
`
`FROM LBR
`SUB-TASKS THAT ARE READY
`
`
`
`SUB-TASKS
` SCHEDULE AND EXECUTE
`
`PRIORITY SUB-TASKS?
` ARE THERE NEW HIGHER
`
`NEXT LOWER PRIORITY
`
`FIG. 3
`
`DETERMINE THE
`CURRENT LOAD
`DISTRIBUTION
`
`
`340
`
`
`
`
`IS THE CPU TIME SLICE FOR\YES
`THIS PROCESS EXPIRED ?
`
`
`
`
`
` IS THE CURRENT LOAD
`DISTRIBUTION RATIO LOWER
`
`THAN THE AGGREGATE
`DISTRIBUTION RATIO ?
`
` RELINQISH CONTROL
`
` 360
`TO THE OPERATING
`
`SYSTEM
`
`4
`
`

`

`U.S. Patent
`
`Nov. 14, 2000
`
`Sheet 4 of 5
`
`6,148,324
`
`CPU LOAD DISTRIBUTION AT INITIAL LBR
`REPORTING INTERVAL
`
`
`
`TOTAL CPU LOAD
`CPU LOAD
`CPU LOAD
`ATTRIBUTABLE TO|ATTRIBUTABLE TO|ATTRIBUTABLE TO
`
`
`
`HIGHEST PRIORITY|LOWER PRIORITY PROCESS
`
`
`SUB-TASKS
`SUB-TASKS
`
`
`(PRIORITY LEVEL 1)|(PRIORITY LEVEL2)
`
`
`
`
`
`
`
`
`
`
`necnecate|Acc,=iaome|Asay=Ht0ne|
`
`
`
`
`AGGREGATE LOADDISTRIBUTION RATIO = AGG, :AGG, = 120:180 = 2:3
`
`FIG. 4A
`
`CPU LOAD DISTRIBUTION AT SECOND LBR
`REPORTING INTERVAL
`
`
`
`CPU LOAD
`TOTAL CPU LOAD
` CPU LOAD
`ATTRIBUTABLE TO|ATTRIBUTABLE TO|ATTRIBUTABLE TO
`
`
`
`HIGHEST PRIORITY|LOWER PRIORITY PROCESS
`
`SUB-TASKS
`SUB-TASKS
`
`
`(PRIORITY LEVEL1)|(PRIORITY LEVEL 2)
`
`
`
`
`PROCESS1
`
`PROCESS2
`
`
`
`AGGREGATE
`
`
`
`PROCESS3
`
`AGG, = 130 ms Po
`AGG, = 120 ms
`
`AGGREGATELOADDISTRIBUTION RATIO = AGG, :AGG,= 120:130
`
`FIG. 4B
`
`5
`
`

`

`U.S. Patent
`
`Nov. 14, 2000
`
`Sheet 5 of 5
`
`6,148,324
`
`CPU LOAD DISTRIBUTION AT THIRD LBR
`REPORTING INTERVAL
`
`
`
`
`CPU LOAD
`CPU LOAD
`TOTAL CPU LOAD
`ATTRIBUTABLE TO|ATTRIBUTABLE TO|ATTRIBUTABLE TO
`
`
`HIGHEST PRIORITY
`LOWER PRIORITY
`PROCESS
`
`
`SUB-TASKS
`
`SUB-TASKS
`
`
`
`(PRIORITY LEVEL 1)|(PRIORITY LEVEL 2)
`
`‘me
`yg" 22 me
`PROCESS |
`Ly4=
`som
`948 me
`PROCESS2
`
`
`
`
`PROCESS ¢ baa=4ome|t00 me
`
`
`AGGREGATE
`AGG, = 120 ms
`AGG, = 105 ms
`
`
`
`
`
`
`
`
`
`AGGREGATELOADDISTRIBUTION RATIO = AGG, ‘AGG= 120:105
`
`FIG. 4C
`
`CPU LOAD DISTRIBUTION AT FOURTH LBR
`REPORTING INTERVAL
`
`
`CPU LOAD
`TOTAL CPU LOAD
` CPU LOAD
`ATTRIBUTABLE TO|ATTRIBUTABLE TO|ATTRIBUTABLE TO
`
`
`
`HIGHEST PRIORITY|LOWER PRIORITY PROCESS
`
`
`
`SUB-TASKS
`SUB-TASKS
`
`
`
`(PRIORITY LEVEL 1)|(PRIORITY LEVEL 2)
`
`PROCESS 1
` PROCESS2
`
`
` PROCESS3
`
`
`[Asc,=ome|acgpesane
`
`
`AGGREGATE LOADDISTRIBUTION RATIO = AGG, :AGG, = 120:93
`
`
`
`AGGREGATE
`
`
`
`FIG. 4D
`
`6
`
`

`

`6,148,324
`
`1
`PRIORITIZED LOAD BALANCING AMONG
`NON-COMMUNICATING PROCESSES INA
`TIME-SHARING SYSTEM
`
`BACKGROUND OF THE INVENTION
`
`This invention relates generally to methods and apparatus
`for controlling digital processing systems involvingat least
`one central processing unit (CPU) and a plurality of appli-
`cation processes to be performed. Specifically, the invention
`relates to systems and techniques for balancing or distrib-
`uting CPU load among non-communicating processes in a
`time-sharing system.
`In time-sharing or multitasking environments, many
`application processes or tasks may, at a given time, compete
`for processing resources provided by one or more central
`processing units. While the CPU doesnot typically execute
`processes simultaneously,
`the processes are active in the
`sense that they share CPU resources, 1e., processing time,
`until they are completed.
`The real-time occupancy of CPU resources by an active
`application processes is referred to as the CPU “load”
`attributable to that process. In a time-sharing system,
`the
`load attributable to each active application process is often
`controlled or balanced by the operating system according to
`a predetermined protocol. The term“load balancing”refers
`to systems and techniques for allocating CPU resources
`among active application processes. Load balancing may
`accomplish different desired objectives. For example,
`the
`CPU load attributable to each application process may be
`governed according to preassigned priority levels. Other
`load-balancing techniques seek quick execution times for
`the application processes.
`In complex time-sharing or multitasking systems, hun-
`dreds of application processes, or tasks, may be in active
`competition for CPU resourcesat a given time. Eachofthese
`application processes mayinclude hundreds or thousands of
`sub-tasks. In wireless cellular communication systems, for
`example,
`telephone network access is provided through
`radio communication between mobile subscriber radiotele-
`
`phones and cell sites located within contiguous geographic
`areas. Each cell site is equipped with various hardware and
`software, including radio transceivers, antennas and control
`equipmentto facilitate signal transmission between mobile
`subscribers and the cell sites. In advanced cellular systems,
`control of a significant portion of cellular networks may be
`provided through a single CPU, the resources of which are
`shared among multiple radio control systems (RCS’s) each
`supporting multiple microcells and each relying on its own
`resident software support applications. An operating system,
`for example a UNIX-based operating system, is provided
`with a scheduler, which is responsible for sharing CPU
`resources among the RCS’s. Within each RCS, software
`applications processes are provided to control various sub-
`tasks, such as call processing,
`translation, and auditing
`associated with that RCS. These sub-tasks have varying
`levels of importance or priority. Operating systems like
`UNIXprovide for externally assigned priories for the appli-
`cation processes running under them. Typically, all software
`application processes of equal priority are allotted equal
`portions of CPU time by UNIX.
`The aforementioned prioritizing techniques for load-
`balancing may provide inadequate results when applied to
`time-sharing systems like those employed to control com-
`plex wireless communication networks. In such systems,the
`particular type of functions being addressed at the sub-task
`level should be considered for proper load-balancing. With
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`known techniques, however, this is not feasible. Typically,
`memory or processing limitations prevent
`the operating
`system from tracking detailed information at the sub-task
`level. Rather, CPU resourcesare allotted only with regard to
`the priorities assigned at
`the application process level.
`Known systems therefore provide no capability for moni-
`toring determining which application processes are, at any
`given time, devoting most of their CPU resource allotment
`to high priority sub-tasks. Nor do they provide the capability
`to monitor or determine which application processes are
`devoting most of their CPU time slice to accomplish low
`priority sub-tasks. Thus,
`the completion of high priority
`tasks in one active application process may be delayed while
`CPU resources are committed to lower priority tasks in
`another application process.
`The problem becomes more apparent when explained in
`the context of the wireless communication system example
`discussed above. Sub-tasks associated with call processing
`or translation are obviously more important than sub-tasks
`associated with auditing, maintenance or “housekeeping”
`functions: a “bottleneck” in call processing might result in
`delays to subscribers placing calls. Maintenance sub-tasks,
`on the other hand, are usually designed to fill “idle time”
`within the CPU timeslice allotted to a given process. Call
`processing and translation are “message driven” processes,
`that is, they are initiated by external events like subscribers
`placing calls and the CPU resources they require vary from
`time to time. From the operating system’s perspective, all
`application processes at a given UNIX priority level are
`competing for equal slices of CPU time. The operating
`system provides no way of determining when one RCSis
`utilizing all of its CPU resource allotment to address call
`processing, a high-priority function, while another RCS may
`be utilizing all of its CPU resources only to accomplish
`less-important auditing or maintenance functions. Thus,
`CPU resources are not allocated in a manner that favors
`
`completion of high-priority functions over
`functions at the sub-task level.
`
`low-priority
`
`It would therefore be desirable to provide a method and
`apparatus for load-balancing which allocates CPU resources
`in a mannerthat favors completion of high-priority functions
`over low-priority functions at
`the sub-task level. Such a
`system would be capable of distributing the CPU load in
`such a manner that active application processes which are
`utilizing their CPU resource allotment to complete a rela-
`tively small proportion of high-priority sub-tasks will relin-
`quish resources in favor of one or more other active pro-
`cesses that are utilizing their CPU resource allotment to
`complete a relatively high proportion of high-priority sub-
`tasks.
`
`SUMMARY OFTHE INVENTION
`
`The present invention provides a method and an apparatus
`for load balancing among non-communicating processes in
`a time-sharing system which method and apparatus achieve
`the aforementioned objectives.
`In accordance with the
`invention, CPU resources are allocated in a manner that
`favors completion of high-priority sub-tasks over comple-
`tion of low-priority sub-tasks within all active processes.
`Sub-tasks in each application process are assigned one ofat
`least two priority levels. Each process is provided with a
`reporting sub-task which interfaces with a Load Balance
`Repository (LBR). The LBR may be another process pro-
`vided under the operating system. The interface may be a
`message interface or may be accomplished through shared
`memory access amongthe processes. The reporting sub-task
`of each active application process reports the load distribu-
`
`7
`
`

`

`6,148,324
`
`3
`tion for that process to the LBR. The load distribution is
`quantified in a ratio of the CPU load,1.e., processing time,
`attributable to highest priority sub-tasks to the CPU load
`attributable to each lowerlevel of priority sub-tasks,for that
`process to the LBR.
`The LBR determines a target load distribution ratio by
`aggregating the load distribution ratios of all active pro-
`cesses and reports the aggregate load distribution back to
`each active application process as a target ratio. A scheduler
`within each process monitors the current load distribution
`ratio of that process. Processes that have a load distribution
`ratio which is lower than the target ratio are utilizing CPU
`resources for a relatively small proportion of high-priority
`sub-tasks compared to the average proportion among all
`active processes. The corresponding scheduler within such
`processesrelinquishes CPU resources when the current load
`distribution equals or exceedsthe target ratio, thus sacrific-
`ing a portion of the CPU timeslice allotted to that process
`under the operating system.
`The invention provides the advantage that the CPU load
`distribution will evolve to a state in whichactive application
`processes that expend CPUresources toward the completion
`of a relatively high proportion of lower priority sub-tasks
`receive a shorter duration of CPU time, while CPU resources
`are applied more frequently to one or more other active
`processes which are expending CPU resources towards the
`completion of a relatively high portion of higher priority
`sub-tasks.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention may take physical form in certain parts and
`steps, a preferred embodiment of which will be described in
`detail in this specification and illustrated in the accompa-
`nying drawings which form a part hereof, wherein:
`FIG. 1 is a schematic showing the organization of a
`computer platform and a prioritized load balancing system
`according to a preferred embodiment of the present inven-
`tion;
`illustrating the Load Balance
`FIG. 2 is a flow chart
`Repository (LBR) process according to a preferred embodi-
`ment of the present invention;
`FIG. 3 is a flow chart illustrating a process scheduler
`according to a preferred embodiment of the present inven-
`tion.
`
`FIG. 4A is a table representing the process load distribu-
`tions at an initial LBR reporting interval according to the
`present invention;
`FIG. 4B is a table representing the CPU load distribution
`at a second LBRreporting interval according to the present
`invention;
`FIG. 4C is a table representing the CPU load distribution
`at a third LBR reporting interval according to the present
`invention; and
`FIG. 4Dis a table representing the CPU load distribution
`at a fourth LBR reporting interval according to the present
`invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`FIG. 1 is a schematic representation of a load-balancing
`system 100 according to the present invention. Computer
`platform 110 includes hardware components such as CPU
`112 for executing instructions stored in RAM 114 and ROM
`116. CPU 112 represents either single CPU or multiple
`CPU’s operating in parallel. Those of ordinary skill will
`
`4
`recognize that FIG. 1 is a rather abbreviated depiction of
`computer platform 110, which would also typically include
`various peripheral devices and data buses. Only those ele-
`ments of platform 110 necessary for a detailed description of
`the present invention are included. Computer platform 110
`also includes operating system 118 which provides a pro-
`cedural interface between CPU 112 and a number (n) of
`application processes 122. Operating system 118 may be a
`full-function operating system such as UNIX.
`As exemplified by the schematic representation of appli-
`cation process 1, each application process 122 includes a
`number (m) of sub-tasks which are executed according to
`the administrative control of a corresponding scheduler 126.
`While only three application processes are represented in
`FIG. 1, it will be recognized that systems typical of those to
`which the invention is applicable may involve hundreds of
`active application processes.
`In turn, each process may
`include hundreds or thousands of sub-tasks.
`
`The sub-tasks within each process 122 will have varying
`priority levels depending on their associated function. The
`scheduler 126 within each process 122 will always schedule
`higher priority sub-tasks to run before lower priority sub-
`tasks. Inits simplest form, the scheduler 126 will recognize
`only two priority levels—high or low. In a more complex
`form,one of several differentpriority levels may be assigned
`to each sub-task. The present invention finds application to
`both priority schemes.
`In accordance with the present invention, LBR 120 inter-
`faces with a reporting sub-task 124 in each of processes
`(1-n). This interface may be in the form of a message
`interface implemented via operating system 118.
`Alternatively, the interface may be implemented via shared
`memory access whereby each application process 122 is
`provided with routines (not illustrated) for writing to and
`reading predetermined memory locations that are also
`accessed by LBR 120. In the case of a messageinterface, the
`LBR will function to update the average for the reporting
`processes and the aggregate load for the CPU atthe time that
`the message is received. The LBR could also function to
`update only at timed intervals for all processes. This would
`require the LBR reporting interval, described below, to be
`more frequent than the reporting interval of any application
`process 122.
`FIG. 2 is a flow chart depicting a process for implement-
`ing the LBR 120 according to the present invention. The
`flow chart describes the general logic flow for a system
`which has (n) processes and (j) priority levels of sub-tasks.
`At step 200, LBR 120 obtains the CPU load distribution
`from each active application process 122. For eachof the (n)
`active processes, the load distribution is reported to LBR
`120 by the application process scheduler 126 via reporting
`sub-task 124. The loadattributable to sub-tasks of process(i)
`at a givenpriority level(j), may be represented by LG,j). For
`example, L (1,1) represents the load attributable to priority
`level 1 (the highest priority level) sub-tasks in process 1;
`L1,2 represents the load attributable to priority level 2
`sub-tasks in process 1; and L(2,1)
`represents the load
`attributable to priority level 1 sub-tasks in process 2. CPU
`load L may berepresented by a value corresponding to the
`time, i.e. milliseconds, that the CPU is executing sub-tasks
`at a given priority level.
`Typically, operating system 118 will recognize different
`several different priority levels assigned to application pro-
`cesses (1-n). Application processes running at
`identical
`priority levels are allotted equal amounts of CPU time under
`operating system 118. The numberofpriority levels utilized
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`
`

`

`6,148,324
`
`
`
`5
`by operating system 118 may differ from the number of
`priority levels by the present invention. For example, UNIX-
`based operating systems may recognize eight (8) priority
`evels: 0 through 7. Sub-tasks running under UNIX may be
`assigned one of eight priority levels. However,
`the load
`distribution scheme of the present invention mayrecognize
`ess than all of the UNIX priority levels. In such a case, each
`application would need to map the UNIX priority levels to
`he priority levels utilized by the LBR. For instance, if the
`LBR implements a load distribution reporting scheme that
`involves only two priority levels—high and low—UNIX
`priority levels 0-3 would map to low priority while UNIX
`priority levels 4-7 would map to high priority. ‘This scheme
`permits application processes with different UNIX priority
`evels to compare loads on equivalent terms within the LBR
`implementation.
`Step 210 is a decision step where the LBR process
`evaluates whether the reporting interval has expired.
`According to a preferred embodiment of the invention, the
`LBRperiodically obtains the load distribution ratios from
`each active process (I) according to a reporting interval,
`preferably on the order of one second. If the reporting
`interval has not expired, the LBR processreturnsto step 200
`to obtain the loads L(i,j). Those of ordinary skill will
`recognize that the loads L(i,j) may change during the report-
`ing interval as various sub-tasks within the processes are
`completed or becomeactive or inactive. In the eventthat the
`reporting interval has expired, the LBR process continues to
`step 212, where aggregate load values are determined for
`each sub-task priority level. At step 212, LBR 120 aggre-
`gates the load L(j) for each priority level (j). The aggregate
`loadattributable to a given sub-task priority level (j) may be
`expressed as:
`
`10
`
`15
`
`30
`
`AGG()=L(L+L(2, J+... LOW)
`
`35
`
`(1)
`
`where n is the number of processes.
`At step 214, the LBR process determines the aggregate
`load distribution or target ratios. These represent the ratio of
`the aggregate highest priority sub-task load to each of the
`aggregate lower priority loads. At step 216, the aggregate
`load ratios are reported to the reporting sub-task of each
`process for use by the corresponding scheduler in a manner
`explained below.
`FIG. 2 represents the generalized logic flow of the LBR
`process. An example of the generalized logic flowapplied to
`a simplified system involving onlythree processes and only
`two sub-task priority levels is instructive with regard to the
`LBR process. Such an example will be explained with
`reference to FIGS. 4A, which represents the CPU load
`distribution during the initial LBR reporting interval for
`such a simplified system. Step 200 would involve the
`determination six CPU loads L(i,j)—two for each of pro-
`cesses 1, 2 and 3. Thus,at the initial reporting interval, the
`100 milliseconds (ms) load, which is the time interval
`allotted by the operating system, attributable to process 1 is
`comprised of 20 ms attributable to high priority (priority
`level 1) sub-tasks, while 80 msis attributable to lower
`priority sub-tasks (priority level 2). The loads for processes
`2 and 3 are similarly represented in FIG. 4A. The total CPU
`load is 100 msfor each process because the operating system
`allots a time slice of 100 ms to each process. While each
`processcan relinquish control to the operating system before
`the time slice expires, processes cannot increase the time
`slice beyond the interval allotted by the operating system.
`Since this example concernsthefirst LBR reporting interval,
`step 210 would, by definition, branch to step 212 where two
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`aggregate loads AGG(1) and AGG(2)—one for each sub-
`task priority level—are determined. In this example, the
`value for AGG(1) would be 150 ms and the value for
`AGG(2) would be 150 ms. At step 214, one aggregate ratio
`would be determined: AGG(1):AGG(2) which is equal to
`120:180. The aggregate load ratio in this case thus represents
`that on average with regard to all active processes (in this
`case three), more CPU loadis attributable to low priority
`sub-tasks than is attributable to high priority sub-tasks.
`FIG. 3 is a flow chart representing the logic flow in a
`process scheduler 126. At step 300 scheduler 126 obtains the
`aggregate load distributionor target ratio(s) from the LBR.
`Next, at step 310, all highest priority (i.c., priority level 1)
`sub-tasks that are ready are scheduled and executed by the
`CPU. The scheduling process then proceeds to step 320
`where the next lower priority sub-tasks are scheduled and
`executed. At step 330, the process determines whether new
`higher priority sub-tasks have becomeactive. If so, these
`sub-tasks are scheduled and executed as the process
`branches back to step 310. If no new higher priority sub-
`tasks have becomeactive, the process determines the current
`load distribution at 340. Step 345 involves a determination
`as to whether the CPU timeslice allocated to the process has
`expired.If so, the routine branches to step 360 where process
`control is relinquished to the operating system. If the CPU
`timeslice has not expired, the process continues to step 350.
`At step 350, the scheduler determines whether the current
`load distribution ratio is lower than the aggregate load
`distribution ratio, the process branches back to step 320
`where the allotted CPU resources are applied to lower
`priority sub-tasks. If the current load distributionratio is not
`less than the aggregate load distribution ratio, the process
`proceeds to step 360 where the load attributable to the
`processis adjusted by reducing the time allotment provided
`to that process.
`Those of ordinary skill in the art will recognize that the
`logic flowdepicted in FIG. 3 is applicable to systems having
`two or more sub-task priority levels. In the case of three
`sub-task priority levels, for example, the scheduling process
`would first adjust CPU load based on current load distribu-
`tion represented by the highest and second-highest priority
`levels. If all sub-tasks of highest and second-highestpriority
`levels are completed, the process would then determine the
`distribution ratio at step 350 by evaluating the CPU load
`attributable to the third-highest priority level and adjusting
`the load when the load distribution respecting the highest
`and third-highest priority levels reach the aggregate values.
`Returning to the simplified example discussed above with
`respect to FIG. 4A, The load distribution during the second
`LBRreporting interval is shownin the table in FIG. 4B. The
`CPU load distribution will be adjusted during the second
`LBRreporting interval as a result of the schedulers 126 of
`processes 1 and 2. This distribution represents a simplified
`situation in which no newhigh priority sub-tasks become
`active during the second reporting interval. Typically,
`however, new highpriority sub-tasks will becomeactive and
`the load distribution within the process will be altered.
`Importantly,
`the scheduler 126 in process 1 voluntarily
`relinquishes CPU resources after 50 ms because process 1
`will meet
`the target distribution ratio, 120:180 after 20
`milliseconds of high priority work and 30 seconds of low
`priority work are performed. The load distribution of process
`2 remains unaltered becauseits original distribution is equal
`to the target distribution ratio. Process 3 will perform 60 ms
`of high priority work and 40 msof lowpriority work, as in
`the initial LBR reporting interval. Although process 3 would
`need to perform 90 ms oflow -priority work to meet the
`
`9
`
`

`

`6,148,324
`
`7
`target distribution ratio, only 100 msoftimeis allotted by
`the operating system.
`It will be recognized that during the second LBRreport-
`ing interval, the CPU loadattributable to process 1 has been
`reduced from 100 ms to 50 ms. Therefore, CPU resources
`will be applied to processes 2 and 3 50 msearlier than would
`be the case without LBR implementation. Thus, high-
`priority sub-tasks within process 3 will be addressed earlier
`because of the LBR implementation. This results a more
`frequent application of CPU resources to processes that are
`busy with a relatively large proportion of high priority
`sub-tasks.
`
`Further iterations of the third and fourth LBR reporting
`intervals in the three-process, two-priority level example are
`shown in FIG. 4C and FIG. 4D, respectively. Referring to
`FIG. 4C, the CPU resources applied to process 1 is further
`reduced to 41.6 ms. Similarly, the CPU resources applied to
`process 2 are reduced from 100 ms (FIG. 4B) to 83.2 ms.
`Process 3, which has the highest load distribution ration
`(60:40) will receive processing time after (42+83=) 125 ms,
`or about 25 msearlier than in the previous iteration repre-
`sented by FIG. 4B. Referring to FIG. 4D, CPU resourcesare
`applied to process 3 after (38+75=) 113 ms. It will be
`recognized that further iterations of the LBR will result in
`further reduction in the aggregate load distribution ratio and
`each application process will drift toward equal load distri-
`butions.
`
`5
`
`,,
`
`8
`4. The method according to claim 1, wherein the step of
`adjusting further comprises the steps of:
`1) reporting the aggregate load distribution ratio to the
`selected process;
`li) determining a current load distribution ratio of the
`selected process; and
`iii) relinquishing a portion of the CPU resourcesallotted
`to the selected process by the operating system when
`the current load distribution ratio of the selected pro-
`cess equals or exceeds the aggregate load distribution
`ratio.
`5. The method according to claim 1, wherein the step of
`determining a load distribution ratio comprises the stepsof:
`1) determining the amount of CPU time occupied by
`highest priority sub-tasks; and
`ii) determining the amount of CPU time occupied by each
`level of lower priority sub-tasks.
`least one
`6. In a digital processing system having at
`central processing unit (CPU) for executing a plurality of
`processes, each process including a plurality of sub-tasks, a
`method of balancing load on the at least one CPU compris-
`ing the steps of:
`a) assigning either a high or low priority level to each of
`the sub-tasks;
`b) determining a load distribution ratio for each process,
`the load distribution ratio being defined as the ratio of
`the load attributable to high priority tasks to the load
`attributable to low priority tasks;
`c) determining an aggregate load distribution ratio by
`aggregating the load distributions ratios for each pro-
`cess;
`
`35
`
`d) adjusting the load attributable to at least one selected
`process whenthe load distributionratio of the selected
`process differs from the aggregate load distribution
`ratio.
`
`The present invention thus provides for a shift of CPU
`resources away from processes that are occupied with a
`relatively low proportion of high priority sub-tasks towards
`application processes that are occupied with relatively high
`proportion of high-priority sub-tasks. It is to be understood
`that the preceding description relates to only one preferred
`embodiment of the invention. Numerous other arrangements
`and modifications will occur to those of ordinary skill upon
`a reading of this specification. The scope of the invention is
`intended to cover all such arrangements and modifications
`and will be defined in the accompanying claims.
`Whatis claimed is:
`
`7. The method according to claim 6, wherein the step of
`adjusting comprises the step of limiting CPU resources
`1. In a digital processing system having a central pro-
`applied to the selected process.
`cessing unit (CPU) and an operating system for executing a
`8. The method according to claim 6, wherein the step of
`plurality of active application processes, the operating sys-
`adjusting further comprises the steps of:
`tem allotting CPU resources to each process, each process
`reporting the aggregate load distribution ratio to the
`including a plurality of sub-tasks, each sub-task being
`selected process;
`assigned one of a plurality of priority levels,
`the priority
`determining a current
`levels including a highest priority level and at least one
`selected process; and
`lower priority level, a method of balancing the CPU load
`relinquishing a portion of the CPU resources allotted to
`comprising the steps of:
`the selected process by an operating system when the
`a) determining a load distribution ratio for each process,
`current load distribution ratio of the selected process
`the load distribution ratio representing the ratio of CPU
`equals or exceeds the aggregate load distribution ratio.
`resources allotted to highest priority sub-tasks to CPU
`9. The method according to claim 6, wherein the step of
`resources allotted to each level of lower priority sub-
`determining a load distribution ratio comprises the stepsof:
`tasks within the process;
`determining the amount of CPU t