[운영체제] Ch7 교착상태

박소미·2024년 12월 3일

운영체제

목록 보기

7/10

7.1 교착 상태 문제 제기

교착상태란?

자원을 소유한 상태에서 상대방이 소유한 자원을 기다리며, 서로의 작업이 무한 대기에 빠지는 상태.

📌실생활에서 발생하는 교착상태 사례

사례 1: 식사 중 교착상태

상황:
- 한 사람이 밥을 먹기 위해 숟가락과 젓가락을 모두 필요로 하는 규칙.
- A는 숟가락을 들고 있고, B는 젓가락을 들고 있는 경우.
문제:
- A는 B가 든 젓가락을 얻기 위해 기다림.
- B는 A가 든 숟가락을 얻기 위해 기다림.
- 결과적으로 무한 대기에 빠짐.

사례 2: 교차로의 교착상태

상황:
- 자동차들이 한 길을 점유하며 다른 길을 기다리는 경우.
- 예를 들어, 한 차량이 교차로를 통과하지 못하고, 다른 방향의 차량들도 진행하지 못함.
문제:
- 모든 차량이 서로를 기다리며 이동하지 못하는 교착상태에 빠짐.

공통점

자원을 소유한 상태에서 추가 자원을 얻기 위해 기다림.
상대방도 동일한 방식으로 기다림.
결과적으로 무한 대기가 발생하여 시스템 정체.

📌식사하는 철학자 문제 (Dining Philosophers Problem)

문제 설명

설정:
- 5명의 철학자가 원형 테이블에 앉아 있음.
- 각 철학자는 스파게티를 먹기 위해 양 옆에 놓인 포크 2개를 사용해야 함.
- 철학자는 옆 철학자와 소통하지 않음.
규칙:
- 왼쪽 포크를 먼저 들고, 다음으로 오른쪽 포크를 듦.
- 포크가 사용 중이라면 대기.

발생할 수 있는 문제

교착상태(Deadlock):
- 모든 철학자가 동시에 왼쪽 포크를 집어 들고, 오른쪽 포크를 기다리는 경우 발생.
- 포크를 기다리며 무한 대기 상태에 빠짐.
기아(Starvation):
- 특정 철학자가 계속해서 포크를 얻지 못해 식사를 시작하지 못하는 상황.
- 다른 철학자들이 반복적으로 포크를 먼저 사용하면서 자원을 독점.
활성화 지연(Livelock):
- 철학자들이 포크를 양보하거나 내려놓았다가 다시 집으려는 상황이 반복되며, 아무도 식사하지 못하는 상태.

철학자가 식사하는 모든 경우 분석

📌철학자들의 교착상태 원인과 해결

1. 교착상태 원인

환형 요청/대기(Circular Wait):
- 각 철학자가 특정 자원을 점유한 상태에서 다음 자원을 요청하며 대기.
- 모든 철학자가 동시에 동일한 상황에 처하면 환형 구조가 형성.
- 특징: 환형 대기는 스스로 인식하거나 해체할 수 없음.

2. 교착상태 해결

‘환형 대기’가 발생하지 않도록 설계:
- 방법:
  1. 규칙적인 자원 요청 순서 설정:
    - 예: 마지막 철학자는 오른쪽 포크를 먼저 요청.
    - 결과적으로 환형 요청 구조가 해체되거나 방지.
  2. 포크 사용 우선순위 부여:
    - 각 포크에 우선순위를 부여하여 철학자가 포크를 요청하는 순서를 명확히 함.

그림 설명

환형 요청 발생: 각 철학자가 왼쪽 포크를 소유하고 오른쪽 포크를 요청.
포크 충돌: 요청이 충돌하여 교착상태가 발생할 위험.
특정 철학자 우선 배정:
- 한 철학자가 먼저 두 개의 포크를 확보하여 식사.
- 해당 철학자가 식사를 끝내면, 나머지 철학자가 순차적으로 자원을 확보하여 교착상태 해소.
순환 요청 방지 규칙:
- 마지막 철학자가 오른쪽 포크를 먼저 요청함으로써 환형 요청 구조 제거.

📌식사하는 철학자와 컴퓨팅 시스템

1. 유사점

철학자 → 스레드
- 철학자는 각각 독립적으로 자원을 사용하려는 스레드를 의미.
포크 → 자원
- 철학자가 사용하려는 포크는 스레드가 필요로 하는 자원과 대응.
스파게티 → 스레드가 처리할 작업
- 스레드가 특정 작업(스파게티 처리)을 완료하기 위해 자원을 확보해야 함.

2. 교착 상태 시나리오

T1~T5 스레드와 자원
- T1~T5의 스레드는 각각 하나 이상의 자원을 요청.
- 이미 다른 스레드가 점유한 자원을 요청하며 대기하게 되어 환형 대기 상황 발생.
- 예시:
  - T1은 파일A를 점유하고 파일B를 요청.
  - T2는 파일B를 점유하고 프린터를 요청.
  - 이러한 순환적인 요청이 이어지며 교착 상태 형성.

3. 문제의 본질

컴퓨터 시스템에서 자원(파일, 프린터, 세마포, 뮤텍스 등)은 여러 스레드가 공유.
스레드가 특정 자원을 점유한 상태에서 다른 자원을 요청하며 무한 대기가 발생하는 것이 문제.

7.2 교착상태

📌컴퓨터 시스템에서의 교착 상태 정의

1. 교착 상태(Deadlock)란?

정의:
- 자원을 점유한 스레드들이 서로가 점유한 자원을 요청하며 무한히 대기하는 현상.
- 자원 요청과 점유가 서로 맞물리면서 더 이상 작업이 진행되지 않음.
발생 조건:
- 자원을 점유하고 추가로 다른 자원을 요청할 때 발생.
- 모든 자원이 사용 중일 때 스레드 간 대기 상태에 빠짐.

2. 교착 상태 발생 위치

멀티스레드 응용프로그램:
- 사용자가 작성한 멀티스레드 환경에서 주로 발생.
- 자원을 공유하는 응용프로그램에서 자주 목격됨.
운영체제 커널 내:
- 커널 수준에서 자원 관리 도중에도 발생 가능.
- 예: 파일, 프린터, 메모리 락 등.
일상적인 발생 가능성:
- 운영 체제는 교착 상태 방지에 많은 자원을 소비하지 않으므로, 종종 예방보다는 "최소화"나 "재시작" 전략을 선택.

3. 교착 상태 발생 시 영향

시간과 공간 낭비:
- 교착 상태를 막기 위해 미리 모든 가능성을 차단하려면 막대한 자원 소모 발생.
- 시스템이 특정 작업을 진행하지 못해 전체 작업 속도 저하.
대응 전략:
- 교착 상태가 발생하면:
  1. 시스템을 재시작.
  2. 일부 프로세스 강제 종료.

📌전형적인 멀티스레드 교착 상태 사례

1. 교착 상태의 전형적 발생 시나리오

스레드 간 자원 경쟁:
- 두 개의 스레드(thread1, thread2)가 서로 다른 락(Lock)을 점유하고, 동시에 상대가 점유한 락을 요청하며 대기.
- 락과 자원에 대한 경쟁이 있는 경우 교착 상태는 언제든 발생 가능.
다중 CPU 환경에서도 발생:
- 병렬 실행되는 스레드들이 동일한 자원을 점유하거나 요청할 때도 교착 상태가 발생.

2. 교착 상태가 발생하는 상황

thread1:
- LockA를 점유 후, LockB를 요청하고 대기.
thread2:
- LockB를 점유 후, LockA를 요청하고 대기.
결과:
- 두 스레드가 서로 대기 상태에 빠지며, 교착 상태 발생.

3. 코드 분석

pthread_mutex_lock():
- 스레드가 특정 락을 획득.
- 이미 점유된 락에 대해 요청하면 해당 락이 해제될 때까지 블로킹.
코드 흐름:

    void* thread1(void* a) {
        pthread_mutex_lock(&LockA); // LockA 획득
        pthread_mutex_lock(&LockB); // LockB 요청 → 대기 발생 가능 (교착 발생 가능)
        pthread_mutex_unlock(&LockB);
        pthread_mutex_unlock(&LockA);
    }
    
    void* thread2(void* a) {
        pthread_mutex_lock(&LockB); // LockB 획득
        pthread_mutex_lock(&LockA); // LockA 요청 → 대기 발생 가능 (교착 발생 가능)
        pthread_mutex_unlock(&LockA);
        pthread_mutex_unlock(&LockB);
    }

📌컴퓨터 시스템에 잠재된 교착 상태 유발 요인

1. 자원은 교착 상태의 발생지

컴퓨터 시스템에는 다양한 자원 존재:
- 소프트웨어 자원:
  - 뮤텍스, 스핀락, 세마포, 파일, 이터베이스, 파일 락 등.
- 하드웨어 자원:
  - 프린터, 메모리, 프로세서 등.
다수의 스레드 또는 프로세스가 동일 자원에 접근하려 할 때 충돌 발생 가능.

2. 자원과 스레드

스레드 간의 자원 경쟁:
- 각 스레드가 여러 자원을 동시에 필요로 하는 상황.
- 예를 들어, 하나의 스레드는 프린터와 파일 락을 동시에 요청하고, 다른 스레드도 동일한 자원을 요청하면 충돌 가능성 존재.

3. 자원과 운영체제

자원 할당 정책:
- 운영체제는 한 번에 하나씩 자원을 할당.
- 스레드가 필요한 모든 자원을 한 번에 요청 또는 할당받지 못하면 대기 상태 발생.
- 이로 인해 점유와 대기(Hold and Wait) 상태 형성.

4. 자원 비선점

비선점 정책:
- 이미 할당된 자원은 해당 스레드가 작업을 완료하고 자발적으로 반환하기 전까지 강제로 회수 불가.
- 운영체제는 자원을 점유한 스레드로부터 자원을 강제로 빼앗지 못함.

📌교착 상태 모델링

1. 자원 할당 그래프 (Resource Allocation Graph, RAG)

그래프의 요소
- 꼭지점(Vertex):
  - 스레드 (원): 시스템에서 실행 중인 스레드.
  - 자원 (사각형): 시스템에서 관리되는 자원.
- 간선(Edge):
  - 소유 관계: 자원이 스레드에 의해 점유됨.
  - 요청 관계: 스레드가 자원을 요청 중.
시스템 내 자원의 상태를 나타내는 방향성 그래프
- 컴퓨터 시스템에 실행 중인 전체 스레드와 자원의 개수 포함.
- 각 자원의 총 인스턴스 개수와 할당 가능 인스턴스 개수 표시.
- 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수.
- 각 스레드가 실행에 필요한 자원 유형 및 인스턴스 개수 포함.

2. 자원 할당 그래프를 통한 교착 상태 판단

교착 상태를 예방, 회피, 감지하기 위한 기본 도구.
알고리즘 개발에 사용:
- 자원 요청 및 할당을 관리하여 교착 상태 발생 여부를 미리 판단.
- 자원 사용 경로를 추적하여 교착 상태를 피할 수 있는 시스템 설계 가능.

📌자원 할당 그래프 사례

📌교착상태가 발생하지 않은 자원할당 그래프와 교착상태가 발생한 사례

1. 교착상태가 아닌 경우

환형 사이클 형성:
- T1, T2, T3 사이에서 자원에 대한 요청과 소유로 인해 환형 사이클이 형성됨.
진정한 교착상태가 아닌 이유:
- T5가 실행을 종료하면, T5가 소유하고 있던 파일 자원이 해제됨.
- 이 파일 자원은 T4가 요청했던 자원이므로 T4가 이를 소유할 수 있음.
교착 상태 해소 과정:
1. T4가 실행을 종료하면, T4가 소유하고 있던 프린터 자원이 해제됨.
2. 이로 인해, T2가 요청한 자원을 할당받을 수 있음.
3. T1, T2, T3 사이의 환형 사이클이 해소되면서 영구적인 교착 상태에 빠지지 않음.

요약:

T5와 T4가 각각 실행을 종료하고 자원을 반환하면서, T1, T2, T3 사이의 환형 사이클이 자연스럽게 풀리게 되어 시스템은 영구적인 교착 상태로 가지 않게 됨.

2. 교착상태가 발생한 사례

📌교착상태에 빠진 응용프로그램 사례

1. 교착 상태 발생 코드

deadlock.c 코드에서 다음 상황이 발생함:

worker1 스레드가 lock1을 획득한 후 2초 동안 멈춤. 이후 lock2를 요청하지만 대기 상태에 빠짐.
worker2 스레드는 반대로 lock2를 먼저 획득한 후 2초 동안 멈춤. 이후 lock1을 요청하며 대기 상태에 빠짐.

이 결과로 두 스레드가 각각 서로가 보유하고 있는 락을 요청하며 무한 대기 상태에 빠져 교착 상태가 발생한다.

2. 실험 코드의 결과

코드를 컴파일하고 실행하면 lock1, lock2를 각각 점유하는 로그가 출력된 후 프로그램이 멈춘다. 이는 교착 상태에 빠졌음을 의미한다.

3. 교착 상태 발생 과정

worker1과 worker2가 각각 lock1과 lock2를 점유하고, 서로 상대의 락을 요청하면서 교착 상태가 발생한다.
아래 방향성 그래프는 교착 상태의 원형 대기를 시각적으로 나타냄:
- T1 → Lock1 → Lock2 → T2 → Lock2 → Lock1...

7.3 교착상태 해결

📌교착상태가 발생하는 4가지 필요충분 조건

코프만 조건(Coffman condition)

상호 배제(Mutual Exclusion)
- 시스템 내의 자원이 한 번에 하나의 스레드만 접근 가능.
- 공유 자원에 대해 동시 접근을 방지하기 위해 락(lock) 메커니즘이 사용되며, 이는 자원의 배타적 소유를 야기.
소유하면서 대기(Hold & Wait)
- 스레드가 이미 자원을 소유한 상태에서 추가 자원을 요청하며 대기.
- 자원을 반환하지 않고 다른 자원을 기다리는 행동이 교착상태를 유발할 가능성을 증가.
강제 자원 반환 불가(No Preemption)
- 스레드가 보유 중인 자원을 다른 스레드가 강제로 빼앗을 수 없음.
- 보유한 자원을 자발적으로 반환하기 전까지 다른 스레드가 해당 자원을 사용하지 못함.
환형 대기(Circular Wait)
- 여러 스레드가 자원을 순환적으로 요청하며 대기.
- 예: 스레드 T1이 자원 R2를 요청하고, T2는 R3를 요청하며 R2를 보유, T3는 R1을 요청하며 R3를 보유, 그리고 T1은 R1을 보유 → 원형 대기가 형성.

✅ 4가지 조건 중 하나라도 성립되지 않으면, 교착상태 발생하지 않음

📌교착상태 해결 방법:

교착상태 예방 (Prevention)
- Coffman 조건 중 하나 이상이 성립하지 않도록 시스템을 설계.
- 조건 별 해결 방법:
  - 상호 배제: 자원의 동시 사용 가능하도록 설계.
  - 소유하면서 대기 방지: 자원을 요청하기 전에 필요한 모든 자원을 할당받도록 요구.
  - 강제 자원 반환: 자원이 강제로 회수될 수 있도록 허용.
  - 환형 대기 방지: 자원 요청 순서를 정의하여 환형 요청이 발생하지 않도록 설계.
교착상태 회피 (Avoidance)
- 시스템이 교착상태로 진입하지 않도록 자원 할당 전에 교착 가능성을 검사.
- 안전 상태와 불안전 상태로 시스템 상태를 분류.
- 자원 할당 시 안전 상태에서만 자원 할당.
- 대표 알고리즘: Banker’s Algorithm.
교착상태 감지 및 복구 (Detection and Recovery)
- 교착상태를 감지하는 프로그램을 백그라운드에서 실행하여 교착상태를 식별.
- 교착상태 발생 시 복구:
  - 특정 스레드 강제 종료.
  - 자원을 강제로 회수.
교착상태 무시 (Ignore)
- 교착상태가 없다고 가정하고 대응하지 않음.
- 사용자가 이상을 느끼면 시스템 재시작.
- 대표적 사례: 리눅스, 윈도우 등의 대다수 운영체제에서 사용.
- Ostrich Algorithm: 문제가 발생하지 않을 가능성이 더 크다고 판단하여 대응하지 않는 전략.

📌교착상태 예방 (Deadlock Prevention):

코프만의 4가지 조건 중 최소 하나를 성립하지 못하게 하여 교착상태를 방지한다.

1. 상호 배제 (Mutual Exclusion) 조건

조건: 동시에 2개 이상의 스레드가 자원을 공유할 수 없음.
해결 방법: 상호 배제 없애기.
- 모든 자원이 동시에 여러 스레드에서 사용 가능하도록 설계.
- 제약: 컴퓨터 시스템에서 대부분의 자원은 상호 배제를 요구하므로 이 방법은 현실적으로 적용 불가.

2. 소유하면서 대기 (Hold and Wait) 조건

조건: 자원을 소유한 스레드가 다른 자원을 요청하며 기다림.
해결 방법: 스레드가 자원을 기다리지 않도록 설계.
- 방법 1: 필요 자원을 모두 한 번에 요청.
  - 장점: 대기 상황 발생 방지.
  - 단점: 자원 활용률 저하, 필요하지 않은 자원도 점유.
- 방법 2: 새로운 자원을 요청 시 기존에 점유한 자원을 반납 후 다시 요청.

3. 강제 자원 반환 불가 (No Pre-emption) 조건

조건: 할당된 자원을 강제로 회수할 수 없음.
해결 방법: 자원 선점 허용.
- 현재 자원을 점유 중인 스레드의 작업을 중단하고 자원을 회수.
- 제약: 구현 복잡도 증가, 추가 오버헤드 발생.

4. 환형 대기 (Circular Wait) 조건

조건: 자원을 기다리는 스레드들이 서로 원형으로 연결되어 무한 대기.
해결 방법: 자원 요청 순서를 정의하여 환형 대기 방지.
- 모든 자원에 번호를 부여하고, 스레드가 자원을 요청할 때 낮은 번호의 자원부터 순서대로 요청.

📌환형 대기가 발생하지 않도록 번호 순으로 자원 할당

📌교착상태 회피

1. 기본 원칙

자원 할당 시, 미래에 환형 대기가 발생할 가능성이 있다고 판단되면 자원 할당을 하지 않음.
교착상태 회피의 대표적인 방법으로 Banker’s Algorithm 사용.

2. Banker’s Algorithm

개발자: Edsger Dijkstra.
기본 개념:
- 자원 할당 전에 시스템이 안전한 상태인지 판단.
- 은행에서 대출 과정을 모델링하여 고안된 알고리즘.

3. 안전한 상태 (Safe State)와 불안전한 상태 (Unsafe State)

안전한 상태:
- 현재 프로세스들이 특정 실행 순서로 실행을 완료할 수 있는 상태.
- 모든 프로세스가 필요한 자원을 획득해 실행을 완료할 수 있음.
불안전한 상태:
- 특정 순서로 실행할 수 없으며, 교착상태가 발생할 가능성이 있는 상태.

4. 알고리즘 작동 방식

자원 요청 과정:
- 각 프로세스는 실행 시작 전에 필요한 자원의 총량을 운영체제에 알림.
- 자원을 요청할 때마다 시스템이 해당 요청을 처리해도 안전한 상태를 유지하는지 확인.
- 안전한 상태일 경우에만 자원 할당.
검증 과정:
- 시스템은 현재 자원 상태와 요청 상황을 시뮬레이션하여 모든 프로세스가 실행을 완료할 수 있는지 판단.
- 안전한 순서가 존재하면 자원 할당, 그렇지 않으면 요청 거절.

5. 한계 및 비현실성

자원 수의 사전 정의:
- 모든 프로세스가 실행에 필요한 자원의 개수를 사전에 명확히 정의해야 함.
- 실제 시스템에서는 프로세스의 요구 자원이 실행 중에 동적으로 변경될 수 있음.
오버헤드:
- 자원 상태를 지속적으로 계산하므로, 계산 비용 증가.
적용 어려움:
- 프로세스와 자원의 개수가 많아질수록 알고리즘의 복잡성이 급격히 증가.

📌교착상태 감지 및 복구

교착상태 감지

백그라운드 감지 프로그램 백그라운드에서 교착상태를 감지하는 프로그램이 실행된다. 시스템 내의 자원 할당 그래프를 분석하여 교착상태를 판단한다.

교착상태 감지 후 복구 방법

자원 강제 선점 (Preemption)
- 교착상태에 빠진 스레드 중 하나가 보유한 자원을 강제로 빼앗아 다른 스레드에게 할당한다.
- 선점된 스레드는 다시 자원을 요청해야 하므로 시스템의 상태가 변화한다.
롤백 (Rollback)
- 교착상태가 발생할 가능성이 있는 경우, 각 스레드의 상태를 주기적으로 저장한다.
- 교착상태가 감지되면 스레드를 이전 상태로 복원하여 교착상태를 해소한다.
- 하지만 롤백은 시간과 메모리 공간에 대한 비용이 크므로 잘 사용되지 않는다.
스레드 강제 종료 (Kill Process)
- 교착상태에 빠진 스레드 중 하나를 선택하여 강제로 종료시킨다.
- 가장 간단하면서도 효과적인 방법이다.
- 그러나 종료된 스레드가 처리하던 작업이 손실될 수 있으므로, 신중히 사용해야 한다.

📌교착상태 무시: 타조(Ostrich) 알고리즘

교착상태를 해결할 필요가 있을까?

교착상태에 대한 통계:
- 교착상태는 드물게 발생하며, 시스템에 따라 1년에 한 번 또는 10년에 한 번 발생할 수 있다.
교착상태의 특성:
- 교착상태는 반드시 발생할 수 있다.
- 그러나 발생 가능성이 극히 적은 경우, 이를 회피하기 위해 드는 비용이 더 클 수 있다.

타조 알고리즘

개념:
- "모래에 머리를 박는 타조처럼 문제를 무시한다."
- 시스템이 교착상태를 감지하거나 처리하지 않도록 설계한다.
사용 환경:
- Unix, Windows와 같은 현대 운영체제 대부분에서 사용된다.

주의 사항

타조 알고리즘이 적합하지 않은 경우:
- 핵 시스템, 비행기, 미사일 시스템 등 하드 리얼타임(hard real-time) 시스템에서는 치명적인 결과를 초래할 수 있다.
- 예를 들어, 이러한 시스템에서는 시스템 재시작이나 작업 중단이 치명적인 결과를 가져올 수 있으므로, 교착상태 감지 및 회피가 필수적이다.

박소미

이전 포스트

[운영체제] Ch6 스레드 동기화

다음 포스트