🧐 Race Condition이란?

Race Hazard라고도 불리는 Race Condition는 시스템의 실질적인 동작이 제어할 수 없는 다른 이벤트의 순서 또는 타이밍에 따라 달라져 예상치 못한 또는 일관되지 않은 결과를 초래하는 시스템의 상태를 말한다.

여러 프로세스 또는 스레드가 서로 메시지를 전송하거나 공유하는 자원(Ex) 변수, 메모리 등등)에 동시에 접근하거나 변경하려고 할 때 발생할 수 있는 문제가 Race Condition의 일종인 Data Race이다.

이를 방지하기 위해서 공유 자원이 시스템 또는 프로세스의 일부인지 코드를 검토하고, 코드의 중요한 부분에 Lock을 걸어 원자성 작업을 적용하고, 한 번 생성하면 변경할 수 없는 불변 개체를 사용하거나 공유 자원에 하나의 프로세스 또는 스레드만 접근할 수 있도록 동기화를 해야 한다. 이러한 동기화를 도와주는 대표적인 방식에는 우리가 많이 알고 있는 뮤텍스(Mutex), 세마포어(Semaphore) 등이 있다.

❗️ 동시 메모리 접근으로 인한 문제만이 Race Condition은 아니다.

Data Race의 정확한 정의는 동시성 모델마다 다르지만 일반적으로 한 스레드의 메모리 작업이 다른 스레드의 메모리 작업이 해당 메모리 위치에 쓰는 것과 동시에 메모리 위치에 액세스하려고 시도할 가능성이 있는 상황을 의미한다. 이는 모든 메모리 액세스가 원자 연산만 사용하는, 즉 Data Race이 없는 프로그램에서도 타이밍으로 인해 결과를 예상하지 못하는 상황이 발생할 수 있다는 것이다.

Race Condition은 조금 더 추상적인 의미를 가지고 있다.

프로그램의 결과가 동시에 실행 중인 여러 프로세스 또는 스레드의 순서나 타이밍 의존할 때 발생하며 실행마다 다른 결과가 나올 수 있는 논리적 버그를 의미한다.

bool ready = false;

void waitForReady() {
    while (!ready) {
        // 기다리는 중...
    }
    std::cout << "Ready!" << std::endl;
}

void setReady() {
    ready = true;
}

int main() {
    std::thread t1(waitForReady);
    std::thread t2(setReady);
    t1.join();
    t2.join();
}

이 예시에서 t1과 t2스레드 중 어느 스레드가 먼저 실행될지 모른다.

만약 t1 스레드가 먼저 실행된다면 ready가 설정되기 전이므로 무한루프에 빠질 수 있다. 따라서 이 코드의 결과는 Ready!가 출력되거나 무한루프를 계속 돌다가 프로그램이 종료될 것이다. 따라서 순서를 제어하거나 동기화 도구를 사용하는 등으로 해결해야 한다.

---

Data Race는 여러 프로세스 또는 스레드가 동일한 메모리 위치에 동시에 접근할 때 적어도 하나의 접근이 쓰기 작업이고, 작업들 간의 순서가 정의되지 않았을 때(즉, happens-before 관계가 없을 때) 발생한다.

int counter = 0;

void increment() {
    counter++;
}

int main() {
    std::thread t1(increment);
    std::thread t2(increment);
    t1.join();
    t2.join();
    std::cout << counter << std::endl;
}

t1 스레드와 t2스레드가 동시에 counter 변수에 접근하면 둘 중 하나의 작업이 덮어쓰여 데이터의 일관성이 깨지므로 실행할 때마다 결과가 다르게 출력될 것이다.

읽기와 쓰기가 충돌하여 발생하는 문제므로 뮤텍스나 세마포어 등 동기화 도구를 사용하여 해결할 수 있다.

🪄 Race Condition이 발생하는 상황

여러 프로세스 또는 스레드가 공유 자원에 동시 접근할 때

프로세스A와 프로세스B가 동시에 같은 파일, 전역 변수, 힙 메모리 등에 접근하여 파일 내용을 수정하거나, 변수 값을 읽고 수정한다면 순서에 따라 파일 내용이 달라지거나 변수 값이 의도와는 다르게 덮어씌워질 수 있다.

이를 해결하기 위해 공유 데이터에 접근할 때마다 그 데이터에 대해서 Lock을 걸고 사용이 완료되면 Lock을 해제하는 식의 방법 등을 사용할 수 있다.

[커널 모드]에서 스케줄링에 의한 문맥 교환 or 인터럽트가 발생

프로세스 A가 커널 모드에서 공유 자원의 데이터를 조작하는 중 정해진 작업 시간이 초과되어 OS의 스케줄러에 의해 CPU 제어권이 프로세스 B로 넘어가 A와 같은 데이터를 조작하게 된다면 A의 작업 내용이 반영되지 않을 수 있다.

또는 프로세스 A가 공유 자원의 데이터를 조작하는 중 인터럽트가 발생하여 프로세스 B로 전환되고 프로세스 B가 A와 같은 데이터를 변경한 뒤 다시 프로세스 A로 전환된다면 일관성이 깨질 수 있다.

이를 방지하기 위해서는 프로세스가 커널 모드에서 작업을 하는 경우에 시간 제한을 두지 않거나 인터럽트를 잠시 비활성화하여 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 해야 한다.

이 외에도 가상 메모리에서 페이지 교체를 수행할 때 교체 대상 페이지를 결정하고 제거하기 전에 다른 프로세스가 동일한 페이지를 참조하여 불일치가 발생하거나 동일한 시스템 콜을 여러 프로세스가 동시에 호출하는 등 여러 프로세스가 동시에 I/O 장치를 사용하려할 때도 Race Condition이 발생할 수 있다.

🧐 Critical Section이란?

위에서 살펴봤듯이 여러 스레드나 프로세스가 공유 자원에 동시 접근하면 Race Condition이 발생할 수 있으므로 이를 방지하려면 공유 자원에 접근하는 프로그램의 일부를 보호하여 동시 접근이 발생하지 않도록 해야 한다. 이처럼 보호된 코드 영역을 Critical Section(임계 구역)이라고 한다. 이 Critical Section에는 한 번에 하나의 프로세스 또는 스레드만 접근할 수 있으며, 다른 프로세스나 스레드는 Critical Section에 들어간 스레드가 나올 때까지 대기해야 한다. 따라서 Critical Section을 너무 길게 유지하면 성능이 저하될 수 있으므로, 정말 중요한 부분에만 적절히 적용하는 것이 중요하다.

⚡️ Critical Section의 동기화를 위한 3가지 조건

1. Mutual Exclusion(상호 배제)

• 한 프로세스가 Critical Section에 들어가면 다른 프로세스는 Critical Section에 들어갈 수 없고 대기해야 한다.

2. Bounded Waiting(유한 대기)

• Critical Section에 들어가기 위해 기다리는 프로세스가 무한으로 대기하지 않아야 한다.

3. Progress(진행의 융통성)

• Critical Section가 비어있다면, 어떤 프로세스라도 들어가서 자원을 활용할 수 있다. 즉, 공유 자원을 번갈아 쓴다고 할 때 한 프로세스가 자신의 차례가 아니라고 해서 비어있는 Critical Section에 들어가지 않고 기다리는 것은 효율적이지 못하다는 것이다.

Critical Section 문제를 해결하려면 위의 3가지를 모두 만족해야 하는데, 그 이유는 아래의 동기화 예시를 통해 알아보자.

1️⃣ Mutual Exclusion (상호 배제)를 만족하지 않는 경우

여기서 포인트는 lock이다. 한 프로세스가 Critical Section에 들어간다면 lock을 걸어(lock을 true로 변경하여) 다른 프로세스가 들어오지 못하도록 하는 것이다. 다른 프로세스는 lock이 걸어져 있으므로 무한루프를 돌면서 기다리게 될 것이다. Critical Section에 들어간 프로세스가 작업을 모두 마치고 나오면 lock을 해제하여 다른 프로세스가 Critical Section을 사용할 수 있게 한다. 하지만 이 예시는 Mutual Exclusion(상호 배제)를 만족하지 않는다.

프로세스 A가 while(lock == true); 문을 실행하면 현재 Critical Section에 프로세스가 들어가지 않았기 때문에 그대로 통과한다. 이어서 다음 코드인 lock = true; 를 실행하려는 순간 정해진 작업 시간이 초과되어 프로세스 A에게 주어진 CPU 제어권이 프로세스 B에게 넘어간다면? 아직 공유 변수 lock은 false인 상태이다.

공유 변수 lock은 false인 상태이므로 프로세스 B가 while(lock == true); 문을 실행하면 아무도 lock을 걸지 않은 상태라고 간주하게 되므로 통과하게 된다. 그렇게 프로세스 B는 문제없이 Critical Section에 진입할 수 있게 된다. 이 상태에서 Context Switching이 발생하고 프로세스 A에게로 제어권이 넘어가게 되면 프로세스 A도 Critical Section에 진입하게 된다. 즉, 두 프로세스가 Critical Section에 진입하게 되고 이는 Mutual Exclusion(상호 배제)에 위배된다.

또한, lock이 해제되기 전까지 다른 프로세스가 계속해서 무한루프를 돌면서 lock의 상태를 확인해야 하므로 lock이 해제되기 전까지 busy waiting이 발생하여 시스템 자원을 낭비한다는 문제점이 있다.

2️⃣ Bounded Waiting(유한 대기)를 만족하지 않는 경우

위의 문제를 해결하기 위해서 lock을 먼저 건다면 어떨까? lock의 상태를 확인한 다음에 lock을 걸었기 때문에 Mutual Exclusion(상호 배제)가 위배된 것이므로 순서를 바꾼다면 해결될 것이다.

lock을 먼저 걸기 위해선 각 프로세스 마다의 lock이 필요하다. 하나의 lock만 존재한다면 while문을 절대 통과할 수 없으므로 동기화가 성립될 수 없다. (이는 확장성이 떨어진다는 문제가 있다. 프로세스가 증가한다면 그만큼 lock의 개수도 증가해야 한다.)

이렇게 프로세스 A와 B 각각의 lock을 사용하면 다른 프로세스가 잠금을 설정했는지 확인 후에 Critical Section에 진입하게 되므로 반드시 하나의 프로세스만 Critical Section에 존재하게 된다. 즉, Mutual Exclusion(상호 배제)를 만족한다. 하지만, 이 예시는 Bounded Waiting(유한 대기)를 만족하지 못한다.

프로세스 A가 lock1 = true; 를 실행하여 공유 변수 lock1이 true로 변경된다. 그리고 CPU 제어권이 프로세스 B로 넘어간다. 프로세스 B 또한 lock2 = true; 를 실행하여 공유 변수 lock2가 true로 변경된다. 이때, 공유변수 lock1 과 lock2 는 모두 true가 된다.

다시 CPU 제어권이 프로세스 A에게 넘어가 프로세스 A가 while(lock2 == true); 문을 실행한다. lock2가 true이므로 무한 루프를 돌면서 lock2가 false가 될 때까지 기다리게 된다. 그 다음으로 프로세스 B 또한 while(lock1 == true); 문을 실행하여 무한루프에 빠지게 된다.

이렇게 프로세스 A, B 모두 Critical Section에 진입하지 못하여 Bounded Waiting(유한 대기)을 만족하지 못하고, DeadLock(교착 상태)에 빠지게 되었다.

3️⃣ Progress(진행의 융통성)를 만족하지 않는 경우

이 예시는 Mutual Exclusion(상호 배제)와 Bounded Waiting(유한 대기)를 모두 만족한다.

하나의 공유 변수 lock만을 사용하여 다른 프로세스가 Critical Section을 사용 중인지 확인하고 아니라면 진입한다. 프로세스 A와 B 각각 다른 프로세스가 lock을 걸었다면 해당 프로세스가 사용을 끝내고 lock을 해제할 때까지 진입할 수 없다.

하지만, 이는 2가지 문제점이 있다. 한 프로세스가 연속으로 Critical Section에 진입할 수 없다. lock을 해제하는 코드가 다른 프로세스에 의해서만 실행되므로 반드시 번갈아가면서 Critical Section에 진입해야한다는 것이다. 즉, 프로세스 B는 프로세스 A가 Critical Section에 진입한 후 lock = 2; 를 실행해줘야만 무한루프를 탈출하여 Critical Section에 진입할 수 있다. 이러한 현상을 경직된 동기화(lockstep synchronization) 라고 하며, 이는 Progress(진행의 융통성)를 만족하지 못한다.

또한, 지금은 프로세스가 2개이지만 프로세스가 더 늘어나게 된다면 실행 순서에 따라 느리게 실행되거나 심할 경우 DeadLock(교착 상태)에 빠질 수 있다. 프로세스가 총 4개로 늘어났다고 해보자. lock을 해제하는 코드는 그 다음 프로세스의 순서를 정해주는 코드와 마찬가지이므로 위의 경우를 따라간다면 임계구역에 진입할 수 있는 프로세스의 순서는 A → B → C → D → A가 될 것이다. 하지만 Context Switching이 D → C → B → A → D 로 실행된다면 D는 C가 먼저 실행되지 않았으므로 무한루프를 돌다 C로 넘어갈 것이고, C는 마찬가지로 B가 먼저 실행되지 않았으므로 무한루프를 돌다 B로 순서가 넘어갈 것이다. 매우 극단적인 예시지만 충분히 발생할 수 있는 상황이고, 교착상태가 아니더라도 매우 비효율적이고 느리게 실행될 가능성이 높다.

위의 문제 상황들을 통해 Critical Section의 동기화를 위해서 Mutual Exclusion(상호 배제), Bounded Waiting(유한 대기), Progress(진행의 융통성)을 만족해야 하는 이유를 알 수 있었다. 다음 포스팅에서는 이러한 문제들을 모두 해결하는 방식들에 대해 알아보고자 한다.

참고 문서

Race condition

What is a Race Condition?

Critical section

OS는 할껀데 핵심만 합니다. 8편 Critical section (임계 구역)

[OS] 4. 프로세스 동기화 (Process Synchronization)

[운영체제] 경쟁 조건(Race Condition)과 임계 구역(Critical Section)