deadlock
일어나지 않을 일을 하염없이 기다리는 상태
<시스템 모델>
시스템은 자원(CPU 사이클, 메모리 공간, I/O 장치 등)을 포함한다.
프로세스의 자원사용순서
1)request(요청)
2)use(사용)
3)release(방출)
<deadlock(교착상태)가 발생하는 조건(이유)>
1)mutual exclusion(상호배제) : 한 번에 한 프로세스만 자원을 사용하는 경우
2)hold and wait(점유 그리고 대기): 프로세스가 자원을 가지고 있는 상태에서 또 다른 자원을 기다리는 것
3)no preemtive(비선점적):선점이면 뺏을 수 있는 데 그렇지 못하니까 , 프로세스가 완료된 후에 리소스를 자발적으로 해제함
4)circular wait(순환 대기):P0은 P1이 가진 자원 P1은 P2가 가진 자원을 기다리는 ~ Pn은 P0이 가진 자원을 기다리는 순환대기가 일어날때
<자원 할당 그래프>
request(요청) edge : Pi -> Rj
assignment(할당) edge : Rj -> Pi
if(사이클이 없다) deaklock 발생 x
else if(사이클이 있다){
if(자원이 하나다)deadlock 발생 o
else if(자원이 여러개다) deadlock 발생 o/x }
<deadlock을 다루는 방법>
1)deadlock prevention(교착상태 예방)
2)deadlock avoidence(교착상태 회피)
unix에서는 교착상태(deadlock)를 그냥 무시, 대부분 user 프로그램에서 발생하기 때문
<deadlock prevention(교착상태 예방)>
deadlock을 실행시키는 4가지 조건 부정
1)mutual exclusion(상호배제)는 부정불가(공유 가능한 자원에서는 부정 불가, 공유 불가능한 리소스에서는 유지 되어야함!)
2)hold and wait(점유 그리고 대기) :
(1)자기가 필요한 모든 자원을 한꺼번에 요청, (기아상태 발생)
(2)프로세스가 어떤 자원도 가지지 않았을 때 프로세스 시작 (자원 활용도 떨어짐)
3)no preemtive(비선점) :
내가 필요한 자원을 가질 수 없는 상태인 경우에 내가 가지고 있는 모든 자원을 방출한다.
자원을 다시 한 번 모두 요청한다.
조건: 복원이 가능한 자원인 경우에 사용가능
4)circular wait(순환대기):
자원(프로세스x)에게 순번을 정한다. 자원의 순번이 증가하는 순서로 요청한다.
문제점: 동적으로 lock의 순번이 정해지는 경우 deadlock 회피 불가능
이 예시에서 교차로 실행될 때 deadlock이 발생한다.
<deadlock avoidance(회피)>
요청을 받고 simulation을 돌려보고 circular wait(순환대기)(unsafe상태)가 발생할 거 같으면 받아들이지 않음
- deadlock을 회피하기 위해서는 몇 가지 사전 정보가 있어야 함
1) 프로세스가 필요한 자원의 최대개수
2) 현재 시스템에 남아있는 자원의 개수
3) 각각의 프로세스가 현재 가지고 있는 자원의 개수
<안전상태란? >
Pi가 요구하는 자원들이 현재 사용가능한 자원들과 Pj(j<i)가 가지고 있는 자원들로 충족되는 상태
즉,
1)Pi의 자원 요구가 즉시 충족되지 않으면, Pi는 모든 Pj가 완료될 때까지 대기할 수 있습니다.
2)Pj가 완료되면, Pi는 필요한 자원을 얻고, 실행하고, 할당된 자원을 반환하고, 종료할 수 있습니다.
3)Pi가 종료되면, Pi+1은 필요한 자원을 얻고 실행할 수 있습니다.
if(시스템이 safe state(안전상태)인 경우)- deadlock 없음
else if(시스템이 safe state(안전상태)가 아닌경우){
deadlock 발생 할 가능성
}
- avoidance(회피) -> 시스템이 unsafe상태로 가지 않도록 해준다.
<avoidance(회피) 알고리즘>
리소스가 단일 인스턴스인 경우: resource-allocation graph(자원 할당 그래프)
리소스가 다중 인스턴스인 경우: banker’s algorithm
<자원할당 그래프>
- claim edge(예약 엣지): 자원이 요청될 가능성이 있지만 아직 요청하진 않는 경우 점선으로 나타냄
- request edge(요청 엣지): 자원 요청 엣지
- assignment edge(할당 엣지): 자원이 할당된 상태를 나타내는 엣지
claim edge에서 request edge로: 프로세스가 자원 요청
request edge에서 assignment edge로: 프로세스에 자원 할당
assignment edge에서 claim edge로: 자원이 해제되고 요청될 가능성이 있는 상태로 감
*모든 자원은 시스템에서 사전에 청구되어야함
자원할당 그래프로 시뮬레이션을 해보고 circular- wait가 나타나면 요청을 받아들이지 않는다.
즉,
요청 엣지(request edge)를 할당 엣지(assignment edge)로 전환해도 사이클이 발생하지 않는 경우에만 요청허용가능
<banker's Algorithm(알고리즘)>
사용할 자원은 사전에 청구해야함
프로세스가 자원을 요청하면 기다려야할 수 있다.
프로세스는 자원을 제한된 시간 내에 반환해야 한다.
banker's 알고리즘 구조:
n:프로세스의 수
m:자원 타입의 수
1)Available :길이가 m인 벡터
ex) Available[j]=k인 경우
Rj의 인스턴스를 k개 사용할 수 있음
2)Max : nxm행렬
ex)Max[i,j]=k
Pi가 Rj를 최대 k개 필요로 한다.
3)Allocation : nxm행렬
ex)Allocation[i,j]=k
Pi에게 Rj가 k개 할당되었음을 의미
4)Need : nxm행렬
ex)Need[i,j]=k;
Pi가 작업을 완료하기 위해 추가적으로 필요한 Rj의 개수가 k임을 의미
so Need[i,j]=Max[i,j]-Allocation[i,j]
<안전한 banker's 알고리즘>
1) 변수 초기화
work와 finish를 m과 n의 벡터로 초기화
Work=available로 초기화 (현재 사용가능한 자원을 나타냄)
Finish[i]=false로 초기화(i는 0~n-1)(프로세스의 완료여부 나타냄)
2)다음을 충족시키는 프로세스i 찾기
(a) Finish[i]=false
(b)need(i)<=work (현재 사용가능한 자원이 need를 충족시키는 지 확인)
충족시키는 i가 없으면 4번으로 가기
3)작업 수행 후
work=work + Allocation[i] (프로세스 i에 할당된 자원을 work에 더함)
Finish[i] = true(프로세스 i를 완료 상태로 설정)
2번으로 가기
4)안전 상태 확인
모든 i에 대해 Finish[i]=true이면, 시스템은 안전 상태에 있음
<프로세스 i의 자원요청 알고리즘>
1)request(i)<=need(i)일 경우 2번으로 넘어감
(요청된 자원이 추가적으로 필요한 자원(need)을 넘는 지 확인) - 넘으면 에러발생
2)request(i)<=available일 경우 3번으로 넘어감
(요청된 자원이 현재 사용할 수 있는 자원(available)을 넘는 지 확인) - 넘으면 대기 해야함
3)요청된 자원을 가상으로 할당
(a) available= available-request(i)
(b) allocation(i)=allocation(i)+request(i)
(c) need(i)=need(i)-request(i)
if(안전 상태){자원을 pi에 할당)
else if(안전상태가 아니라면){pi를 대기시키고 자원을 원상태로 복구}
<banker 알고리즘의 예시>
위의 예시에서 P1 Request (1,0,2)한 경우
<deadlock detection(감지)>
(a) 시스템이 교착상태로 가도록 허용
(b) 감지 알고리즘(Detection algorithm)
(c) deadlock 복구(recovery)
<자원이 단일 인스턴스인 경우>
wait-for 그래프 유지
ex) P(i)->P(j)
wait-for 그래프? 자원할당 그래프에서 자원을 뺀 형태, 프로세스의 관계를 그린 그래프
그래프에서 사이클을 찾는 알고리즘(n^2의 연산순서 필요(n은 정점 수)) 주기적으로 호출
<리소스 유형의 사례(인스턴스)>
a) Available : m길이의 벡터는 각 유형의 사용 가능한 리소스 수를 나타냄
b) Allocation: nxm 행렬의 각 프로세스에 할당된 각 유형의 리소스 수를 정의
c) Request: nxm 행렬은 각 프로세스의 현재 유형을 나타냄
ex)request[i][j]=k <- 프로세스 P(i)가 자원 R(j)을 k개 요청함
<Detection(감지) 알고리즘>
1) 변수 초기화
work와 finish를 m과 n의 벡터로 초기화
Work=available로 초기화 (현재 사용가능한 자원을 나타냄)
모든 i에 대해 Allocation이 0인 경우 Finish[i]=true로 초기화, 그 외인 경우 Finish[i]=false로 초기화
2)다음을 충족시키는 프로세스i 찾기
(a) Finish[i]=false
(b)Request(i)<= work
충족시키는 i가 없으면 4번으로 가기
3)작업 수행 후
(a)work=work + Allocation[i] (프로세스 i에 할당된 자원을 work에 더함)
(b)Finish[i] = true(프로세스 i를 완료 상태로 설정)
2번으로 가기
4)deadlock 확인
Finish[i]=False인 i가 있다면 시스템은 deadlock 상태임
추가로 Finish[i]=False인 경우 P(i)가 deadlock상태
알고리즘에서 시스템이 교착 상태에 있는지 여부를 감지하려면 O(m x n^2)개의 연산 순서가 필요합니다
<감지(detection) 알고리즘 예시>
<detection 알고리즘 사용>
호출하는 시기와 빈도
a) 교착상태가 발생할 가능성이 얼마나 되는 지
b) 얼마나 많은 프로세스를 rollback 해야하는 지 -> 분리된 사이클마나 하나씩
탐지 알고리즘이 임의로 호출되면 어떤 프로세스가 교착상태를 야기했는 지 알기 어려움
< Recovery from Deadlock(교착상태 복구)>
1) 프로세스 종료(termination)
2) 자원 선점(preemtion)
<Process Termination(프로세스 종료)>
교착사이클이 없어질 때까지 한번에 하나씩 교착상태인 모든 프로세스 중단
<어떤 순서로 프로세스를 중단(abort)하는 가에 고려할 점>
1) 프로세스의 우선순위(낮은 친구 먼저)
2) 프로세스가 얼만큼 실행되고 얼만큼 남았는지 (막 시작한 프로세스 abort)
3) 프로세스가 사용한 자원의 수(자원의 수가 적은 프로세스 abort)
4) 프로세스 완료까지 얼만큼의 자원이 더 필요한가
5) 종료해야 할 프로세스 수(적은 수의 프로세스가 종료되는 것이 좋음)
6) 프로세스는 대화형(interect)인지, 배치(batch)인지?
< Resource Preemption(자원 선점)시 고려해야할 점>
1)희생자(victim) 선정: 비용 최소화 고려
2)rollback: checkpoint까지 돌아가 프로세스 다시 시작
3)starvation: 항상 동일한 프로세스를 희생자로 선택할 수 있기 때문에 롤백 횟수도 고려할 수 있음
