[OS] 프로세스 동기화

1. Background: 공유 데이터와 Race Condition

• 공유 데이터 문제: 읽기만 할 경우 문제없으나, 쓰기 작업 시 데이터 일관성 훼손 가능
• Producer-Consumer 예시:
  • count 변수: 현재 버퍼에 채워진 데이터 개수를 추적

  • Producer: 버퍼에 데이터 삽입 후 count++

    Producer: 버퍼에 데이터 삽입 후 count++

  • Consumer: 버퍼에서 데이터 추출 후 count--

    Consumer: 버퍼에서 데이터 추출 후 count–

  • in 포인터: 다음 쓰기 위치, out 포인터: 다음 읽기 위치, 순환 버퍼 구조(% buffer_size)
• 어셈블리 수준 분해:
  • count++ → register1 = count / register1++ / count = register1
  • count-- → 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가지:
  1. Mutual Exclusion(상호 배제): 동일 크리티컬 섹션에 동시에 둘 이상의 프로세스 진입 불가 → Entry Section에서 보장
  2. Progress(진행): 크리티컬 섹션이 비어 있고 진입을 원하는 프로세스가 있을 때, 다음 진입자 선정이 무한정 지연되어서는 안 됨 → Exit Section에서 보장
  3. 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을 이용한 두 프로세스 동기화

  1. flag[i] = true → 진입 의도 표시
  2. turn = j → 순서를 상대방에게 양보
  3. while (flag[j] == true && turn == j) → 상대방이 진입 의도가 있고 순서도 상대방이면 대기
  4. 크리티컬 섹션 진입 및 작업 수행
  5. Exit Section: flag[i] = false → 진입 의도 해제, 상대방의 while 조건 해제
• 조건 만족 여부:
  • Mutual Exclusion: turn 값은 i 또는 j 중 하나만 가능 → 동시 진입 불가 ✔️
  • Progress: 퇴출 시 flag[i] = false로 상대방 while 조건 해제 → 다음 진입자 선정 ✔️
  • Bounded Waiting: 프로세스가 2개이므로 상대방이 나오면 반드시 자기 차례 ✔️
• 한계: 프로세스가 3개 이상인 경우 적용 불가

---

4. Bakery Algorithm (베이커리 알고리즘)

베이커리 알고리즘은 n개의 프로세스에 적용 가능한 소프트웨어 동기화 알고리즘으로, 빵집에서 번호표를 뽑아 순서대로 서비스받는 방식에서 착안하였다. 번호표 값이 작을수록 먼저 크리티컬 섹션에 진입한다.

• 사용 변수:
  • choosing[i]: 프로세스 i가 번호표를 발급받는 중임을 표시 (true/false), 초기값 false
  • number[i]: 프로세스 i의 번호표 값, 초기값 0 (0은 경합 비참여 또는 이미 완료 의미)
• 번호표 발급: number[i] = max(number[0], ..., number[n-1]) + 1 → 현재 발급된 번호표 중 최댓값 + 1
• 동일 번호표 처리: 번호표 값이 같을 경우 프로세스 ID(PID)가 작은 프로세스 우선

• 알고리즘 동작(Pi 기준):

  Bakery Algorithm: 번호표 기반 n개 프로세스 동기화

  1. choosing[i] = true → 번호표 발급 시작
  2. number[i] = max(...) + 1 → 번호표 발급
  3. choosing[i] = false → 발급 완료
  4. 모든 j에 대해: while choosing[j] → 다른 프로세스가 번호표 발급 중이면 대기
  5. while number[j] != 0 && (number[j], j) < (number[i], i) → 번호표가 더 작은 프로세스가 있으면 대기
  6. 크리티컬 섹션 진입
  7. 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 와 같이 먼저 나온 프로세스가 재진입할 때 현재 대기열에 있는 프로세스보다 더 큰 번호를 부여받는다는 보장이 없다.

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과 동일한 이유로 한정 대기 미보장