Lock Graph

lock이 언제 acquire되고 release되는지 관찰할 수 있게 해주는 Graph이다.

방법

  • 쓰레드가 lock X를 acquire하면 nx라는 노드를 만들어준다.
  • lock X를 hold한 상태에서 lock Y를 acquire하면 ny 노드를 생성해주고 nx->ny 라는 edge를 만들어준다.
  • remove nx, nx->*, *->nx를 다 삭제해준다.
  • 이 도중에 cycle이 발생하면 무조건 report한다.

사진

Resource Allocation Graph vs. Lock Graph

  • Resource Graph는 Process와 Resource의 관계를 표현하는 반면에 Lock Graph는 그래프에서 lock의 관계만을 표현한다.
  • 하지만 둘다 Cycle을 확인하는 용도로 쓰인다는 점에서는 같다.
  • 내가 고민했던 Cycle인데도 deadlock이 아닌 경우 또한 어김없이 같다…(흐음…)

사진

Prediction에는 어떻게 활용하지

  • 하나의 프로그램이 다 돌고 나면 lock graph를 저장한다.
  • 이때 저장되는 lock graph에는 release할 때 remove해주는 과정이 생략된다.
  • 즉, lock graph가 막 이 뒤엉켜있을 예정이다.
  • 그리고 lock graph에서 cycle을 확인하며 potential cycle을 확인한다.

믿고 거르는 Cycle

저장한 lock graph의 Cycle 중에도 의미 없는 Cycle들이 존재한다.

하나의 thread 내에서 Cycle이 만들어졌을 때 사진

  • 위와 같은 경우에는 cycle이 하나의 thread에서 만들어졌으므로 거짓이다.
  • 생각해봐라. thread가 자기 자신을 고립시킬 수 있는가.

두개의 thread의 Gate Lock이 같은 경우 사진

  • 잘 이해가 안간다.

Cycle이 발생한 thread 내에서 thread를 생성한 경우 사진

  • thread 내에서 thread를 생성하였다면 1~4번이 진행된 뒤에 11~14가 진행됐을 것이다.
  • 즉 하나의 thread인 것처럼 순서대로 돌 것이기 때문에 deadlock 아니야!

GoodLock Algorithm

이 알고리즘은 위의 3가지 경우를 모두 고려한 deadlock detection algorithm이다.

방법

  1. 일단 Lock Graph를 만든다. 이때 lock graph의 root node는 각 thread이다.
  2. 같은 Lock은 다 연결시켜준다.(bi directional edge로!)
  3. Cycle을 찾는데 안에 Cycle의 lock 중에서 같은 thread로 부터 나온 연속적인 Edge와 Node들은 최대 1번만 존재한다면 valid Cycle로 인정한다.(2,3연속은 상관없는데 연속의 갯수가 1개가 넘어가면 안돼!)

예시

하나의 Lock으로 Cycle이 구성된 경우 - INVALID 사진

같은 thread에서 나온 연속된 Edge가 2개 이상인 경우 - INVALID 사진

VALID한 경우 사진

느낀점

  • 아직은 Goodlock 알고리즘이 감이 잘 안온다.
  • 이거를 어떻게 구현하지….. ㅋㅋㅋ 일단 좀 더 생각해보고 구현해봐야겠다.
  • linked list를 써야하나…ㅠ