* 이 글은 학부생 시절 개인 Notion에 작성했던 강의 필기 노트를 Velog에 옮긴 글입니다.
📗: 운영체제 제10판 | Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 저/박민규 역 | 퍼스트북
교착 상태란?
프로세스가 한 자원을 점유하고 봉쇄되고, 다른 프로세스가 이 자원을 획득하기 위해 요청 후 기다린다면 두 프로세스는 교착 상태에 있다고 함
시스템 모델
시스템의 자원은 다수의 유형으로 분할되며, 각 자원의 유형은 동등한 다수의 인스턴스들로 구성됨
자원 유형의 예로는 메모리 공간, CPU 주기, 파일, 입/출력장치(프린터,DVD 드라이브 등) 등
프로세스는 다음 순서로만 자원을 사용한다.
- 요청(request): 요청이 즉시 허용되지 않으면(예를 들어, 자원이 다른 프로세스에 의해 사용될 경우) 요청 프로세스는 자원을 얻을 때까지 대기
- 사용(use): 프로세스는 자원에 대해 작업을 수행
- 방출(release): 프로세스가 자원을 방출
다중 스레드 응용에서의 교착 상태
교착상태는 시스템 콜(자원 요청, 해제), 동기화를 위한 락킹 등에 의해서 발생
다중 스레드 응용에서 뮤텍스락, 세마포 등을 사용한 동기화 시 교착 상태의 가능성을 고려해야 함
Ex) 은행 계좌 교착 상태
트랜잭션 1,2가 병행 실행하면…?
- 트랜잭션 1은 계좌 A에서 계좌 B로 5만원 이체
- 트랜잭션 2는 계좌B에서 계좌 A로 10만원 이체
교착 상태 특징
필요조건
교착 상태는 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생
- 상호 배제: 한 번에 오직 한 프로세스만이 한 자원을 사용해야 함
- 점유하며 대기: 최소한 하나의 자원을 점유한 프로세스가 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 대기해야 함
- 비선점: 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 그 프로세스에 의해 자발적으로만 방출될 수 있음
- 순환 대기: 대기하고 있는 프로세스의 집합에서 P0은 P1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기하고,P2,…P(n-1)은 Pn이 점유한 자원을 대기하며, Pn은 P0가 점유한 자원을 대기함
자원 할당 그래프
정점 V 유형
- P={P1,P2,…,Pn}, 시스템 내의 모든 활성 프로세스 집합
- R={R1,R2,…,Rm}, 시스템 내의 모든 자원 유형의 집합
방향 간선 유형
- P(i)→R(j), 프로세스 P(i)가 자원 유형 R(j)의 인스턴스를 하나 요청
- R(j)→P(k), 자원 유형 R(j)의 한 인스턴스가 프로세스 P(k)에 할당
교착 상태를 가지는 자원 할당 그래프
그래프가 사이클을 포함하지 않으면 시스템은 교착 상태가 아니다. 반면, 그래프가 사이클을 포함하면 교착 상태가 존재할 수 있다.
만일 각 자원 유형이 정확하게 하나의 인스턴스만을 가지면, 사이클은 교착 상태를 암시한다.
각 자원 유형이 여러개의 인스턴스를 가지면. 사이클이 반드시 교착 상태를 의미하지는 않음
교착 상태 예방
교착 상태 예방 알고리즘은 요청 방법을 제약하여 교착 상태를 예방함.
교착 상태를 발생시키는 네 가지 조건 중에서 최소한 하나가 성립하지 않도록 보장
이런식으로 예방할 때, 장치의 이용률이 저하되고 시스템 처리율이 감소할 수 있다.
상호배제
- 공유 가능한 자원들은 배타적인 접근을 요구하지 않아 교착 상태와 관련 없음(Ex.읽기 전용 파일)
- 공유 불가 자원에 대해서는 상호 배제 조건이 반드시 성립해야 함(Ex. 프린터)
→ 일반적으로 상호 배제 조건을 거부함으로써 교착 상태를 예방하는 것은 불가능
점유하며 대기
프로세스가 자원을 요청할 때는, 다른 자원들을 점유하지 않을 것을 반드시 보장해야한다.
방법들
- 각 프로세스가 실행되기 전에 사용되는 모든 자원을 요청하고 모두 할당 받을 것을 요구
- 다른 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용
단점
- 많은 자원이 할당된 후 오랜 기단동안 사용되지 않기 때문에 자원의 이용도가 낮음
- 기아 상태 유발 가능성
비선점
이미 할당된 자원이 선점되지 않아야 한다는 조건이 성립되지 않도록 보장
- 만일 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면, 현재 점유하고 있는 모든 자원들이 선점. 즉, 현재 점유하고 있는 자원들을 방출
- 선점된 자원들은 기다리고 있는 프로세스 자원들의 리스트에 추가
- 자원이 선점된 프로세스는 자신이 요청하고 있는 새로운 자원은 물론 이미 점유했던 옛 자원들을 다시 획득할 수 있을 때에만 다시 시작
순환 대기
순환 대기 조건이 성립되지 않도록 모든 자원 유형들에게 전체적인 순서를 부여
각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구
교착 상태 회피
교착 상태 회피 알고리즘은 시스템에 순환 대기 상황이 발생하지 않도록 자원 할당 상태를 검사함
자원 할당 상태는 가용 자원의 수, 할당된 자원의 수 그리고 프로세스들의 최대 요구 수에 의해 정의
안전 상태
시스템이 모든 프로세스들의 안전 순서를 찾을 수 있다면 시스템은 안전
시스템이 안전 상태 → 교착 상태 아님
시스템이 불안전 상태 → 교착 상태 가능성
자원 할당 그래프 알고리즘
단일 인스턴스의 자원 유형인 경우, 교착 상태 회피를 위해 자원 할당 그래프를 변형하여
예약 간선을 새로 도입
- 예약 간선 P(i) → R(j)는 P(i)가 미래에 자원 R(j)를 요청할 것이라는 의미
- 점선 화살표로 표시
- 프로세스 P(i)가 자원 R(j)를 요청하면, 예약 간선 P(i) → R(j)는 요청 간선으로 변환
- P(i)가 자원 R(j)를 방출할 때, 할당 간선 R(j)→P(i)는 예약 간선 P(i) → R(j)로 다시 변환
시스템에서 자원이 반드시 미리 예약되어야 함
- 프로세스 P(i)가 실행되기 전, 프로세스의 모든 예약 간선들이 자원 할당 그래프에 표시되어야 함
알고리즘
- P(i)가 자원 R(j)를 요청하는 경우를 가정
- 요청 간선을 할당 간선으로 변환해도 사이클이 발생하지 않으면 요청을 수락
Ex) P2가 R2를 요청하면?
→ R2를 할당한 경우
할당할 수 없다! 왜냐하면, 할당할 경우 그래프에 사이클이 생기기 때문이다. 따라서 요청도 수락할 수 없음
은행원 알고리즘
다수의 인스턴스를 갖는 자원 유형인 경우 적용
각 프로세스는 필요한 자원의 최대 개수를 자원 종류마다 미리 신고해야 함.
프로세스가 자원들을 요청하면 시스템은 요청 수락 시 시스템이 계속 안전 상태에 머무르게 되는지 여부를 판단한다.
계속 안전하다면 그 요청을 수락하고, 불안전하면 요청은 수락되지 않은 채 다른 프로세스가 끝날 때 까지 기다리게 된다.
알고리즘의 자료 구조
n: 프로세스의 수, m: 자원 종류의 수 일때
- Available: 각 종류별로 가용한 자원의 개수를 나타내는 벡터로 크기가 m Available[j]=k 라면 현재 R(j)를 k개 사용할 수 있다는 의미
- Max: 각 프로세스가 최대로 필요로 하는 자원의 개수를 나타내는 행렬로 크기가 n*m Max[i,j]=k 라면 P(i)가 R(j)를 최대 k개까지 요청할 수 있음을 의미
- Allocation: 각 프로세스에 현재 할당된 자원의 개수를 나타내는 행렬로 크기가 n*m Allocation[i,j]=k라면 현재 P(i)가 R(j)를 k개 사용중임을 의미
- Need: 각 프로세스가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬로 크기가 n*m Need[i,j]=k라면 P(i)가 향후 R(j)를 k개까지 더 요청할 수 있음을 의미 Need[i,j]=Max[i,j]-Allocation[i,j]
안전성 알고리즘
시스템이 안전한지 알아내는 알고리즘
-
Work=Available로 초기화. i=0, 1, …, n-1에 대해서 Finish[i]=false로 초기화
(Work, Finish는 크기가 m과 n인 벡터)
-
아래 두 조건을 만족시키는 i 값을 탐색
- Finish[i]==false
- Need(i) ≤ Work
만족하는 i 값을 찾을 수 없다면 step4로 이동
-
Work=Work+Allocation(i)
Finish[i]=true
수행 후 step2로 이동
-
모든 i 값에 대해 Finish[i]==true이면 이 시스템은 안전 상태에 있다.
자원 요청 알고리즘
Request(i)는 프로세스 P(i)의 요청 벡터. Request(i)[j]==k라면 P(i)가 R(j)를 K개 요청하고 있음을 의미
-
Request(i) ≤ Need(i) 이면 step2로 이동, 아니면 시스템에 있는 개수보다 더 많이 요청했으므로 오류로 처리
-
Request(i) ≤ Available 이면 step3로 이동, 아니면 요청한 자원이 당장은 없으므로 P(i)는 대기함
-
마치 시스템이 P(i)에게 자원을 할당해준 것처럼 시스템 상태 정보를 아래처럼 변경해본다.
Available=Available-Request(i)
Allocation(i)=Allocation(i)+Request(i)
Need(i)=Need(i)-Request(i)
이렇게 변경한 상태가 안전하다면 P(i)에게 자원을 할당, 불안전하다면 정보를 원상태로 복원하고 P(i)는 대기
은행원 알고리즘 적용 예
시스템에는 A 10개, B 5개, C 7개의 자원이 있다. 아래 그림은 시스템의 현재 상태를 나타낸다.
Need 행렬의 값은 Max-Allocation로 얻을 수 있다.
- 이 시스템은 안전할까?
- P1의 Need 1 2 2 ≤ Work 3 3 2 이므로 Work= 3 3 2 + 2 0 0 (Allocation) = 5 3 2, Finish[1]=true
- P3의 Need 0 1 1 ≤ Work 5 3 2 이므로 Work= 5 3 2 + 2 1 1 (Allocation) = 7 4 3, Finish[3]=true
- P4의 Need 4 3 1 ≤ Work 7 4 3 이므로 Work= 7 4 3 + 0 0 2 (Allocation) = 7 4 5, Finish[4]=true
- P0의 Need 7 4 3 ≤ Work 7 4 5 이므로 Work= 7 4 5 + 0 1 0(Allocation) = 7 5 5, Finish[0]=true
- P2의 Need 6 0 0 ≤ Work 7 5 5 이므로 Work= 7 5 5 + 3 0 2 (Allocation) = 10 5 7, Finish[2]=true
모든 i 값에 대해 Finish[i]==true이므로 이 시스템은 안전 상태에 있다.
- P1이 (1,0,2)을 요청하면?
- Request 1 0 2 ≤ Need 1 2 2 을 만족함
- Request 1 0 2 ≤ Available 3 3 2 을 만족함
- 자원을 할당해준 것처럼 상태 정보 변경
- 안전성 여부 판단 → <P1, P3, P4, P0, P2> 순서로 안전
- 요청을 들어줌
교착 상태 탐지
교착 상태 발생이 가능한 시스템에서는 다음 알고리즘들을 지원해야 함
- 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
- 교착 상태로부터 회복하는 알고리즘
각 자원 유형이 한 개씩 있는 경우
- 대기 그래프 사용
- 자원 할당 그래프로부터 자원 유형의 노드를 제거
- P(i)→P(j)의 간선은 는 프로세스 P(j)가 가진 자원을 P(i)가 요청하여 기다리는 것을 의미함
- 주기적으로 그래프에서 사이클을 조사하여 교착 상태 탐지(사이클 탐지 연산은 O(n^2) 요구)
(a) 자원 할당 그래프 (b) 대기 그래프
각 유형의 자원을 여러개 가진 경우
은행원 알고리즘과 같이 시시각각 그 내용이 달라지는 자료 구조를 사용 O(m*n^2)
- 가용 Available: 각 종류의 자원이 현재 몇 개가 가용한지를 나타내는 벡터로 크기가 m
- 할당 Allocation: 각 프로세스에게 현재 할당되어 있는 자원의 개수를 나타내는 행렬로 크기가 n*m
- 요청 Request: 각 프로세스가 현재 요청중인 자원의 개수를 나타내는 행렬로 크기가 n*m
탐지 알고리즘
-
Work=Available로 초기화. i=0, 1, …, n-1에 대해서 Allocation≠0이면 Finish[i]=false, 아니면 Finish[i]=true (Work, Finish는 크기가 m과 n인 벡터)
-
아래 두 조건을 만족시키는 i 값을 탐색
- Finish[i]==false
- Request(i) ≤ Work
만족하는 i 값을 찾을 수 없다면 step4로 이동
-
Work=Work+Allocation(i)
Finish[i]=true
수행 후 step2로 이동
-
어떤 i 값에 대해 Finish[i]==flase이면 P(i)가 교착 상태(즉, 시스템이 교착 상태)
Ex) 교착 상태에 빠지는 예
알고리즘에 따라 탐지해보면…
- P0의 Request≤Work 이므로 Work= 0 0 0 + 0 1 0 = 0 1 0
- Request≤Work를 만족하는 프로세스 없음. 따라서 P1, P2, P3과 P4가 교착 상태에 연루
탐지 알고리즘 사용
탐지 알고리즘의 수행 빈도는 다음을 고려
- 교착 상태가 얼마나 자주 일어나는가?
- 교착 상태가 일어나면 통상 몇 개의 프로세스가 연루되는가?
프로세스의 요청이 즉시 만족되지 않을 때마다 수행하면 교착상태에 연루된 프로세스들 뿐 아니라 교착 상태를 야기한 장본인 프로세스도 탐지 가능
→ 자원을 요청할 때마다 탐지 알고리즘을 돌리면 너무 오버헤드가 큼
탐지 알고리즘을 가끔씩만 돌리면 한꺼번에 여러 개의 사이클이 탐지되어 어느 프로세스가 최종적으로 교착상태를 야기한 장본인인지 알아내기 어려움
교착 상태 회복
프로세스 종료
프로세스를 중지시킴으로써 교착 상태를 제거
- 교착 상태 프로세스를 모두 중지
- 교착 상태가 제거될 때까지 한 프로세스씩 중지
부분 종료 방식의 경우 다음을 고려하여 중지될 프로세스 선택
- 프로세스의 우선순위
- 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는데 더 필요한 시간
- 프로세스가 사용한 자원 유형과 수 (예를 들어, 자원들을 선점하기가 단순한지)
- 프로세스가 종료하기 위해 더 필요한 자원의 수
- 얼마나 많은 수의 프로세스가 종료되어야 하는지
- 프로세스가 대화형인지 일괄 처리 인지
자원 선점
자원 선점을 이용해 교착 상태를 제거하려면 다음을 고려
- 희생자 선택
- 어느 자원과 어느 프로세스들이 선점될 것인가를 결정
- 비용을 최소화하기 위해 선점의 순서를 결정
- 후퇴
- 중지될 프로세스를 안전한 상태로 후퇴시키고, 그 상태로부터 다시 시작
- 안전 상태가 어떤 것인지를 결정하기 어렵기 때문에, 가장 단순한 해결안은 프로세스를 중지시키고 재시작
- 기아 상태
- 동일한 프로세스가 항상 희생자로 선택되어 자신의 태스크를 결코 완료하지 못하는 기아 상태가 발생하는 것을 방지해야함
- 일반적인 해결 방법은 비용 요소에 후퇴의 횟수를 포함
