JPS5930304B2 - Deadlock detection circuit - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a circuit for detecting system deadlock that occurs in a system that includes a plurality of exclusively used resources and processes a plurality of processes in parallel.

In the above system, assume that process A is being processed using resource R, while process B is being processed using resource s.

If process A now needs more resource s, it cannot proceed because resource s is being used by process B, and process B will have to wait until resource s is released. . In this state, if process B reaches a state where it requires resource R in addition to resource s, it is clear that both processes cannot proceed any further. This state of the system is called a deadlock. When such a deadlock occurs in a system, not only will the process that caused the deadlock become unable to proceed, but if left unchecked, the resources allocated to that process will remain unused. , which reduces the processing efficiency of the system.

For example, in a computer system that performs multiprogramming, various peripheral devices correspond to the above resources, but it is extremely uneconomical that some of these peripheral devices remain unused due to deadlock. Therefore, detection of deadlock conditions is very important.

Detection of deadlock conditions is the job of the operating system (OS) in computer systems, and thus has traditionally been performed by software.

However, the problem with software is that the processing occupies the CPU (central processing unit) and main memory, resulting in a reduction in system throughput.

The present invention aims to solve these conventional problems by means of new hardware.

That is, according to the present invention, 05 only needs to input the current system status to the circuit of the present invention, and the circuit automatically determines whether a deadlock condition exists.

Moreover, according to the present invention, since the above-described determination is performed by a simple combinational circuit, the time required for the determination is extremely short. Next, the present invention will be explained in detail with reference to illustrated embodiments.

In the figure, resource allocation registers 101, 102,
..., 105 stores the status of resources allocated to processes. Each register corresponds to one processor, and each bit of the register corresponds to a resource. Therefore, the number of registers and the length (number of bits) of each register are set to cover the maximum number of processes processed by the system and the maximum number of resources used. In this embodiment, the resources allocated to the processes are such that the corresponding bits of the corresponding registers are set to 1. The same applies to the resource request registers 201, 202, . . . , 205.

In other words, the bit corresponding to the resource in the register corresponding to the requesting process becomes 1. The resource bus 50 has a number of signal lines corresponding to each bit of the resource allocation register, and the signal lines that pass from the resource allocation register through the AND gates of the resource release circuits 11, 12, . . . , 15 are wired 0R. It is connected.

If all the AND gates of the resource release circuit are now open, a state appears on the signal line of the resource bus 50 in which the resource is occupied by a process. Therefore, if the value is 0, it means that the resource has not been allocated to any process. Deadlock free detection circuits 21, 22, . . . 25
is the resource bus 50 and resource request register 20
This is a logic circuit that compares signals 1, 202, .

For example, if the resource bus is (0, 0, 1, 1, 0), that is, the rest is free except for the third and fourth resources, then if the contents of the resource request register are (1, 0
, 0, 0, 1), that is, the output of the deadlock free detection circuit is 0 for the processes requesting the first and fifth resources.

On the other hand, if the contents of the resource request register are (1, 0, 1
, 0, 1), the third resource request overflows the state of the resource bus, so the output is 1.
It is. The deadlock free detection circuit detects when a resource is requested (the bit corresponding to the resource in the resource request register is 1) even though the resource bus status is 1 (allocated to another process).
If there is one, the output of the deadlock free circuit of the process is 1, so as shown in the figure, the AND gate and 0
This is realized with an R gate. The 0R gates 31 to 35 input the operation control signal T of this circuit and the outputs d1 to Dn of the deadlock detection circuit, respectively. For example, the 0R gate 31 becomes 0 when both T and d1 are O.
is output, and all gates in the resource release circuit 11 are closed.

Next, let's explain the operation of this circuit.

First, necessary information is loaded into each register by OS or the like. At this time, resource release circuits 11, 12, ..., 1
All of the 5 AND gates are opened by a signal T that controls the operation of the circuit. That is, during the load period, T=1, and the AND gates of the resource release circuit are all opened by the 0R gates 31, 32, . . . .

When the code is finished, T=0 and the deadlock determination operation is started. In order to understand the operation of this embodiment, however, it is necessary to pay attention to the values of D, d2, .

A process whose d is O means that the resource it is currently requesting is not allocated to another process. This means that these processes are not in deadlock. It is also clear that a process requesting only the resources allocated to a process that is not deadlocked is also not deadlocked.

d of this process is 1 at the moment T=0, but
When T=0, the resources of the process that is outputting d=0 are released on the circuit at d=0. That is, T=0
If the process that was d=1 at T=1 is also requesting the released resource, d also becomes 0 at T=0. This operation starts from the moment T=0. If Dl, d2, . . . , Dn all become O, there is no deadlock in the system.

This appears at the output of 0R gate 40. If anything remains as 1, there is a deadlocked process in the system, and that process is the one with d=1.

As is clear from the above description, all circuits other than the digitals indicating the system status are combinational circuits.

Therefore, speeding up the circuit operation is extremely easy. Furthermore, in the illustrated embodiment, the signals Dl, d2,..., Dn and TO
) Although the resource release circuit is controlled by 0R logic, there is also a method of omitting the resource release circuit. For example, instead of the 0R gate, a NAND gate may be configured to reset all bits of the corresponding resource allocation register to 0 using a special signal. Furthermore, in the above embodiment, the deadlock free detection circuit and the resource release circuit are all provided in each register, but the resource bus 50 and Dl
, d2, . . . , Dn, the above circuit can be switched and shared among processes, and the number of gates in the circuit can be reduced. Here, the procedure for using this circuit is summarized as follows.

First, the operation control signal T is set to 1, and the 0R gates 31 and 32
, . . 35 are open, the system's resource allocation status is set in the resource allocation register, and the resource request status of each process is set in the resource request register. Next, when T is set to 0, all the 0R gates 31, 32, . . . , 35 are opened and the detection operation of this circuit is stopped. The detection results are output to Dl, d2, . . . , Dn. Therefore, when process i is deadlocked, 1 is output to Di, and when it is not deadlocked, 0 is output. As is clear from this explanation, the interface circuit when this circuit is incorporated into a computer does not need to be complicated.

Basically, the following functions are required. a) Loading state data into resource allocation registers and resource request registers.

b) Supply of operation control signal T.

c) Reading of detection results.

It is known that prediction of deadlock can be performed using the same procedure as detection of deadlock.

Therefore, if the maximum required resources of each process are known in advance, the circuit of the present invention can determine whether there is a risk of deadlock occurring for a given resource allocation state of the system. In the illustrated embodiment, an AND gate and an OR gate are used in the combinational circuit, but it goes without saying that other gates can be used as well.

[Brief explanation of the drawing]

The figure is a circuit diagram of an embodiment of the present invention, with 101, 102, .
. . , 105 are resource allocation registers that store the resource allocation status; 201, 202, . . . , 205 are resource request registers that store the resource request status;
11, 12, . . . , 15 are resource release circuits that generate signals equivalent to releasing allocated resources;
Reference numerals 21, 22, . . . , 25 are deadlock-free detection circuits for detecting that the device is not in a deadlock state.

Claims (1)

[Claims] 1 A plurality of resource allocation registers that store resource allocation states to processes, a plurality of resource request registers that store resource request states from processes, and input signals from the resource allocation registers and the resource release circuit described below. a deadlock-free detection circuit for detecting that the process is not in a deadlock state;
A resource release circuit generates a signal equivalent to releasing the resources allocated to the process corresponding to the output of the deadlock free detection circuit, and the output of the deadlock detection circuit is sent to the corresponding resource release circuit. A deadlock detection circuit characterized by being connected so as to provide feedback.