JPS6365977B2 - - Google Patents

Description

[Detailed Description of the Invention] The present invention provides a scheduling control method, in particular, a system in which a plurality of processes execute data processing while communicating with each other, in which part of the scheduling control is entrusted to hardware processing. This invention relates to a scheduling control method.

In conventional data processing systems, when a program accesses hardware or software resources (program blocks such as tasks), it requests processing from the management program for each resource, and accesses the resources through the execution of the management program. . If there are multiple programs to access, a queue is set up between the accessing program and the management program, and when an access request occurs, the access request event is linked to the queue, and the management program sequentially retrieves the request event from the queue and processes it. Execute. For example, when a program makes a processing request to a task, the request event is linked to the task queue, the task dispatcher (task resource management program) is executed, the request event is retrieved from the task queue, and the task that executes the request event is activated. . Also, if the program is I/O
When making an access request to a device, the request event is linked to the I/O queue, and the input/output scheduler (I/O device resource management program) is executed to extract the request event from the I/O queue and process the request event. Start the input/output program to be executed. Conventionally, all of the above operations are performed by software, and the scheduling control of each resource is performed independently of each other, but these operations are an overhead when performing data processing and need to be reduced.

In order to solve the above-mentioned drawbacks, the present invention centrally manages the parts corresponding to the queues of each resource by arranging them in a matrix configuration on the S-table memory, and also realizes the S-table memory with hardware. It is characterized by providing a means (instruction) for registering and deleting processes in the S table memory and searching for the next process to be executed, and using this means to manage the scheduling of processes. The goal is to reduce ring overhead.

FIG. 1 is a conceptual diagram of the scheduling control method of the present invention, where 1 is the process identification number (QN).
S-table memory with a matrix configuration of m rows and n rows, which is addressed by a processing execution priority number (LN), 2
3 is one information block in the S table memory consisting of a count section (CNT) indicating the number of connected messages and a pointer section (PTR) indicating the position of the first message; 3 is the main memory memory (MEM);
101, 102 is the message body, 103, 10
4 is a pointer block consisting of a part (MA) pointing to the first main memory address of the message body and a part (PA) storing the main memory address of the next pointer block.

In the S table memory 1, QN is associated with access resources, ie, processor resources, I/O device resources, memory resources, task (program) resources, etc. Further, the LN is associated with the execution priority level of the processing process to be accessed. In the scheduling control method of the present invention, the management program for each of the access resources uses instructions for registering and deleting processes in the S-table memory and the S-table memory, and searching for the next process to be executed from the S-table memory. A processor scheduler, an input/output scheduler,
It implements some of the functions of a memory allocation scheduler, task dispatcher, etc.

Figure 2 shows the same QN registered in main memory,
This is a diagram showing the connections between pointer blocks belonging to LN, where 1 is S table memory, 2 is one information block in S table memory, 3 is main memory memory, 4 is the earliest registered pointer block, and 6 is a diagram showing the connections between pointer blocks belonging to LN. is the pointer block registered the latest, and 5 is the pointer block registered between blocks 4 and 6.

As shown in FIGS. 2A and 2B, there are two main methods for connecting pointer blocks. First, in the method shown in FIG. 2A, the PTR of the S table memory points to the earliest registered pointer block 4, and among the pointer blocks, points from the earliest registered pointer block 4 to the latest registered pointer block 6. This is a method of accruing points. In the method shown in Figure 2B, the PTR of S table memory is
points to the latest registered pointer block 6, and points to the latest registered pointer block 6.
The system points to the pointer block 4 that was registered earliest, and points from the pointer block 4 that was registered earliest to the pointer block 6 that was registered latest among the pointer blocks.

Next, the operations of three types of instructions for registering and erasing a process in the S-table memory 1, and searching for a process to be executed next from the S-table memory 1 will be explained below. As shown in Fig. 2, the operation of each of the above instructions differs slightly depending on the method of linking between pointer blocks, but if one method is shown, the others can be easily inferred, so here we will discuss the case of the method shown in Fig. 2A. Only shown. The queuing algorithm of the pointer block is FIFO (First In First Out).
shall be.

(1) Process registration command <operand> Process identification number; QN Process execution priority number; LN Message pointer block address to be registered; MAP <process> S table memory 1 addressed by QN and LN
CNT and PTR are read out, the connection of message pointer blocks on the main memory 3 addressed by PTR is searched, and the value of MAP is written in the PA section of the message pointer block 6 that was registered the latest.

S table memory 1 addressed by QN, LN
Add 1 to the CNT part.

(2) Process deletion command <Operand> Process identification number; QN Process execution priority number; LN <Process> S table memory 1 addressed by QN and LN
The PTR is read and the contents of the PA portion of the message pointer on the main memory 3 addressed by the PTR are written to the PTR.

S table memory 1 addressed by QN, LN
Decrease the CNT part by 1.

(3) Search instruction for the next process to be executed <operand> General-purpose register (GR) number that stores the main memory address of the message block processed by the next process to execute; J Process identification number of the next process to execute (QN) and the processing execution priority number (LN);
From QN=1, LN=1, QN=
1. Go to LN=m, then repeat the same process with QN=2, finally QN=n, LN=
m), search for LN and QN such that CNT≠0. The search is performed once for LN where CNT≠0,
The process ends when QN is found.

Store the retrieved QN and LN in the general-purpose register GR specified by I.

The contents of the PTR section in the S table memory 1 addressed by the searched QN and LN are stored in the general-purpose register GR specified by J.

In an actual system, in addition to the above three instructions, an instruction for resetting the S table memory 1 (setting all CNT sections to all 0s) is required, but a detailed explanation will be omitted. Further, although the functions of each of the above instructions have been explained assuming that the S-table memory 1 is provided in the CPU, the S-table memory 1 can also be placed in the main memory. At this time, the processing of each of the above instructions is slightly different, but since it can be easily inferred, it will not be explained again. As an example, FIG. 3 shows the flow of operations when the above three instructions are applied.

FIG. 3 shows the flow of the scheduling control method of the present invention, in which 11 and 12 are scheduling programs, 13, 14, 15, and 16 are instructions related to S table memory, and 17 and 18 are processes. Execution programs 19, 20, and 21 are S table memories (as an example, QN=4 and LN=4. The values written therein are the values of the CNT section). Also, those shown in bold frames are QNs and LNs that were subject to registration or deletion.
, and the dotted line frames represent QNs and LNs searched by the search command.

Next, process scheduling control will be explained with reference to FIG. For convenience of explanation, S
It is assumed that the table memory is composed of a 4×4 matrix. Assume that the S table memory is now in the state shown in FIG. 19, and the scheduling program 11 is searching for a process to be executed next. In this state, when the scheduling program 11 executes the search command 13, the S table memory is searched for the execution priority side and the process to be executed next (QN=1, LN
The address of the most recently registered pointer block (corresponding to 103 in FIG. 1) and QN and LN at that time are stored in the general-purpose register.
Next, based on the contents of QN and LN stored in the general-purpose registers, a normal instruction (instructions other than those related to the S table memory) is processed to branch to the start address of the process execution program 17 to be executed next. The process execution program 17 extracts a message based on the address of the pointer block stored in the general-purpose register and executes a predetermined process. When a request to execute a process with QN = 4 and LN = 1 is issued, S Perform registration processing for QN=4 and LN=1 in table memory. At this time, the S table memory is in the state shown in FIG. When the process execution program completes a predetermined process, it passes control to the scheduling program 12. The scheduling program 12 is a process (in the example, QN=1,
LN=3) is deleted from S table memory. When this command is executed, the S table memory becomes in the state shown in 21 in the figure. Similarly, scheduling control can be performed by supporting commands for registering and erasing processes in the S-table memory and retrieving the next process to be executed from the S-table memory.

FIG. 4 shows an example of the hardware configuration of the S-table memory, where 31 is the CPU, 32 is the CPU processing block other than the S-table memory-related parts, 33 is the S-table memory, 34 is the main memory (MEM), 35 is a memory for storing information in the S table memory (contents of the CNT section and PTR section); 36 is a memory for reading information from the memory 35;
Register (AR) for storing write address, 37
is a register (WTDR) that holds data written to the memory 35; 38 is a register (RDDR) that holds data read from the memory 35; 39, 40,
41 and 42 are data lines from the processing block section 32 to the registers 36 and 37, from the register 37 to the memory 35, from the memory 35 to the register 38, and from the register 38 to the processing block section 32, respectively;
43, 44, and 45 are registers 36 and 3, respectively.
A control line for instructing data setting to 7 and 38, 4
6 and 47 are control lines for instructing the memory 35 to write and read data, respectively; 48 is the register 3;
6 is the address line of the memory 35 stored in the memory 35.

In this example, we are considering configuring the S table memory as a 4x4 matrix, so the memory 35 is 16
It has 1 address. The operation of writing and reading data to and from the memory 35 is the same as a commonly used method and is a well-known fact, so a description thereof will be omitted. The instructions for registering and deleting processes in the S table memory and searching for the next process to be executed are executed by the hardware functions of the processing block section 32 that executes instructions other than those mentioned above (decoding of instructions, data writing to the memory 35). creation, manipulation of data read from the memory 35, control of the various signal lines 43 to 47 that control the S table memory 33, etc.) and the functions of the S table memory 33.

As described above, according to the present invention, in a system in which a plurality of processes perform data processing while communicating with each other, unified scheduling control is performed using S table memory for various process execution requests. That's what I do. Therefore, it becomes possible to uniformly and quickly process a considerable part of the scheduling control, which was conventionally controlled by software control using independent algorithms for each resource.

[Brief explanation of drawings]

Fig. 1 is a conceptual diagram of the scheduling control method of the present invention, Fig. 2 is an explanatory diagram showing connections between pointer blocks, Fig. 3 is a flowchart of the scheduling control method of the present invention, and Fig. 4 is an S An example of a hardware configuration of an embodiment of a table memory is shown. In the figure, 1 is S table memory, 2 is 1 in S table memory
1 information block, 3 is main memory, 101,
102 is the message body, 103 and 104 are pointer blocks, 4 is the earliest registered pointer block, 6 is the latest registered pointer block, 5 is the pointer block registered between 4 and 6, 11 and 12 are Scheduling program, 13, 14, 15, 16 are S table memory related instructions, 17, 18 are process execution programs, 1
9, 20, 21 are S table memory, 31 is CPU, 3
2 is a part other than the S table memory of the CPU, 33 is an S table memory, 34 is a main memory, 35 is a memory for storing information in the S table memory (contents of the CNT section and PTR section), and 36 is a memory 35 A register 37 stores read and write addresses for the memory 3.
A register 38 holds data to be written to the memory 35, and a register 38 holds data read from the memory 35.

Claims (1)

[Claims] 1 In a system where multiple processes execute processes while communicating with each other, the process identification number QN given to identify the process and the process execution priority number LN given to the process group executed by the process are expressed as line numbers. and a scheduling matrix table memory (referred to as S table memory) that stores control information for managing communication information of the process executed by the process at the address designated as the column number, and a scheduling matrix table memory (referred to as S table memory) that stores the control information on the S table memory. and a main memory for storing a group of connected communication information, and the control information includes:
It consists of an address part that indicates a group of communication information on the main memory memory and a count part that indicates the number of communication information in the group of communication information. When an instruction for requesting the execution of a process is executed, the control information addressed by the specified QN and LN is read from the S table memory, and when a deletion request is made in accordance with the request, the counting section of the control information is read out. The value of the control information is changed by -1, or when an execution request is made, the value of the count section of the control information is changed by +1, the control information is rewritten, and then written to the S table memory, and further linked to the control information on the storage memory. Executes a means for removing the communication information specified at the time of deletion request or concatenating communication information specified at the time of execution request from among the group of communication information contained in the existing communication information group, and a command for requesting a process search for the next process to be executed. When this happens, the control information in the S table memory is read sequentially in order of execution priority, and it is checked whether the value of the count part in the control information is 1 or more, and if the value of the count part is 1 or more, QN and LN that address the control information and the control information when the control information is detected
1. A scheduling control method, comprising: means for reading out.