[운영체제] 6주차: 전통적인 동기화 문제

여기부터 7장

 

Bounded-Buffer problem

Buffer의 크기가 N이고, data 생산자(Producer)와 소비자(consumer)가 있다고 하자.

Producer는 Buffer가 꽉 차면 동작하지 않고 consumer는 buffer가 비어있으면 동작하지 않는다.

 

semaphores

mutex

buffer는 critical section이므로 mutex로 mutual exclusion을 보장한다.

초기값 1

 

full

꽉 찬 버퍼의 수

초기값 0

 

empty

비어있는 버퍼의 수

초기값 N

 

 

 

 

 

ⓐ Producer:

wait(empty)

empty가 하나도 없으면 기다림

처음에는 N이므로 block()이 호출되지 않는다

 

wait(mutex)

buffer에 대한 독점권을 얻는다

mutex는 binary semaphore로 0이면 실행이 안 됨

처음에는 1이므로 실행됨

 

signal(mutex)

mutex를 0으로 설정해 Producer가 buffer에 접근할 수 없게 함

 

signal(full)

Buffer가 비어서 대기 상태인 Consumer가 있다면 wakeup 시킨다.

signal(full)을 호출하면 full이 0(초기값)이었다가 1이 되므로 Consumer가 실행된다.

 

 

ⓑ Consumer

wait(full)

처음에는 0이므로 block 됨

Produer가 실행되면 full이 0보다 커지므로 block되지 않음

 

wait(mutex)

처음에는 1이라 실행됨

0이면 Consumer가 block됨

 

signal(mutex)

wait(mutex)에서 mutex가 1이었으면 여기까지 옴

이제 0으로 해서 Consumer가 더이상 buffer에 접근할 수 없게 함

 

signal(empty)

empty 값이 0이라 대기하던 Producer가 empty가 1 늘어나서 실행됨

 

 

wait(mutex)가 wait(empty)나 wait(full)보다 먼저 호출되면 deadlock 발생

 

Consumer가 먼저 실행된다 하자.

mutex는 처음에 1이므로 wait(mutex)에 의해 0으로 바뀜

wait(full)을 호출하면 full의 초기값은 0이라 여기서 대기하게 됨

 

이제 Producer가 실행 됨

현재 Consumer가 mutex를 0으로 해놓은 상태이므로 wait(mutex)에서 기다리게 됨

 

따라서 둘 다 대기하게 됨

 

Producer가 실행되려면 Consumer에서 signal(mutex)를 호출해야 됨

그러려면 full이 0에서 1로 바뀌어야 되는데 이건 Producer가 signal(full)로 바꿔줌

근데 Producer가 대기 중이라 이게 안 됨

-> Deadlock

 

Semaphore를 쓰면 문제를 쉽게 해결할 수 있으나 전적으로 프로그래머에 의존적임

 

 

Readers-Writers promblem

Readers: 데이터를 읽기만 하고 update 하지 않음

Writer: 읽기 쓰기 다 함

 

여러 개의 Reader와 Writer가 하나일 때 공유 데이터를 어떻게 보호할 것인가?

 

Writer가 데이터에 접근 중이면 Reader는 접근하면 안 된다

반대도 마찬가지

다만 여러 개의 Reader는 동시에 접근 가능(데이터를 수정하지 않으니까)

 

 

Semaphores

read_count

Reader가 read할 때마다 1씩 증가함

즉 프로세스가 공유 데이터를 읽으려면 read_count를 1 증가시켜야 함

여러 Reader 프로세스가 동시에 공유 데이터를 읽을 때 mutex로 read_count를 보호함

 

mutex

read_count에 접근하기 위함

1로 초기화

 

rw_mutex

writer가 있을 때는 Reader가 공유 데이터에 접근하지 못 하도록 함

1로 초기화

 

 

Writer:

wait(rw_mutex)

초기값이 1이므로 Writer는 block되지 않음

그러고 나서 0으로 바꿔서 Reader가 접근하지 못 하게 함

 

signal(rw_mutex)

다 쓰면 rw_mutex를 1로 바꿔서 Reader가 접근할 수 있도록 함

 

 

Reader:

wait(mutex)

읽기 전에 read_count를 1 늘리고 다 읽고 나면 1 감소시킨다

그런데 이 read_count는 그 자체가 critical section이므로 우선 wait(mutex)로 독점권을 얻는다.

 

if (read_count == 1)

read_count == 1은 최초의 Reader가 있음을 의미하므로

wait(rw_mutex)를 호출해 Writer가 접근하지 못 하게 한다.

 

wait(mutex)

read_count에 접근하므로 다시 독점권을 얻음

 

signal(mutex)

다른 프로세스가 read_count를 증가시킬 수 있게 함

 

두 번째 Reader가 진입했다고 하자.

이미 rw_mutex는 lock이 걸려 있으므로 굳이 wait(rw_mutex)를 또 호출할 필요는 없음

 

읽기가 끝나면 wait(mutex) 호출 후 read_count--함

 

if(read_count == 0)

더이상 데이터에 접근하는 Reader가 없으므로 signal(rw_mutex)를 호출해 Writer가 접근할 수 있게 함

 

 

① wait(rw_mutex) (Writer)

rw_mutex가 0으로 바뀜

 

② 데이터 씀

 

③ wait(mutex) (Reader)

mutex = 0됨

 

④ wait(rw_mutex) (Reader)

rw_mutex가 0이므로 대기

첫 번째 Reader는 여기서 대기한다.

 

⑤ wait(mutex) (두 번째 Reader)

현재 mutex가 0이므로 두 번째부터는 Reader의 첫 줄 wait(mutex)에서 대기하게 됨

 

⑥ signal(rw_mutex) (Writer)

rw_mutex가 1이 됨

 

⑦ 읽음(첫 번째 Reader)

 

⑧ wait(mutex) (첫 번째 Reader)

mutex가 0이 됨

 

⑨ read_count-- (첫 번째 Reader)

read_count가 1이 됨

 

⑩ signal(mutex) (첫 번째 Reader)

mutex가 1이 되어 두 번째 Reader부터 실행됨

 

⑪ wait(rw_mutex) 두 번째 Reader

현재 read_count가 1이므로 wait(rw_mutex)에 의해 rw_mutex는 0이 됨

 

⑫ wait(rw_mutex) (Writer)

rw_mutex가 0이므로 대기

 

 

저거 없어도 잘 동작함

근데 여러 개의 Reader가 동시에 데이터를 읽을 수는 없게 된다

처음 wait(mutex) 하고 다 읽은 다음에 signal(mutex)하므로 읽는 작업을 독점하게 되는 것이다.

동작은 잘 되는데 효율이 떨어짐

 

 

Dining-Philosopher problem

 

 

5명의 철학자가 있고 젓가락도 딱 5개라고 하자. 이 경우 몇 명은 밥을 못 먹는다.

 

이 경우 Deadlock이 발생할 수 있다.

모든 철학자가 자기의 왼편에 있는 젓가락을 집었다(lock을 건다)고 하자.

이 때 한 철학자가 자기의 오른쪽에 있는 젓가락을 집으려고 하면(lock을 걸려고 하면) 영원히 기다리게 된다.

 

Monitor를 이용한 solution은 다음과 같다.

 

기본적으로 pickup - EAT - putdown의 순서로 실행된다.

 

test

오른쪽의 철학자 상태와 왼쪽의 철학자 상태를 확인한다.

자신은 HUNGRY고 양쪽의 철학자가 EATING이 아니면 젓가락 2개를 쓸 수 있음을 의미한다.

따라서 이 경우 자신의 상태를 EATING으로 바꾸고 자기 자신에 대한 signal()을 호출한다.

즉 자신의 프로세스를 하나 가져와 실행한다.

 

putdown

다 먹었으니까 THINKING으로 상태를 바꿈

왼쪽과 오른쪽 철학자에 대해 test 호출

왼쪽 철학자 입장에서는 우선 오른쪽(putdown을 호출한 철학자)는 HUNGRY가 아님

따라서 왼쪽 철학자 입장에서 자신의 왼쪽도 HUNGRY가 아니면 젓가락을 가져올 수 있다.

그리고 putdown을 호출한 철학자에 의해 대기 중이었으면 test()의 signal()에 의해 wakeup 된다.

 

 

그런데 Monitor 방법은 starvation 문제가 발생할 수 있다.

즉 어느 철학자가 먼저 젓가락을 가져갈 지 장담할 수 없어서

극단적인 경우 한 철학자가 계속 젓가락을 가져갈 수도 있다.

 

Bounded waiting에 의해 한 철학자가 pickup한 다음에 바로 pickup하지 말라는 법이 없어서 이런 문제가 발생하는 것