운영체제의 기초 - 12. Deadlock

What is Deadlock?

내용 정리

Process Synchronization은 여러 Process가 Concurrent하게 수행하면서 shared resource를 가지고 있을 때

또는 shared data를 접근하려고 할 때 그것을 관리하는 메커니즘

여러 프로세스가 shared data 접근하는 것을 막지 못하면 race condition 발생

race condition은 concurrent 프로그램의 버그

race condition이 발생하지 않겠끔. OS은 primitive를 제공해줘야 하는데

- interrupt disable / enable

- Bus Transaction을 read, modify, write를 하나의 트랜잭션으로 만들어주는 기법 (TAS)

- 그것을 기반으로 해서 S/W적 메커니즘인 세마포어가 있고

- 세마포어를 기반해서 monitor 라는 synchronization 기법들도 있음

이중에서 OS이 맡고 있는 부분은 Synchronization 중 세마포어

나머지는 H/W primitive 고 

monitor는 프로그램 랭기지가 제공해주는 메커니즘(컴파일러가 monitor가 나오게 되면 P/V() operation으로 conversion해줌

막아야 하는 방법 2가지

1. 예방하는 방법

2. 발생했을 때 증상을 최소화 하는 방법

대부분의 경우 데드락은 자원 공유에서 발생함

Resource Allocation Graph

- 사각박스: 프로세스

- 둥근박스: 자원

- 자원 >> 프로세스: 자원이 프로세스에 할당되었음을 표현

- 프로세스 >> 자원: 프로세스가 자원을 사용하기 원하는 상황을 표현

Resource Allocation Graph에 사이클이 존재하면 데드락이 있다: 

Proc0  >>  semaY  >>  Proc1  >>  semaX  >>  Proc0 (자신으로 돌아옴)

Resource Allocation Graph를 사용한 Deadlock 탐지

Cycle이 존재하는 경우 Deadlock이 발생한 상황임을 알 수 있음

단, 자원을 관리하는 Semaphore가 Binary Semaphore인 경우에만 반드시 Deadlock이 발생

--> 단순하고 제한적 상황에서만 데드락을 찾을 수 있음 (자원이 여러개면 데드락이 발생 안한다)

Deadlock: 자원을 공유하는 프로세스들이 서로가 원하는 자원을 분점하고 있기 때문에 더 진행하지 못하는 것

- Deadlock에 관련된 Process는 수행하지 못하지만 Process를 낭비하지 않음 (CPU관점예서)

- 자기가 원하는 resource를 기다리면서 전부 waiting상태에 있기 때문 

- Deadlock의 경우 2개 이상의 process가 있어야 발생

Livelock: 자원을 계속적으로 사용하지만 아무런 일도 하지 못하는 상황

Indefinite postponement: 절대 일어날 수 없는 이벤트를 기다리는 상황

- 혼자서 발생

- ex) 어떤 프로세스로부터 메세지를 기다린다고 할 때, 그 프로세스가 문제가 생겨 terminate되었을 경우 indefinite postponement에 빠지게 된다.

네트워크 bandwidth가 너무 낮아 병목현상이 생겨 서버검색이 느려짐

기가비트 ethernet으로 스위치, 라우터를 바꿨으나 오히려 성능이 낮아짐

- 왜 이런문제가 발생했을까? Livelock 때문

DB서버에 접근하기 위해 리퀘스트를 보내게 되면 DB서버 하단에 붙어있는 네트웍인터페이스카드(NIC)가 인터럽트를 건다

인터럽트 서비스 루틴이 incoming packet을 패킷큐(ip프로토콜이 처리하는 패킷큐)에 껴넣는다 

IP프로토콜 모듈이 TCP처리 모듈을 호출하여 다음 프로세스 처리

궁극적으로 DB operation을 하는 App에게 그 패킷을 넘겨줌

유저레벨까지 갔다가 계산결과를 밖으로 출력하는 현상이 나올 것임

그런데 Badwidth가 너무 커서 패킷이 너무 많이 도착 (인터럽트 과다)

ip큐에서 패킷을 읽기전에(유저레벨에서 데이터 읽어가기 전에) 큐가 꽉참

공간을 비워야됨(있던 것들을 버림)

새로운 패킷으로 채우자마자 또 인터럽트가 들어옴

인터럽트 프로세싱 > 유저프로세싱보다 우선순위 높아 유저 프로세싱이 CPU사용을 못함 

- 이 시스템은 인터럽트만 받아 IP큐에 데이터 패킷만 채우고 버리길 반복 

- 그래서 아무런 서비스를 하지 못함

이런 문제를 "Receive Livelock" 이라고 함

통신에서 발생이 흔한 문제임

그리고 라우터에서 많이 발생하는 문제

문제의 근원: 너무 많은 인터럽트 발생

해결

1. Interrupt Coalescing

2. IP Level에서 패킷이 들어오면 우선순위를 정함(중요한 패킷순으로 처리)

Interrupt Coalescing

Interrupt 발생 빈도를 줄이기 위해서, 여러 번의 입력을 모아서 한번에 

Interrupt를 발생시키거나 일정 시간마다 한번씩 Interrupt를 발생시키는 기법

Deadlock 필요조건 4가지

1. Mutual exclusion: 어떤 한 프로세스가 리소스를 점유하는 데 일단 점유되면 그 리소스는 다른 프로세스에게 공유가 안됨

2. No preemption: 내가 리소스를 장악하면서 상대편 리소스를 원할 때 내 리소스를 포기하지 않는다

3. Hold and wait(Multiple independent requests): 내가 리소스를 가지고있는데 다른 리소스 원하는 상황에서 내 리소스는 점유하면서 원하는 리소스도 계속 원하고 있는다

4. Circular wait: 리소스를 점유하고 원하는 상황이 서클이 되야 한다

Deadlock을 방지하는 방법

1,2 조건의 경우는 프로세스의 특성으로 막을 수가 없다

3,4 조건이 발생하지 않도록 한다

3. 프로세스가 수행을 시작할 때 걔가 사용할 리소스를 미리 다 받는다(하나라도 못받으면 wait함)

    비현실적: 어떤 프로세스가 어떤 리소스를 얼마만큼 필요로 하는지 미리 알 수 없음 

    안다고 하더라도 비 경제적(리소스가 1개만 필요한데 1000을 전부 받음)

4. 프로세스들이 사용할수 있는 시스템의 리소스에 일련번호를 적는다

    리소스번호가 커지는방향으로만 할당받음(사이클의 백워드 엣지를 막는다)

결국 모든 방법들이 데드락을 막기에는 비현실적이다

Deadlock을 처리하는 방법

1. Prevention(예방): 아예 Deadlock이 생기지 않도록 원천적으로 막는 것

2. Detection and recovery: Deadlock 상황이 발생하면 그 상황을 바로 인지해서 Deadlock을 깨버리는 방법

Deadlock Prevention and Detection

Prevention 중 가장 유명한 방법 Banker's Algorithm

프로세스가 System에 존재하는 자원들을 점유하고 있으면 그 상태를 2가지로 나누는 방법

Banker's Algorithm의 Safe State와 Unsafe State

Safe State: 시스템이 Deadlock 상태에 빠지지 않는 상태

Unsafe State: 시스템이 Deadlock 상태에 빠질 가능성이 있는 상태

남은 리소스를 계산하여 현재 프로세스 중 종료시킬 수 있는 얘를 찾는다

p1이 2개만 더 있으면 되니까 자원할당해줘서 수행을 종료시키고 p1의 자원 회수한다

현재 자원 3->5 로 증가

p0 5개 있으면 수행 종료 가능하니까 자원주고 수행 종료시키고 자원회수

현재 자원 5->10 로 증가

p2도 이제 수행가능함

- safe sequence: p1->p0->p2

- 이런 상태를 safe state라고 한다

- but safe state라고 해서 항상 safe한 것은 아니다.

- 만일 p2가 자원을 하나 더 요구했다면 현재 자원 2로 p1은 종료시킬 수 있으나 p0와 p2가 최대치로 요구할 때 데드락 발생

- 프로세스가 새로 들어오면 최대의 Needs를 선언해야 한다.

- 프로세스가 프로그램을 요청하면 그것을 들어줬을 때 생기는 리소스 상태가 안전한 상태인지를 체크한다.

- 안전하다면 리소스를 응해주고 

- 아니라면 프로세스를 waiting 상태로 만든다.

시스템에 존재하는 프로세스, 시스템에 존재하는 Resource를 표현해야 함

m: 시스템에 존재하는 Resource 개수

n: 시스템에 존재하는 Process 개수

Available[]: 어떤 리소스 i 가 현재 몇개나 있는지를 표현

Max[]: 프로세스 i 가 j 타입의 리소스를 몇 개까지 원하는가?

Allocation[]: 프로세스 i 가 j 타입의 리소스를 몇 개 가지고 있는가?

Need[]: Max-Allocation 향후 몇개의 리소스를 더 원하는가?

Work Array: 어떤 자원의 중간 계산 결과를 저장하고 있는 Array

Finish Array: 어떤 프로세스가 현재 종료되었는지를 나타내는 Boolean Array

- 데드락을 피하기 불가능한 경우 발생한 데드락을 회복시키는 방법 사용

결국 Deadlock avoidance(회피)의 한계점은 비싸고, 비효율적이다

그리고 Deadlock avoidance가 불가능한 경우도 존재한다.

이럴 경우 Deadlock Detection을 한다.

- Resource Allocation Graph를 그려서 사이클이 발생하면 Deadlock이다.

- 그런데 이 알고리즘은 multiple instance가 있을 경우 작동을 안한다.

- Banker's Algorithm을 약간 변경시킨 알고리즘을 이용해서 Deadlock Detection을 하는 것이 이번 슬라이드 내용

보통은 pc에서 사용자가 알아서 데드락 문제 해결(프로세스 킬)

하지만 서버에서는 문제가 됨

이런 복잡한 방법으로 데드락 찾기보단 프로세스의 response-time을 모니터링하는 타임아웃루프를 둔다(흔히 watchdog timer)

종료의 비용이 큰 경우 -> CPR 사용

Checkpoint and Resume (Checkpoint and Restart) - CPR

앱이 동장 중에 일정 시간 간격으로 앱의 모든 상태를 디스크에 저장하고, 

문제가 발생했을 때 저장된 앱의 상태를 사용해 앱의 수행을 재개하는 기법

Checkpoint를 Resume하는 것을 Rollback한다고 표현한다.

강의 정리

Deadlock이라는 것은 흔히 발생하는 상황인데 

어떤 환경에 따라서는 별로 중요하지 않지만 경우에 따라서는 굉장히 중요한 문제다.

특히 mission critical system에서는 중요

Kernel 안에도 lock을 굉장히 많이씀

spin lock, semaphore 등..

Kernel이 Deadlock 상태에 빠지는 경우

일정 시간동안 Kernel이 반응하지 않으면 Watchdog Timer가 동작하여

Kernel을 종료하고 재시작 시킴

---

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=661

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=662