[운영체제 6주차] - 병행 제어 II

반효경 교수님의 운영체제 강의와 Operating System Concepts 10th ed. 를 참고하였습니다.

Semaphore

자원을 얻는 P연산과 V연산을 atomic하게 수행하여 공유 자원을 관리하는 방법

Deadlock and Starvation

• Deadlock
  둘 이상의 프로세스가 서로 상대방에 의해서만 충족될 수 있는 event를 무한히 기다리는 현상

• 서로 다른 프로세스 P0, P1이 S와 Q라는 1로 초기화된 세마포어를 동시에 필요로 한다고 하자.
  P0는 S, P1는 Q라는 자원을 가지고 내어놓지 않으면서 서로의 것을 요청하게 되면 데드락에 빠지게 된다.

• Starvation : indefinite blocking, 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

Classical Problems of Synchronization

Bounded-Buffer Problem (Producer-Consumer Problem)

생산자 프로세스와 소비자 프로세스가 공유 자원인 buffer를 접근할 때 발생하는 상황을 묘사한 문제이다.
각 프로세스가 동시에 들어오는 경우에 race condition이 발생하므로 적절한 lock이 필요하다.
이 문제에서는 empty, full로 대표되는 buffer 자체와 buffer pool에 접근할 수 있는 권한 자체를 공유자원으로 정의한다.

위 그림에서 mutex는 권한 자체, empty/ full이 buffer 자체를 의미한다.

그리하여 위와 같은 코드 흐름으로 버퍼를 관리하게 된다.

The Readers-Writers Problem

데이터베이스가 여러 프로세스 간에 공유되고 있다고 하자. 한 부류의 프로세스는 읽는 데에만 관심이 있고, 한 부류의 프로세스는 쓰는 데에만 관심이 있다.

읽는 프로세스는 동시에 접근하더라도 문제가 없지만 쓰는 프로세스와 다른 프로세스가 동시에 접근하면 문제가 발생한다. 그렇기 때문에 쓰는 프로세스를 중심으로 lock을 걸어서 해결할 수 있다.

위 그림에서 rw_mutex는 writer가 DB에 접근하는 것을 관리하는 세마포어이고, mutex는 read_count를 조작할 때 동시에 count하는 경우를 막기 위한 세마포어이다. 이를 통해, read_count가 1이 아닐 때는(즉, 이미 들어간 reader가 있는 경우에는), mutex를 통해 차례대로 count를 올리고 진입한다. 만약 read_count가 1보다 큰데 writer가 접근한 경우 reader가 모두 빠져나갈 때까지 기다렸다가 진입한다. 그럼 reader는 DB에 접근이 불가능해지고 writer가 다시 rw_mutex를 1로 바꿀때까지 기다린다.

Writer는 reader가 계속 도착하는 경우 들어갈 수가 없기 때문에 Starvation이 발생할 수 있다. 해결하기 위해서는 reader가 일시적으로 접근하지 못하도록 막고, 기다리는 writer들을 진입시키는 방법이 있다.

Dining-Philosophers Problem

위 그림과 같이 5명의 철학자가 원형 식탁에서 중간중간 밥을 먹는데, 자신의 양 옆에 있는 젓가락을 동시에 집어야만 밥을 먹을 수 있다고 하자. 이 문제에서 공유자원은 놓인 5개의 젓가락이다.

위 그림은 철학자가 젓가락을 집는 과정을 나타낸 과정이다. 양 옆에 있는 젓가락을 순차적으로 집어들고, 밥을 먹은다음 다 먹으면 반납하는 과정이다. 그런데 이 코드에는 문제가 있다. 모든 철학자가 동시에 젓가락을 집으면 자신의 왼쪽 젓가락을 집게 되는데, 그 다음부터는 어느 철학자도 오른쪽 젓가락을 집을 수 없다. 아무도 밥을 먹을 수 없기 때문에 반납또한 되지 않는다.

해결방안

• 4명의 철학자만 테이블에 동시에 앉을 수 있도록 한다.
• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있도록 한다. (critical section 처리가 필요하다)
• 비대칭적으로 집도록 하는 방법

Monitor

• Semaphore의 문제점
  • 코딩하기 힘들다
  • 정확성의 입증이 어렵다.
  • 자발적 협력이 필요하다.
  • 한번의 실수가 모든 시스템에 영향
• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
  • 세마포어는 원자적 연산을 제공할 뿐, lock에 대한 구현 책임은 개발자에게 있었다.
  • 하지만 monitor는 공유 자원 동기화를 알아서 보장해준다.

deadlock(교착상태)

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

Deadlock의 4가지 조건(상비보순)

1. Mutual Exclusion(상호 배제): 매 순간 하나의 프로세스만 자원을 사용할 수 있음
2. No preemption(비선점): 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
3. Hold and wait(보유 대기): 프로세스가 다른 자원을 갖고 있는 상태에서 다른 프로세스가 보유한 자원을 기다리는 상황
4. Circular wait(순환 대기): 자원을 기다리는 프로세스 간에 사이클이 형성되어야 함. P0는 P1을 기다리고 P1는 P2를 기다리고 P2는 P0을 기다리는 상황

Resource-Allocation Graph

자원 할당 그래프를 통해 데드락이 있는지 없는지 판단할 수 있다. 사이클의 유무도 파악하기 쉽다.

위 그림에서는 데드락이 발생하지 않았다. 사이클과 무관한 P3이 보유 대기를 하고 있지 않다.

위 그림에서는 P3가 사이클에 관여하고, 보유 대기를 하고 있기 때문에 데드락이 발생한다.

Deadlock의 처리 방법

• Deadlock Prevention: 데드락의 필요 조건 중 하나를 성립하지 못하게 막는 방법
• Deadlock Avoidance: 데드락이 발생하지 않도록 할당 시 추가적인 정보를 이용하는 방법
• Deadlock Detection and recovery: 데드락이 발생하는 지 탐지하여 발생 시 복구하는 방법
• Deadlock Ignorance: 데드락이 발생하도록 방치하는 방법

Deadlock Prevention

• Mutual Exclusion 방지: 원천적으로 불가능한 말이다. 공유 자원 접근에 대한 동기화를 위해 lock을 하는 과정에서 deadlock이 발생하는 것인데, 동시에 접근하도록 만들면 동기화 문제가 발생하게 된다.

• Hold and Wait: 프로세스가 실행되기 전에 필요한 모든 자원을 할당받도록 하는 방법이다. 그럼 부족한 자원을 기다리는 일이 없기 때문이다. 하지만 매우 비효율적이므로 대안으로 생각한 것이 한 프로세스가 자원을 요청할 때 가진 자원을 모두 반납하고 요청하도록 하는 방법이다.

• No Preemption: 한 프로세스가 요청한 자원이 즉각적으로 할당될 수 없는 경우에, 해당 프로세스가 가졌던 자원을 모두 빼앗긴다.

• Circular Wait: 자원을 요청하는 순서를 매기는 방법으로 해결한다.

-> 너무 과한 제한조건으로 Utilization 저하, throughput 감소, starvation 문제 발생

Deadlock Avoidance

Resource Allocation Graph algorithm

자원 할당 그래프에서 점선을 추가하여 해당 프로세스가 미래에 요청할 수 있는 자원을 다 표시한다.
그 점선을 포함하여 사이클이 형성된다면 데드락 가능성이 있기 때문에 자원을 할당하지 않는다.
n개의 프로세스 간 사이클 생성 여부를 조사하려면 O(n^2) 시간이 걸린다.
(DFS를 사용하면 O(V+E)일 것 같은데??)