Java环境下死锁检测与合法资源操作序列生成技术求助

需求说明 #

我需要编写程序实现以下功能：

• 生成进程资源请求（req）、释放（rel）操作的所有合法排列：进程内部的操作顺序不可打乱（例如进程A必须先执行A req R，再执行A req S），但不同进程的操作顺序可自由调整。
• 对每个排列输出：排列标题、完整操作序列，并标注该序列是否触发死锁。

问题现状 #

我编写了一段Java代码，但代码中的死锁判断逻辑存在错误，无法正确识别死锁场景。以下是我的代码：

import java.io.FileWriter;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

public class SortStr {

    public static Set<String> permutations = new HashSet<String>();
    public static void main(String[] args) {
    
        List<String> processes = List.of("A req R", "A req S", "A rel R", "A rel S", "B req S", "B req R", "B rel S", "B rel R");
        // List<String> processes = List.of("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");
        Map<String, List<String>> grouped = processes.stream().collect(Collectors.groupingBy( s -> s.substring(0, 1) ) );
    
        String order = processes.stream().map( s -> s.substring(0, 1) ).collect( Collectors.joining() );
        permutations(order);
    
        int key = 0;
        try{
            String filename= "MyFile.txt";
            FileWriter fw = new FileWriter(filename,true); //the true will append the new data

            for (String o : permutations) {

                Map<Character, Iterator<String>> iterators = grouped.entrySet().stream().collect( 
                    Collectors.toMap( 
                        e->e.getKey().charAt(0), 
                        e-> e.getValue().iterator() 
                    ) 
                );

                String s = "ORDER "+ ++key + " : ";
                Map<String, Boolean> isResourceUsed = new HashMap<>();
                boolean deadlock = false;

                for( char c: o.toCharArray() ){ 
                    // s += iterators.get(c).next() + ", ";
                    // System.out.print( iterators.get(c).next() + ", ");

                    String pro = iterators.get(c).next();
                    String process = pro.substring(0, 1);
                    boolean isRequest = pro.substring(2,5).equals("req");
                    String resource = pro.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) {
                        s += " DEADLOCK !";
                        break;
                        // System.out.println("deadlock");
                    }
                    else {
                        s += pro +", ";
                        // System.out.println("no deadlock");
                    }
                }
                System.out.println(s);
                fw.write(s + "\n"); //appends the string to the file
                System.out.println(); 
            }
            fw.close();
        } catch(IOException ioe){
            System.err.println("IOException: " + ioe.getMessage());
        }
    }

    public static void permutations(String s) { permutation("", s); }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            permutations.add(prefix);
        } else {
            Set<Character> checked = new HashSet<>();
            for (int i = 0; i < n; i++){
                Character c = str.charAt(i);
                if( checked.contains(c) ) continue;
                permutation(prefix + c, str.substring(0, i)  + str.substring(i+1, n));
                checked.add(c);
            }
        }
    }
}

测试用例 #

测试用例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

测试用例2 #

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 exchange，提问作者Harsh Patel