JPS6152494B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a dispatching method in a multi-programming information processing system.

In information processing devices, input/output devices are generally slower than central processing units. For this reason,
By storing multiple programs in main memory and executing them while one program is performing input/output operations, the central processing unit (hereinafter referred to as CPU) and input/output device in a computer system A so-called multi-programming method is generally used to effectively utilize physical resources such as

In this multiprogramming method,
When there are multiple programs that can be executed by a CPU, it is necessary to select one of them and allocate the CPU to that program, in other words, to perform dispatching. (below
(abbreviated as DP), and the CPU is allocated to the program with the highest DP value.

In general, when assigning a DP to each program, the information processing system Two factors are considered: the extent to which it contributes to the effective use of physical resources.

In other words, by assigning a high DP to a certain program, it is possible to shorten the waiting time in the CPU and processing time, and by assigning a high DP to a program that frequently uses input/output devices, the input/output The utilization rate of the device can be increased.

The present invention provides a first
By creating a DP by combining the index and a second index indicating the degree of use of input/output devices,
The purpose of this invention is to provide a dispatching method that satisfies both the requirements in terms of response time and resource utilization.

In the present invention, a two-dimensional DP consisting of the first index and the second index is adopted as the DP, and a threshold value is provided for the value of the first index, and the value is higher than the threshold value. If it has a low value, the first index is ignored, and if it is higher than a threshold, its value is reflected in dispatching, thereby reducing resource utilization due to response time requirements. According to the present invention, only programs that require a particularly high response time will have their requirements taken into account during dispatching, and If they are equal, by performing dispatching based on the second index from the perspective of the frequency of use of the input/output device, it becomes possible to measure the effective use of resources and also to meet the demands for response time. .

Next, one embodiment of the present invention will be described.

In this embodiment, the DP is represented by 8 bits as an example, and the first index indicating the degree of response time requirement is used as the upper 4 bits, and the lower 4
As a bit, the second bit depends on the frequency of use of the input/output device.
indicators are used.

In this embodiment, several types of response time requests are provided, and for each type, the target response time given to that type, the severity of achieving the target response time, and the request for achieving the target response time. The initial value and final value of the first index and the increase interval of the first index are given depending on the degree of the increase.

When a certain program is input into an information processing device, an initial value corresponding to the type of the program is given, and from then on, each time the time corresponding to that type elapses, the value is changed to the final value. Deadline control has been introduced to raise the limit.

In addition, in this example, each program
A means is provided to measure the time that the CPU is used and the number of times that the input/output device is used.The number of input/output operations that each program performs while using a certain amount of CPU time is measured, and depending on this number, 4 A function that gives each program a second indicator of the bit value (hereinafter referred to as
It is assumed that the device is also equipped with an APG function (called an APG function).

Next, the configuration of this embodiment will be explained.

In this embodiment, a control table 1 is prepared that has an entry for each program and is accessed by program number. 1 and a second index section 11, 12, a ready flag section 13 that indicates whether the program is currently executable on the CPU, and a pointer section 14 that holds the number of the program with the next highest DP at the present time. ing.

Additionally, a top pointer 2 is provided as a register that holds the number of the program with the largest DP among the programs. This top pointer 2
and the pointer section 14 of the control table 1,
A dispatching queue is maintained that manages programs in descending order of DP. In addition,
It is assumed that the pointer section of the last program in the queue, that is, the program with the lowest DP, has the value -I.

Further, a threshold value register 3 is provided as means for holding the threshold value. A comparison circuit 4 and a suppression circuit 5 are provided as means for correcting DP by ignoring a value less than or equal to a threshold value as a first index. The value of the first index section 11 read from the control table 1 is sent to the comparator circuit 4.
is compared with the value of the threshold register 3, and if the value is larger than this value, the value of the first index is used as the upper 4 bits of DP and has a value smaller than or equal to this value. in case of,
The read value of the first index is suppressed by the suppression circuit 5, and the value 0 is output as the corrected value of this first index value. This is the value of the DP used as the upper 4 bits of the DP. The second index is used as is as the lower four bits.

Therefore, with these DP correction means, if the first index of a certain program is larger than the specified threshold value, the 8 bits of the first and second indexes of program i read from the control table remain unchanged. If the first index is not larger than the threshold, the first index of the upper four bits will be 0, and only the second index of the lower four bits will be output as the DP.

Next, the operation in this embodiment will be explained.

When the first index of a certain program i changes due to the deadline control or when the second index of a certain program i changes due to the APG function, the following operation is performed. It is assumed that normal dispatching is not performed while this operation is being performed.

Here, the updating of the dispatching queue held in the pointer section 14 is performed in two steps: deleting program i from the dispatching queue and inserting it into an appropriate location. Note that when a new program is registered, it is only inserted into the dispatching queue.

To do this, a DP register 10 holding the modified DP read from the control table 1
1. DP register 101 output and control table 1
A DP comparison circuit 102 that compares the corrected DP read from the control table 1, a first pointer register 103 that holds the value of the pointer section 14 read from the control table 1, and a first pointer register 103 that holds the value of the pointer section 14 read from the control table 1; 2, a holding register 105 that holds the changed program number i of the DP, a pointer comparison circuit 106 that compares the output of the pointer section 14 of the control table 1 with the output of the holding register 105, and the A detection circuit 107 that detects that the output of the pointer section 14 of the control table 1 is -1 and a related control circuit 108 are provided.

Deletion of program i from the dispatching queue in the pointer section 1 is performed by the control circuit 10.
8, the following steps are performed. First, the program number i is set in the holding register 105, the value of the top pointer 2 is set in the first pointer register 103, and then the value of the top pointer 2 is set in the first pointer register 103.
The value of the holding register 105 is compared with the value of the holding register 105 by the pointer comparison circuit 106.

a If the values are equal, that is, if the comparison circuit 106 detects a match, the first pointer register 103 output is used as the address in the control table 1.
is read out, the value of this pointer section 14 is set in the first pointer register 103, this value is stored in the top pointer 2, and the deletion is completed.

b If the values are not equal, holding register 10
5 is stored in the control table 1 as an address, and the value of the pointer section 14 is set to the first
It is set in the second pointer register 104 via the pointer register 103.

c Next, the control table 1 is read using the value of the first pointer register 103 as an address, and the value of the pointer section 14 and the value of the holding register 105 are compared by the pointer comparison circuit 106.

d If the pointer comparison circuit 106 does not detect a match, the read value of the pointer section 14 is set in the first pointer register 103, and using this as an address, the control table is run and the pointer comparison circuit 106 detects a match. Repeat d until.

e If a match is detected, the value of the second pointer register 104 is transferred to the first pointer register 10.
3 is written to the pointer section 14 of the control table 1 addressed by 3, and the deletion of program i from the dispatching queue is completed.

Program i is registered in the dispatching queue as follows.

a First, set i in the holding register 105,
Using this as an address, read control table 1 and set the DP corrected by threshold register 3 to DP.
At the same time, the value of top pointer register 2 is set in first pointer register 103.

b Next, the control table 1 is read as an address to the first pointer register 103, and the read corrected DP and the value of the DP register 101 are compared by the DP comparison circuit 102.

c At this time, if the value of the DP register 101 is larger, i has the highest DP, and in order to place it at the beginning of the dispatching queue, the next c-1, c-2 processing is performed.

The value of c-1 holding register 105 is set to top pointer register 2.

The value of the first pointer register 103 is written into the pointer section of the control table 1 addressed by the c-2 holding register 105, and the process ends.

If the value in the DP register 103 is not larger in dc, the value in the first pointer register 103 is set in the second pointer register 104, and
The value of the pointer section 14 of the control table is set in the first pointer register 103, and the same processing as shown in b is performed.

f At this time, if the value of the DP register 101 is larger at c, the second pointer register 104 and the first
In order to insert program i between the programs indicated by pointer register 103, the following f
-1 and f-2 are performed, and the updating of the dispatching queue is completed.

f-1 The value of the holding register 105 is written to the pointer section 14 of the control table 1 using the second pointer register 104 as an address.

Using the f-2 holding register 105 as the address,
The value of the first pointer register is written to the pointer section 14 of the control table 1.

If the value of the DP register 101 is not larger in gf, the operation in e is repeated.

Note that if the value of the pointer portion of the read control table 1 is -1 in d or g, that is, if it is the last dispatching queue, the following processing is performed. That is, the holding register 105 is stored in the pointer section 14 of the control table 1 addressed by the first pointer register.
, and then use the holding register 105 as an address to write the value in the pointer section 1 of the control table 1.
Write the value -1 to 4.

In this embodiment, dispatching is the same as in the conventional information processing apparatus, and is performed as follows.

First, if the currently executing program executes an input/output instruction and the CPU cannot continue processing, the ready flag of the corresponding entry in the control table is set to 0 and the dispatcher is activated.

When the input/output operation is completed, an interrupt occurs, the cause of which is analyzed by the interrupt analysis routine, the ready flag of the corresponding program is set, and the dispatcher is activated.

When the dispatcher is activated, the dispatcher first searches the dispatch queue using the top pointer 2, finds the first program whose ready flag is set to 1, and dispatches that program. .

An embodiment of the present invention has been described above, but the gist of the present invention is to combine the first indicator indicating the response request and the second indicator indicating the degree of resource usage,
When creating a DP, if the first index is higher than the specified threshold, the first index is given priority over the second index, and if it is not higher than the first index, then the first index is given priority over the second index. , ignore this and only use the second indicator,
A DP that can be used as a DP to meet response time and throughput requirements.
The purpose of this invention is to provide a means for providing the following information, and since operations not directly related to this purpose are realized by conventional techniques, detailed explanations are not provided.

For example, this embodiment does not provide a detailed explanation of the specific operations of the deadline control or APG function;
Regarding the APG function, fields are provided in the control table to hold the number of I/Os and CPU consumption time from a certain point, and these corresponding fields are integrated every time an I/O command or dispatching occurs. By calculating this ratio at regular intervals, the second index can be obtained.

In addition, in this embodiment, it is assumed that the dispatching queues are connected to the CPU by pointers, whether they are in a state where the CPU can be used (those in the ready state) or not. It is not necessary to do this, and it is also possible to configure so that only programs in the ready state are registered in the dispatching queue.In addition, in this embodiment, the first index indicating the responsiveness requirement is the conventional one. It stipulates that a timer interrupt is generated and the first index of the control table is rewritten by the deadline control that is specified.
The present invention does not necessarily require deadline control, and deadline control may not be applied to all or some programs, and the first index at the time of input is retained until the program is completed. It's okay.

In addition, in this embodiment, the APG function is applied to all programs, and the APG function is applied to all programs.
Record the CPU time and I/O number, and use this to record the second
However, it is not necessary to use the APG function for all programs, and if the characteristics of some or all programs are known, the second index is calculated in advance. It is also possible to provide the following values, in which case there is no need to perform measurements while the program is running.

[Brief explanation of the drawing]

The figure shows an embodiment of the present invention, in which 1 is a control table, 2 is a top pointer, 3 is a threshold register, 4 is a comparison circuit, 5 is an inhibition circuit, and 101 is a DP.
register, 102 is the DP comparison circuit, 103 is the first
104 is a second pointer register, 105 is a holding register, 106 is a pointer comparison circuit, 107 is a -1 detection circuit, and 108 is a control circuit.

Claims (1)

[Claims] 1 means for holding a first index set according to the degree of response request of each program and a second index set according to the degree of use of the input/output device, and a threshold value for the first index; If the first index of each program is greater than this threshold, the first index and the second index are output as the dispatching priority of that program, and if it is not greater than the held threshold. includes a dispatching priority correction means that ignores the first index and outputs only the second index as the dispatching priority, and dispatching of each program modified by the dispatching priority modification means. Means for maintaining the magnitude relationship of the dispatching priorities as a dispatching queue; A dispatching method characterized by having means for updating a dispatching queue.