교착 상태
deadlock. 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상
식사하는 철학자 문제
- 계속 생각을 하다 왼쪽 포크가 사용 가능하면 집어든다
- 계속 생각을 하다 오른쪽 포크가 사용 가능하면 집어든다
- 왼쪽과 오른쪽 포크 모두 집어들면 정해진 시간동안 식사를 한다
- 식사 시간이 끝나면 오른쪽 포크를 내려놓는다
- 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다
- 다시 1번부터 반복
모든 철학자가 왼쪽 포크를 들면 모두가 오른쪽 포크를 들 수 없음
→ 모든 철학자가 동시에 포크를 들면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황 발생.
- 철학자 : 프로세스 또는 스레드
- 포크 : 자원이자 임계구역
- 생각하는 행위 : 자원을 기다리는 것
💡 뮤텍스락에서의 교착 상태
lock1 = true; //프로세스1 while (lock2 == true) ; //임계구역 작업 lock1 = false; ------------------------ lock2 = true; //프로세스2 while (lock1 == true) ; //임계구역 작업 lock2 = false;
자원 할당 그래프
resource-allocation graph. 어떤 프로세스가 어떤 자원을 사용/기다리고 있는지 표현
- 프로세스는 원으로, 자원 종류는 사각형으로 표현
- 사용할 수 이쓴 자원의 개수는 자원 사각형 내 점으로 표현
- 프로세스가 어떤 자원을 할당받아 사용중이라면 자원 → 프로세스. 화살표 표시
- 프로세스가 어떤 자원을 기다린다면 프로세스 → 자원. 화살표 표시
- 식사하는 철학자 문제의 자원할당 그래프
교착 상태 발생 조건
- 상호 배제mutual exclusion
한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때 - 점유와 대기hold and wait
자원을 할당받은 상태에서 다른 자원을 할당받기를 기다릴 때 - 비선점nonpreemptive
어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못함 - 원형 대기circular wait
자원 할당 그래프가 원의 형태로 그려질 때
교착 상태 해결 방법
교착 상태 예방
case 1. 자원의 상호 배제 제거
= 모든 자원을 공유한다... 현실적으로 무리
case 2. 점유와 대기 제거
특정 프로세스에 모든 자원을 할당 또는 아예 할당하지 않음
→ 자원의 활용률이 낮아짐. 많은 자원을 필요로 하는 프로세스의 기아현상 발생가능
case 3. 비선점 제거
자원을 이용중인 프로세스로부터 해당 자원 뺏을 수 있음(ex 한 프로세스가 CPU이용하다가 일정 시간 지나면 작업이 안끝났어도 다른 프로세스가 CPU할당 받아 사용 가능. 범용성은 떨어짐
case 4. 원형 대기 제거
모든 자원에 번호를 붙이고, 오름차순으로 자원 할당.
모든 컴퓨터 시스템 내의 수많은 자원에 번호를 붙이는건 간단하지않음. 각 자원에 어떤 번호를 붙이느냐에 따라 특정 자원의 활용률 떨어질 수 있음.
교착 상태 회피
교착 상태가 발생하지 않을 정도로만 조심히 자원 할당. 항시 안전상태 유지하도록 자원 할당
→ 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주
- 안전 순서열safe sequence
교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서- 안전 상태safe state
교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원 할당받고 종료될 수 있는 상태. 안전 순서열대로 자원 배분
- 불안전 상태unsafe state
교착 상태가 발생할 수도 있는 상황. 안전 순서열X
교착 상태 검출 후 회복
교착 상태 발생을 인정하고 사후 조치
프로세스들이 자원을 요구할 때마다 그때그때 할당하여 교착 발생 여부 주기적 확인
- 선점을 통한 회복
교착 상태가 해결될 때까지 다른 프로세스부터 자원 빼앗아 한 프로세스씩 자원 몰아줌 - 프로세스 강제 종료를 통한 회복
1) 교착 상태에 놓인 프로세스 모두 강제 종료
: 한 번에 해결 가능하지만, 많은 프로세스들이 작업 내용 잃을 수 있음
2) 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료
: 작업 내역 잃는 프로세스 줄어듦. 교착 상태 여부 확인에서 오버헤드 야기💡 타조 알고리즘ostrich algorithm : 드물게 발생하는 잠재적 문제를 무시로 대처
