[운영체제] 동기화(Process Synchronization)
동기화(Process Synchronization)
배경
💡Producer-Consumer 문제 (Race Condition)
count = 0 이라는 변수가 있을 때, producer는 count++을 시키고, consumer은 count--를 시킨다고 하자.
두 사람은 공유하는 data를 동시에 변경하려고 하니까 엉뚱한 결과가 나올 수 있다. 두 명의 사람이 칠판에 그림을 그리고 있다고 할 때 순서가 있게 해야지 동시에 그림을 그리려고 하면 칠판은 엉망이 될 것이다.
둘 다 공유하는 data를 읽기만 하면서 두 프로세스가 실행되면 문제가 되지 않는다. 하지만 동시에 변경하려고 할 때 이 문제가 발생한다.
우리는 멀티 스레드 환경을 보통 사용하므로 프로세스 동기화를 잘 시켜주어야 한다.
☝️Critical Section
공유하는 data를 조작하는 코드의 부분을 뜻한다.
즉, 하나의 process가 Critical Section에 진입해서 실행 중일 때, 다른 process가 진입할 수 없게 막아둬야 한다.
Race Condition 해결 방법
Critical Section이 시작되기 전과 후에 특별한 코드를 추가하는 방식으로 해결 할 수 있다.
이는 3가지 조건을 만족 시켜야 한다.
1. Mutal Exclusion
오직 하나의 process만이 Critical Section에 접근할 수 있다.
2. Progress
Critical Section을 아무도 조작ㅎ고 있지 않을 때 빠르게 어느 process를 들여보낼 지 결정해야한다.
3. Bound Waiting
여러 개의 process가 동시에 진입하고 싶어할 때 줄을 세우다가, 특정 process의 기다리는 시간이 너무 지연돼서는 안된다. 따라서 기다리는 시간의 bound가 필요하다.
💡 Peterson's Solution
공유하는 두 개의 변수 turn과 flag를 둬서 enter과 exit을 할 때 flag를 변경해주는 식으로 SW적으로 해결하는 방법이다.
- turn: Critical Section에 진입할 차례인 process를 나타낸다.
- flag: process가 Critical Section에 진입할 준비가 됐음을 나타낸다.
동기화 하드웨어(Synchronization Hardware)
요즘 기계들은 TestAndSet이나 Swap과 같은 특별히 atomic(=non-interrupable) 하드웨어 명령어들을 제공한다.
밑에 두 명령어는 "atmoically" 실행된다. 즉, 두개의 TestAndSet 명령어가 동시에 실행되려고 하면, 어떤 임의의 순서대로 실행 될 것이다.
하지만 둘 다 Race Condition을 해결하기 위한 3번째 조건인 Bound Waiting은 충족되지 않는다.
🔷 TestAndSet 명령어
boolean TestAndSet(boolean *target){
boolean rv = *target;
*target = true;
return rv;
}
🔹 TestAndSet을 이용한 해결 방법
공유하는 boolean 변수 lock을 false로 초기화 해둔다.
lock 변수가 true라면 어떤 프로세스가 Critical Section에 접근 중임을 의미해서 락을 거는 것과 같은 효과를 낸다.
boolean lock = false;
TestAndSet(lock) //lock이 true로 바뀌면서 진입이 가능해짐
어떤 한 프로세스가 Critical Section에 진입해 있는 상태라면 공유하고 있는 lock 변수의 값이 true로 바뀌면서 다른 프로세스는 접근할 수 없게 된다.
진입해 있던 프로세스가 Critical Section에서 exit을 하게 되면 lock=false로 다시 변경해주면서 다른 프로세스가 접근할 수 있게 된다.
🔷 Swap 명령어
void Swap(boolean *a, boolean *b){
boolean temp = *a;
*a = *b;
*b = temp;
}
🔹 Swap을 이용한 해결 방법
이 방법에서도 위와 같이 공유하는 boolean 변수 lock을 false로 초기화 해둔다.
lock 변수가 true라면 어떤 프로세스가 Critical Section에 접근 중임을 의미해서 락을 거는 것과 같은 효과를 낸다.
또, 공유하는 변수 말고 각각의 프로세스 마다 key라는 변수를 둔다.
두개의 프로세스가 동시에 Critical Section에 접근하려고 하면?
임의의 하나가 실행된다. P1이 선택되었다고 가정하면,
key1=true;
swap으로 인해 lock=true, key1=false가 되면서 Critical Section에 진입하게 된다.
이때 time slice로 인해 P2로 CPU가 넘어갔다고 하면, key2=true, lock=true이기 때문에 Critical Section에 접근하지 못하고 무한 루프 상태에 걸려 대기하게 된다.
이런 식으로 Swap 명령어를 통해서 락을 구현할 수 있다.
Mutex Locks (SpinLock)
acquire() 와 realse() 두 함수로 Critical Section 문제를 SW적으로 해결하는 방법이다.
Mutual Excluesion에서 mut+ex를 따서 Mutex lock이라고 부른다고 한다.
아무것도 하지않고 기다리기만 하니까 busy waiting 이라고 한다.
acquire()은 lock이 true인지 false인지 알아와서 true라면 lock을 이용할 수 있는 상태이고, false면 l다른 process가 사용 중이다.
그림에서와 같이 cpu가 p0을 실행하고 CS에 진입한 상태라면, p1은 acquire()에서 무한 루프로 busy waiting 중일 것이다.
이 방법은 "busy waiting"을 필요로 한다. 이런 특징 때문에 여기서의 lock을 Spinlock이라고 부른다!
이런 Busy Waiting은 CPU 낭비를 하기 때문에, Spinlock에 걸리게 하기 보다는, 이런 상황이 발생할 때 해당 프로세스를 wait 상태로 보내주는 것이 좋겠다.
하지만 그러려면 Context Switch가 일어나야하고, 그 또한 cpu 낭비가 된다.
따라서 busy waiting이 짧다면 차라리 busy waiting이 아무것도 안하는 거여서 좋을 수 있다. 이런 상황에 알맞게 잘 설정해주어야 한다.
Semaphore
Semaphore은 Critical Section 문제 뿐만이 아니라 일반적인 동기화 문제 해결방법으로 쓰이는 Synchronization Tool이다.
S라는 Semaphore 정수 변수가 있고, wait(), signal()이라는 두 함수로만 접근이 가능하다.
wait(S){
while(S <= 0);
S--;
}
signal(S) {
S++;
}
동작 방식은 복잡하지만, 간단히 말하자면 S-- 나 S++ w중에는 context switch가 일어나서는 안된다.
Semaphore 변수를 적절한 수로 초기화를 하고, signal()과 wiat()을 적절히 배치한다면 항상 S1 다음 S2가 실행되도록 만들 수 있다.
🔹Semaphore with no Busy Waiting
운영체제가 block()과 wakeup()이라는 system call 함수를 제공해서 busy waiting이 없는 Semaphore를 만들 수 있다.
block()
호출한 process를 waiting queue로 보낸다.
wakeup()
waiting queue에서 꺼내서 ready queue에 보낸다.
이렇게 wait에서 busy waiting이 걸리게 되면 block()을 통해 wating queue로 보내버릴 수 있고, signal에서는 wakeup을 통해 ready queue로 보내서 cpu 낭비가 되지 않도록 구현하는 방법도 있다.