공유 데이터 (Shared Data)
| 정의 | 여러 프로세스(process) 또는 **스레드(thread)**가 동시에 접근할 수 있는 데이터. |
| 위치 | 메인 메모리(RAM) 안에 있는 전역 변수, 힙 영역 데이터, 커널 자원 등 혹은 파일, 데이터베이스, I/O 버퍼 같은 외부 저장장치도 공유 데이터가 될 수 있음. |
| 특징 | 동시에 여러 주체가 접근할 수 있기 때문에, 동기화(synchronization) 없이는 값이 손상될 수 있음. |
| 예시 | 은행 계좌 잔액
|
경쟁 조건 (Race Condition)
| 정의 | 여러 프로세스가 공유 데이터에 동시에 접근할 때 발생하며, 실행 순서에 따라 결과가 달라질 수 있는 상황. |
| 문제점 | 특정 실행 순서에서 공유 데이터가 손상될 수 있음. |
임계 구역 (Critical Section)
| 정의 | 공유 데이터에 접근하거나 수정하는 코드 영역으로, 경쟁 조건이 발생할 수 있음 |
| 해결 목표 | 프로세스가 데이터를 협력적으로 공유할 수 있도록 동기화 프로토콜을 설계하는 것 |
임계 구역 vs 공유데이터
- 공유 데이터는 자원(무엇)이고,
- 임계 구역은 그 자원을 사용하는 코드(어디서)임.
- 공유데이터 전체에 락을 걸면 너무 비효율적이라 꼭 필요한 코드 부분(임계 구역)만 보호하면 됨
임계 구역 문제 해결을 위한 3가지 요구사항
| 상호 배제 (Mutual Exclusion) | 동시에 하나의 프로세스만 임계 구역에 진입할 수 있어야 한다. |
| 진행 (Progress) | 임계 구역 진입 후보가 없는 프로세스는 진입 결정을 방해하지 않아야 한다. 즉, 어떤 프로세스가 다음에 진입할지 협력적으로 결정해야 한다 |
| 한정된 대기 (Bounded Waiting) | 한 프로세스가 임계 구역에 들어가기 위해 무한정 대기하지 않도록 보장해야 한다 |
소프트웨어적 해결책 - Peterson 알고리즘
- 두 프로세스 환경에서 상호 배제를 보장하는 고전적인 소프트웨어적 해결책.
- 단, 오직 2개의 프로세스에 대해서만 설계됨. (확장은 가능하지만 복잡해짐)
- 그러나 최신 CPU 아키텍처(명령 재정렬, 메모리 캐시 최적화 등)에서는 올바르게 동작하지 않을 수 있음.
기본 아이디어
- 두 프로세스가 **차례(turn)**와 **의도(flag)**를 공유해서 임계 구역 진입을 조율한다.
boolean flag[2]; // 프로세스 i가 임계 구역에 들어가고 싶으면 flag[i] = true
int turn; // 차례 (0 또는 1)
// 알고리즘 동작 (프로세스 i 관점)
flag[i] = true; // 나 임계 구역 들어가고 싶다
turn = j; // 상대방 차례로 넘긴다
while (flag[j] && turn == j) {
// 상대방이 원하고, 지금은 상대방 차례면 기다린다
}
// ---- 임계 구역 ----
... 공유 데이터 접근 ...
flag[i] = false; // 나 다 끝났다 (임계 구역 해제)
동작 원리
- 상호 배제 (Mutual Exclusion)
- 두 프로세스가 동시에 임계 구역에 들어갈 수 없음.
- flag와 turn 조합으로 둘 중 하나만 통과 가능.
- 진행 (Progress)
- 임계 구역에 아무도 없으면, 진입 의사가 있는 프로세스가 들어갈 수 있음.
- 한정된 대기 (Bounded Waiting)
- turn을 교대로 넘기므로 무한정 기다리는 상황(기아)이 발생하지 않음.
하드웨어적 지원
- 메모리 장벽 (Memory Barrier): CPU의 명령 실행 순서를 제어하여 일관성을 유지.
- 원자적 명령 (Atomic Instruction):
- test_and_set, compare_and_swap(CAS) 등
- 락을 구현하는 데 사용 가능.
- 원자적 변수 (Atomic Variable): 하드웨어 차원에서 원자성을 보장
동기화 도구
- 뮤텍스(Mutex) 락
- 이진 상태(locked/unlocked)를 가지며, 한 번에 하나의 프로세스만 임계 구역에 진입 가능.
- 프로세스는 진입 전 락을 획득하고, 종료 시 락을 해제해야 한다.
- 세마포어(Semaphore)
- 정수 값을 가지며 뮤텍스보다 일반적인 동기화 도구.
- binary semaphore는 뮤텍스와 유사하게 동작하지만, counting semaphore는 여러 자원을 제어할 수 있음.
- 모니터(Monitor)
- 고수준의 추상 데이터 타입.
- 공유 데이터와 그 조작 방법을 캡슐화하며, 조건 변수(Condition Variable)를 이용해 특정 조건이 만족될 때까지 대기하거나, 조건이 만족되면 다른 프로세스에 신호를 보낼 수 있음.
라이브니스(Liveness) 문제
- 임계 구역 문제 해결 과정에서 발생할 수 있는 추가 문제.
- 예시:
- 교착 상태(Deadlock): 두 프로세스가 서로 자원을 기다리며 무한 대기.
- 기아(Starvation): 특정 프로세스가 자원 할당을 계속 못 받아 실행되지 못하는 경우.
평가 관점
- 동기화 도구는 경합 정도(Contension Level)와 사용 환경에 따라 성능과 효율이 달라진다.
- 예: 경합이 심한 환경에서는 CAS 기반 스핀락(spinlock)이 비효율적일 수 있고, 대신 세마포어나 모니터가 더 적합하다.