[운영체제] 뮤텍스, 세마포어, 튜링 동치

경쟁 상태(Race Condition)

둘 이상의 프로세스가 읽거나 쓸 때 타이밍이나 순서에 따라 결과 값이 달라질 수 있는 상태

임계 구역(Critical Section)

여러 프로세스가 공유하는 자원에 대해 한번에 둘 이상의 프로세스가 접근해서는 안되는 영역. 한번에 여러 스레드가 접근하여 값을 변경하면 데이터의 일관성이 깨지는 race condition이 발생할 수 있다.

1.  상호 배제(mutual exclusion): 특정 프로세스가 크리티컬 섹션에서 실행되면 다른 프로세스는 크리티컬 섹션에서 실행 불가
2. 진행(progress): 자기 크리티컬 섹션에서 실행되는 프로세스 없고 해당 크리티컬 섹션에 진입하려고 하는 다른 프로세스들 있으면 나머지 구역에서 실행중이지 않은 프로세스들만 다음 누가 그 임계구역에 진입할 수 있는지 결정하는데 참여할 수 있으며, 이 선택은 한정된 시간 내에 수행된다. -> 임계구역 비어 있으면 적절하게 순서 선택해서 진입.
3. 한정된 대기(bounded waiting): 프로세스가 자기의 크리티컬 섹션에 진입하려는 요쳥 후 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있다.

뮤텍스(Mutex, Mutual Exclusion)

• 두 처리 단위가 동시에 임계구역에 진입하지 못하게 하는 방법
• 좁은 의미로는, 임계구역 제어를 위해 사용하는 lock 객체. 한번에 하나의 스레드만 진입할 수 있도록 함

Acquire: 락 획득
Release: 락 제거

Acquire( ) {
	While (!available) busy wait; // 대기
	available = false;
}

Release( ) {
	Available = true;
}

int getchar()
{
    int pos;
    char ret;
    
    lock(keymutex); /* entry section */
    /* critical section begin */
    pos = head;
    ret = queue[pos];
    pos = (pos + 1) % 32;
    head = pos;
    /* critical section end */
    unlock(keymutex); /* exit section */
    return ret; /* remainder section */
}

세마포어(semaphore)

• 공유 자원이 여러개인 경우 공유 자원에 대한 접근을 제한하는 방법
• 두개의 원자적 함수로 조작되는 정수 변수
• S: 세마포어 정수 값
• P: 임계구역 진입에 사용하는 원자적 함수
• V: 임계구역 탈줄에 사용하는 원자적 함수

 P(S) {
     S--;
     if S < 0
         // 이 프로세스를 재움 큐에 추가 (잠 듦)
 }

 V(S) {
     S++;
     if S <= 0
         // 재움 큐로부터 프로세스를 제거 (깨어남)
 }

튜링 동치

컴퓨터 P와 Q가 있을 때, P가 할 수 있는 일을 Q로 표현 가능(simulate)하고, Q가 할 수 있는 일을 P로 표현 가능하다면 P와 Q는 튜링 동치다.

뮤텍스, 세마포어와 튜링 동치

뮤텍스 - 세마포어는 튜링 동치다.

1. 세마포어 => 뮤텍스 구현: 세마포어의 count 값을 1로 두면 mutex의 동작을 표현할 수 있다.
2. 뮤텍스 => 세마포어 구현: wait / signal의 원자성을 구현할 때 mutex를 이용

class Semaphore {
private:
    int count;                 // 세마포어 카운터
    std::mutex mtx;            // 뮤텍스
    std::condition_variable cv; // 조건 변수

public:
    Semaphore(int initial_count) : count(initial_count) {}

    // 획득 (P 연산)
    void wait() {
        std::unique_lock<std::mutex> lock(mtx);
        while (count == 0) {
            cv.wait(lock); // 카운터가 0일 때 대기
        }
        count--; // 카운터 감소
    }

    // 해제 (V 연산)
    void signal() {
        std::unique_lock<std::mutex> lock(mtx);
        count++; // 카운터 증가
        cv.notify_one(); // 대기 중인 스레드 중 하나를 깨웁니다.
    }
};

획득 / 해제 연산에 진입할 때 mutex lock을 걸면 스레드의 수가 많더라도 원자적으로 처리할 수 있다. 따라서 mutex를 통해 Semaphore의 동작을 표현할 수 있다.

---

mutex를 semaphore로 구현할 수 있다는 것은 생각했지만, semaphore을 mutex로 구현 가능한지는 고민해본 적이 없던 것 같다. 연산에 mutex 락을 거는 등의 방식을 통해 semaphore을 묘사할 수 있다는 것을 잘 기억해둬야 겠다.