JPS6048795B2 - deadlock detector - Google Patents

Description

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

Assume that in the above system, process A is being processed using resource R, while process B is being processed using resource S.

Now, if process A is in a state where it needs more resource S, this resource s is in use by process B, so process A can proceed with its processing until process B releases resource S. This will stop the process and wait. In this state, if process B becomes in a state where it needs resource R in addition to resource s, since resource R is held by process A, it is clear that neither process can 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 not be able to proceed, but the resources held by those processes will remain unused, reducing the processing efficiency of the system. I'll let you.

For example, in a computer system that performs multiprogramming or multiprocessing, various peripheral devices correspond to the above resources, but it is extremely uneconomical and uneconomical for some of these peripheral devices to remain unused due to deadlock. Therefore, early detection of deadlock 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 its processing occupies the CPU (central processing unit) and main memory, reducing system throughput (computer processing power). As one solution to this problem, a deadlock detection method using hardware has been proposed. The details are published in the Journal of the Institute of Electronics and Communication Engineers, Vol. The detection process is performed without memory and much faster than with software. However, the drawback is that the number of registers and gates is large, resulting in expensive hardware, which is a practical problem. SUMMARY OF THE INVENTION An object of the present invention is to provide a new deadlock detector which requires a significantly smaller number of registers and gates than conventional ones.

Next, the present invention will be explained in detail with reference to illustrated embodiments.

In the figure, the resource allocation register 101 is loaded with the status of whether each process is holding a resource or not using OS or the like and stored therein. The figure shows, as an example, a deadlock detector for a system with four or less processes, so the register has four bits, and each bit corresponds to each process. For example, if the first, second, and fourth processes hold some resource, the contents of the register will be (101c). Similarly, the resource request registers 201, 202, 203, and 204 correspond to each process. It is located.

201 is for the first process, and if its contents are (01
1), then the first process is requesting the resources held by the second and third processes. represents.

The reason this register is 3 bits instead of 4 bits is because it does not require its own bits. 202, 203, 204
are the resource request registers for the second, third, and fourth processes, respectively. Ru.

The resource bus 50 connects the resource allocation register 101 to the resource release circuit 11 with the number of signal lines corresponding to each bit of the resource allocation register 101.
The signal passing through the N1 gate appears.

Deadlock free detection circuits 21, 22, 23, and 24 are also arranged corresponding to each process, and are connected to a resource bus 50 and resource request registers 201, 20.
2, 203, and 204, and the resource bus 50
It is detected whether the process corresponding to the deadlock free detection circuit requests the resource held by any of the processes appearing above.

For example, when the signal on the resource bus 50 is (1011), that is, the first, second, and fourth processes are in possession of the resource, and the level of the signal T is 1, the content of the resource request register 201 of the first process As shown above (01
C. In other words, when the second and third processes are requesting the resources held by them, the signals corresponding to the second process on the resource bus 50 and the second process (first bit) of the resource request register 201 are transmitted. 1, so their N1 is 1.

However, for the third and fourth processes on the resource bus 50, the N loss with respect to the signal of the corresponding bit of the resource request register 201 is zero. The final stage of the deadlock free process detection circuit 21 is the 0 of these AND gate outputs.
Since it is configured to take R, the output of this circuit is 1 in the end.
It is. As is clear from the above explanation, the deadlock-free process detection circuit determines whether there are any resources that are requested by the process corresponding to the deadlock-free process detection circuit and which are held by other processes. Detect.

If the grip is held, the output is 1, otherwise the output is 0.
becomes. It is clear that a process whose output is o is not deadlocked. In other words, the process for which the output of the deadlock-free process detection circuit 21 is o (the first process corresponding to this change) is not in a deadlock state. The same goes for other processes, and processes whose requests are held by processes whose requests are not in a deadlock state with resources that are not in a deadlock state are also not in a deadlock state.

The resource release circuit 11 is a circuit for detecting such a process.

Now, when T=0, the control circuit 31 inputs the outputs of the deadlock free process detection circuits 21, 22, 23, and 24 as they are to the AND gates corresponding to the respective processes of the resource release circuit 11.

If this input is 0 and T=0, no output is made to the resource bus 50 even if that bit of the resource allocation register 101 is 1. In other words, the resources held by that process are the same as being released, and the processes described above (resources that are not held by any process and processes within the resources held by processes that are not in a deadlock state) are released. It is detected by the drag-free process detection circuits 21-24. T is a control signal input line for controlling the operation of the present deadlock detector.

If T=1, the zero output from the deadlock free process detection circuits 21 to 24 is blocked by the control circuit 31 and is not transmitted to the resource release circuit 11, which has the effect of stopping the operation of the deadlock detector. Therefore, T=1 is set when loading data into each register. The operation of this deadlock detector is T=1
After loading data into each register as follows, starting from the moment when T=0, output terminals of the deadlock free process detection circuits 21 to 24 output whether or not each process is in a deadlock state. .

If D, ~Dn all become 0, there is no deadlock in the system.

If some remain as 1, the system is deadlocked, and the process is one whose d terminal is 1.

For example, if the dl terminal is 1, this means that the first process is deadlocked. As is clear from the above description, all the registers other than the resource allocation register and the request register, which indicate the state of the system, are combinational circuits, so the operation is fast.

Furthermore, compared to the prior art, the number of registers and logic elements used in the circuit is greatly reduced. In other words, in the known circuit, the circuit is configured based on the allocation status and request status of each resource, so the number of registers is approximately twice as necessary, and the number of bits in each register is equal to the number of resources. Ta. Since in many systems the number of resources is significantly greater than the number of processes, the present invention also reduces the number of bits in these registers.

Let us explain the difference from the known example in more detail from the circuit configuration. The first notable difference in circuit configuration from the known example is the resource allocation register.

In the known example, registers with a bit width equal to the number of resources corresponding to each process are required, but according to the present invention, only one register with a width equal to the number of processes is sufficient. For example, as a typical example in a computer, the number of processes is 1
0 and the number of resources is 30, the total number of register bits is 101 (30×10) according to the present invention compared to the known example.
= 1130, resulting in an extremely large simplification. The second difference from the known example appears in the resource bus.

In the known example, since there are a plurality of resource allocation registers, it is necessary to connect them to the resource bus after passing through an 0R gate. According to the present invention, since there is only one register, an 0R gate is not required. Here, too, the number of logic elements has been greatly reduced, and there is no delay due to gates, making it possible to speed up the operation. As described above, the present invention provides a novel device that has a much simpler register configuration and logic circuit configuration than the known examples, and therefore requires a much smaller number of elements and operates at high speed. You can get Tsukudaytekta.

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

Therefore, the circuit of the invention can also be used to determine whether there is a risk of deadlock in the system. In the illustrated embodiment, an AND gate and an 0R gate are used in the combinational circuit, but it goes without saying that other gates such as a NAND gate can also be used.

[Brief explanation of the drawing]

The figure is a circuit diagram of an embodiment of the present invention, in which 101 is a resource allocation register that stores resource allocation status to processes, 201 to 204 are resource request registers that store resource request status of processes, and 11 is a resource allocation register that stores resource allocation status to processes. 21 to 24 are deadlock-free process detection circuits that detect that a process is not in a deadlock state; 31 is the operation of this deadlock detector; This is a control circuit for controlling.

Claims (1)

[Claims] 1 Does each process own any resource?
a resource allocation register that stores the state of resource allocation, such as whether each process is not holding the resource at all, and a resource request register that stores the state of resource request, such as which other process is requesting the resource that each process is holding; a deadlock-free process detection circuit that detects a process requesting a resource held by a process that is not in a deadlock state based on logic between the allocation register output signal and the resource request register output signal; and a resource release circuit that blocks a corresponding process bit output signal of the resource allocation register to the deadlock free process detection circuit to release the resource when there is no output signal of the deadlock free process detection circuit. A deadlock detector characterized by: