[운영체제/OS] 동기화 문제 - 세마포어(Semaphore)

동기화 문제가 발생할 수 있는 경쟁 상황과 그것의 해결 방안인 임계 구역을 지난번에 알아보았다.

(https://highlaw00-dev.tistory.com/62)

 

해결 방안 중 세마포어에 대해서 알아보자.

 

세마포어는 신호등과 같은 신호전달기를 의미한다.

서론

 

세마포어가 무엇인지 알기 전에, 아래 사례가 임계구역을 만족하는지 알아보자!

A 회사의 대표인 B씨.
B씨의 회사에 존재하는 프린터는 스풀링 기능이 지원되지 않아 동시에 여러 PC에서 프린트를 요청하면 요상한 출력물이 나온다!
이것을 해결하기 위해 B씨는 프린터를 프린터 룸에 격리시키고, 자신의 방에 프린터 룸의 열쇠를 놓았다.
이제 직원들은 다음과 같은 프로세스를 거쳐 프린터를 사용한다.

1. 프린터를 하고 싶은 직원은 대표의 방으로 간다.
2. 프린터 룸의 키가 있는지 확인한다.
3. 프린터 룸의 키가 있다면 가져가 프린터 룸에서 작업을 한다. (단, 혼자 들어가야 하고 외부인의 출입을 막아야한다)
3-1. 만약 없다면, 열쇠가 반납될 때 까지 기다린다.
4. 작업이 끝나면 대표의 방에 열쇠를 가져다 둔다.

 

위 사례를 상상해보면 임계구역의 조건 중 하나인 Mutual exclusion를 완벽히 만족한다고 볼 수 있다. Progress나 bounded waiting 조건은 명시되지 않아 만족한다고 확언할 순 없지만 가정사항을 일부 추가해주면 손쉽게 만족한다.

 

경쟁 상황(Race condition)은 공유되는 리소스가 동시에 접근되고 갱신되기 때문에 발생하는 문제이다.

위 사례에서 보호해야하는 리소스는 단언컨대 프린터이다.

 

그렇다면 위 사례에서 프린터를 보호하기 위해 어떤 개념을 도입했는가? 바로 열쇠라는 한정된 자원을 도입하였다.

 

세마포어란, 위 사례에서 등장한 열쇠와 비슷한 개념이다.

 

 

세마포어

 

세마포어는 정수형 변수(S)이다. S가 의미하는 바는 열쇠의 개수이다.

또, 세마포어는 2가지의 연산을 지원하는데 그것은 wait()와 signal() 이다. 이 연산은 반드시 원자성을 보장해야한다.

 

wait() 의 수도 코드

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

 

signal() 의 수도 코드

signal(S) {
    S++;
}

 

위 두 연산은 반드시 원자성을 보장한다고 가정할 때, 다음과 같은 과정으로 앞서 서술한 임계 구역을 구현해낼 수 있다.

세마포어 변수 S에 접근하여 임계 구역에서의 작업을 하려는 스레드 2개가 존재한다고 해보자!
세마포어 변수 S의 초기값은 1이라고 가정할 때, 먼저 수행된 스레드가 wait(S)을 호출하고 while문을 탈출한다.
이후 임계구역에서 작업을 수행한다. 이 때, 문맥 교환이 일어나 또 다른 스레드는 wait(S)을 호출하고 S의 값이 0이기 때문에 busy wait을 하게 된다. (busy wait은 CPU 사이클을 소모하며 기다리는 것을 의미한다)

처음 수행된 스레드가 임계 구역에서의 작업을 마치고 signal(S)를 호출하면 그제서야 후발 스레드가 wait으로부터 빠져나와 임계 구역에 들어가게 된다.

 

이진 세마포어, 카운팅 세마포어

 

세마포어는 정수형 변수라고 하였고, 그 값은 열쇠의 개수를 의미한다고 하였다. (정확히는 남아있는 열쇠의 개수)

만약, 세마포어가 0과 1의 값만을 가질 수 있다면 그것은 이진 세마포어이고 여러 값(가령 2 이상)을 가질 수 있다면 카운팅 세마포어라고 한다.

 

카운팅 세마포어의 경우, 가용한 리소스의 개수가 세마포어의 값이라고 생각하면 된다. (이 부분은 확실하지 않으나 예를 들어 데이터베이스 풀 같은 경우 커넥션의 개수가 세마포어의 값이 될 수 있겠다)

 

세마포어의 구현

 

wait() 연산의 수도 코드를 살펴보면, 세마포어 변수 S의 값이 양수가 될 때 까지 무한정 기다리는 것을 확인할 수 있다.

이렇게 CPU 사이클을 소모하며 어떤 리소스나 인터럽트를 기다리는 것을 Busy wait이라 하며 임계 구역의 길이에 따라 매우 비효율적일 수 있다.

 

Busy waiting을 하지 않는 세마포어를 구현하기 위해선 다음과 같은 동작의 세마포어를 생각할 수 있다!

 

A회사의 대표 B씨는 프린터 룸에 관한 민원 때문에 골치 아프다.

하루에 프린터를 사용하는 직원들이 수십명인데 프린터 룸의 열쇠를 기다리기 위해서 직원들이 줄을 서서 기다리는 것이다!
이 문제를 해결하기 위해 사원 C씨가 다음과 같은 아이디어를 냈다.

"프린터 룸에 들어가고 싶은 사람들은 대기 명단에 이름을 적어두고, 프린터 룸 대기열을 관리하는 관리인을 한 명 둡시다. 그리고 프린터 룸이 비게 되면 관리인이 대기 명단의 가장 윗 쪽에 적힌 사람을 직접 부르죠!"

 

이것을 운영체제의 세계에서 해석해보자면...

 

1. 프로세스가 wait() 연산을 수행했을 때, 만약 세마포어 변수가 양수가 아니라면 해당 프로세스는 자신을 일시 중지 시킨다.
2. 일시 중지된 프로세스는 "세마포어 큐"에 삽입되어 대기 상태로 전환된다.
3. 임계구역에서 나온 프로세스는 signal() 연산을 수행할 때, "세마포어 큐"에 있는 프로세스를 wake 시킨다.
4. wake 된 프로세스는 임계구역으로 들어간다.

 

 

자 이제 세마포어의 구현과 wait, signal의 자세한 코드를 봐보자.

 

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

 

이전과 다르게 세마포어는 정수형 변수 value와 프로세스 리스트를 의미하는 list를 가진다.

프로세스가 세마포어를 기다려야 되는 상황이 되면, 해당 프로세스를 프로세스 리스트에 추가한다.

그리고 signal() 연산은 프로세스 리스트에서 한 프로세스를 꺼내 그 프로세스를 깨워준다!

 

wait()

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list; // list에 현재 프로세스 삽입
        sleep(); // 현재 프로세스 대기
    }
}

 

signal()

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

 

 

wait과 signal의 동작을 살펴보자.

 

wait 연산은 세마포어 변수의 값을 decrement한다.
이후 세마포어 변수의 값이 0보다 작다면 해당 프로세스를 대기시킨다.

signal 연산은 세마포어 변수의 값을 increment한다.
이후 세마포어 변수의 값이 0 이하 라면 세마포어를 대기중인 프로세스를 깨운다.

세마포어 변수의 값이 양수라면 남아있는 가용한 리소스의 개수를 의미하고, 음수라면 해당 세마포어를 대기하는 프로세스의 개수를 의미한다.

 

 

세마포어의 원자적 실행

 

앞서 언급했듯이 세마포어 wait과 signal은 원자적 수행이 보장되어야 합니다.

싱글 프로세서 환경이라면 wait, signal 연산이 수행되는 동안 인터럽트를 disable하면 된다. 인터럽트가 disable 된다는 것은 문맥 교환이 일어나지 않는다는 것이기도 하다.

 

반면, 멀티 프로세서 환경이라면 원자적 수행의 보장을 위해 조금 다른 방법을 적용해야한다. 물론 무식하게 모든 코어의 인터럽트를 금지하는 등의 방법이 있을 수 있겠지만 오버헤드가 상당하다. 따라서 compare_and_swap() 과 같은 명령어나 스핀락과 같은 기법을 사용하는데 이것은 다음에 알아보자.

 

 

정리

• 세마포어는 동기화 문제를 해결하기 위한 방법 중 하나이다.
• 세마포어 변수는 가용한 리소스의 개수를 의미한다.
• 세마포어 기법은 wait() 연산과 signal() 연산이 존재한다. wait 연산은 리소스를 lock하는 개념으로도 볼 수 있고, signal 연산은 리소스를 unlock하는 개념으로 볼 수도 있다.
• 공유 리소스를 Busy waiting 하지 않고 sleep, wake하는 방법이 존재한다. (세마포어 큐의 도입)
• wait(), signal() 연산은 반드시 원자적 수행이 보장되어야 한다.