* 동기화 기본 코드
# 그림설명 : 임의의 프로세스의 code 소개.
cf> critical section : 공유데이터를 접근하는 코드
remainder section : 공유데이터를 접근하지 않음
(entry, exit) section : lock을 거는 행위
???) 여러 프로세스가 동시에 critical section에 들어가는 것을 막는다. (이것이 동기화 개념!)
* Critical Section문제를 풀기 위해서 만족해야 할 조건
: 크게 3가지가 있다.
# Mutual Exclusion : (entry, exit) section 부분.
Progress : 코드를 잘 못 짜면 이러한 문제 발생.
Bounded Waiting : 기다리는 시간이 유한해야 된다.(즉, starvation이 생기지 않아야 한다.)
ex> cirtical section에 들어가고 싶은 프로세스가 3개가 있는데 2개만 들락날락 거리고
나머지 한개는 마냥 기다리는 상황이 생겼을때 Bounded Waiting조건을 만족하지 못한다.
=> 이 3가지 조건을 만족하면서 lock을 잘 걸었다가 푸는 그런 알고리즘들을 알아보도록 하자!
* Algorithm 1
: turn 교대가 포인트!!
cf>
1) P0를 위한 코드
| do { while(turn != 0); // 0이 아니면 못들어 간다. critical section turn = 1; // citical section에서 빠져 나와서 다음 차례로 만들어준다. remainder section }while(1); | cs |
2) P1를 위한 코드
| do { while(turn != 1); critical section turn = 0; remainder section }while(1); | cs |
# turn이 0이면 0번 프로세스, 1이면 1번 프로세스!
# 위에 코드는 1번 조건인 Mutual Exclusion은 만족한다 (P0의 경우, while (turn != 0), turn = 1로 인해서)
But, 2번 조건인 Progress는 만족 x.
why??))
코드를 보면 한 프로세스가 critical 세션에서 나와야 지만 턴이 상대 차례로 변하게 된다. 근데 이런 프로세스의 critical section 빈도가 다를수 있다.
극단적으로, P0는 critical section에 여러번 들어가고 싶은데, p1은 한번만 들어가고 안들어가도 된다. 이런 경우엔 P1이 한번만 들어가고 안들어가기 때문에 P0차례를 만들어주지 못한다. (차례를 바꿔 주려면 일단 들어갔다가 나올때 바꿔줌으로..)
P0는 영원히 못들어가게 된다...
=> turn을 교대로만 해주면 안되겠다.. 다른방법을 생각해 보자!
* Algorithm 2
: flag가 포인트
# Critical Section에 접근하는 방법
[단계 1] Critical Section에 들어가려면 flag를 true로 바꾼다.
[단계 2] 상대방 flag를 chk한다.
(IF, 상대방 flag가 true가 있으면 기다린다.)
[단계 3] 들어갔다 나올때 flag를 false로 바꿔준다.
# 이 알고리즘의 문제??
: Critical Section에는 아무도 안들어 갔는데 P0와 P1이 동시에 true로 한 경우. 이 경우에는 끊임없이 서로 양보하는 상황이 발생.
=> flag를 이용하는 알고리즘도 Progress는 충족시키지 못했다.... 다른 방법을 생각해 보자!
* Algorithm 3 (Perterson`s algorithm)
: turn과 flag 모두 사용.
# Critical Section에 접근하는 방법
[단계 1] Critical Section에 들어가려면 flag를 true로 바꾼다.
[단계 2] turn을 상대방 turn으로 바꿔 놓는다.
[단계 3] turn과 상대방 flag를 chk한다.
(IF, 상대방의 flag가 true이고, turn도 상대방이면 기다린다.)
[단계 4] 들어갔다 나올때 flag를 true로 바꿔준다.
=> 조건 3가지(Mutual Exclusion, Progress, Bounded Waiting) 모두 만족
But, 이 코드의 문제점이 있다.
# Spin Lock(= Busy Waiting)
ex> p0한테 cpu 할당 시간이 왔을때, while (flag [j] && turn == j);에서 빠져 나가지 못 할 경우도 있다.
결국 자신의 cpu할당 시간에 3번째 구간에서 chk만하다가 끈나는 경우.
=> 즉, 비효율 적인 방법을 나타냄
cf> instruction 단위로 time sharing이 일어나서 cpu 사용권이 바뀌기 때문에 이런 문제가 발생한다!
=> Spin Lock의 해결법은 나중에 알아보도록 하자!
!!!) 사실은 H/W 적으로 하나의 Instruction만 주어지면 이러한 critical section문제는 아주 쉽게 해결이 된다. => Test_and_Set
cf> : Data를 읽는것과 쓰는것을 하나의 instruction으로 처리할수 없기 때문에 동기화 문제가 발생한다.
* Synchronization Hardware
# 보라색 그림 설명
: a라는 데이터를 읽어내고, 그다음에 a라는 데이터 값을 1로 바꿔주는 것을 하나의 instruction으로 처리 해준다.
cf> 여기서 1은 lock = 1(true)를 의미 한다.
