Process Synchronization
Background
- 동시에 shared data를 access할경우 결과가 틀리게 된다!
- 협력적 프로세스의 규율있는 실행을 책임지기위해 데이타 일관성을 유지하는 메커니즘을 요구한다.
- shared-memory 해결방법을 bounded-buffer 문제로 재해석 해보잔다 ㅡㅡ;
Bounded Buffer
- 제한된 Buffer에 뭔가 넣기; 이때 i++ , i--를 사용하는데 이것이 한번에(Atomically) 실행되지 않고 인터럽트가 걸리게 되면 문제가 발생한덴다..ㅡㅡ;
- 왜냐면 asembly(스펠링이...덜덜덜;)로 보면 i++은 하나의 명령어가 아니라 3개의 명령어 이기 때문이다.......하드웨어...-_-ㅋ...컴공들은.. 하드웨어는 전자의 전유물로 알고있고 전자는 소프트웨어를 자신들의 하위개념으로 이해하고 있다.....하드웨어...-_-ㅋ 일.반.적.으.로..
Race Condition
- 그냥 서로그냥 달리겠다고 하다가 결론적으로 둘다 넘어지는 경우를 말한다. 인터럽트가 걸리면서..
- 그러므로 반드시 동기화가 되어져야 한다.
Critical-Section Problem(임계구역문제)
- n개의 프로게스들이 경쟁한다 shared data로
- 각가의 프로세스들은 shared data가 access되는 CRITICAL SECTION이라 불리는 구역을 가진다.
- 문제 : 한프로세스가 critical-section에서 실행될때 타프로세스가 참견안하도록 확실히 해야한다.
ㅁMutual Exclusion(상호배제)
: Critical-section에서 한 프로세스가 실행되고 있다면 침범하지 않는다.
ㅁProgress(진행)
: Critical-section에서 실행되는기 없으면 암꺼나 드가라고!
ㅁBounded Waiting(한정된 대기)
: 배고파죽는거 없다~ 그랄라믄 드간놈 바로 드가지 마!
알고리즘 1번
while (turn != i) ;
critical section
turn = j;
reminder section
} while (1);
turn 변수를 두어 0으로 초기화
while(turn != i); 하다가
불만족 하면!
critical-section하고 나서 turn을 상대방 (turn = j;)를 한다.
//M.E.는 만족 P.R.은 불만족
알고리즘 2번
flag[i] := true;
while (flag[j]) ;
critical section
flag [i] = false;
remainder section
} while (1);
flag를 두어 false로 초기화
자신의 프로세스에서 자신을 true로 만든후 상대방을 지켜본다.
critical-section하고 나서 자신의 flag를 false로 만든다.
//M.E.는 만족 P.R.은 불만족
true를 만들어주는것과 while을 바꿔도 해결되지 않고 단지 M.E.가 불만족되어진다.
알고리즘 3번
1번과 2번의 변수를 합친다.
do {
flag[i] = true;
turn = j;
while(flag[j] and turn = j);
critical section
flag [i] = false;
remaind
}while(1);
//M.E. P.R. B.W. 만족 for two processes
Bakery Algorithm
- Critical section for n processes
- critical section에 들어가기 전에 프로세스를 번호를 받는다. 작은거 일찍들어가는...
ex) 1.2.3.3.3.4.4.5
- 만약에 3이라는 숫자를 Pi Pj가 받으면 프로세스ID(PID)가 작은놈이 먼저 실행(걍 무조건 작은놈이 대가리여~)
- 번호메기는데 있어 요점은 무조건 늘어만 나는것!
- shared data : boolean choosing[n], int number[n];
: init false init 0
do {
choosing[i] = true;
number[i] = max(number[0], number[1], …,
number [n ? 1])+1;
choosing[i] = false;
for (j = 0; j < n; j++) {
while (choosing[j]) ;
while ((number[j] != 0) && (number[j],j < number[i],i)) ;
}
critical section
number[i] = 0;
remainder section
} while (1);
Synchronization Hardware(B.W. 가 안됨!)
그럼..choosing은..A,B가 있는데 A가 뽑는중이이었고 결국에 A,B의 번호가 같아 질것이다
그런데 B는 critical section에 들어가버리고 A는 뽑기를 마쳤다. A의 PID가 B보다 작고 그래서 A도 들어가버린다.
Deadlock : 깨워줄놈끼리 큐에 들어가버려서 wake up 못시켜줄때
Starvation : 영~원히
Binary Semapore로 Counting Semapore 구현 모르겠음 ㅡ,.ㅡ;
7.5 고전적인 동기화 문제들
- Bounded-Buffer Problem
ㅁ 생산자는 FULL뮤텍스를 증가
ㅁ 소비자는 EMPTY뮤텍스를 증가
ㅁ empty와 full세마포의 위치를 바꿔버리면 생산자는 한번생산했는데 소비자는 계속 소비하는 이상한 결과가 발생된다.
- Readers and Writers Problem
ㅁ Readers에서는 readcount를 두어 1개의 reader가 있을때 writer가 들어오는것을 방지하기 위해 조건문 if를 사용 2개 이상일때는 이미 그 조건문을 지나쳐 1개의 writer만 지날수 있는 뮤텍스 값이 0이기 때문에 그냥 지나감ㅋ
ㅁ Writers에서는 별거 없고 뮤텍스 wrt만을 검사한다.
- Dining-Philosophers Problem
ㅁ 짝수이면 왼쪽먼저 홀수이면 오른쪽먼저..
Monitors
- 좋은거!
- condition varable은 한 프로세스를 모니터 내부에서 wait하는것을 허용하기 위해 반드시 선언되어야한다. ex) condition x,y;
- Condition variable은 wait와 signal 명령으로 인해서만 사용되어질수 있다.
ㅁ x.wait();
ㅇ 그 프로세스를 중지한다.
ㅁ x.signal();
ㅇ 중지된 프로세스를 재시작한다. 중지된 프로세스가 없으면 아무효과가 없다.
- condition variable로 해결한 dining philosophers problem
ㅁ 그냥 해결...중요한것은 test문장 마지막에 자신을 signal시켜준다는것.. 그 이유는 putdown에서 양옆의 녀석들을 체크 해주기 때문이다.
- 나쵸스에서의 condition은...아마도..ㅡ,.ㅡ;
ㅁ waiter는 condition variable로써 내부적으로 wait될놈과 signal될놈들 결정(철학자에서 여러철학자중 한명(양옆중 1명이 밥먹고 있을때)을 wait시킴과 같음
ㅁ conditionLock은 monitor자체의 큐로써 내부적으로 놀다가 waiter로 block되면 밖의 놈을 불러 들이기 위함, signal에 의해 waiter된놈이 살아나면 conditionLock을 Acquire시켜 딴놈 못들어 오게 막고 critical section을 수행한다.
Comments List
醫