如何检测Java中模型死锁

bbmckpt7 于 2023-02-28 发布在 Java

关注(0)|答案(2)|浏览(120)

怎样写程序来检测型号？
进程、资源、请求和版本列表：

A req R
A req S
A rel R
A rel S
B req S
B req R
B rel S
B rel R

进程内的排序不能重新安排（在上面的例子中，A必须总是在请求S之前请求R），但是跨进程的排序可以重新安排（B可以在A请求R之前请求S和R）
每个排序都将输出一个标头、排序和一个指示该排序是否会导致死锁。
那么，如何对资源请求/释放所有可能的顺序进行排序呢？

测试用例输入：-

情况1：

A req R A req S A rel R A rel S B req S B req T B rel S B rel T C req T 
C req R C rel T C rel R

案例二：

A req R A req S A rel R A rel S B req T B rel T C req S C rel S D req U 
D req S D req T D rel U D rel S D rel T E req T E req V E rel T E rel V 
F req W F req S F rel W F rel S G req V G req U G rel V G rel U

我需要Stack社区的指导来解决这个问题。所以请帮助我。谢谢...
参见下面的源代码

package Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class SortStr {
    public static void main(String[] args) {

        Set<String> s = new HashSet<String>();

        List<String> A = List.of("A req R", "A req S", "A rel R", "A rel S");
        List<String> B = List.of("B req S", "B req R", "B rel S", "B rel R");
        s.addAll(A);
        s.addAll(B);

        /* List<String> A = List.of("A");
        List<String> B = List.of("1");
        List<String> C = List.of("X");

        s.addAll(A);
        s.addAll(B);
        s.addAll(C); */

        Map<Integer, List<String>> result = new HashMap<>();
        permutations(s, new Stack<String>(), s.size(), result);

        result.forEach((key, value) -> 
            System.out.println("ORDER " + key + " : " + value)
        );
    }

    public static void permutations(Set<String> items, Stack<String> permutation, int size,
            Map<Integer, List<String>> result) {

        /* permutation stack has become equal to size that we require */
        if (permutation.size() == size) {
            /* print the permutation */
            // System.out.println(Arrays.toString(permutation.toArray(new String[0])));

            /* add the permutation in the result */
            Integer key = (result.size() > 0) ? result.size() + 1 : 0;
            result.put(key, Arrays.asList(permutation.toArray(new String[0])));
        }

        /* items available for permutation */
        String[] availableItems = items.toArray(new String[0]);
        for (String i : availableItems) {
            /* add current item */
            permutation.push(i);

            /* remove item from available item set */
            items.remove(i);

            /* pass it on for next permutation */
            permutations(items, permutation, size, result);

            /* pop and put the removed item back */
            items.add(permutation.pop());
        }
    }
}

Java

来源：https://stackoverflow.com/questions/75540173/how-to-detect-model-deadlock-in-java

2条答案

按热度按时间

bnlyeluc1#

我会尝试类似这样的方法（根据您的具体要求，您可能需要添加一些逻辑）：

String case1 = "A req R A req S A rel R A rel S B req S B req T B rel S B rel T C req T C req R C rel T C rel R";
    String case2 = "A req R A req S A rel R A rel S B req T B rel T C req S C rel S D req U "
            + "D req S D req T D rel U D rel S D rel T E req T E req V E rel T E rel V "
            + "F req W F req S F rel W F rel S G req V G req U G rel V G rel U";
    String input = case1;
    boolean deadlock = false;
    
    Map<String, Boolean> isResourceUsed = new HashMap<>();
    
    for (int i=0; i<input.length()-7; i+=8) {
        String str = input.substring(i, i+7);
        String process = str.substring(0, 1);
        boolean isRequest = str.substring(2,5).equals("req");
        String resource = str.substring(6,7);
        
        if (isRequest) {
            if (isResourceUsed.containsKey(process) && isResourceUsed.get(process) == true) {
                deadlock = true;
                break;
            }
            else {
                isResourceUsed.put(process, true);
            }
        }
        else {
            if (isResourceUsed.containsKey(process)) {
                isResourceUsed.put(process, false);
            }
        }
        if (deadlock) {
            System.out.println("deadlock");
        }
        else {
            System.out.println("no deadlock");
        }
    }

赞(0）回复(0）举报 2023-02-28

mum43rcc2#

所以你有一组不能改变顺序的动作。

List<String> A = List.of("A req R", "A req S", "A rel R", "A rel S");
List<String> B = List.of("B req S", "B req R", "B rel S", "B rel R");

现在，您将创建一个进程列表。

List<String> processes = new ArrayList<>();

processes.addAll(A);
processes.addAll(B);

然后检查进程是否存在死锁，我们可以为此创建一个方法。

boolean checkForDeadlock( List<String> processes);

第一个问题，你需要生成所有的排列。

a, a, a, a, b, b, b, b
a, a, a, b, a, b, b, b
...

你可以看到有很多可能性，你可以写一个4x嵌套循环。

List<String> processes = new ArrayList<>(B);
for( int i = 0; i<5; i++){
    for(int j = 0; j<=i; j++){
        for(int k = 0; k<=j; k++){
            for(int m = 0; m<=k; m++){
             processes.add( m, A.get(0) );
             processes.add(1 + k, A.get(1));
             processes.add(2 + j, A.get(2));
             processes.add(3 + i, A.get(3));
            }
        }
    }
}

然后是死锁检查，当A持有R，B持有S时，死锁发生。

int aqr = processes.indexOf("A req R");
int bqr = processes.indexOf("B req R");
int alr = processes.indexOf("A rel R");
if( aqr < bqr && alr > bqr){
    //possible deadlock.
    int aqs = processes.indexOf("A req S");
    int bqs = processes.indexOf("B req S");
    
    if( ars > brs ){
        //A requests S after B has acquired S
        return true;
        //we don't need to see if B has released S, because
        //because we know B has not acquired R yet.
    }
}
return false;

这是非常具体的第一个例子。在第二个例子中，你必须1。将排列推广到不仅仅是A和B物种。2。推广资源获取以处理循环依赖。例如D有U需要T;E有T需要V，G有V需要U。
作为第二个例子的提示。单锁是不相关的，所以划掉B和C。A只共享一个资源，所以可以划掉它。F只共享一个资源，所以划掉它。所以你唯一可能的死锁是在DE和G之间
这不仅仅是一个家庭作业，这是一个完整的项目。你真的应该把它分解成个别的问题，然后问那些。

赞(0）回复(0）举报 2023-02-28

我来回答

如何检测Java中模型死锁

2条答案

相关问题

热门标签

最新问答