All
교착상태
프로세스의 자원 사용 절차
운영체제에서 프로세스는 자원을 사용할 때 아래와 같은 순서를 따른다.
1.
요구 (Request): 자원을 요청한다.
2.
사용 (Use): 자원을 할당받고 실제로 사용한다.
3.
해제 (Release): 사용이 끝난 자원을 반환한다.
이자원을 요구했지만 가용한 자원이 없다면 프로세스는 자원이 할당될 때까지 대기 상태에 들어간다.
교착상태란?
여러개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어 어느쪽도 영원히 진행하지 못하는 상태
예시 상황
•
프로세스 1: 자원 A를 획득한 후 자원 B를 요구하며 대기
•
프로세스 2: 자원 B를 획득한 후 자원 A를 요구하며 대기
두 프로세스는 서로의 자원을 기다리기 때문에 진행이 불가능한 상태에 빠지게 된다.
교착상태와 기아상태 차이
교착상태 | 기아상태 | |
정의 | 여러 프로세스가 서로 자원을 점유한 채로 무한 대기 | 특정 프로세스가 자원을 지속적으로 할당받지 못해 무기한 대기 |
원인 | 자원 점유 간의 순환 구조 | 우선순위나 자원 배분 정책 |
영향 | 관련된 모든 프로세스가 멈춘다 | 특정 프로세스만 멈춘다 |
교착상태의 특성
교착상태는 아래 네 가지 조건이 동시에 성립할 때 발생할 수 있다.
1. 상호배제 (Mutual Exclusion)
•
자원은 한 번에 하나의 프로세스만 사용할 수 있어야 함
•
공유 불가능한 자원일 경우 이 조건이 성립
•
예: 프린터, 파일 잠금 등
2. 점유대기 (Hold and Wait)
•
프로세스가 하나 이상의 자원을 점유한 상태에서, 다른 자원을 추가로 요청하면서 대기하는 상태
•
이미 점유 중인 자원은 해제하지 않고 대기
3. 비선점 (No Preemption)
•
한 번 할당된 자원은 프로세스가 자발적으로 해제하기 전까지 강제로 회수할 수 없음
•
다른 프로세스가 해당 자원을 사용하려면 기다릴 수밖에 없음
4. 환형대기 (Circular Wait)
•
둘 이상의 프로세스가 원형 구조로 자원을 기다리는 상태
•
예를 들어 P1이 P2의 자원을 기다리고, P2가 P3의 자원을 기다리며, P3가 다시 P1의 자원을 기다리는 식
이 네 가지 조건이 모두 충족될 경우 교착상태가 발생할 수 있으며, 하나라도 제거되면 교착상태는 발생하지 않음
자원 할당 그래프
프로세스와 자원의 상태를 시각적으로 표현하여 교착상태의 가능성을 판단하는 데 사용
그래프에서 사이클이 있는지 확인을 통해 교착상태 발생 가능성 여부를 직관적으로 판단 가능
기본 구성
자원 할당 그래프는 다음과 같은 요소들로 구성된다:
•
정점 (Vertex)
◦
P1, P2, ..., Pn: 프로세스(Process)
◦
R1, R2, ..., Rm: 자원(Resource)
•
간선 (Edge)
◦
요구 간선 (Request Edge): Pi → Rj프로세스 Pi가 자원 Rj를 요청하고 있음
◦
할당 간선 (Assignment Edge): Rj → Pi자원 Rj가 프로세스 Pi에 할당된 상태
예시 1: 교착상태가 아닌 경우
•
P1은 R1을 요청하고 있고, R1은 P2에게 할당되어 있음
•
P3는 R2를 요청하고 있음
•
사이클이 없음 → 교착상태 아님
예시 2: 교착상태가 발생한 경우
•
P1은 R1을 요청하고 있고, R1은 P2에게 할당되어 있음
•
P2는 R2를 요청하고 있고, R2는 P1에게 할당되어 있음
•
사이클이 존재 → 교착상태 발생
핵심 판단 기준
•
사이클 없음: 교착상태 발생 가능성 없음
•
사이클 존재:
◦
자원이 하나씩만 존재하는 경우 → 반드시 교착상태 발생
◦
자원이 여러 개 존재하는 경우 → 사이클이 있어도 교착상태가 아닐 수 있음
◦
교착상태 아닌 예
◦
교착상태의 처리기법
교착상태를 해결하기 위해 예방, 회피, 탐지 및 복구 세가지 방법이 존재
교착상태 예방
교착상태의 4가지 발생 조건 중 최소 하나를 사전에 차단하여 교착상태를 예방하는 방법
1. 상호배제(Mutual Exclusion) 조건 제거
자원이 한 번에 하나의 프로세스에게만 할당되어야 한다는 조건을 없앰
•
공유 가능한 자원의 경우에는 상호배제 필요 없음 예: 읽기 전용 파일, 캐시 데이터 등은 여러 프로세스가 동시에 접근 가능
•
하지만 대부분의 물리 자원(프린터, 파일 쓰기 등)은 공유가 불가능해, 이 조건을 완전히 제거하는 것은 현실적으로 어려움
2. 점유대기(Hold and Wait) 조건 제거
프로세스가 이미 점유한 자원을 유지한 채로 추가 자원을 요구하는 상황을 막는 것
방법 1: 필요한 자원을 한 번에 모두 요청
•
프로세스 시작 시 모든 자원을 한꺼번에 요청
•
교착상태는 방지되지만, 자원의 낭비와 기아상태 가능성
방법 2: 새로운 자원을 요청할 때 기존 자원을 반환
•
실행 도중 새로운 자원이 필요할 경우 현재 점유한 자원을 모두 반납한 뒤 재요청
•
자원 회수 → 모든 자원 가용 상태로 만들고 → 재요청
•
단점: 자원 해제 후 재할당 과정이 반복되면서 오버헤드 발생, 일부 자원은 중간에 해제할 수 없어 적용 불가
3. 비선점(No Preemption) 조건 제거
프로세스가 점유한 자원을 강제로 회수할 수 있도록 허용
•
어떤 프로세스가 자원을 점유 중일 때, 다른 프로세스가 해당 자원을 요청하면 운영체제가 자원을 회수
•
나중에 자원이 다시 가용해지면 원래의 프로세스는 대기 후 다시 자원을 요청하여 재시작할 수 있음
4. 환형대기(Circular Wait) 조건 제거
여러 프로세스가 자원을 점유하고 다음 자원을 요구하면서 원형 구조를 만드는 상황을 방지
자원에 일련번호를 부여하고 항상 정해진 순서대로 자원을 요청하게 만듦
방법 1: 오름차순 자원 요청 방식
•
모든 자원에 고유한 일련번호 f(R) 부여
•
프로세스는 자원을 요청할 때, 가장 마지막으로 점유한 자원보다 더 큰 번호의 자원만 요청 가능
예시:
•
프로세스가 자원 R3(번호 3)를 점유한 상태라면, 이후에는 R4, R5 같은 더 큰 번호의 자원만 요청 가능
•
R2처럼 더 작은 번호의 자원은 요청 불가
→ 자원 요청 순서가 항상 단방향이므로, 사이클 형성이 불가능
방법 2: 작은 번호 자원만 점유 허용 방식
•
프로세스는 자원을 요청할 때, 자신이 점유한 자원의 일련번호보다 작은 번호 자원은 미리 해제한 후 요청
예시:
•
R3을 점유한 프로세스가 R2를 요청하고자 하면, 먼저 R3을 해제해야 R2 요청 가능
•
항상 작은 번호 → 큰 번호 방향으로 자원을 점유하게 되며, 이로 인해 환형 구조가 생성되지 않는다.
교착상태 회피
시스템이 교착상태에 빠지지 않도록 사전에 판단해서 자원의 할당 여부를 결정하는 방식
사전정보 : 현재 할당된 자원, 가용상태의 자원, 프로세스들의 최대 요구량 등
안정상태
•
모든 프로세스가 최대 자원 요구량까지 자원을 순차적으로 할당받고도 종료할 수 있는 상태
•
적절한 순서로 자원을 할당해 나가면 교착상태 없이 모든 프로세스를 완료할 수 있는데 이런 순서를 안전 순서열이라고 함
불안정 상태
•
안전순서열이 존재하지 않는 상태
•
아직 교착상태가 발생한 것은 아니지만 교착상태에 이를 가능성이 존재함
안전 순서열(Safe Sequence)
•
시스템 내의 프로세스들을 어떤 순서로 자원을 할당하더라도 교착상태 없이 모든 프로세스가 종료될 수 있는 실행 순서
안전 순서열 예제 펼치기
자원의 개수에 따른 차이
•
자원이 하나만 있는 경우
◦
자원 할당 그래프에 사이클이 생기면 교착상태가 반드시 발생
•
자원이 두 개 이상 있는 경우
◦
사이클이 있다고 해도 교착상태가 발생하지 않을 수 있음
◦
실제 자원 배분 시에는 은행원 알고리즘과 같은 방식으로 안전성을 평가해야 함
은행원 알고리즘
자원을 요구받으면 그 자원을 할당해주고 난 후의 상태를 계산해서 안전상태가 보장되는 경우에만 자원을 할당하는 방식
필요한 정보
•
프로세스는 자원을 요청할 때, 자신의 최대 요구량(Max)과 현재 할당량(Allocation), 요청량(Request) 제출
•
Max: 각 프로세스의 최대 자원 요구량
•
Allocation: 현재 할당된 자원
•
Available: 시스템에 현재 가용한 자원
•
Need = Max - Allocation: 앞으로 필요한 자원의 수
수행 과정
1.
프로세스가 자원을 요청
2.
요청량이 그 프로세스의 최대 요구량(Max)를 넘지 않고 Available보다 작거나 같은지 확인
3.
요청을 일시적으로 할당한 후, 시스템이 안전상태인지 검사
4.
안전하다면 자원을 실제로 할당, 불안정하다면 할당 취소하고 대기
교착상태 탐지 및 복구
교착상태 발생 후 사후에 처리하는 방법
교착상태 탐지
•
시스템의 교착상태 여부를 조사하기 위해 주기적으로 상태 조사 알고리즘 수행
•
대표 알고리즘 - Shoshani와 Coffman 알고리즘, 자원할당 그래프 분석해 사이클 존재하는지 확인
교착상태 복구
교착상태에 빠진 프로세스를 종료시켜 자원을 회수
•
모든 교착상태 프로세스 종료
◦
사이클에 포함된 모든 프로세스를 종료
◦
진행했던 내용에 대한 복원비용이 큼
•
사이클이 제거될때까지 교착상태 프로세스 하나씩 종료
◦
사이클이 사라질 때까지 프로세스를 하나씩 종료
◦
종료할 프로세스를 선택하고 → 종료 후 다시 교착상태 여부 검사
◦
이 과정이 반복되므로 오버헤드가 큼
교착상태 프로세스가 할당받은 자원을 강제로 회수
•
사이클이 제거될 때까지 할당된 자원을 단계적으로 선점하여 다른 프로세스들에 재할당
•
중단된 프로세스는 대기 상태로 보냄
•
기아 상태 방지
◦
자원이 반복적으로 회수되어 특정 프로세스가 무한히 대기하는 상황을 피해야함
◦
복구 횟수나 우선순위를 기준으로 공정하게 선점대상 선택
요약
•
교착상태는 네 가지 조건이 동시에 만족될 때 발생(상호배제, 점유대기, 비선점, 환형대기)
•
자원 할당 그래프의 사이클 여부로 교착상태 발생 가능성 판단
•
예방: 네 가지 조건 중 최소 하나를 사전에 차단
•
회피: 사전 정보로 안전 상태 유지, 대표 알고리즘은 은행원 알고리즘
•
탐지 및 복구: 교착상태 발생 후 사이클 탐지, 프로세스 종료 또는 자원 선점으로 복구