Process Synchronization
동기화 Problem
공유데이터에 접근하는 코드를 critical section(임계구역)이라고 했다.
어떤 프로세스 간에 공유데이터를 접근하거나, 접근하지 않거나를 반복하는 것으로 동작한다.
공유데이터를 동시에 접근하면 않되기 때문에 entry section(진입 구역)으로 락을 걸어서 동시에 접근하는 것을 막는다.
접근이 끝나면 락을 풀어서 다른 프로세스가 접근할 수 있게 한다.
solved 충족조건
Critical Section을 풀기 위해 만족해야 할 3가지 조건
- Mutual Exclusion (상호배제)
- Progress(진행)
- Bounded Waiting(유한대기)
해결 알고리즘1
Turn변수를 통해 본인 차례가 아닌 동안은 while문을 돌고 자신의 턴이면 들어가서 critical section에서 작업후 작업이 완료 후에 turn을 바꾸어 주어 다른 프로세스가 접근할 수 있게 한다.
한번 들어갔다가 나와야지만 교대로 사용할 수 있다.
critical section에 들어가는 빈도가 프로세스 별로 다를 수 있다.
Progress조건을 만족하지 않는 알고리즘이다.
Turn을 교대로 해주어야지만 임계영역에 들어갈 수 있다.
해결 알고리즘2
Flag변수를 이용해서 자신이 critical section에 들어가고자하는 의중을 표현하는 것이다.
들어가고자 하는 경우 flag를 true로 바꾸어서 들어가고자함을 알려준다.
그리고 상대방의 flag를 확인하다.
해결 알고리즘3
Turn변수와 Flag변수를 모두 사용하는 알고리즘이다.
들어가고자 하면 자신의 플래그를 들어서 의중을 표하고 Turn을 상대방으로 바꾼다.
둘다 모두 들어가고자 할 경우에만 Turn을 따져서 들어가는 것이고, 아무도 없므면 Turn에 관계없이 들어간다.
busy waiting = critical section에 들어가고자 하는데, 이미 누가 들어가 있다면, while문을 돌면서 기다릴 것인데, 상대방이 cpu를 잡아서 작업을 할 때 까지 계속해서 while문을 돌면서 기다릴 것이다.
Synchronization Hardware
동기화를 위한 하드웨어 지원
하드웨어적으로 atomic하게 작동할 수 있다면, lock을 걸고 푸는게 좀 더 간달하게 될 수 있다.
위의 문제들은 공유데이터를 읽는 것과 쓰는 것을 하나의 인스트럭션에 작업을 할 수 없기 때문에 발생한 문제들이다.
인스트럭션 하나를 가지고 데이터를 읽는 것과 쓰는 것이 동시에 작업이 가능하다면, critical section문제를 쉽게 해결할 것이다.
test_and_set(a) 원래값을 읽고 다시 쓰는것이 가능하다면 코드가 간결하게 바뀌게 될 것이다.
Semaphores 세마포어
세마포어는 추상자료형이다.
세마포어에 대한 연산이 필요하다. 세마포어 연산으로는 p연산하고 v연산이 정의된다.
락을 걸고, 락을 풀고하는 것을 세마포어를 이용해서 간단하게 구현할 수 있다.
공유자원을 획득하고, 반납하는 것을 세마포어가 처리해준다.
p연산은 세마포어 변수 값(공유데이터)을 획득하는 과정이다
v연산은 다 사용하고서 반납하는 과정이다.
세마포어 변수는 정수값을 가질 수 있다고 했는데,
변수값이 5면은 5이서 동시에 가져갈 수 있고,
락을 걸고 푸는 과정은 세마포어 변수값이 1이라고 생각하면 된다. p연산을 하면 락을 거는 것, v연산은 락을 푸는 것이라고 생각하면 된다.
p연산과 v연산은 atomic하게 한다고 가정하고 있다.
세마포어를 획득할 수 없으면, 그 프로세스를 블럭시키고, 누군가가 세마포어를 쓰고 반납하면, 하나를 깨워서 획득하게 하는 것이다.
p는 자원을 획득하는 과정이다.
자원의 여분이 있다면 바로 획득하고 없다면 잠든다.
v연산은 다 쓰고서 반납하는 과정이다.
v연산은 반납하고서 깨워주는 역할까지 코드로 구현한다.
which is better?
block/wakeup이 더 효율적이다.
세마포어의 타입
binary sempahore
세마포어 변수값이 자원의 값이 1인 경우는 binary sempahore라고 한다.
counting sempahore
세마포어 변수값이 자원의 갯수가 여러개 있어서 여분이 있어서 가져다 쓸 수 있는 경우는 counting sempahore라고 한다.
그외 용어 설명
Deadlock
둘이상의 프로세스가 서로 충족되어야 하는 event의 경우라면 무한히 기다려야하는 현상이 발생할 수 있다.상대방이 가진것을 기다리면서 자신이 가진것을 내놓지 않는 상태이다.
자원을 획득하는 순서를 똑같이 맞추어 주면 문제가 해결될 수 있다.
Starvation
특정프로세스가 영원히 기다려야 하는 상황을 의미한다.
