OS_ch7_Process Synchronization

1. Background

 - 동시에 shared data에 접속해서 값을 바꾸면 충돌이 일어나겠지요?

1) Producer-Comsumer with Bounded Buffer 생각해보자

1> shared data

#define BUFFER_SIZE 10

typedef struct{

...

}item;

item buffer[BUFFER_SIZE];

int in=0;

int out=0;

int counter=0;

2> Producer process

item nextProduced;

while(1){

while(counter==BUFFER_SIZE);

buffer[in]=nextProduced;

in=(in+1)%BUFFER_SIZE;

counter++'

}

3> Consumer process

item nextConsumed;

while(1){

while(counter==0);

nextConsumed=buffer[out];

out=(out+1)%BUFFER_SIZE;

counter--;

}

=> counter++; counter--; 는 atomically 수행되어야 한다. 즉 누가 증가시키고 있는데 감소를 동시에 시키면 안됨

=> 실제 어셈블리 연산은 reg1=counter;  reg1=reg1+1;   counter=reg1;   이런 식으로 이루어 지기 때문에 중간에 껴들수 있음..

=> producer와 consumer 스케줄링 된것에 따라서 결과값 마구 바뀔 수 있음....

 * 경쟁조건(Race Condition): 프로세스 여러개가 동시에 공유 자원을 가지고 경쟁할 때 가장 마지막에 접근한 프로세스에 의해 값이 바뀜

=> 따라서 동기화(Synchronizaion) 를 꼭 해줘야함

2. The Critical-Section Problem

 - n개의 프로세스가 공유 자원을 가지고 경쟁

 - Critical-Section에는 오직 하나의 프로세스만 돌 수 있게 함

1> Mutual Exclusion: 서로 겹치지 않는 것이 너무 강조되면 dead-lock 걸릴수도..

2> Progress: 그러다가 아무도 진행 못하면 어쩔? 공간 비었으면 바로바로 스케줄링 해줘야함

3> Bounded Waiting: 들어간다고 요청한 뒤에 기다리는 시간이 유한해야함.. 평생 Critical Section에 들어갈 날만 기다릴 순 없음

 - 문제해결 알고리즘(프로세스 두개, i와 j)

1> turn 방식, process P_i

do{

while(turn!= i);  //turn 내차례 아니면 뱅뱅 돌기

크리티컬섹션 드뎌 들어감

turn=j; //턴 넘겨줌

남은 다른 작업함

}while(1);

=> mutual exclusion 하지만.. progress가 안됨. 상대방이 크리티컬섹션에 오래 있으면 나에게 턴 안줌 난 아무것도 못함

2> flag 방식, process P_i

do{

flag[i]=true;  //내가 들어가겠다는 의사표시를 함

while(flag[j]); //상대방이 의사표시를 하고있는 동안 난 놀음

크리티컬 섹션 드뎌 들어감

flag[i]=false; //섹션 일 다하면 난 이제 의사 표시 안함

남은 다른 작업함

}while(1);

=> mutual exclusion 하지만 역시 progress 가 안됨

3> turn & flag 방식, process P_i

do{

flag[i]=true;  //나 하긴 할껀데

turn=j;   //지금 니차례야

while(flag[j] and turn=j); //쟤가 의사표시 중& 턴도 쟤면 난 아무것도 안함... 상대방이 만족 안할경우엔 while 탈출가능

크리티컬 섹션 드뎌 들어감

flag[i]=false  //할거 다했음 난 관심없음 이제

남은 다른 작업함

}while(1);

=> 세가지 요구조건 만족!, mutual exclusion, progress, bounded waiting time

4> Bakery Algorithm

- 우선순위 스케줄링처럼 프로세스가 번호표 받음ㅋㅋㅋㅋㅋㅋㅋ낮은 번호 먼저 입장

- 같은 번호표 받으면 먼저 요청한 애가 먼저 들어감

- 항상 오름차순으로 우선순위 배분

3. Synchronization Hardware

4. Semaphores

5. Classical Problems of Synchronization

6. Critical Regions

7. Monitors