[운영체제] 동기화

✅  경쟁 상태 (Race Condition)

: 여러 프로세스나 스레드가 동시에 공유 데이터에 접근할 때, 수행 순서에 따라 실행 결과가 달라질 수 있는 상황

 

경쟁 상태는 공유 자원에 대한 접근을 적절히 통제하지 못할 때 발생하는 문제이다.

예상치 못한 실행 순서 때문에 데이터 불일치나 프로그램 오류가 발생할 수 있다.

 

---

 

✅ Thread Safe

: 여러 스레드가 동시에 같은 자원에 접근해도 프로그램 실행 결과가 올바르게 나오는 상태

 

여러 스레드가 함께 실행되더라도 데이터가 손상되지 않고, 예상한 대로 정확하게 동작하는 프로그램을 Thread Safe 하다고 한다.

즉, 여러 스레드가 Race Condition에 들어가더라도 연산 결과는 정합성이 보장될 수 있도록 메모리 가시성이 확보된 상태이다.

 

메모리 가시성: 스레드에서 변경한 특정 메모리 값이 다른 스레드에서 확실히 인식할 수 있는지

 

---

 

📍 보장하는 방법

1️⃣ Re-entrancy(재진입성)

: 여러 스레드에 의해 동시에 호출되더라도 올바르게 동작할 수 있도록 설계함

 

• 내부 상태를 공유하지 않거나 항상 독립적인 데이터 사용
• 함수 자체가 Thread Safe 하게 작동하도록 만드는 것

 

2️⃣ Mutual Exclusion(상호 배제)

: 공유 데이터에 접근하는 임계 영역에 하나의 스레드만 접근 가능하도록 함

 

• 일반적으로 가장 많이 사용되는 방법
• 대표적인 알고리즘: 뮤텍스, 세마포어, 모니터

 

3️⃣ Thread-local storage (스레드 로컬 저장소)

: 공유 자원의 사용을 최대한 줄이고, 각각의 스레드에서만 접근 가능한 저장소 사용

 

• 공유 상태를 피할 수 없는 경우 사용

 

4️⃣ Atomic Operation (원자 연산)

: 공유 자원에 원자적으로 접근하는 방법

 

• 공유 자원 변경에 필요한 연산을 원자적으로 분리
• 실제 데이터 변경이 이뤄지는 시점에 락 걸기
• 데이터 변경 시간 동안은 다른 스레드의 접근을 막음

 

---

✅  Peterson's Algorithm

: 멀티스레드 환경에서 두 개의 프로세스(또는 스레드)가 동시에 임계 구역(Critical Section)에 진입하지 못하도록 막는 고전적인 소프트웨어 기반 상호 배제 알고리즘

 

이 알고리즘은 락이나 세마포어 같은 동기화 도구 없이, 순수한 소프트웨어 로직만으로 상호배제를 보장하려는 시도이다.

 

• 두 개의 공유 변수로 동작
  
  • `flag [i]`: 프로세스 i가 임계 구역에 들어가고 싶어 하는지 여부 표시
  • `turn`: 어느 프로세스 차례인지 나타내는 변수
• 어떤 프로세스도 무한히 대기하지 않음을 보장함

 

🛠️ 문제점

이론적으로는 훌륭하지만, 현대 하드웨어 구조에서는 정상적으로 동작을 보장할 수 없다.

그 이유는 다음과 같다.

• 메모리 일관성 문제: 대 CPU는 성능 최적화를 위해 캐시를 사용하기 때문에, 한 스레드에서 변수 값을 변경해도 그 값이 다른 CPU에 즉시 반영되지 않을 수 있음
• 명령어 재배치: 명령어 실행 순서가 뒤 바뀌어 두 프로세스가 동시에 임계 구역에 진입하는 문제 발생
• Busy Waiting: 조건이 만족될 때까지 계속해서 검사하므로 CPU 자원을 비효율적으로 소모함

 

---

✅  프로세스 동기화 (Process Synchronization)

: 경쟁 상태를 방지하고, 공유 데이터의 일관성을 유지하기 위해 사용되는 기법

 

프로세스 동기화는 이러한 경쟁 상태를 방지하고, 공유 데이터의 일관성을 유지하기 위해 사용되는 필수 기법이다.

여러 프로세스가 동시에 공유 자원에 접근하더라도, 정해진 규칙에 따라 작업을 수행하게 만들어 데이터 무결성을 보장한다.

 

대표적인 동기화 도구에는 세마포어, 뮤텍스, 모니터가 있다.

 

---

 

📍 세마포어 (Semaphore)

: 임계 영역에 접근할 수 있는 프로세스 수를 제어하는 동기화 기법

 

• 종류 2가지
  • 1. Binary Semaphore: 뮤텍스와 동일하게 value 1을 가지는 세마포어
    2. Counting Semaphore: value가 1보다 큰 세마포어
• 여러 개의 프로세스나 스레드가 동시에 접근할 수 있는 자원의 개수 제어 가능
• n개 자원을 동시에 관리 가능
• 소유 개념 없음 → 락을 얻은 스레드와 해제하는 스레드가 달라도 무관
• 주로 제한된 수의 자원 접근 제어에 사용됨
• 현재 임계 영역에 접근 불가능하면, 프로세스는 대기 상태가 됨
  • 세마포어 값이 0보다 크면 임계영역에 접근 가능하고, 값이 0이면 대기 상태가 됨

 

임계 구역(Critical Section): 여러 프로세스가 데이터를 공유하며 수행될 때, 문제가 발생하지 않게 독점을 보장해줘야 하는 영역

 

---

 

📍 뮤텍스 (Mutex)

: 임계 영역에 접근할 수 있는 프로세스를 한 번에 하나만 허용하는 동기화 기법

 

• 1개의 스레드만 자원에 접근할 수 있도록 하는 이진 세마포어 형태의 락
• 이진 세마포어이므로 0 또는 1의 값을 가짐(0은 잠겨 있음을 의미)
• 소유 개념이 있음 → 락을 획득한 스레드만 해제 가능
• 임계구역 보호에 주로 사용됨

 

---

 

📍 모니터 (Monitor)

: 조건 변수를 사용하여 특정 조건이 충족될 때까지 프로세스를 대기시키는 동기화 기법

 

앞서 언급했던 뮤텍스와 세마포어는 락(lock)이나 해제(unlock) 호출 순서가 잘못되면, 타이밍 오류가 발생할 수 있다.

ex) 락을 거는 작업과 푸는 작업의 순서가 뒤바뀌는 경우

 

모니터는 이러한 문제를 방지하기 위해 고안된 개념이다.

 

• 세마포어의 발전된 형태
• 스레드가 모니터에 진입할 때 자동으로 락을 걸고, 작업을 마치고 나올 때 자동으로 락을 해제 -> 타이밍 오류 방지
• 모니터 내부에 정의된 프로시저를 통해서만 공유 데이터에 접근할 수 있도록 제한 -> 무결성 보장
• 운영체제 차원이 아닌, 프로그래밍 언어 자체에서 제공
  • ex) Java에서는 `synchronized` 키워드를 통해 모니터 기능 제공

 

[조건 변수의 주요 동작]

• `wait()`: 특정 조건이 만족될 때까지 스레드를 대기 상태로 전환
• `signal()`: 대기 중인 스레드를 깨워 실행 재개
• `broadcast()`: 모든 대기 중인 스레드를 깨움

 

---

📍 스핀락 (Spin Lock)

: 락이 해제될 때까지 반복적으로 CPU를 점유하며 루프를 도는 방식

 

뮤텍스에서 하나의 프로세스만 임계 영역에 접근할 수 있으므로, 다른 프로세스들은 임계영역에 접근하기 위해 Spin Lock을 발생시킨다.

 

장점

• 문맥 전환 비용 없음 -> Lock이 아주 짧게 점유될 경우 유리
• 커널 또는 하드웨어 초기화 코드에서 유용 (스케줄러 없는 환경에서도 동작)

단점

• CPU를 낭비함 -> 락을 오래 기다릴수록 비효율적

단점 해결

• 하이브리드 락 사용
• 짧은 임계 구역에서 사용

 

---

 

✅ Wait-Free와 Lock-Free

멀티스레드 환경에서 락을 사용하지 않고도 동기화할 수 있는 방법으로
Wait-Free와 Lock-Free 방식이 있다.

 

---

 

📍 Wait-Free

: 모든 스레드가 유한한 시간 안에 반드시 작업을 완료할 수 있는 동기화 방식

 

• 개별 스레드 완료 보장
• 모든 스레드가 동시에 진행
• 구현이 복잡하고 어려움
• Lock-Free에 비해 더 많은 오버헤드 발생 가능

 

---

 

📍 Lock-Free

: 시스템 전체로 보면 진행은 보장하지만, 개별 스레드가 무한 대기할 수 있는 동기화 방식

 

• 시스템 전체 진행 보장
• 항상 하나 이상의 스레드가 진행할 수 있음을 보장
• 일부 스레드가 대기될 가능성이 있다는 단점
• 비교적 구현이 쉬움

 

---

 

✅ 하드웨어적 동기화 기법

앞서 본 뮤텍스, 세마포어 등은 모두 소프트웨어적으로 구현된 동기화 기법이다.

CPU는 간단하고 빠른 하드웨어 명령어도 제공한다.

 

---

 

📍 TestAndSet (TAS)

: 변수의 현재 값을 확인(Test)하고, 값을 설정(Set)하는 동작을 한 번에 원자적으로 수행하는 명령어

 

• 현재 lock 변수 값을 읽음 (Test)
• lock 변수에 1을 저장함 (Set) - 이전 값과 상관없이
• 전체 동작이 한 번에 (atomic) 실행됨
• 단순하고 빠름
• 하지만 경쟁이 많을수록 불필요한 write가 많이 발생해 병목 가능

 

bool TestAndSet(bool* lock) {
    bool old = *lock;     // 현재 lock 값을 읽음
    *lock = true;         // lock 값을 1(true)로 설정
    return old;           // 기존 lock 값 반환
}

• false 반환: 락을 처음으로 획득
• true 반환: 이미 다른 스레드가 사용 중

 

---

 

📍 CompareAndSwap (CAS)

: 현재 메모리 값이 기대하는 값과 같을 경우에만 새로운 값으로 교체하는 명령어

 

• TAS보다 효율적
  • TAS는 메모리 값의 변경 여부에 상관없이 항상 값을 변경했더라면 CAS는 기댓값과 메모리 값이 같을 때만 값을 변경
• 실패한 스레드는 반복적으로 CAS를 재시도하여 진행성 보장

 

bool CompareAndSwap(int* addr, int expected, int newVal) {
     // addr이 가리키는 현재 값과 기대값(expected)을 비교
    if (*addr == expected) {

        // 같으면 newVal로 교체 → 원자적으로 수행됨
        *addr = newVal;

        // 교체 성공
        return true;
    }

    // 값이 달랐기 때문에 교체 실패
    return false;
}

• 현재 값이 기대한 값이면, newVal로 변경하고 true 반환
• 다르면, 아무것도 하지 않고 false 반환

 

---

✅ 멀티코어 환경에서 동기화 기법

멀티코어 환경에서는 여러 코어가 동시에 하나의 공유 자원에 접근할 수 있기에 동기화 기법이 필수이다.

 

1. 락 기반 동기화: 뮤텍스, 세마포어 등을 이용해 한 번에 하나의 코어만 자원 접근 가능
2. 원자적 연산: TAS, CAS처럼 중단 없이 실행되는 연산으로 락 없이 동기화 가능
3. 메모리 배리어: CPU 명령어 순서 재정렬을 막아 메모리 일관성 유지
4. 락 프리 알고리즘: 락 없이도 시스템 전체 진행 보장
5. 프레임워크 활용: OpenMP, Java Concurrency 등 병렬 처리 지원 라이브러리로 안전한 동기화 구현

 

---

 

✨ 동기화 추가 질문

[ Thread Safe를 구현하기 위해 반드시 락을 사용해야 할까요? 그렇지 않다면, 어떤 다른 방법이 있을까요? ]

반드시 락을 사용할 필요는 없다. 락 외에 다음과 같은 방법이 있다.
- Atomic 연산
- Immutable 객체(불변 객체)
- Thread-local storage (스레드 로컬 저장소)
- Lock-Free / Wait-Free 알고리즘

 

[ 이진 세마포어와 뮤텍스의 차이 ]

둘은 거의 비슷하지만, 이진 세마포어는 실행 순서의 제어도 가능하다.

 

[ 뮤텍스 vs. 세마포어]

- 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
- 세마포어는 소유 불가능하지만, 뮤택스는 소유가 가능하다.
- 동기화의 개수가 다르다.

 

[ 뮤텍스와 세마포어 모두 커널이 관리하기 때문에, Lock을 얻고 방출하는 과정에서 시스템 콜을 호출해야 합니다. 이 방법의 장단점이 있을까요? 단점을 해결할 수 있는 방법은 없을까요? ]

장점
- 운영체제 보호면에서 안정성이 높음
- 프로세스 간에도 사용 가능

단점
- 유저 모드 -> 커널 모드 전환 비용 발생
- 오버헤드 존재

해결 
- 커널에 진입하는 횟수 줄이기

 

[ volatile 키워드는 어떤 의미가 있나요? ]

volatile은 컴파일러에게 해당 변수의 값이 외부 요인에 의해 언제든 변경될 수 있음을 알리는 키워드이다.
따라서 최적화 대상에서 제외되며, 항상 메인 메모리에서 값을 읽고 쓰도록 강제한다.

컴파일러 최적화로 인해 변수 값이 캐싱되는 것을 방지하고, 항상 최신 값을 보장하고자 할 때 사용된다.

주로 아래 3가지 경우에 사용된다.
- MIMO(Memory-mapped I/O)
- 인터럽트 서비스 루틴(Interrupt Service Routine): 인터럽트에 의해 변경될 수 있는 변수를 메인 루프에서 참조할 때
- 멀티 스레드 환경: 두 스레드 이상이 하나의 변수를 읽고 쓸 때