동기화

Race Condition

여러 프로세스가 동일한 데이터에 접근할 때 접근 순서에 따라 결과가 달라지는 상황을 의미한다. 

Critical Section 문제

코드 영역 중 다른 프로세스와 공유하는 데이터에 접근하는 영역을 크리티컬 섹션이라고 한다. 각 프로세스는 자신의 크리티컬 섹션에 진입하기 위해 엔트리 섹션에서 허가를 받아야 한다. 

엔트리 섹션 → 크리티컬 섹션 → 엑시트 섹션 → 리메인더 섹션으로 코드 영역이 구분된다.

Critical Section 해결책

다음 세 가지 필요 조건이 만족되어야 한다.

• 1. 상호 배제(Mutual Exclusion): 한 프로세스가 크리티컬 섹션을 실행하고 있으면 다른 코드는 크리티컬 섹션을 실행할 수 없다.
• 2. 진행(Progress): 모든 프로세스가 크리티컬 섹션을 실행하고 있지 않고, 어떤 프로세스가 크리티컬 섹션을 실행하고자 한다면 리메인더 섹션을 실행하고 있지 않은 프로세스(크리티컬 섹션에 직접적 연관이 있는 프로세스)만이 다음 크리티컬 섹션을 실행할 프로세스를 결정하는 데 관여할 수 있으며 이 결정이 미뤄져서는 안 된다. 
• 3. 한계 대기(Bounded Waiting): 크리티컬 섹션에 진입 요청을 한 프로세스가 진입 전까지 다른 프로세스가 크리티컬 섹션의 실행을 허가받는 횟수에 제한이 있어야 한다.

하드웨어 기반 솔루션

Peterson’s solution

크리티컬 섹션 문제를 flag와 turn 변수를 관리하여 해결하지만, 코드가 순서대로 실행될 때만 적용 가능하기에 현대 컴퓨터에는 잘 적용되지 않는다. memory barrier를 통해 한 프로세서의 변수의 로드/저장 순서를 강제할 수 있다.

Atomic instruction

- atomic instruction은 실행 중간에 CPU를 빼앗기지 않는다.
- test_and_set() / compare_and_swap() 연산을 통해 상호 배제를 구현한 예시가 있다. 하지만 bounded waiting 조건이 만족되지 않기 때문에, 완전한 critical section의 해결책은 아니다.

소프트웨어 기반 솔루션

하드웨어 기반 해결책은 애플리케이션 프로그래머에게 너무 복잡하고 접근하기도 어렵다.

Mutex Lock

- acquire(), release()의 아토믹 연산을 통해 해결
- acquire를 호출하면 while문을 통해 lock 변수를 계속 검사하는 spin lock 문제가 있음
- spin lock은 컨텍스트 스위치가 일어나지 않는다는 점에서 현대 멀티 코어 환경에서는 나쁘지 않다.
- 단, CPU 자원이 쓸모 없는 곳에 낭비된다는 점은 단점이다.

Semaphore

- wait(), signal()을 통해 해결
- 정수 \(S\)와 대기 중인 쓰레드 리스트로 구성된다.
- wait: \(S\)를 1 감소시키고, 음수일 경우 해당 쓰레드를 리스트에 넣고 sleep 시스템 콜을 호출한다. (엔트리 섹션)
- signal: \(S\)의 값을 1 증가시킨다. 리스트에 쓰레드가 있으면 아무 쓰레드나 깨운다. (엑시트 섹션)
- \(S\)의 초기값이 동시에 자신의 critical section에 진입할 수 있는 쓰레드의 수가 된다.
- \(S\)는 atomically 업데이트 되어야 하며, 이는 또다른 크리티컬 섹션 문제가 된다.

Mutex lock이나 semaphore는 유용하지만, wait/signal 순서를 반대로 쓰거나 wait를 중복 사용하는 등 프로그래밍 실수가 발생할 수 있다. 이를 해결하기 위해 Monitor가 고안되었다.

Monitor

모니터 타입은 공유 데이터를 관리하는 데이터 클래스이다.

모니터의 장점

크리티컬 섹션의 범위를 설정하고, 앞뒤로 wait/signal을 배치하며 세마포어 변수명을 일일이 관리하는 비효율적인 작업을 생략할 수 있다.
단점은 이해하기가 어렵다는 것이다...

• 모니터는 공유 데이터, 조건(Condition), 함수로 이루어진다.
• 공유 데이터는 내부 함수를 통해서만 접근되며, 조건은 프로세스의 동기화를 위해 사용된다.
• 모니터와 관련된 코드를 실행하는 프로세스는 최대 하나이다. (상호 배제)

모니터의 구현 (C++)

struct BinarySemaphore {
    // spin lock 버전
    int x;
    void wait() {
        while (x == 0); // 누군가 사용중이다. busy waiting.
        x--; // 0으로 만들어서 사용하지 못하게 한다.
    }
    void signal() {
        x++; // 1로 증가시켜서 누군가 사용할 수 있게 한다.
    }
};

struct Condition {
    int x_count; // 이 조건을 통한 시그널을 기다리는 프로세스의 개수
    BinarySemaphore x_sem; // 동기화를 위한 세마포어

    void wait(Monitor *monitor) {
        /* 조건이 만족될 때까지 기다린다. */
        x_count++; // 시그널을 기다리는 프로세스에 현재 프로세스를 추가.
        /* 멈추기 전에 다른 프로세스가 모니터 내부 함수를 실행할 수 있도록 깨운다. */
        monitor->exitSection();
        x_sem.wait(); // 시그널을 기다리며 멈춘다.
        x_count--; // 시그널이 도착했으므로 조건 대기 프로세스에서 현재 프로세스를 제거한다.
    }
    
    int signal(Monitor *monitor) {
        /* 이 조건을 기다리는 다른 프로세스를 깨우고 멈춘다. */
        monitor->next_count++; // 멈출 예정이므로 멈춘 프로세스 개수를 증가시킨다.
        x_sem.signal(); // 이 조건을 기다리는 다른 프로세스를 깨운다.
        monitor->next.wait(); // 멈춘 상태로 기다린다.
        monitor->next_count--; // 누군가 모니터를 나가면서 깨웠으므로 현재 프로세스를 재실행한다.
    }
};

struct Monitor {
    BinarySemaphore mutex; // 상호 배제 mutex lock.
    BinarySemaphore next; // 모니터 내부 함수를 실행 도중 wait(x)로 중간에 멈춘 프로세스를 관리하는 세마포어
    int next_count; // 모니터 내부 함수 실행 중 멈춘 프로세스의 개수
    int shared_data; // 프로세스간 공유된 데이터
    Condition cond; // 조건

    void entrySection() {
        mutex.wait(); // 모니터에 접근하기 위해 기다린다.
    }
    void exitSection() {
        // 모니터에서 나갈 때 다른 프로세스의 접근을 허가한다.
        if (next_count > 0) next.signal(); // 멈춰 있는 프로세스를 우선하여 실행한다.
        else mutex.signal(); // 다른 프로세스의 모니터 접근을 허가한다. 
    }

    void F() {
       entrySection(); // 공유 데이터 접근을 위해 mutex 락을 획득한다.

       cond.wait(this); // 이 조건과 관련된 다른 프로세스가 신호를 줄 때까지 대기한다.
       shared_data += 1; // 작업을 수행한다.
       cond.signal(this); // 관련 작업을 마쳤으므로 조건과 관려된 다른 프로세스를 실행할 수 있게 한다.
       std::cout << shared_data; // 다른 프로세스가 F2를 실행했다면 2가 곱해진 값이 출력된다.

       exitSection(); // 공유 데이터 접근이 끝났다. mutex lock을 푼다.
    }

    void F2() {
        entrySection();
        cond.wait(this);
        shared_data = 2*shared_data;
        cond.signal(this);
        exitSection();
    }
};