critical section 동기화 2

critical section의 동기화를 성립하기위해서는 3가지 조건을 만족해야 한다고 했다.

1. mutual exclusion(상호 배제)
2. bounded waiting(한정된 대기)
3. progress(진행의 융통성)

1. 피터슨 알고리즘

이전의 bounded waiting(한정된 대기)의 코드와 비슷한데 여기에 turn이라는 개념을 도입하였다.

위 코드는 mutual exclusion은 해결했지만, bounded waiting 문제가 발생한다. 이는 lock1=true가 실행될 때, 타임슬롯이 소모되고 프로세스 p2가 lock2=true가 실행될 때 타임슬롯이 소모되면 서로 데드락(deadlock)이 걸려 무한 대기하기 때문이다.

그래서 turn이라는 개념을 활용하여, lock을 걸면서 다음의 상대에게 turn을 넘겨주는 것이다. 이렇게 되면 둘 다 lock을 걸어도 상대에게 turn을 주어 마지막으로 turn을 받은 process가 실행이 되게 된다.

즉, turn을 상대에게 서로 양보하는 것이다.

피터슨 알고리즘은 critical section 해결의 세 가지 조건을 만족하지만 2개의 프로세스만 사용할 수 있다는 한계가 있다. 여러 프로세스가 하나의 critical section을 사용하려면 공유 변수를 추가하고 코드를 변경해야 한다.

2. 데커 알고리즘

데커 알고리즘은 다음과 같이 작동한다.

1. 프로세스 P1은 우선 잠금을 건다(lock1 = true)
2. 프로세스 p2의 잠금이 걸렸는지 확인한다(while(lock2 == true))
3. 만약 프로세스 p2도 잠감을 걸었다면 누가 먼저인지 확인한다.( if(turn == 2)) 만약 프로세스 p1의 차례라면(trun = 1) 임계구역으로 진입한다. 만약 프로세스 p2의 차례라면 (trun =2) 4로 이동한다.
4. 프로세스 p1은 잠금을 풀고(lock1 = false) 프로세스 p2가 작업을 마칠 때까지 기다린다. (while(turn==2)) 프로세스 p2가 작업을 마치면 잠금을 걸고(lock1=true) 임계구역으로 진입한다.

피터슨 알고리즘이나 데커 알고리즘은 임계구역 해결의 세가지 조건을 모두 만족하지만 매우 복잡하다. 프로세스가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해진다.

그래서 굉장히 쉽고 간결한 해결 방법들이 등장하게 된다.

3. 세마포어(semaphore)

하드웨어적 해결방법, 피터슨, 데커 알고리즘 3개는 busy waiting을 사용하기 때문에 자원 낭비도 심하고 알고리즘도 복잡하다.

이러한 단점을 해결하기위해 다익스트라는 세마포어라는 알고리즘을 제시하였다.

세마포어는 critical section에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어간다. 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다. 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다. 세마포어는 다른 알고리즘과 달리 임계구역이 잠겼는지 직접 점검하거나 busy waiting을 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

세마포어는 3가지 방식으로 이루어져 있다.

1. Semaphore(n)로 초기 설정을 한다. 이 때 n은 공유 가능한 자원의 수를 나타낸다.
2. P()으로 임계구역에 들어가기 전에 사용중이라는 표시를 한다
3. V()으로 임계구역에 나올 때 비었다고 표시한다.

Semaphore(n);
P()
//임계구역
V()

세마포어가 어떻게 작동하는지 세마포어 내부 코드를 통해 알아보자

대기할 때는 block() 코드를 사용한다.

1. Semaphore(n) : 전역 변수 RS를 n으로 초기화한다. RS에는 현재 사용 가능한 자원의 수가 저장된다.
2. P() : 잠금을 수행하는 코드로 RS가 0보다 크면(사용 가능한 자원이 있다면) 1만큼 감소시키고 임계구역에 진입한다. 만약 RS가 0보다 작으면(사용할 수 있는 자원이 없으면) 0보다 커질 때까지 기다린다.
3. V() : 잠금 해제와 동기화를 같이 수행하는 코드로 , RS 값을 1 증가시키고 세마포어에서 기다리는 프로세스에 임계구역에 진입해도 좋다는 wake_up 신호를 보낸다.

세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up신호를 받으면 큐에서 나와 임계구역에 진입한다. 따라서 busy waiting하는 프로세스가 없게 된다.

그러나 세마포어의 P(), V() 내부 코드가 실행되는 도중에 context switching이 발생하면 mutial exclusion과 bounded waiting 조건을 보장하지 못한다. 따라서 P(), V()의 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고 완전히 실행되게 해야 한다. 즉, atomicity가 보장되어야 한다.

3.1 예시

위의 그림에서 공유 자원은 예금 하나이므로 RS(resource)의 초깃값은 1이다.

1. 먼저 도착한 프로세스 P1이 임계구역에 진입한다. 현재 RS는 1이므로 이 값을 1 감소시키고 임계구역에 진입한다.
2. 나중에 도착한 프로세스 P2는 현재 RS값이 0이므로 프로세스 P1이 임계구역에 빠져나올 때까지 세마포어 큐에서 기다린다.
3. 프로세스 P1은 현재 예금이 10만원 인 것을 확인하고 10만원을 더해 20만원으로 바꾼 다음 작업을 마친다.
4. 프로세스 P1은 V()를 실행하여 RS 값을 1 증가시키고 wake_up 신호를 프로세스 P2에 보낸다.
5. block 상태에 있던 프로세스 P2는 다시 일어나 코드를 실행시킨다.

세마포어는 공유 자원이 여러 개일 때도 사용할 수 있다. 위 그림은 세마포어를 사용하여 2개의 공유 자원을 가지고 3개의 프로세스가 작업하는 예를 나타낸 것이다.

1. 프로세스 P1은 RS 값을 1 감소시키고 임계구역에 진입한다.
2. 프로세스 P2도 RS 값을 1 감소시키고 임계구역에 진입한다.
3. 프로세스 P3은 RS 값이 0이므로 다른 프로세스가 임계구역을 빠져나올 때까지(RS가 0보다 커질 때까지) 기다린다.
4. 프로세스 P1이 작업을 마치고 V()를 실행하면 RS 값은 1이 되고, wake_up 신호가 프로세스 P3에 전달된다.
5. 프로세스 P3이 임계구역에 진입한다.

4. Mutex

뮤텍스는 사실 세마포어의 공유자원(RS)가 1일 때를 말한다. 즉, 세마포어는 뮤텍스의 특별한 버전으로 RS가 1 이상일 때를 말한다. 따라서, 뮤텍스와 세마포어는 구동 방법, 원리가 모두 같다.

wait(mutex);
// critical section
signal(mutex);

세마포어가 P(), V() 연산으로 이루어져 있다면, 뮤텍스는 wait(mutex), signal(mutex)로 이루어져 있다. 이름만 다를 뿐이지 내부 연산은 같으므로 사실 이름은 크게 중요하지 않다. 즉, wait을 하면 공유자원 mutex(이전에는 RS)를 하나 감소시키고, signal을 하면 mutex를 하나 증가시키고 block 상태에 빠져있는 프로세르를 뮤텍스 큐에서 깨워 ready queue로 보내는 역할을 한다. 따라서 뮤텍스 역시도 세마포어와 같이 3가지 임계구역 조건인 mutual exclusion, bounded waiting, progress를 지키며, busy waiting을 하지않은 효율적인 알고리즘이다.

다음과 같이 mutex는 공유 자원이 하나일 때를 말한다.

1. 프로세스 P1이 먼저 wait(mutex)을 호출하여 mutex = 0으로 만들고 임계 구역에 진입한다.
2. 프로세스 P2가 wait(mutex)을 호출하지만 mutex는 이미 0이므로 임계 구역에 진입하지 못하고 block된다. mutex queue에 들어간다.
3. 프로세스 P3가 wait(mutex)을 호출하지만 mutex는 이미 0이므로 임계 구역에 진입하지 못하고 block된다. mutex queue에 들어간다.
4. 프로세스 P1이 임계구역의 일을 마치고 signal(mutex)을 호출하여 mutex = 1로 만들고 mutex queue에서 block 상태인 프로세스 P2를 깨운다.
5. 프로세스 P2는 ready queue에 들어가고 다시 wait(mutex)을 호출하고 mutex = 0으로 만들고 임계 구역에 진입한다.
6. 프로세스 P2이 임계구역의 일을 마치고 signal(mutex)을 호출하여 mutex = 1로 만들고 mutex queue에서 block 상태인 프로세스 P3를 깨운다.
7. 프로세스 P3는 ready queue에 들어가고 다시 wait(mutex)을 호출하고 mutex = 0으로 만들고 임계 구역에 진입한다.

세마포어는 mutex의 특별한 버전으로 공유자원이 n개 일 때(n >= 1)를 말한다는 것을 알아두자.

5. 모니터

세마포어의 가장 큰 문제는 잘못된 사용으로 인해 임계구역이 보호받지 못한다는 것이다.

다음은 세마포어의 잘못된 사용으로 문제가 발생한 경우이다.

1. 세마포어를 사용하지 않고 임계구역에 들어갈 때, 임계구역이 보호받지 못한다. 즉, mutual exclusion이 보장되지 않아 race condition이 발생한다.
2. P()만 두 번 사용하고 V()를 사용하지 않아서 wake_up 신호가 발생하지 않은 경우 무한대기 상태가 발생한다.
3. P()와 V()를 반대로 사용하여 mutual exclusion이 보장되지 않는다.

만약, 공유자원을 사용할 때 모든 프로세스가 세마포어 알고리즘을 따른다면 굳이 P(), V()를 사용할 필요 없이 자동으로 처리하도록 하면 된다. 이를 실제로 구현한 것이 모니터이다. 모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화를 시킨다.

모니터는 system call과 같은 개념으로 생각하면 된다. 운영체제의 자원을 일반 사용자가 접근하는 것을 허용하지 않기 위해서 시스템 자원을 숨기고 인터페이스만 제공하는 system call처럼, 모니터도 보호할 자원을 임계 구역으로 숨기고 임계구역에서 작업할 수 있는 인터페이스만 제공하여 자원을 보호한다.

모니터의 특징은 다음과 같다.

1. 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P(), V()를 사용하지 않고 모니터에 작업을 요청한다.
2. 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.

위의 예제에서 예금 공유자원을 사용한 것을 보았다. 해당 예제를 모니터는 어떻게 해결하는 지 보도록 하자

monitor shared_balance{
    private:
     int balance = 10;
     boolean busy = false;
     condition mon;
    public:
     increase(int amount){
        if(busy == true) mon.wait();
        busy = true;
        balance = balance + amount;
        mon.signal();
     }
}

프로세스 P1, P2가 increase() 함수를 호출한다고 하자, 이 때 모니터를 이용한 코드가 다음과 같다.

모니터는 임계구역 보호와 동기화를 위해 내부적으로 조건 변수(condition variable) 사용한다. condition variable은 특정 조건이 완료될 때까지 block상태로 만든다는 의미이다. 다음의 기능이 있는데 위의 변수 mon이 condition variable이다.

1. wait() : 모니터 큐에서 자신의 차례가 올 때까지 기다린다. 세마포어 P()의 block과 같다.
2. signal() : 모니터 큐에서 기다리는 다음 프로세스에 순서를 넘겨준다. 세마포어의 V()에 해당한다.

우리가 설정한 공유자원 balance는 increase 함수를 통해서만 접근이 가능하다. increase는 임계구역이 잠겼는지 busy를 check하게 된다. busy는 하나의 lock과 같은 기능을 하고, lock이 걸려있다면 mon.wait()을 호출되어 block상태에 빠지게 되고 모니터 큐에서 기다리게 된다. lock이 안걸려있다면 임계구역에 들어가게 된다.

만약 프로세스 P1이 increase를 사용하고 balnce = balance + amount을 호출하기 전에 타임 슬롯이 마감되어 ready queue에 돌아간다고 하자. 이 때 프로세스 P2가 increase를 사용한다면 P2는 busy가 true이기 떄문에 모니터 큐에 배치되고 block 상태로 간다. P1이 임계구역의 작업을 완료하고 mon.signal을 호출하면 busy = false 바꿔주고, wake_up()을 통해 프로세스 P2를 깨워 ready queue로 보낸다.

이렇게 모니터는 불필요한 정보를 숨기고 공유 자원에 대한 인터페이스만 제공하는 점에서 오늘 날 객체 지향의 information hiding과 매우 닮았다.

6. condition variable vs mutex vs semaphore vs lock

출처 : https://stackoverflow.com/questions/3513045/conditional-variable-vs-semaphore

1. lock은 mutual exclusion을 보장할 뿐 bounded waiting, progress을 보장하진 못한다. 또한 busy waiting의 문제도 있다. 이를 해결하기 위해 mutex 개념이 등장했다.
2. mutex는 공유 자원 수가 1일 때를 말한다. 공유자원을 RS라고, 또는 mutex라고도 부른다. 3가지 동기화 조건을 모두 만족하고 busy waiting이 아닌 큐를 통한 wake_up 개념을 사용한다.
3. semaphore는 공유 자원 수가 1 이상일 때를 말한다. 즉, mutex의 특별한 버전으로 semaphore가 된다. 따라서 3가지 동기화 조건을 모두 만족하고 busy waiting이 아닌 큐를 통한 wake_up 개념을 사용한다.
4. condition variable은 공유 자원 카운팅을 필수로 사용하지 않는다. 즉, mutex와 semaphore 처럼 공유자원(RS, mutex, semaphore라고 불린다)을 counting하는 방식이 아닌, lock과 함께 사용되어 큐를 이용할 수 있다. 즉, 큐가 필수적으로 필요하지 공유자원을 필수로 하진 않는다. 물론 공유자원을 사용하여 counting하는 방식도 가능하다. 동기화 3가지 조건은 만족하지 못하지만 busy waiting을 해결하기 위해 사용된다.

즉, semaphore는 counter(++, -- 연산) + mutex(공유 자원을 카운팅하는 변수) + wait queue로 이루어져있고, condition variable은 wait queue만을 만족하면 되고 busy waiting문제를 해결하기위해 도출되었다.

어떻게 구현하느냐는 사용자들의 몫이기 때문에 이들 간의 개념이 섞이거나 상관없이 사용하는 경우가 많다. 그러나 본래적인 의미는 위와 같으므로 조심하도록 하자.