JPS5935454B2 - Prioritization method and device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a priority determination method and apparatus for dynamically controlling priorities for allocating central processing units (CPUs) to programs in a computer system that performs multiprogramming.

Generally, in a multiprogramming type computer system, each program is assigned a certain priority, and CPU allocation called dispatching is controlled based on this priority. In other words, the first program with the highest priority is running on the CPU, and the second program with a lower priority can be executed on the CPU if the CPU is allocated. Assume that there are l states (ready). At this time, if the first program, for example, executes an I/O instruction and enters a wait state until the 1/0 operation is completed (
1), the second program with the next highest priority is C
It is executed on the PU and enters a running state (Fig. 1, 2). Here, when the I/O operation of the first program is completed, the first program enters the executable READY state (FIG. 1, 4), but the second program currently running on the CPU Since this program has a lower priority than the first program, it is immediately allocated the CPU and enters the RUN state (FIG. 1, 2). As a result, the CPU is taken away from the second program and the second program is returned to the ready state (Figure 1 (2)).Even if there are many priorities, the second program is taken away from the CPU and returned to the ready state. A high priority program can be executed by the CPU, and by increasing the priority, the CPU can be preferentially allocated to that program.

Conventionally, in computer systems, each program has been given a dispatch priority depending on the degree of urgency of the program or the frequency of occurrence of I/0 instructions, and as mentioned above, this priority determines the execution of the program by the CPU. It is being controlled.

It is known that the throughput of the entire system can be increased by giving a high dispatching priority to a program that frequently generates 1/0 instructions.

The frequency of occurrence of I/O commands is determined by the time the program is in a wait state, that is, the wait time (
The ratio of CPU time to wait time is commonly used. However, in this conventional system, the magnitude of priority only represents the order of allocation to the CPU, and does not necessarily correspond to the degree of execution of the program on the CPU. Therefore, in some cases, a situation may occur in which no CPU is allocated to a program with a low priority, and if the priority is low to a certain extent, the processing does not proceed at all. SUMMARY OF THE INVENTION An object of the present invention is to provide a prioritization method and apparatus for overcoming these drawbacks.

That is, according to the present invention, the priority given as an index regarding the relative degree of execution of each program in the CPU (ratio of time in ready state to time in run state), that is, external priority is Given.

In order to provide each program with the CPU service specified by this external priority, the present invention determines an internal priority and dispatches on the CPU accordingly. That is, in the present invention, the degree of service of the CPU to each program is checked at fixed time intervals, and the internal priority order for the next period is determined from this and the given external priority order. In addition, in the present invention, the degree of service allocation by the CPU to each program is determined not only by the execution time of each program by the CPU (hereinafter referred to as run time) but also by the time during which each program is in a ready state (hereinafter simply referred to as ready state). It is calculated by taking into consideration the amount of time (referred to as time).

Such consideration is due to the nature of program operation in computers as described below.

That is, the program executed on the computer is:
Items that use many l/0 instructions or operations that are mostly I/0
There are some things that don't issue orders. The operation of the I/0 device is
It is slow compared to the processing speed of the CPU, and once a 1/0 instruction is issued, the program is interrupted. Therefore, programs that issue many I/O instructions will receive I/O instructions even if their priorities are equal.
/0 Programs that do not receive many CPU services compared to programs that do not issue many instructions6. Therefore, it is inappropriate to determine the degree of execution of a program based solely on the run time that is serviced by the CPU. Not. Furthermore, assuming that the priorities are the same, the ready time will be approximately equal, and if the priority is raised, the ready time will be shortened. Therefore, a short ready time indicates that the degree of service received is high. The present invention utilizes these properties, and the run time and ready time of a program are measured at regular intervals, and the degree of execution of the program is calculated from these values.

The degree of execution of this program is compared with the degree specified by the given external priority to determine the internal priority for the next period, which for said next period is specified by the external priority. Goals will be achieved. In other words, if we consider the case where external priorities are given equally, dispatching priorities will be given so that the ratio of ready time and run time is equal, and a program that uses many I/O instructions will A relatively high dispatching priority is given so that the ready time corresponds to a short CPU time, and a relatively low dispatching priority is given to a calculation-intensive program so that the ready time corresponds to a long CPU time. C
In the case where no PU is allocated at all, the dispatching priority in the next cycle is raised.
Since the /O command occurs less frequently, it is assigned a low dispatching priority, and it is possible to eliminate the disadvantage that the CPU is not given and the processing does not proceed at all.

Next, the present invention will be explained in detail with reference to the drawings. FIGS. 2 and 3 are diagrams showing one embodiment of the present invention. In this embodiment, the ratio R between the ready time and the run time during a certain period of operation with a given internal priority P is calculated, and the value P of the external priority given as a target is calculated.
Modify the internal priority by taking the ratio of E and the aforementioned R, multiplying this value by the internal priority P, and use this modified value as the internal priority for the dispatch in the next time interval. By using this, it is possible to bring the service provided by each program closer to the target by the CPU.

In addition, in this embodiment below, the number of programs executed in the multi-program state is less than N, and
It is assumed that each program is assigned a number 1(g)xN).

Furthermore, in this embodiment, the ratio of ready time to run time is used as the degree of program execution. moreover,
Management table 1 addressed by program number 1
are prepared as shown in FIG. Management table 1
A second field T2 holds the cumulative amount of time the program has been in the ready state during a fixed time interval Tp, a first field t1 holds the cumulative amount of time the program has been in the run state, and It has a third field T1 that holds the time when the program entered the state, a fourth field P that holds the current internal priority, and a fifth field PE that holds the external priority given to each program. , the reference letter T indicates a timer (clock device), which consists of a counter that counts up by 1 every 10 μs (microseconds), and the current time T
OD is measured and a certain time interval Tp (here,
Interrupts the control circuit 4 every 500 milliseconds)
wake up The reference alphabet Td is a register that holds the time when the program was dispatched to the CPU, and this output and the first to third fields Tl,
The values of t2 and t1 are applied to one side of the arithmetic circuit 2 via the switching gate SWl. In addition, the output of the second field T2 of the output TOPl management table 1 of the timer T and the first latch (Tw) connected to the arithmetic circuit 2
The output of No. 3 is applied to the other input of the arithmetic circuit 2 via the switching gate SWl. The output of the arithmetic circuit 2 is also applied to the second latch 5, and the output of this latch 5 is applied to the switching gate S.
It is applied to the human power of the arithmetic circuit 2 via Wl. In addition, the control circuit 4 receives a timing interrupt Itl from the timing device T, a signal Sal indicating that the program i has been assigned to the CPU, a signal Sb indicating that the execution of the program IOCPU has been interrupted, and a signal Sb indicating that the program i has become ready. It receives a signal Sc indicating , and issues control commands such as reading and writing of a management table, commands to arithmetic circuits, storage to registers and latches, and setting of switching gates using these signals as activation signals. Next, the operation of the present invention performed under the control of this control circuit 4 will be explained. Note that at the start of the time interval Tp set by the clock device T, the internal priority value P(1) of each program for the next period is determined, and this value is determined from the fourth value in the management table 1. It is assumed that the priority is stored in field P, and dispatch is performed based on this internal priority order.

Further, it is assumed that the run time t1(1) and the ready time T2(1) on the management table 1 are both 1. At a certain time, when a CPU is assigned to a certain program i, a signal Sa is applied to the control circuit 4.
As a result, the operation shown in FIG. 2a is performed. That is, the TOD at this time indicated by the value of the timer T is the register T.
d, and the calculation circuit 2 calculates the difference between this value and the time T3(1) when this program i became ready, that is, the time that this program i was in the ready state before being dispatched. It is stored in the first latch 3 (Tw). Next, this value and the ready time stored in the second field T2(1) of the management table 1 are added by the arithmetic circuit 2, and the result is sent to the same field in the management table 1 via the first latch 3. It is returned to the storage location T2(1), and the ready time of program i is accumulated. Also, while program i is running, this program i
When this program i becomes unable to be executed by the CPU because it issues a command or a program i with a higher priority than this program i becomes ready, the signal Sb is applied to the control circuit 4. , the operation as shown in FIG. 2b is started.

That is, the difference between the time TOD at this time and the value of the register Td, that is, the time during which the program i was in the running state in the current dispatch is calculated by the arithmetic circuit 2 and stored in the latch 3.

Next, this value is set to i in the first field of management table 1.
is added to the value of the word t1(1) of the program i
The run time is accumulated. Because the I/O command issued by program i has completed, or because program α has a higher priority than program i while it is being executed.
When the program i becomes ready to be executed by taking away the CPU, the signal Sc is applied to the control circuit 4, and as shown in FIG. 2c, the current time, i.e. , the value of the timer T is the i-th word T3(1) of the third field T3 of the management table 1.
This updates the time when the program became ready.

When a timekeeping interrupt is generated by the timekeeping device T, that is, when a predetermined time interval Tp has elapsed, an interrupt generation signal 1t is applied to the control circuit 4, thereby starting the operation shown in FIG. 2d. First, O is applied as program number 1,
The cumulative value of ready time stored in the second field T2(1) of management table 1 and the first field t
1(1) is read out, the arithmetic circuit 2 calculates the ratio R(1), and this value is stored in the second latch 5.

Next, the external priority stored in the fifth field PE(1) of the management table 1 and the fourth field P(1
) is read out, multiplication is performed by the arithmetic circuit 2, and the result is stored in the latch 3. This value is then divided by the ready/run time ratio previously stored in the second latch 5, and the result is passed through the first latch 3 to the fourth field P of the management table 1. It is stored in the storage location P(1) corresponding to the program and used as an internal priority in the next period. Further, the value 1 is stored in t1(1) and T2(1) as initial values. Note that this value 1 corresponds to a unit time of 10 μs.
is set to 1 so that the value 0 is not applied to the divisor during division. These operations are set to program number N-1.
The calculation of priorities and the cumulative values of run time and ready time are initialized for the next period Tp. Note that in the description of one embodiment of the present invention, the specific configuration of the control circuit is not mentioned in order to simplify the explanation, but the control circuit for performing the operations shown in the above description is a normal logic circuit. It is clear that this can be easily realized by a combination of the above or by a microprogram type control circuit.

Further, the above-mentioned signals Sa and Sb of this embodiment are generated by a dispatcher for dispatching programs provided in an information processing apparatus in which the priority determining apparatus of the present invention is used, and the above-mentioned signal Sc is Although this is generated by an interrupt processing mechanism provided in the information processing device, a detailed explanation will be omitted since it is not directly related to the gist of the present invention.

[Brief explanation of the drawing]

FIG. 1 is a transition diagram showing the state of program processing, FIG. 2 is a flowchart for explaining the operation of the priority determining method and device of the present invention, and FIG. 3 is an embodiment of the priority determining device of the present invention. FIG. In Figure 3, reference number 1 is a management table, reference number 2 is an arithmetic circuit, reference numbers 3 and 5 are latches, reference number 4 is a control circuit, reference letter T is a clock device, reference letter Td is a register and reference letter SWl and SW2 respectively indicate switching gates.

Claims (1)

[Scope of Claims] 1. In a priority determination method for determining the priority of each program in a multi-programming computer system that executes a plurality of programs and controlling the priority of allocation to a central processing unit, Check the time during which each program was running on the central processing unit during a certain time interval, that is, the run time, and the time when each program was ready to run on the processing unit, that is, the ready time, and calculate these times. A method for determining priorities, characterized in that: is used as a factor for determining priorities in the next time interval. 2. In a multi-programming computer system that executes a plurality of programs, the time during which each program is being executed by the central processing unit, that is, the run time, and the executable time during which each program is waiting for allocation to the processing unit, namely, a first one having a storage location for respectively holding a ready time and said executable time;
second and third holding means, fourth holding means for holding the current priority of each program, and fifth holding means for holding the time at which one program in the central processing unit is assigned; , a timekeeping device whose contents are counted up at regular time intervals; and a timekeeping device whose contents are counted up at regular time intervals; and when execution of the one program is interrupted in the central processing unit, the current time and the time are stored in the fifth method holding means. The run time of the program is calculated based on the difference between the run time and the current time, and this value is calculated as the cumulative run time of the program up to now, which is stored in the memory location corresponding to the program in the first storage means. This additional value is stored in the storage location of the first holding means in addition to the value, and when a certain program becomes executable, the value of the clocking device is stored in the program in the third holding means. and the value of the clock device and the value stored in the storage location corresponding to the program in the third holding means at the time when the one program is assigned to the central processing unit. The ready time of this program is calculated based on the difference between the above, and this value is added to the cumulative value stored in the storage location corresponding to the program in the second storage means, and this is set as a new cumulative value to the second storage unit. The ready time is stored in the memory location of the holding means, and the ready time at the given time interval is calculated based on the values stored in the storage locations of the first and second holding means corresponding to each program at each given time interval. Calculating means that performs an operation of knowing the cumulative value and the cumulative value of the run time, using these to calculate the priority value of each program at the next fixed time interval, and storing the result in the fourth holding means. and a control means.