동기화(1) - 임계구역 문제 (Critical Section)

임계구역 문제는 여러 프로세스 혹은 스레드가 공유 자원에 동시에 접근할 때 발생하는 동기화 문제를 의미한다.

이를 해결하지 않으면 데이터 충돌 , 정합성 문제 , 교착 상태 (Deadlock) 등이 발생할 수 있다.

임계구역이란?

임계구역은 여러 프로세스가 공유자원 (메모리, 파일, 변수 등)에 접근하는 코드 영역이다.

다중 프로세스/스레드 환경에서 동시에 같은 자원에 접근하면 데이터 일관성이 깨질 수 있기 때문에 상호 배제를 보장하여 한 번에 하나의 프로세스만 임계구역에 들어가도록 제한해야한다.

임계구역 문제 해결 조건

상호 배제 (Mutual Exclusion) : 동시에 임계 구역에 두 개 이상의 프로세스가 진입할 수 없어야 한다.
진행 (Progress) : 임계 구역이 비어 있을 때, 진입을 원하는 프로세스는 반드시 유한 시간 내에 진입할 수 있어야 한다.
유한한 대기 (Bounded Waiting) : 프로세스가 임계 구역 진입을 요청한 후, 다른 프로세스가 임계 구역에 계속 진입하더라도 유한한 횟수 이후에는 임계 구역에 진입할 수 있어야 한다. (Starvation 방지)

임계구역 문제 해결 방법

1. 소프트웨어적 해결 방법 (Software Approach)

peterson's Algorithm

피터슨 알고리즘은 두 개의 공유 변수를 사용한다.

// 프로세스가 2개 (0번, 1번 프로세스)
int turn;
bool flag[2];

turn 변수는 임계 구역에 진입 차례를 표시하는 변수이다. ex) 0이면 0번 프로세스 차례

flag[] 변수는 각 프로세스의 진입 의사를 표시한다. ex) flag[1]=true 이면 1번 프로세스가 진입하고 싶다.

// i는 현재 프로세스 번호 (0 또는 1)
// j는 다른 프로세스 번호 (1 또는 0)

do {
    // 진입 희망을 표시
    flag[i] = true;
    turn = j;  

    // 다른 프로세스가 진입을 원하고, 동시에 다른 프로세스 차례이면 기다림
    while (flag[j] && turn == j);

    /* 임계구역 진입(Critical Section) */
    
    // 임계구역을 벗어남
    flag[i] = false;

    /* 나머지 작업(Reminder Section) */

} while(true);

예시) 프로세스 0과 1이 동시에 임계구역에 진입을 시도할 때

그런데 분명 프로세스 0과 1이 동시에 접근했다고 했는데 왜 프로세스0이 먼저 실행된걸까?

정확히 말하자면 cpu는 한 번에 하나의 명령어만 수행하기 때문에 프로세스가 정확히 동시에 명령을 수행할 수 없다. 피터슨 알고리즘은 논리적으로는 두 프로세스가 동시에 접근했을 때를 가정하지만, 현실적으로는 미세한 시간차로 인해 실제 순서는 반드시 존재하는것이다. 하지만 그 시간차가 너무 미세하기 때문에 동시 접근이라 봐도 무방하다.

그럼 멀티프로세스 환경에서 여러개의 cpu가 동시에 임계구역에 접근한다면? 동시에 접근하는거 아닌가?

실제로 멀티프로세스 환경에서 peterson 알고리즘은 잘 동작하지 않는다. 그렇기에 하드웨어적 해결방법 또는 운영체제가 제공하는 동기화 도구를 사용해야 한다. !!!

그럼 3개가 동시에 오면..?

마찬가지로 피터슨 알고리즘은 3개이상의 프로세스에서는 제대로 동작하지 않는다.

2. 하드웨어적 해결 방법 (Hardware Support)

하드웨어적 해결 방법은 cpu 차원에서 원자적으로 수행되는 연산을 이용해서 상호배제를 완벽히 보장하는 방법이다. 즉, 특정 연산을 실행하는 동안 다른 cpu가 그 변수에 접근할 수 없도록 하드웨어적으로 보장한다.

대표적인 해결 방법

Test-and-set
Compare-and-Swap
Fetch-and-Add
Load-Link / Store-Conditional

1. Test-and-Set (TAS)

가장 대표적인 하드웨어 기반 연산으로 TAS는 메모리 위치의 값을 읽고 그 값을 즉시 1(True)로 설정한다.

// Test-and-Set의 원형 (pseudo-code)
bool TestAndSet(bool *target) {
    bool rv = *target;  
    *target = true;     // 항상 true로 변경
    return rv;          // 원래 값 리턴
}

while (TestAndSet(&lock));  // lock이 풀릴 때까지 바쁜 대기
// 임계 구역 진입
lock = false;               // 임계구역 빠져나오며 lock을 false로 초기화

만약 target이 false 이면 리턴값은 false이므로 임계구역 진입이 가능하다. 또한, target의 값이 true로 바꼈으므로 다른 프로세스는 접근할 수 없다.

매우 간단하고 구현하기 쉽지만 lock이 끝날때 까지 기다려야하는 busy-wait 상태로 cpu자원을 비효율적으로 사용한다.

2. Compare-and-Swap(CAS)

다중 스레딩 및 멀티코어 환경에서 자주 사용된다. CAS는 세 개의 매개변수 ( 메모리 주소 , 기대값 , 변경할 값 ) 가진다.

지정된 메모리 주소의 값이 기대한 값과 같다면 이를 변경하고 , 아니면 아무것도 하지 않는다.

bool CAS(int *addr, int expected, int newValue) {
    if (*addr == expected) {
        *addr = newValue;
        return true; // 성공
    }
    else {
        return false; // 실패
    }
}

예시) 공유 변수 value(초기상태=5)에 두 개의 스레드 T1,2가 동시에 이 값을 증가시키려고 접근할때

T1은 기대값(5)과 메모리의 값(5)이 같으므로 CAS 실행, T2는 기대값(5) 와 메모리의 값(6)이 다르므로 실패

이때 T2는 메모리에서 값을 읽어 기대값을 갱신한 후 기대값과 메모리의 값이 일치할 때 까지 재시도를 하게 된다.

AtomicInteger atomicValue = new AtomicInteger(0);

public void increment() {
    int oldValue, newValue;

    do {
        oldValue = atomicValue.get();   // ✅ 메모리에서 현재값을 읽음
        newValue = oldValue + 1;
        
        // compareAndSet이 실패하면 다시 메모리에서 읽어서 oldValue 갱신
    } while (!atomicValue.compareAndSet(oldValue, newValue));
}

일치할 때 까지 다시 값을 읽어 T2의 역할(+1) 을 해준다.

하지만 재시도가 무한정 반복될 수 있기 때문에 이를 방지하기 위한 추가 전략을 고려해야 한다.

그중 하나인 Back-off 전략은 실패할 때마다 재시도 간격을 점진적으로 늘려 경쟁을 줄이는 방식이다.

int retries = 0;
do {
    oldValue = value.get();
    newValue = oldValue + 1;

    if (value.compareAndSet(oldValue, newValue))
        break;

    // Back-off: 실패하면 일정 시간 기다림
    Thread.sleep(1 << retries); // 지수적으로 기다리는 시간 증가
    retries++;
} while (retries < MAX_RETRIES);

3.Fetch-and-Add

Fetch-and-Add는 특정 메모리 위치의 값을 원자적으로 증가시키고 원래의 값을 반환한다. 원자적으로 실행된다는 말은 스레드나 프로세스가 메모리 값을 읽고 연산을 수행하는 과정 중 다른 스레드가 끼어들지 못한다는 의미이다. 연산 자체는 항상 성공하지만 어떤 스레드가 먼저 실행될지 보장하지 않기 때문에 수행 순서가 상관없는 제한적인 상황에서만 사용한다.

int FetchAndAdd(int *addr, int increment){
    int old = *addr;      // 기존 값 저장(fetch)
    *addr = old + increment;  // 증가한 값 저장(add)
    return old;           // 기존 값을 반환
}

4. Load-Link / Store-Conditional (LL / SC)

ARM 및 MIPS 프로세서에서 널리 사용되는 방식이다.

Load-Linked (LL)
- 특정 메모리 주소의 값을 읽고(Load), 이 주소를 모니터링 상태로 설정
- 모니터링된 주소의 값이 변경될 경우 이를 감지할 수 있도록 CPU가 상태를 기록
Store-Conditional (SC)
- LL 이후 다른 스레드가 그 주소를 변경하지 않았다면 새로운 값을 저장
- 만약 다른 스레드가 그 값을 변경했다면, 저장을 수행하지 않고 실패를 반환

do {
    oldValue = LL(&value); // LL 명령 수행 (읽기+모니터링)
    newValue = oldValue + 1;
    
    // SC 연산 (모니터링 중 변경 없으면 성공)
} while (!SC(&value, newValue));

이러한 하드웨어적 방법은 멀티 cpu 환경에서도 상호 배제를 완벽하게 보장하고 임계구역에 원자적으로 접근하도록 보장되지만 하드웨어(cpu)의 특정 명령어가 필요하고 busy-wait 문제가 발생할 수가 있다. 이는 OS의 Sleep/Wakeup을 병행하여 해결한다.

3. OS 커널 기반 해결 방법 ( Operating System Support)

하드웨어적 방법에서 발생하는 busy-wait을 해결하기 위해 운영체제가 제공하는 동기화 기법을 사용하여 임계구역 문제를 해결할 수 있다. 대표적인 방법으로는 세마포어(Semaphore) , 뮤텍스(Mutex) , 모니터(Monitor) 가 있다.

1. 세마포어 (Semaphore)

하드웨어 기반 원자적 명령을 이용하여 구현된다. 세마포어는 일반적으로 정수형 변수로 나타내며, 초기값을 부여한 뒤 두가지 주요 연산 (wait ,signal)을 통해 값을 변경한다.

wait 연산 : 자원을 얻으려는 프로세스가 수행하는 연산으로 세마포어 값을 하나 감소시킨다. 만약 세마포어 값이 음수가 되면 프로세스는 대기 상태로 전환된다.

// Wait 연산의 예시 코드
wait(S):
    S--;
    if (S < 0)
        프로세스를 대기상태로 전환;

signal 연산 : 프로세스가 자원을 사용한 뒤 반환할 때 수행하는 연산으로 세마포어 값을 하나 증가시킨다. 세마포어가 0이하일 경우 대기 상태였던 프로세스 중 하나를 깨워 실행 가능한 상태로 만든다.

※세마포어에 의해 대기상태로 진입한 프로세스는 운영체제의 waiting queue에 저장된다. 프로세스의 실행 순서는 운영체제에 따라 FIFO , Priority , RR 등 여러 방식으로 나뉜다.

세마포어는 초기값에 따라 이진 세마포어와 계수 세마포어로 나뉜다.

이진 세마포어 (Binary Semaphore) : 세마포어 값이 0또는1 , 주로 뮤텍스와 같은 용도로, 오직 하나의 프로세스만 임계 구역에 진입하도록 상호 배제를 보장할 때 사용된다.
계수 세마포어 (Counting Semaphore) : 세마포어의 값이 0이상인 정수로 여러 개의 자원을 동시에 접근 가능하게 하고 싶을 때 사용한다.

예시)

하지만 잘못 사용하면 데드락(deadlock)이나 기아(starvation)가 발생할 수 있다.

2. 뮤텍스 (Mutex)

뮤텍스는 이진 세마포어의 특수한 형태라고 볼 수 있다.

mutex.lock();
// 임계구역 진입
// 공유 자원 접근 (변경, 작업 등)
mutex.unlock();
// 임계구역 벗어남

lock() 연산을 수행했을 때 다른 프로세스가 뮤텍스를 소유하고 있다면, 해당 프로세스는 대기(블록) 상태로 들어가고

unlock()연산을 수행하면 대기 상태의 프로세스 중 하나가 깨어나 뮤텍스를 소유한다.

뮤텍스와 세마포어는 비슷하지만 뮤텍스는 상호배제용, 세마포어는 동기화목적에 조금 더 치우친 방식이라 생각하자

3. 모니터 (Monitor)

모니터 내부에 공유 자원 및 보호된 코드(임계구역) 포함
하나의 프로세스(또는 스레드)만 모니터에 진입 가능
다른 프로세스(또는 스레드)가 접근을 시도하면 대기(waiting)
현재 실행 중인 프로세스(또는 스레드)가 모니터에서 나가면, 대기 중인 프로세스(또는 스레드) 중 하나가 실행됨

임계구역이란?

임계구역 문제 해결 조건

임계구역 문제 해결 방법

1. 소프트웨어적 해결 방법 (Software Approach)

2. 하드웨어적 해결 방법 (Hardware Support)

3. OS 커널 기반 해결 방법 ( Operating System Support)

티스토리툴바