[운영체제 5주차] 하루 30분 컴퓨터 과학 공부하기

---

전통적 동기화의 예제

이번에는 전통적 동기화의 예제 세 가지에 대해서 볼 것이다.

 

1. 생산자-소비자 문제(Producer and Consumer Problem)

2. 공유 데이터 베이스 접근(Readers-Writers Problem)

3. 식사하는 철학자 문제(Dining Philosopher Problem)

 

첫 번째로 볼 것은 생산자-소비자 문제이다.

생산자가 데이터를 생산하면 소비자는 그것을 소비할 수 있다. 생산자와 소비자의 생산과 소비 속도가 항상 일정하지 않기 때문에 중간에 bounded buffer가 존재하며, 생산자는 생산한 데이터를 버퍼에 저장하고, 소비자는 버퍼에서 데이터를 꺼내서 소비한다. 현실 시스템에서 이 버퍼의 사이즈는 유한하다. 이 유한성 때문에 문제가 생기게 된다.

생산자는 버퍼가 가득차면 더이상 데이터를 넣을 수 없고, 소비자는 버퍼가 비면 뺄 수 없다. 

이를 우리가 전에 배웠던 세마포를 사용해서 해결해보자.

 

생산자 소비자 버퍼의 관계

 

우리가 해결해야 될 문제는 총 3가지이다. 우선은 공통변수인 버퍼에 동시 접근해서 임계구역 문제가 발생하지 않도록 상호 배타적으로 처리할 수 있는 세마포가 필요하다. 그리고 버퍼가 꽉 찼을 때 생산자가 빈 공간이 생길 때까지 기다리도록 해주는 세마포가 하나 필요하고, 버퍼가 비었을 때 찬 공간이 생길 때까지 소비자가 기다리도록 해주는 세마포가 필요하다. 

생산자 소비자 문제 해결 with 세마포

3가지 세마포가 위의 문제를 해결한다. mutex.val은 상호 배타의 문제를 각 각 producer와 consumer의 상위에 두어 동시에 들어가지 않도록 체크하고 임계 구역을 지나서 relase해서 다음 쓰레드가 실행되도록 해준다. 

empty.val은 버퍼의 사이즈로 버퍼의 size가 0이 되었을 때 producer가 블록되도록 한다. full.val은 버퍼에 데이터가 0일 때 producer가 데이터를 생산할 때까지 consumer가 블록 되도록 하는 역할을 한다. 

 

두 번째로 볼 것은 공유 데이터 베이스 접근 문제(Readers-Writers Problem)이다. 사용자가 데이터를 사용할 때 데이터를 작성하는 Writers가 있고 데이터를 읽는 Readers가 있다. Readers는 데이터를 변경하지 않기 때문에 다수의 Readers가 한 번에 데이터 베이스에 접근해도 임계구역 문제가 발생하지 않는다. 하지만, Writers 같은 경우 데이터를 변경하기 때문에 이 경우에는 임계구역 문제가 발생하지 않도록 Writers는 한 번에 한 개의 프로세스만 접근 가능하도록 한다.

공유 데이터 베이스 접근 문제

마지막으로 볼 것은 식사하는 철학자 문제(Dining Philosopher Problem)이다. 아래와 같이 철학자 5명이 5개의 젓가락을 사용해서 밥을 먹는다고 생각해보자. 철학자는 주로 생각을 하다가 배고플 때만 밥을 먹는다. 식사를 위해서는 2개의 젓가락이 필요하다. 따라서, 젓가락은 세마포로 한 번에 한 철학자만 접근 가능하도록 해야 된다. 철학자가 식사할 때 왼쪽 젓가락 먼저 들고 오른쪽 젓가락을 들어서 밥을 먹도록 한다. 

철학자 - 젓가락

초반에는 철학자가 돌아가면서 밥을 잘 먹는 것 같다가 갑자기 프로그램이 중단되는 현상이 발생한다. 이유가 무엇일까? 그 이유는 바로 모든 철학자가 동시에 식사를 할 때이다. 모든 철학자가 동시에 왼쪽 젓가락을 들면 모두 오른쪽 젓가락은 모두 할당되어 있는 상태이기 때문에 모두 밥을 먹을 수 없고 결국 철학자는 모두 굶게 되는 현상이 발생한다. 이를 교착상태(Deadlock)라고 한다.

 

---

교착상태(Deadlock)

 

교착상태는 사실 잘 발생하지 않는 문제이고 이러한 현상이 발생하기 위해서는 필요 조건 4가지가 있다. 물론, 이 4가지를 모두 충족시킨다고 하더라도 교착상태가 발생하지 않을 수 있다. 필요 조건에서 1가지라도 충족하지 않으면 교착상태는 발생하지 않는다. 

*필요조건 : 어떠한 일이 발생하기 위해서 필수적으로 갖추어야 되는. 하지만, 조건을 갖추었다고 조건이 무조건 발생하는 것은 아님. (<-> 충분조건) 

 

교착상태의 필요 조건 4가지

- 상호배타(Mutual Exclusion)

- 보유 및 대기(Hold and Wait)

- 비선점(No Preemption)

- 환형대기(Circular Wait)

환형 대기의 자원 할당도

 

*자원 할당도

어떤 자원이 어떤 프로세스에 할당되어 있는지를 알 수 있는 그래프

자원 : 사각형, 프로세스 : 원, 할당 : 화살표

자원 할당도A, 자원 할당도B

자원 할당도A에서는 P2가 R1 자원을 사용하기 위해서 요청한 상태이고, P1이 현재 자원을 사용하고 있다.

자원 할당도B에서는 R1의 자원을 P1이 요청하고 있고, P2가 자원을 할당받은 상태이다. R2의 자원은 2개이며, 각 각 P1과 P2에 할당되어 있다. P2는 R3의 자원을 요청하고 있고, P3에 R3의 자원이 할당되어 있다. R4자원은 총 3개이며 어떤 곳에도 요청 및 할당이 되어 있지 않다. 

 

교착 상태를 처리하는 방법 4가지

- 교착상태 방지 : 필요조건의 중 한 가지 이상 불만족

- 교착상태 회피 : 자원을 안전하게 할당할 것

- 교착상태 검출 및 복구 : 교착상태 허용, 주기적 검사, 교착 상태 발생 시 복구 -> 문제 : 검사에 따른 추가 부담(overhead)

- 교착상태 무시 : 교착 상태가 잘 일어나지 않으니 그냥 무시하기...