[운영체제] 6. 데드락

Preemtable : 사용 도중 자원을 다른 프로세스에게 줄 수 있는 자원 / 메모리, CPU

Nonpreemtable : 실행도중 다른 프로세스에게 줄 수 없는 리소스 -> 데드락 발생 -> 안걸리게 할 수 있다.

 

<리소스를 대표하는 자원이 세마포어로 설정>

b : 자원이 2개라면 down : 1,2 요청하고 -> 쓰고 -> 2,1 순으로 해제

 

<데드락 프리>

리소스 1에서부터 경쟁 -> 이긴 프로세스가 2까지 가져가서 작업, 진 프로세스는 sleep -> 이후 해제하면 진 애가

 

<잠재적 데드락 가능>

a가 1받고 이제 2 받아야 하는데 b가 2를 이미 받았다면 -> 둘 다 sleep : 이 상황이 deadlock
->그럴수도, 그러지 않을 수도 있음. 즉 잠재적으로 일어날 가능성이 있다.

<교차로의 꼬리물기 상황>

데드락 상황 : 집합에 있는 각 프로세스가 다른 프로세스가 발생시킬 수 있는 이벤트를 기다림. 이 때 이 이벤트가 일어날 수 없기 때문에 데드락에 걸린 상태

 

- 데드락의 조건

1. 자원은 독점 사용

2. 자원 할당 받은 후 또 다른 자원 받기 위해 기다림

3. 비선점 형태

4. 여러 프로세스가 필요한 자원을 요청하다보면 사이클이 생김

<데드락 모델링 : 데드락 발생 확인을 위해 모델링을 해봐야 함>

a : 리소스 R이 a에게 할당됨

b : 프로세스 B가 자원 S 요청(필요로 한다)

c : D는 T점유 U요청 / C는 U점유, T요청 -> 사이클 발생 = 데드락 발생

 

d의 순서를 보면

A - R할당

b - S할당

C - T할당

--------

A - S요청 but B가 점유 중

B - T요청 but C가 점유 중

--------

C -R요청 but A가 점유중 -> 이 때 사이클이 발생하여 데드락 발생

-> 실행 순서에 의해 데드락이 발생할 수도 있음

 

A - R,S 할당

C - T할당

----------

C - R 요청 : A가 필요한거 전부 받았으니 진행 끝내고 자원 반납하면 C에게 할당 -> 데드락이 안생길 수는 있음

그러나 위험한 상황. 데드락은 절대 발생하면 안되는 상황. 항상이 아니라 어쩌다 데드락이 발생하면 디버깅이 어려움.

 

데드락 처리방안

1. 무시(타조알고리즘)

2. 데드락 감지(사이클 감지하거나 뱅커스 알고리즘) 후 복구(하나 선택해서 kill하고 자원 뿌림)

3. 데드락 어보이던스 : 자원 요청이 오면 banker's 알고리즘으로 미리 검토하여 데드락 발생한다고 판단되면 승인 안하는 것

4. 예방 : 데드락 조건 4가지 하나라도 일어나지 않게 함. 

 

1. 디텍션 : 그래프를 이용하여 사이클이 아닌 것을 제거

-> 사이클이 남아 있으면 데드락 발생하는 것으로 판단, 자원의 종류가 늘어나면 그림 그리기 어려움

그래서 매트릭스로 표현 -> 이게 뱅커스 알고리즘

 

프로세스 : 0~4 / 자원 : A~C,
Allocate : 현재 할당받은 상태에 대한 매트릭스

MAX : 각 프로세스가 진행할 때 필요한 최대 자원의 개수에 대한 매트릭스
Available : 현재 시스템에서 갖고 있는 자원의 개수

Need : 앞으로 몇 개 필요한가. Max - Allocate

Available 테이블을 보고, p0-4 프로세스를 수행시킬 방법이 존재하느냐 = 자원할당 시퀀스가 존재하느냐 판단해야함.

-----------------------------

1. P0는 현재 Available로 실행 불가 -> P1이 되니까 1에게 Av준 후 실행 끝나면 회수

2. 이제 P3에 할당 -> 자원 반납하면 P4 P2 P0 순서대로 다 해주면 safe state가 됨.

-> 가용 자원을 가지고 실행중인 프로세스가 진행 가능하도록 하는 자원 할당 시퀀스가 존재하면 safe state

-----------------------------

Req P1 : 1번에 1,0,2 요청 -> 3,0,2가 됨 -> 남은 2,3,1 가지고 1에게 주면 가능 : 시퀀스가 존재

Req P4 : 4번에 3,3,0 요청 -> 3,3,2가 됨 -> 남은 0,0,3 가지고 충족시킬 시퀀스 없음 : unsafe -> deadlock

 

 

데드락 회복 방법

1. preemption(선점) : 다른 프로세스 자원 뺏어오기

2. 롤백 : 프로그램 동작 중간에 체크포인트를 남기면서, 데드락 발생시 이 위치로 돌아감 -> 한정적 특수 케이스

 

 프로세스 A,B존재

A는 프린트 할당 -> 플로터 할당 -> 플로터 해제 -> 프린트 해제

B는 플로터 할당 -> 프린트 할당 -> 프린트 해제 -> 플로터 해제

a실행(q) -> b실행(r) -> A가 프린트 할당 받음 (s)-> t로가면 플로터를 B가 받으므로 데드락 발생

-> 할당 주체가 그래프로 데드락을 알 수 있으므로 B에게 플로터를 할당해주지 않음

 

 

 

데드락 prevention

 Circular Wait Condition - 번호 부여

낮은 번호순 부터 자원을 요청하도록 하면, 서큘러 웨잇 상황이 발생하지 않음.

-> 어렵다. 컴퓨터시스템은 자원이 너무 많아서 다 순서대로 할당하라고 강제  불가능.

1. 노 프림ㅍ션 -> preemption 가능한 자원으로 만들기 -> 운영체제는 프로세스가 반드시 자원을 해제하고, 다시 사용할 때 요청하도록 해야함

2. 상호배제 -> 독점적으로 사용하지 않게끔 : ex)  프린터 스풀러

3. Hold and Wait -> 한번에 자원을 할당 : 거의 불가능, 자원 utilization이 떨어짐, 어떤 리소스가 필요한지 프로그래밍 시점엔 알 수 없음

-> 많이 쓰는 프로세스는 순위가 밀려 starvation 발생

표로 정리하면 이렇게 되겠지.

1 : 실행과 동시에 프로세스가 필요한 만큼 할당

2 : 할당 순서를 정해주는 것. 리소스 오더링

3 : 메인메모리는 선점 가능하게.

4 : 내부 리소스는 오더링

-> 여러 방법을 써서 데드락이 일어나지 않도록 함.

 

two pase locking : 각각 레코드에서 순서대로 lock을 검. 실패하면 처음부터 다시.

커뮤니케이션 데드락 : 서로 전송하려고 버퍼를 채움 -> 받을 수가 없네? : 사실은 송수신버퍼는 분리. 생각지도 못한 데드락

라이브락 : 서로 다음 자원 달라고 call중 -> 실행은 되는데 진행은 되지 않음

starvation : 죽인 프로세스가 다시 새로 실행되면 또 데드락 발생하는 케이스.