운영체제 정리 🦖 ch06. 프로세스 동기화

공유자원 문제

덮어씌우기

현대 시스템은 다중 처리기 시스템이므로 여러개의 작업이 동시에 실행될 수 있으며, 공유 메모리를 사용하여 작업들은 서로에게 영향을 주고받을 수 있습니다. 이러한 현대 시스템 작업의 특징을 병렬성과 협력성이라고 부릅니다.

만약 두 개의 작업이 하나의 공유 영역에 동시에 접근하면 어떤 일이 일어날까요? 아래와 같이 공유변수 v에 쓰기연산을 실행하는 쓰레드를 정의해보겠습니다.

char v = 'X';

void assignToA(){
    _sleep(1000); // 1초 대기
    v = 'A';
}

void assignToB(){
    _sleep(0); // 0초 대기
    v = 'B';
}

int main()
{
    thread a(assignToA);
    thread b(assignToB);
    a.join();
    b.join();
    cout << v;
}

위의 경우에는 v의 결과가 A로 고정됩니다. v = 'A'가 v = 'B'보다 나중에 실행되는 것이 보장되므로 v = 'B'의 영향을 덮어쓰기 때문입니다. 즉, 나중에 실행되는 쪽이 먼저 실행된 쪽의 결과를 덮어씌우게 됩니다.

---

비일관성

이번에는 작업이 2개 이상인 경우를 생각해보겠습니다. 다음 코드는 카운터를 1 증가시키는 쓰레드 100개를 생성하는 코드입니다. 스레드가 모두 정확히 실행되었다면, 최종 결과는 100이 되야 하지만, 실제로는 100보다 작은 값이 출력됩니다.

#include <bits/stdc++.h>
using namespace std;

int value = 0;
void increase(int seq)
{
    int _value = value;
    printf("[%4d] %4d \n", seq, _value);
    value = _value + 1;
}

int main()
{
    vector<thread> threads;
    for (int i = 0; i < 100; i++)
    {
        threads.push_back(thread(increase, i));
    }
    for (int i = 0; i < 100; i++)
    {
        threads[i].join();
    }
    cout << value;
}

그 이유는 printf가 너무 오래 걸리기 때문에 선행 스레드의 value = _value + 1가 실행되기도 전에 후행 스레드의 int _value = value가 먼저 실행되었기 때문입니다. 즉, 위의 코드는 실행 할 때 마다 스레드 간 작업순서에 따라 결과가 달라지게 되며, 이처럼 실행결과가 작업 간 실행순서에 의존하는 상황을 경쟁 상태(Race Condition)라고 부릅니다.

경쟁 상태가 발생한 시스템은 같은 상황이라도 실행순서에 따라 결과가 매번 달라지기 때문에 시스템의 일관성이 무너지게 되므로 항상 경쟁 상태가 발생하지 않도록 유의해야 합니다.

---

임계 영역

개념

이러한 경쟁 상태를 해결하기 위한 기본적인 아이디어는 선행 작업이 공유자원의 사용을 끝낼 때 까지, 후행 작업이 공유자원을 사용할 수 없도록 작업 간 순서를 강제하는 것 입니다.

이러한 개념을 구현한 것이 임계 영역이며, 최대 하나의 작업만이 임계 영역에 접근할 수 있도록 보장하고, 임계 영역에서만 공유 자원을 사용할 수 있도록 강제함으로써, 경쟁 상태를 예방할 수 있습니다.

---

구성 및 요구조건

임계 영역은 다음과 같이 4가지 섹션으로 구성되어 있으며, 세 가지의 요구 조건을 만족해야 합니다.

구성 :

1. 진입 영역 : 임계 영역으로의 접근 허가를 받는 지점
2. 임계 영역 : 공유 자원을 사용하는 지점
3. 퇴출 영역 : 접근 허가를 반납하는 지점
4. 나머지 영역 : 그 외의 영역

요구 조건 :

• 상호 배제 : 최대 하나의 작업만이 임계 영역에 접근할 수 있어야 한다.
• 진행 : 진입 영역에 있는 작업들만 임계 영역에 접근할 기회를 얻을 수 있어야 한다.
• 한정된 대기 : 임계 영역을 요청하는 작업이 기아 상태가 되서는 안된다.

---

임계 영역 구현법

스핀락 계열의 해결안

고전 시스템 해결안

선점이 발생하지 않는다면 피터슨의 해결안을 통해 작업 2개의 공유 자원 문제를 해결할 수 있습니다. 선점이 발생하는 현대 시스템에서는 올바르게 동작하지 않음에 유의해주세요.

필요 변수 :

int turn; // 임계 영역에 접근할 수 있는 작업의 번호
bool flag[2]; // i번째 작업이 임계 영역에 들어갈 준비가 되었는가?

구현 :

#include <bits/stdc++.h>
using namespace std;

int value = 0;
int turn = 0;
bool isReady[2];
void peterson(int n)
{
    //
    // 자신의 준비여부를 true로 설정하지만,
    // 접근 기회는 반대편 작업에게 양보한다.
    isReady[n] = true;
    turn = !n;

    //
    // 자신의 차례가 올 때 까지 대기한다.
    while (isReady[n] && turn == n);

    //
    // 임계 영역.
    {
        int _value = value;
        printf("[%d] %4d \n", n, _value);
        value = _value + 1;
    }

    //
    // 자신의 준비여부를 false로 변경한다.
    isReady[n] = false;
}

int main()
{
    vector<thread> threads;
    for (int i = 0; i < 100; i++)
    {
        threads.push_back(thread(peterson, i % 2));
    }
    for (int i = 0; i < 100; i++)
    {
        threads[i].join();
    }
    cout << value;
}

---

단일 처리기 해결안

단일 처리기 시스템에서는 작업이 병렬로 실행될 수 없기 때문에, 이 경우에서 공유 자원 문제를 일으키는 유일한 원인은 선점입니다. 즉, 선점이 아예 발생할 수 없도록 인터럽트를 불능화하면 공유 자원 문제를 해결할 수 있습니다.

그러나 인터럽트의 불능화는 다중 처리기 시스템에서 매우 비싸고 효율성이 떨어지는 방안이기 때문에, 현대 시스템에서는 사용하지 않습니다.

int value = 0;
void increase(int seq)
{
    //
    // 진입영역 : 인터럽트 off

    //
    // 임계 영역
    {
        int _value = value;
        printf("[%4d] %4d \n", seq, _value);
        value = _value + 1;
    }

    //
    // 퇴출영역 : 인터럽트 on
}

---

원자함수를 이용한 해결안

현대 하드웨어는 Test And Set 또는 Clear 같은 원자적 연산(도중에 선점되지 않는 연산)을 제공합니다.

//
// 해당 불리언 값의 현재 값을 반환하고 true로 고친다.
// 이 연산은 선점되거나 동시에 실행되지 않는다.
bool test_and_set(bool *target){
    bool v = *target;
    *target = true;
    return v;
}

//
// 해당 불리언 값을 false로 고친다.
// 이 연산은 선점되거나 동시에 실행되지 않는다.
void clear(bool *target){
    *target = false;
}

두 개 이상의 작업이 공유 플래그 bool isUsed = false에 대해 동시에 test_and_set을 수행하더라도 해당 연산은 동시에 실행되거나 선점되지 않으므로, 오직 하나의 작업만 false를 반환받음을 보장할 수 있습니다. 이러한 원자적 연산의 특징을 사용하여 Lock을 구현할 수 있습니다.

bool isUsed = false;
int value = 0;
void increase(int seq)
{
    //
    // 진입영역
    while(test_and_set(*isUsed));

    //
    // 임계 영역
    {
        int _value = value;
        printf("[%4d] %4d \n", seq, _value);
        value = _value + 1;
    }

    //
    // 퇴출영역
    clear(*isUsed);
}

---

세마포를 이용한 해결안

원자함수는 기본적으로 하드웨어가 제공하는 Low-Level 기능이므로, 대다수의 프로그래머들이 사용하기에는 적합하지 않습니다. 이러한 어려움을 극복하기 위해 운영체제에서 제공하는 세마포라는 동기화 도구를 사용할 수 있습니다.

세마포는 내부적으로 공유자원의 개수로 초기화된 카운팅을 가지고 있으며, 공유 자원을 빌려줄 때 마다 1씩 감소하고, 공유 자원이 반납될 때 마다 1씩 증가하도록 설계되어 있습니다. 카운팅이 0이라면 공유 자원이 반납될 때 까지 대기합니다.

아래의 코드는 세마포의 개념적 구현입니다. 개념적으로는 동일하지만, 실제 세마포의 기능을 수행하지 못하는 코드임에 유의해주세요. 다시 한번 강조하자면, 세마포는 운영체제에서 제공하는 도구입니다.

class Semaphore{
private:
    int n;

public:
    Semaphore(int n){
        this->n = n;
    }

    //
    // 실제 운영체제의 세마포는 원자적으로 실행되도록 구현되어 있음.
    void wait(){
        while(this->n <= 0) {
            //
            // 모든 공유 자원을 빌려준 상태이므로 대기.
        }
        this->n--;
    }

    //
    // 실제 운영체제의 세마포는 원자적으로 실행되도록 구현되어 있음.
    void signal(){
        this->n++;
    }
};

대부분의 운영체제는 세마포와 이진 세마포를 구분하여 부릅니다. 일반적인 세마포의 카운트 값은 제한 없는 도메인을 갖는데 반해, 이진 세마포의 카운트는 0 또는 1만 가질 수 있습니다. 이진 세마포는 상호 배제(mutual exclusion)를 효과적으로 제공하므로 뮤텍스(MutEx)라는 이름으로 불립니다.

Semaphore s(1); // = Mutex
void increase(int n)
{
    //
    // 진입 영역
    s.wait();

    //
    // 임계 영역.
    {
        int _value = value;
        printf("[%d] %4d \n", n, _value);
        value = _value + 1;
    }

    //
    // 퇴출 영역.
    s.signal();
}

---

조건변수 계열의 해결안

스핀락의 특징

지금까지 설명했던 해결안은 조건이 만족될 때 까지 while을 반복하는 스핀락을 통해 임계영역을 구현한 것입니다. 구현이 매우 간단하다는 장점이 있지만 조건이 만족되기 전까지는 반복문을 벗어나지 못한다는 것을 유의해야 합니다.

위의 이유로 인해, 기껏 CPU 사용기회를 얻었음에도 반복문을 빠져나가지도 못하며, 매번 반복문의 조건문을 계산하느라 이상한 곳에다 CPU를 할애합니다. 이와 같은 스핀락의 특징을 바쁜 대기(Busy Waiting)라고 부릅니다.

반면에 조건변수 계열의 해결안은 스케쥴링 큐 수준에서 동작하며, 공유자원을 요청할 때 대기상태로 변화하고, 공유자원이 준비되고 나서야 대기상태에서 벗어납니다. 대기상태인 작업은 스케쥴러에 의해 선택되지 않기 때문에 효율적인 대기가 가능해집니다.

그러나 항상 조건변수가 좋은 것이 아니라는 것을 알아둬야 합니다. 조건변수는 반드시 문맥교환이 한 번은 발생하기 때문입니다. 스핀락이 충분히 짧다면 문맥교환을 수반하는 조건변수보다 좋은 선택일 수 있습니다.

---

조건변수를 이용한 해결안

작업이 진행되기 위해 필요한 조건을 정의한 변수를 조건변수라고 부르며, 다음과 같은 3가지 연산을 가지고 있습니다.

• wait() : 자신을 대기상태로 변화시킨다.
• nofity_one() : 해당 조건변수에 연관된 대기상태 중인 작업을 하나 깨운다.
• nofity_all() : 해단 조건변수에 연관된 대기상태 중인 작업을 모두 깨운다.

조건변수들은 자신과 관련된 대기중인 작업을 파악하기 위해 wait() 호출 시에 작업정보를 저장하며, 기아상태를 막기위해 큐 자료구조를 사용하여 저장합니다.

이제 공유자원에 대응되는 조건변수를 생성하면, 다음과 같이 공유자원 문제를 해결할 수 있습니다.

1. 작업들은 wait()를 통해 공유자원을 요청한다.
2. 메인 또는 공유자원의 사용을 끝마친 작업이 notify_one()을 실행한다.
3. 다음 공유자원을 획득한 작업이 깨워지고 2로 되돌아간다.

conditional_variable cv1, cv2;

int value;
void increase(){
    //
    // 진입 영역
    // 진입 허가가 내려질 때 까지 대기한다.
    cv1.wait();

    //
    // 임계 영역
    {
        int _value = value;
        printf("%d", _value);
        value = _value + 1;

        //
        // 이것이 마지막 쓰레드라면 메인 쓰레드를 깨운다.
        if(value == 100) {
            cv2.nofity_one();
        }
    }

    //
    // 퇴출 영역
    // 대기중인 작업 하나를 wait()에서 깨운다.
    cv1.notify_one();
}

int main(){
    // ... 100개의 쓰레드를 생성하고.

    //
    // 처음에는 모두가 wait()하고 있으므로,
    // 메인문에서 하나를 깨운다.
    cv1.nofity_one();

    //
    // 모든 쓰레드가 완료될 때 까지 기다린다.
    cv2.wait();

    cout << value;
}

---

모니터를 이용한 해결안

하드웨어 수준에서 제공하는 원자함수보단 낫지만, 운영체제 수준에서 제공하는 세마포도 사용하기 까다로운 것은 매한가지입니다. 때문에 언어 개발자들은 세마포보다 더 사용하기 쉬운 고수준 객체인 모니터를 개발하기에 이르렀습니다.

모니터는 뮤텍스(이진 세마포) + 조건변수로 생각하면 편하며, 다음과 같이 최대 하나의 작업만 모니터에 접근하는 것을 허용합니다.

1. 최대 하나의 작업만이 모니터에 진입할 수 있으며,
2. 선행 작업이 존재한다면 후행 작업은 대기상태로 변화하고,
3. 선행 작업이 signal()을 호출하면 대기큐에서 하나를 꺼내 활성화합니다.

Monitor m;

int value;
void increase(){
    //
    // 진입 영역
    // 모니터 내부로 접근을 시도한다.
    m.wait();

    //
    // 임계 영역
    {
        int _value = value;
        printf("%d", _value);
        value = _value + 1;
    }

    //
    // 퇴출 영역
    // 모니터를 떠난다.
    m.signal();
}

세마포와 모니터는 동기화 도구라는 점에서 같지만, 세세한 곳에서는 다릅니다.

세마포는 운영체제 레벨에서 제공하는 동기화 도구이며, 운영체제에서 공통으로 사용하는 공유자원의 잔여량 파악과 접근 제어를 위해 만들어졌습니다. 필요하다면 프로그래머가 시스템 호출을 날려서 새로운 세마포를 운영체제에 생성할 수 있습니다.

모니터는 프로그래밍 언어 레벨에서 제공하는 동기화 도구이며, 최대 하나의 작업만 활성화할 수 있도록 도와줍니다. 내부적으로는 이진 세마포 + 조건변수로 구성되어 있으며, 응용 프로그래머가 쉽게 사용할 수 있도록 언어 개발자가 설계한 고수준 객체입니다.

정리하자면 세마포는 사용할 수 있는 리소스의 개수를 파악하려고 만든 운영체제 레벨의 저수준 객체, 모니터는 어플리케이션에서 작업을 직렬화하기 위해 만든 어플리케이션 레벨의 고수준 객체입니다.