데드락
: 프로세스와 한정된 자원에서 생기는 문제 -> traffic jam이 생겨버리는 것 -> 영원히 대기 상태에 머무르게 됨
6.1.1 자원이란?
1) 선점가능성에 따라
선점가능자원(preemptible)
: cpu, 메모리와 같은 자원처럼 한 프로세스에 의해 사용 도중 다른 프로세스에 뺏기는것
선점 불가능한 자원(nonpreemtible)
: 선점될 경우 자원을 뺏긴 프로세스는 정상적인 진행을 포기해야 하는 불이익을 받게 되는 경우의 자원?
2) 자원이 사용되어지는 방식에 따라
공유가능 자원 : 공유가능한 프로그램과 공유 데이터
배타적 사용 자원 : cpu, 메모리, 테이브, 버퍼, 키보드, 모니터
자원의 속성 : 순차적 재사용이 가능한 자원(serially reusable) 이것만 다룰거야 (소모성 자원은 제외함)
6.1.3 교착상태의 원인은?
4가지 조건들이 모두 갖춰질 때 교착상태가 발생한다
1) 자원의 배타적인 사용
: 교착상태는 시스템이 보유한 한정적인 자원에 대한 프로세스들 간의 사용경쟁 때문
: 자원이 한정적이더라도 모두 공유 가능한 자원이라면, 교착상태 발생 불가 = 상호배제 조건(mutual exclusion condition)
2) 자원의 부분할당(partial allocation)
: 프로세스 필요한 자원을 그때그때 달라고 하는데 시점이 제각각이므로 필요할 때 할당 불가능. 이에 미리 확모한 자원들을 소유한 채 대기상태(hold & wait)가 되어버리는 과정을 겪으면서 교착상태에 빠질 가능성을 높인다
3) 자원의 선점불가능성(no preemption)
: 비선점의 조건이라고도 함. 자원 뺏기 불가능해!를 고수하면 교착상태가 발생해. 필요한 프로세스들의 정상적인 실행을 포기할 수밖에 없게 되므로...무한대기 발생...
4) 자원에 대한 환형대기(circular-wait)
: 프로세스들이 자신의 자원 보유한채 서로 상대방의 자원을 요청하고있는..그래서 결과적으로 대기 상태에 빠져버리는 것.
6.2 교착상태 해결하기 위한 기법
1) 예방기법(prevention)
: 앞에서 본 4가지 중 하나라도 생기지 않게끔하면 데드락 발생안함
: 자원의 배타적 사용 조건을 배제한다. (현실적으로 불가능 에베ㅔ)
: 자원의 부분 할당을 없앤다 - all at once (all or none) 프로세스 실행 시작할 때 시작~끝날때까지의 자원을 모두 들고 시작하는 것. 대기 될 이유 없이 순탄하게 종료됨. 그러나 단점 : 일부자원만 확보되면 시작 가능한데, 모든 자원 할당받을때까지 기다려야함. 할당 가능했던 일부 자원들은 사용되지 못하고 낭비되는 현상 발생(자원의 심각한 낭비 초래, 무한대기 프로세스 발생)
: 자원의 선점불가능 배제 - 선점 불가능한 자원을 선점 가능하게 만드는데 발생하는 비용이 클 것. 하나씩 확보해서 주는데, block되면 자신이 가지고있는 자원을 모두 내놓는 것...(형-톱, 동생-망치 -> 형이 망치 달라고 하면 (block이 됨) : 그러면 모든 자원을 내놓게 됨.... -> 처음부터 다시 해야하는 무한대기를 겪을 수도 있음)
linear ordering : 순서대로 대기 확보를 하는 것을 의미함
데드락을 발생할 수 있는 조건?
나머지 조건 3개를 안생길 수 있도록 하면 -> 데드락 안생김!
리소스(자원) 심각한 낭비 + 무한대기 현상은 어쩔 수 없이 갖고가야한다..
2) 회피기법(avoidance)
:다익스트라 은행가 알고리즘!
안정상태(safe state)
: 시스템 프로세스가 유한한 시간 내에 정상 종료될 수 있느 상태를 말한다. 그러지 못할 경우 불완전 상태라고 한다..
안전-불안전-교착상태의 관계(그림 추후첨부)
:다익스트라 은행가 알고리즘! -어떻게 운영되냐 ? 교착상태 얼씬도 안함! 안정상태로만 가게끔한다~!!
-몇 가지 가정이 요구된다
1)시스템 내 프로세스 수 고정되어야 한다
2) 자원 수 고정
3) 각 프로세스가 요구할 자원의 퇴대개수 알려져야
4)프로세스는 할당받은 자원을 사용 후 반드시 반납해야한다
(현실적으로 불가능한 가정들)
자원의 낭비는 무조건 발생할 수 밖에 없음...
현재 시스템 할당 여유량, cpu현재 보유량, 최대요구량 존재
할당결과 : safe - 준다 / unsafe - 안 준다!
#불완전상태의 예시도 존재 -> 요지는 데드락 절대 발생하지 않게끔 하겠다! 의미임
3) 탐지 및 복구기법(detection and recovery)
: 교착상태(데드락) 허용. 탐지(찾아내어) 적절한 조치를 취한다는 의미!
자원할당그래프(RAG) - 그림 6.2
+) RAG : 방향성이 있는 노드와 에지들로 구성되어져있다. 에지(방향성 있음) resource -> process로 가야하는 에지는 할당되는 것. process -> resource는 대기상황인 것?(p.121 이해하지 못햇음)
자원을 네모 안에 표현을했는데, 이제는 동그라미를 표현해 자원을 2개 혹은 3개 ...n개 이렇게 표현한다!
RAG는 어떤 프로세스가 어떤 자원을 갖는지? 어떤 프로세스가 어떤 자원에의해 대기상태가 되는지를 잘 나타내고있고, 여유량이 있는 자원에 의해 대기상태가 아닌 프로세스들에 대한 정보도 알려줄 수 있다.
p.122
활동이 바로 가능한 프로세스를(cpu를 받은 프로세스:갖고있는 걸 누구한테 주거나, 더 자원을 요청하거나 등등)의 행동을 할 수 있는 것으로 그걸 unblocked 프로세스 or sink 라고 부른다. 이런 프로세스들이 자원에 대한 요청이나 반납의 실행을 할 수 있고, 그 결과 RAG도 변경시킬 수 있다.
block이 되면 꼼짝 못해~!!!~!!~!~~
싱크프로세스?
:반납할 수 있어서 자원 모두 반납하면 rag는 반납된 자원들로 이전 대기된 애들이 할당받을 수 있어 sink 대열에 합류할 수 있다. rag는 이 작업을 계속 시행해서 edge를 제거되면 교착상태가 없다고 판단하고, 만약 지워지지 않은 에지들이 있다면 이 에지들에 연결된 프로세스들이 교착상태에 빠져있다고 결론이 난다.
반답된 자원을 p2에 할당해주면 p2 싱크되어 다시 엦지들 제거 가능함
현재 당장 사용할 수 없는 자원을 달라고했는데 block 되었을 때 = 데드락 발생한다(block할수록 데드락에 가까워짐)
프로세스 블록될 때마다, 에지 따라가보고 sink 되면데드락 아니다 라고 판단, 다 돌아봤는데 sink가 안 나왔다 라고 하면 그건 데드락임
이 얘기는 123쪽에서 나온다. 두번째 detection 방법을 의미함
:
6.2.4 복구기법
1) 프로세스 종료방식
: 희생 최소화를 위해 종료비용, 강제종료 프로세스에서 잃게되는 양을 따져 종료비용이 최소한 되는 것으로 종료시켜나간다.
2) 자원선점에 의한 방식
:
너무 어려운데...?
화살표 따라가는데, 실수 나오면?
대드락 그래프 : not 포함(사이클 표현되어있음)
7장
