[운영체제] Critical-Section Problem

Background

• 프로세스는 동시에 실행 가능합니다. Shared data에 대한 Concurrent access는 데이터 일관성 문제가 발생하게 됩니다. 이를 위해 협력적 프로세스들 간의 실행 순서를 정해야 합니다.

Race Condition

이렇게 fork() 하는 코드를 생각해보면, fork() 실행 중 interrupt 가 발생하여 두 프로세스를 번갈아가며 실행하다보면, 같은 pid 값을 가진 두 자식 프로세스가 나타갈 수 있습니다. 이렇게 동시에 여러 개의 프로세스가 동일한 데이터에 접근하여 변경하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 Race Condition 이라고 합니다.

경쟁 상태를 회피하기 위해서 한 순간에 하나의 프로세스만이 공유 변수를 조작하도록 보장해야 하고 이를 위해 프로세스들이 동기화되어야 합니다.

Critical Section(CS) Problem

각 프로세스는 code 영역에 4가지 영역이 존재합니다.

• Entry section : 공유 자원 점유 전 대기 영역
• Critical section : 공유 자원에 접근하여 작업을 수행하는 코드
• Exit section : 공유 자원 점유 해제를 수행하는 코드
• Remainder section : 이외 나머지 작업 코드

Critical section 에는 오직 하나의 프로세스만 들어갈 수 있습니다. 코드로 나타내면

while (true) {
    // entry section
    // critical section
    // exit section
    // remainder section 
}

이런 구조입니다. 그러면 왜 Critical section이 문제일까요 ?! 3가지 측면에서 살펴봐야 합니다.

1. Mutual Exclusion : 오직 하나의 프로세스만 Critical section에 존재하는지
2. Progress : 오직 Entry section 에 있는 프로세스들만으로 결정되는지 (즉, Remainder section에 있는 프로세스가 다음 Critical section을 점유할 프로세스 선택에 영향을 주어서는 안됨)
3. Bounded Waiting : 무한 대기 불가능

Interrupt-based Solution

인터럽트를 줘서 관리한다면?! 즉, Critical section에 들어갈 때 인터럽트를 끄고, 나오면 킨다면 ?? 문제가 많습니다.

• Critical section이 1시간 동안 실행된다면?
• 아니면 영원히 Critical section을 점유하면?
• CPU가 2개 이상이라면? (나머지 CPU는 다 꺼버리는 문제)

이를 위해 여러 솔루션들이 있습니다.