JPH0254363A - Deadlock control system - Google Patents

Abstract

PURPOSE:To carry out the deadlock control with no dependence on an integrated control mechanism by adding an original identifier to each process and checking these identifiers via a deadlock control mechanism to decide the propriety for acceptance of a lock request. CONSTITUTION:A module of a deadlock control mechanism I accepts a lock request at the time point T1 against the resources R2 of a process P1. While a module of a deadlock control mechanism II accepts a lock request at the time point T2 against the resources R2 of a process P2. Then T1<T2 is defined. Then the process P1 gives the lock request of the resources R1 to the mechanism I via an identifier ID1. Under such conditions, the mechanism I checks the ID1 and 'NO' is decided owing to T1<T2. Thus the request of the ID1 is rejected. While the mechanism I which is processing the deadlock request given from an identifier ID2 sends back an answer showing that the resources R1 related to the ID2 is locked by the process P2 only. Then the mechanism I finishes the process requested by the ID2.

Description

[Detailed description of the invention] [Objective of the invention] (Industrial application field) The present invention is directed to deadlock management between multiple processes executed in parallel in a system consisting of one or more computers. The present invention relates to a deadlock management method that manages deadlock detection or deadlock prevention requests from multiple processes without contradiction and without falling into a deadlock state while processing the requests.

(Prior art) Generally, in a system in which peripheral resources such as database resources, printers, and blocks are shared between multiple processes,
In many cases, some kind of deadlock prevention method is employed to manage processes so that they do not compete for resources and fall into a deadlock state.

Additionally, deadlock detection methods are often used to quickly detect when a deadlock has occurred.

In conventional systems, a management mechanism that centrally manages the system executes one of the above methods.

This is because conventional systems adopt a centralized management method centered on large computers, but in this case, if the large computer that is the host computer goes down, the system will stop, making deadlock management impossible.

Incidentally, in recent years, the decentralization of systems in various fields such as ASEA and FA has become a demand of the times, and system configurations in which a plurality of small and medium-sized computers are interconnected through a network are becoming mainstream.

One of the functions required of such a distributed system is system robustness, which means that even if some of the computers go down, the remaining computers can handle the necessary work. It means that you can.

However, even in a distributed system, if a centralized mechanism centrally manages deadlock detection and prevention measures for resources within the system, if the computer in which the centralized mechanism is installed goes down, multiple processes will be interrupted even if other computers are running. Unable to handle work.

To avoid this situation, the deadlock management mechanism that detects and prevents deadlocks is not centralized, but decentralized to each computer, and each computer uses its own resources (database). One example is a distributed deadlock management method in which deadlock management is performed only for peripheral devices, peripheral devices, etc.).

By using a distributed deadlock management method, even if some of multiple computers go down, multiple processes can continue processing work on the remaining computers while detecting and preventing deadlocks.

However, in the distributed deadlock management method, there is no centralized mechanism that can grasp the resource usage situation such as what kind of resources each of multiple processes needs and which process is currently using which resources. When using resources belonging to multiple computers, it is necessary to communicate information necessary for deadlock management between these computers.

In Figure 4, process PI and process P2 each have resource R.
1 and resource R2 to process the work of each process.

Now, process P1 and resource R1 are on computer I, and process P
2 and resource R2 belong to computer H. Assume a situation where process P1 locks resource R2 and process P2 locks resource R1.

In FIG. 4, an arrow a pointing from the resource gR2 to the process PL and an arrow a pointing from the resource R1 to the process P2 express this situation. At this time, the process P
Assume that process P1 and process P2 request locks on resource R1 and resource R2, respectively.

Process Pi requests resource R1 from deadlock management mechanism I.
When the lock request is made, the deadlock management mechanism I inquires of the deadlock management mechanism H about the situation inside the computer (2) in order to check whether the lock request of the process P1 will cause a deadlock.

The deadlock management mechanism (2) responds to the request from the deadlock management mechanism (I) by stating that the process P2 is only locking the resource R1.

Deadlock management mechanism I prevents process P from locking resource R1 because process Pi's lock request to resource R1 does not cause a deadlock.
1 is allowed to wait for the lock of capital 1XR1.

Therefore, as shown in Figure 4, from process PL to resource R
An arrow pointing to 1 is drawn. Capital of process P1? fR1
At approximately the same time as the lock request to the resource R2, the process P2 also requests the deadlock management mechanism ■ to lock the resource R2.

The deadlock management mechanism (2) asks the deadlock management mechanism (I) about the status of the computer I in order to check whether the lock request of the process P2 will cause a deadlock.

At this stage, we have not accepted the lock request for the resources Fi and R1 of the process pt of the deadlock management mechanism I, so
The deadlock management mechanism I replies to the deadlock management mechanism ■ that the process Pl has locked the resource R2.

Therefore, the deadlock management mechanism (2) allows the process P2 to wait for the lock on the resource R2, so that an arrow b' is drawn from the process P2 to the resource R2.

At this stage, the deadlock management mechanism I and the deadlock management mechanism II only permit lock waiting for the lock requests of the process Pl and the process P2, and determine that there is no deadlock.

(Problem to be Solved by the Invention) However, as shown in Figure 4, there is a closed arrow path between process Lumi, resource R1, process P2, and resource R2, so the system is actually deadlocked. I'm depressed.

As in the example described here, the reason why the deadlock management mechanism was unable to detect the occurrence of a deadlock even though it actually occurred is due to the deadlock management mechanism 1. II is two computers 1. Check for deadlock across II (
This is because monitoring for prevention or detection was not carried out correctly.

In other words, ``While the deadlock management mechanism I is checking for deadlocks regarding process Pi's lock request to resource R1, deadlock checks by other processes related to resource R1 should not be allowed. This is due to the fact that the management mechanism I and the deadlock management mechanism (2) independently executed deadlock checks without considering the occurrence of lock requests from other processes.

The present invention was made under these circumstances, and aims to provide a deadlock management method that can correctly execute deadlock management without relying on a centralized management mechanism.

[Structure of the Invention] (Means for Solving the Problems) The deadlock management method of the present invention is a computer system in which each of a plurality of processes executes work while each process shares or exclusively holds one or more resources. Within the system, a process that issues either deadlock detection or deadlock prevention +L request to the deadlock management mechanism attaches a unique process identifier within the system to the request issued to the deadlock management mechanism.

(Operation) In the deadlock management method of the present invention, a process identifier is assigned to each process, and a deadlock management mechanism distributed among multiple computers checks the identifier, thereby handling lock requests for each process. Since the receiver determines whether or not to attach, deadlock management can be performed correctly without relying on a central management mechanism.

(Example) Hereinafter, details of an example of the deadlock management system of the present invention will be described based on the drawings.

First, as shown in FIG. 1, the computer engineer is provided with a deadlock management mechanism I, to which a process P1 and a resource R1 belong.

In addition, the computer ■ is equipped with a deadlock management mechanism ■.
Process P2 and resource R2 belong to it.

FIG. 2 is a diagram showing the configuration of the deadlock management mechanisms I and H.

The deadlock management mechanism performs a comparison check between module A, which accepts resource holding requests from processes in its own computer, and the unique identifier of this process in the system, and the identifiers of this process and the identifiers of other processes. module B, which generates a resource queuing graph, and module C, which detects deadlock and predicts the occurrence of deadlock.

FIG. 3 is a diagram showing details of the processing in module A.

First, module A of deadlock management mechanism I sets the time T
l, the time when module A of deadlock management mechanism H accepted the lock request for resource R2 of process P2 is T.
Set it to 2.

Now, assume that T1 times T2, that is, process P1 requests a lock earlier than process P2.

Each deadlock management mechanism 1. Module A of II receives an identifier (ID) from the process at the same time as the lock request.

The identifier is a time value and a computer number (referred to as a site number).
and is the only one in the system.

In FIG. 1, process P1 with identifier IDI created from time value TI and site number 31 locks resource R2, and process P2 with identifier ID2 created from time value T2 and site number S2 locks resource R1. It's locked.

At this time, assume that process P2 in computer (2) issues a lock request to resource R2 to deadlock management mechanism (2) with ID2 attached.

Since the deadlock management mechanism ■ is not currently performing a deadlock check, it stores the lock request for resource iR2 of process P2 as ID2, and since resource R2 has already been locked by process P1, the request for ID2 is dead. Starts a check to determine whether the lock will occur.

Deadlock management mechanism (2) displays that it is processing the request with ID2, and also informs deadlock management mechanism I of computer I that it is requesting process P2 or resource R2 with identifier ID2.

Since deadlock management mechanism I is not currently executing a deadlock check, this ID indicates that the deadlock check request from deadlock management mechanism I is being processed.
2 flag is displayed and a deadlock check is performed.

During this check, process P1 issues a lock request to resource R1 using the deadlock management mechanism
Suppose we go to .

The deadlock management mechanism I checks the identifier according to the routine shown in FIG. 3, but since the time value T2 of the ID2 being processed is greater than the time value Tl of the request IDI, it returns NO in step b in the figure. and the IDI request is rejected.

On the other hand, the deadlock management mechanism I, which is processing the deadlock check request from ID2, checks the resource R related to ID2.
1 replies that it is locked only to process P2,
Deadlock management mechanism I ends the request processing of ID2.

The deadlock management mechanism (2), which received the response from the deadlock management mechanism I, allows the process P2 to wait for the lock on the resource R2, since the lock request of the process P2 to the resource R2 will not cause a deadlock. In the graph display of resource waiting, arrow i points from process P2 to resource R2.
is drawn.

On the other hand, the process pt, whose request to lock resource R1 was rejected using the IDI identifier, locks the resource R1 at the current time T3 (T3 > T2
>Tl) to create a new identifier ID3 and enter the ID again.
3, a lock request for resource R3 is made to the deadlock management mechanism I.

If the deadlock management mechanism I is still processing the request for ID2, it queues the request for ID3 according to step C in FIG. Start checking.

The deadlock management mechanism I is connected to the deadlock management mechanism H.
It transmits the request of D3 and receives from the deadlock management mechanism ■ that the resource R2 is locked by the process PI and that the process P2 is waiting to lock the resource R1.

The deadlock management mechanism I uses this received content and the process pt
It is detected that a deadlock has occurred due to this lock request.

In the resource waiting display, arrow j is drawn, indicating that a closed path is formed between process Pl, resource R1, process P2, and resource R2, and a deadlock state exists.

In this way, according to this embodiment, it is possible to distribute and execute deadlock management while maintaining the validity of the contents of various resources that belong to a system that is distributed among a plurality of computers. Even if one computer goes down, resources belonging to other computers can be managed without contradiction.

[Effects of the Invention] As explained above, in the deadlock management method of the present invention, a unique identifier is assigned to each process, and deadlock management mechanisms distributed across multiple computers check the identifier. , since it determines whether a lock request from each process can be granted or not, deadlock management can be performed correctly without relying on a central management mechanism.

[Brief explanation of the drawing]

Figure 1 shows the overall configuration of an embodiment of a system to which the present invention is applied, Figure 2 shows the configuration of a deadlock management mechanism in the system, and Figure 3 shows the flow of processing in the system. 4 are diagrams showing an example of the configuration of a conventional distributed processing system. B1 C...Module, Pl, B2...Process,...Resource.

Claims (1)

[Claims] (1) In a computer system where each process executes its work while sharing or exclusively holding one or more resources, a deadlock management mechanism is required to perform either deadlock detection or deadlock prevention. A deadlock management method characterized in that a process issuing a request attaches a process identifier that is unique within the system to a request issued to the deadlock management mechanism.