CN121187812A - A method and system for predicting and dynamically intervening in mutex deadlock risk - Google Patents

Abstract

The invention discloses a method and a system for predicting the deadlock risk of a mutex and dynamically intervening, which relate to the technical field of deadlock risk intervening, and the method comprises the steps that a task T requests the mutex M; if the mutex M is occupied, updating the task T to be a waiter, otherwise, granting a lock to update holder=T and starting timing, adding the edge T to M, detecting whether the added edge forms a loop or not through an increment loop judging module, calculating a deadlock risk value through a risk evaluation module, and until the lock is granted safely. The system comprises a prediction deadlock protection module, wherein the prediction deadlock protection module comprises a mutex registry, a waiting diagram construction module, an increment ring judgment module, a risk scoring module and an execution intervention module, input data sequentially carry out mutex registry recording, waiting diagram construction module processing, increment ring judgment module detection and risk scoring module evaluation, and finally the execution intervention module completes intervention. The method can predict the potential deadlock in real time and actively prevent the deadlock from happening according to the intervention measures.

Description

Method and system for mutex deadlock risk prediction and dynamic intervention

Technical Field

The invention relates to the technical field of deadlock risk intervention, in particular to a method and a system for predicting and dynamically intervening mutex deadlock risk.

Background

Deadlock refers to a state in which two or more threads cannot continue to execute due to competing for resources or waiting for each other to release resources during execution. Mutex (Mutex) is a common way of inter-thread synchronization to protect shared resources from data contention. Improper use of the mutex can easily result in deadlock. If multiple tasks cross hold different mutexes and wait for locks held by each other, mutual waiting may be formed, resulting in deadlock. In a real-time operating system, deadlock can be avoided generally by fixing the acquisition sequence of locks, adding a lock acquisition timeout mechanism, priority inheritance and the like.

In the prior art, measures can only be taken when deadlock is about to occur or after deadlock occurs, but a system layer and kernel layer active prediction and deadlock prevention mechanism is lacked:

1. The method has the advantages that the acquisition sequence of the lock is fixed, namely, all tasks are required to apply a plurality of mutexes in a unified sequence, so that loop formation is avoided, but the method has the defects that depending on the design of an application program, the system cannot be forcedly executed, and deadlock is easy to occur due to negligence;

2. The lock acquisition timeout mechanism is added, namely, a task gives up a request after waiting for lock timeout, but the method has the defects that the request can only be processed when the deadlock is formed and the deadlock can not be actively prevented before the lock is granted;

3. Priority inheritance, namely temporarily improving the priority of a task holder with low priority and solving the deadlock caused by priority overturn, but has the defects that the cyclic waiting type deadlock cannot be blocked, and the situation that a plurality of tasks wait for each other still can occur.

Therefore, there is a need to design a method for performing a mutex deadlock risk prediction and dynamic intervention in a real-time operating system, which can solve the existing problems.

Disclosure of Invention

The invention aims to provide a method and a system for predicting and dynamically intervening the risk of a mutex deadlock, which can discover the risk of the potential deadlock before a lock is granted and actively prevent the occurrence of the deadlock from the source through real-time intervening measures (such as delay grant, priority adjustment, lock sequence optimization and the like).

In order to achieve the above purpose, the invention provides a method and a system for predicting the risk of deadlock and dynamically intervening of a mutex, which adopts the following technical scheme:

A method of mutex deadlock risk prediction and dynamic intervention, comprising the steps of:

step 1, requesting a mutex M by a task T;

step 2, if the mutex M is occupied, updating a task T by a mutex registry to be a waiter, otherwise, granting a lock to update holder=T, and starting timing;

Step 3, newly adding an edge T-owner (M) in the WFG through a waiting diagram construction module;

step 4, detecting whether the newly added edge forms a loop or not through an increment loop judging module;

step5, calculating a deadlock risk value through a risk assessment module;

and 6, repeating the steps 1-5 until the lock security is granted.

Based on the above technical scheme, in step 3, the operation process of adding the edge is as follows:

a. firstly, confirming whether the mutex M has a holder or not, if the mutex M has no holder, no dependence is required to be established;

b. If the task O of the holder exists, recording the waiting task as O in the state information of the task T;

c. Task O is added to the waiting list of task T and the waiting number count value is updated.

Based on the above technical solution, the detection process in step 4 further includes, when the task T requests the mutex M, if the lock is held by the task O, adding an edge t→o in the WFG, starting from O, searching forward along the existing dependent edge in the WFG, where the search path represents a "waiting chain" between tasks, i.e. task O waits for P, task P waits for Q, and so on, and expanding in sequence, if the task T reaches a closed loop in the search process, indicating that the added edge forms a loop, otherwise, safety is achieved.

Based on the technical scheme, in step 5, if the deadlock risk value is not more than the threshold value, the system normally grants the mutex and updates the information of the registry holder, and if the deadlock risk value is not less than the threshold value, the policy intervention module takes or triggers corresponding intervention measures according to the configuration, wherein the value range of the threshold value is 0-1.

Based on the technical scheme, the threshold value is further in the range of 0.4-0.7.

Based on the technical scheme, the deadlock risk value is related to local loop information, mutex lock holding time and task priority difference, and the formula is as follows:

;

wherein L represents the number of tasks in the ring; representing the ratio of the average holding time of the mutex to the maximum value of the system; Representing the priority differences of the dependent edges in the ring; a weight representing the number of tasks in the ring; the weight after the sum of the average holding time of the mutex and the maximum value ratio of the system is represented; Weight representing priority differences and risk score representing a deadlock risk value.

Based on the technical scheme, the judgment index of the lock security grant is ① that the waiting diagram has no loop, and the ② deadlock risk value is lower than the threshold.

A system for predicting and dynamically intervening mutex deadlock risk comprises a prediction deadlock protection module, wherein the prediction deadlock protection module is used for executing a method for predicting and dynamically intervening mutex deadlock risk, the prediction deadlock protection module comprises a mutex registry, a waiting diagram construction module, an increment judgment ring module, a risk scoring module and an execution intervention module, wherein input data are sequentially subjected to mutex registry recording, waiting diagram construction module processing, increment judgment ring module detection and risk scoring module evaluation, and finally the execution intervention module is used for completing intervention.

Based on the technical scheme, the mutex registry is further used for maintaining state information of all mutexes M in the system, the waiting diagram construction module is used for maintaining a dependency diagram among tasks according to the dependency relationship between the tasks T and the mutexes M, the increment loop judgment module is used for detecting whether newly added dependencies form loops, the risk scoring module is used for calculating deadlock risk values according to factors such as local loop information, locking time and task priority, and the execution intervention module is used for taking measures to block potential deadlock risks when the risk values exceed a preset threshold.

Based on the above technical solution, further, the operation of removing edges is performed in the processing procedure of the waiting chart construction module, and the operation procedure is as follows:

A. when the task T successfully acquires the lock or exits from the waiting state, the system can clear the dependency relationship with the task O;

B. Setting the waiting state of the task T as a non-waiting state, and simultaneously finding out the record of the task O in a waiting list and deleting the record;

C. the deleted mode is to cover the deleted position with the last waiting element and reduce the number count value to keep the data structure compact.

Compared with the prior art, the invention has the following beneficial effects:

According to the invention, through maintaining a mutex registry and a task waiting chart in a kernel layer of a real-time operating system, combining an increment judgment ring and a risk scoring model based on ring length, locking time and task priority difference, a potential deadlock is predicted in real time, and intervention measures such as delay grant, priority lifting or locking sequence adjustment are dynamically adopted according to a risk value, so that the deadlock is actively prevented.

Drawings

FIG. 1 is a flow chart of the method of the present invention.

Detailed Description

The following description of the embodiments of the present invention will be made clearly and fully with reference to the accompanying drawings, in which it is evident that the embodiments described are only some, but not all embodiments of the invention. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

It should be noted that, if directional indications (such as up, down, left, right, front, and rear are referred to in the embodiments of the present invention), the directional indications are merely used to explain the relative positional relationship, movement conditions, and the like between the components in a specific posture, and if the specific posture is changed, the directional indications are correspondingly changed.

In addition, if there is a description of "first", "second", etc. in the embodiments of the present invention, the description of "first", "second", etc. is for descriptive purposes only and is not to be construed as indicating or implying a relative importance or implicitly indicating the number of technical features indicated. Thus, a feature defining "a first" or "a second" may explicitly or implicitly include at least one such feature. In addition, if "and/or" and/or "are used throughout, the meaning includes three parallel schemes, for example," a and/or B "including a scheme, or B scheme, or a scheme where a and B are satisfied simultaneously. In addition, the technical solutions of the embodiments may be combined with each other, but it is necessary to base that the technical solutions can be realized by those skilled in the art, and when the technical solutions are contradictory or cannot be realized, the combination of the technical solutions should be considered to be absent and not within the scope of protection claimed in the present invention.

Examples

With reference to fig. 1, this embodiment provides a method for predicting and dynamically intervening the risk of a mutex deadlock, which includes the following steps:

step 1, requesting a mutex M by a task T;

step 2, if the mutex M is occupied (i.e. in a non-idle state), updating the task T by the mutex registry as a waiter, otherwise, granting a lock to update holder=T, and starting timing;

further, when the lock is idle, starting timing, when the mutex M is released, stopping timing to obtain a lock holding time, updating the lock holding time into hold_ ewma (exponentially weighted moving average of the lock holding time), and updating hold_max (maximum lock holding time);

Step 3, newly adding an edge T-owner (M) in the WFG through a waiting diagram construction module;

Further, the operation process of the newly added edge (record dependence) is as follows:

a. firstly, confirming whether the mutex M has a holder or not, if the mutex M has no holder, no dependence is required to be established;

b. If the task O of the holder exists, recording the waiting task as O in the state information of the task T;

c. meanwhile, adding the task O into a waiting list of the task T, and updating a waiting number count value;

Step 4, detecting whether the newly added edge forms a loop (potential deadlock) or not through an increment loop judging module;

in the embodiment, the specific detection process comprises the steps of when a task T requests a mutex M, if the lock is held by a task O, adding an edge T-O in a waiting diagram WFG, starting from O, searching forwards along the existing dependent edge in the WFG, wherein a searching path represents a waiting chain between tasks, namely, the task O waits for P, the task P waits for Q and the like, and expanding in sequence;

And 5, calculating a deadlock risk value through a risk assessment module, wherein if the deadlock risk value is less than or equal to a threshold value, the system normally grants the mutex, updates the information of a holder of the mutex registry, and if the deadlock risk value is greater than or equal to the threshold value, the strategy intervention module takes or triggers corresponding intervention measures according to configuration. Preferably, the threshold value is in the range of 0 to 1, more preferably 0.4 to 0.7;

In this embodiment, the deadlock risk value is related to local loop information (loop length), mutex lock duration, and task priority difference.

According to the following formula:

;

wherein L represents the number of tasks in the ring; representing the ratio of the average holding time of the mutex to the maximum value of the system; Representing the priority differences of the dependent edges in the ring; a weight representing the number of tasks in the ring; the weight after the sum of the average holding time of the mutex and the maximum value ratio of the system is represented; A weight representing a priority difference, risk_score representing a deadlock risk value;

Further, the intervention measures adopted comprise delaying retry, temporarily blocking high-risk tasks, waiting for low-risk tasks to release locks, improving priority, temporarily improving the priority of low-priority lock-holding tasks, accelerating lock release, adjusting lock acquisition sequence, destroying potential loops and the like.

Step 6, repeating the steps 1-5 until the lock security is granted;

In this embodiment, the security grant refers to that before the system grants the lock, after all deadlock risk prediction and intervention mechanisms determine, the system confirms that the grant of the lock does not lead to a potential deadlock or high risk condition, and the specific determination index is ① that the waiting chart has no loop, and ② deadlock risk value is lower than a threshold. It should be noted that these two criteria must be satisfied at the same time to allow the security grant.

In other embodiments, a system for predicting and dynamically intervening the risk of a mutex deadlock is also provided, the core of which comprises a prediction deadlock protection module, wherein the prediction deadlock protection module is used for executing the method for predicting and dynamically intervening the risk of the mutex deadlock, the prediction deadlock protection module comprises a mutex registry, a waiting pattern constructing (WFG) module, an increment ring judging module, a risk scoring module and an executing intervening module, wherein the input data sequentially carries out mutex registry recording, waiting pattern constructing (WFG) module processing, increment ring judging module detecting and risk scoring module evaluating, and finally the intervening module completes intervening.

Specifically, a predicted deadlock protection module is introduced into the kernel mutex management of the real-time operating system, and is used for predicting potential deadlock before lock grant and adopting dynamic intervention. The prediction deadlock protection module consists of the following parts:

(1) The mutex registry is used for maintaining state information of all mutexes M in the system, including mutex id, task id of the currently held mutex, task queue waiting for the mutex, and lock holding time statistics (average value and maximum value);

The data structure is as follows:

typedef struct {

mutex_id_titd;// unique identifier of mutex

Task_id_ tholder;// currently held task, -1 indicates idle

Task_id_ twaiters [ MAX_ WAITERS ];// task queue waiting for the lock (FIFO or priority order)

Intwaiters _cnt;// number of waiting tasks

Index weighted moving average of uint32_thold_ ewma;// lock hold time

Uint32_thold_max;// historical maximum lock duration

} mutex_info_t;

The update logic is as follows:

a) Mutex creation:

allocating a free space is set to mutex_info_t;

Setting a mutex id, holder= -1;

waiters _cnt=0;// number of waiting tasks is 0

B) When a task requests a mutex:

If the lock is idle, directly setting holder=t, and starting timing;

if the lock is occupied, add T to waiters [ ], waiters _cnt++;

c) The mutex release is:

Stopping locking timing, calculating the locking duration and updating to hold_ ewma;

update hold_max (maximum hold time);

Setting holder to-1;

selecting a waiting task from waiters [ ] to grant a lock, updating the holder, and resetting the lock holding timing of the task;

(2) And a waiting graph construction (WFG) module for maintaining a dependency graph among tasks according to the dependency relationship between the task T and the mutex M.

In this embodiment, when a task T requests a certain mutex M, if M is held by a task O, an edge t→o is added in the wait graph to indicate that T waits for O to release resources, and when the task obtains resources or exits from waiting, an edge removing operation is performed to ensure that the wait graph always reflects real-time dependency of the system, and no invalid or expired edge occurs.

Further, the operation procedure of removing the edge (releasing the dependency) is as follows:

A. when the task T successfully acquires the lock or exits from the waiting state, the system can clear the dependency relationship with the task O;

B. Setting the waiting state of the task T as a non-waiting state, and simultaneously finding out the record of the task O in a waiting list and deleting the record;

C. the deleted mode is to cover the deleted position with the last waiting element and reduce the number count value to keep the data structure compact.

The data structure is as follows:

typedef struct {

task_id_t wait_for [ MAX_ TASKS ];// task list waiting

Int count;// number of tasks waiting

} wfg_node_t;

STATIC WFG _node_ t WFG [ MAX_ TASKS ]; the/WFG node table

Newly adding edges:

void WFG_add_edge(task_id_t T, task_id_t O) {

if (O < 0) return;// no holder, no addition

Record waiting relationship

task_table[T].waiting_for = O;

Addition of/to adjacency list

wfg[T].wait_for[wfg[T].count++] = O;

}

Removing the edge:

void WFG_remove_edge(task_id_t T, task_id_t O) {

task_table[T].waiting_for = -1;

for (int i = 0; i<wfg[T].count; i++) {

if (wfg[T].wait_for[i]== O) {

Deletion of/coverage

wfg[T].wait_for[i]= wfg[T].wait_for[--wfg[T].count];

break;

}

}

}

(3) The increment ring judging module is used for detecting whether the newly added dependence forms a loop (namely potential deadlock);

(4) The risk scoring module is used for calculating a deadlock risk value according to factors such as local loop information, locking time, task priority and the like;

(5) And executing an intervention module, wherein the intervention module is used for taking measures to block the potential deadlock risk when the risk value exceeds a preset threshold value.

The foregoing description is only of the optional embodiments of the present invention, and is not intended to limit the scope of the invention, and all the equivalent structural changes made by the description of the present invention and the accompanying drawings or the direct/indirect application in other related technical fields are included in the scope of the invention.

Claims (10)

1. A method for mutex deadlock risk prediction and dynamic intervention, comprising the steps of:

step 1, requesting a mutex M by a task T;

step 2, if the mutex M is occupied, updating a task T by a mutex registry to be a waiter, otherwise, granting a lock to update holder=T, and starting timing;

Step 3, newly adding an edge T-owner (M) in the WFG through a waiting diagram construction module;

step 4, detecting whether the newly added edge forms a loop or not through an increment loop judging module;

step5, calculating a deadlock risk value through a risk assessment module;

and 6, repeating the steps 1-5 until the lock security is granted.

2. The method for predicting and dynamically intervening mutex deadlock risk according to claim 1, wherein in step 3, the operation procedure of newly adding an edge is:

a. firstly, confirming whether the mutex M has a holder or not, if the mutex M has no holder, no dependence is required to be established;

b. If the task O of the holder exists, recording the waiting task as O in the state information of the task T;

c. Task O is added to the waiting list of task T and the waiting number count value is updated.

3. The method of claim 1 wherein the mutex deadlock risk prediction and dynamic intervention, the method is characterized in that the detection process of the step 4 is as follows:

When a task T requests a mutex M, if the lock is held by a task O, an edge T-O is newly added in the WFG, starting from the O, searching forwards along the existing dependent edge in the WFG, wherein a searching path represents a waiting chain between tasks, namely, the task O waits for P, the task P waits for Q and the like, and the tasks are sequentially unfolded, if the task T reaches a closed loop in the searching process, the newly added edge forms a loop, otherwise, the task is safe.

4. The method for predicting and dynamically intervening the deadlock risk of a mutex according to claim 1 is characterized in that in step 5, if the deadlock risk value is less than or equal to a threshold value, the system normally grants the mutex, updates the information of a registry holder, and if the deadlock risk value is more than or equal to the threshold value, a policy intervening module takes or triggers corresponding intervening measures according to configuration, wherein the threshold value is in a range of 0-1.

5. The method of claim 4, wherein the threshold is in the range of 0.4-0.7.

6. A method of mutex deadlock risk prediction and dynamic intervention according to any of the claims 1-5, wherein the deadlock risk value is related to local loop information, mutex lock time and task priority differences;

The formula is:

;

wherein L represents the number of tasks in the ring; representing the ratio of the average holding time of the mutex to the maximum value of the system; Representing the priority differences of the dependent edges in the ring; a weight representing the number of tasks in the ring; the weight after the sum of the average holding time of the mutex and the maximum value ratio of the system is represented; Weight representing priority differences and risk score representing a deadlock risk value.

7. The method of claim 4-5, wherein the lock security grant is determined by ① wait for a graph to be loop free and ② deadlock risk value is below a threshold.

8. The system for predicting and dynamically intervening the mutex deadlock risk is characterized by comprising a predicted deadlock protection module, wherein the predicted deadlock protection module is used for executing the method for predicting and dynamically intervening the mutex deadlock risk according to any one of claims 1-7, the predicted deadlock protection module comprises a mutex registry, a waiting diagram construction module, an increment ring judgment module, a risk scoring module and an executing intervening module, wherein input data sequentially carries out mutex registry recording, waiting diagram construction module processing, increment ring judgment module detection and risk scoring module evaluation, and finally intervening is completed by the executing intervening module.

9. The system for mutex deadlock risk prediction and dynamic intervention according to claim 8, wherein the mutex registry is configured to maintain status information of all mutexes M in the system;

The waiting diagram construction module is used for maintaining a dependency diagram among tasks according to the dependency relationship between the task T and the mutex M;

The increment ring judging module is used for detecting whether the newly added dependence forms a loop or not;

the risk scoring module is used for calculating a deadlock risk value according to local loop information, locking time and task priority factors;

The execution intervention module is used for taking measures to block potential deadlock risks when the risk value exceeds a preset threshold value.

10. The system of claim 9, wherein the wait map construction module performs an operation of removing edges during processing, the operation being:

A. When the task T successfully acquires the lock or exits from the waiting state, the system clears the dependency relationship with the task O;

B. Setting the waiting state of the task T as a non-waiting state, and simultaneously finding out the record of the task O in a waiting list and deleting the record;

C. the deleted mode is to cover the deleted position with the last waiting element and reduce the number count value to keep the data structure compact.