교착상태(DeadLock) 정의

• 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상

• 프로세스들이 더 이상 진행을 못하고 영구적으로 블록 되어 있는 상태 => 기다리던 사건이 영구적으로 결코 발생하지 않기 때문

• 시스템 자원에 대한 경쟁 도중에 발생할 수도 있고 프로세스 간 통신 도중에 발생할 수도 있다.
• 교착상태가 일어나지 않도록 프로그램을 잘 짜면 좋지만 잘 돌아가던 프로그램이 몇년후에야 특수한 조건이 맞물려 교착상태가 일어나기도 한다.

교착상태가 일어나기 위한 조건

	교착상태 가능	교착상태 발생
1.상호배제	O	O
2.점유대기	O	O
3.비선점	O	O
4.환형대기	X	O

4가지 조건 모두를 교착상태가 일어나기 위한 조건이라고 보는곳도 있고 아닌곳도 있다. <운영체제 내부구조 설계 및 원리 8판>에서는 1-3번은 지켜야할 조건이고 4번은 1-3을 지키면서 발생한 상태라고 설명하기도 한다.

• 상호배제(Mutual Exclusion) : 한 순간에 한 프로세스만이 자원을 사용할 수 있다. 즉 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수는 없다

• 점유대기(Hold and Wait) : 이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다리고 있다.

• 비선점(No Preemption) : 프로세스에 의해 점유된 자원을 다른 프로세스가 강제적으로 빼앗을 수 없다.

• 환형대기(Circular Wait) : 프로세스들 간에 closed chain이 존재한다. 자원할당 그래프에서 환형이 만들어진다. Closed chain에서 블록된 프로세스가 자원을 점유하고 있는데 이 자원을 체인 내부의 다른 프로세스가 원하며 대기하고 있다.

교착상태 해결

예방은 교착상태가 일어나지 않도록 하고, 회피는 자원할당을 조절하여 교착상태를 피하고 발견은 일단 실행하되 교착상태가 발생하면 그제서야 수정을 하는 방법. 몇 년후에야 발생하는 교착상태도 있다는 것을 고려하면 detect도 좋은 방법이 될 수 있다.

1. 예방 (Prevent)

교착 상태의 발생조건 1-4에서 하나를 시스템에서 허용하지 않음. 자원낭비가 가장 심한 기법이다.

상호배제

• 한번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 합니다.
• 하지만 공유자원의 일관성을 유지하기 위해 반드시 필요한 조건이라서 읽기는 동시에 가능, 쓰기는 하나의 프로세스만이 허용되는 방식을 사용한다.

점유대기

• 프로세스가 필요한 자원들을 모두 요청하고 모두 할당에 성공했을 때만 프로세스를 실행한다.
• 단점
  • 모든 자원을 할당받기위해 너무 오래 기다릴 수는 없다.
  • 한꺼번에 할당 받은 자원들 중에 특정 자원이 프로세스가 거의 끝날때 잠깐 필요한것이라면 쓰지도 않는데 점유를 해서 낭비, 비효율적이다.
  • 프로세스가 미래에 사용될 모든 자원을 알기 어렵다. (특히 app이 모듈화 구조이거나 멀티쓰레드로 구성된 경우)

비선점

• 자원을 점유한 프로세스가 다른 자원을 할당 받을 수 없다면 일단 자신이 점유했던 자원을 반납한다

• 다른 프로세스가 점유중인 자원을 원하면 OS가 강제로 자원을 반납시켜 필요한곳에 할당한다.

환형대기

• 자원을 선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 하는 것입니다.
• 예 : 자원을 R1->R2 순서로만 할당받도록 순서를 미리 정한다. 프로세스A가 R1을 점유하고 R2를 요구했을때 교착상태가 일어나려면 프로세스B가 R2를 점유하고 R1을 요구하는 상태여야 한다. 그런데 프로세스B는 자원을 할당받을 수 있는 순서가 틀렸기에 처음부터 교착상태가 일어나는 일은 없다.

2. 회피 (Avoid)

예방이 교착상태 발생을 위해 필요한 4가지 조건중에 하나를 예방하는 방법이라면 회피는 1~3은 허용하되 대신 자원을 할당할때 교착상태가 발생가능한 상황으로 진행되지 않도록 고려한다. 현재 자원 할당의 상태에 따라 안전하게 자원 할당을 결정

• 장점 : 예방에 비해 상대적으로 자원 사용 효율성이 높아짐

• 단점 : 앞으로 교착상태가 일어날지 계산한다는것 자체가 미래를 내다본다는 것으로 현실적으로 계산하기 어렵다. 다음 조건들에 부합해야 계산이 가능하다.

  • 프로세스들이 사용할 최대 자원 요구량을 미리 OS에게 알려줘야 한다.

  • 프로세스들이 독립적이어야 한다. ProcessA가 ProcessB보다 먼저 수행되어야 한다는 것과 같은 수행순서 종속 관계가 없어야 한다.
  • 자원 개수가 고정되어 있어야 한다.
  • 자원을 선점한 채 종료하는 프로세스가 없어야 한다.

프로세스 시작거부

• 프로세스가 시작하려 할 때 요구하는 자원 할당이 교착상태 발생의 가능성이 있으면, 프로세스를 시작 시키지 않는다.

• 새로운 프로세스와 기존의 프로세스들이 요구하는 자원의 개수가 그 자원의 전체 개수보다 적을 경우에 수행을 허용

• 단점 : 최악의 경우 모든 프로세스들이 동시에 최대 자원을 요구하여 사용함을 가정하고있으므로 효율적이진 않다.

자원할당 거부

• 수행 중인 프로세스가 요구하는 추가적인 자원할당이 교착상태 발생의 가능성이 있으면, 자원을 할당하지 않는다.

• Banker’s Algorithm (은행원 알고리즘)

  • Edsger Dijkstra가 개발

  • 프로세스가 자원을 요구할 때 시스템이 자원을 할당한 후 안정상태로 남아있게 되는지를 사전에 검사하여 교착상태를 회피하는 방법

  • 참고 링크

    http://www.jidum.com/jidums/view.do?jidumId=451

    https://jhnyang.tistory.com/102

    https://m.blog.naver.com/dong5053/220717510273

3. 발견 (Detect)

자원 할당에 따로 제약을 두지 않고 주기적으로 시스템에 교착상태가 (or 환형대기조건이 발생) 발생하면 그때 발견하고 회복시킨다.

교착상태 발견 Alg

1. 할당행렬에서 행의 값이 모두 0인 프로세스를 우선 표시한다. P4는 보유한 자원이 없으니까 교착상태에 있을 수가 없다. 따라서 제외를 한다.

   

2. 임시벡터 W를 만든다. 그리고 가용 벡터의 값 (= 현재 사용가능한 자원의 개수)를 W의 초기값으로 설정한다. A자원을 보유하고 있는 프로세스가 B자원을 요구할때 B자원을 할당받을 수 없을때 데드락이 발생한다. 그러므로 할당해줄 수 있는, 사용가능한 자원의 수를 체크해야한다. P4의 요청행렬 값을 W에 넣는다.

   

3. mark되지 않은 프로세스(P1,P2,P3) 들 중에서 요청행렬Q의 특정 행의 값이 모두 W보다 작은 프로세스를 찾는다. P3이 해당된다. 만약 해당하는 프로세스가 없다면 ALG를 종료한다.

   

4. 만족하는 행을 찾으면 해당프로세스의 할당행렬 행 값으로 W를 갱신한다. 임시벡터 W에 P3의 할당행렬 값을 더한다. 현재 사용가능한 자원으로 다음 작업을 수행할 수 있는 프로세스를 찾는것이다. P3은 R5자원을 얻어서 작업을 수행하고 R4자원을 내놓을 것이다. 따라서 사용가능한 자원은 R4, R5가 되고 P3은 교착상태가 일어나지 않을 프로세스이다.

   

5. 다시 Q에서 W보다 작은 행을 찾는다. 없다면 ALG를 종료한다. 이때 표시되지 않은 상태로 남아있는 프로세스들이 교착상태에 있는 것이다. 교착상태에 있는 프로세스를 이러한 과정으로 발견 후 회복 Alg를 실행한다. 예시에서는 P1과 P2가 교착상태에 있는 프로세스들이다.

   

교착상태 회복 Alg

• 프로세스 종료 : 교착상태에 있는 프로세스를 종료
  • 교착상태에 있는 모든 프로세스를 종료하는 방법
  • 교착상태에 있는 프로세스들을 하나씩 종료해가며 교착상태를 해결하는 방법. 종료 시키는데 비용이 적은 순서로 종료시킨다. 1개를 종료시키고 발견Alg를 적용하는 방식으로 해결됐는지 확인한다.
  • 교착상태에 있는 프로세스의 수행을 롤백 시키는 방법. 미리 정의된 특정 체크포인트 시점까지 되돌린 후 다시 수행
• 자원선점 : 교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시키는 방법
  • 자원 선점 시 고려사항
    1. 자원을 선점할 프로세스 선택 문제 : 최소의 피해를 줄 수 있는 프로세스를 선택
    2. 자원을 선점한 프로세스의 복귀 문제 : 자원이 부족한 상태이므로 대부분 일시 중지시키고 다시 시작하는 방법을 사용
    3. 기아 현상 문제 : 한 프로세스가 계속하여 자원 선점 대상이 되지 못하도록 고려

정리

교착상태 해결에 여러가지 방법이 있지만 실제로 OS를 설계할 때는 여러가지 전략을 섞어서 사용한다.

통합적인 전략

1. 자원들을 유형에 따라 나눈다. (자원 클래스)

2. 자원 클래스들 간에 할당 순서를 두어 환형대기를 막는다.

3. 클래스 내부의 자원들 간에는 각 클래스에 적절한 교착상태 해결 방법을 사용한다.

• 스왑공간 : 보조기억장치 상의 메모리 블록, 프로세스들을 스와핑하는데 사용됨
  • 예방 : 필요한 모든 자원을 한꺼번에 요청 è hold and wait 조건을 없앤다. 스왑공간을 할당하려는 프로세스가 미리 필요한 공간의 크기를 알 수 있기 때문에 가능한 방법이다.
• 프로세스자원 : 테이프 드라이브나 파일 같은 할당 가능한 장치 자원
  • 회피 : 프로세스가 이 클래스에 속한 자원의 예상 사용 시간을 미리 예측할 수 있으며, 이 시간을 OS에게 알릴 수 있으므로 구현가능.
  • 예방 : 자원 할당 순서를 미리 결정하는 방법도 가능
• 주 메모리 : 페이지나 세그먼트 등의 단위로 프로세스들에게 할당되는 자원
  • 예방 : 선점을 허용하는 방법이 적절하다. (예 – 프로세스가 블록되면 그 프로세스의 수행 이미지는 보조 기억 장치로 스왑되고, 프로세스가 사용하던 메모리 공간을 반납하는 것)
• 내부 자원 : 입출력 채널 같은 자원
  • 예방 : 자원 할당 순서를 미리 결정하는 방법

추가로 공부해야 할 것

• 은행원 알고리즘
• 교착상태 발견 알고리즘
• Wait-die와 Wound-wait 기법
• 식사하는 철학자 문제
• Livelock

참고

운영체제 내부구조 설계 및 원리 8판

http://www.jidum.com/jidums/view.do?jidumId=451 Banker’s 알고리즘

https://jhnyang.tistory.com/102 [운영체제]교착상태 회피-은행원 알고리즘(Banker’s Algorithm) 쉬운 예시, 안전상태, 불안전상태

https://m.blog.naver.com/dong5053/220717510273 운영체제 - 교착상태, 기아상태, 은행가 알고리즘

https://coding-factory.tistory.com/311 [OS] 교착상태란 무엇인가?

http://www.jidum.com/jidums/view.do?jidumId=447 교착상태(Deadlock)