JPH0247772B2 - MACHIGYORETSUSEIGYOHOSHIKI - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a queue control method, and more particularly, to a control method that can minimize the data area required to form a queue and prevent an increase in main memory capacity. It is related to.

A computer system includes various shared resources, such as a central processing unit (CPU), channels, memory, lines, etc. As a result of the introduction of multiple programming to improve the efficiency of computer system usage, a large number of processes exist within the system.
The limitations of available shared resources result in queuing due to competition for these resources.

On the other hand, the memory of a computer system has
Management of shared resources, scheduling of jobs and flow of control, management of program combinations, commands, job control language, etc. Interface with users such as receiving job processing instructions from users and outputting job output, An operating system is stored therein, which has functions related to file access and the like that are used in subroutines by user programs.

By the way, when forming a queue, pointer areas necessary for forming the queue have conventionally been provided in all control tables that may be registered in the queue. However, all of those control tables are never enqueued at the same time, and when they are enqueued, there are usually only a few, so many control table pointer areas are wasted. .
Moreover, as the number of control tables increases, the amount of wasted pointer area increases, resulting in an enormous amount of memory occupied by the entire operating system (hereinafter referred to as OS), which puts pressure on the user area. There is a problem that

Typical queues that occur in computer systems are execution queues for user programs (hereinafter referred to as tasks) and shared resource occupancy queues between tasks.

FIG. 1 is an explanatory diagram of an OS control table necessary for forming a conventional queue.

The OS provides tables 100, 120, . Also, the OS is
In order to manage the execution queue, an execution queue queue header 15 corresponding to the priority level of the task is provided.
0.155 and a queue header 160 for shared resource occupancy queue corresponding to various shared resources,
170 are provided respectively.

The above various queues are stored in the task management tables 100 and 11 in the corresponding queue header.
Therefore, each task management table 100, 110, 120, 130 includes information 110 for managing the state of the task, as well as information for the execution queue. forward pointer 102, backward pointer 1
04, and a forward pointer 106 and a backward pointer 108 for the shared resource occupancy queue. The need to provide both forward and backward pointers allows for fast control when removing part of a ring of addresses or when joining sequential tasks to the end of a queue. It's for a reason.

In addition, each queue header 150, 155, 16
0,170 also have forward pointer 15 respectively.
2,162 and backward pointers 154,164 are provided. The size of these forward and backward pointers is 4 bytes each.

FIGS. 2a and 2b are explanatory diagrams each showing a conventional queue management state.

When there is a task for which an execution request has been issued, the OS inserts the management table for that task at the end of the execution queue managed by the execution queue queue header 150 corresponding to the priority level of that task.
Make the task wait for its turn to execute.

Now, as shown in FIG. 2a, the task management table 10 is stored in the execution queue queue header 150.
0 and 120 are connected, and when inserting the task management table 130 next to the table 120, the OS sets the start address of the table 130 in the forward pointer 122 of the task management table 120, and pointer 13
2, the start address of the queue header 150 for the execution queue is set, the start address of the table 120 is set in the backward pointer 134 of the table 130, and the start address of the table 130 is set in the backward pointer 154 of the queue header 150 for the execution queue. Possibly task management table 1
30 is registered in the execution queue managed by the queue header 150. When the task's turn for execution comes and the processing is completed, the management table for that task is removed from the execution queue by the OS.

On the other hand, if a task waits for exclusive use of a shared resource during execution, the OS stores the management table for that task at the end of the shared resource exclusive queue managed by the exclusive queue header 160 corresponding to that shared resource. and suspends execution of the task until the shared resource is no longer held.

In this case, as shown in FIG. 2b, when the task management tables 180 and 190 are already connected to the execution queue queue header 155,
The task management table 190 is not removed from the execution queue and newly connected to the shared resource occupancy queue queue header 160; A method is used in which a user remains connected to a queue and also connects to another shared resource occupancy queue. That is, the task management table 190
queue header 16 while executing a task corresponding to
When a shared resource corresponding to 0 is waiting for occupancy, assuming that no table is connected to the queue header 160, the OS stores the start address of the table 190 in the forward pointer 162 and backward pointer 164 of the queue header 160. Set forward pointer 1 of table 190
By setting the start address of queue header 160 in queue header 96 and backward pointer 198, table 190 is registered in the shared resource occupancy queue managed by queue header 160. When the shared resource occupancy queue is released, the management table 190 for that task is removed from the occupancy queue by the OS.

In this way, conventionally, the task management table 10
0, forward pointers 102, 106, backward pointers 104,
It is necessary to provide 108 bytes, and 16 bytes are used as a pointer for each management table case. For example, if the number of registered tasks is 256, the total memory capacity required for the management table pointer is 4096 bytes (= 16 x 256), and the number of tasks connected to the execution queue at the same time is estimated to be large. Assuming that there are 32 pointers, the pointer area effectively used at that time is 512 bytes (= 16 ×
32), and the other 3584 bytes are wasted.

An object of the present invention is to eliminate such conventional drawbacks by minimizing the capacity of the control table required to form a queue, eliminating wasted area, and, moreover, using the same method as the conventional method. An object of the present invention is to provide a queue control method that allows a user to operate a queue through an interface.

In order to achieve the above object, the queue control method of the present invention stores pointers necessary for forming a queue.
A second control table consisting only of the pointer is separated from the first control table containing information for managing the state of the task.
After configuring a control table and setting the start address of the first control table on the second control table and registering it in the queue, when the processing is completed, the settings on the second control table are The feature is that it is canceled and separated from the above queue.

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 3 is a schematic block diagram of a queue control system illustrating an embodiment of the present invention.

The area on the main memory 300 that stores the OS is
Task management tables 400, 420, . Queue header 480 manages matrix pointer tables (hereinafter referred to as queue blocks) 490, 495 and their free space.
Control tables such as the following are provided. In addition, programs 310, 315, etc. are also stored.

The processing device 370, which is a shared resource, includes an arithmetic circuit 340, a control circuit 350, and a control memory 360.
An interface circuit including a memory address register 330, a memory data register 335, etc. is provided, and its operation is the same as that of the conventional one. That is, the address of the next instruction to be executed is set in the memory address register 330 via the arithmetic circuit 340 in response to a command from the control circuit 350, and by issuing an access request to the main memory 300, the address of the next instruction to be executed is set in the memory address register 330 via the arithmetic circuit 340. The next instruction to be executed is read and set in memory data register 335. The instruction set in the memory data register 335 is immediately sent to the control circuit 350, where it is decoded and stored in the control memory 335.
Among the microprograms stored in 60, the microprogram 70 executes the instructions.
0,900,1100,1150,1400,1
Control is passed to 450. The control circuit 350 sequentially reads out and decodes the microprogram from the control memory 360, and based on it reads out the microprogram from the control memory 360 and executes the arithmetic operation circuit 34.
0, memory interface, and memory control circuit 3
Control 20.

The queue operation instructions newly established according to the present invention are as follows:
Microprogram 700, 900, 1100,
1150, 1400, 1450.

FIG. 4 is a structural diagram of a control table showing an embodiment of the present invention.

Task management table 400, 420,...430
are arranged in order of task number as before,
The start address is managed by a pointer 440. The composition of one case of the task management table is as follows:
The task status information area 404 that remains after removing the queue pointers (16 bytes) from the conventional task management table and the pointer 402 (4 bytes) for associating the queue blocks 490, 495, etc. when connecting to the queue. ).

Queue blocks 490 and 495 are tables containing pointer information necessary when forming a queue, and the configuration of one case is a forward pointer 492 for the first queue (execution queue), a backward pointer 494, and a backward pointer 494 for the second queue (execution queue). It consists of a forward pointer 496 for the shared resource occupancy queue, a backward pointer 498, and a pointer 499 for the associated table, and is 20 bytes (4 bytes x 5) in total. These queue blocks 49
0,495 is managed as an empty queue block list in the initial state, that is, when not in use.
A free management queue header 480 is newly provided for this management. Free space management queue header 480
has a forward pointer 482 and a backward pointer 484 for connecting empty queue blocks.
The execution queue queue headers 450 and 455 are execution queue queue headers corresponding to the priority levels of tasks having bidirectional pointers, as in the past, and the queue headers 455 for shared resource occupation queues
60 and 470 are dedicated queue queue headers corresponding to each shared resource that have bidirectional pointers as in the conventional case.

FIGS. 5a and 5b are explanatory diagrams of a queue forming method showing an embodiment of the present invention.

In FIG. 5a, the task indicated in the task management table 550 is placed in the execution queue queue header 4.
50 will be described.

When an execution request is issued to a task shown in the task management table 550, the OS selects one queue block 500 from the head of the free queue block matrix managed by the free management queue header 480.
, and set the start address of the queue block 500 in the pointer 552 of the task management table 550, and set the start address of the table 550 in the table pointer 509 of the queue block 500.
0 and the queue block 500.
Furthermore, the OS performs an operation for inserting the queue block 500 into the execution queue in the same manner as before. That is, information is set so that the forward pointer 502 of the queue block 500 holds the start address of the next queue block 510 in line, and the backward pointer 504 holds the start address of the queue header 450 for the execution queue lined up before it. do. Note that when another queue block is connected next to the execution queue queue header 450, the head address of the queue block in front of it is held.

Next, in FIG. 5B, it is assumed that the shared resource corresponding to the shared resource occupancy queue queue header 460 is waiting for occupancy while the task represented by the task management table 590 is being executed.
In this case, the queue block 540 corresponding to the table 590 is inserted into the exclusive queue managed by the queue header 460, but the pointer values of the queue header 460 and queue block 540 are This is the address of the forward pointer 546 for 2 queues. That is, the OS sets the address of the forward pointer 546 of the queue block 540 in the backward pointer 464 of the queue header 460, and sets the start address of the queue header 460 in the forward pointer 546 and backward pointer 548 of the queue block 540.

FIG. 6 is an explanatory diagram of a queue operation command showing an embodiment of the present invention.

In FIG. 6, uppercase letters (letters) indicate mnemonics of each instruction, and child letters (letters) indicate operands. topqhd is the top address of the queue header,
toptbl indicates the start address of the table, reg indicates the register number, and eaddr indicates the jump destination address in the event of an error.

(a) The GTFQT instruction removes one queue block QB from the head of the free queue block list managed by the free management queue header EQBH indicated by topqhd, and matches the task management table TCB indicated by toptbl with that queue block QB. It performs the function of attaching the queue block QB and setting the start address of that queue block QB to the register indicated by reg. At this time, if there is no free queue block QB in the free management queue header EQBH indicated by topqhd, do nothing and
Jump to the address indicated by eaddr.

(b) The FREQT instruction cancels the association between the queue buffer QB associated with the task management table TCB indicated by toptbl and its task management table TCB, and
It functions to insert at the top of the free queue block list managed by the free management queue header EQBH indicated by topqhd.

(c) The INQLT command uses the queue header indicated by topqhd.
Functions to insert the task management table indicated by toptbl (actually the queue block QB corresponding to this task management table TCB) at the end of the queue managed by EQBH so that the queue becomes the first queue. .

(d) The INQLS command uses the queue header indicated by topqhd.
At the end of the queue managed by EQBH, there is a table indicated by toptbl (actually, a queue block (QB) corresponding to this table TCB).
The function is to insert the queue so that it becomes the second queue.

(e) The RMVQT instruction serves to remove the table indicated by toptbl (actually, the queue block QB corresponding to this table TCB) from the first queue.

(f) The RMVQS instruction serves to remove the table indicated by toptbl (actually the queue block corresponding to this table) from the second queue.

FIG. 7 is a flowchart of the processing procedure of the GTFQT instruction shown in FIG. 6, and FIG. 8 is an explanatory diagram of data manipulation of the GTFQT instruction.

In block 705, as shown in FIG. 8a,
The contents of the forward pointer 482 of the free management queue header 480 indicated by topqhd 602 are retrieved. Next, block 710 compares the contents of forward pointer 482 with topqhd 602 (i.e., the top address of management queue header 480);
Check whether there are any free queue blocks.

That is, if the forward pointer 482 points to the queue header itself, this means that nothing is connected, so the contents of the pointer 482 are checked. If the comparison results are equal, there is no free queue block, so the process advances to block 735 and is left to the user's processing. In other words, set eaddr in the program counter so that the program branches to eaddr. Move to the command at eaddr address.

If there is a free queue block, block 715
Then, the contents of the forward pointer 482 (that is, the start address of the free queue block) are set to reg606.
(dotted line arrow in FIG. 8).

Next, in block 720, the queue block 810 at the head of the free queue block list is removed from the list by performing the following operations. That is, the contents of the forward pointer 812 of the queue block 810 are set to the forward pointer 482 of the free management queue header 480 (dotted arrow in FIG. 8), and the contents of the forward pointer 812 of the queue block 810 are set to
14 is set in backward pointer 824 of queue block 820 (or backward pointer 484 of management queue head 480) indicated by the contents of forward pointer 812 (dotted arrow in FIG. 8).

Next, in block 725, the queue block 810 is associated with the table 830 indicated by toptbl 604 by the following operation (see FIG. 8b). That is, toptbl 604 (i.e.,
The start address of the queue block 810 set in the register 800 in block 715 is set in the pointer 832 of the table 830 (dotted line arrow in FIG. 8). When the processing of block 725 is completed, this instruction is completed, and the process moves to execution of the instruction at the next address (730).

By moving from the state shown in FIG. 8a to the state shown in FIG. 8b, one of the empty queue blocks 810 becomes
This means that it is associated with the table 830 indicated by toptbl.

FIG. 9 is a flowchart showing the processing procedure of the FREQT instruction in FIG. 6, and FIG. 10 is a data manipulation diagram thereof.

In block 905, the contents of pointer 1032 of table 1030 indicated by toptbl614 (the top address of queue block 1010 corresponding to that table) is retrieved. Next, block 91
0, the following operation will change the queue block 10.
10 is inserted at the beginning of the free queue block list indicated by topqhd 612 and managed by queue header 480. That is, queue header 4
80 to the forward pointer 1012 of the queue block 1010, topqhd 612 to the backward pointer 1014 of the queue block 1010, and the backward pointer 1 of the queue block 1020 indicated by the contents of the forward pointer 482 of the queue header 480.
024 (or backward pointer 484 of queue header 480) to pointer 1 of table 1030.
Set the contents of 032.

Next, in blocks 915 and 920, table 1030 and queue block 10 are
The association with 10 is canceled. That is, all zeros 1000 are set in the pointer 1032 of the table 1030 and the pointer 1019 of the queue block 1010, respectively. When block 920 ends, this instruction ends, so the instruction at the next address is executed (925).

FIG. 11A is a flowchart showing the processing procedure of the INQLT command in FIG. 6, and FIG. 12 is a data operation diagram thereof.

Block 1105 retrieves the contents of pointer 1232 of table 1230 indicated by toptbl624. Next, in block 1110,
The contents of the backward pointer 454 of the task execution queue queue header 450 indicated by topqhd 622 are retrieved.

Next, in block 1115, the queue block 1210 indicated by pointer 1232 of table 1230 is inserted at the end of the queue as the first queue managed by queue queue header 450 according to the following contents. That is, the backward pointer 454 of the cue header 450
Forward pointer 1202 of queue block 1200 (or forward pointer 452 of queue queue header 450) and backward pointer 454 of queue queue header 450, indicated by the contents of
Set to . By terminating block 1115, this instruction is terminated and execution of the next instruction is started (1120).

FIG. 11B is a flowchart showing the processing procedure of the INQLS command in FIG. 6, and FIG. 13 is a data operation diagram thereof.

The difference between the INQLT command and this command (INQLS) is that the former targets the first queue, while the latter targets the second queue. That is, blocks 1155 and 1160 in FIG.
has the same content as blocks 1105 and 1110 in FIG. 11A, so the difference between block 11
65 will be explained.

In block 1165, the queue block 1310 indicated by pointer 1332 of table 1330 is inserted into the queue managed by shared resource occupancy queue queue header 460 as a second queue at the end of the queue by the following operation.
That is, forward pointer 1306 of queue block 1300 (or forward pointer 46 of queue queue header 460
2) is set to the forward pointer 1316 of the queue block 1310, the contents of the backward pointer 464 of the queue queue header 460 are set to the backward pointer 1318 of the queue block 1310, and the contents of the pointer 1332 of the table 1330 are set to 8 (bytes) 1340. plus the value (i.e.
Forward pointer 131 of queue block 1310
6 address) to forward pointer 1306 of queue block 1300 (or forward pointer 462 of queue queue header 460) and backward pointer 464 of queue queue header 460.
Set to .

FIG. 14A is a flowchart showing the processing procedure of the RMVQT command in FIG.
The figure is also a data operation diagram.

Block 1405 retrieves the contents of pointer 1542 of table 1540 indicated by toptbl642. Next, in block 1410, pointer 1542 of table 1540 is set by the following operation.
Remove the queue block 1510 indicated by the contents of the queue block 1510 from the first queue to which it is connected. The contents of the forward pointer 1512 of the queue block 1510 are transferred to the forward pointer 15 of the queue block 1500 as indicated by the contents of the backward pointer 1514.
02 (or execution queue queue header 450
The contents of the backward pointer 1514 of the queue block 1510 are set to the backward pointer 1524 of the queue block 1520 (or the backward pointer 454 of the queue queue header 450) indicated by the contents of the forward pointer 1512.

When the processing of block 1410 is completed, this instruction ends and the execution moves on to the next instruction (1415).

FIG. 14B is a flowchart showing the processing procedure of the RMVQS command in FIG. 6, and FIG. 16 is a data operation diagram thereof.

The difference between the RMVQT command mentioned earlier and this command is
The former is for the first queue, while the latter is for the second queue. Therefore, block 1455 of FIG. 14B
is the same as block 1405 in FIG. 14A,
Since only block 1460 is different, only the different operations will be described.

The contents of the forward pointer 1616 of the queue block 1610 indicated by the contents of the pointer 1642 of the table 1640 indicated by toptbl 652 are transferred to the forward pointer 1606 of the queue block 1600 indicated by the contents of the backward pointer 1618.
(or the forward pointer 462 of the shared resource occupancy queue queue header 460) and the backward pointer 1618 of the queue block 1610.
The contents of the backward pointer 16 of the queue block 1620 are indicated by the contents of the forward pointer 1616.
28 (or backward pointer 464 of cue header 460).

The operations of each instruction shown in Fig. 6 have been explained above, but as is clear from these explanations, the queue pointer is separated from the task management table TCB and made independent as a queue block QB, and the queue block QB is not required. By preparing only the minimum number of cases and creating a table structure in which the task management table TCB and the queue block QB are associated with each other as necessary to form a queue for the table TCB, wasted memory capacity in the pointer area can be reduced. I can do it. For example, the total number of tasks
The management table
The total capacity of the TCB pointer and queue block is 2304 bytes (=4 bytes x 5 x 64 + 4 bytes x 256), of which the area that is effectively used is 768 (=4 bytes x 5 x 32 + 4 bytes x
32). In other words, whereas previously 4096 bytes (=4 bytes x 4 x 256) were required for queue management, this can be reduced to 2304 bytes, and the utilization of those areas has been improved. can.

Next, GTEQT, FREQT, shown in Figure 6,
By providing commands such as INQLT, INQLS, RMVQT, and RMVQS, users can use the task management table in the same way as before, without having to be aware of the structure of queue blocks or the connections between queue blocks.
Task queue control can be performed simply by being aware of the start address of the TCB, and the correspondence between the task management table TCB and the queue block QB is realized by a microprogram.
The overhead associated with them can be negligible.

As explained above, according to the present invention, the pointers necessary for the queue are separated from the general table to form an independent control table, and the number of cases of the control table is prepared to the minimum necessary. Since the table structure is such that a queue is formed by associating the control table with a general table according to the data, it is possible to reduce the increase in control table capacity and waste area due to queue pointers. In addition, the user can operate the queue using the same interface as before by simply issuing the queue operation command according to the present invention without being aware of the table structure as described above. The overhead associated with association can also be reduced to a negligible level.

[Brief explanation of drawings]

FIG. 1 is a structural diagram of a control table related to a conventional queue, FIG. 2 is an explanatory diagram showing a conventional queue management state, and FIG. 3 is a schematic block diagram of a queue control system showing an embodiment of the present invention. FIG. 4 is a structural diagram of a control table showing an embodiment of the present invention, FIG. 5 is an explanatory diagram of a queue formation method showing an embodiment of the present invention, and FIG. 6 is a queue diagram showing an embodiment of the present invention. The explanatory diagrams of the operation commands, FIGS. 7, 9, 11, and 14 are all flowcharts of the control command processing procedure shown in FIG. 6, and FIGS. 8, 10, 12, 13, FIG. 15, and FIG. 16 are all explanatory diagrams of data manipulation accompanying the control command shown in FIG. 6. 400, 420, 430, 550, 560, 5
70,580,590,830,1030,12
20, 1230, 1320, 1330, 153
0,1540,1550,1630,1640,
1650: Task management table (TCB), 14
0,440: Start address pointer, 150,
155, 450, 455: Queue header for execution queue, 160, 170, 460, 470: Queue header for shared resource occupation queue, 480:
Free management queue header, 490,495,50
9,510,520,530,540,810,
820, 1010, 1020, 1200, 121
0,1300,1310,1500,1510,
1520, 1600, 1610, 1620: queue block, 370: processing unit, 300: main memory, 330: memory address register, 33
5: Memory data register, 340: Arithmetic circuit, 350: Control circuit, 360: Control memory, 7
00,900,1100,1150,1400,
1450: Microprogram for queue operation.

Claims (1)

[Scope of Claims] 1. In a computer system consisting of a main memory, a central processing unit, and a peripheral device, a first control system that controls a pointer necessary for a queue for occupying a task or a shared resource and that includes information for managing the state of the task. Separate from the table, configure a second control table consisting only of the pointers, set the start address of the first control table on the second control table, register it in the queue, and then process When the process is completed, the settings on the second control table are canceled and the queue is separated from the queue. 2. The queue control method according to claim 1, wherein registration or separation of the queue is performed using only an instruction specifying a first control table.