Method of Operating a Multiprogrammed Computing System

This invention relates to new and useful improvements in the methods of operating general purpose digital computing systems on one or more programs at the same time (multiprogramming). More specifically, the present invention relates to dynamically adjusting both the productivity and the sharing characteristics of the computing system.

Over the last several years, multiprogramming has been widely accepted by the data processing industry. Prior to multiprogramming, computing systems processed programs on a one-at-a-time basis. If a program did not require all of the resources of the computing system, the unused resources were forced to remain idle for the duration of that particular program. An objective of multiprogramming was to significantly increase resource utilization by processing more than one program concurrently, hence, increasing thruput (productivity). This goal of multiprogramming has seldom been realized primarily because the programs that are attempting to process in parallel often require the same resources. At best, the result is a larger, more expensive computing system run in a shared serial manner. Frequently, and worse, the resources the programs are trying to share operate in a less efficient manner when shared. Thus, the effective utilization actually degrades to a level lower than that of one-at-a-time serial processing.

Resource scheduling for the multiprogrammed computing system is very different from the non-multiprogrammed system where the number or resources is always greater than or equal to the individual program's requirements. In the multiprogrammed system, the situation normally exists where there is an insufficient number of separate physical resources to satisfy the needs of all of the programs being multiprogrammed. This being the case, it becomes necessary to regulate the resource access of the various programs within the system.

There are three basic prior art techniques for regulating resource access. The first is fixed system priority; the second is manual priority; and the third is internal program controlled priority.

Fixed system priority is normally associated with some physical characteristic of the computing system. Different priority levels may be built into the CPU itself. Process control computers are frequently made this way. Certain multiprogramming operating systems are designed such that physical memory location determines priority within the system. Thus, the programs that reside in the highest storage addresses may have the highest resource priority within the system. In either case, once a program begins execution within the computing system, its resource priority is fixed.

Manual priority simply removes the hardware considerations from assigning program resource priority. Any program can be assigned a priority which is independent of the portion of the computing system in which it operates. As with fixed system priority, once the resource priority assignment is made, it is fixed for the duration of the program's execution.

With internal program controlled priority, any program which is specifically written to take advantage of this characteristic has the ability to change its own priority as it executes.

Recently, the problems of the above-described priority assignment techniques have led to consideration of changing access priorities from time to time to improve thruput. However, in these instances, only the CPU's activity was considered.

Fixed priority and manual priority systems cannot optimize thruput except in special instances. During a time interval when two parallel processing programs require the use of a given resource, the program with the higher priority may so dominate the use of that resource that the lower priority program is locked out. Further, the lower priority program may be locked out even though it only needs a relatively small amount of time on the resource under consideration. Finally, the lower priority program will not be able to use other resources for which it has a relatively large demand because of its need for some time on a dominated resource. Hence, the computing system works on a more or less one-at-a-time basis.

Internal program controlled priority has several drawbacks. The programs themselves must have been specifically written to take advantage of the priority assignment capability in the system. Programs that run CPU-bound on one machine may run very peripheral-bound on another machine. (When a program can saturate, that is, use 100% of a particular resource, it is said to be bound by that resource.) So, for internal program controlled priority to work effectively, it must take into consideration the particular computing system in which it is running. A human failing comes into play also. When the programmer himself has the ability to select his programs' resource priorities, more often than not he will select the very highest priority in the system.

When two or more programs time share a resource with equal resource priority or when two or more programs with different resource priority share a resource because of the inability of the program with highest resource priority to saturate the resource, the resulting alternate use of that peripheral resource may cause the total effective system utilization to be significantly lower than executing one program at a time. This system degradation occurs frequently today in computing systems that utilize disk storage facilities. When the disk is dedicated to one of the programs, it can perform many data transfers without seeking to a new location on the disk. However, when it is shared between two programs, the data transfers are frequently separated by delaying or degrading seeks. The function of mechanically moving the read/write heads to the new disk location is called seeking.

The shortcomings of prior art are tabulated briefly below:

1. There is no analysis of the peripheral resources.

2. There is no priority control of degradable resources.

3. There is no method of regulating a program's access to different resources in the system in an unlike manner.

4. There is no method of taking into consideration program resource contention and selecting a subset of the processing programs that will increase total system resource utilization.

5. There is no method of varying the regulating characteristics with time.

Briefly, according to this invention, a computing system processes one or more programs concurrently. The computing system comprises one or more central processing unit resources having associated logic and main memory functions and an interrupt capability, and at least one peripheral resource capable of functioning in parallel with the central processing units. The operating system according to this invention contains data gathering subprograms which accumulate system utilization data for one or more processing programs during a processing interval. Based on the accumulated system utilization data, at spaced intervals the regulating program analyzes and regulates resource access to one or more resources for one or more processing programs to provide increased or maximized thruput. Thereafter, the regulating program directs the operating system to continue executing the processing programs according to the regulated resource access. The data gathering and regulating steps are continually repeated at spaced intervals to provide a dynamically regulated resource access method. According to a preferred embodiment of this invention, the resource access is regulated on an inverse need basis and/or to limit degradation resulting from the inefficient competing between programs for degradable resources. According to yet another preferred embodiment of this invention, on the basis of program resource contention a particular combination of processing programs which provides the most productive use of the computing system is selected for execution.

It is the general object of this invention to provide an improved automated method of multiprogramming a computer system.

It is another object of this invention to improve the total resource utilization or thruput of a computing system.

It is another object of this invention to provide an improved method of sharing the computing system's resources between programs.

It is another object of this invention to provide a mode of operation which consists of alternating between the objective of maximized resource utilization and the objective of sharing the computing system.

It is another object of this invention to enable the computing system to change its mode of operation with time.

FIG. 1 illustrates the overall functional relation of the central processing unit to the degradable and non-degradable peripheral resources in a computing system according to this invention;

FIG. 2 illustrates the degradation of a resource as a result of competing programs;

FIG. 3 illustrates the meaning of priority controlled resource activity and shared resource activity;

FIG. 4 is a collection of tables showing the type of data accumulated by the data gathering subprograms according to this invention; (Embodiments I through V are explained with reference to this data.)

FIGS. 5 a,b,c are flow diagrams illustrating the data gathering subprogram;

FIGS. 6 a,b are flow diagrams illustrating the regulating program of Embodiment I;

FIG. 7 illustrates the way priorities are assigned according to Embodiment I;

FIG. 8 is a flow diagram illustrating the regulating program of Embodiment II;

FIG. 9 illustrates the way in which priorities are assigned in accordance with Embodiment II;

FIG. 10 is a flow diagram illustrating the regulating program of Embodiment III;

FIGS. 11, 12 and 13 illustrate the way priorities are assigned according to Embodiment III;

FIG. 14 is a flow diagram illustrating the regulating program of Embodiment IV;

FIGS. 15 and 16 illustrate the way priorities are assigned according to Embodiment IV;

FIG. 17 is a flow diagram illustrating the regulating program according to Embodiment V; and,

FIGS. 18, 19, 20 and 21 illustrate modes and a timetable according to Embodiment V.

This invention relates to the multiprogramming operating systems of general purpose digital computers, i.e., those having the capability of processing more than one program in parallel. More precisely, this invention relates to certain resource supervising portions of the operating system. Other portions of the operating system which are not particularly related to this invention are, for example, the contents supervisor, the overlay supervisor and the timer supervisor.

FIG. 1 illustrates the overall functional relationship of the central processing unit (CPU) to the peripheral resources in a computing system. The general purpose digital computing systems to which this invention is applicable may comprise one or more central processing units with their associated memory units and one or more peripheral units (generally input/output or I/O devices) that may or may not be shared between the central processing units. The distinction between the central processing units and the peripheral units is that the peripheral units are in some way subordinate to the central processing units. Card readers, printers, tape drives, disk drives, channels, controllers, special purpose computers and general purpose computers may all be peripheral units. All peripheral units are capable of processing in parallel with the CPU's.

Generally, the CPU executes a machine language embodiment of the method according to this invention. However, the embodiment may take place in a programmable peripheral processor which is more or less an auxiliary CPU. The CPU comprises an arithmetic-logic unit and main memory. The preferred embodiments of this invention employ a CPU which has an interrupt capability enabling the regulating program to interrupt the processing programs at intervals such that it may, for example, impose new access priorities upon the processing programs.

The interrupt capability is most conveniently provided by an interval timer which is common on third and fourth generation computers. Basically, the interval timer is an electrical device that periodically decrements a numerical value stored at a selected memory location (word) and triggers an interrupt when the value of the word reaches a predetermined value, for example, zero. On the IBM 360 computer, line cycle alternating current is used to decrement the timer word every one sixtieth of a second. On other machines an internal oscillator of higher frequency decrements the timer word. Obviously, the reset value of the timer word and the decrementing frequency controls the timer interrupt interval. The interval timer and the software routines to maintain it for IBM System/360/370 general purpose computers using the Operating System/360/370 are more fully discussed in IBM manual number GY286659.

Rather than using a timer interrupt, the existing system interrupts which occur, for example, at the end of every peripheral operation might be used to give the regulating program control. The processing interval could be based on a certain number of the system interrupts. The length of the processing interval with this type of an embodiment would depend upon the nature of the programs being processed.

There are two basic types of peripheral resources, non-degradable and degradable. A degradable peripheral resource is one that when shared by the operating system between two or more programs incurs a significant amount of overhead while switching its service from one program to another. Disk drives, data cells and cram files are the most common degradable resources. Input/output channels which incur no switching overhead are a common example of a nondegradable resource. Tape drives are generally nondegradable resources but for a very different reason. The degradation incurred by attempting to share a tape drive between two different programs is so obvious that the operating system prevents this type of sharing altogether. FIG. 2 illustrates how a disk drive can be degraded. In FIG. 2(a) Program A having the higher resource access priority makes continuous use of the peripheral and thus avoids degradation of the disk. FIG. 2(b) shows the degrading effect of frequent seeks when the two programs share the disk. The time required by this overhead is defined as degradation time.

As used herein, systems utilization data is a general term meaning resource activity and/or degradation data. Subprograms to collect this data are described in detail hereafter. As used herein, program resource contention involves the analysis of two or more programs' requirements for two or more resources. As used herein, regulating resource access, within the context of this invention, means to assign a resource access priority and/or to prevent resource access altogether.

The meaning of resource access priority as used in the context of this specification is illustrated in FIGS. 3(a) and 3(b). FIG. 3(a) gives a picture of resource utilization with time by Programs A, B and C whose respective priorities are 3, 2 and 1;3 being the highest priority. Note that the lower priority programs are only given access to the resource when all higher priority programs no longer need it. However, whenever a higher priority program needs the resource again, processing for the lower priority program is interrupted. FIG. 3(b) defines the meaning of equal priority. Note that service for A, B and C is effectively time sliced as long as those programs require the resource.

Dynamic resource regulation according to this invention comprises a method for dynamically regulating the resource access of the processing programs while they execute. Dynamic regulation has three basic requirements: First, it must gather data relating to the resource utilization of the various programs it is attempting to control. Second, it must have an algorithm for analyzing the data and regulating resource access. Third, it must be given control periodically to execute its regulating algorithm. The latter requirement is easily met by most modern computers having an interrupt capability as previously described. The regulating program includes the operating system interface and the regulating algorithm.

By giving the regulating program a higher CPU priority than any of the regulated programs and by allowing it to use the timer interrupt capability as previously explained, it obtains control at space intervals to provide the necessary analysis and regulation. The time period between consecutive executions of the regulating program during which the operating system is executing processing programs is referred to herein as the processing interval. The time period following the interrupts during which the regulating program is executing is referred to herein as the regulating interval. In practice a suitable processing interval can be found by varying the length of the interval until best results are achieved. An interval of about one-half a second has been found to be a good starting point.

Since the regulating program requires some of the CPU resource, it is very important that the embodiments do not interfere with the normal processing by requiring excessive amounts of main memory space or CPU time. For computing systems that have slow CPU's or that have very high CPU utilization, a simple embodiment of this invention should be used. When more CPU time is available and warranted for effective optimization a more elaborate or sophisticated embodiment may be used. The embodiment illustrated in Appendix A may, for example, require twelve to sixteen thousand characters of main memory. On the IBM 360 Model 65 the regulating program takes less than one percent of the available CPU time. On an IBM 360 Model 50 the regulating program of Appendix A could take as much as three percent of the available CPU time. These costs are indeed nominal when compared to the increased thruput resulting from the use of this invention.

Systems utilization data relating to at least one program is essential to this invention. Utilization data pertains to resource activity and/or degradation. The data itself may take the form of event counts or time. Since the performance of the regulating program is highly dependent upon the accuracy of the systems utilization data, time rather than event counts is used in the descriptions of the preferred embodiments that follow.

These are two fundamental techniques for accumulating data, sampling and direct measurement. A sampling technique has two major disadvantages when it is used to accumulate data for a dynamic regulating method. The first is that the processing interval may have to be made much longer than desired in order that the sampling data have statistical validity. The second drawback is that a sampling form of data gathering can incur high CPU overhead and in fact significantly alter the characteristics of the system that it is trying to measure.

For the above reasons a direct time measurement technique is preferred for embodiments of this invention. Appendix A contains a commented symbolic machine language listing of three data gathering subprograms which have been added to the IBM System/360/370 operating system. The three data gathering subprograms are called the dispatcher subprogram, the start I/O subprogram and the asynchronous I/O interrupt subprogram. They interface with standard operating system functions by the same name that are described in IBM manual GY28-6659.

It is a function of these data gathering subprograms to provide basic resource utilization data for the processing programs that are being executed in parallel. FIG. 4 illustrates in tabular form the timing information that is maintained by the data gathering subprograms for each regulated processing program. These tables show a brief history of program resource activity immediately preceding the execution of the regulating program. They may also show the total amount of degradation time attributed to the program.

The data gathering may take place over more than one processing interval for one or more programs when this is necessary to accumulate sufficient usage data for analysis. The history recorded (see FIG. 4) by the data gathering subprogram may reflect many processing intervals. In any event, the history must be set long enough or short enough to be useful in predicting what will take place in the next processing interval. If the combination of programs being processed by the computing system does not have enough natural sharing of resources, it may be necessary to switch to a time sharing mode (for example, described hereafter with reference to Embodiment IV) to gather data on all the processing programs.

The dispatcher subprogram measures CPU resource time for the processing programs, and the start I/O and asynchronous I/O interrupt subprograms measure peripheral resource time and degradation.

Appendix A is the source listing of a proprietary system of Duquesne Systems, Inc., called Quantitative Computer Management (QCM). As such, its function is broader than data gathering for this invention. Flow charts are described herein in detail to point out the portions of Appendix A that are applicable to the data gathering for this invention. Source listing sequence numbers from Appendix A are used frequently in the descriptions that follow. The sequence numbers are eight digit numbers enclosed in parentheses.

Referring to FIG. 5(a), control is received from the operating system at BLOCK 500 (26220000). In an MFT environment, registers are saved (26300000). Local addressability is obtained (26400000) and a test is made to determine if the CPU is going to wait (26640000, MFT) (26700000, MVT); if not, the program resource table (TTT) is found for the program to be dispatched, BLOCK 501 (26760000). This pointer is then stored, BLOCK 502 (26800000), and control is passed to BLOCK 503 where the time of the previous dispatch is saved (26860000). The current time is obtained, BLOCK 504 (26880000); a test is made to determine if the CPU has been waiting (26900000). If so, then wait analysis is performed (43820000).

At BLOCK 505, the current time (time of this dispatch) is saved (26980000). The second time through this code and thereafter a test is made to see if the interrupt time was billable (27100000). If not, control is passed to BLOCK 506; otherwise, the duration of the interrupt CPU activity is computed (27180000). The program resource table (TTT) for the program which caused the interrupt is found (27280000). A test is made to see if it is regulated (27320000). If so, the interrupt CPU time is added to the interrupt causing program's CPU accumulator in the (TTT) (27400000). Other timing functions not related to the regulator are performed (27440000).

At BLOCK 506 the duration of the previous dispatch is computed (27800000). Then the program resource table (TTT) associated with the previous dispatch is found, BLOCK 507 (27920000). A test is made to see if this program is regulated (27960000). If so, the CPU time is added to its CPU accumulator, BLOCK 508 (28020000). Other timing functions not related to the regulator are performed (28080000). A test is made to see if the CPU is going to wait (28640000, MFT) (28580000, MVT). If so, no program resource table (TTT) is located (28720000) and the TTT pointer is zeroed; otherwise, the TTT is found (28820000). The TTT pointer of this dispatch is saved, BLOCK 509 (28880000) and the registers are restored (2896000, MVT) (29020000, MFT). Finally, the program that was to be dispatched is dispatched, BLOCK 510 (29040000).

Referring to FIG. 5(b) at BLOCK 511, control is received from the operating program (29320000). The peripheral (I/O) operation is started at BLOCK 512 (29420000). A test is made to check for valid condition codes (29440000) (not shown on diagram). If not valid, control is passed to BLOCK 522. Registers are saved at (29480000). A test is made for condition code 1 (29580000). If it is not condition code 1, then the control unit's status is tested (29680000). If the control unit is untimed, then control is passed to BLOCK 522 (29700000). Otherwise, the rest of the registers are saved (29780000).

The current time is found, BLOCK 513 (29820000). This is the time of the start I/0. Next, the peripheral unit tables for the peripheral just started are found at BLOCK 514 (29860000). A test is made to see if this is a disk (29880000). If it is a disk, then a test is made to see if it is a seek (30060000). If it is a seek, then a test is made to see if it is the same cylinder (30120000). If it is the same cylinder, a test is made to see if it is a stand-alone seek (30160000). If it is a stand-alone seek, (30280000), then the registers are restored (30940000) and control is passed to the operating system at BLOCK 522.

If any of the above tests failed, then the program resource table (TTT) is found at BLOCK 515 (30340000). A test is made to see if an interrupt was lost (30360000). If so, the interrupt lost is indicated (30400000). The charge flag is turned on (30440000) and a test is made for non-seeks, BLOCK 516 (30480000). If it isn't a seek, the channel busy flag is turned on (31500000) and control is passed to BLOCK 520. A test is made to see if this operation is for the same program that previously used this peripheral (30600000), BLOCK 517. If not, then the previous program's TTT pointer is saved in the program's peripheral resource table, BLOCK 518 (31840000). The indicator is turned on to indicate a degrading operation, BLOCK 519 (31900000). Some housekeeping is done (31620000) and control is passed to BLOCK 520 (31700000). If it was the same program resource table (TTT), some housekeeping is done and control is passed directly to BLOCK 520.

At BLOCK 520, the new program's resource table (TTT) pointer is saved in the peripheral unit table (30780000). The start time of this peripheral unit is saved, BLOCK 521 (30840000). Registers are reloaded (30900000) and control is returned to the operating system, BLOCK 522 (31060000).

If the start I/O done at BLOCK 512 resulted in a condition code of 1, then a test is made to see if it is contol unit busy (31960000). If not, then return housekeeping is performed (31320000) and control is passed to BLOCK 522 (31420000). Otherwise, register seven is saved (32000000) and a test is made to see if the control unit is timed (32080000). If the control unit is untimed (32100000), then register seven is reloaded (31280000), the return housekeeping is performed (31320000) and control is passed to BLOCK 522 (31420000). If the control unit is timed, the rest of the registers are saved (32140000). A test is made to see if any channel attached to this control unit is busy of if the time is already being billed (32240000). If it is, register seven is reloaded (31280000, the return housekeeping is performed (31320000)) and control is passed to BLOCK 522 (31420000). If it isn't, then the program's resource table is found (32360000) as in BLOCK 515. The logic flow at this point is similar to the device timing described above.

A test is made at BLOCK 517 to see if this operation is for the same program that previously used the control unit (32400000). If so, flags are turned off (32420000), the TTT is stored (32540000) at BLOCK 520 and the return housekeeping is performed (32600000) and control passes to BLOCK 522. Otherwise, a test is made to see if the charge flag is on (32640000). If the charge flag is on (32660000), the return housekeeping is performed (32600000) and control passes to BLOCK 522. If the charge flag is off, the degradation flag is turned on (32680000) at BLOCK 519, the charge flag is turned on (32480000), the TTT is stored (32540000) at BLOCK 520, the return housekeeping is performed (32600000), and control passes to BLOCK 522.

Referring to FIG. 5(c), control is received from the asynchronous interrupt function of the CPU at BLOCK 523 (32900000). After the registers are saved (32980000), local addressability is obtained (33020000). Then the interrupt unit address and channel address are examined (33140000). The current time is obtained, BLOCK 524 (33200000). A test is made to determine if the interrupt is stacked (33220000). If the interrupt is not stacked, then the interrupt time is saved (33280000). Stacked or not, the time of the interrupt is always saved at (33320000).

A test is made to see if the CPU was waiting (33340000). If not, the CPU wait analysis is skipped. The wait analysis routine (43820000) updates accumulators not required by the regulator program. Next, a test is made at (33480000) to determine if the peripheral unit is timed or untimed. If the peripheral unit is untimed, preparations are made for returning control to the operating system (33560000). For timed peripherals, the peripheral control unit entry and peripheral device entry are located at BLOCK 525, (33720000). A test is made to determine if this is a channel end interrupt (33820000). If so, the channel time is accumulated for that channel (35720000).

Next, a test is made for control unit end and/or device end (33880000, 33940000). If only one of the conditions exist, only one pass will be made through the following logic, BLOCKS 526 through 535. If both conditions are present, two passes will be made, one for each condition.

At BLOCK 526, the program resource table (TTT) associated with the peripheral that interrupted is found (34180000). A test is made at BLOCK 527 to see if this operation was degrading (34280000). If not degrading, control is passed to BLOCK 533. If it was degrading, the time is computed for the degrading I/O operation at BLOCK 528 (36960000) and program housekeeping is done (37100000). At BLOCK 529, a check is made to see if the current program has the highest degradation priority (37400000). If so, the previous program's TTT is pointed to for degradation accumulation at BLOCK 530 (37520000). If the current program's degradation priority is not higher, control is passed to BLOCK 531 (37680000). Then, at BLOCK 531 the degradation time is accumulated in the TTT program with the lower degradation priority (37680000). Other housekeeping is done and the charge flag is turned off (37920000).

As noted previously, non-degrading operations pass through BLOCK 533 (34560000). At BLOCK 533, the time is computed for the I/O operation. The time is added to the peripherals associated resource time accumulator in the program resource table (TTT) at BLOCK 534 (34900000).

If both control unit end and device end are present and only one has been processed, control will pass back to BLOCK 526 to process the second interrupt condition.

When all of the above interrupt conditions have been processed, control pass to BLOCK 535 returns to the operating system.

The regulating program according to this embodiment requires a minimal amount of CPU time. The systems utilization data accumulated by the data gathering subprograms previously described is analyzed by a regulating program which regulates CPU and peripheral access to increase or maximize thruput.

The regulating program increases thruput by favoring the more overlapped programs. An overlapped program is one which can use two or more resources in parallel. The more overlapped programs are favored by giving them higher resource access priority than the less overlapped programs. The regulated programs are assigned to two different classes, CPU bound and peripheral bound, based on an analysis of their recent performance. Their CPU priority is calculated to favor overlap and give higher CPU access priority to the peripheral bound programs. The peripheral access priorities are then assigned inversely to the calculated CPU priorities giving CPU bound programs higher peripheral access priority than peripheral bound programs.

Preferably, in addition to analyzing resource activity and assigning resource access priorities, the regulating program analyzes the degradation data collected by the data gathering subprograms and further alters access priorities to reduce or minimize degradation.

FIG. 6 is a flow diagram illustrating the regulating program of this embodiment. Sequence numbers from Appendix A appear within parenthesis throughout the descriptions of this and all other embodiments of the invention. They identify where possible specific OS/360/370 symbolic machine language translations of the functions in the flow diagrams.

FIG. 7 illustrates the assignment of resource access priorities to processing programs A through F by Embodiment I.

The regulating program consists of an operating system interface and a regulating algorithm, described in that order.

The regulating program waits at BLOCK 600 (01640000) for the processing interval to end. When the timer interrupt is fielded, indicating the end of the processing interval, the operating system passes control back to the regulating program. At BLOCK 601, the duration of the next processing interval is specified (10640000).

The next step is to locate the processing programs that are to be regulated. At BLOCK 602 (11860000), a pointer is obtained to the task control block associated with the master scheduler. This pointer points to the beginning of the list of all the processing programs that are currently active in the system. The first test made at BLOCK 603 (11940000) determines if there are any more programs in the list. If more programs exist, processing continues to BLOCK 604. If the end of the list has been detected, control passes to BLOCK 610.

At BLOCK 610 the regulating program determines if any regulated programs were found. If regulated programs have been found, control passes to BLOCK 619. If no regulated programs have been found, then control passes back to BLOCK 600 where the regulating program waits for the end of the next processing interval.

If the end of the list was not detected by the test at BLOCK 603, the next program in the list is examined. At BLOCK 604 (12060000), a test is made to determine if this program is to be regulated. If the answer is no, control passes to BLOCK 605 (11920000) where a pointer to the next program in this list is loaded. Control then passes back up to BLOCK 603. This loop is followed until all programs have been examined, at which point control passes to BLOCK 610.

If the test made at BLOCK 604 indicated that the program was to be regulated, control passes to the regulating algorithm, BLOCK 606 (15160000). The total peripheral time and the maximum peripheral time are calculated at this point.

The next three blocks describe the degradation analysis of this embodiment. Since the regulating algorithm of this embodiment assigns a unique peripheral access priority to all regulated programs, degradation is eliminated by preventing the degrading programs from accessing the CPU.

The first step of degradation analysis, BLOCK 607 (15635000), is to compute the total resource time (T.sub.total). At BLOCK 608 (15636000), the regulating program analyzes the degradation time accumulated during the previous processing intervals and compares the degradation time (T.sub.d) to the total usage (T.sub.total) of all resources: ##EQU1##

If the degradation time exceeds the total usage time for a program, it is prevented from accessing the CPU, BLOCK 609 (15643000), for at least the next processing interval. Referring to FIG. 7, program C would not execute during the next processing interval. In this way, it would not compete with programs B and D for the degradable resource marked 1d. The program's degradation is zeroed and control then passes to BLOCK 611.

According to this embodiment, the CPU priorities are next calculated dependent upon whether the CPU time (T.sub.CPU) is greater than or equal to the maximum peripheral time (TP.sub.max). This test is made at BLOCK 611 (15840000).

Referring to FIG. 6(b), if the program is peripheral bound, control passes to BLOCK 612. At BLOCK 612 (16260000) a test is made to see if the program has accumulated enough history to assure a valid calculation of its CPU priority. If not, its previous CPU priority is retained and control passes to BLOCK 618.

If the processing program is CPU bound, BLOCK 611 passes control on to BLOCK 615. Here, a test similar to that which occurred in BLOCK 612 is made to determine if enough CPU history has been accumulated (15900000). If not, control passes to BLOCK 618.

If the sufficient history exists, as determined by BLOCK 612 or 615, the processing program's productivity factor is calculated and its CPU priority is assigned.

The productivity factor (PF) is calculated at BLOCK 613 or BLOCK 616, according to the following formula: ##EQU2## where T.sub.CPU =the CPU time used;

TP.sub.i =the time for each peripheral resource used;

T.sub.max =the maximum time used on any resource; and,

.alpha.=a CPU preferential weighing factor generally set to one. Note that the more overlapped programs are assigned higher factors. This productivity factor is then used as a degradation priority during the next processing interval and until new access priorities are computed. The program with the lower degradation priority accumulates the degradation time whenever it occurs. In FIG. 7, the productivity factors for programs A to F are shown as calculated using the above-described formula for the systems utilization data given in FIG. 4.

When a peripheral time is greater than the CPU time, the following formula is used to assign CPU access priority in BLOCK 614 (16500000): ##EQU3## where n is equal to the number of peripherals. The CPU priority for programs C through F shown in FIG. 7 were calculated by using formula (b 3) above. The program's resource history is then zeroed.

When the CPU time is greater than or equal to the maximum peripheral time, the following formula is used to assign CPU access priority in BLOCK 617 (16180000): ##EQU4##

Note that the maximum value of this formula is n, the number of peripheral units in the computing system, and it could only occur when all the resources in the system are saturated by the processing program. Thus, all values calculated by formula (4) will be less than all values calculated by formula (3). The CPU priorities of programs A and B shown in FIG. 7 were calculated using the formula (4) above.

Note that the CPU priorities are substantially inverse need assigned. The history is zeroed and control then passes to BLOCK 618.

At BLOCK 618, theprogram is put into an ordered list based upon its CPU priority (17760000).

BLOCK 619 (19340000) is entered from BLOCK 610 after all regulated programs have been analyzed. A pointer to the first program in the list that was created in BLOCK 618 is obtained. At BLOCK 620 (19700000), peripheral resource access priorities are assigned inversely to the CPU priorities. FIG. 7 shows the assignment of peripheral resource priorities according to BLOCK 620. Note that the peripheral resource priorities are also generally inverse need assigned. At BLOCK 621 (20320000), the peripheral resource access queues are sorted according to the new peripheral resource priorities so that sequential requests are not executed out of order. When the sort is finished, control is returned to BLOCK 600 where the regulating program waits for the end of the next processing interval. During the processing interval the operating system uses the new resource access priorities.

In the second thruput embodiment according to this invention, the regulator program performs degradation analysis and assigns the regulated programs a separate inverse need access priority for each active resource. This embodiment requires slightly more CPU time and occupies slightly more main memory space than Embodiment I. This type of pure inverse need resource access priority substantially reduces the chance that a program will be unable to execute because of a nominal need for service froma saturated resource. This embodiment is particularly effective in optimizing computing systems that are predominantly peripheral bound. FIG. 8 and FIG. 9 are used to explain the details of this embodiment.

BLOCK 800 represents the operating system interface with degradation analysis of BLOCKS 600 through 610 Embodiment I. The degradation analysis of BLOCKS 607 through 609 would prevent program C from accessing the CPU during at least the next processing interval. BLOCK 609 would then pass control to BLOCK 801.

At BLOCK 801, a test is made to see if the program has accumulated enough history to assure a valid calculation of its resource access priorities. If not, control passes to BLOCK 804. If the history is sufficient, control passes to BLOCK 802.

At BLOCK 802, the regulator program assigns a separate resource access priority to all of the program's active resources according to the following formula: ##EQU5##

The active resource priorities determined by formula (5) for programs A through F are illustrated in FIG. 9. Control then passes to BLOCK 803.

At BLOCK 803, the program's productivity factor is computed, using formula (2) and its history is zeroed. The PF is used as a degradation priority in exactly the same way it was in Embodiment I, see FIG. 9.

At BLOCK 804, the program is put into an ordered list based upon its productivity factor. Control then passes back into the operating system interface at BLOCK 603.

If the test at BLOCK 610 within the operating system interface is positive, control then passes to BLOCK 805, where a pointer to the program with the highest productivity factor is obtained.

The next step for the regulator program is to assign inactive resource priorities at BLOCK 806. This is done by selecting an arbitrary high priority value, say 100, and assigning it to all inactive resources for the program having the highest productivity factor (PF). The program with the next lowest productivity factor is assigned an inactive resource priority decremented by one and so forth until all programs have been assigned inactive resource priorities, see FIG. 9. Thus, with this embodiment, active resources are inverse need queued, and the inactive resources are queued to favor the more overlapped programs.

Control then passes to BLOCK 807, where all of the peripheral access queues are sorted according to the newly assigned peripheral resource priorities so that as in Embodiment I sequential requests are not executed out of order. When the sort is finished, control is returned to BLOCK 600 where the regulating program waits for the end of the next processing interval. During the processing interval, the operating system uses the new resource access priorities.

Embodiments I and II increase the thruput of the computing system by analyzing individual programs, which is very effective when a small number of programs are involved. When a large number of programs compete for a limited number of resources, and when sufficient CPU processing time is available, optimization by simulation and/or mathematical programming techniques may yield significantly greater thruput. According to this embodiment of the regulator program, a dynamic linear programming (LP) model is used to maximize the total system's resource utilization (thruput) by selecting a subset of programs to be executed.

This embodiment uses a special form of the general linear programming model, which is an established technique for maximizing a linear function where the variables are limited by linear inequalities. The object will be to find an x.sub.1, x.sub.2 . . . , x.sub.n which maximizes the linear function.

where PF.sub.i is equal to the program productivity factor of the i th program and n is equal to the number of programs executing in parallel, subject to the restrictions ##EQU6## where m is equal to the number of active resources and

and

are bivalent, that is, equal to either 0 or 1.

The inequalities of (7) set forth the restriction that a resource cannot be used more than 100% of the time.

The purpose of the model is to find the subset of programs that can run compatibly and provide the maximum possible thruput. The restrictions imposed upon this model are such that the solution values of x will be either 0 or 1. The programs whose x values are equal to 1 represent the subset of programs that should maximize system thruput.

FIG. 10 through FIG. 13 are used to illustrate this embodiment.

BLOCK 1000 represents the operating system interface with degradation analysis of BLOCKS 600 through 610 of Embodiment I. The degradation analysis of BLOCKS 607 through BLOCK 609 would prevent program C from accessing the CPU during at least the next processing interval. BLOCK 609 would then pass control to BLOCK 1001.

At BLOCK 1001, a test is made to see if the program has accumulated enough history to insure a valid calculation of its Percent of MAX's and its productivity factor. If not, control passes back into the operating system interface at BLOCK 603.

If enough history has been accumulated, control passes to BLOCK 1002. At this point, the Percent of MAX is calculated for each of the program's active resources according to the following formula: ##EQU7## The results of Percent of MAX calculations are set forth in the second column of the tables in FIG. 11.

At BLOCK 1003, the program's productivity factor is computed using formula (1). The productivity factor, in combination with the subset priorities, to be explained later, is used to determine the program's degradation priority. The degradation priority is then used in exactly the same way as it was in Embodiment I. The program's history is zeroed and control then passes back into the operating system interface at BLOCK 603.

If the test at BLOCK 610 within the operating system interface is positive, control then passes to BLOCK 1004. At this point, the amount of unused CPU time (wait time) during the previous processing interval is compared to the amount of CPU time required to solve the LP model. If the wait time is significantly larger than the time required to solve the LP model, control passes to BLOCK 1005.

Referring to FIG. 11, the regulating program at this time would construct the following specific LP optimizing function:

At BLOCK 1006 the regulating program determines and assigns the restriction coefficients a.sub.mn according to the following rules:

1. Assign the a.sub.mn coefficients values of 1 if the Percent of MAX is greater than 60% on nondegradable resources, or if the percent of MAX is greater than 15% on degradable resources. The results are set forth in the second column of the tables in FIG. 11.

2. If, according to the previous coefficient assignments, a degradable resource has been assigned a coefficient value of 1 for any of the programs, then all programs that use that resource are assigned a corresponding a.sub.ij value of 1. For example, peripheral 2 for program C(a.sub.33) is assigned a value of 1 although its percent utilization is only 7% because program B had previously been assigned as a coefficient value of 1 for peripheral 2(a.sub.32), see FIG. 11.

3. All remaining coefficients are assigned a value of 0. FIG. 11 illustrates the completed assignment of all a coefficients. The resulting model restrictions are as follows: ##EQU8## Note that there is no inequality expressed for resource (3)d since none of the a.sub.ij coefficient values were equal to 1 for that resource.

At BLOCK 1007, the simplex method, or a revised form of the simplex method, is used to solve this linear programming model. The time of day of this LP solution is then saved for subsequent analysis. For the example shown in FIG. 11, the results are as follows: x.sub.1 is equal to 1, x.sub.2 is equal to 0, x.sub.3 is equal to 0, x.sub.4 is equal to 1, x.sub.5 is equal to 1, and x.sub.6 is equal to 1.

At BLOCK 1008, programs A, D, E and F, comprising the favored subset of programs, i.e., those that should yield maximum thruput, are all assigned resource access priorities of 500. Programs B and C, comprising the unfavored subset, are assigned resource access priorities of 0. These priorities are defined as the subset priorities, see FIG. 12.

If, as a result of the test in BLOCK 1004, insufficient CPU time was available to solve the LP model, control passes to BLOCK 1009. At this point, the time of the last LP solution is examined. If the solution is very old, control passes to BLOCK 1010 where all of the subset priorities are set equal to the unfavored subset's priority which, in this instance, is 0. Control then passes to BLOCK 1011.

In the last LP solution is still considered to be valid, control passes directly to BLOCK 1011.

At BLOCK 1011, all of the peripheral access queues are sorted according to the newly assigned peripheral resource access priorities, so that as in Embodiment I, sequential requests are not executed out of order. When the sort is finished, control is returned to BLOCK 600 where the regulating program waits until the end of the next processing interval. During the processing interval, the operating system uses the new resource access priorities.

According to this embodiment, the regulating program can further increase thruput by incorporating separate resource access priority logic, for example, that of Embodiments I or II. FIG. 13 illustrates a combination of Embodiment III with the resource access priority assignments of Embodiment II.

To accomplish the priority assignment of FIG. 13, the logic flow of the regulating program of Embodiment II in FIG. 8 is slightly modified. BLOCK 1002 is added to FIG. 8 underneath BLOCK 801. BLOCK 1002 would then pass control on to BLOCK 802. Only one other change is required. It is to cause BLOCK 806 to pass control to BLOCK 1004.

The advantages of analyzing program resource contention can be seen by comparing the priorities assigned as the result of Embodiment II (FIG. 9) to the priorities that are assigned as the result of Embodiment III (FIG. 13). With Embodiment II, Program B is favored among all of the programs. However, with Embodiment III Programs A, D, E, and F are all favored over Program B. The result of the regulating program's LP analysis of program resource contention is significantly higher thruput.

The previous embodiments and regulating programs function to maximize systems resource utilization (thruput). Unfortunately, when thruput is maximized, the programs that are assigned low priorities may be delayed significantly. As a result, the projects or people that depend upon results from these low priority programs may incur costly delays.

A program's turnaround is the elapsed time from when the program is first recognized by the computing system to when the computing system completes all processing associated with it. Often, the turnaround characteristics of the computing system are considered to be more important than its thruput characteristics.

Forced sharing of all system resources with all programs will generally give the computing system a good turnaround characteristic. For nondegradable resources, sharing can be accomplished efficiently by assigning all of the programs the same access priority. As discussed previously with reference to FIG. 3(b), this will time-slice the resources among the various programs that need their service. However, assigning equal access priorities to degradable resources will not only kill thruput, but it will significantly degrade turnaround as well.

The regulator program of this shared embodiment of the invention attempts to eliminate degradation by first regulating resource access priorities. Then only after priority regulation fails is a degrading program prevented from accessing the CPU.

Two terms need to be defined before the flow diagram of this embodiment, FIG. 14, is described. The first term is phase. It is defined as an integer number of processing intervals. The second term is hog. It is defined as any program whose resource time over the previous processing interval is greater than that interval length divided by the number of active programs. For example, if the monitor interval is 40 units of time and there are two programs processing in parallel, then any program that receives more than 20 units of service from a resource in the previous interval will be considered a hog.

BLOCK 1400 represents the operating system interface for the regulator program. Note that it does not contain the degradation analysis of BLOCKS 608 and 609.

When control passes out of BLOCK 607 into BLOCK 1401, a test is made to determine if a new phase is to begin. This is done by comparing the phase accumulator with the phase length. If a new phase is to be started, control passes to BLOCK 1406. BLOCK 1406 performs phase initialization, which consists of four steps. The first step is to zero the phase accumulator. The second step is to set all of the program's resource priorities (RP) to a predetermined high value, for example, 100. The next step is to set the program's degradation priority (DP). The first program encountered by the regulator program is assigned a degradation priority equal to the initial resource priority. All subsequent programs are given degradation priorities that are one less than their predecessor. The last step is to guarantee that the program is executable. Control then passes to BLOCK 603 in the operating system interface.

If the new phase test at BLOCK 1401 is negative, control passes to BLOCK 1402. At this point the program's degradation time is compared to its total resource time (productivity). If the degradation time is less than the productive time, control passes to BLOCK 1407. When the degradation time is not less, BLOCK 1402 passes control to BLOCK 1403.

At BLOCK 1403 a test is made to determine if the program's resource priority is equal to its degradation priority. If the priorities are unequal, control passes to BLOCK 1404, where the program's resource access priority is set equal to its degradation priority (eliminating degradation by priority control is preferable to suspending the program's execution). Control then passes to BLOCK 1407.

When priority control has failed to eliminate degradation, BLOCK 1403 passes control to BLOCK 1405. At this point, the program is made not executable for at least the next processing interval. Control then passes to BLOCK 1407.

At BLOCK 1407 analysis is performed to determine if the program is a hog. If the program is not a hog, control passes to BLOCK 1412. If the program is a hog, control passes to BLOCK 1408, where both its resource priority and degradation priority are decremented by a number larger than the maximum number of programs that can be regulated simultaneously. Control then passes to BLOCK 1412.

At BLOCK 1412, the resource time and degradation time of the program are zeroed. Control passes to BLOCK 603 in the operating system interface.

When the test made at BLOCK 610 within the operating system interface is positive, control passes to BLOCK 1409. At this point, a test is made to determine if a resource hog has been found. If no hogs were found, control passes to BLOCK 1411. If a hog was found, control passes to BLOCK 1410. At BLOCK 1410 all programs that had been prevented from accessing the CPU during the previous processing intervals are allowed to again access the CPU during the next processing interval. Control then passes to BLOCK 1411.

At BLOCK 1411 the previous processing interval's time is added to the phase accumulator. Control is then returned to BLOCK 600, where the regulating program waits until the end of the next processing interval. During the next processing interval, the operating system uses the new resource access priorities.

FIG. 15 and FIG. 16 illustrate a sequence of 12 processing intervals according to this embodiment of the invention. The processing interval is 40 units of time long and the phase is 9 processing intervals in length, or 360 units of time. During these 12 processing intervals, Program A and Program B share the same degradable resource.

FIG. 15 illustrates the resource regulation of this regulating program when priority control is effective in eliminating degradation. FIG. 16 illustrates the sequence of events when the regulating program is unable to control degradation with resource priority assignment. Note how service flip-flops, first in favor of one program and then in favor of another, yielding a significantly more efficient sharing of the degradable resource.

With regulating algorithms for optimizing two different computing system performance characteristics, for example, thruput and turnaround, it is possible to vary the computing system's characteristics with time according to this embodiment of the invention. This embodiment makes it possible to adjust the system characteristics to meet a specific or varying load.

A mode of operation is defined as alternating between a share or shared phase and a thruput phase. In FIG. 18 the share phase is 5 processing intervals long and the thruput phase is 5 processing intervals long.

The mode of operation can be biased in favor of either turnaround or thruput. A thruput mode is one in which the number of processing intervals during the thruput phase is larger than the number of processing intervals during the shared phase, see FIG. 19. A turnaround mode is one in which the number of processing intervals during the share phase is larger than the number of processing intervals during the thruput phase, see FIG. 20. Note than an almost unlimited number of different operating modes exists with this embodiment of the invention.

The mode of operation should define more regulating program characteristics than just the shared thruput biasing. The mode control elements in Appendix A control the length of the processing interval, the history values for CPU time and peripheral time, the hog value, and a threshold characteristic that determines whether or not the thruput phase is entered at all. It is desirable to have the mode control element specify all of the critical regulating program characteristics.

It is often desirable to change computing system's performance at different times of day. It is a function of the timetable to specify the desired mode changes at different times of day, see FIG. 21. At just after midnight, the computing system enters a mode consisting of two share processing intervals and 6 thruput processing intervals. It stays in this mode of operation until 8:00 a.m. when it automatically changes to a new mode consisting of 5 shared processing intervals and 2 thruput processing intervals. From 8:00 a.m. until 6:00 p.m. this shared or turnaround mode of operation is used. At 1800 the mode switches back to a thruput mode consisting of 2 shared processing intervals and 6 thruput processing intervals. This mode of operation continues until midnight, at which point the timetable recycles.

The regulating program for Embodiment V is illustrated in FIG. 17. At BLOCK 1700, the regulating program waits for either a processing interval to end or for a timetable interval to end (01640000). When the end of an interval occurs, the operating system passes control back to the regulating program at BLOCK 1701, where a test is made to determine if the timetable interval has elapsed. If it has, control passes to BLOCK 1702.

At BLOCK 1702 (03480000), the next timetable interval is set and the next processing interval is set. Control then passes to BLOCK 1703, (02490000) where the new regulating program characteristics are set. Next, control passes down to BLOCK 1712.

When the test at BLOCK 1701 indicates the processing interval has elapsed, control passes to BLOCK 1709 (10640000). At this point, the next processing interval is set and control passes to BLOCK 1710.

At BLOCK 1710, a test is made to determine if the current phase is over (10880000). If the phase isn't over, control passes to BLOCK 1711. If the phase is over, control passes to BLOCK 1704.

At BLOCK 1711, a test is made to determine if the current phase is a shared phase. If it is, control passes to the shared phase algorithm at BLOCK 1713. If the test at BLOCK 1711 indicates a thruput phase is in process, control passes to the thruput phase algorithm at BLOCK 1707.

If the test at BLOCK 1710 indicated that the phase was over and a new phase is to begin, control passes to BLOCK 1704. At BLOCK 1704 (10920000), a test is made to determine if the ending phase was a thruput phase. If it was, control passes to BLOCK 1712 to start a new shared phase. If the previous phase was a shared phase, control passes to BLOCK 1705.

At BLOCK 1705 (11480000), a sequence of tests are made to determine if there appears to be any advantage in entering the thruput phase. When tests at BLOCK 1705 indicate that there appears to be no advantage to entering the thruput phase, control passes to BLOCK 1712. If, however, the advantages of the thruput phase appear evident, control passes to BLOCK 1706 where the thruput phase is started (11620000). BLOCK 1707 is entered next.

At BLOCK 1707, the thruput phase algorithm is entered. This thruput phase algorithm has been described previously with reference to Embodiment III. After completing the thruput phase algorithm, control passes to BLOCK 1708. Here, the processing interval time is added to the phase accumulator and control is passed back up to BLOCK 1700.

At BLOCK 1712, a new shared phase is started (11000000). Control then passes into the shared phase algorithm at BLOCK 1713. This shared phase algorithm has been described previously with reference to Embodiment IV. BLOCK 1713 then passes control back to BLOCK 1700 where the regulating program waits for the end of the next interval. During the processing interval, the operating system uses the new resource access priorities. ##SPC1## ##SPC2## ##SPC3## ##SPC4## ##SPC5## ##SPC6## ##SPC7## ##SPC8## ##SPC9## ##SPC10## ##SPC11## ##SPC12## ##SPC13## ##SPC14## ##SPC15## ##SPC16## ##SPC17## ##SPC18## ##SPC19## ##SPC20## ##SPC21## ##SPC22## ##SPC23## ##SPC24## ##SPC25## ##SPC26## ##SPC27## ##SPC28## ##SPC29## ##SPC30## ##SPC31## ##SPC32## ##SPC33## ##SPC34## ##SPC35## ##SPC36## ##SPC37## ##SPC38## ##SPC39## ##SPC40## ##SPC41## ##SPC42## ##SPC43## ##SPC44## ##SPC45## ##SPC46## ##SPC47## ##SPC48## ##SPC49## ##SPC50## ##SPC51## ##SPC52## ##SPC53## ##SPC54## ##SPC55## ##SPC56## ##SPC57## ##SPC58## ##SPC59## ##SPC60## ##SPC61## ##SPC62## ##SPC63## ##SPC64##

Having thus described the invention with the detail and particularity as required by the Patent Laws, what is desired protected by Letters Patent is set forth in the following claims.