동기화 문제, 세마포어 & 뮤텍스

728x90

동기화 (Synchronization)

프로세스들 간에 자원에 대한 접근 순서를 정하거나 특정 기능의 실행 순서를 정하는 행위
즉, 여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것

프로세스의 코드 영역 中 공유 자원을 접근하는 코드를 `임계 영역`이라고 부름

경쟁 조건 문제 = 임계 영역의 문제

경쟁 조건 (Race Condition)

여러 개의 스레드나 프로세스가 동시에 공유 자원에 접근하면서, 실행 순서에 따라 결과가 달라지는 문제
즉, 누가 먼저 실행되느냐에 따라 결과가 달라짐

이는 예측 불가능한 결과나 시스템의 오류를 초래할 수 있음

왜 경쟁 조건이지 ❓
여러 스레드 (프로세스)가 공유 자원에 먼저 접근하려고 `경쟁(Race)`하기 때문
경쟁 결과에 따라 의도치 않게 동작할 수 있으므로 `조건 (Condition)`이 붙어서
👉 Race Condition = 경쟁 상태에서 발생하는 조건적 문제

경쟁 조건이 발생하지 않도록 하려면, 스레드의 순차적 실행을 보장하면 됨

임계 영역 (Critical Section)

공유자원에 접근하는 코드 중 동시에 실행했을 때 문제가 발생할 수 있는 코드
즉, 경쟁 조건을 유발시키는 코드 영역

if (balance > 0) {
    withdraw(100);   // 계좌에서 돈 빼기
}

여러 스레드에서 동시에 실행되면 잔액이 마이너스가 될 수 있음!

임계 영역 문제의 해결조건

근본적인 해결책은 공유자원에 대한 동시접근을 방지하는 것임

2개 이상의 프로세스가 동시에 공유자원에 접근하지 못하도록 해야하는데, 이를 상호 배제라고 함
하지만, 상호 배제에 집중 하다 보면 의도치않게 프로세스가 실행되지 못하고 마냥 대기하는 기아 상태에 빠질 수 있음

이를 방지하기 위해 `진행 (progress)`와 `한계 대기 (bounded wating)`라는 조건을 추가해야 함

∴ 임계 영역 문제를 해결하기 위해서는 세 가지 기본 조건이 충족돼야 함

상호 배제 (Mutual Exclusion): 한 시점에 하나의 스레드(프로세스)만 임계 영역에 접근해야 함.
이는 다른 스레드가 동시에 같은 자원을 변경할 수 없도록 보장
진행 (Progress) : 임계 영역에 접근하고자 하는 스레드가 없거나, 임계 영역에서 실행을 마친 스레드가
다른 스레드의 진입을 무한히 지연시키지 않아야 함
한계 대기 (Bounded Wating) : 어떤 스레드도 다른 스레드에 의해 무한히 대기 상태로 남겨져서는 안 됨.
즉, 모든 스레드는 유한 시간 내에 임계 영역에 진입할 수 있어야 함

어떻게 상호 배제를 보장할 수 있을까?

👉 Lock 이용!!

임계 영역 문제의 해결 방법

크게 소프트웨어적 방법, 하드웨어적 방법, 그리고 운영체제에 의한 방법으로 구분됨.

해결 방식	설명	실 사용 여부
하드웨어적 해결	CPU 명령어 (Test-and-Set) 등으로 구현	✅ OS나 라이브러리 내부에서 사용 (직접 사용은 드묾)
운영체제적 해결	세마포어, 모니터, Mutex 등 OS 수준에서 제공하는 동기화 기능	✅ 자주 사용
소프트웨어적 해결	순수 SW로 알고리즘 구현 (ex: 피터슨 알고리즘)	❌ 실제 개발에서는 거의 안 씀 (교육용 多)

운영체제적 + 하드웨어적 방법이 실무에서 주로 사용

`Java synchronized` : JVM이 내부적으로 OS의 Mutex 또는 모니터 이용

하드웨어적 해결방법

CPU의 명령어 수준에서 상호배제를 구현할 수 있도록 지원하는 방식
Test and Set과 Compare and Swap 등의 명령어가 있음.
원자적으로 수행될 수 있도록 상호배제가 필요한 코드 영역에 대해서 인터럽트를 금지
인터럽트가 금지 되면 `time-out` 인터럽트도 발생하지 않아 임계 영역 내에서 준비나 대기상태로 돌아가는 일이 없도록 할 수 있음

1. Test-and-Set

병렬 프로그래밍 및 운영 체제에서 임계 영역에 대한 접근을 제어하는데 사용

하나의 원자적(atomic) 연산으로, 메모리 위치의 값을 테스트 하고, 그 값을 설정하는 동작을 함

CPU atomic 명령어 ❓
- 실행 중간에 간섭받거나 중단 되지 않음
- 같은 메모리 영역에 대해 동시에 실행되지 않음
ex) 두 스레드가 old 값을 확인 할 때 동기화 하여 실행함 (= cpu 레벨에서 하나씩만 실행함)

작동 원리

하나의 변수(보통 락 변수)를 사용하여 구현됨.
이 변수는 두 가지 상태, 즉 잠김(locked) 상태와 해제(unlocked) 상태를 가질 수 있음.

연산의 기본 원리

테스트: 함수는 락 변수의 현재 값을 읽습니다.
셋: 읽은 값에 상관없이 락 변수의 값을 "잠김" 상태로 설정합니다.
결과 반환: 원래 락 변수의 값을 반환합니다.

테스트 앤드 셋 연산의 핵심은 이 과정이 원자적 연산으로 수행된다는 것임.
즉, 연산을 수행하는 동안에는 다른 어떤 프로세스나 스레드도 락 변수에 접근할 수 없음

bool test_and_set(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

void acquire_lock(bool *lock) { 
    while (test_and_set(lock)) {
        // 바쁜 대기: 락이 해제될 때까지 계속 시도 = 스핀락
    }
    // 락 획득
}

void release_lock(bool *lock) {
    *lock = false; // 락 해제
}

왜 계속 잠김 상태로 설정하나 ❓
만일, 조건문으로 lock이 false인 경우에만 true로 설정하면,
동시에 접근 했을 때 lock==false면, 둘 다 락을 얻을 수 있는 상태가 되버림

즉, 두 스레드가 동시에 락을 잡을 수 있는 경쟁 조건이 발생할 수 있음

스핀 락 (Spin Lock)

락을 가질 수 있을 때까지 반복해서 시도
락을 기다리는 동안 CPU를 낭비한다는 단점 존재
이를 개선하기 위해 락이 준비되면 깨우는 방식이 등장

2. Comparre and Swap (CAS)

CAS 연산은 원자적으로, 메모리 위치의 값을 비교하고 예상되는 값과 일치하는 경우에만 새로운 값으로 Update

기본 동작

CAS 연산은 세 가지 주요 인자를 받음

ptr (메모리 위치): 연산이 적용될 메모리 위치의 포인터
expected_value (예상 값): 해당 메모리 위치에서 예상하는 값
new_value (새로운 값): 메모리 위치에 저장하고자 하는 새로운 값

동작 원리

CAS 연산은 메모리 위치 ptr에 저장된 현재 값을 expected_value와 비교
현재 값과 expected_value가 같으면, 메모리 위치 ptr에 new_value를 저장하고 true를 반환하여 연산이 성공했음을 나타냄.
만약 값이 다르면, 아무것도 변경하지 않고 false 반환

bool compare_and_swap(int* ptr, int expected_value, int new_value) {
    if (*ptr == expected_value) {
        *ptr = new_value;
        return true;
    }
    return false;
}

void atomic_increment(int* counter) {
    int oldValue;
    do {
        oldValue = *counter; // 현재 카운터 값을 읽어옴
    } while (!compare_and_swap(counter, oldValue, oldValue + 1)); 
    // CAS를 사용하여 안전하게 카운터를 증가
}

락을 사용하지 않기 때문에, 컨텍스트 스위치 오버헤드가 없도 데드락의 위험이 줄어듦

운영체제 지원에 의한 해결 방법

운영체제는 다양한 동기화 도구를 제공하여 프로세스와 스레드가 공유 자원에 대해 안전하게 접근할 수 있도록 함

이런 동기화 도구들은 데이터의 일관성을 유지하고, 경쟁 조건 방지에 필수

세마포어 (Semaphore)

signal mechanism을 가진, 하나 이상의 프로세스 / 스레드가 임계 영역에 접근 가능하도록 하는 장치
`정수 값`과 두 가지 원자적 연산 `wait()`와 `signal()`로 구성
세마포어의 값 = 공유 자원에 접근할 수 있는 권한의 수

wait 연산 (p 연산)	세마포어의 값 감소, 값이 0보다 크면 프로세스는 계속 실행. 0인 경우, 세마포어 해제까지 대기
siganl 연산 (v 연산)	세마포어의 값 증가 대기 중인 프로세스가 있는 경우 하나를 깨움

한 번에 여러 스레드가 특정 자원에 접근할 수 있도록 허용해야 하거나, 복잡한 동기화와 요구사항이 있는 경우 효과적

이진 세마포어: 공유 자원에 하나의 프로세스만 접근하도록 통제
카운팅 세마포어: 여러 스레드가 동시에 공유 자원에 접근할 수 있도록 함

Semaphore sem = new Semaphore(3); // 동시에 3개까지 접근 가능

sem.acquire(); // 자원 요청 (카운터 -1)
try {
    // 공유 자원 사용
} finally {
    sem.release(); // 자원 반납 (카운터 +1)
}

최대 3개의 스레드가 동시에 접근 가능.
소유권이 없기 때문에, acquire와 release를 다른 스레드가 호출해도 됨

악의적으로 release를 실행하면 ❓
예상 시나리오:
Semaphore sem = new Semaphore(3); // 동시에 3개만 접근 가능

// 어떤 스레드가 acquire()도 안 하고 그냥 release() 호출
sem.release(); // 🎯 카운터가 4가 됨 → 실제보다 자원이 하나 더 있다고 착각
세마포어는 본래 단순한 카운터 모델이라 소유권 추적 X
release()가 정확히 acquire()와 1:1 매칭된다는 신뢰를 전제로 함
∴ 개발자 책임이 큼

세마포어는 순서를 정해줄 때 사용

P1이 먼저 실행되든, P2가 먼저 실행되든 task3는 항상 task1이 선행돼야 함
👉 세마포어는 시그널 메커니즘을 갖는다

또한, signal과 wait는 수반되지 않아도 됨.

뮤텍스 (Mutexes)

상호 배제를 위해 사용되는 동기화 도구, 한 번에 하나의 스레드만 특정 자원 또는 임계 영역에 접근 가능

`잠금(Lock)`과 `잠금 해제 (UnLock)` 두 가지 기본 연산 제공

잠금(Lock)	스레드가 임계 영역 진입 전 호출되며, 뮤텍스가 이미 다른 스레드에 의해 잠겨있는 경우 호출한 스레드는 대기 상태로 들어감
잠금 해제 (UnLock)	스레드가 임계 영역의 작업을 완료한 후 호출되며, 뮤텍스를 해제하고 다른 스레드의 접근 허용

ReentrantLock lock = new ReentrantLock();

lock.lock();        // 락 획득 (임계 구역 진입)
try {
    // 임계 구역 작업
} finally {
    lock.unlock();  // 락 해제 (다른 스레드 진입 가능)
}

잠금을 획득한 스레드만이 잠금을 해제할 수 있음

이진 세마포어 = 뮤텍스 ❓
이진 세마포어는 단순한 값 기반 동기화 도구 (누구나 release 가능)
뮤텍스는 자원 보호를 위한 소유권 기반 락

뮤텍스는 priority inheritance 속성을 가짐 → 락에 관한 의존을 해결하기 위함 (스케줄링 알고리즘 관련)

뮤텍스가 스핀락보다 항상 좋을까?

멀티 코어 환경이고, 임계 영역에서의 작업이 컨텍스트 스위칭보다 더 빨리 끝난다면
스핀락이 뮤텍스보다 더 이점이 있다.

컨텍스트 스위칭: 잠들고 깨는 과정에서 컨텍스트 스위칭 발생
멀티 코어: 싱글 코어인 경우 스핀락의 이점이 없음 컨텍스트 스위칭 발생

뮤텍스 vs 세마포어

공통점

동시에 실행되는 프로세스/스레드 간에 공유 자원 보호
잘못 사용 시 교착상태 발생 가능
자원을 사용할 수 없으면 스레드를 대기 상태로 만들 수 있음

차이점

구분	세마포어	뮤텍스
자원 수	여러 자원 동시 제어 가능 (카운팅 세마포어의 경우)	오직 1개의 자원 보호
소유권	누구나 release 가능, 소유권 X	락을 획득한 스레드만 해제 가능
목적	자원 수 제어 또는 동기화	상호 배제
실수 가능성	release만 따로 호출 가능	락/언락 짝이 맞지 않으면 컴파일 에러나 예외 발생
값의 범위	0이상의 정수 \|\| 0/1	일반적으로 0또는 1
busy wait	구현 방식에 따라 스핀락으로도 작동 가능	일반적으로 block / unblock
사용 예시	임계 구역 보호, 단일 자원 보호	다수 자원 제어, 생상자 - 소비자 문제

교착 상태 (Dead Lock)

두 개 이상의 프로세스 혹은 스레드가 서로가 가진 리소스를 기다리는 상태

데드락을 만드는 네 가지 조건

상호 배제 (Mutual exclusion)
리소스를 공유해서 사용할 수 없다. (한 번에 하나씩)
점유 대기 (Hold and Wait)
프로세스가 이미 하나 이상의 리소스를 취득한 상태에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다림
비선점 (No Preemption)
리소스 반환은 오직 그 리소스를 취득한 프로세스만 할 수 있음
순환 대기(Circular Wait)
프로세스들이 순환 형태로 서로의 리소스를 기다림

OS의 데드락 해결 방법

1. 데드락 방지 (Deadlock prevention)

네 가지 조건 중 하나가 충족되지 않게 시스템을 디자인

리소스를 공유 가능하게 함 👉 현실적으로 불가 (상호 배제)
사용할 리소스들을 모두 획득한 뒤 시작 & 리소스를 전혀 가지지 않은 상태에서만 요청 (점유 대기)
이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 함 (비선점)
모든 리소스에 순서 체계를 부여, 오름차순으로 리소스 요청 (순환 대기, 1번 먼저 요청)

2. 데드락 회피 (Deadlock Avoidance)

실행 환경에서 추가적인 정보를 활용하여 데드락이 발생할 것 같은 상황을 회피하는 것

프로세스가 자원을 요청할 때마다 시스템 상태를 검사하여 교착 상태 가능성 판단.
만일, 가능성이 있는 경우 요청 거부 혹은 지연

교착상태 회피 기법의 핵심은 `안전 상태(Safe State)`와 `불안전 상태(Unsafe State)`의 개념에 기반을 둠

안전 상태 ❓
시스템이 프로세스의 모든 추가 요구를 충족시킬 수 있는 충분한 자원을 가지고 있어서,
모든 프로세스가 교착상태 없이 실행을 완료할 수 있는 상태 의미

은행원 알고리즘 (Banker's Algorithm)

교착상태 회피 알고리즘 중 하나로, 다익스트라에 의해 고안됨

핵심아이디어는 은행이 고객에게 대출을 해주는 방식에 비유
👉 고객이 대출 요청 시, 그 요청이 은행의 현재 자본을 기반으로 안전하게 충족되는지 판단하여 대출 승인 또는 거절

즉, 프로세스가 자원을 요청할 때, 그 요청이 시스템을 안전 상태에 유지할 수 있는지 판단하여 자원 할당 결정

은행원 알고리즘의 주요 요소

최대 요구량(Maximum Demand): 각 프로세스가 실행을 완료하기 위해 요구할 수 있는 자원의 최대량
할당량(Allocation): 현재 각 프로세스에게 할당된 자원의 양
필요량(Need): 각 프로세스가 요구할 수 있는 최대 자원에서 현재 할당된 자원을 뺀 양 `필요량 = 최대 요구량 - 할당량`
가용량(Available): 시스템에서 현재 사용 가능한 자원의 양

작동 원리

안전성 검사(Safety Check): 시스템이 안전 상태인지 확인
자원 요청(Resource Request): 프로세스가 자원을 요청할 때, 시스템은 요청이 안전 상태를 유지할 수 있는지를 검사
만약 요청을 충족시키고도 시스템이 안전 상태에 있을 경우에만 자원을 할당

예시1

자원 종류: A, B, C

A = 10, B = 5, C = 7
5개의 프로세스 P0 ~ P4

Process	Max (A B C)	Allocation (A B C)	Need (A B C)
P0	7 5 3	0 1 0	7 4 3
P1	3 2 2	2 0 0	1 2 2
P2	9 0 2	3 0 2	6 0 0
P3	2 2 2	2 1 1	0 1 1
P4	4 3 3	0 0 2	4 3 1

사용 가능한 자원 계산: (A:3개), (B:3개), (C:2개)

안전 상태 시뮬레이션

초기 Available: [3, 3, 2]

P1의 Need [1 2 2] <= Available [3 3 2] → 실행 가능
- 자원 회수 후 Available = [3+2, 3+0, 2+0] = [5, 3, 2]
P3의 Need [0 1 1] <= Available [5 3 2] → 실행 가능
- 자원 회수 후 Available = [5+2, 3+1, 2+1] = [7, 4, 3]
P4의 Need [4 3 1] <= Available [7 4 3] → 실행 가능
- 자원 회수 후 Available = [7+0, 4+0, 3+2] = [7, 4, 5]
P0의 Need [7 4 3] <= Available [7 4 5] → 실행 가능
- 자원 회수 후 Available = [7+0, 4+1, 5+0] = [7, 5, 5]
P2의 Need [6 0 0] <= Available [7, 5, 5] → 실행 가능
- 최종 Available = [7+3, 5+0, 5+2] = [10, 5, 7]

➡️ 모든 프로세스가 순차적으로 실행될 수 있으므로, 이 상태는 안전 상태(Safe State)!

3. 데드락 감지 & 복구 (Deadlock Detection and Recovery)

데드락을 허용하고 데드락이 발생하면 복구하는 전략

1) 프로세스 종료

교착상태에 관련된 프로세스 중 하나 또는 여러 개를 종료
프로세스를 종료하는 방법에는 임의로 선택하여 종료시키거나, 교착상태를 해결하는 데 필요한 최소한의 프로세스 수를 종료시키는 방법 등이 존재
비용이 높은 방법일 수 있으며, 작업의 손실이 발생할 수 있음

2) 리소스의 일시적 선점 허용

교착상태 해결을 위해 하나 이상의 프로세스로부터 자원을 강제로 회수
선점된 자원은 다른 프로세스에 재할당되어 교착상태를 해결
자원을 선점하는 과정에서 프로세스의 상태를 안전하게 복구할 수 있는 방법을 고려해야 함.
예를 들어, 프로세스를 이전의 안전한 지점으로 롤백시키고 재실행할 수 있어야 한다.

참고

https://wikidocs.net/232212#_1

728x90

동기화 (Synchronization)

경쟁 조건 (Race Condition)

임계 영역 (Critical Section)

임계 영역 문제의 해결조건

어떻게 상호 배제를 보장할 수 있을까?

임계 영역 문제의 해결 방법

하드웨어적 해결방법

1. Test-and-Set

작동 원리

연산의 기본 원리

스핀 락 (Spin Lock)

2. Comparre and Swap (CAS)

기본 동작

동작 원리

운영체제 지원에 의한 해결 방법

세마포어 (Semaphore)

세마포어는 순서를 정해줄 때 사용

뮤텍스 (Mutexes)

뮤텍스가 스핀락보다 항상 좋을까?

뮤텍스 vs 세마포어

공통점

차이점

교착 상태 (Dead Lock)

데드락을 만드는 네 가지 조건

OS의 데드락 해결 방법

1. 데드락 방지 (Deadlock prevention)

2. 데드락 회피 (Deadlock Avoidance)

은행원 알고리즘 (Banker's Algorithm)

안전 상태 시뮬레이션

3. 데드락 감지 & 복구 (Deadlock Detection and Recovery)

1) 프로세스 종료

2) 리소스의 일시적 선점 허용

티스토리툴바