Balancing data-processing work loads

The machine-implemented method of balancing workloads between two parallel data processing paths, the automatic machine steps of:

• segmenting the data processing in each path into work allocations;
• separately tabulating undesired delays in data processing for each of said work allocations;
• totaling said tabulations for each of said data processing paths;
• independently comparing the total tabulations for each path with a first threshold of such undesired delay tabulations;
• when one of said total tabulations for a given one of said data processing paths exceeds said first threshold, then determining the difference in the total delay tabulations between said paths;
• when the difference between the totals of delay tabulations exceeds a predetermined value, then transfer a one work allocation of said given one data processing path to a second data processing path;
• selecting said one work allocation to have an average number of all said separate undesired delay tabulations in the one data processing path with respect to said difference of said total delay tabulations;
• and
• each time said first threshold is exceeded in either one of said paths, recalibrating said separate and total tabulations for all of said data processing paths and without affecting said determining step and said selecting step.

A machine-implemented method of operating a data processing system having a plurality of independent, program controlled, data processors for regulating the flow of tasks to said data processors from a plurality of sources to facilitate the processing of the tasks with a minimal delay, comprising the automatic machine steps of:

• assigning said tasks to said data processors, each task being assigned to but one data processor, monitoring and totaling, individually for each task and collectively for each data processor for each data processor, the number of time delay occurrences in each of said data processors resulting from tasks then being performed by them, the totaling of said time delays being substantially concurrent with the occurrence of the respective time delays;
• selecting a separate upper limit value for a total number of task delay occurrence for each said data processor;
• diverting a task having a mean number of occurrences of said task delay occurrences of all task delay occurrences in a one of said data processors and assigned to one of said data processors to another of said data processors upon a determination that the difference between task delay occurrence totals of said data processors exceeds a given difference limit value;
• and
• processing said diverted task in said another data processor.

An automatic load-balancing data processing unit adapted to be connected to at least another data processing unit in a distributed processing network, a memory in each of said data processing units and each memory having allocatable segments for use with diverse data processing operations,

• the improvement comprising:
• means in each of said data processing units for indicating data processing delays in any of said data processing operations associated with said segments;
• a work delay counter for each segment in each of said data processing units and respectively coupled to said indicating means to respond to each indicated delay for the respective segments for tallying a number of said indicated data processing delays respectively associated with data processing operations using each such segment;
• a total delay counter in each of said data processing units and coupled to said indicating means, respectively, for tallying all of said delay indications independent of which data processing operation is involved in such delay;
• a first threshold detector in each of said data processing units and coupled to said total delay counter, respectively, for detecting and indicating when a count in said total delay counter exceeds a predetermined value;
• and
• transfer means in each of said data processing units and coupled to said work delay counters, respectively, in said data processing units, and responsive to said respective first threshold detector for separately comparing the number in each said work delay counters with the number in said total delay counter to indicate a one of said segments associated with a one of said data processing operations having a number of delays closest to a given mean number of delays with respect to all said number of work delays for said segments, in a respective one of said data processing units whereby such one data processing operation is indicated as eligible for transfer to said another data processing unit for initiating a load balancing operation between the two data processors.

Data processing apparatus including a host processor system (12) connected to issue work instructions to a plurality of peripheral devices (13), each of said peripheral devices having an operational status and being allocatable for operation to either of two control units (11), each of which allocates work to its said allocated peripheral devices or stores such work, depending upon said operational status of the device concerned, and to initiate work transfer between control units each control unit including:

• means (41,42) to separately store the number of work delay occurrences for each of its said allocated peripheral devices means (45) to summate the the delay occurrences, means (46) to indicate when the summation of delay occurrences exceeds a threshold value, means (55), responsive to such indication, to compare the summation of delay occurrences in the two control units to obtain a difference, means (55) to compare such difference with a threshold difference value, means (58) responsive to initiation of work transfer to compare the separately stored number of work delay occurrences with said difference of summated delays and to select a one of said peripheral devices corresponding to a one of said stored number of work delay occurrences having a value closest of any of said stored numbers of work delay occurrences to a transfer value which is a predetermined proportion of said difference between the summated delay occurrences such that the transfer or non-transfer of any particular peripheral device depends on its own contribution to the overall work load of the pertinent control unit, and means (60), responsive to such difference exceeding the threshold difference value, to initiate transfer of said selected one peripheral device from a first one to a second one of said control units control unit.