프로세스 동기화와 관련된 고전적인 문제는 세 가지 정도가 있습니다.
- Bounded-Buffer Problem (Producer-Consumer Problem)
- Readers and Writers Problem
- Dining - Philosophers Problem
오늘은 이 세 가지 문제들에 대해 포스팅하겠습니다.
1. Bounded-Buffer Problem (Producer-Consumer Problem)
버퍼(Buffer)란 데이터를 임시로 저장하는 공간입니다. Bounded-Buffer Problem은 버퍼의 크기가 유한한 환경에서의 문제가 발생하는 것입니다.
위 사진에서는 버퍼가 크기가 유한한 원형 형태로 구성이 되어있습니다. 그리고 프로세스가 생산자(Producer)와 소비자(Consumer)의 두 가지 종류가 있습니다. 그리고 이 두 가지 프로세스는 하나씩만 있는 것이 아니라, 생산자가 여러 개, 소비자가 여러개로 있는 상황입니다. 여기서 생산자 프로세스는 공유 버퍼에다가 데이터를 하나 만들어서 집어넣는 역할을 하게 됩니다.
사진에서 주황색으로 표시된 버퍼들이 데이터가 들어있는 버퍼이고, 아무 색이 없는 버퍼는 내용이 없는 빈 버퍼입니다. 주황색 버퍼들은 생산자 프로세스가 데이터를 만들어 집어넣어 놓은 상태를 나타내는 것이고, 빈 버퍼들은 처음부터 비어있었거나 아니면 생산자 프로세스가 데이터를 집어넣었지만 소비자 프로세스가 데이터를 꺼내가서 비어있는 상황일 것입니다.
그럼 위와 같은 상황에서 동기화와 관련해 어떤 문제가 발생할 수 있을까요?
먼저 한 가지 문제는 버퍼가 공유 버퍼이기 때문에 생산자 프로세스가 동시에 도착해서 비어있는 버퍼를 보고 그 위치에 동시에 데이터를 집어 넣으면 문제가 생길 수 있습니다. 지난 포스팅까지 살펴본 동기화 문제와 비슷한 유형입니다.
그래서 생산자 프로세스가 비어있는 버퍼를 확인하고 그 데이터를 만들어 집어넣는 작업을 할 때에는 공유 버퍼에다가 Lock를 걸어서 다른 프로세스들의 접근을 막은 다음, 비어있는 버퍼에다 데이터를 집어넣고 작업이 끝나면 Lock을 풀어 다른 프로세스가 이 공유 버퍼에 접근할 수 있게 해야 합니다.
그리고 두 번째 문제는 생산자 프로세스가 동시에 도착하는 것이 아니라 소비자 프로세스가 동시에 도착하여 동시에 데이터를 꺼내가면서 생기는 문제입니다. 그래서 이때에도 소비자가 데이터를 꺼내갈 때에는 Lock을 거는 절차가 필요합니다.
위와 다른 성격의 문제가 있는데, 바로 버퍼의 크기가 유한(Bounded) 하기 때문에 생기는 문제입니다. 만약 생산자 프로세스들이 한꺼번에 도착해서 공유 버퍼의 공간을 가득 채웠다고 가정해 보겠습니다. 그런 상황에서 생산자 프로세스가 또 도착해서 데이터를 집어넣고 싶지만 버퍼는 꽉 차있기 때문에, 생산자 프로세스 입장에서는 사용할 수 있는 자원이 없는 상태로 볼 수 있습니다. 이런 상황에서는 생산자 프로세스가 비어있는 버퍼가 생길 때까지, 즉 소비자 프로세스가 데이터를 꺼내갈 때까지 기다려야 합니다.
반대로 소비자 프로세스 입장에서는 데이터가 차있는 버퍼의 개수가 자원의 개수가 될 것입니다. 모든 버퍼가 비워져 있으면 소비자 프로세스는 생산자 프로세스가 자원을 넣기 전까지 기다려야 합니다.
그래서 이 Bounded-Buffer Problem에서는 세마포어를 활용해서 해야할 업무가 두 가지가 있습니다.
첫 번째는 두 가지 프로세스가 동시에 공유 버퍼에 접근하는 것을 막기 위해 Lock을 걸어주어야 합니다. 그리고 두 번째는 버퍼가 가득 차거나 버퍼가 모두 비었을 때, 가용 자원의 개수를 세는 Counting 하는 세마포어 용도의 세마포어 변수가 필요합니다.
그래서 위 사진에서 세마포어 변수로 세 가지를 두는 것을 확인할 수 있습니다. Lock을 걸기 위한 변수 mutex, 내용이 들어있는 버퍼의 개수를 세기 위한 full과 비어있는 버퍼의 개수를 세기 위한 empty가 있습니다.
생산자 프로세스의 의사코드를 보면 먼저 아이템 x를 만든 다음, 버퍼에 집어넣기 전 P(empty) 연산을 통해 비어있는 버퍼가 있는지 확인한 후, 비어있는 버퍼가 있으면 버퍼 전체에 Lock를 걸고 데이터를 집어넣습니다. 작업이 끝났다면 Lock을 다시 풀고 V(full) 연산을 통해 소비자 프로세스의 자원을 하나 증가시켜 줍니다. 소비자 프로세스는 이와 반대로 작동합니다.
이렇게 Bounded-Buffer Problem를 세마포어로 푸는 방법에 대해 설명드렸습니다.
2. Readers and Writers Problem
여기서는 프로세스가 읽는 프로세스와 쓰는 프로세스 두 종류가 있습니다. 그리고 여기서는 공유 데이터를 DB라고 칭하겠습니다.
프로세스는 DB에서 데이터를 읽는 Reader 프로세스와 데이터를 쓰는 Writer 프로세스가 있습니다. 여기서도 Reader 프로세스는 여러 개가 있고 Writer 프로세스가 또 여러개 있습니다.
공유 데이터인 DB에 여러 프로세스가 동시에 접근하면 문제가 생기는 것은 위에서의 문제와 같지만, 한 가지 다른 것은 DB에 데이터를 쓰는 것은 여럿이서 동시에 하면 문제가 생기지만 여럿이서 동시에 읽는 작업은 가능하다는 것입니다.
그래서 위 문제를 쉽게 구현을 한다면, 읽고 쓰는 작업 둘 다 Lock를 걸어 다른 프로세스의 접근을 막을 수는 있습니다. 하지만 이는 비효율적이기 때문에, Writer 작업 시에만 Lock을 걸어 접근을 막는 것입니다. 구체적으로 설명 드리자면, Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 DB에 접근하게 해줍니다. Writer는 대기 중인 Reader가 없을 때 DB 접근이 허용되고 Writer가 DB에서 작업을 수행한다면 Reader들은 접근이 금지됩니다. Writer가 DB에서 빠져나가면, Reader의 접근이 허용됩니다.
아래의 코드를 한번 살펴보겠습니다.
코드에서 DB는 공유데이터이고, 세마포어 변수로 mutex와 db가 선언되어있습니다.
Writer는 공유 데이터에 접근하기위해 P연산을 통해 Lock을 겁니다. 누군가가 DB를 사용하던 중이었다면 P연산을 통과하지 못하고 기다리게 됩니다. 공유 데이터에 쓰는 작업이 끝났으면 V연산을 통해 Lock를 푸는 식으로 진행이 됩니다.
Reader는 위에서 언급한 것처럼 읽는 작업은 여럿이서 동시에 해도 가능하다고 했습니다. 하지만 Reader의 경우에도 데이터에 접근할 때 P연산을 통해 Lock을 거는데, 이것은 만약에 Lock을 걸지 않고 데이터를 읽으면 Writer가 와서 Lock이 걸려있지 않으니 Lock을 걸고 쓰는 경우가 생길 수 있기 때문입니다. 이를 막기 위해 우선 Lock은 걸게 됩니다. 다만 Lock은 걸었지만, 읽기 위해 Lock을 건 것이라면 다른 Reader들이 와도 같이 읽을 수 있게 해야 합니다. 그래서 readcount라는 공유 변수를 두게 됩니다. readcount는 Reader 몇 명이 지금 읽고 있는지를 나타내는 변수입니다. 그리고 공유 변수이기에 변수 값을 변경하는 것은 모든 Reader들이 할 수 있습니다.
그래서 만약 DB에 접근하는 최초의 Reader라면 자신이 처음 들어온 것이기 때문에 DB에 Lock을 걸고 Readcount를 1 증가시킵니다. 이후에 들어오는 Reader들은 Lock을 걸 필요 없이 readcount만 증가시키고 DB를 읽으면 됩니다.
그런데 이 readcount도 공유 변수이기 때문에, 여러 Reader가 동시에 와서 readcount를 증가시킨다면 동기화 문제가 발생할 수 있습니다. 그래서 이 readcount에 대한 lock이 필요한데 여기서 mutex라는 세마포어 변수가 그 역할을 합니다. readcount에 대한 작업 전에 mutex로 lock을 걸고 작업이 끝나면 다시 lock을 푸는 작업이 있게 됩니다.
코드상으로는 Writer가 너무 오래 기다릴 수 있어 starvation의 발생 가능성이 있습니다.
3. Dining-Philosophers Problem (식사하는 철학자 문제)
철학자 다섯 명이 원탁에 앉아있습니다. 다섯 명의 철학자는 생각하는 일과 밥을 먹는 일 두 가지 작업을 수행합니다. 배가 고프면 자신의 왼쪽과 오른쪽에 있는 젓가락을 집어 밥을 먹고, 다 먹고나면 젓가락을 내려놓고 생각하는 일을 반복합니다. 밥을 먹으려면 양 쪽의 젓가락 두 개를 모두 잡아야합니다.
코드는 아래와 같습니다.
왼쪽 젓가락과 오른쪽 젓가락을 얻는 것을 P(chopstick[i])와 P(chopstick[(i+1)%5]로 표현한 것이고, 마찬가지로 젓가락을 놓을 때도 V연산을 수행합니다.
이 코드는 데드락의 위험이 있습니다. 데드락은 지난 포스팅에서 언급을 했는데 더 이상 아무것도 진행이 안되고 막혀있는 상황입니다.
위 상황에서 만약 모든 철학자가 배가 고파져서 왼쪽 젓가락을 잡는다고 하면, 오른쪽 젓가락은 아무도 잡을 수 없고 모두가 식사를 하지 못하는 문제가 생길 수 있습니다.
이 문제의 해결방안은 여러가지를 생각해볼 수 있는데, 우선 4명의 철학자만 테이블에 동시에 앉을 수 있도록 하는 것입니다. 또 비대칭을 고려해서 짝수 철학자는 왼쪽 젓가락만 잡고, 홀수 철학자는 오른쪽 젓가락만 잡도록 하게 하는 방법이 있습니다.
그리고 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 잡게 하는 방법이 있습니다. 아래는 그 코드입니다.
먹기 전에는 Pickup(), 먹고 나서는 Putdown() 함수를 호출합니다. 세마포어 변수 self[5]는 각각 다섯명의 철학자가 젓가락을 양쪽 다 잡을 수 있느냐 없느냐에 따라 권한을 주는 변수이 고, state[5]는 철학자의 상태를 나타내며 생각하는 상태, 먹는 상태, 배고픈 상태로 나눈눕니다.
그리고 mutex라는 세마포어 변수는 공유 데이터의 접근을 막기 위함입니다. 젓가락을 잡는 함수를 호출하게 되면 자신의 상태를 변경하기 전에 다른 철학자가 상태를 변경할 수 없게끔 Lock을 먼저 걸고 배고픈 상태로 바꾼 후, test() 함수로 가게 됩니다. test 함수는 양쪽 철학자가 밥을 먹지 않고, 내가 배고픈 상태의 조건을 만족할 때 젓가락을 잡을 수 있는 권한을 부여합니다.
보통 세마포어라고 함은 자원의 갯수를 1로 시작을 하는데, 이 세마포어는 0으로 시작을 한 후, test()를 진행하는 단계에서 주변 철학자들이 밥을 먹지 않고 있으면서, 배고프면 V()으로 자원을 얻어 1이 됩니다.
지금까지 세마포어 방식을 통해 고전적인 문제를 해결하는 방법에 대해 알아보았습니다. 다음 포스팅에서는 모니터 방식을 소개하겠습니다.
참고자료
[KOCW 이화여대 반효경 교수님 - Process Synchronization 3]
https://core.ewha.ac.kr/publicview/C0101020140408134626290222?vmode=f
반효경 [운영체제] 14. Process Synchronization 3
설명이 없습니다.
core.ewha.ac.kr
[ Chapter5 Operating System Concepts - Abraham Silberschatz ]
https://www.yes24.com/Product/Goods/89496122
운영체제 - 예스24
운영체제
www.yes24.com
'CS > 운영체제' 카테고리의 다른 글
| [운영체제] 7. Deadlocks : 데드락 (Deadlocks 1, 2) (0) | 2024.01.16 |
|---|---|
| [운영체제] 6. 프로세스 동기화 : Monitor (Process Synchronization 4) (0) | 2024.01.16 |
| [운영체제] 6. 프로세스 동기화 : Semaphores (Process Synchronization 2) (0) | 2024.01.15 |
| [운영체제] 6. 프로세스 동기화 : 임계영역, 동기화 해결 조건 및 소프트웨어적 초기 접근법 소개 (Process Synchronization 1) (0) | 2024.01.14 |
| [운영체제] 6. 프로세스 동기화 : Race Condition (Process Synchronization 1) (0) | 2024.01.12 |
