💻 데드락
프로세스들이 더 이상 진행을 하지못하고 "영구적"으로 Block 되어있는 상태
프로세스 A는 프로세스 B가 가진 자원이 있어야 실행이 가능한데
프로세스 B 또한 프로세스 A가 가진 자원이 있어야 실행이 가능하다면
두 프로세스는 상대가 자원을 주기만 바라면서 멈춰있다.
💻 자원할당 그래프
교착상태는 자원 할당 그래프를 통해 쉽게 표현가능하다.
자원은 직사각형으로 프로세스는 원으로 표현되며
사용가능한 자원의 개수는 직사각형 안의 점으로 표시된다.
프로세스가 요청을 하면 외부에 화살표를
할당을 받으면 자원 안의 점에서 프로세스로 할당을 해준다.
이는 자원을 요청할때는 아무거나 받으면 되기때문이고
받았으면 어떤 자원을 받았는지 알아야 하기 때문이다.
📖 자원의 종류
프로세스가 사용하는 자원은 크게 2가지이다.
1. 재사용 가능한 자원
- 프로세서, 입출력 채널, 메모리, 파일, 세마포어 등과 같이 재사용이 가능한 자원
2. 소모성 자원
- 프로듀서 컨슈머 문제에서 처럼 사용하고나면 사라지는 자원💻 데드락 조건
데드락이 발생하기 위해서는 다음 3조건이 필요하다.
1. 상호 배제 : 한 프로세스가 점유한 자원을 다른 프로세스가 접근이 불가하다.
2. 점유대기 : 한 프로세스가 자원을 들고있으면서 다른 자원을 요청하며 기다리고 있다.
3. 비선점 : 프로세스가 점유한 자원을 다른 프로세스가 강제 빼앗을수 없다.
여기에 하나더 "환형 대기" 조건이 만족되면 데드락이 발생한다.
4. 환형 대기 : 자원할당 그래프에서 환형이 만들어 지는것
이 환형대기는 위의 1~3의 결과에 의해 발생한다.
위의 조건을 만족한다면 데드락이 발생하며
만약 이중 하나라도 만족치 않는다면 데드락은 발생하지 않는다.
데드락을 막는 방법은 3가지로
1. 예방
2. 회피
3. 발견
이다 밑에서 더 자세히 알아보자.📚 데드락 예방(Deadlock prevent)
데드락을 막기위한 방법 중 한개로 교착상태가 발생할 가능성을 없앤다.
데드락은 앞서 살펴본 4가지의 조건을 만족한다면 발생하니 위의 조건중 아무거나 1개만
막는다면 데드락을 예방할수 있다.
1. 상호 배제
- 상호 배제 조건을 없앨수 없다.
공유 자원의 일관성을 유지하기 위해서 반드시 필요하기에 이는 불가하다.
2. 점유대기
- 프로세스가 자원을 가지고 있으면서 요청하는 것이 문제라면
한번에 모든 자원을 할당 시키거나 하나라도 할당이 불가하면 아예 할당을 시켜주지 않는다.
이는 여러 문제가 있는데 만약 일부만 할당 받아 실행이 가능함에도 모든 자원을 할당시키려고
한다면 비효율의 문제가 있다.
3. 비선점
- 자원을 점유한 프로세스가 다른 자원을 요청했을때 할당이 불가하다면 자신이 점유한 자원을 반납한다.
한 프로세스에서 다른 프로세스가 원하는 자원을 가지고 있다면 다른 프로세스가 점유한 자원을 뺏어서 준다.
이를 통해 우선순위 별로 실행을 시킬수가 있다.
단, 이때 프로세서처럼 저장과 복구가 쉬운 자원에만 활용한다.
4. 환형대기
- 자원들의 할당 순서를 정하면 없앨수가 있다.
모든 자원에 순서를 정해준뒤 해당 순서대로만 할당시켜준다.
예를들어 1,4,7번의 자원을 요청하면 할당을해주지만
2,1,8 순으로 요청을한다면 이는 불가하다.📚 데드락 회피(Deadlock avoid)
할당전에 이 할당이 교착상태를 발생시킬 가능성이 있는지 없는지 검사후
없다면 자원을 할당해준다.
회피에는 2가지 기법이 존재한다.
1. 프로세스 시작 거부
2. 자원 할당 거부📖 프로세스 시작거부
시작 거부를 위해서는 다음과 같은 정보를 미리 알고있어야 한다.
1. 모든 자원의 개수(R)
2. 현재 사용가능한 자원의 개수(V)
3. 프로세스가 요구하는 자원의 개수(C)
4. 현재 할당받아 점유하고 있는 자원의 개수(A)
시작 거부에서는
R>= 모든 프로세스가 요구하는 자원 + 새롭게 실행할 프로세스가 요구하는 자원
인경우에 실행이 가능하다.
만약 R 벡터를 알수가 없다면 A+V 벡터를 더한다면 R을 구할수가 있다.📖 자원 할당 거부
은행원 알고리즘을 활용하며 요약하자면 일당 실행을 시키고 그뒤에 줄지 말지를 정한다.
은행원 알고리즘은 시스템의 상태를 안전한 상태와 불안전한 상태로 구분한다.
<안전한 상태>
현재 할당 가능한 자원을 어떤 프로세스에게 줬을때
모든 프로세스들이 종료가 가능한 경로가 존재한다면 이는 안전한 상태이다.
<불안전한 상태>
현재 할당 가능한 자원들을 어떤 프로세스에게 줬더라도
모든 프로세스가 종료 가능한 경로가 존재치 않는다면 이는 불안전한 상태이다.📖 안전한 상태
C-A는 현재 필요한 자원의 개수이다. 이 자원만 할당해준다면 프로세스는 종료가 가능하다.
현재 사진에서 P2가 종료가 가능하고 종료시 Claim된 자원전부를 반납한다.
P2 종료후 Available vector는 6 2 3 이되며 이 다음에 종료가 가능한 프로세스를 찾아야한다.
이때 보통 번호순으로 진행이 된다.(알고리즘에서 반복은 for을 보통 쓰기에)
다음에 종료가 가능한 프로세스는 P1이며
프로세스 종료후 Availavle vector는 7 2 3이 되며 이런식으로 P3 P4도 종료가 가능하다.
이렇게 모든 프로세스가 종료가 가능한 상태를 안전한 상태라 한다.📖 불안전한 상태
현재 상태는 안전한 상태이자 여기서 조금만 값을 바꿔보자.
P1이 R1과 R3 자원을 하나 사용한다면 종료할수 있는 프로세스가 없어지며
데드락이 걸려버릴수가 있는 불안전한 상태이다.
이렇게 P1에서 R1,R3를 하나씩 더 주는것과 같이 만드는 방식을 거부하는 것이
자원 할당 거부방식이다.📖 알고리즘 코드
<전역 자료구조>
struct state{
int resource[m]; /* 자원 벡터 */
int available[m]; /* 가용 벡터 */
int claim[n] [m]; /* 요구 행렬 */
int alloc[n] [m]; /* 할당 행렬 */
}
<자원할당 알고리즘>
if (alloc [i,*] + request [*] > claim[i,*])
<에러(error)>;
/*지금 쓰는 자원 + 새롭게 요청하는 자원이 처음에 쓰기로한 자원보다 크냐?
더 크다면 처음에 쓰기로한 자원 개수 약속을 지키지 않았기에 에러다*/
else if(request [*] > available [*])
<프로세스 일시중지>;
/*사용 가능한 자원보다 더 많은 걸 요구한다면 프로세스를 suspend 시킴 자원이 준비될때 까지*/
else {
<새로운 상태(newstate)로 전이:
alloc [i,*] = alloc[i,*] + request [*];
availavle[*] = available [*] - request [*]>; //일단 자원주고 생각해
}
if(safe(newstate))
<자원할당 수행>;
else {
<원상태 복구>;
<프로세스 일시중지>;
}
<안전한지 아닌지 확인(은행원 알고리즘)>
boolean safe(state s){
int currentavail [m];
process rest[<number of processes>];
currentavail = available;
rest = {all processes};
possible = true;
while(possible){
<find a process Pk in rest such that
claim [k,*] - alloc [k,*]<=currentavail;
if(found) {
currentavail = currentavail + alloc [k,*];
rest = rest -{Pk};
}
else possible =false;
return (rest==null);
/*
앞서 말로 풀었듯이 하나씩 요구하는 자원 주면서 모든 프로세스가 종료 가능한지 검사해봄
검사후 모든 프로세스가 종료 된다면 true 리턴
*/
}
📖 단점
1. 프로세스가 실행할 최대 자원의 개수를 OS가 알고 있어야한다.
- if문을 통해서 특정 상황에서만 자원을 많이 쓰는등의 경우가 있음에도 반드시 최대 개수필요
2. 자원의 개수가 고정되어야한다.
- 앞에서 본 재사용 불가능한 자원처럼 자원의 개수가 변한다면 안된다.
3. 시간이 굉장히 오래걸린다.
- 코드만 보면 간단한 것 처럼보이나 실제로 검사해야할 프로세스가 굉장히 많다.
그렇기에 반복문으로 모든 프로세스들이 실행이 가능한지 계속 검사하는것은 비효율적이다.📚 데드락 발견(Deadlock Detect)
실제 데드락의 90%는 두 프로세스 사이에서 발생한다.
두 프로세스가 가지고 있는 자원이 사용불가가 되고 이것이 다른 프로세스에 영향을 미치기 시작하면서
전염병처럼 모든 프로세스들을 마비 시켜버릴수 있다.
교착상태 발견은 프로세스가 요구하는 자원을 일단 준뒤 데드락이 발생하면
빠르게 데드락 발견후 조치를 취하여 시스템 전체에 데드락이 발생하는걸 막겠다는 뜻이다.
이를 위해 주기적으로 데드락이 발생했는지 검사하고
발생시 회복 알고리즘을 통해 해결한다.📖 데드락 발견 알고리즘
앞서 살펴본 데드락 회피와 비슷하다.
다만 여기서는 가용 벡터를 계산하여 임시 벡터로 만든뒤에 사용한다.
1. 할당 행렬에서 행의 값이 모두 0인 프로세스를 우선 mark 한다.
2. 임시벡터 W를 만든다. 현재 사용가능한 자원의 개수를 임시벡터 W의 초기값으로 설정한다.
3. 표시되지 않은 프로세스들 중에서 요청하는 값이 임시벡터 W의 값보다 작으면 mark한다.
4. 단계 3의 조건을 만족하는 프로세스를 찾는다면 임시벡터 W에 프로세스가 가지고 있던 자원을 더한다.
3~4번 과정을 더이상 표시할 프로세스가 없어질때까지 반복한다.
만약 이과정이후에 남아있는 프로세스가 존재한다면 해당 프로세스는 "데드락"에 빠진상태이다.
<예시>
위 상황을 예시로 들어보자.
1. 모든 할당이 0인 P4를 mark한다.
2. 가용 벡터(위에서 임시벡터 W)를 가지고 현재 자원을 주면 끝낼수 있는 프로세스를 찾는다.
3. P3가 종료 가능하니 종료후 P3에게 할당되었던 벡터를 돌려받는다.(W 00011로 바뀜)
4. 이후 종료가능한 프로세스가 없다.
P1과 P2는 데드락 상태이다.
위와 같은 과정으로 찾으며 만약 동시에 두 프로세스 이상이 종료가 가능하다면
오름차순으로 먼저 종료시켜준다.
📖 데드락 회복 알고리즘
데드락을 발견하면 이를 해결하기 위한 방법이 필요하다.
다음과 같은 방법을 사용하여 회복한다.
1. 데드락이 생긴 프로세스를 그냥 종료한다.
- 이게 뭔 방법이냐 싶겠지만 상당히 자주 사용되는 방법이다.
2. 데드락 상태에 포함되어 있는 프로세스를 롤백한다.
- 데드락 발견 과정에서 통과되었다면 그 상황은 데드락이 발생하지 않는 상황이다.
- 따라서 위 상태를 저장후 데드락이 발생하였다면 롤백한다. 다만 다시 데드락이 발생할 가능성이 있다.
3. 데드락 상태가 없어질때 까지 한 프로세스식 종료한다.
- 데드락은 원형 사이클 때문에 발생한다.
- 따라서 모든 프로세스를 종료하기 보단 사이클을 깨지게 하는 프로세스가 나올때까지 하나씩 종료해본다.
4. 데드락이 없어질때까지 데드락에 포함되어 있는 자원들을 하나씩 회수후 다른 프로세스에 할당시킨다.
- 선점후 다시 발견알고리즘을 통해 데드락상태에 빠졌는지 확인한다.
- 위 과정을 반복하여 데드락 상태에서 벗어날때까지 한다.
학생