10. Synchronization(동기화)-2

동기화의 고전적인 문제 Big 3

1. Bounded-Buffer Problem

2. Readers and Writers Problem

3. Dining Philosophers Problem

 

Bounded-Buffer Problem

: N개의 Item을 삽입할 수 있는 Buffer가 있음. 여기에 여러 생산자와 소비자들이 접근함.

- 생산자: 하나의 Item을 생산해서 Buffer에 넣는 사람.

-> Buffer 배열 중 같은 index에 접근해서 Item을 넣을 시 Race Condition이 발생할 수 있음.

 

- 소비자: Buffer에서 하나의 Item을 가져오는 사람.

-> Buffer에서 가져오는 Item을 소비하고 비워주는데 Buffer의 상태가 Empty면 대기함. 근데 이런 거에 많이들 대기하면 CPU 효율성 떨어지는 문제 발생할 수 있음.

 

-> 이런 문제들을 해결하고자 하는 것임.

Buffer에 접근하게 해주는 것이 Critical Section임.

가장 좋은 방법: 한번에 하나의 프로세스만이 Critical Section에 접근할 수 있게 하는 것임.

-> 우린 이 Bounded-Buffer Problem에 '세마포어'를 쓸 것임.

 

Bounded-Buffer Problem에서의 세마포어

총 3개의 세마포어 사용!!!

 

1) Empty 세마포어: Buffer 내에 저장할 공간이 있음을 표시함으로서 생산자의 진입을 관리함.

2) Full 세마포어: Buffer 내에 소비할 아이템이 있음을 표시함으로서 소비자의 진입을 관리함.

3) Mutex 세마포어: Buffer에 대한 접근을 관리하는데 이는 Buffer의 상태 값을 변경하기 위한 세마포어임.

 

[세마포어 초기 값]

Empty = n(버퍼에 empty인 entry가 n개 있다는 뜻이니까)

Full = 0

Mutex = 1(한번에 하나씩만 접근하니까)

Readers-Writers Problem

: 여러 Readers와 Writers가 하나의 공유 데이터를 읽거나 쓰기 위해 접근함.

 

- Readers: 공유 데이터를 읽음.

-> 동시에 여러 Reader가 같은 Data를 읽을 수는 있음.

 

- Writers: 공유 데이터에 씀.

-> Writer가 데이터를 수정하기 위해서는 Reader나 Writer가 작업을 하고 있지 않아야 함.

 

-> 이 문제의 해결을 위해서 1개의 int 값과 2개의 세마포어를 사용할 것임.

 

1) int readcount: Buffer에 현재 몇 개의 Reader가 접근 중인지 표시함.

2) wrt 세마포어: Writers 사이의 동기화(Mutual Exclusion)를 관리함.

3) mutex 세마포어: Readcount와 wrt에의 접근이 원자적으로 수행됨을 보장하기 위한 세마포어

 

[자료구조 및 세마포어 초기 값]

readcount = 0; (아무도 접근 안한 상태니까.)

wrt = 1; (하나의 실행흐름만 통과 가능하니까)

mutex = 1; (하나의 실행흐름만 통과 가능하니까)

문제점...!!!!!!이 슈발 발(시험 문제 가능성 높음)

writer가 reader들이 데이터를 읽고 있을 때 진입하고 싶으면 신호를 줘서 나써야댕~~~해주면 더 이상 readcount가 늘어나지 않도록 함.

 

Dining Philosophers Problem

문제 해결 방안

1) 단순히 젓가락을 집는 것에 대한 동기화를 부여함.

-> 각 젓가락에 세마포어를 부여: chopstick[i], 이때 값은 1로 초기화. 

각 젓가락에 세마포어를 부여했기에 철학자 기준으로 양쪽 세마포어를 모두 할당 받으면 그때부터 eat!

어? 근데 각자가 다 같은 방향(모두 지 기준 왼쪽 or 모두 지 기준 오른쪽)으로 집는다? 다들 "아 반대꺼 언제 줌!!?!?!!?!?"이러고 있음

==>Deadlock 발생

 

아 다른 Deadlock을 개선하는 방법 없냐?

1. 한번에 최대 4명의 철학자만 식탁에 앉히는 방법

-> 이건 왜 개선된 거임? 알 수가 없네?

 

2. 젓가락의 상태를 미리 검사하여 양쪽의 젓가락이 모두 사용 가능할 때만 젓가락을 집도록 함.

3. 철학자에게 번호를 부여해서 홀수인 철학자는 왼쪽의 젓가락을 집고, 짝수인 철학자는 오른쪽의 젓가락을 먼저 집도록 함.

-> 이것도 뭐가 개선된 거임? 아 몰라~~~~~~~~~~~~

 

이렇게 3가지가 있는데 얘네들 Starvation이 해결 안됨. 어케 해결함?

-> 한 차례 굶은 철학자들에게는 우선권을 주는 방식으로 해결 가능.

ㅇㅋㅇㅋ 근데 이제 세 방식 다 모르겠고~~~2번이 짱짱맨임~~~2번이나 살펴BOZA

- state[i] : i번째 철학자 상태(THINKING / HUNGRY / EATING)

- self[i]: 철학자가 딱 젓가락 두개를 잡기를 기다리는 세마포어. 얘는 초기화 값이 0임. 근데 이걸 take_chopsticks의 test에서 V해주잖슴? 그걸로 1이 되었다가 test가 지나가면 밥 먹을 수 있잖슴? 그러고서 take_chopsticks의 P(self[i]) 거치면서 이제서야 take_chopsticks를 빠져나와서 밥을 먹을 수 있어짐.

말이 개 어려울 수 있음. 다시 보자.

test함수에서 배가 고픈 상태이면서 양쪽이 뭘 안먹는 상태여야 내가 EATING이 되고, V(self[i])로 self[i]가 1이 되기에 take_chopsticks의 P(self[i])를 벗어나고, 그래야 take_chopsticks를 벗어나고 진또배기로다가 밥을 먹을 수 있음.

-> self 세마포어의 궁극적인 목적: 양쪽이 안 먹고있는 상태여야 먹을 수 있도록 설정.

(그렇다면, mutex의 궁극적인 목적: 양쪽 젓가락을 집든, 놓든 하는 행위를 단 한명만 할 수 있도록 설정.)

-> 일단 각 철학자는 프로세스를 do-while문으로 계속 도는데 일단 thinking 중임. 그러다가 take_chopsticks를 통해 젓가락 집어보려고 함. 집으면 eat하고 다 먹으면 put_chopsticks로 내려둠. 그걸 반복할 거임.

일단 take_chopsticks를 보자. mutex는 알다시피 0 or 1을 갖는 값이니, 젓가락을 집는 행위는 한번에 한명만 가능하다. 물론 젓가락을 내려놓는 행위도 마찬가지이기에(put_chopsticks에도 mutex에 대한 P, V 연산있잖아!!) 젓가락이란 걸 들거나 내려놓는거 통틀어서 한 사람만이 집거나 내려놓는 행위 중 하나를 진행할 수 있다.(동시에 집거나 내려놓거나, 한 사람이 내려놓고 한 사람이 드는 행위는 절대 있을 수가 없다.) 계속해서 take_chopsticks를 보자. mutex가 1(내게 집을 수 있는지 검사할 수 있는 타이밍이 옴(집을 수 있단게 아니라 집을 수 있나 검사할 기회가 온 것임.))이면 0으로 바꾸고 내 상태를 HUNGRY로 바꾸고 test를 시작함. test 함수를 보자.

만약 나 지금 배고픈데 양 옆이 다 뭐 안먹는 중이네..?? 바로 나 EATING으로 바꾸고 0이던 self[i]를 V를 통해 1 증가시킴. 그러고 test 나와서 mutex 풀어주고 P(self[i])로 self[i] 0으로 만들고 take_chopsticks 빠져나와서 eat...eat...eat함. 아 배불띠~~한 후엔 바로 put_chopsticks에서 내려놓을 타이밍 각(mutex가 1이 되는 타이밍~)잼. 각 나오면 내 상태 EATING에서 THINKING으로 바꿔주고 test(i-1)해줌. (LEFT가 i-1임.) test(i+1)도 해줌. 얘네는 내가 다 먹고나서 "양쪽 놈들이 나때문에...밥을 못먹었겠지..?ㅠㅠ"하면서 검사하고 밥 먹기 허용해주려고 test해주는 것임. 그거 끝나면 나 mutex 내려놓고 끝남.

만약 나 배고픈데 양옆 중 EATING 있음...? 그럼 바~~~로 밥먹을 기회 무산되고 test 나와서 mutex 풀어주고 P(self[i])감. 근데 self[i]가 초기값이 0이었어서 0이잖아? 그럼 무-한 wait하다가 얘를 eat하도록 허용해주는 프로세스에 의해 EATING으로 바뀌고 V(self[i])가 풀려서 eat...eat...eat

 

이 전략의 목표는 '철학자의 좌우 젓가락이 사용 가능할 때만 Cirtical Section에 진입이 가능함.'이다.

 

Concurrency를 유지하기 위해서 || No Race Condition || 여러 프로세스가 협업 시 정상적으로 수행되기 위해서 확인해야할 요소

1) Data Consistency가 확보되는지

2) Deadlock이 발생하는지

3) Starvation 가능성이 있는지

4) Concurrency를 얼마나 제공하는지