[운영체제] 5. Concurrency: Semaphores and Deadlock2

Common Concurrency Problem

프로세스를 병렬적으로 처리하면 처리율이 증가한다는 장점이 있찌만 여러가지 병행성 문제가 발생할 수 있어 이를 잘 관리하여야 한다.

 

 

Non-deadlock bug

① Atomicity-violation bug: lock을 이용하여 원자성을 보장하는 형태로 해결한다.

② Order-violation bug: condition variable을 이용하여 해결한다. (lock의 보조 필요)

 

Deadlock bug

여러 쓰레드들이 절대 발생하지 않을 상황을 기다리며 무한히 대기하는 상태이다.

데드락의 필요 조건

1. 상호 배제
2. 점유 대기
3. 자원 비선점
4. 환형 대기

 

 

데드락의 해결책

1. 데드락 예방: 데드락의 필요 조건 4가지 중 하나를 해결하여 데드락을 미연에 방지한다.

① 상호 배제: lock free 방식으로 lock을 사용하지 않고 상호 배제를 보장한다.

counter의 lock based 구현과 lock free 구현

② 점유 대기: 모든 lock을 원자적으로 수행하게 만든다. 더 큰 lock으로 모든 lock을 잡거나 못잡게 되는 형식.

③ 자원 비선점: 다른 lock을 잡지 못했다면 잡고 있던 lock을 선점한다.

live lock이 발생할 수 있다는 문제점이 있다

live lock이란? 쓰레드가 뭔가 바쁘게 해결하려고 분주히 움직이지만 절대 해결되지 않는 상태이다.

④ 환형 대기: 락을 잡는 것에 모두 순서를 부여한다.

 

2. 스케쥴링을 통한 데드락의 회피

① 데드락 소지가 있는 쓰레드를 같은 CPU에 위치시켜 동시에 수행되어 데드락이 되는 경우를 줄인다.

lock contention이 증가할 경우 load balancing이 되지 않는다.

 

② Banker's alogithm: safe 상태를 유지할 수 있는 요청만 수락한다.

예시. 위에서 각 쓰레드들은 초기에 자원을 갖고 있지 않고 Max 만큼의 자원을 얻게 되면 종료가 된다. 초기 전체 시스템에 10개의 자원이 존재한다. 상태1에서는 총 8개의 자원이 각 쓰레드에 배분되어 2개가 남아있다. 이 상태에서 남은 두개의 자원을 C, D에게 주는건 safe한 상태를 유지하는 요청이다. C나 D가 종료되어 갖고 있던 자원을 반환하게 된다. 하지만 A나 B에게 주는건 unsafe하다. 이렇게 되면 데드락이 발생할 수도 있다. 맨 우측의 상태2가 자원을 잘못 배분하여 unsafe한 상태가 된 모습이다. 

 

3. 데드락을 발견하고 해결: 데드락이 발생할 경우 단순히 프로그램을 종료시킨 뒤 재실행 하는 방식으로 해결한다.

* 자원 할당 그래프(RAC; Resource Allocation Graph)

쓰레드(프로세스)는 원으로 표시하고, 자원은 네모로 표시한다. 그리고 쓰레드에서 자원으로 화살표 방향이 위치한다면 이는 자원을 갖고 싶다는 요청이다. 그리고 자원에서 쓰레드로 화살표 방향이 위치한다면 이는 쓰레드가 해당 자원을 갖고 있음을 의미한다. 전체 시스템에 대하여 해당 그래프를 그리고 환형이 있을 경우, 데드락이 발생할 수도 있다.