Tôi đang cố gắng viết thuật toán phát hiện bế tắc. Tôi phải sử dụng mảng 7x7 chứa đầy w, x và n. w = đang chờ tài nguyên, x = tài nguyên độc quyền, n = tài nguyên không cần thiết. Hàng đại diện cho công việc hoặc quy trình và cột đại diện cho tài nguyên. Tôi sẽ đưa ra một loạt các trường hợp thử nghiệm:

    Chuỗi [][] lưới = {{"w","n","x","x","x","n","n"},
                        {"x","w","n","n","n","x","n"},   
                        {"n","x","w","n","n","n","n"},   
                        {"n","n","n","n","n","n","x"},   
                        {"n","n","n","n","n","n","n"},   
                        {"n","n","w","n","n","n","w"},   
                        {"w","w","w","w","w","w","w"}};

Như bạn có thể thấy, bế tắc xảy ra giữa các dòng 0, 1 và 2. R0 đang đợi C0 (tài nguyên 1), nhưng R1 đang giữ nó. R1 đang đợi C1 (tài nguyên 2), nhưng R2 đang bảo lưu nó. R2 đang đợi C2 (tài nguyên 3), nhưng R0 đang giữ lại nó. Nhìn bề ngoài, đây là một chu kỳ.

Thuật toán của tôi tìm kiếm w trong hàng và x trong cột và đặt chúng vào mảng 1D. Phần đó hoạt động. Mảng sẽ đọc wxwxw x... cho đến hết. Để kiểm tra xem chúng ta đã hoàn thành một vòng lặp hay chưa, tôi theo dõi chỉ mục của hàng nơi tìm thấy w và x và đặt chúng vào một mảng 1D khác. Vì vậy, trong ví dụ này, mảng đầu tiên sẽ đọc wxwxw x... và mảng thứ hai sẽ đọc 0 1 1 2 2 0... Khi kích thước của mảng một chiều đạt 4 (được xác định bởi biến đếm), tôi sẽ kiểm tra chỉ mục đầu tiên (mảng[0]) và chỉ mục cuối cùng (mảng[count-1]). Nếu mảng [0] là 'w' và mảng [đếm-1] là 'x' và chỉ số hàng bằng nhau thì sẽ phát hiện thấy bế tắc.

Thuật toán của tôi hoạt động trên giấy nhưng bằng cách nào đó, phép toán cho mảng thứ hai (WHI) của tôi sai, các chỉ mục trong lần đầu tiên in chính xác (0 1 1 2 2 0...) nhưng nếu tôi in ra WHI [0] (phải luôn là 0 ) nó cho tôi 1 2 5 5 6 6 6 6 ...

    public void printSingleArrays()
{
    Chuỗi [] WH = Chuỗi mới [14];
    int [] WHI = int mới[14];
    số int = 0;

    for (int a = 0; a < WH.length && a < WHI.length; a += 2)
        for (int i = 0; i < array.length; i++)
            for (int j = 0; j < array[i].length; j++)
            {
                if (mảng[i][j].equals("w"))
                {
                    WH[a] = mảng[i][j];
                    WHI[a] = tôi;

                    count++;

                    System.out.print(WH[a] + " ");
                    System.out.println(WHI[a] + " ");

                    for (int k = 0; k < array.length; k++)
                    {
                        if (mảng[k][j].equals("x"))
                        {
                            WH[a+1] = mảng[k][j];
                            WHI[a+1] = k;

                            System.out.print(WH[a+1] + " ");
                            System.out.print(WHI[a+1] + " ");

                            count++;

                            nếu (đếm >= 4)
                            {
                                System.out.print("Số đếm là: " + count); // dùng để gỡ lỗi
                                System.out.print(", Chữ cái đầu tiên là: " + WH[0]);
                                System.out.println(", Chỉ mục là: " + WHI[0]);
                            }
                            khác
                                System.out.println();
                        }
                    }
                }
            }
    for (int m = 0; m < WH.length; m++)
    {
        System.out.print(WH[m] + " ");
    }
    System.out.println();
    for (int n = 0; n < WH.length; n++)
    {
        System.out.print(WHI[n] + " ");
    }
}

Rõ ràng, cần phải có một hàm tạo và một lớp máy khách. Tôi chỉ muốn biết mảng WHI của tôi thay đổi như thế nào khi tôi in ra WHI[0]? Nếu bạn cần thêm tài nguyên hoặc hướng dẫn để giải quyết vấn đề, vui lòng cho tôi biết!

câu trả lời hay nhất

Đây là một ví dụ về việc sử dụng đồ thị để giải một bài toán.

• Đầu tiên xây dựng biểu đồ bằng cách lặp qua lưới
• Đầu tiên lặp qua tất cả các hàng (j) của mỗi cột (i), nó sẽ tìm nút thu thập có "x" và nút chờ có "w".
• Sau đó thêm nút getter vào danh sách nhận của từng nút đang chờ.
• Bây giờ chúng ta đã có sẵn biểu đồ, chỉ cần lặp qua biểu đồ dfs để tìm chu trình và xem liệu nút đã được truy cập trước đó chưa, nếu bất kỳ nút nào đã được truy cập trước đó thì đó là một chu trình, nghĩa là nó đang bế tắc.
• Bây giờ trong trường hợp này, biểu đồ có thể là biểu đồ bị ngắt kết nối, nghĩa là tất cả các nút có thể không truy cập được một hoặc nhiều nút. Trong trường hợp này, chúng ta có thể cần theo dõi những nút nào đã được truy cập khi phát hiện các vòng lặp và tìm kiếm các vòng lặp cho các nút chưa được truy cập.

Đây là mã:

ví dụ gói;

nhập java.util.ArrayList;
nhập java.util.HashSet;
nhập java.util.List;
nhập java.util.Set;

lớp công khai DeadlockDetection {
    Chuỗi tĩnh [][] lưới = {{"w","n","x","x","x","n","n"},
        {"x","w","n","n","n","x","n"},
        {"n","x","w","n","n","n","n"},
        {"n","n","n","n","n","n","x"},
        {"n","n","n","n","n","n","n"},
        {"n","n","w","n","n","n","w"},
        {"w","w","w","w","w","w","w"}};

    public static void main(String[] args) {
        System.out.println(isDeadlock());
    }


    Nút lớp tĩnh công khai {
        int id;
        List AcacquirNodes = new ArrayList();
        Nút công khai(int id){
            this.id=id;
        }
    }

    boolean tĩnh công khai isDeadlock(){
        Nút List = new ArrayList();
        //Xây dựng đồ thị
        for(int i=0; i< Grid.length; i++){
            nút.add (Nút mới (i));
        }
        for(int i=0; i
            Danh sách waitNodes = new ArrayList();
            Người mua nút = null;
            for(int j=0; j
                if(grid[j][i].equals("w") ){
                    chờNodes.add(nodes.get(i));
                } else if(grid[j][i].equals("x") ){
                    người mua = node.get(i);
                }
                if(người mua != null)
                    for(Node n: waitNodes)
                        n.acquirerNodes.add(người mua);
            }
        }
        // Trong trường hợp biểu đồ không bị ngắt kết nối mạnh, chúng ta có thể cần duyệt qua tất cả các nút.
        HashSet nodeFoundInGraph = new HashSet();
        for(int i=0; i< Grid.length; i++){
            if(!nodesFoundInGraph.contains(nodes.get(i))){
                HashSet đã truy cập = new HashSet();
                if(isCycle(nodes.get(i), đã truy cập))
                    trả về đúng sự thật;
                nútFoundInGraph.addAll(đã truy cập);
            }
        }
        trả về sai;
    }

    boolean tĩnh công khai isCycle(Nút nút, Set đã truy cập){
        if(visited.contains(node)){
            trả về đúng sự thật;
        }
        đã truy cập.add(nút);
        for(Node n: node.acquirerNodes){
            if(isCycle(n, đã truy cập)){
                trả về đúng sự thật;
            }
        }
        trả về sai;
    }
}

Về java - mô phỏng bế tắc bằng mảng đa chiều, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/22624836/