Method and apparatus for adaptively blocking outgoing communication requests and adjusting the blocking factor according to the volume of requests being received in an information handling system

A method and apparatus for handling outgoing communication requests in an information handling system in which outgoing communication packets are accumulated into a block that is written to an input/output (I/O) device. For each I/O device there is generated a blocking factor representing a predetermined number of packets that are accumulated before the block is written to the I/O device, as well as a push interval representing a maximum period of time for which any packet in the block can be stalled. Upon the arrival of a new outgoing packet, the packet is added to the block, and the block is written to the I/O device if either the block now contains the predetermined packets or any packet in the packet has been waiting for more than the push interval. A timer running asynchronously with the arrival of outgoing requests periodically pops to write the block to the I/O device if it has been waiting overlong, even if no new requests have arrived. Both the blocking factor and the push interval are periodically adjusted in accordance with the actual throughput so that the blocking factor corresponds to the exact level of consistent parallelism for a given workload.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
This invention relates to a method and apparatus for adaptively blocking 
outgoing communication requests in an information handling system and, 
more particularly, to a method and apparatus for adaptively blocking such 
requests in a client/server system in which a plurality of requesters are 
operating concurrently. 
2. Description of the Related Art 
Computer systems use what are known as input/output (I/O) operations to 
transmit data from a central processing unit (CPU) or main memory to an 
external device. The external device may be an output device such as a 
printer, a storage device such as a disk or tape drive, or a communication 
channel such as a local area network (LAN). There is generally a fixed 
cost associated with each I/O operation performed. As the amount of data 
being sent per I/O operation decreases, the fixed overhead of the I/O 
driver processing becomes proportionally larger relative to the amount of 
data sent. Many network applications today cause an extremely high 
frequency of small data requests (possibly mixed with larger amounts of 
data), such that the overhead incurred by the I/O driver becomes a 
significant portion of the overall communication stack processing. 
Various attempts have been made before to proactively block the outgoing 
requests, but they have subsequently been abandoned, due to the inability 
to find the consistent level of parallelism for all possible workloads. 
The net result of these attempts was that certain workloads would incur 
unreasonable delays. 
SUMMARY OF THE INVENTION 
In general, the present invention contemplates a method and apparatus for 
handling outgoing communication requests in an information handling system 
in which outgoing communication packets are accumulated into a block that 
is written to an input/output (I/O) device. For each I/O device there is 
generated a blocking factor (BF) representing a predetermined number of 
packets that are accumulated before the block is written to the I/O 
device, as well as a push interval representing a maximum period of time 
for which any packet in the block can be stalled. Upon the arrival of a 
new outgoing packet, the packet is added to the block, and the block is 
written to the I/O device if either the block now contains the 
predetermined packets or any packet in the packet has been waiting for 
more than the push interval. A timer running asynchronously with the 
arrival of outgoing requests periodically pops to write the block to the 
I/O device if it has been waiting overlong, even if no new requests have 
arrived. Both the blocking factor and the push interval are periodically 
adjusted in accordance with the actual throughput so that the blocking 
factor corresponds to the exact level of consistent parallelism for a 
given workload. 
The invention contemplates determining the exact level of consistent 
parallelism for a given workload. This specification calls this value the 
incremental blocking factor (BF) for the workload. Once the correct 
blocking factor is known, multiple outgoing requests can be proactively 
stalled until that blocking factor is reached (without causing significant 
delay), thereby allowing the I/O driver costs to be amortized across 
multiple requests. This grouping of requests into blocks occurs between 
the main CPU processor(s) and the I/O adapter. Depending on the type of 
communication channel, the adapter may then deblock the group of requests 
and send them out over the media. 
Although the disclosed embodiment is designed for outgoing MVS TCP/IP 
packets, the invention defined within this specification applies equally 
well to any communication stack, on any platform, where there is the 
potential for a high frequency of relatively small outgoing I/O requests. 
Just because an adapter reaches a high packet throughput rate, it doesn't 
mean that blocking is right for that workload. In the case where a single 
client/server pair are communicating over the adapter, activating blocking 
could be devastating to the throughput when a request/response model is 
being used. This is because the first outgoing request would be stalled, 
waiting for the second to arrive, but since there is only one client, it 
will never arrive. That is why the invention only keeps blocking active 
for a given workload if the level of parallelism is consistently 
maintained. This level of parallelism is directly related to the number of 
concurrent client/server sessions that are active at any point in time. 
The goal of the invention is to get close to a "streaming" level of 
performance, even when there is only a high frequency of small interactive 
traffic across the adapter. 
The invention tracks outgoing packet heuristics, makes decisions based upon 
those heuristics (i.e., adjusts the incremental blocking factor), and then 
enforces the decisions that are made. All tracking and decision processing 
is done on a per-network adapter basis. This allows each adapter to have a 
unique blocking factor, based upon current load. 
Decisions to adjust the incremental blocking factor are made every r number 
of outgoing requests made (under normal circumstances). Decisions could 
alternatively be made via a timer, but high frequency timers cause 
unnecessary overhead. Instead, very responsive decisions are made on the 
requesters thread of execution, while an outgoing request is being 
processed. 
The tracking of outgoing packet heuristics is implemented by counting the 
number of outgoing requests, and noting the time-of-day (TOD) interval 
between decisions. This is then used to determine the average interval 
between outgoing requests during that decision cycle. The enforcement of 
decisions is also primarily done during the processing of an outgoing 
request. 
This enforcement comes in two forms. The first, involves determining if the 
current request "fills" the block. For example, if the current blocking 
factor is 5 and only 3 packets are pending in the block, then the current 
request will also be stalled, waiting for the 5th packet. When that packet 
does arrive, it will "fill" the block, and cause the block to be written 
immediately. The invention is ignorant of when the size of the data causes 
the block to be filled with data (thereby causing the block to be written 
immediately, independent of the number of requests it contains). 
The second form of enforcement involves maintaining an adaptive "push 
interval" in addition to the BF value. When a decision is made, the 
maximum interval that a packet should be delayed is also calculated 
(described in more detail later). If at the time of a new outgoing 
request, a block has been pending for more than the target push interval, 
then that block is pushed out immediately, independent of the number of 
packets it contains. 
As can be seen from the above, there is very low overhead involved in both 
tracking, and enforcing blocking factor decisions in the mainline flow. 
This invention does assume however that a very efficient method of 
serializing the concurrent access to the outgoing I/O buffer is used, 
otherwise the performance gains obtained by blocking may be reduced. 
The current workload defines the average packet throughput rate that must 
be maintained in order to keep blocking active for that adapter. For 
example, if a given adapter reaches 1000 packets per second before it 
enters blocking (i.e., a blocking factor &gt;1), then the adapter must 
maintain at least that rate when the incremental blocking factor is 
increased. Otherwise, the blocking factor will be decreased, which may 
switch the adapter back to non-blocking mode. The current workload must 
consistently exceed the entry-level minimum requirement of e sustained 
packets per second before blocking will even be considered. 
Blocking factor decisions are based upon two factors: the average interval 
between outgoing requests; and the average interval between outgoing 
blocks. It takes g consecutive good decision cycles to cause the 
incremental blocking factor to be increased. It takes b bad decision 
cycles to cause the blocking factor to be decreased (a value of g being 
greater than b has proved to be the most effective). For a decision cycle 
to be considered good, both the outgoing request rate, and the block rate 
(related to the push interval described above) must be within f percent of 
the target rates calculated when the BF was last increased, otherwise it 
is considered bad. By including the block rate in the decision process, we 
are assured that BF increases do not cause excessive throughput delays. 
Since the invention proactively stalls outgoing requests, preferably there 
is some mechanism to ultimately drive out stalled requests if the request 
being waited for never arrives. The mechanism used in the disclosed 
embodiment is a last-resort timer which fires every t ms, to drive out 
pending blocks as required. This timer uses the push interval described 
above to see if a block has been pending too long. If the invention is 
working correctly, this timer will most often find nothing to do. 
The push interval is initially calculated very conservatively to insure the 
invention can quickly detect when blocking is not appropriate for a given 
workload (i.e., a high frequency of requests, but little to no consistent 
parallelism). Once the workload sustains blocking using the conservative 
model, the invention switches to a more aggressive model which attempts to 
get the highest possible blocking factor within an i ms interval. 
If BF increases have been consistently determined to be bad for a given 
workload, then future increase attempts are delayed, to avoid the 
performance degradation that occurs every time a bad BF increase occurs. 
This delay is implemented by defining an adaptive multiplier to the g good 
decision cycles required to increase the blocking factor. By increasing 
this multiplier every time a BF increase is considered bad (capped at some 
value), subsequent BF increase attempts are effectively delayed. This 
multiplier is only relevant to a given blocking factor value (i.e., bad 
experiences with a BF of 4 should be forgotten when the BF is reduced to 
3). 
If the current BF is no longer appropriate due to a downturn in outgoing 
request throughput, then a decision can be made earlier than the normal 
request-based cycle. This decision is made by the push interval enforcing 
routine, by counting the number of times a block had to be pushed out 
because it exceeded the target push interval (includes f percent fudge 
factor to allow for some variation) calculated during the previous 
decision cycle. When the push count reaches a threshold value within a 
decision cycle, a decision is made immediately to decrease the blocking 
factor. If the BF has very recently been increased, then the threshold 
value is smaller than it normally would be (i.e., decreases BF more 
aggressively). 
A second level of decision making is performed to complete the invention. 
The decision making up to this point is both fairly aggressive, and low 
level. It is aggressive because it ultimately attempts to get the highest 
possible BF within a i ms interval. It is low level because it is based 
directly upon the average request/block throughput rates. If left to its 
own, the above portion of the invention would produce widely varying BFs, 
even for a steady workload, due to its immediate nature. For example, for 
a fairly heavy workload it may determine that a BF of 8 is good for a 
short interval, but then it finds that blocking the requests at that rate 
causes starvation because that is not the consistent level of parallelism 
for that workload, so the invention would subsequently lower the BF. This 
oscillation in BFs has a negative impact on performance because whenever a 
bad decision is made (i.e., a packet is stalled too long), it takes time 
to adjust the BF back to what it should be. 
To stop this oscillation, a conservative governor is integrated into the 
invention. This governor uses the output of the lower level decisions as 
its sampling set, to determine the consistent level of parallelism for a 
given workload. The governor sampling set is implemented by maintaining 
counts of the results of each of the lower level decision cycles. Each 
time a lower level decision is made, the count associated with the 
resulting BF is incremented. When any one count exceeds a threshold value 
(i.e., the lower level decisions are focusing on a particular BF), a new 
governor level decision is made. 
The governor portion of the invention defines the highest possible BF that 
can be set at a given point in the life cycle of a workload. The lower 
level decision making is restricted to making a decision ranging from 1 to 
the current governor BF. The governor value is initially set to a low 
value, until the workload has been consistent enough to warrant increasing 
the governor BF. The ideal distribution of the lower level decisions 
occurs when the majority of the decisions made, fall close to the governor 
BF value. When this is sustained (i.e., c consecutive good governor BF 
samples) the governor BF value is increased by 1, thereby giving the lower 
level decision processing one more option to chose from. When the 
distribution of the lower level decisions is any but ideal, the governor 
BF value is immediately reduced. 
Once the governor BF reaches its highest point for a given workload, the 
invention has determined the exact level of consistent parallelism for 
that workload. This value produces optimal throughput results in that it 
minimizes delay, while at the same time minimizing the overhead required 
to satisfy the high frequency of outgoing requests. 
This invention determines the exact level of consistent parallelism for any 
workload, as it changes over time. Once this blocking factor is known, the 
I/O driver costs can be effectively amortized by proactively stalling 
outgoing requests, without incurring any significant delays. The net 
effect of applying this invention is unique, in that the harder you push 
the adapter, the more efficient the communication with that adapter 
becomes. An interesting external phenomenon in fact occurs during stress 
testing when this invention is applied correctly. Specifically, a given 
null transaction workload can cause the CPU to become 100% busy, but this 
invention then allows significant new workload to be added without 
incurring any additional delay, while using the same 100% of the CPU.

DESCRIPTION OF THE PREFERRED EMBODIMENT 
FIG. 1 shows a typical configuration 100 in which the present invention may 
be used. In the configuration 100, a first computer system 102 (the 
"local" system) communicates with a remote system 104 via a communication 
channel 106. Communication channel 106 may be of any suitable type known 
to the art, such as a local area network (LAN), a point-to-point 
connection or the like; the particulars of its construction form no part 
of the present invention. 
Local system 102 may be a server system servicing a remote client system 
104, although the particular allocation of client functions and server 
functions among systems 102 and 104 forms no part of the present 
invention. Local system 102 is referred to as such because it is assumed 
to be transmitting data to remote system 104 and is therefore the system 
of interest in explaining the present invention. In an actual 
configuration, remote system 104 may be similarly equipped for when it 
assumes a transmitting role. Local system 102 has the usual components of 
a programmed general-purpose computer system (as does remote system 104), 
including a central processing unit (CPU) 108, an operating system (OS) 
kernel 110, an input/output (I/O) adapter or subsystem 112 coupling the 
system to communication channel 106, and one or more requesters 114 that 
issue communication requests to OS kernel 110. Requesters 114 may be 
different processes (either different applications or multiple instances 
of the same application), different threads of the same process, or a 
combination of both. In the embodiment shown, local system 102 comprises 
an IBM S/390.TM. server such as an S/390 Parallel Enterprise Server.TM.0 
G3 or G4, while OS kernel 110 comprises the IBM OS/390.TM. operating 
system. However, the invention is not limited to any particular platform. 
Requesters 114 issue communication requests to a communication stack 118 
(e.g., a TCP/IP stack) of the OS kernel 110. Communication stack 118 
constructs packets 116 containing the user data which are assembled into 
blocks 120 containing one or more packets 116. After it has assembled a 
block 120 of the desired size, communication stack 118 calls an I/O driver 
122, a software component that transfers the block 120 from the buffer 
storage of the communication stack to the I/O adapter 112. 
The manner in which the blocks 120 are handled by the I/O adapter 112 
depends on the type of communication channel 106, among other factors. 
Thus, referring to FIG. 2, if communication channel 106 is a local area 
network (LAN), then the local I/O adapter 112 may deblock (or unblock) the 
packets 116 and transmit them separately over the communication channel. 
On the other hand, referring to FIG. 3, if communication channel 106 is a 
point-to-point connection, then local I/O adapter 112 may send the packets 
116 as blocks 120 to the remote system, whose own I/O adapter (not 
separately shown) unblocks the packets. 
Further details of the operation of the communication stack 118 may be 
found in the related application referred to above, incorporated herein by 
reference. 
Pseudocode listings 1-8 in the Appendix show the procedure of a preferred 
embodiment of the present invention. The procedure is executed by the 
communication stack 118, either upon receiving a communication request 
from a requester 114 or asynchronously, depending on the operation 
involved. 
The procedure uses the following control structures on a per blocking 
device (i.e., I/O adapter 112) basis. All fields but the flags are 
integers. All fields are initialized to zero unless otherwise noted. 
902 Current.sub.-- BF: Current Blocking Factor for device (initialized to 
1). 
903 Goal.sub.-- Met.sub.-- Count: Number of times throughput goals were met 
since last increase of the Current.sub.-- BF (intervening decrements cause 
this field to be reset). 
904 Write.sub.-- Count: Number of packet requests made since last decision. 
905 Target.sub.-- Interval: Current target packet throughput interval. This 
target throughput rate (and the Push.sub.-- Interval which is based upon 
it) must be consistently maintained to keep the current BF value. 
906 Push.sub.-- Count: Number of times block 120 was pushed out due to 
exceeding the target Push.sub.-- Interval (907) since last decision. 
907 Push.sub.-- Interval: Interval between block writes that must be 
maintained in order to keep the current BF. 
908 Probation.sub.-- Flag: Flag indicating that BF was just increased. It 
is used to determine if a recent increase was "bad". 
909 Aggressive.sub.-- Flag: Flag stating that there has been enough 
consistent parallelism to maintain blocking using the conservative 
Push.sub.-- Interval calculation. When set, attempt to reach the highest 
possible BF, bounded by both MAX.sub.-- DELAY.sub.-- INTERVAL and the 
current Governor.sub.-- BF (914). 
910 Consecutive.sub.-- Decr.sub.-- Flag: Flag used to determine when 
previous bad history for a given BF (i.e., Goal.sub.-- Met.sub.-- 
Multiplier) should be cleared. 
911 Goal.sub.-- Met.sub.-- Multiplier: Multiplier used to delay future 
Current.sub.-- BF increases because recent increase attempts have 
consistently proven to be "bad" (initialized to 1). 
912 Historical.sub.-- Thruput(MAX.sub.-- BF): Array containing the packet 
throughput interval that was reached when the Current.sub.-- BF was last 
incremented. This is primarily used during decrement Current.sub.-- BF 
processing to determine what the Target.sub.-- Interval should be for the 
newly decremented BF. 
913 Decision.sub.-- TOD: TOD at time last decision was made. Preferably in 
units no greater than 16 microseconds. 
914 Governor.sub.-- BF: Highest BF the low level decision processing has to 
choose from (i.e., the consistent level of parallelism for this work 
load). Initialized to MIN.sub.-- GOVERNOR.sub.-- BF. 
915 Governor.sub.-- Goal.sub.-- Met.sub.-- Count: Number of times 
throughput goal was met since last increase of the Governor.sub.-- BF 
(intervening decrements cause this field to be reset). 
916 BF.sub.-- Decisions.sub.-- Sampling.sub.-- Set(MAX.sub.-- BF): Array 
used as input to the Governor.sub.-- BF decision making. It contains 
counts of the resulting Current.sub.-- BF after each low-level decision 
cycle is made. 
917 Aggressive.sub.-- Decrement.sub.-- Count: Number of consecutive 
decrements that have occurred (i.e., without an intervening increment) 
while using the aggressive Push.sub.-- Interval calculation. 
The following static values are also used (on either a per device or global 
basis): 
918 AGGRESSIVE.sub.-- THRESHOLD: Threshold value of Aggressive.sub.-- 
Decrement.sub.-- Count 917 beyond which operation reverts to conservative 
model. 
919 DECISION.sub.-- CYCLE.sub.-- THRESHOLD: Number of packet requests 
between decisions to raise or lower Current.sub.-- BF 902. Corresponds to 
the value r. 
920 ENTRY.sub.-- LEVEL.sub.-- BLOCKING.sub.-- INTERVAL: Minimum (and 
initial) value of Target.sub.-- Interval 905. Corresponds to the value e. 
921 FUDGE.sub.-- FACTOR: Used when calculating the Push.sub.-- Interval. It 
is really f percent of the product of the Current.sub.-- BF and the 
Target.sub.-- Interval. 
921a FUDGE.sub.-- FACTOR2: Used when calculating the Target.sub.-- 
interval. It is really f percent of the Target.sub.-- Interval. 
922 GOAL.sub.-- MET.sub.-- THRESHOLD: Minimum value of Goal.sub.-- 
Met.sub.-- Count 903 for Current.sub.-- BF 902 to be raised. Corresponds 
to value g. 
923 GOVERNOR.sub.-- DECISION.sub.-- THRESHOLD: Value of BF.sub.-- DECISIONS 
SAMPLING.sub.-- SET(x) 916 causing a governor decision to be made. 
923a GOVERNOR.sub.-- GOAL.sub.-- MET.sub.-- THRESHOLD: Value of 
Governor.sub.-- Goal.sub.-- Met.sub.-- Count 915 for Governor.sub.-- BF 
914 to be raised. Corresponds to value c. 
924 MAX.sub.-- BF: Upper bound on Governor.sub.-- BF 914. 
925 MAX.sub.-- DELAY.sub.-- INTERVAL: Upper bound on Push.sub.-- Interval 
907. 
926 MAX.sub.-- MULTIPLIER: Upper bound on Goal.sub.-- Met.sub.-- Multiplier 
911. 
927 MAX.sub.-- PROBATION.sub.-- STALL.sub.-- INTERVAL: Probation threshold 
value of Stalled.sub.-- Interval beyond which Current.sub.-- BF 902 is 
decremented. 
928 MIN.sub.-- GOVERNOR.sub.-- BF: Minimum (and initial) value of 
Governor.sub.-- BF 914. 
929 PUSH.sub.-- THRESHOLD: Threshold value of Push.sub.-- Count 906 beyond 
which Current.sub.-- BF 902 is decremented. 
Listing 1 shows the mainline packet write flow routine 100. This routine 
100 is performed by a layer of the communication stack 118 that receives a 
request from another layer of the stack that has created a packet 116 in 
response to a request from a requester 114. 
Upon receiving an outgoing packet, the routine 100 adds the packet 116 to 
the current block 120 (step 101) and determines whether the block 120 is 
to be considered "full" due to reaching Current.sub.-- BF 902, using the 
routine shown in Listing 2 (step 110). If the block 120 is not "full", 
then the routine 100 determines whether the block 120 must be pushed out 
due to its being stalled too long as determined from Push.sub.-- Interval 
907, using the routine shown in Listing 7 (step 120). If the block 120 is 
"full" or must be "pushed out", then the routine 100 causes the block 120 
to be written by calling the device driver 122 for the I/O adapter 112 
(step 121). 
A separate routine implements an asynchronous last-resort timer that loops 
through all pending blocks 120 (one for each device 112 that is blocking 
data) to write blocks 120 that have been stalled too long because 
Current.sub.-- BF 902 was not met (step 130). 
Listing 2 shows the routine 110 for determining if the block 120 is "full". 
Initially, the routine 110 increments the count (Write.sub.-- Count 904) 
of packets 116 written to the device 112. If Write.sub.-- Count 904 
reaches DECISION.sub.-- CYCLE.sub.-- THRESHOLD 919, then the routine 110 
calls the "Make BF Decision" routine 210 shown in Listing 3 and zeros 
Write.sub.-- Count 904 and Push.sub.-- Count 906 (step 202). If 
Write.sub.-- Count 904 modulo Current.sub.-- BF 902 is zero, then the 
routine 110 informs the caller that the block 120 is "full" (step 203). 
Listing 3 shows the "Make BF Decision" routine 210 invoked at step 202 of 
routine 110. The routine 210 initially serializes at least on a per device 
basis if required (step 301). The routine 210 then calculates the time 
since the decision was made for this device (Elapsed.sub.-- Time) by 
subtracting Decision.sub.-- TOD 913 from the current time-of-day (TOD) 
Current.sub.-- TOD (step 302). The routine 210 then sets Decision.sub.-- 
TOD equal to Current TOD (step 303) and calculates the average time 
between packet requests (the packet throughput interval) by dividing 
Elapsed.sub.-- Time by Write.sub.-- Count 904 (step 304). Next, the 
routine 210 calculates the average time between block writes (the block 
throughput interval) by dividing Elapsed.sub.-- Time by Write.sub.-- 
Count/Current.sub.-- BF 902 (step 305). The routine then determines target 
throughput intervals for both packets 116 and blocks 120 (step 306). 
If Current.sub.-- BF 902 is greater than 1 or there is a history of BF 
"bad" increments (i.e., Goal.sub.-- Met.sub.-- Multiplier 911.noteq.1), 
then the routine 210 sets the target packet throughput interval 
(Target.sub.-- Interval 905) equal to the sum of the Target.sub.-- 
Interval that caused the most recent increase of Current.sub.-- BF 902 and 
FUDGE.sub.-- FACTOR2 921a, and sets the target block throughput interval 
(Push.sub.-- Interval 907) equal to the Push.sub.-- Interval calculated 
during most recent action on Current.sub.-- BF at step 408 or 510 (step 
307). Otherwise, the routine 210 sets both the target block throughput 
interval (Push.sub.-- Interval 907) and the target packet throughput 
interval (Target.sub.-- Interval 905) equal to ENTRY.sub.-- LEVEL.sub.-- 
BLOCKING.sub.-- INTERVAL 920 (step 308). 
If both target throughputs are met, then the routine 210 invokes the 
"Consider BF Increment" routine 320 shown in Listing 4 (step 309). 
Otherwise, the routine 210 invokes the "Consider BF Decrement" routine 330 
shown in Listing 5 (step 310). 
The routine 210 then records the latest BF decision in the BF.sub.-- 
Decisions.sub.-- Sampling.sub.-- Set array 916 (i.e., increments BF.sub.-- 
Decisions.sub.-- Sampling.sub.-- Set(Current.sub.-- BF) by 1) (step 311). 
If BF.sub.-- Decisions.sub.-- Sampling.sub.-- Set(Current.sub.-- BF) is 
greater than GOVERNOR.sub.-- DECISION.sub.-- THRESHOLD 923, then the 
routine 210 calls the "Set Governor BF processing" routine 340 shown in 
Listing 8 (step 312). Finally, the routine 210 unserializes if it 
serialized above at step 301 (step 313). 
Listing 4 shows the "Consider BF Increment" routine 320. At step 401, if 
Probation.sub.-- Flag 908 is ON, the routine 320 sets Probation.sub.-- 
Flag equal to OFF and sets Goal.sub.-- Met.sub.-- Multiplier 911 equal to 
1. The routine then increments Goal.sub.-- Met.sub.-- Count 903 (step 
402). If Goal.sub.-- Met.sub.-- Count 903 is greater than the product of 
GOAL.sub.-- MET.sub.-- THRESHOLD 922 and Goal.sub.-- Met.sub.-- Multiplier 
513 (step 403), then the routine 320 performs some or all of steps 
404-410; otherwise, it jumps to step 411. 
At step 404, if Current.sub.-- BF 902 is less than Governor.sub.-- BF 914 
(340), then the routine 320 performs some or all of steps 405-410; 
otherwise, the routine jumps to step 411. 
At step 405, the routine 320 saves the current packet throughput interval 
that must be maintained to keep Current.sub.-- BF (i.e., stores it as the 
Historical.sub.-- Thruput(Current.sub.-- BF) entry of array 912 and as 
Target.sub.-- Interval 905). The routine 320 then increments the 
Current.sub.-- BF 902 for this device (i.e., I/O adapter 112) (step 406) 
and sets Probation.sub.-- Flag 908 equal to ON (step 407). The routine 
then calculates a new target block throughput interval (Push.sub.-- 
Interval 907) (step 408). If the conservative model is active (i.e., 
Aggressive.sub.-- Flag 909=OFF), then the routine 320 sets Push.sub.-- 
Interval 907 equal to Current.sub.-- BF * Target.sub.-- 
Interval+FUDGE.sub.-- FACTOR 921 (capped by MAX.sub.-- DELAY.sub.-- 
INTERVAL 925) (step 409). Otherwise (Aggressive.sub.-- Flag=ON), the 
routine 320 sets Push.sub.-- Interval 907 equal to MAX.sub.-- DELAY.sub.-- 
INTERVAL 925 (step 410). 
Finally, the routine 320 zeros Goal.sub.-- Met.sub.-- Count 903 and 
Aggressive.sub.-- Decrement.sub.-- Count 917 and sets Consecutive.sub.-- 
Decr.sub.-- Flag 910 equal to OFF (step 411). 
Listing 5 shows the "Consider BF Decrement" routine 330. At step 501, the 
routine 330 zeros Goal.sub.-- Met.sub.-- Count 903. If Current.sub.-- BF 
902 is greater than 1 (step 502), then the routine 330 performs some or 
all of steps 503-515. Otherwise, it jumps to step 516. 
At step 503 the routine 330 decrements Current.sub.-- BF 902 by 1. The 
routine then restores the target packet throughput interval to the value 
before the most recent BF increase (i.e., Target.sub.-- Interval 
905=Historical.sub.-- Thruput(Current.sub.-- BF)) (step 504). Next, the 
routine 320 recalculates the target block throughput interval (Push.sub.-- 
Interval 907), using the routine shown in Listing 6 (step 510). If the 
decrement occurred immediately after an increment (i.e., Probation.sub.-- 
Flag 908=ON) (step 511), then the routine 330 performs steps 512-515. 
At step 512, the routine 330 sets Probation.sub.-- Flag 908 equal to OFF. 
The routine 330 then increments Goal.sub.-- Met.sub.-- Multiplier 911 
(bounded by MAX.sub.-- MULTIPLIER 926) to delay future increase attempts, 
as the most recent increment was "bad" (i.e., the throughput rate was 
high, but the parallelism not consistent) (step 513). If Goal.sub.-- 
Met.sub.-- Multiplier 911 is being increased consistently (i.e., 
Goal.sub.-- Met.sub.-- Multiplier 911 modulo some value&gt;1=0), if the 
conservative push interval model is active (i.e., Aggressive.sub.-- Flag 
909=OFF), and if Current.sub.-- BF 902&gt;1, then we have reached the highest 
possible BF using the conservative push interval calculation method, and 
consistent parallelism exists (step 514). The routine 330 therefore 
switches into the aggressive push interval model (i.e., sets 
Aggressive.sub.-- Flag=ON) (step 515). 
As noted above, control passes to step 516 if Current.sub.-- BF 902 is 1. 
The action taken at this point depends on whether there has been a 
previous bad history of BF increments. If there has been no previous bad 
history of BF increments (i.e., Goal.sub.-- Met.sub.-- Multiplier=1)), 
then the routine 330 resets Target.sub.-- Interval 905 equal to 
ENTRY.sub.-- LEVEL.sub.-- BLOCKING.sub.-- INTERVAL 920 (step 517). If 
there has been a previous bad history, the routine 330 keeps the 
throughput rates that caused entry to blocking as the target throughputs 
(i.e., the last BF increment for this throughput was "bad", therefore 
don't reconsider incrementing Current.sub.-- BF 902 until this level of 
throughput is exceeded) (step 518). 
Listing 6 shows the routine 510 for recalculating Push.sub.-- Interval 907. 
At step 601, if the conservative model is active (i.e., Aggressive.sub.-- 
Flag 909=OFF), the routine 510 sets Push.sub.-- Interval 
907=(Current.sub.-- BF 902 * Target.sub.-- Interval 905)+FUDGE.sub.-- 
FACTOR 921 (where FUDGE.sub.-- FACTOR 921=Current.sub.-- BF * 
Target.sub.-- Interval * f) and skips to step 605. 
If, on the other hand, Aggressive.sub.-- Flag 909 is ON, the routine 510 
performs steps 602-604 before proceeding to step 605. At step 602, the 
routine 510 increments Aggressive.sub.-- Decrement.sub.-- Count 917. At 
step 603, if Aggressive.sub.-- Decrement.sub.-- Count 917 is greater than 
AGGRESSIVE.sub.-- THRESHOLD 918, then the routine recalculates Push.sub.-- 
Interval 907 using the conservative model (601), sets Aggressive.sub.-- 
Flag 909 equal to OFF, and zeros Aggressive.sub.-- Decrement.sub.-- Count 
917. Otherwise, the routine 510 takes no immediate action on Push.sub.-- 
Interval 907 (i.e., waits until a switch back to the conservative model 
occurs). 
At step 605, if Consecutive.sub.-- Decr.sub.-- Flag 910 is ON, then the 
routine sets Goal.sub.-- Met.sub.-- Multiplier 911 equal to 1 and sets 
Consecutive.sub.-- Decr.sub.-- Flag 910 equal to OFF. Otherwise, the 
routine 510 sets Consecutive.sub.-- Decr.sub.-- Flag equal to ON. 
Listing 7 shows the routine 120 for determining whether the block 120 must 
be pushed out. The routine 120 first calculates Stalled.sub.-- Interval by 
subtracting the TOD of when the first packet 116 was written to the 
stalled block 120 from the current TOD (step 701). If the block 120 has 
been stalled longer than the Push.sub.-- Interval 907 calculated at step 
408 (step 702), then the routine 120 informs the caller that the block 120 
must be "pushed out" (step 703). If Current.sub.-- BF 902 was recently 
increased (i.e., Probation Flag=ON) and Stalled.sub.-- Interval is greater 
than MAX.sub.-- PROBATION.sub.-- STALL.sub.-- INTERVAL 927, then the 
routine 120 notes that a decrement is required (step 704). Otherwise (step 
705), the routine 120 increments Push.sub.-- Count 906 (step 706) and, if 
Push.sub.-- Count is greater than PUSH.sub.-- THRESHOLD 929 (step 707), 
notes that a decrement is required (step 708). 
If a decrement is required (step 709), then the routine 120 serializes at 
least on a per device basis if required (step 710) and performs steps 
711-713 before unserializing at step 714. At step 711 the routine 120 
calls the "Consider BF decrement" routine 320 and zeros Write.sub.-- Count 
904 and Push.sub.-- Count 712. At step 712 the routine 120 records the 
latest BF decision in the BF.sub.-- Decisions.sub.-- Sampling.sub.-- Set 
array 916 (i.e., increments BF.sub.-- Decisions.sub.-- Sampling.sub.-- 
Set(Current.sub.-- BF) by 1). At step 713, if the array entry BF.sub.-- 
Decisions.sub.-- Sampling.sub.-- Set(Current.sub.-- BF) is greater than 
GOVERNOR.sub.-- DECISION.sub.-- THRESHOLD 923, then the routine 120 calls 
the "Set Governor BF processing" 340 shown in Listing 8. Finally, the 
routine 120 unserializes if it serialized above at step 710 step 714). 
Listing 8 shows the "Set Governor BF Processing" routine 340 invoked from 
step 713 of routine 120 or step 312 of routine 210. At step 801 the 
routine calculates the total number of decisions made since the last 
Governor decision was made by summing the counts within the BF.sub.-- 
Decisions.sub.-- Sampling.sub.-- Set array 916. 
If the majority of the decisions made during the last governor decision 
cycle are close to Governor.sub.-- BF 914 (step 802), the routine 340 
increments Governor.sub.-- Goal.sub.-- Met.sub.-- Count 915 (step 803) 
and, if Governor.sub.-- Goal.sub.-- Met.sub.-- Count 915 is greater than 
GOVERNOR.sub.-- GOAL.sub.-- MET.sub.-- THRESHOLD 923a (step 804), 
increments Governor.sub.-- BF 914 (bounded by MAX.sub.-- BF 924) and zeros 
Governor.sub.-- Goal.sub.-- Met.sub.-- Count 915, thereby giving the 
low-level decision making one more BF to choose from (step 805). 
On the other hand, if the majority of the decisions made during the last 
governor decision cycle are far below Governor.sub.-- BF 914 (step 806), 
then the routine 340 decrements Governor.sub.-- BF 914 by 2 (bounded by 
MIN.sub.-- GOVERNOR.sub.-- BF 928) and zeros Governor.sub.-- Goal.sub.-- 
Met.sub.-- Count 915 (step 807). 
If neither of these circumstances obtain (i.e., performance is neither good 
nor very bad) (step 808), then the routine 340 decrements Governor.sub.-- 
BF 914 by 1 (bounded by MIN.sub.-- GOVERNOR.sub.-- BF 928) and zeros 
Governor.sub.-- Goal.sub.-- Met.sub.-- Count 915 (step 809). 
After performing steps 802-805, 806-807 or 808-809, the routine 340 clears 
the BF.sub.-- Decisions.sub.-- Sampling.sub.-- Set array 916 to prepare 
for next Governor.sub.-- BF decision (step 810). 
The invention is preferably implemented as software (i.e., a 
machine-readable program of instructions tangibly embodied on a program 
storage device) executing on a hardware machine. While a particular 
embodiment has been shown and described, it will be apparent to those 
skilled in the art that various modifications may be made without 
departing from the spirit of the invention. 
APPENDIX 
__________________________________________________________________________ 
LISTING 1: 100 Mainline Packet Write Flow 
101 
Add packet to current block 
110 
Determine if block is to be considered "full" due to reaching 
the Current.sub.-- BF(902) 
120 
If (not "full") Then 
Determine if block must be pushed out due to it being stalled too long 
(Push.sub.-- Interval(907)) 
121 
If (block is "full" or must be "pushed out") Then 
Cause block to be written 
130 
Implement an asynchronous last resort timer that loops through all 
pending blocks (one for each device that is blocking data) to 
write blocks that have been stalled too long because the 
Current.sub.-- BF 
was not met 
LISTING 2 110 Determine if Block is "Full" 
201 
Increment Write.sub.-- Count(904) of packets written to this device 
202 
If (Write.sub.-- Count reaches the DECISION.sub.-- CYCLE.sub.-- 
THRESHOLD) Then 
Call "Make BF decision" (210), and zero Write.sub.-- Count, Push.sub.-- 
Count(906) 
203 
If (Write.sub.-- Count modulo the Current.sub.-- BF(902) = 0) Then 
Inform caller that block is "full" 
LISTING 3: 210 "Make BF Decision" 
301 
Serialize at least on a per device basis (if required) 
302 
Calculate time since decision was made for this device (Elapsed.sub.-- 
Time) 
by subtracting the Decision.sub.-- TOD(913) from the Current.sub.-- 
TOD 
303 
Set Decision.sub.-- TOD = Current.sub.-- TOD 
304 
Calculate average time between packet requests (packet throughput 
interval) 
by dividing Elapsed.sub.-- Time by Write.sub.-- Count(904) 
305 
Calculate average time between block writes (block throughput 
interval) 
by dividing the Elapsed.sub.-- Time by (Write.sub.-- Count/Current.sub. 
-- BF(902)) 
306 
Determine target throughput intervals for both packets, and blocks 
307 If (Current.sub.-- BF(902) &gt; 1 OR There is a history of BF "bad" 
increments 
(i.e., Goal.sub.-- Met.sub.-- Multiplier(911) -= 1)) Then 
. Set Target packet throughput interval = Throughput that caused the 
most recent increase of the Current.sub.-- BF (405) (504) 
(i.e., Target.sub.-- Interval) + FUDGE.sub.-- FACTOR 
. Set Target block throughput interval = Push.sub.-- Interval(907) 
calculated 
during most recent action on the Current.sub.-- BF (408) (510) 
308 Else 
. Set Target block, and packet throughput intervals = 
ENTRY.sub.-- LEVEL.sub.-- BLOCKING.sub.-- INTERVAL 
309 
If (Both target throughputs are met) Then "Consider BF increment" 
(320) 
310 
Else "Consider BF decrement" (330) 
311 
Record latest BF decision in the BF.sub.-- Decisions.sub.-- Sampling.su 
b.-- Set(916) array 
(i.e., increment BF.sub.-- Decisions.sub.-- Sampling.sub.-- Set(Current 
.sub.-- BF) by 1) 
312 
If (BF.sub.-- Decisions.sub.-- Sampling.sub.-- Set(Current.sub.-- BF) 
&gt; GOVERNOR.sub.-- DECISION.sub.-- THRESHOLD) 
Then Call "Set Governor BF processing" (340) 
313 
Unserialize if serialized above 
LISTING 4: 320 "Consider BF Increment" 
401 
If (Probation.sub.-- Flag(908) = ON) Then 
keep Current.sub.-- BF (i.e., store it into the Current.sub.-- 
BF(902) entry of the 
Historical.sub.-- Thruput(912) array, and into Target.sub.-- Interval( 
905)) 
406 
. Increment the Current.sub.-- BF for this device 
407 
. Set Probation.sub.-- Flag = ON 
408 
. Calculate new target block throughput interval (Push.sub.-- Interval( 
907)) 
409 . If (Conservative model active (i.e., Aggressive.sub.-- Flag(909) = 
OFF)) Then 
. . 
Set Push.sub.-- Interval = Current.sub.-- BF * 
Target.sub.-- Interval + FUDGE.sub.-- FACTOR 
(capped by MAX.sub.-- DELAY.sub.-- INTERVAL) 
410 . Else (Aggressive.sub.-- Flag = ON) 
. . 
Set Push.sub.-- Interval = MAX.sub.-- DELAY.sub.-- INTERVAL 
411 Zero Goal.sub.-- Met.sub.-- Count, Aggressive.sub.-- Decrement.sub.-- 
Count(917), and 
Set Consecutive.sub.-- Decr.sub.-- Flag(910) = OFF 
LISTING 5: 330 "Consider BF Decrement" 
501 
Zero Goal.sub.-- Met.sub.-- Count(903) 
502 
If (Current.sub.-- BF(902) &gt; 1) Then 
503 Decrement Current.sub.-- BF by 1 
504 Restore Target packet throughput interval to value before the most 
recent 
BF increase 
(i.e., Target.sub.-- Interval(905) = Historical.sub.-- Thruput(Current.sub 
.-- BF)) 
510 Recalculate target block throughput interval (Push.sub.-- Interval(90 
7)) 
511 If (decrement occurred immediately after an increment 
(i.e., Probation.sub.-- Flag(908) = ON)) Then 
512 . 
Set Probation.sub.-- Flag = OFF 
513 . 
Increment the Goal.sub.-- Met.sub.-- Multiplier(911) (bounded by 
MAX.sub.-- MULTIPLIER) to 
delay future increase attempts, as most recent increment was 
"bad" 
(i.e., throughput rate high, but parallelism not consistent) 
514 . 
If (the Goal.sub.-- Met.sub.-- Multiplier is being increased 
consistently 
(Goal.sub.-- Met.sub.-- Multiplier modulo some value &gt; 1 = 0) 
AND the conservative push interval model is active 
(i.e., Aggressive.sub.-- Flag(909) = OFF) 
AND Current.sub.-- BF &gt; 1) Then 
(i.e., we have reached the highest possible BF using the 
conservative push interval calculation method, and consistent 
parallelism exists) 
515 . Switch into the aggressive push interval model 
(i.e., Set Aggressive.sub.-- Flag = ON) 
516 
Else (Current.sub.-- BF = 1) 
517 When (no previous bad history of BF increments 
(i.e., Goal.sub.-- Met.sub.-- Multiplier = 1)) 
. Reset Target.sub.-- Interval = ENTRY.sub.-- LEVEL.sub.-- BLOCKING.su 
b.-- INTERVAL 
518 When (Previous bad history) 
. Keep throughput rates that caused entry to blocking as the target 
throughputs (i.e., last BF increment for this throughput was "bad", 
there- 
fore don't reconsider incrementing the Current.sub.-- BF until this 
level of 
throughput is exceeded) 
LISTING 6: 510 Recalculate Push Interval 
601 
If (Conservative model active (i.e., Aggressive.sub.-- Flag(909) = 
OFF)) Then 
Set Push.sub.-- Interval(907) = Current.sub.-- BF(902) * 
Target.sub.-- Interval(905) + FUDGE.sub.-- FACTOR 
602 
Else (Aggressive.sub.-- Flag = ON) 
Increment Aggressive.sub.-- Decrement.sub.-- Count(917) 
603 If (Aggressive.sub.-- Decrement.sub.-- Count &gt; AGGRESSIVE.sub.-- 
THRESHOLD) Then 
. Recalculate Push.sub.-- Interval using the conservative model 
(601) 
. Set Aggressive.sub.-- Flag = OFF, and zero Aggressive.sub.-- 
Decrement.sub.-- Count 
604 Else Take no immediate action on Push.sub.-- Interval 
(i.e., wait until switch back to the conservative model occurs) 
605 
If (Consecutive.sub.-- Decr.sub.-- Flag = ON) Then 
Set Goal.sub.-- Met.sub.-- Multiplier(911) = 1 
Set Consecutive.sub.-- Decr.sub.-- Flag = OFF 
606 
Else Set Consecutive.sub.-- Decr.sub.-- Flag = ON 
LISTING 7: 120 Determine if Block must be Pushed Out 
701 
Calculate Stalled.sub.-- Interval by subtracting the TOD of when the 
first packet 
was written to the stalled block, from the current TOD 
702 
If (block has been stalled longer than the Push.sub.-- Interval(907) 
(408)) Then 
703 Inform caller that block must be "pushed out" 
704 If (Current.sub.-- BF(902) was recently increased (i.e., 
Probation.sub.-- Flag = ON) 
AND Stalled.sub.-- Interval &gt; MAX.sub.-- PROBATION.sub.-- STALL.sub.-- 
INTERVAL) Then 
. Note Decrement required 
705 Else 
706 . 
Increment Push.sub.-- Count(906) 
707 . 
If (Push.sub.-- Count &gt; PUSH.sub.-- THRESHOLD) Then 
708 . Note Decrement required 
709 If (Decrement required) Then 
710 . 
Serialize at least on a per device basis (if required) 
711 . 
Call "Consider BF decrement" (320), and zero Write.sub.-- Count 
(904), 
Push.sub.-- Count 
712 . 
Record latest BF decision in the BF.sub.-- Decisions.sub.-- 
Sampling.sub.-- Set(916) array 
(i.e., increment BF.sub.-- Decisions.sub.-- Sampling.sub.-- 
Set(Current.sub.-- BF) by 1) 
713 . 
If (BF.sub.-- Decisions.sub.-- Sampling.sub.-- Set(Current.sub.-- 
BF) &gt; 
GOVERNOR.sub.-- DECISION.sub.-- THRESHOLD) Then 
. Call "Set Governor BF processing" (340) 
714 . 
Unserialize if serialized above 
LISTING 8: 340 "Set Governor BF Processing" 
801 
Calculate total number of decisions made since last Governor decision 
was 
made by summing the counts within the BF.sub.-- Decisions.sub.-- 
Sampling.sub.-- Set(916) array 
802 
When (The majority of the decisions made during the last Governor 
decision cycle are close to the Governor.sub.-- BF(914)) Then 
803 Increment Governor.sub.-- Goal.sub.-- Met.sub.-- Count(915) 
804 If (Governor.sub.-- Goal.sub.-- Met.sub.-- Count &gt; GOVERNOR.sub.-- 
GOAL.sub.-- MET.sub.-- THRESHOLD) Then 
805 . 
Increment Governor.sub.-- BF (bounded by MAX.sub.-- BF), and zero 
Governor.sub.-- Goal.sub.-- Met.sub.-- Count, thereby giving the 
low level decision making 
one more BF to choose from 
806 
When (The majority of the decisions made during the last Governor 
decision cycle are far below the Governor.sub.-- BF) Then 
807 Decrement the Governor.sub.-- BF(914) by 2 (bounded by MIN.sub.-- 
GOVERNOR.sub.-- BF), 
and zero Governor.sub.-- Goal.sub.-- Met.sub.-- Count 
808 
Otherwise (neither good or very bad) 
809 Decrement the Governor.sub.-- BF(914) by 1 (bounded by MIN.sub.-- 
GOVERNOR.sub.-- BF), 
and zero Governor.sub.-- Goal.sub.-- Met.sub.-- Count 
810 
Clear BF.sub.-- Decisions.sub.-- Sampling.sub.-- Set array to prepare 
for next Governor.sub.-- BF 
decision 
__________________________________________________________________________