[OS] 프로세스 동기화
Race Condition과 공유 데이터 문제, Critical Section 3가지 조건, Peterson's Solution, Bakery Algorithm, Test-and-Set, Swap 하드웨어 명령어
1. Background: 공유 데이터와 Race Condition
- 공유 데이터 문제: 읽기만 할 경우 문제없으나, 쓰기 작업 시 데이터 일관성 훼손 가능
- Producer-Consumer 예시:
count변수: 현재 버퍼에 채워진 데이터 개수를 추적Producer: 버퍼에 데이터 삽입 후
count++
Producer: 버퍼에 데이터 삽입 후 count++Consumer: 버퍼에서 데이터 추출 후
count--
Consumer: 버퍼에서 데이터 추출 후 count–in포인터: 다음 쓰기 위치,out포인터: 다음 읽기 위치, 순환 버퍼 구조(% buffer_size)
- 어셈블리 수준 분해:
count++→register1 = count/register1++/count = register1count--→register2 = count/register2--/count = register2- 두 명령어 시퀀스가 인터리빙되면 초기값 5 기준으로 결과가 4 또는 6으로 달라짐
- Race Condition: 마지막으로 실행된 명령어에 따라 공유 변수 값이 결정되는 비결정적 상황
- 원인: CPU가 하나여도 인터럽트 발생 시 컨텍스트 스위치로 다른 프로세스가 동일 공유 변수에 접근 가능
2. Critical Section 문제와 해결 조건 3가지
Critical Section의 전체 구조: Entry Section → Critical Section → Exit Section → Remainder Section
Critical Section 진입/퇴출 코드 구조
- 크리티컬 섹션: 공유 변수(전역 데이터)를 변경하는 코드 구간, 어느 한 순간에 오직 하나의 프로세스만 진입 가능해야 함
- Entry Section: 크리티컬 섹션 진입 허가를 요청하는 구간
- Exit Section: 크리티컬 섹션 퇴출 후 다른 프로세스에게 진입 기회를 부여하는 구간
- 해결 조건 3가지:
- Mutual Exclusion(상호 배제): 동일 크리티컬 섹션에 동시에 둘 이상의 프로세스 진입 불가 → Entry Section에서 보장
- Progress(진행): 크리티컬 섹션이 비어 있고 진입을 원하는 프로세스가 있을 때, 다음 진입자 선정이 무한정 지연되어서는 안 됨 → Exit Section에서 보장
- Bounded Waiting(한정 대기): 특정 프로세스가 진입 요청 후 다른 프로세스들이 크리티컬 섹션에 진입하는 횟수에 상한이 존재해야 함 (n개 프로세스 경합 시 n번 안에 반드시 자기 차례가 돌아와야 함)
- 서로 다른 공유 변수에 대한 크리티컬 섹션은 동시에 접근해도 무방, 동일 변수에 대한 크리티컬 섹션만 상호 배제 필요
3. Peterson’s Solution
피터슨의 솔루션은 두 개의 프로세스(Pi, Pj) 에만 적용 가능한 소프트웨어 기반 동기화 알고리즘이다. 두 개의 공유 변수 turn(순서)과 flag[](의도 표시)를 사용하며, 세 가지 조건을 모두 만족한다.
- 사용 변수:
turn: 현재 크리티컬 섹션 진입 순서 (i 또는 j 중 하나만 가능)flag[i],flag[j]: 해당 프로세스가 크리티컬 섹션에 진입하고자 하는 의도 표시 (true/false)
알고리즘 동작(Pi 기준):
Peterson’s Solution: flag와 turn을 이용한 두 프로세스 동기화flag[i] = true→ 진입 의도 표시turn = j→ 순서를 상대방에게 양보while (flag[j] == true && turn == j)→ 상대방이 진입 의도가 있고 순서도 상대방이면 대기- 크리티컬 섹션 진입 및 작업 수행
- Exit Section:
flag[i] = false→ 진입 의도 해제, 상대방의 while 조건 해제
- 조건 만족 여부:
- Mutual Exclusion:
turn값은 i 또는 j 중 하나만 가능 → 동시 진입 불가 ✔️ - Progress: 퇴출 시
flag[i] = false로 상대방 while 조건 해제 → 다음 진입자 선정 ✔️ - Bounded Waiting: 프로세스가 2개이므로 상대방이 나오면 반드시 자기 차례 ✔️
- Mutual Exclusion:
- 한계: 프로세스가 3개 이상인 경우 적용 불가
4. Bakery Algorithm (베이커리 알고리즘)
베이커리 알고리즘은 n개의 프로세스에 적용 가능한 소프트웨어 동기화 알고리즘으로, 빵집에서 번호표를 뽑아 순서대로 서비스받는 방식에서 착안하였다. 번호표 값이 작을수록 먼저 크리티컬 섹션에 진입한다.
- 사용 변수:
choosing[i]: 프로세스 i가 번호표를 발급받는 중임을 표시 (true/false), 초기값 falsenumber[i]: 프로세스 i의 번호표 값, 초기값 0 (0은 경합 비참여 또는 이미 완료 의미)
- 번호표 발급:
number[i] = max(number[0], ..., number[n-1]) + 1→ 현재 발급된 번호표 중 최댓값 + 1 - 동일 번호표 처리: 번호표 값이 같을 경우 프로세스 ID(PID)가 작은 프로세스 우선
알고리즘 동작(Pi 기준):
Bakery Algorithm: 번호표 기반 n개 프로세스 동기화choosing[i] = true→ 번호표 발급 시작number[i] = max(...) + 1→ 번호표 발급choosing[i] = false→ 발급 완료- 모든 j에 대해:
while choosing[j]→ 다른 프로세스가 번호표 발급 중이면 대기 while number[j] != 0 && (number[j], j) < (number[i], i)→ 번호표가 더 작은 프로세스가 있으면 대기- 크리티컬 섹션 진입
- Exit Section:
number[i] = 0→ 번호표 반납 (경합 제외)
- 조건 만족 여부:
- Mutual Exclusion: 번호표 비교로 가장 작은 값의 프로세스만 진입 ✔️
- Progress: 퇴출 시
number[i] = 0으로 해당 프로세스 제외, 나머지 경합 지속 ✔️ - Bounded Waiting: 처음 n개 프로세스 기준으로 n번 안에 자기 차례 보장, 재진입 시 더 큰 번호표 발급되어 후순위로 밀림 ✔️
5. 동기화 하드웨어: Atomic Instructions
소프트웨어 솔루션의 한계를 극복하기 위해 하드웨어 수준에서 Atomic(원자적) 명령어를 제공한다. Atomic 명령어는 실행 도중 인터럽트가 발생하지 않는(Non-interruptible, Non-preemptive) 명령어로, CPU가 여러 개인 환경에서도 효율적으로 동기화를 구현할 수 있다. 대표적인 두 가지 명령어는 Test-and-Set과 Swap이다.
5-1. CPU 단일 환경에서의 인터럽트 비활성화 방식
- 크리티컬 섹션 진입 전 인터럽트 비활성화(
disable interrupts) → 작업 완료 후 재활성화(enable interrupts) - CPU가 하나일 때는 유효하나, 멀티프로세서 환경에서는 비효율적이고 확장성 문제 발생
- 모든 CPU가 껐다 켰다를 반복하면 오버헤드 급증
5-2. Test-and-Set 명령어
Test-and-Set 명령어: 현재 값을 반환하고 true로 설정하는 원자적 연산
- 동작: 타겟 변수의 현재 값(옛날 값)을 반환하고, 타겟 변수를 무조건
true로 설정 Entry Section 구현:
Test-and-Set을 이용한 Critical Section 진입 구현- 공유 변수
lock초기값:false while (test_and_set(&lock))→ lock이 false일 때만 while 탈출 → 크리티컬 섹션 진입- Exit Section:
lock = false로 복원
- 공유 변수
- 조건 만족 여부:
- Mutual Exclusion ✔️, Progress ✔️
- Bounded Waiting ❌: 먼저 나온 프로세스가 재진입 시 재수 좋으면 다시 선택될 수 있어 특정 프로세스가 무한정 대기 가능
- Bakery Algorithm의
number[i] = max(...) + 1와 같이 먼저 나온 프로세스가 재진입할 때 현재 대기열에 있는 프로세스보다 더 큰 번호를 부여받는다는 보장이 없다.
- Bakery Algorithm의
5-3. Swap 명령어
Swap 명령어: 두 변수의 값을 원자적으로 교환
- 동작: 두 변수의 값을 원자적으로 교환 (
temp = a; a = b; b = temp) Entry Section 구현:
Swap을 이용한 Critical Section 진입 구현- 공유 변수
lock초기값:false, 로컬 변수key = true do { swap(lock, key) } while (key == true)→ lock이 false일 때 swap 후 key가 false가 되어 while 탈출- Exit Section:
lock = false로 복원
- 공유 변수
- 조건 만족 여부:
- Mutual Exclusion ✔️, Progress ✔️
- Bounded Waiting ❌: Test-and-Set과 동일한 이유로 한정 대기 미보장
6. 세마포어(Semaphore) 개념 및 연산
세마포어는 busy waiting 없이 동기화를 구현할 수 있는 도구로 정의된다. 정수형 변수 S에 대해 wait(S)와 signal(S) 두 가지 원자적(atomic/indivisible) 연산만을 허용하며, 이 연산들은 시작되면 방해받지 않고 완료된다. 세마포어는 카운팅 세마포어(값 제한 없음)와 바이너리 세마포어(0 또는 1, 뮤텍스 락이라고도 함) 두 종류로 구분된다.
- Busy Waiting 정의:
while (S <= 0) do no-operation형태로, 조건이 충족될 때까지 루프를 반복하며 CPU를 점유하는 방식이다. wait(S)연산: S 값이 0 이하이면 루프에서 대기(busy waiting); S > 0이면 S를 1 감소시키고 크리티컬 섹션 진입을 허용한다.signal(S)연산: 조건 없이 S 값을 1 증가시킨다.- 카운팅 세마포어: 정수 값이 제한 없이 증감 가능하며, 바이너리 세마포어 여러 개로 구현 가능하다.
- 바이너리 세마포어(뮤텍스 락): 값이 0 또는 1만 가능하며, Mutual Exclusion의 앞 글자를 따 “뮤텍스”라 부른다. 구현이 간단하다.
- 상호 배제 구현: 세마포어 초기값을 1로 설정하고, 엔트리 섹션에
wait(S), 엑시트 섹션에signal(S)를 배치하여 구현한다. - 순서화(Ordering) 예시: P1의 S1 이후 P2의 S2가 실행되도록 강제하려면, S2 앞에
wait(S)(초기값 0)를 두고 S1 실행 후signal(S)를 호출한다.
7. 세마포어 구현: Busy Waiting vs. 블록/웨이크업
Busy waiting 방식은 코드가 단순하고 크리티컬 섹션 진입 빈도가 낮을 때 유리하지만, 대기 시간이 길거나 크리티컬 섹션 내 작업량이 많을 경우 비효율적이다. 이를 해결하기 위해 각 세마포어가 자신만의 대기 큐(waiting queue)를 보유하고, block()과 wakeup() 연산을 활용하는 방식이 도입된다.
- 스핀락(Spin Lock): 락 획득을 위해 프로세스가 루프를 돌며 대기하는 busy waiting 방식; 대기 시간이 짧을 때 적합하다.
- 블록/웨이크업 방식: 대기 시간이 길 경우 프로세스를 블록시켜 대기 큐에 삽입하고, 조건 충족 시
wakeup()으로 레디 큐로 이동시킨다. - 세마포어 구조: 각 세마포어는 정수 값(value)과 다음 대기 프로세스를 가리키는 포인터(list)로 구성된 대기 큐를 보유한다.
- 블록/웨이크업 방식의
wait(S)구현: S 값을 먼저 1 감소시키고, 감소 후 값이 0 미만이면 해당 프로세스를 대기 큐에 삽입 후 블록한다. - 블록/웨이크업 방식의
signal(S)구현: S 값을 1 증가시키고, 증가 후 값이 0 이하이면 대기 큐에서 프로세스 하나를 꺼내wakeup()으로 레디 큐에 삽입한다. - 실행 시나리오 예시(P1→P2→P3→P4 순 wait 실행):
- P1: S=1→0, 크리티컬 섹션 진입
- P2: S=0→-1, 대기 큐 삽입 및 블록
- P3: S=-1→-2, 대기 큐 삽입 및 블록
- P1 signal: S=-2→-1, P2 웨이크업 → 레디 큐 이동
- P4 wait: S=-1→-2, 대기 큐 삽입
- P2 signal: S=-2→-1, P3 웨이크업 → 순차 진행
8. 데드락(Deadlock)과 기아(Starvation)
- 데드락 정의: 두 개 이상의 프로세스가 서로 상대방이 해제해야 하는 조건을 기다리며 무한 대기하는 상태.
- 예시(세마포어 S, Q, 초기값 각 1): P0가
wait(S)후wait(Q)시도, P1이wait(Q)후wait(S)시도 시 — S=0, Q=0이 되어 양쪽 모두 진행 불가. - 식사하는 철학자 비유: 두 사람이 포크와 나이프를 하나씩 나눠 갖고 서로 양보하지 않으면 둘 다 식사를 못 하는 상황과 동일하다.
- 기아(Starvation): 세마포어 대기 큐에서 특정 프로세스가 계속 배제되어 CPU를 할당받지 못하는 상태; 데드락의 심화 형태이다.
9. 고전적 동기화 문제: 유한 버퍼(Bounded Buffer) 문제
생산자-소비자 문제(Bounded Buffer Problem)는 크기 n인 공유 버퍼를 생산자(Producer)와 소비자(Consumer) 프로세스가 동시에 접근할 때 발생하는 동기화 문제이다. 세 개의 세마포어(mutex, full, empty)를 활용하여 상호 배제와 버퍼 상태 관리를 동시에 구현한다.
- 세마포어 구성:
mutex(초기값 1): 버퍼(크리티컬 섹션)에 대한 상호 배제 보장full(초기값 0): 데이터가 채워진 버퍼 공간의 수empty(초기값 n): 비어 있는 버퍼 공간의 수
- 생산자 프로세스 흐름:
- 아이템 생성
wait(empty)— 빈 공간 존재 여부 확인; 없으면 대기wait(mutex)— 크리티컬 섹션 진입- 버퍼에 아이템 삽입
signal(mutex)— 크리티컬 섹션 해제signal(full)— 채워진 공간 수 증가
- 소비자 프로세스 흐름:
wait(full)— 소비할 아이템 존재 여부 확인; 없으면 대기wait(mutex)— 크리티컬 섹션 진입- 버퍼에서 아이템 제거
signal(mutex)— 크리티컬 섹션 해제signal(empty)— 빈 공간 수 증가- 아이템 소비
- 시나리오 예시(버퍼 크기 3, 생산자 4회 → 소비자 4회):
- 생산자 3회 실행 후 버퍼 만석(empty=0); 4번째 생산자는
wait(empty)에서 블록 - 소비자 1회 실행 시 full 감소, empty 증가 → 블록된 생산자 진행 가능
- 소비자가 계속 실행되어 full=0이 되면 다음 소비자는
wait(full)에서 블록
- 생산자 3회 실행 후 버퍼 만석(empty=0); 4번째 생산자는
10. 운영체제별 동기화 기법 사례 연구
- Solaris:
- 어댑티브 뮤텍스(Adaptive Mutex): 크리티컬 섹션이 짧고 해당 프로세스가 실행 중(run 상태)이면 스핀(busy waiting); 그렇지 않으면 블록 후 대기 큐 삽입
- 단일 프로세서 환경에서는 슬립(sleep/block) 방식 선호
- 크리티컬 섹션이 긴 경우 조건 변수(Condition Variable) 활용
- 리더-라이터 락(Reader-Writer Lock): 읽기 락은 다수 허용, 쓰기 락은 단독 허용
- 턴스타일(Turnstile): 락 대기 스레드를 순서화하는 큐 자료구조; 회전문처럼 한 번에 하나의 프로세스만 통과
- Windows XP:
- 단일 CPU: 인터럽트 마스킹(interrupt masking)으로 공유 변수 보호
- 다중 CPU: 스핀락(busy waiting) 제공
- 디스패처 오브젝트(Dispatcher Object): 뮤텍스·세마포어처럼 동작하며, 이벤트(Event) 객체는 조건 변수(Condition Variable)와 유사하게 동작
- Linux:
- 크리티컬 섹션이 짧은 경우: 인터럽트 비활성화(disable interrupt)
- 세마포어 제공
- 다중 프로세서: 스핀락(busy waiting)
- 단일 프로세서: 커널 선점(Kernel Preemption) 비활성화(non-preemptible, non-interruptible)
- Pthreads(POSIX, Apple/iOS 포함):
- OS 독립적 API
- 기본 제공: 뮤텍스 락, 조건 변수
- 확장 버전: 리더-라이터 락, 스핀락(busy waiting) 추가 제공