critical section의 동기화를 성립하기위해서는 3가지 조건을 만족해야 한다고 했다.
이전의 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을 사용하려면 공유 변수를 추가하고 코드를 변경해야 한다.
데커 알고리즘은 다음과 같이 작동한다.
피터슨 알고리즘이나 데커 알고리즘은 임계구역 해결의 세가지 조건을 모두 만족하지만 매우 복잡하다. 프로세스가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해진다.
그래서 굉장히 쉽고 간결한 해결 방법들이 등장하게 된다.
하드웨어적 해결방법, 피터슨, 데커 알고리즘 3개는 busy waiting을 사용하기 때문에 자원 낭비도 심하고 알고리즘도 복잡하다.
이러한 단점을 해결하기위해 다익스트라는 세마포어라는 알고리즘을 제시하였다.
세마포어는 critical section에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어간다. 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다. 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다. 세마포어는 다른 알고리즘과 달리 임계구역이 잠겼는지 직접 점검하거나 busy waiting을 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.
세마포어는 3가지 방식으로 이루어져 있다.
Semaphore(n)
로 초기 설정을 한다. 이 때 n은 공유 가능한 자원의 수를 나타낸다.P()
으로 임계구역에 들어가기 전에 사용중이라는 표시를 한다V()
으로 임계구역에 나올 때 비었다고 표시한다.Semaphore(n);
P()
//임계구역
V()
세마포어가 어떻게 작동하는지 세마포어 내부 코드를 통해 알아보자
대기할 때는 block() 코드를 사용한다.
wake_up
신호를 보낸다.세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up
신호를 받으면 큐에서 나와 임계구역에 진입한다. 따라서 busy waiting하는 프로세스가 없게 된다.
그러나 세마포어의 P()
, V()
내부 코드가 실행되는 도중에 context switching이 발생하면 mutial exclusion
과 bounded waiting
조건을 보장하지 못한다. 따라서 P()
, V()
의 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고 완전히 실행되게 해야 한다. 즉, atomicity가 보장되어야 한다.
위의 그림에서 공유 자원은 예금 하나이므로 RS(resource)의 초깃값은 1이다.
세마포어는 공유 자원이 여러 개일 때도 사용할 수 있다. 위 그림은 세마포어를 사용하여 2개의 공유 자원을 가지고 3개의 프로세스가 작업하는 예를 나타낸 것이다.
뮤텍스는 사실 세마포어의 공유자원(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는 공유 자원이 하나일 때를 말한다.
wait(mutex)
을 호출하여 mutex = 0으로 만들고 임계 구역에 진입한다.wait(mutex)
을 호출하지만 mutex는 이미 0이므로 임계 구역에 진입하지 못하고 block된다. mutex queue에 들어간다.wait(mutex)
을 호출하지만 mutex는 이미 0이므로 임계 구역에 진입하지 못하고 block된다. mutex queue에 들어간다.signal(mutex)
을 호출하여 mutex = 1로 만들고 mutex queue에서 block 상태인 프로세스 P2를 깨운다.wait(mutex)
을 호출하고 mutex = 0으로 만들고 임계 구역에 진입한다.signal(mutex)
을 호출하여 mutex = 1로 만들고 mutex queue에서 block 상태인 프로세스 P3를 깨운다. wait(mutex)
을 호출하고 mutex = 0으로 만들고 임계 구역에 진입한다.세마포어는 mutex의 특별한 버전으로 공유자원이 n개 일 때(n >= 1)를 말한다는 것을 알아두자.
세마포어의 가장 큰 문제는 잘못된 사용으로 인해 임계구역이 보호받지 못한다는 것이다.
다음은 세마포어의 잘못된 사용으로 문제가 발생한 경우이다.
만약, 공유자원을 사용할 때 모든 프로세스가 세마포어 알고리즘을 따른다면 굳이 P(), V()를 사용할 필요 없이 자동으로 처리하도록 하면 된다. 이를 실제로 구현한 것이 모니터이다. 모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화를 시킨다.
모니터는 system call과 같은 개념으로 생각하면 된다. 운영체제의 자원을 일반 사용자가 접근하는 것을 허용하지 않기 위해서 시스템 자원을 숨기고 인터페이스만 제공하는 system call처럼, 모니터도 보호할 자원을 임계 구역으로 숨기고 임계구역에서 작업할 수 있는 인터페이스만 제공하여 자원을 보호한다.
모니터의 특징은 다음과 같다.
위의 예제에서 예금
공유자원을 사용한 것을 보았다. 해당 예제를 모니터는 어떻게 해결하는 지 보도록 하자
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
이다.
우리가 설정한 공유자원 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과 매우 닮았다.
출처 : https://stackoverflow.com/questions/3513045/conditional-variable-vs-semaphore
즉, semaphore는 counter(++, -- 연산) + mutex(공유 자원을 카운팅하는 변수) + wait queue로 이루어져있고, condition variable은 wait queue만을 만족하면 되고 busy waiting문제를 해결하기위해 도출되었다.
어떻게 구현하느냐는 사용자들의 몫이기 때문에 이들 간의 개념이 섞이거나 상관없이 사용하는 경우가 많다. 그러나 본래적인 의미는 위와 같으므로 조심하도록 하자.
와 글 진짜 잘쓰시네요.. 요즘 님 OS 글 보면서 공부하고있습니당