[Operating System] Mutual Exclusion

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은 이러한 기아 상태를 방지하기 위한 조건이다.

세 가지 조건 정리

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

Peterson's Algorithm

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

두 개의 변수만 사용한다.

bool flag[2];
int 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)을 제공한다.

대표적으로

등이 있다.

이러한 명령어는 실행 도중 인터럽트나 다른 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이면 CAS가 성공하고 lock을 획득한다.
• lock = 1이면 CAS가 실패하고 lock을 획득하지 못한다.

CAS는 락 없이 구현 가능하고 현대 CPU가 지원한다는 장점이 있다.

단점으로는 Busy Waiting과 ABA Problem이 발생할 수 있다.

Spinlock

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

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

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

critical_section();

이후

lock = 0;

으로 해제한다.

Spinlock은 문맥 교환 비용이 없기 때문에 짧은 임계 구역에 효과적이다.

하지만 CPU를 계속 사용하므로 긴 대기(Busy Waiting)에는 비효율적이다.

Mutual Exclusion 기법 정리