[OS] 뮤텍스, 세마포어, 모니터

이번 포스팅에서는 뮤텍스, 세마포어, 모니터에 대해 알아보겠습니다. 뮤텍스와 세마포어를 어떻게 구현할 수 있는지, spin lock의 장단점은 무엇인지, binary 세마포어와 뮤텍스는 어떤 차이가 있는지를 이해할 수 있습니다. 그리고 모니터의 conditional variable과 entry queue를 보고 게시물에서 첨부한 모니터의 schematic view를 이해할 수 있습니다.

 

만약, 동기화를 해야하는 이유와 락을 걸고 해제하는 과정을 모른다면 먼저 아래 게시물을 보고 이 게시물을 읽는 것을 추천합니다.

https://mini98.tistory.com/69

[OS] 동기화 문제, Peterson's solution, 하드웨어 명령어

목차

1. Mutex Lock
2. Semaphores
3. Monitor

---

1. Mutex Lock

이전에 하드웨어적으로 지원하는 동기화 함수, test_and_set과 compare_and_swap를 학습했습니다. 이번에 다룰 내용 Mutex Lock로, 하이 레벨의 소프트웨어 도구로서 더 간편하게 critical section problem을 해결할 수 있습니다.

while (true) {
    acquire lock
    critical section
    release lock
    remainder section
}

critical section에 들어가기 전에 lock을 획득하고, 작업을 마치고 critical section에서 나오면 lock을 반환합니다. acquire()와 release()를 어떻게 구현하는지 살펴보겠습니다.

acquire() {
    while (!available); /* busy waiting */
    available = false;
}

release() {
    available = true;
}

mutex lock은 공유변수로 boolean 변수 available을 사용합니다. 말 그대로 available은 lock을 현재 사용할 수 있는지를 나타내는 변수입니다.  프로세스가 acquire()를 호출했을 때 만약 락을 얻을 수 없다면, 다른 프로세스가 release()할 때까지  while문 내에서 대기합니다.

 

두 함수 acquire()과 release() 모두 당연히 atomic하게 동작합니다.

Busy waiting

acquire()를 호출하면 락을 얻을 때까지 (즉 available이 true가 될때까지) while 문에서 대기합니다. while 문에서 대기하는 동안 lock을 얻을 수 있는지 계속 확인하며 CPU를 의미 없이 계속해서 점유합니다. 그래서 mutex lock을 다른 말로 spin lock이라고 표현하기도합니다.

CPU 사이클을 낭비한다는 단점도 있지만 장점도 있습니다. 락을 기다리는 동안 컨텍스트 스위칭을 하지 않는다는 것입니다. 컨텍스트 스위칭은 그 자체로 오버헤드기 때문에, 멀티코어 환경에서 컨텍스트 스위칭이 빈번하게 일어날 것 같다거나, critical section에서의 작업량이 적어서 lock을 조금 쥐고 있을 것 같으면, 의도적으로 spin lock을 선택하기도 합니다.

2. Semaphores

세마포어는 뮤텍스와 비슷하게 동작하지만, 조금 더 많은 기능을 제공합니다. 세마포어는 뮤텍스와 다르게 boolean 변수가 아닌 integer 변수 S를 갖습니다. 이 정수 값은 얻을 수 있는 자원의 개수라고 생각하면 좋습니다. 세마포어 S를 바꾸려면 wait()와 signal() 함수로 접근을 해야만 바꿀 수 있습니다. wait()는 세마포어를 획득하는 과정이고 signal()은 세마포어를 반납하는 함수입니다.

wait(S) {
    while (S <=0 ); /* busy waiting*/
    S--;
}

signal(S) {
    S++;
}

세마포어 구현

위처럼 구현하면 뮤텍스 락과 마찬가지로, busy waiting으로 CPU를 낭비할 수 있습니다. block & wakeup 방식으로 wait()와 signal()을 수정해보겠습니다. block & wait 방식은 while문을 돌면서 기다리는게 아니라 프로세스를 block시켜 잠들게 한 뒤에 공유데이터를 가지고 있던 프로세스가 세마포어를 내놓으면 그 때 다시 깨어나 레디큐에 보내는 방식입니다.

세마포어 재정의

typedef struct {
    int value;
    struct process *list;
} semaphore;

value는 세마포어의 변수 값이고 list는 잠들어 있는 프로세스를 연결하기 위한 큐 입니다. 프로세스가 세마포어를 얻을 수 없으면 커널은 프로세스를 wait 큐에 넣고, signal()을 호출하면 wait 큐에서 잠든 프로세스 중 하나를 꺼내서 레디큐로 옮길 수 있습니다. 아래와 같이 구현할 수 있습니다.

wait(semaphohre *S) {
    s->value--;
    if (s->value < 0) {
        add this process to S->list;
        sleep();
    }
}

signal (semaphore *S) {
    s->value++;
    if (s->value <=0 ) {
        remove a process P from S->list;
        wakeup(P);
    }
}

 

위처럼 block&wait 방식으로 구현한 것과 busy waiting으로 구현한 것이 어떤 차이가 있을까요? busy waiting으로 구현했을 때는 semaphore를 얻을 때까지 기다리고 semaphore를 얻어갑니다. (선 대기 후 sempahore 감소) 그런데 위처럼 구현했을 때는 sempahore 값을 감소시키고 나서 잠듭니다. (선 semaphore 감소 후 대기)

 

다시 정의한 signal 함수를 보면 세마포어 값이 음수일 때를 고려하고 있는 것을 확인할 수 있습니다. busy waiting에서는 세마포어의 의미를 자원의 개수로 생각하지만, block & wait에서는 의미가 조금 다릅니다. 세마포어를 음수라는 것은 다른 프로세스가 자원을 기다리고 있는 것으로 이해하면 좋을 것 같습니다. 그래서 세마포어가 양수면 기다리고 있는 프로세스가 없다는 뜻이기 때문에, wait()를 호출해도 따로 wait큐에서 대기하지 않고 바로 critical section으로 들어가면 되는 것이고, 마찬가지로 signal()에서 세마포어가 양수라면 대기하고 있는 프로세스가 없기 때문에 wake up을 호출하지 않습니다.

 

세마포어를 구현하는 방식으로 busy waiting과 block & wakeup 두 가지 방식을 설명했는데 뮤텍스락에서 설명했듯이 busy waiting은 CPU를 낭비하기 때문에 보통은 block & wakeup을 사용하는 것이 효율적입니다. 하지만 다시 설명해보자면, busy waiting은 대신 컨텍스트 스위칭을 하지 않기 때문에, critical section이 짧거나, context switching이 빈번하게 일어날 것 같다면 busy waiting이 더 좋은 선택일 때도 있습니다.

세마포어 활용

그렇다면 세마포어를 어떻게 활용할 수 있을까요? 리소스에 접근하는 프로세스의 수를 제한하는데 사용할 수 있고, 또 프로세스의 실행순서를 정하는데 사용할 수 있습니다.

 

첫번째 경우, 처음 세마포어는 리소스의 수로 초기화됩니다. 리소스에 접근하는 프로세스가 추가될 때마다 wait()를 호출해서 세마포어를 하나씩 가져갑니다. 세마포어가 0이 되면, 리소스가 전부 사용중이라는 뜻이고 그 다음부터 프로세스는 어떤 프로세스가 signal()로 깨워줘여 세마포어를 얻을 수 있게 됩니다.

 

두번째 경우, 상황을 가정해봅시다. 서로 다른 프로세스 $P_{1}$과  $P_{1}$는 각각 명령어 $S_{1}$과 $S_{2}$를 가지고 있습니다. $S_{1}$은 무조건 $S_{2}$보다 먼저 실행되길 바랍니다. 간단하게 해결할 수 있습니다.  $S_{1}$ 뒤에 signal(synch)를 추가하고, $S_{2}$ 앞에 wait(synch)를 추가하면 됩니다.

 

 $S_{1}$;

signal(synch);

 

wait(synch);

$S_{2}$;

 

synch는 공유변수이고 0으로 초기화됐기 때문에,  $P_{2}$는 $P_{1}$이 signal(synch)을 호출해야만, 대기큐에서 나와 $S_{2}$를 실행할 수 있습니다.

Binary 세마포어는 뮤텍스?

뮤텍스를 바이너리 세마포어로 설명하는 분들도 계신데 사실은 같은 것은 아닙니다. 일단 첫번째로 뮤텍스는 락을 가진 프로세스만 그 락을 해제할 수 있습니다. 하지만 위에서 구현한 것을 확인하면 알 수 있듯이 세마포어는 그렇지 않아서 프로세스의 실행 순서를 동기화시키는 작업도 할 수 있습니다.

 

락을 가진 프로세스만 락을 해제할 수 있다는 특징 때문에, 뮤텍스는 priority inheritance라는 속성을 가집니다. 우선순위가 높은 프로세스도 우선 순위가 낮은 프로세스가 lock을 쥐고 있으면 아무 작업도 못하고 기다리는 문제를 가지기도 합니다. 그래서 뮤텍스에서는 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스에 의존하고 있을 때 낮은 우선순위의 프로세스를 높은 우선순위의 프로세스만큼 우선순위를 올려버리는 전략을 사용하기도 하는데, 이를 priority inheritance라고도 합니다.

3. Monitor

모니터는 세마포어보다도 하이레벨로 concorrency control을 도와주는 도구입니다. 모니터는 프로그래밍 언어 차원에서 동시 접근과 관련된 공유데이터에 접근하는 것을 자동으로 해결시켜줘서 세마포어에 비해 프로그래머에게 부담을 줄여줄 수 있습니다. 

 

모니터 내부에 공유데이터와, 그 공유데이터에 접근하는 코드를 모드 정의합니다. 그래서 공유 데이터에 접근하려면 모니터 안에 정의된 코드를 사용해서만 접근할 수 있게 하고, 그 정의된 코드가 공유데이터에 동시에 접근하려면 모니터가 애초에 막아버립니다. 그래서 프로그래머는 공유데이터에 접근하는 A와 B를 모두 만들고 나서 락을 걸고 풀어주는 코드를 더 추가해줄 필요가 없어집니다. 모니터가 모두 알아서 제어해주기 때문입니다.

모니터

Entry queue

$P_{1})$이 공유데이터를 사용하는 도중에 CPU를 빼앗겼다고 가정해봅시다. 그리고 또 다른 프로세스 $P_{2}$가 공유데이터에 접근하려 합니다. $P_{1}$이 active한 상태로 모니터에 남아있기 때문에,  $P_{2}$는 공유데이터에 접근하지 못하고 $P_{1}$이 다시 CPU를 얻어 작업을 끝낼때까지 Entry queue에서 대기하게 됩니다. 혹은 $P_{1}$이 레디큐에 잠깐 대기해야하는 것이 아니라, 모니터 내부에서 어떤 조건이 충족되지 않아서 잠들게 되면 Entry queue에서 줄 서 있던 $P_{2}$가 모니터 내부로 들어올 수 있습니다.

Condition Variable

$P_{1}$이 어떤 조건을 충족하지 못해서 오랫동안 잠들어야하는 상황입니다. Condition Variable을 사용해서 어떤 조건을 충족하지 못해서 잠들게 된 것인지를 명시할 수 있습니다. Conditional Variable은 세마포어와 같은 값이 아니라 프로세스를 잠들게 하고 줄 세우기 위한 변구입니다. 그래서 만약 x라는 조건을 충족하지 못하면 x라는 condition variable에 가서 줄서서 기다리게 됩니다. condition variable은 두 가지 연산을 지원합니다. 하나는 wait() 하나는 signal()입니다.

어떤 프로세스가 x라는 조건을 충족하지 못하면 x.wait()를 호출해서 위의 그림에서 표현된 것과 같이 condition variable에 줄 서서 기다리게 됩니다. x.signal()을 사용하면 x에서 기다리고 있는 다른 프로세스를 깨워줄 수 있습니다.

조금 이해가 안간다면 다음 포스팅의 생산자 소비자 문제를 보면 더 쉽게 이해할 수 있을 것입니다.

Monitor 사용

모니터 추상화

위 코드는 모니터를 추상화시킨 것입니다. 주로 객체지향 프로그래밍에서 지원합니다. 위처럼 모니터와 이름을 적고, 공유데이터와, 공유데이터에 접근하기 위한 함수를 정의합니다.

https://mini98.tistory.com/70

[자바 스터디] 멀테쓰레드 프로그래밍

이 게시글에서 java를 이용한 모니터 활용 예제를 확인할 수 있습니다.

---

하이레벨의 동기화 도구에 대해 알아봤는데, 다음 게시물에서는 세마포어와 모니터를 활용해서 어떻게 동기화의 고전적인 문제들을 해결할 수 있는지 알아보겠습니다.

Reference

1. 반효경 교수님 KOCW 운영체제 강의

2. Operating System Concepths, TENTH EDITION