다차원 배열을 사용하여 교착 상태 시뮬레이션

Question

교착 상태 감지 알고리즘을 코딩하려고합니다. w, x 및 n으로 채워진 7x7 배열을 사용해야합니다. w = 자원 대기, x = 배타적으로 자원 보유, n = 자원 필요 없음. 행은 작업 또는 프로세스를 나타내며 C 럼은 자원을 나타냄니다. 나는 테스트 케이스 배열을 줄 것이다 :

String [][] grid = {{"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"}}; 

당신이 교착 상태가 행 0, 1 중 하나입니다, 2 R0는 forC0 (자원 1) 대기 알 수 있듯이, 그러나 R1은 그것을 들고있다. R1은 C1 (자원 2)을 기다리고 있지만 R2는 그것을 보유하고 있습니다. R2는 C2 (자원 3)를 기다리고 있지만 R0은이를 보유하고 있습니다. 시각적으로, 이것은 순환이다.

내 알고리즘은 행에 대해 w를 검색하고 x에 대해 열을 검색하고이를 단일 차원 배열에 배치합니다. 그 부분은 작동합니다. 배열은 끝까지 w x w x w x ...로 읽어야합니다. 사이클을 완료했는지 확인하려면 w와 x가있는 행의 인덱스를 추적하여 다른 일차원 배열에 배치하십시오. 그래서이 예제에서 첫 번째 배열은 wxwxw x를 읽을 것이고 두 번째 배열은 0 1 1 2 2 0 ... 일차원 배열이 count 변수에 의해 결정된 4의 크기에 도달하면 첫 번째 인덱스 (array [0])와 마지막 인덱스 (array [count-1])를 확인하십시오. 배열 [0]이 'w'이고 배열 [count-1]이 'x'이고 행 인덱스가 같으면 교착 상태가 감지됩니다.

내 알고리즘은 종이에서 작동하지만 어떻게 든 내 수학은 두 번째 배열 (WHI)에서 잘못되었습니다. 색인은 처음으로 올바르게 인쇄됩니다 (0 1 1 2 2 0 ...). 그러나 WHI [0 (항상 0이어야 함)는 분명히 ... 나에게

public void printSingleArrays() 
{ 
    String [] WH = new String[14]; 
    int [] WHI = new int[14]; 
    int count = 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 (array[i][j].equals("w")) 
       { 
        WH[a] = array[i][j]; 
        WHI[a] = i; 

        count++; 

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

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

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

          count++; 

          if (count >= 4) 
          { 
           System.out.print("Count is: " + count); // used for debugging 
           System.out.print(", First letter is: " + WH[0]); 
           System.out.println(", Index is: " + WHI[0]); 
          } 
          else 
           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] + " "); 
    } 
} 

1 2 5 5 6 6 6 6을 제공, 생성자와 클라이언트 클래스가 필요하다. WHI [0]를 출력 할 때 WHI가 어떻게 변하는 지 알고 싶습니다. ?? 더 많은 리소스가 필요하거나 문제를 가르치고 싶다면 알려주세요!

Answer 1

다음은 그래프를 사용하여 문제를 해결하는 예입니다. 각 열 (I)의 모든 행 (j)을 통해 그리드를 통해

우선 순회를 반복하여

• 먼저 구조체 그래프, 그것은 "w"를 가지고있는 "X"및 대기 노드가 취득자 노드를 찾는 것이다.
• 그런 다음 대기 노드 각각의 획득 목록에 획득 노드를 추가하십시오.
• 이제 우리는 그래프를 준비했습니다. 그래프를 반복하여 dfs를 통해주기를 찾고 노드가 방문했는지 확인하십시오. 노드가 이전에 방문한 적이 있다면 사이클입니다. 이는 교착 상태를 의미합니다.
• 그래프가 연결 해제 될 수 있음 그래프는 모든 노드가 하나 이상의 노드에 도달하지 않을 수 있음을 의미합니다. 이 경우주기를 감지하는 동안 어떤 노드가 방문되었는지 추적하고 방문하지 않은 노드의주기를 찾아야 할 수도 있습니다. 여기

코드이다

package example; 

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Set; 

public class DeadlockDetection { 
    static String [][] grid = {{"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()); 
    } 


    public static class Node{ 
     int id; 
     List<Node> acquirerNodes = new ArrayList<Node>(); 
     public Node(int id){ 
      this.id=id; 
     } 
    } 

    public static boolean isDeadlock(){ 
     List<Node> nodes = new ArrayList<Node>(); 
     //Construct Graph 
     for(int i=0; i< grid.length; i++){ 
      nodes.add(new Node(i)); 
     } 
     for(int i=0; i<grid.length; i++){ 
      List<Node> waitingNodes = new ArrayList<Node>(); 
      Node acquirer = null; 
      for(int j=0; j<grid.length; j++){ 
       if(grid[j][i].equals("w")){ 
        waitingNodes.add(nodes.get(i)); 
       } else if(grid[j][i].equals("x")){ 
        acquirer = nodes.get(i); 
       } 
       if(acquirer != null) 
        for(Node n: waitingNodes) 
         n.acquirerNodes.add(acquirer); 
      } 
     } 
     //In case of non-strongly disconnected graph, we may need to traverse through all nodes. 
     HashSet<Node> nodesFoundInGraph = new HashSet<Node>(); 
     for(int i=0; i< grid.length; i++){ 
      if(!nodesFoundInGraph.contains(nodes.get(i))){ 
       HashSet<Node> visited = new HashSet<Node>(); 
       if(isCycle(nodes.get(i), visited)) 
        return true; 
       nodesFoundInGraph.addAll(visited); 
      } 
     } 
     return false; 
    } 

    public static boolean isCycle(Node node, Set<Node> visited){ 
     if(visited.contains(node)){ 
      return true; 
     } 
     visited.add(node); 
     for(Node n: node.acquirerNodes){ 
      if(isCycle(n, visited)){ 
       return true; 
      } 
     } 
     return false; 
    } 
}