DeadLock - (5)

1. DeadLock 이란

 

1) DeadLock 은 각자의 프로세스가 자원을 점유하고 있으면서 다른 프로세스가 점유한 자원을 기다리며 block 된 교착 상태를 말한다.

 

2) Resource(자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념

ex) I/O device, CPU cycle, memory space, semaphore 등

• 프로세스가 자원을 사용하는 절차

Request(요청) → Allocate(할당) → Use(사용) → Release(방출)

 

※ Resource-Allocation Gragh (자원 할당 그래프)

 

- 프로세스와 자원의 요청 및 할당 관계를 표시한 그래프다

=> 순환 대기 조건을 발견하기 위한 목적으로 사용한다

 

 

---

 

2. DeadLock 의 발생 조건(=이유)

 

1. Mutual Exclustion (상호 배제)

항상 한 프로세스만이 하나의 자원을 사용할 수 있다 → 자원 독점 현상 발생

 

2. Non-preemptive (비선점)

프로세스는 자원을 스스로 반납할 분 강제로 빼앗기지 않는다

 

3. Hold and wait (보유 대기 or 점유 대기)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다

 

4. Circular wait (순환 대기)

자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다

ex) 프로세스 번호 0 부터 n 까지 있을때

 

 

---

 

 

3. DeadLock 처리 방법

 

대부분의 운영체제(Unix 계열)는 교착 상태 발생을 무시한다. 사용차가 처리하게 냅둠.

-> 무시는 해결 방법이 아니라고 생각해서 목차에 넣지 않았다

=> 실제로 처리하는 프로그램의 작성은 SW 개발자의 책임이라고 한다...ㄷㄷ

 

1. DeadLock Prevention (교착 상태 예방)

 

- 교착 상태 발생 조건 중 1가지가 만족되지 않도록 하는 방법

 

1) 상호 배제 예방 : 동시 접근하는 자원에 대한 상호배제를 무시. - 일반적으로 허용되지 않는 방법이다

 

2) 비선점 예방 

1. 프로세스가 어떤 자원이 필요해서 요청 대기 상태에 빠지게 될 경우 이미 보유한 자원들을 해제해버리고 모든 필요한 자원을 얻을 수 있을 때 그 프로세스가 다시 시작되게 한다
2. 프로세스 대기줄에 끼어들어서 선점해버리기~

→ State를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용한다(CPU, memory)

 

3) 보유 대기 예방

1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청하는 방법

ex) 두 개의 critical section 을 하나의 critical section으로 묶어서 처리하는 방식을 이용하면 점유하여 대기하는 것을 방지할 수 있다.

→ 효율이 많이 떨어지기 때문에 좋은 해결 방법은 아니라고 한다.

 

4) 순환 대기 예방 : 프로그래밍에서 적용할 수 있는 현실적인 방법. 핵심은 lock을 걸어주는 타이밍을 잘 조정하는 것이다.

ex) 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당

 

=> 교착 상태 예방은 Starvation, 자원의 이용률 저하(Utilization 저하), 시스템의 성능 저하(throughput 감소) 등이 발생할 수 있다 = 그냥 비효율적이다

 

 

 

2. DeadLock Avoidance (교착 상태 회피)

 

 

- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock 가능성이 없는지를 동적으로 조사해서 안전한 경우에만 자원을 할당.

- 시스템 state 가 원래 state 로 돌아올 수 있는 경우에만 자원 할당 (unsafe state X)

 

=> 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다

 

▶ 안전 상태 (safe state)

• 시스템 내의 프로세스들에 대한 safe sequence 가 존재하는 상태

▶ 안전 순서열 (safe sequence)

• Pi (sequnce<P1 ... Pn>) 의 자원 요청이 가용 자원 + 모든 Pj(j < i)의 점유중인 자원에 의해 충족되는 순서열

 

 

▷ 교착상태를 피하는 2가지 알고리즘

 

1. 자원 할당 그래프 알고리즘 - 자원 타입 당 사용할 수 있는 인스턴스가 하나일 경우 사용

 

자원 할당 그래프 알고리즘 에는 요청 화살표(request edge), 할당 화살표(assignment edge)에 더하여 클레임 화살표(claim edge)의 개념이 더 추가 된다.

 

클레임 화살표는 프로세스가 미래 언젠가 자원을 요청 할 수도 있다는 것을 나타낸다.

이것을 이용해서 자원의 요청이 들어와도 프로세스들이 서로 보유한 자원을 고려해서 점유되어 있지 않은 상태더라도 할당을 바로 해주지 않고 대기시킨다.

 

**안전 상태에서 프로세스가 작업을 처리하기 위해 필요한 전체 자원의 수가 요청 시 추가 요구 되는 정보였다면, 이번에는 클레임 화살표가 추가 요구 되는 정보다.

 

 

 

1. 은행원 알고리즘

 

    ※ 은행원 알고리즘 구현을 위해 필요한 자료구조

 

• Available(가용 자원) : Available[자원 타입] 로 정의되는 1차원 배열.
  • 각 자원 타입마다 현재 사용 가능한 개수를 저장한다.
• Max(최대 요구가능 자원) : Max[프로세스 , 자원 타입] 로 정의되는 2차원 배열.
  • 각 프로세스가 요구할 수 있는 최대 자원 개수를 나타낸다
• Allocation (현재 할당 자원) : Allocation[프로세스, 자원 타입] 로 정의되는 2차원 배열.
  • 각 프로세스 별 현재 할당되어 있는 자원, 현재 할당되어 있는 자원의 개수를 나타낸다
• Need (필요 자원) : Need[프로세스, 자원 타입] 로 정의되는 2차원 배열.
  • 각 프로세스 별 작업을 완료하기 위해 추가로 필요한 자원의 개수를 나타낸다

 

**Available 이 Maximum 을 충족할 때 프로세스에 우선 순위를 주게 된다고 한다

 

 

3. Deadllock Detection (교착 상태 검출)

 

- OS 가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법이다. 가장 현실적인 교착상태 해결방법!

 

 

1) 자원 타입 당 single instance 인 경우 => 자원할당 그래프 알고리즘 & Wait-for 그래프(= 자원할당 그래프의 변형) 사용

 

 

2) 자원 타입 당 multiple instance 인 경우 => Banker's algorithm 과 유사한(= 더 낙관적인) 방법 활용

3) 타임 아웃: 일정 시간 동안 작업이 진행되지 않는 프로세스를 교착상태가 발생한 것으로 간주하여 처리하는 방법

• 가벼운 교착 상태를 검출할 수 있다
• 엉뚱한 프로세스가 강제 종료될 수 있다
• 모든 시스템이 적용할 수 없다

-> 하지만 데이터베이스와 운영체제에서 많이 선호한다 ex) Window, Oracle ..

=> 데이터의 일관성이 깨지는 문제를 해결하기 위해서 체크 포인트와 롤백을 사용!

 

4. Deadllock Recovery (교착 상태 회복)

 

1) Process termination (프로세스 종료)

 

• 교착상태를 일으킨 모든 프로세스를 동시에 종료한다
• 교착상태가 해결될때 까지 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료한다

 

2) Resource Preemption (자원 선점화)

 

1. 비용을 최소화할 victim 선정해서 자원 뺏기
2. safe state 를 rollback 하여 process를 restart

 

- Starvation 문제

• 동일한 프로세스가 계속해서 victim으로 선정되는 경우
• cost factor에 rollback 회수도 같이 고려