JPH0443303B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a method for detecting deadlock occurring in a complex data processing system that uses shared data.

(a) Industrial application field Data that is used by multiple jobs and has the same purpose is treated as one file, and even files used by multiple systems can be shared because system resources can be used effectively. , the use of shared data has been applied to complex data processor systems.

(b) Prior Art Even in a single data processing device system, when data is shared, a declaration is made that the data to be used is occupied, and a specific job or task uses the data exclusively for a certain period of time. However, due to this occupation, a deadlock phenomenon occurs, which hinders the operation of the data processing device system. In particular, in a complex system consisting of a plurality of data processing devices, the transaction waiting time is affected by a complicated network structure in which the plurality of systems are intertwined, as shown in FIG.

(c) Problems to be Solved by the Invention By thoroughly searching this network structure, it is possible to detect routes that become loops, that is, deadlocks. However, when searching all routes, a data processing device is used for the processing, and there is a problem in that overhead of the data processing device is generated.

The present invention proposes a deadlock detection method that eliminates the above-mentioned problems and can efficiently detect deadlocks.

(d) Means for solving the problem This proposal provides a control table in the data management section of each data processing device in a complex data processing device system that uses shared data, and a control table that stores data in a waiting state in the control table. Enter the transaction name, the time it entered the waiting state, the requesting system name, and the count value of the deadlock detection counter.
detecting the deadlock of the transaction by selecting consecutive transactions in sequence from the transaction with the oldest time in the control table, and creating a route by assigning the same count value as the count value to the selected transactions; When the root again selects a transaction having the same count value, the root is recognized as a deadlock consisting of closed root transactions.

(e) Effect In other words, transactions in the waiting state are managed by the waiting occurrence factor and the occurrence time, and a route is searched in the waiting order of each transaction starting from the transaction at the old time, and a closed route is detected. This transaction is recognized as a deadlock.

(f) Examples Hereinafter, the gist of the present invention will be specifically explained with reference to the drawings.

FIG. 1 is a block diagram of an embodiment of the deadlock detection method according to the present invention, and FIG. 3 is a flowchart of the present invention.

Data processing devices 1, 2, and 3 commonly use a shared file 4 that stores shared data. Data management units 11, 2 of each data processing device 1, 2, 3
1 and 31 respectively control tables 12, 22, and 3.
2 will be provided. As shown in the figure, the control tables 12, 22, and 32 are provided with columns such as transaction, wait occurrence time, cause, and count. In the waiting network shown in FIG. 4, for example, in the table processing device 1, transaction A1 is transferred to data B.
For example, an occupancy declaration was made at time 8,00, but since data B is already occupied by transaction A2, it is in a waiting state as shown in the figure, and at this time, deadlock detection is executed. This is an opportunity to start.

This state is recorded in the control table 12. That is, the transaction name is recorded as A1, the cause column as B, and the occurrence time as 8,00, etc. Of course, this recording is performed by the data management section 11 that manages the data. The other data processing devices 2 and 3 also perform the same operation. Note that each data processing device 1, 2, and 3 reports its own waiting state to other devices.

The deadlock detection method will be explained using the flowchart of FIG.

Hereinafter, the data processing device 1 will be explained.

First, the state before transaction A1 performs deadlock detection will be described.

For example, in the past, deadlock detection was started from transaction A2, deadlock detection processing was performed along the route of transactions A2-A3...An-A1, and when transaction A1 was reached, transaction A1 was not in a waiting state and was normal. If it is in operation, "in operation" in Fig. 3, which will be described later.
Therefore, it is determined that this route is not a deadlock, and the deadlock detection ends.

However, transaction A2-A3...An
is in a waiting state until the resources occupied by transaction A1 are released.

Here, if the value of the deadlock detection counter indicating the number of times deadlock detection has been performed in the past in transaction A2 is, for example, "9", transaction A2-A
3...The count values of the deadlock detection counter of An-A1 are all "9".

In this state, it becomes necessary to use data B during the operation of transaction A1, and when the occupancy of data B is declared, if data B is occupied by another transaction, it enters a waiting state.

Since transaction A1 has entered the waiting state, deadlock detection processing is immediately started.

First, the data management unit 11 increases the past count value "9" of the deadlock detection counter in the count column of the control table 12 by +1 count to "10", and sets the count value of the sequential counter indicating the order of the route string to "10". 0'' and starts deadlock detection.

This state is state (1) in the flowchart of FIG.

Next, the data management unit 11 continues deadlock detection using the above state as an initial condition.

This state is "continuation" in FIG. 32.

Next, the data management unit 11 starts route detection from transaction A1, and the control table 12
In , +1 is added to the count value of the sequential counter indicating that transaction A1 is the first in the route detection order, and the count field is set to 10-1.
shall be.

This state is the state of the control table 12 in FIG. 1, and also in FIG. 3.

Since the data processing devices each know the status of other devices, the data management unit 11 determines the cause of transaction A1 entering the wait state, that is, the oldest wait occurrence among the transactions occupying data B. The timed transaction is recognized as A2 and is selected.

This state is shown in FIG. 34.

Next, the status of transaction A2 in FIG. 3 is determined.

If transaction A2 is "running", transaction A is not deadlocked.
1 can wait for data B to be released.

If transaction A2 is in the "waiting state", it is determined whether the data B is data unique to another system, and if it is data unique to another system, the other system is notified of the exclusive use of that data. Request a condition inspection.

If it is not another system, return to FIG. 3 and perform a deadlock determination.

That is, in the control table 12, when the count column of transaction A2 (not shown) is compared with the count column of transaction A1, the count value of the deadlock detection counter of transaction A2 is the past "9", and transaction A1 is The count value of is “10”.

Therefore, in the deadlock determination shown in FIG. 3, since the count value of transaction A2 is not "large", that is, the count value of transaction A2 is neither "11" or more, nor is it "equal", that is, the count value is not "10", the deadlock detection is "continued".
do.

Next, as shown in Figure 3, transaction A
Rewrite the deadlock detection counter in step 2 to “10”, the same count value as transaction A1, and add +1 to the count value of the sequential counter to 10.
-2.

In this state, A1 is 10-1 and A2 is 10-1 in Figure 4.
-2.

Furthermore, the next transaction A3 is selected and the third
Repeat the steps in Figures 4, 5, 2, and 3.

This iterative process is shown in the transaction in Figure 4.
Counts of An are carried out up to 10-n, each time Figure 3 2
A deadlock determination is made as described above.

Finally, if the cause of transaction An's waiting state is transaction A1, the count columns of both transactions are 10-n and 10-1,
The count values of the deadlock detection counters are both "10".

Therefore, as shown in FIG. 3, a closed loop has been completed for this route, and it is determined that the route is deadlocked.

Here, as shown in Figure 4, transaction A1
~ During the deadlock detection process in the route of An,
If another transaction B1 enters the waiting state in the middle of the deadlock detection device on the route of other transactions A1 to An, and a new deadlock detection is started from transaction B1, the above-mentioned 3 Figures 1-5
processing is performed.

Therefore, the count column of transaction B1 is
11-1 is written.

If the cause of transaction B1's waiting state is transaction A1, transaction
_A1 is selected, and 11-2 is rewritten in the count column of A1.

As a result, when transaction An selects transaction A1, the counter column of An is 10.
-n, but the count column of A1 has changed to 11-2, and in the deadlock judgment in Figure 3 2, transaction A1 is
The count value of the deadlock detection counter is "large" and it is determined that there is no deadlock,
The detection process is aborted.

However, a new deadlock detection starts with the count value "11" of the deadlock counter, and the fourth deadlock detection starts.
As shown in the figure, the count values in the count fields 11-(n+1) and 11-2 between transaction An and transaction A1 become equal, and this route forms a closed loop and is a deadlock. is detected.

The above explanation has been made regarding the table processing device 1, but the same applies to the data processing devices 2 and 3 as well.

(g) Effects of the Invention As explained above, in the present invention, routes are systematically detected starting from the transaction with the oldest waiting time, and a closed route is detected as a deadlock, which is an efficient detection method and improves data processing. This has the advantage of shortening the deadlock detection time of the device.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of an embodiment of the deadlock detection method according to the present invention, FIG. 2 is a schematic diagram showing a transaction waiting state, FIG. 3 is a flowchart of the present invention, and FIG. 4 explains the present invention. A schematic diagram illustrating the transaction state for each is shown. In the figure, 1, 2 and 3 are data processing devices, 4
11, 21, and 31 are data management units, and 12, 22, and 32 are control tables, respectively.

Claims (1)

[Claims] 1. In a composite data processing device system that uses shared data, a control table is provided in the data management unit of each data processing device, and the name of the transaction in the waiting state, the time when the transaction entered the waiting state, and the requesting system name are stored in the control table. and the count value of the deadlock detection counter, and for deadlock detection of the transaction, successive transactions are selected in order from the transaction with the oldest time in the control table, and the same count value as the count value is selected. A route is created by attaching the transaction to the transaction, and when the route selects a transaction having the same count value again, the route is recognized as a deadlock consisting of transactions with a closed route. How to detect deadlock.