[운영체제] 프로세스 동기화 3

여기서 드디어 채정아 문제 나온다 ..

정아가 문제라는 건 아니고 .. 우리 정아는 최고야 -3-

 

동기화와 관련된 고전적인 문제 

1. Producer - Consumer Problem

(= 생산자 소비자 문제)

 

생산자

버퍼의 홀에 데이터를 채우는 역할

 

소비자

데이터를 가져가는 역할

 

생산자와 소비자는 여러 명이 있으며 그렇기 때문에 이들 사이에는 동기화가 필요하다.

예를 들어서 생성자가 2번째 홀에 데이터를 넣었는데 또 다른 생성자가 다시 데이터를 넣으면 안된다.

 

또한 버퍼가 다 채워져 있는 상태에서는 소비자가 데이터를 가져가지 전까지 생산자는 데이터를 넣을 수 없다. 

 

개인적으로 생산자-소비자 (버퍼/홀/데이터) 개념을 어떻게 이해했냐면 .. 회전초밥 집이라고 비유해서 생각했다.

회전 초밥 집이 있고, 여러 명의 요리사와 손님이 있다.
이 회전 초밥 집에서는 몇가지 규칙이 있는데,
1. 하나의 그릇에 한 사람의 요리사가 초밥을 만들 수 있다.
2. 그릇이 비워져 있을 때만 초밥을 만들 수 있다.
... 라는 규칙이 있다.

그래서 그릇에 초밥이 있을 때 다른 요리사가 그 그릇에 초밥을 만들어서 놓을 수 없고,
그릇이 비워져 있지 않음에도 불구하고 초밥을 새로 만들 수 없다.

 

생산자/소비자 형태에서 생기는 문제를 해결하기 위해서는

✅ 둘 이상의 생산자/소비자가 데이터에 동시에 접근하는 것을 방지하기 위해 데이터 접근에 대한 lock/unlock이 필요하다.

✅ 버퍼가 가득 차 있거나/비어있을 때 생산자/소비자가 확인할 수 있도록, 가용 자원을 확인할 수 있도록 counting 세마포어가 필요하다.

 

위의 세마포어 변수 3가지는 full, empty, mutex이다.

full : 버퍼 내 내용이 들어 있는 홀의 개수

empty : 버퍼 내 비어 있는 홀의 개수

mutex : lock을 걸기 위한 변수  

 

위의 세마포어 변수를 바탕으로 이루어지는 과정은 아래와 같다. ⬇️

생산자 : 버퍼에 데이터를 넣는다.

먼저 P(empty)로 버퍼가 비어 있는 지를 확인한다. 비어있지 않다면 (데이터를 넣을 수 있는 공간이 없으므로) 소비자가 데이터를 가져갈 때까지 기다린다. 비어 있다면 빈 버퍼를 얻어 P(mutex)로 lock을 걸고 데이터를 넣는다.

그리고 과정이 다 끝났다면 V(mutex)로 unlock을 한 후 V(full)로 full의 개수를 증가시킨다. 

 

소비자 : 버퍼의 데이터를 가져간다.

먼저 P(full)로 내용이 들어 있는 버퍼가 있는지 확인하고 데이터가 있는 버퍼가 있다면 P(mutex)로 lock을 건다. 그리고 데이터를 가져간 뒤 V(mutex)로 unlock을 한 뒤, P(empty) 연산으로 비어 있는 버퍼의 개수를 증가시킨다. 

---

2. Reader and Writers Problem

read/write 하는 작업의 대상을 DB라고 생각해보자.

 

만약 한 프로세스가 DB에 write를 하고 있을 때 다른 프로세스가 접근하면 안된다.

하지만 단순히 DB의 내용을 읽기만 한다면 여러 프로세스가 접근해도 된다.

 

해당 형태에서 해결해야 하는 부분은

✅ write는 DB를 읽는 프로세스가 하나도 없을 때 할 수 있으며

✅ read는 여러 프로세스가 할 수 있고, write를 하고 있다면 read 할 수 없다. 

 

위에서 사용하는 변수는 아래와 같다.

DB : 접근하려는 공유 데이터

db : DB에 대한 세마포어 변수 

readcount : DB의 데이터를 read하는 프로세스의 수

mutex : readcount에 대해 lock을 걸기 위한 변수

P(mutex), V(mutex) : readcount 접근에 대한 Lock/Unlock 연산

P(db), V(db) : DB 접근에 대한 Lock/Unlock 연산

 

 

Writer : DB에 데이터를 write

write를 하고 있을 때는 read하는 프로세스가 있으면 안되므로 P(db)로 DB 접근에 대한 lock을 건다. 만약 다른 프로세스가 DB에 접근해 있다면 대기한다.

DB에 lock을 걸고 write 작업을 한 뒤, 작업이 끝났다면 V(db)로 unlock을 한다. 

 

하지만 만약, read하는 프로세스가 계속 접근하게 된다면 DB가 unlock이 되지 않아 기아 현상이 발생할 수 있다.

 

 

Reader : DB의 데이터를 read 

writer의 경우와 마찬가지로 lock/unlcok해도 되지만 이 방식은 비효율적인 방식이다.

DB의 내용을 단지 읽기만 하기 때문에 여러 프로세스가 접근해도 문제가 생기지 않기 때문에 read인 경우라면 lock을 걸긴 하지만 write하는 프로세스가 아닌 read하는 프로세스는 접근할 수 있도록 한다. 

 

먼저 read하기 위해 DB에 접근하면 readcount+1 한다. (이 때, readcount도 공유변수기 때문에 readcount를 조작할 때 P(mutex), V(mutex)를 해줍니다). 근데 만약 readcount==1인 경우 즉, DB의 내용을 읽는 프로세스가 하나라면 DB에 lock(P(db))을 해줍니다. 다른 프로세스가 write하면 안되기 때문이다. 

 

이렇게 DB를 read하는 여러 프로세스가 내용을 읽을 수 있다. 하지만 만약 read 프로세스가 내용을 읽고 빠져나간 후 readcount==0인 경우, 즉 더이상 read 프로세스가 없다면 DB를 unlock(V(db))한다. 그래야 DB에 write할 수 있고 기아현상 등이 발생하지 않을 것이다.

 

이렇게 readcount변수로 read하는 프로세스를 DB에 여러개가 접근할 수 있게 한다.

 

---

3. Dining - Philosophers Problem

철학자들의 만찬 문제는 각 자리가 있고 자리왼쪽/오른쪽에 포크가 하나씩 있다.

식사를 하기 위해서는 왼쪽/오른쪽 포크를 모두 사용하여 식사를 해야 하며 철학자들이 할 수 있는 일은 식사를 하거나 생각을 하거나 둘 중 하나이다.

 

이 때, 어떻게 하면 철학자들이 공평하게 식사를 할 수 있을지에 대한 문제를 다룬다.

 

i 번째 철학자는 i번째와 i+1번째 포크를 집고 식사를 하고 다 먹은 후 반납하고 생각을 한다.

 

이 때 포크를 잡고/반납 할 때 lock/unlcok을 하는 것이다.

하지만 위의 방법은 만약 i번째 철학자가 모두 i번째 포크를 잡는다면 모두 한쪽포크만 가지고 있기 때문에 그 누구도 식사를 하지 못하게 된다. 이런 문제를 Deadlock, 교착상태라고 한다.

 

이를 해결 하기 위한 방법으로는 3가지가 있습니다.

1. 4명의 철학자만이 이 테이블에 동시에 앉을 수 있도록 한다.

2. 젓가락을 두 개 모두 잡을 수 있을 때에만 젓가락을 잡을 수 있게 한다

3. 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락 부터 집도록 한다.

 

*이후에 monitor라는 방법으로 철학자의 만찬 문제를 좀 더 깔끔하게 해결할 수 있다.

 

---

Monitor

프로세스 동기화 2에서 임계영역을 세마포어로 해결하는 방법을 다뤘다.

이 때 세마포어를 정확하게 잘 사용하면 문제가 되지 않지만 개발자의 실수로 시스템에 치명적인 영향을 끼칠 수 있다.

 

예를 들어서 P(S), V(S)를 잘못 사용하는 경우 상호 배제가 깨지거나 (상호 배제 상태는 반드시 지켜져야 한다.) 데드락 문제가 발생할 수 있기 때문에 이런 경우 문제가 될 수 있다.

 

 

이러한 문제를 해결하기 위해 나온 방법이 모니터이다.

 

모니터 방법

프로세스가 공유데이터에 접근하기 위해서는 모니터 내부의 어떠한 절차를 통해서만 공유 데이터에 접근할 수 있게 한다.

위의 사진에서 프로세스가 shared data에 접근하기 위해서는 n개의 operations을 통해서만 접근할 수 있다.

 

또한 모니터의 경우 기본적으로 여러 프로세스가 모니터에 대한 동시 접근을 제한한다.

그렇기 때문에 한 순간에 하나의 프로세스만 모니터에 접근하여 공유 데이터를 사용할 수 있다. 하나의 프로세스가 공유 데이터를 사용할 때 다른 프로세스가 접근하면 queue에서 기다린다.

➡️ 그래서 (모니터가 알아서 제어를 하기 때문에) 세마포어처럼 lock/unlock을 할 필요가 없다.  

 

만약 A 프로세스가 모니터에 있는 도중에 CPU 시간이 끝나게 되어서 B 프로세스가 모니터에 접근하려는 경우,
A 프로세스가 이미 모니터에 활성화된 상태로 존재하기 때문에 B 프로세스는 모니터에 들어가지 못하고 큐에 가서 줄을 서게 된다.

 

 

모니터에서 사용하는 변수도 있다.

모니터에서는 Condition Variable를 사용하는데 위의 사진에서 full, empty 변수가 있는 것을 볼 수 있다.

 

만약 프로세스가 모니터에서 어떤 일을 하는데 조건이 충족되지 않아, 잠시 잠들게 하는 경우

어떤 조건이 충족되지 않았는지에 따라 그 조건에 해당하는 것을 변수로 설정할 수 있다.

 

Condition Variable은 2가지 연산을 할 수 있다.

1. wait()
   어떤 프로세스를 잠들게 하는 경우 해당 condition variable에 들어가서 줄서게 된다.
2. signal()
   누군가 condition variable를 사용하고 나가면 condition variable를 기다리는 프로세스를 깨운다.

 

condition var는 값을 가지지 않고 

✔️ 자신의 큐에 프로세스를 매달아서 sleep 시키거나

✔️ 큐에서 프로세스를 깨우는 역할만 한다. 

 

---

생산자 소비자 문제를 모니터로 해결해보자.

 

full : 내용이 들어 있는 버퍼를 기다리는 프로세스를 줄 세운다.

empty : 빈 버퍼를 기다리는 프로세스를 줄 세운다. 

 

생산자

만약 버퍼가 모두 차서 데이터를 넣을 버퍼가 없다면 빈 버퍼를 기다리는 큐에 가서 잠들게 한다. (empty.wait())

그렇지 않고, 빈 버퍼가 있다면 버퍼에 데이터를 넣고 내용이 들어 있는 버퍼를 기다리면서 잠들어 있는 프로세스를 깨운다. (full.signal())

 

소비자

만약 내용이 들어있는 버퍼가 없다면 내용이 들어 있는 버퍼를 기다리는 줄에 가서 잠들게 한다. (full.wait())

그렇지 않고 내용이 들어있는 버퍼가 있다면 버퍼로부터 아이템을 가져오고 빈 버퍼를 기다리는 프로세스를 깨운다. (empty.signal())