Critical Section

Critical Section(임계 구역)은 여러 프로세스나 스레드가 공유 자원(Shared Resource)에 접근하는 코드 영역을 의미한다.

예를 들어 전역 변수, 파일, 메모리 버퍼와 같은 데이터를 여러 스레드가 동시에 수정하려고 하면 Race Condition이 발생할 수 있다.

따라서 운영체제는 공유 자원에 접근하는 특정 구간을 Critical Section으로 지정하고, 한 번에 하나의 스레드만 접근할 수 있도록 동기화를 수행한다.

count++; // Critical Section

위 코드 역시 단순히 한 줄로 보이지만 실제로는 여러 개의 기계어 명령어로 수행되므로, 실행 도중 다른 스레드가 개입하면 예상하지 못한 결과가 발생할 수 있다.

Critical Section Problem

임계 구역 문제(Critical Section Problem)는 여러 프로세스 또는 스레드가 공유 자원을 안전하게 사용할 수 있도록 하는 방법을 찾는 문제이다.

운영체제에서 임계 구역 문제의 해결책은 다음 세 가지 조건을 반드시 만족해야 한다.

1. Mutual Exclusion (상호 배제)

어떤 프로세스가 자신의 임계 구역을 실행 중이라면 다른 프로세스는 해당 임계 구역에 진입할 수 없어야 한다.

즉, 한 순간에는 최대 하나의 프로세스만 공유 자원에 접근할 수 있어야 한다.

P1 : Critical Section 실행 중
P2 : 대기
P3 : 대기

만약 두 개 이상의 프로세스가 동시에 임계 구역에 진입한다면 Race Condition이 발생할 수 있다.

2. Progress (진행)

현재 어떤 프로세스도 임계 구역을 사용하지 않고 있고, 임계 구역에 진입하려는 프로세스가 존재한다면 다음에 진입할 프로세스를 무한정 미룰 수 없어야 한다.

예를 들어

P1 : Rest
P2 : Critical Section 진입 요청
P3 : Rest

상태라면 운영체제는 적절한 시점에 P2를 임계 구역으로 진입시켜야 한다.

즉, 아무도 사용하지 않는 자원을 비워두면서 계속 기다리게 해서는 안 된다.

3. Bounded Waiting (한정 대기)

프로세스가 임계 구역 진입을 요청한 후에는 다른 프로세스들이 무한정 먼저 들어가는 상황이 발생해서는 안 된다.

즉, 프로세스는 언젠가는 반드시 임계 구역에 진입할 수 있어야 한다.

P1 : 진입 요청
P2 : 진입
P3 : 진입
P2 : 진입
P3 : 진입
...

위와 같이 P1이 계속 밀려나는 현상이 발생하면 기아 상태(Starvation)가 발생한다.

Bounded Waiting은 이러한 기아 상태를 방지하기 위한 조건이다.

세 가지 조건 정리

조건	의미
Mutual Exclusion	한 번에 하나의 프로세스만 임계 구역 진입 가능
Progress	비어 있는 임계 구역은 적절한 프로세스가 진입해야 함
Bounded Waiting	특정 프로세스가 무한정 기다리면 안 됨

운영체제에서 사용하는 Mutex, Semaphore, Monitor 등의 동기화 기법은 이러한 조건들을 만족시키기 위해 사용된다.

가. Peterson's Algorithm

Peterson's Algorithm은 두 개의 프로세스가 공유 자원에 접근할 때 소프트웨어적으로 상호 배제를 보장하는 알고리즘이다.

두 개의 변수만 사용한다.

bool flag[2];
int turn;

flag[i] : 프로세스 i가 진입을 원하는지 여부
turn : 누가 먼저 양보할지 결정

flag[i] = true;
turn = j;

while(flag[j] && turn == j);

상대방도 진입을 원하고, 상대방 차례라면 대기한다.

장점

Mutual Exclusion 만족
Progress 만족
Bounded Waiting 만족

단점

프로세스 2개만 가능
현대 CPU의 메모리 재정렬 문제로 실제 환경에서는 사용하기 어려움

나. Interrupt Disable

단일 CPU 환경에서는 인터럽트를 비활성화하여 문맥 교환(Context Switch)을 막을 수 있다.

disable_interrupt();

critical_section();

enable_interrupt();

장점

구현이 매우 단순하다.

단점

멀티코어에서는 동작하지 않음
커널만 수행 가능
인터럽트를 오래 막으면 시스템 응답성이 떨어짐

다. Special Machine Instructions

CPU는 원자적 연산(Atomic Operation)을 제공한다.

대표적으로

Test-And-Set
Compare-And-Swap
Swap

등이 있다.

이러한 명령어는 실행 도중 인터럽트나 다른 CPU의 개입이 불가능하다.

라. Compare-And-Swap (CAS)

CAS는 현재 값이 기대한 값과 같으면 새로운 값으로 교체하는 원자적 연산이다.
여기서 기대한 값은 lock이 걸리기 전에 저장하고 있었던 값을 의미한다.
즉, 다른 프로세스를 처리하고 왔을 때 동일한 값을 참조하는지 확인하는 것이다.

bool CAS(int* addr, int expected, int new_value)
{
    if (*addr == expected)
    {
        *addr = new_value;
        return true;
    }

    return false;
}

예시

CAS(&lock, 0, 1);

lock = 0 → 성공
lock = 1 → 실패

장점

락 없이 구현 가능
현대 CPU가 지원

단점

Busy Waiting 발생 가능
ABA Problem 발생 가능

마. Spinlock

Spinlock은 락을 얻을 때까지 반복해서 검사하는 방식이다.

while(CAS(&lock, 0, 1) == false);

락을 획득하면 임계 구역 진입

critical_section();

이후

lock = 0;

으로 해제한다.

장점

문맥 교환 비용 없음
짧은 임계 구역에 효과적

단점

CPU를 계속 사용함
긴 대기(Busy Waiting)에는 비효율적

바. Semaphore

Semaphore는 여러 프로세스의 접근을 제어하는 동기화 기법이다.

정수 변수와 두 개의 연산을 사용한다.

wait()
signal()

wait(P)

S--;
if(S < 0)
    block();

signal(V)

S++;
if(S <= 0)
    wakeup();

Binary Semaphore

이름에서도 나오듯이 0과 1만 사용해서 관리한다.

S = 1

Mutex와 유사하게 사용한다.

Counting Semaphore

S = N

동시에 N개 프로세스까지 허용한다.

예시

DB Connection Pool
Producer Consumer Problem

사. Deadlock

둘 이상의 프로세스가 서로 자원을 기다리며 영원히 진행하지 못하는 상태이다.

예시

P1
Lock A
Wait B

P2
Lock B
Wait A

Deadlock 발생 조건

Mutual Exclusion

자원을 공유할 수 없음

Hold and Wait

자원을 가진 채 다른 자원을 기다림

No Preemption

강제로 뺏을 수 없음

Circular Wait

원형 대기 발생

P1 → P2 → P3 → P1

위 4개가 모두 만족해야 Deadlock이 발생한다.

아. Two-Phase Locking (2PL)

데이터베이스에서 직렬 가능성(Serializability)을 보장하기 위한 락 프로토콜이다.

Growing Phase

락만 획득 가능

lock(A)
lock(B)

Shrinking Phase

락만 해제 가능

unlock(B)
unlock(A)

핵심 규칙

락을 해제하기 시작하면
새로운 락을 획득할 수 없다.

장점

Conflict Serializable 보장

단점

Deadlock 발생 가능

[운영체제] 상호배제