교착상태
라이브락, 데드락
-
데드락은 A,B B,A 요청상황
-
라이브락은, 네트워크에서 패킷상황.
인터넷이 엄청 빨라져서 DB에 엄청 많이 써야 함
하지만 이부분은 병목임
그래가지고, 패킷 큐에 계속 쌓임
패킷 큐가 꽉 참
그래서 다른 애들은 통신오류인 줄 알고 계속 보냄
운영체제는 인터럽트가 계쏙 걸리면서 아무것도 할 수 없게됨
시간차로 극복
조건
-
상호 배제
한번에 하나의 작업흐름만 해당 리소스를 점유할 수 있다.
-
점유하고 대기
-
비선점(실제 스케줄링이 아니라, 자원의 관점에서. 스레드가 무조건 버려야지 자원이 뺏어진다.)
-
순환대기
그래프
-
한 개의 인스턴스만 가지면, 사이클 존재 시 무조건 데드락 발생한다.
-
두 개 이상을 가지면, 사이클이 존재할 수도, 안 존재할 수도 있다.
즉, 상황에 따라 다르며, 모른다.
교착상태 예방
-
상호배제
예를 들어, 읽기만 하면 상관 없지만 쓰기 상황일 때 상호배제를 안 하게 되면 망한다.
게다가, 애초에 뮤텍스 락이라는 자원은 개념적으로 공유할 수가 없는 자원이다.
-
점유하며 대기
자원을 가지고 가기 전 all or nothing으로 리소스를 할당하면 가능하지만, 잠깐 쓰이는 자원을 위해 오래동안 기다려야 할 수도 있으므로 효율적이지 못하다.
-
비선점
만약, 어떤 자원을 가지고 있는 상태에서 락이 걸리면, 그냥 자원을 방출한다. 그리고 다시 모든 자원을 획득할 수 있을 때 시작한다. 프로세스 실행 시간이 엄청나게 길어질 수도 있다.
또한 뮤텍스의 정의 상, 한번 가지고 있던 뮤텍스락을 놓아버린다는 것이 말이 안 된다.
-
순환대기
가장 가능성 있다.
자원에 번호를 매겨놓고, 오름차순으로만 자원 할당이 가능하도록 한다.
결국 성능은 또 떨어질 수 밖에 없다.
교착상태 회피 방법
안전상태
- 즉, 현재 가용한 자원들로 잘 스케줄링 하면 모든 스레드를 종료시킬 수 있는가?
자원할당그래프알고리즘
이렇게 사이클이 있다면,, 예약간선은 현재 상태가 아니라 미래의 상태이다. 굵은게 현재 상태.
뱅커스 알고리즘
-
스레드가 필요한 자원의 갯수를 스레드 시작 시 모두 다 신고하여야 한다.
-
Need = MAX - ALLOCATION
-
안전성 검증 알고리즘
- NEED는, 현재 전체 테스크가 필요한 자원의 양이 써져 있다.
- 즉, 전체 태스크를 돌면서, 현재 자원을 가지고 끝낼 수 있는 일을 다 끝낸다.
- 일을 마쳤다면, 안전한 상태이다
- 자원 요청 알고리즘
- Need(i)는 요청된 후의 필요한 자원 크기
- 일단, 현재 need인 것 보다 request가 크다면, max 이상을 요구한 것이기 때문에 반환한다.
- need를 해결할 수 있는지를 본다.
- 자원을 할당했다고 가정하고, 시스템이 안정상태인지 확인한다.
교착상태 탐지
자원이 종류별로 한개씩 있는 경우
- 사이클 쓴다.
각 유형의 자원을 여러 개 가진 경우
- 다른 점은, 이전에는 MAX값과 NEED값이 있었다. 하지만 지금은 REQUEST가 조금은 다른 값이다.
- 그냥, 알고리즘이 끝나는 지를 확인하면 된다.
- 끝낼 수 있는 (request를 만족 시킬 수 있는) 쓰레드들을 차례로 끈다.
- 만약, 끝낼 수 있는 쓰레드들이 없다면 교착상태이다.
언제 사용할 것인가?
-
자주, 몇 개가 걸리는 지에 따라 달려있다.
-
스레드의 요청을 만족시키지 못할 때마다, 교착상태를 탐지하는 알고리즘이 있긴 한데, 조금 그래.
-
교착상태에 빠진 모든 스레드에 대해 실행하기 때문에, 원인파악이 가능하다.
-
CPU 이용률이 엄청 떨어졌을 때, 알고리즘을 돌려서 교착상태를 확인한다.
원인파악은 불가능하다.
회복 방법
교착 상태인 프로세스를 종료
-
그냥 다 꺼버린다. 끔찍하네
-
아니면 하나씩 끄면서 교착상태가 해결되어ㄴㅆ는지 본다.
-
뭘 끌 것인가는,,
여태까지 실행된 정보라던가, 우선순위라던가, 자원의 수라던가,, 진짜 많다.
자원 선점 방법
-
롤백
결국, 자원을 먹기 전으로 되돌려놓아야 한다. 쉽지 않은 일.
-
희생자 선택
-
기아 상태. 즉, 맨날 나한테만 자원선점하려해 ㅠㅠ 이럴 수도 있지.
리눅스커널은 그냥 재시작..
