📒01_교착상태란
두 개 이상의 프로세스가 각자 먼저 확보한 자원을 가진 채 상대방의 자원을 필요로 할 경우, 외부에서의 조치가 없는 한 무한정 대기하는 상황
교착상태의 문제점
- 해당 프로세스가 더 이상 실행되지 못해 사용자에게 응답하지 않음
- 보유된 자원들이 교착 상태에서 벗어나기 전까지는 전혀 활용되지 못한다는 점이다.⇒ 시스템의 성능 저하
무한 대기와 교착상태는 다르다! 외부적조치가 없어도 서비스 받을 수 있냐의 여부
✅자원(Resource)이란?
하드웨어 자원 - 하드디스크 , 테이프, 드라이브, 메모리
소프트웨어 자원 - 데이터 , 메세지
선점가능자원(Preemptible)
- 한 프로세스에 의해 사용도중 선점되어 다른 프로세스에게 할당해주었다가 다시 원래 프로세스에게 돌려주어도 되는 자원들
- 운영체제에 의해 사용도중 뺏길 수 있다.
- 다중 프로그래밍의 성공을 위한 것
선점불가능자원(NonPreemptible)
- 사용도중 뺏을 수 없는 자원
- 프린터, 테이브 드라이브
- 정상적인 진행을 위한 것
자원이 사용되어지는 방식
공유 가능 자원(Sharable)
- 한 프로세스에게 할당된 자원을 다른 프로세스가 할당 받아 같이 사용할 수 있다.
- 공유가능한 프로그램
- 시스템 프로그램이나 유틸리티 프로그램, 공유데이터
배타적 사용 자원(Exclusive)
- CPU, 메모리, 테이프, 버퍼, 키보드, 모니터
자원의 속성에 따른 분류
순차적 재사용 가능 자원(Serially Reusable)
- 할당된 자원이 사용 후 반납(Release)되었을 때 자원 자체는 계속 존재하여 또 다른 프로세스에게 할당가능함
- 시스템에서 프로세스들이 아무리 사용하여도 없어지지 않고 영구히 존재함.
그외에는 소모성(Consumable)자원과 시그널(Signal)이나 메세지가 해당됨
✅프로세스는?
- 프로세스는 자원에게 요청(Request)을 할 수 있다. 이때 두가지 경우가 발생
- 사용가능(Available)하다면, 이 자원을 할당 받아 이용한다. 사용중이라면 반납 되어 질때까지 대기
- 사용이 끝난 자원을 반납. 대기 상태의 프로세스는 아무것도 할 수 없다.
⇒ 요청과 반납은 실행중인 프로세스가 시스템 서비스를 호출(System call)함으로서 운영체제에 의해 이루어짐.
⇒ 대기가 된 프로세스들이 늘어나 엮임으로써 모두 대기가 된다.(교착상태)
✅교착상태의 원인
4가지 중 하나라도 부정 가능하면 교착 상태는 일어나지 않는다.
1.자원의 배타적인 사용
- 교착 상태란, 시스템이 보유한 한정적인 자원에 대한 프로세스들의 사용 경쟁
- 상호배제 조건(Mutual Exclusion)
2.자원의 부분 할당(Partial Allocation)
- 각각의 프로세스는 자신의 실행 전체 과정에서 필요한 자원을 필요할 떄마다 할당 받아 사용.
- 이미 확보한 자원을 소유한 채 대기 ⇒ 교착 상태 발생
- Hold & Wait
3.자원의 선점 불가능성
- 선점 권한이 있으면 교착 상태 벗어날 수 있음 ⇒ 선점 당한 프로세스는 지금까지 해왔던 일 전부 잃음
- 비선점 조건(Nonpreemption)
4.자원에 대한 환형 대기(Circular-Wait)
- 프로세스들이 자신의 자원을 보유한 채로 서로 상대방의 자원을 요청하고, 결과적으로 대기 상태가 되어버리는 일련의 과정
- 동그라미는 프로세스, 네모는 자원
📒02_교착상태의 해결
교착상태 일어나지 않도록 사전에 : 예방(Prevention), 회피(Avoidance)
교착상태 일어난 이후에 조치: 탐지(Detection), 복구(Recovery)
✅예방(Prevention)
무한대기와 자원의 심각한 낭비
1.자원의 배타적 사용을 배제
- 모든 자원을 공유가능자원으로 활용 ⇒ but 배타적으로만 사용가능한 자원 있음(프린터기, 테이프 장치)
- 불가능!
2.자원의 부분 할당을 배제
- 모두 할당(total Allocation)
- 일부자원만 있어도 실행 가능하지만, 모든 자원이 할당될때까지 기다림
- 심각한 자원낭비
- 무한 대기
3.자원의 선점 불가능을 배제
- 선점 불가능한 자원을 선점 가능으로 만듦.
- 반납한 프로세스는 나중에 한꺼번에 필요한 자원 요청
- 문제점은 비정상적인 종료와 함께 심할 경우 처음부터 다시 시작해야하는 불이익, 무한대기
4.자원의 환형 대기를 배제
- P1,P2가 각각 R1,R2/ R2,R1을 할당 받을 떄, 순서대로 할당 받아야한다. 무조건 1⇒2⇒3 ….
- 무한대기
✅회피(Avoidance)
자원의 낭비는 예방 기법보다는 덜하나, 낭비는 여전히 일어난다.
안전상태(safe state)
시스템에 있는 모든 프로세스가 유한 시간 안에 정상적으로 종료될 수 있는 상태
안전상태가 아니라고 모두 교착 상태를 일으키지는 않는다
✏️Dijkstra의 은행가 알고리즘
은행가 알고리즘의 조건
- 시스템 내 프로세스 수가 고정되어 있어야한다.
- 자원의 수 역시 고정되어 있어야한다
- 각 프로세스가 요구할 최대 자원수가 알려져야한다
- 각 프로세스는 할당받은 자원을 사용후 반드시 반납하여야 한다.
| 프로세스 | 현재 보유량 | 최대 요구량 |
|---|---|---|
| P1 | 1 | 4 |
| P2 | 4 | 6 |
| P3 | 5 | 8 |
| 여유량 = 2 |
⇒ 현 상태에서 모든 프로세스가 정상적으로 종료할 수 있는 길이 적어도 하나 이상 있는가?
⇒ 현상황은 P2에게만 할당가능하다
✅탐지(Detection)
탐지프로그램이 가져야할 정보
- 어떤 프로세스가 어떤 자원을 가지고 있는가?
- 어떤 프로세스가 어떤 자원에 의해 대기 상태가 되어 있는가?
✏️ 자원할당그래프(Resource Allocation Graph, RAG)
- RAG는 방향성 이분 그래프이며 노드와 엣지로 이루어져있다
- 한 자원형에 여러개의 자원이 있을 수 있다.
- 자원으로 향하는 에지가 없는 프로세스는 싱크, 활동이 가능한 프로세스이다.
✅복구(Recovery)
1.프로세스의 종료(Process Termination) 방식
- 교착 상태를 일으킨 프로세스 중 몇개를 강제로 종료
- 종료 비용이 최소인 프로세스부터 종료 시작 아니면 집합 형태로도 종료
2.자원의 선점에 의한 방식
- 필요한 자원을 가지고 있는 프로세스로 부터 자원을 강제로 뺏어 프로세스의 강제 종료
- 교착상태와 전혀 연관이 없는 프로세스도 강제 종료 당할 수 있다.
- 강제종료 낭비 줄이기 ⇒ 검사점 지정(Checkpointing), 재시작(Restart)
