💡 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착상태라고 한다.

• 식사하는 철학자 문제

1. 교착 상태 vs 아사 현상

1. 아사 현상: 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제
   1. 에이징(Ageing)으로 해결 가능
   2. 에이징: 몇번 이상 양보를 했다면 더이상 양보하지 않도록 조정
2. 교착 상태: 여러 프로세스가 작업을 진행하다보니 자연적으로 일어나는 문제
   1. 운영체제는 감시를 하다가 교착 상태가 발생하면 강압적으로 해결해야한다.

2. 교착 상태의 발생

1. 시스템 자원
   1. 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다.
   2. e.g. 어떤 프로세스가 임계구역으로 보호되는 프린터, 스캐너, CD등 동시에 같이 사용할 수 없는 시스템 자원을 할당받은 후 양보하지 않는 경우
2. 공유 변수
   1. e.g. 임계 구역에서의 무한 대기
3. 응용 프로그램
   1. 데이터베이스에서는 데이터의 일관성을 유지하기 위해 잠금(lock)을 사용하는 경우

3. 교착 상태 필요 조건

1. 상호 배제(Mutual Exclusion)
   1. 배타적인 자원은 임계구역으로 보호가 되기 때문에 다른 프로세스가 동시에 사용할 수 없다.
   2. 임계구역을 보호하기 위해 잠금 장치를 사용하면 상호 배제와 비선점 조건이 보장되기 때문에 교착상태가 일어날 수 있다.
2. 비선점(Non-preemption)
   1. 한 프로세스가 사용중인 자원은 다른 프로세스가 빼앗을 수 없다. 즉 공유할 수 없다.
3. 점유와 대기(Hold and Wait)
   1. 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서 또 다른 자원을 기다려야한다.
4. 원형 대기(Circular Wait)
   1. 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이룬다.

4. 교착 상태 해결 방법

4.1 교착 상태 예방

💡 교착 상태를 유발하는 4가지 조건을 예방하여 해결한다.

4.1.1 상호 배제 예방

• 시스템 내에 있는 상호 배타적인 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버린다.
• 시스템내의 자원을 공유할 수 있다면 교착 상태가 일어나지 않는다.

한계

• 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야하는 자원이 있다.

4.1.2 비선점 예방

• 모든 자원을 빼앗을 수 있도록 만든다.

한계

• 임계구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없을 뿐만아니라 상호 배제도 보장할 수 없다.
• 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 기준을 정하기가 어렵다.
• 아사 현상을 유발한다.

4.1.3 점유와 대기 예방

• 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 한다.
• 전부 할당하거나 아니면 아예 할당하지 않는 방식을 적용한다.
• 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나 그렇지 못할 경유 자원을 모두 반납해야한다.

한계

• 프로세스가 자신이 사용하는 모든 자원을 자세히 알기어렵다.
• 자원의 활용성이 떨어진다.
• 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다
  • 아사 현상 발생
• 결국 일괄방식으로 작동한다.

4.1.4 원형 대기 예방

• 점유와 대기를 하는 프로세스들이 원형을 이루지 못하게 한다.
• 프로세스들이 한줄로 길게 늘어선다면 그 줄의 맨끝에서부터 문제가 해결될 것이다.
• 자원을 한 방향으로만 사용하도록 설정한다.
  • 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당한다.
  • 숫자가 작은 자원을 잡은 상태에서 큰 숫자를 잡는것은 허용하지만, 그 반대의 경우는 허용하지 않는다.

한계

• 프로세스 작업 진행에 유연성이 떨어진다.
• 자원의 번호를 어떻게 부여할지가 문제이다.

4.2 교착 상태 회피

💡 교착 상태가 발생하지 않는 범위내에서만 자원을 할당하고 교착상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.

• 할당되는 자원의 수를 조절한다.
• 자원이 많이 할당될수록 교착상태가 발생할 확률이 커진다.
  • e.g. 자원이 20개일 때, 20개의 자원을 모두 할당할 경우
• 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(Safe State)와 불안정 상태(Unsafe State)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.
  • 할당된 자원이 적으면 안정상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 크다.

한계

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야한다.
• 시스템의 전체 자원 수가 고정적이여야한다.
• 자원이 낭비된다.

4.2.1 은행원 알고리즘

💡 은행이 대출해주는 방식, 즉 대출 금액이 대출 가능한 범위내이면(안정상태) 허용되지만 그렇지 않으면 거절되는 것과 유사해서 이렇게 불리게 되었다.

변수	설명
전체 자원(Total)	시스탬 내 전체 자원의 수
가용 자원(Available)	시스템 내 현재 사용할 수 있는 자원의 수(가용 자원 = 전체 자원 - 모든 프로세스의 할당 자원)
최대 자원(Max)	각 프로세스가 선언한 최대 자원의 수
할당 자원(Allocation)	각 프로세스에 현재 할당된 자원의 수
기대 자원(Expect)	각 프로세스가 앞으로 사용할 자원의 수 (기대 자원 = 최대 자원 - 할당 자원)

방식

1. 각 프로세스는 자신이 사용할 자원의 최대수(max)를 운영체제에 알려준다.
2. 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다. (안정상태)
3. 가용 자원이 어떤 기대 자원보다 작으면 할당하지 않는다. (불안정 상태)
4. 현재 실행중인 프로세스 가운데 하나라도 끝낼 수 있을 때 가용자원을 할당 해야한다.

4.3 교착 상태 검출

💡 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법이다. 만약 교착 상태가 발견되는 회복 단계를 밟아서 해결한다.
1. 타임 아웃 이용 (가벼운 교착 상태 검출)
2. 자원 할당 그래프 이용 (무거운 교착 상태 검출)

4.3.1 타임아웃(Timeout)

• 일정시간동안 작업이 진행되지 않은 프로세스를 교착상태로 간주하여 처리하는 방법
• 교착상태가 자주 발생하지 않을거라는 가정하에 사용한다.
• 대부분의 데이터베이스에와 운영체제에서 많이 선호하는 방식이다.

한계

1. 엉뚱한 프로세스가 종료될 수 있다.
2. 모든 시스템에 적용할 수 없다.
   1. 하나의 운영체제에서 동작하는 프로세스들은 그 상태를 운영체제가 감시하기 때문에 타임아웃 방식을 적용할 수 있다.
   2. 분산 데이터베이스의 경우, 데이터가 여러 시스템이 나뉘어있고 각 시스템이 네트워크로 연결되어있다.
      1. 원격지에 프로세스가 응담이 없는것이 교착상태인지 네트워크 문제인지, 처리가 늦어지는 건지 파악이 어렵다.

데이터베이스의 교착 상태 처리

💡 데이터베이스에서는 데이터의 일관성이 깨지면 안된다. 데이터를 조작할 때는 반드시 잠금을 얻은 후 작업을 시작한다. 만약 여러개의 잠금을 얻어 작업을 하던 중 타임아웃으로 프로세스가 종료되면 일부 데이터에 문제가 발생할 수 있다.

1. 데이터베이스에서 중요한 데이터에 잠금을 요청하면 체크포인트를 만들고 해당 시점의 스냅샷을 저장한다.
   1. 체크포인트(check point): 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시
   2. 스냅샷(snapshot): 체크포인트 설정시, 하드디스크에 저장되는 현재의 시스템 상태
2. 잠금을 얻은 후 작업을 진행한다.
3. 타임아웃이 걸려서 프로세스를 중단하거나 잠금을 포기해야한다면 롤백을 사용하여 체크포인트 지점으로 시스템을 복귀시킨다.
   1. 롤백(rollback): 작업을 하다가 문제가 발생하여 과거의 체크포인트로 돌아가는 것
   2. e.g. 윈도우의 시스템 복원은 스냅샷과 롤백을 이용하여 운영체제를 복원시키는 작업이다.

4.3.2 자원 할당 그래프 (Resource-Allocation Graph)

• 자원할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고있는지 혹은 기다리고있는지를 알 수 있다.
• 프로세스 작업 장식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다.

한계

• 오버헤드가 발생한다.
  • 그래프 유지, 갱신, 사이클을 검사등 추가 작업

교착 상태가 있는 자원 할당 그래프

1. 운영체제는 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신한다.
2. 이 때 사이클이 발생하면 교착 상태가 검출된 것으로 판단한다.
   1. 단일 자원을 사용하는 경우에만 해당
   2. 다중 자원의 경우, 그래프를 감소한 후 사이클이 남아있는지 확인하여 교착상태를 검출한다.

1. 교착 상태 예방: 실제로 구현하기 어렵다.
2. 교착 상태 회피: 구현할 수 있지만 낭비가 심하다.
3. 교착 상태 검출: 가장 현실적인 방법이다.

5. 교착 상태 회복

💡 교착 상태가 검출된 경우 교착 상태를 푸는 후속작업이다. 교착 상태를 유발한 프로세스를 강제종료한다. 그리고 프로세스가 실행되기 전에 시스템을 복구한다.

강제 종료하는 방법

1. 교착 상태를 일으킨 모든 프로세스를 동시에 종료
   1. 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착상태를 일으킬 가능성이 크다.
   2. 모든 프로세스를 강제로 종료한 후, 다시 실행할 때 순차적으로 실행해야하며, 이 때 어떤 프로세스를 먼저 실행할 것인지 기준이 필요하다.
2. 교착 상태를 일으킨 프로세스중 하나를 골라 순서대로 종료
   1. 교착상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악한다.
      1. 우선순위가 낮은 프로세스를 먼저 종료한다.
      2. 우선순위가 같은 경우 작업시간이 짧은 프로세스를 먼저 종료한다.
      3. 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료한다.

시스템 복구

• 명령어가 실행될 때마다 체크포인트를 만들어서 가장 최근의 검사 시점으로 돌아간다.
  • 이 방법은 작업량이 상당해서 시스템에 부하를 주므로 선택적으로 사용해야한다.

6. 다중 자원과 사이클

1. 단일자원만 있는 자원 할당 그래프에서는, 사이클만으로 교착 상태를 검출
2. 다중 자원을 사용할 때는 그래프 감소를 한 후 사이클이 남아있는지 확인하여 교착상태를 검출

6.1 다중 자원

• 하나의 자원을 여러개의 프로세스가 동시에 사용할 수 있는 경우에는 교착 상태 검출이 복잡하다.
• 다중 자원이 포함된 자원 할당 그래프에서는 대기 그래프와 그래프 감소 방법을 이용하여 사이클을 찾는다.

6.2 사이클

6.2.1 대기 그래프(Wait for graph)

• 자원 할당 그래프에서 프로세스와 프로세스 간에 기다리는 관계만 나타낸 그래프

6.2.2 그래프 감소(Graph reduction)

• 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속적으로 지워가는 작업
  • 작업이 끝날 가능성이 있는 프로세스: 기다리는 자원이 없는 프로세스
• 그래프 감소를 완료한 후에도 사이클이 남아있으면 교착상태가 발생한 것으로 간주한다.