JPS5931736B2 - Queue management method - Google Patents

Description

[Detailed description of the invention] The present invention relates to queue management schemes.

In a shared memory or a shared I/O, a large number of request sources use the memory at random, so it is necessary to manage the queue by determining the order of use in response to request signals from the request sources.

Conventionally, queue management has been carried out to control competition for access to shared resources by preliminarily determining a priority order between request sources according to the processing speed 25 of the request sources.
However, such a method has a drawback in that only requestors with a high priority can make full use of the shared resource, while requestors with a low priority are often forced to wait for a long time. In particular, when the functions of each request source are almost uniform, it is desirable that shared resources can be used uniformly, that is, according to the order in which each request signal is generated. Since a fixed priority order is determined based on the original physical layout relationship, the overall efficiency of the system has decreased. The present invention provides a method for finely controlling the holding queue for randomly occurring requests other than the above-mentioned shortages, depending on the time point at which the request is generated.

The details of the present invention will be explained in detail below with reference to the drawings. FIG. 1 is a block diagram showing one embodiment of the present invention.

1 is a shared memory as a shared resource; 2, 3, and 4 are each a CPU as a request source; 5 is a memory bus; 6 to 10
is the control line.

The control line 6 is constantly transmitted with 4-bit information (GD) indicating the length of the data being carried.The control line 7 receives an end signal END every time the memory access operation of the shared memory 1 is completed.
is supplied. A use permission signal START for the shared memory 1 is supplied to the control line 8 . A control line 9 supplies a request signal REQ from each request source to the shared memory 1. The control lines 9 are wired OR connected between each request source. A control line 10 sequentially connects the shared memory 1 and each request source 2, 3, 4. When one pulse ACK is supplied from the shared memory 1 to the control line 10, this pulse is sent to the requester 2,
The information is taken into each request source in the order of 3 and 4.

As will be explained in detail later, the shared memory 1 has a 4-bit register that indicates the length of the matrix, and each request source 2, 3
, 4 have registers that store six orders for shared memory 1.

When a request signal is generated from any request source, this information is transmitted to the shared memory 1 via the control line 9. The shared memory 1 thereby supplies an ACK pulse to the control line 10. The request source 2 sends a PAL. ' When the signal is supplied, if it is the one that outputs the request signal, it takes in the information on the control line 6 into an internal register and stops outputting the request signal. If the request source 2 is not outputting a request signal, the request source 2 outputs the pulse 5 supplied to the RACK terminal as it is from the TACK terminal.
Thereafter, each of the request sources 3 and 4 also performs the same operation. Also, the shared memory 1 counts up the internal register by 1 every time an ACK pulse is generated. The shared memory 1 supplies a START signal to the control line 84 when the contents of the internal register are other than O. When the request sources 2, 3, and 4 are supplied with this START signal, if the content of the internal register is 1, they start memory access using the memory bus 5.
Shared memory 1 is set to EN every time a memory access operation is completed.
A D signal is supplied to the control line γ to cause the internal register to count down by 1. Further, each request source causes an internal register to count down by 1 each time an END signal is supplied. This operation will be explained in detail below using FIGS. 2 and 3. FIG. 2 is a diagram showing a specific configuration of the shared memory 1, and FIG. 3 is a diagram showing a specific configuration of the request sources 2, 3, and 4.

In FIG. 2, the shared memory is composed of a storage section 200 and a control circuit 201 thereof. As mentioned above, the pedestal circuit 201 has a 4-bit register 20 that accommodates the "length" LENGTH of the holding matrix.
The contents are always displayed on the control line 6. Assume now that Regis 20 is composed of an up-down counter. Also, in Figure 3, each request source is CPU3OO
and an input/output control section 301.

As described above, the input/output control unit 301 stores the 8 order of memory accesses ``0RDER'' for the shared memo 1 month.
It has a bit register 30. It is now assumed that the register 30 is composed of a down counter that can be preset. When the CPU 3OO generates the REQ signal, this signal is sent to the determination circuit 21 of the control circuit 201 via the control line 9.
supplied to

The determination circuit 21 generates an output signal regardless of the state of the memory 200 if the REQ signal is true. This output signal is supplied to the pulse generating circuit 22 and the up terminal of the register 20. Register 20 thereby counts up its contents by one. On the other hand, the pulse generation circuit 22 supplies one pulse ACK to the Fbl leg line 10. As shown in FIG. 1, this ACK pulse is sequentially supplied to request sources 2, 3, and 4. In Figure 3, this A
The CK pulse is supplied to the RACK terminal of the pulse control circuit 31. If the CPU 3OO is not generating the REQ signal when the ACK pulse is input, the pulse control circuit 31 directly outputs the ACK pulse from the TACK terminal to the control line 10. Also, when the ACK pulse is input, CPU3
When OO is generating the REQ signal, the pulse control circuit 31 generates an output signal and opens the gate 32. At this time, the pulse control circuit 31 does not output an ACK pulse via the TACK terminal. By opening gate 32, the contents of register 20 (FIG. 20) are set in register 30 (FIG. 3) via control line 6. Further, the output signal of the pulse control circuit 31 is sent to the CPU3OO, and the output signal of the pulse control circuit 31 is sent to the CPU3OO.
OO stops generating the REQ signal. In other words, LE
NGTH indicates the number of request sources that currently wish to use the shared memory, and 0RDER indicates the number of request sources that can use the shared memory.

When a REQ signal is generated from any request source, LENG
Count up the contents of TH by 1 and set this value to 0RD
By setting it as ER, it is possible to store the usage order of the request source that generated the REQ signal. In FIG. 2, the state of the storage section 200 is indicated by a state indicating circuit 23. In FIG.

The determination circuit 24 determines a memory access operation start signal ST from the status signal of the status indication circuit 23 and the contents of the register 20.
Output ART. That is, when the storage unit 200 is not in the BSY state and the contents of the register 20 are other than O, S
A TART signal is supplied to the control line 8. In Figure 3,
The determination circuit 33 receives START supplied via the control line 8.
When the content 0RDER of the register 30 is 1, the bus control circuit 34 and the CPU
An output signal is provided to 3OO to initiate an access operation to the shared memory. Referring again to FIG. 2, the state indicating circuit 23 supplies the END signal to the control line T upon completion of the memory access operation of the storage unit 200.

The END signal is also supplied to the down count terminal of the register 20, and counts down the value of LENGTH by one. On the other hand, in FIG. 3, the END signal supplied via the control line 8 is supplied to the countdown terminal of the register 30, and counts down the value of 0RDER by one.

The END signal is generated each time a memory access operation is completed. In this way, the value of 0RDER for each request source is reduced by 1 each time a request source finishes using it, and control is performed so that only request sources whose UORDER value is 1 are allowed to use the shared memory. .

Therefore, in FIG. 1, if each of the request sources 2, 3, and 4 randomly generates request signals, the shared resource 1 can be used in accordance with the order in which the request sources generate requests.

On the other hand, if, for example, requester 4 generates request signals almost simultaneously, requestor 3 can use shared resource 1 first. As described in detail above, according to the present invention, it is possible to finely control the holding queue for shared resource use requests randomly generated from a large number of requests, depending on the time point at which each request source generates a request.

Furthermore, according to the present invention, since the use of shared resources is not monopolized only to a specific request source, even if the functions of each request source are averaged, the physical arrangement of each request source, for example, It is possible to reduce the influence of priority etc. caused by such factors.

Note that the present invention is not limited to the above embodiments.
For example, the shared resource consists of shared 1/0, shared processor, etc., and the request source is not limited to the CPU.
It can also be used for equipment, etc.

[Brief explanation of drawings]

FIG. 1 is a diagram showing an embodiment of the present invention, and FIGS. 2 and 3 are specific configuration diagrams of a portion of an embodiment of the present invention. 1... Shared memo) 几 2, 3, 4...
Request source, 5...Memory bus, 6, Otsu 8, 9, 1
0... Control line.

Claims (1)

[Scope of Claims] 1. A shared resource, a plurality of request sources that randomly use the shared resource, a first register that holds the length of a queue for the resource, and a register that corresponds to each of the request sources. a second register group that is provided to store an order regarding the use of the shared resource; and the contents of the first register are incremented by generation of a request signal regarding the use of the shared resource from an arbitrary request source. a first means; a second means for setting the contents of the first register incremented by the means in a second register corresponding to a request source that has generated the request signal; a third means for generating a usage permission signal for the shared resource when the content of the register is other than a predetermined value; and a third means for generating a termination signal when the usage of the shared resource by any of the request sources is completed. and a fifth means for inverting the first register and the second register group by the end signal generated by the fourth means,
A queue management method characterized in that a request source corresponding to a register holding a predetermined value among the second register group is controlled to use the shared resource. 2. The second means includes a control line that sequentially connects the shared resource and the plurality of request sources, and a control line that is sequentially transmitted to the request sources on the control line upon generation of the request signal.
a second pulse corresponding to the request source that generated the request signal when the pulses supplied by the means reach the request source that generated the request signal;
2. The queue management method according to claim 1, wherein the contents of the first register are set in the register of the first register. 3. The shared resource includes a resource section and a control circuit for the resource section, and the first means, third means, and fourth means are provided in the control circuit. The queue management method described in item 1. 4. The queue management system according to claim 1, wherein the second register group is provided at each corresponding request source.