동기화 (Synchronization)
> CS 문제 해결 알고리즘
1. Bounded_buffer //waiting
2. Reader and Writter
3. Dining_Philosophers
1. Bounded_buffer
semaphore mutex = 1;
semaphore full = 0;
semaphore empty = n;
/*
wait(s)
{
while(s<=0) bysy waiting;
s--;
}
// s가 있으면 Pass 및 s-- 해서 다른거 wait 하도록 // 초기실행보장!
// s가 0이면 Wait
signal(s)
{
s++;
}
// s 를 증가시켜 다른 wait 중인 P 가 실행하도록 signal*/
[생산자]
while()
{
wait(empty) // 빈놈들 다들어가!!
wait(mutex) // 잠글게
CS // bufer ++ // 내용 채우고
signal(mutex) // 이제 문연다~
signal(full) // 채워졌어! 라는 signal
[소비자]
while()
{
wait(full); // 이제 쓸게
wait(mutex); // 내가 쓸거니깐 잠그고
CS // 버퍼 --
signal(mutex); // 다썼으니깐 풀고
signal(empty); // 비웠으니 채워줘~
2. Readers - Writters
: Readers : Only read / 값 update X > 여러 Reader 의 CS 접근 가능
// 공유변수를 다룰땐 당연히 1개만 // mutex
: Writters : Read/Write > 값 update O > Only One
>
Shared_Data
a) Data set
b) semaphore ( rw_mutex (Writter), mutex(Reader) ) = 1
c) int read_count =0;
[Writter]
while()
{
wait(rw_mutex); // 초기보장 / 잠그고
CS // 작성하고
signal(rw_mutex); // 다했어~ 풀고
}
[Reader]
while()
{
wait(mutex); // read_count 는 나만 바꿀꺼야
read_count++; // 내가 들어갈거야~
if(read_count == 1) // 내가 처음이면.. // 초기값 0
{
wait(rw_mutex); // 나 들어갔고, 우리 Readers 들이 0 될때까지 Write 하지마!
} // W 가 쓸수 있기에 R이 들어갈땐 첫째가 잠가줘야함
signal(mutex); // R 칭구들아 이제 들어와 ,
CS //readings
wait(mutex); // 나 다 읽었어 나갈거고 count 바꿀거니깐 기다려
read_count--; // 나왔어
if(rw_count == 0 ) // 마지막 나오는 막내야
{
signal(rw_mutex); // Writter 이제 들어오라고해라
} else signal(mutex);// 막내가아닌 둘째 셋째는 mutex 풀고나와
}
3. Dining_philosophers // 철학자들이라 밥안먹을땐 생각만함
(조건)
1. Thinking / Eating 한가지씩만
2. 원형 테이블에서 내 왼쪽/오른쪽의 젓가락(공유자원)을 두개가 있어야 먹을수(쓸 수) 있음
(공유)
Rice(한개의 Data Set)
semaphore chapstick[n]; // 다 1로 초기화 , 각 사람 사이에 젓가락이있음
> 좌우의 공유자원
/*
int chapstick [n];
for(int i = 0; i < n; i++) {
chapstick [i] = 1;
}
*/
[Philosopher i ]
while()
{
wait(chapstic[i]); // 왼쪽을 확인
wait(chapstic[i+1]% N); // 오른쪽을 확인
// 둘다 있어야(wait X) CS로 넘어감
// 나머지연산) i/N 마다 내차례가 옴
CS // EATING!!
signal(chapstic[i]); // 다먹었으니 왼쪽걸 줄게
signal(chapstic[i+1]% N); // 오른쪽도 줄게
}
> but if)
왼쪽을 확인하다가 C/S 를 모두가 한다면..
> 오른쪽을 확인하려고 다시 C/S 할때는 wait 에 걸림 > ALL Wait : DeadLock!
// 원형이기에 나의 오른쪽 == 오른쪽 사람에게는 왼쪽
>>
Monitor -> Dining_philosophers
// 객체
// 5명의 철학자들이 있다고하자..
// #define N 5
monitor DiningPhilosophers
{
enum {THINKING, HUNGRY, EATING}
//enum :THINKING =1 , HUNGRY=2, EATING=3 으로 이름붙여줌
state [5] ;
condition self [5];
void pickup (int i) { // 나 먹을거야
state[i] = HUNGRY; // 나 배고파
test(i); // 배고픈지 확인.. > 맞으면 먹어
if (state[i] != EATING) self[i].wait; //거짓배고픔은 wait 기다려
}
void putdown (int i) { // 나 다먹었어
state[i] = THINKING; // 이제 생각할거야
test((i + 4) % 5); // 내 왼쪽아 너 먹을래?
test((i + 1) % 5); // 내 오른쪽아 너 먹을래?
// >좌우에게 의사를 확인하며 순환
}
void test (int i) { // 너가 진짜 배고픈지 먹을수 있는지 확인할거야
if ((state[i] == HUNGRY) && // 너 배고픈건 맞지?
(state[(i + 4) % 5] != EATING) && // 너 왼쪽은 안먹고있지?
(state[(i + 1) % 5] != EATING) ) // 너 오른쪽은 안먹고있지?
// >공유자원 서로 접근 방지
{
state[i] = EATING ; // 먹어!!
self[i].signal () ; // pickup의 wait 중인걸 먹으라고 signal줌
}
}
initialization_code() { // 초기화, THINKING
// 철학자니깐 기본은 생각중
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}
main 구현..
DiningPhilosophers.pickup(i); // wait 에 빠지지 않았다면 CS 로넘어감
CS // EAT !!
DiningPhilosophers.putdown(i); // 다먹었음 나와
Monitor Solution 의 장단점
장점) DeadLock X : 회전형으로 좌우로 확인 및 다른놈 못들어옴 , 먹고있을때 또 먹으려안함(과식X)
단점) Starvation : 회전형이라 좌우로만 확인함
> ex) 1 2 3 4 5 일때 2 3 4 만 돌아가면서 지들만 먹을 수 있음
> 1,5 : starve상태