[운영체제] ch06. Process Synchronization

📄 OS에서의 Race Condition (1/3)

 
슬라이드는 운영체제에서 매우 중요한 개념인 Race Condition (경쟁 조건),
그 중에서도 커널 모드에서 interrupt가 발생했을 때의 위험성을 설명하고 있어.
"Interrupt handler vs. kernel" 상황을 시각화한 그림과 함께, 실습처럼 레지스터 값을 따라가며 설명하는 구조야.
 

interrupt handler vs. kernel

---

🧠 핵심 개념 요약

Race Condition:
둘 이상의 프로세스(또는 interrupt)가 **공유 자원(예: count 변수)**에 동시 접근하면서
의도하지 않은 결과가 발생하는 문제.

---

🔁 발생 상황 시나리오

• count++ 수행 시 내부적으로 다음 순서로 처리됨:
  1. load count → 레지스터 R1 ← count (예: 10)
  2. inc R1 → R1 ← 11
  3. store R1 → count

---

🚨 위험 상황

1. 사용자가 count++ 실행 중 (Kernel mode에서 실행 중)
2. 이 때 인터럽트 발생
3. → 인터럽트 핸들러도 같은 count++ 수행
4. 두 곳 모두 같은 count 주소 참조 (공유 변수)
   → 값이 꼬임 (Race 발생)

---

📌 문제의 핵심

• 10 → 11로 올라가야 하는데,
  둘 다 load 시점에서 10을 읽음 → 둘 다 11로 만들고 저장
  → 결과적으로 두 번 증가해야 할 값이 한 번만 증가됨

---

✍️ 슬라이드 필기 정리

• “둘 다 10에서 시작해서 11로 저장함 → 하나만 반영됨”
• “CPU에 저장된 register 값 복구됨 → 이전 값이 덮어써짐”
• “커널 모드 중 인터럽트 걸리면 위험”
• “context switch 발생 → count 값 유실 가능”
• “kernel 모드 실행 중 disable interrupt 필요”
• 아래쪽 설명: if you preempt CPU while in kernel mode … → 문제 발생 조건 요약

---

✅ 암기 포인트

• Race Condition은 공유 자원과 비동기 접근이 동시에 일어날 때 발생
• 특히 **count++, count--**는 내부적으로 3단계 → 중간에 끼어들면 문제 발생
• 해결 방법:
  • Interrupt disable/enable로 보호
  • Lock, Mutex, Semaphore로 동기화
• 커널 모드 중 preemption/interruption 금지가 핵심

---

✍️ 정리 문장

"Kernel 모드에서 공유 변수 접근 중 interrupt가 발생하면
Interrupt handler도 동일 자원을 수정하게 되어 race condition이 발생한다."

---

이건 Race Condition의 구조적 발생 이유와 방지 방법을 설명하는 가장 전형적인 슬라이드야.
 
 
 
 

📄 If you preempt CPU while in kernel mode …

이번 슬라이드는 앞선 내용과 연관된 Race Condition의 실질적인 예시 상황을 다루고 있어.
특히, "커널 모드 중 preemption(선점)이 발생할 경우" 어떤 일이 생기는지를 시각적으로 설명하고 있어.
📌 슬라이드에 그려진 타임라인, 시스템 콜 흐름, count 값 변화, 그리고 빨간 필기까지 포함해서 정리할게!

---

📄 If you preempt CPU while in kernel mode …

---

🧠 배경 설명

**커널 모드(kernel mode)**는 운영체제의 핵심 기능이 실행되는 특수 권한 모드야.
만약 이 상태에서 다른 프로세스가 **CPU를 선점(preempt)**한다면…
➝ Race Condition이 발생할 수 있음 ⚠️

---

🧵 시나리오 요약

(1) 프로세스 A (Pₐ)

• 사용자 모드 → 시스템 콜 read() 호출 → 커널 모드 진입
• 커널에서 count++ 수행 중이었음 (아직 완료되지 않음!)

(2) 타임퀀텀 종료 & 프로세스 B (P_b)가 CPU 요구

• Pₐ는 커널 모드 상태에서 preempt 당함
• P_b가 커널에 진입해 count 변수 사용
• P_b가 count 수정한 뒤 → 다시 Pₐ 복귀 → Pₐ가 이전 register 값으로 count 덮어씀!

→ 🔥 결국 count = 10 → 9 → 11로 오염됨 (올바른 값 아님)

---

📌 슬라이드 필기 요약

• “count값이 10→9→11 이상하게 바뀜”
• “CPU 되돌려 받음 → 이전 값으로 덮어쓰기”
• “INC/STORE ↔ LOAD/DEC/STORE 사이클 충돌”
• "해결책이 아닌 '회피책' = 커널 모드에서는 preempt하지 않도록"

---

✅ 해결/회피 방안

구분설명

🔒 해결책	Critical Section 보호 (예: Mutex, Semaphore, Spinlock 등)
⚠️ 회피책	커널 모드에서는 CPU를 preempt하지 않음
🧠 실제 적용	Linux는 preempt 가능하되 **preempt_disable/enable()**로 구간 보호

---

핵심 문장 정리

“커널 모드에서 count를 수정하는 중간에 preempt가 발생하면,
이전 값이 덮어씌워져 Race Condition이 발생할 수 있다.
따라서 커널 모드에서는 preemption을 막거나, 동기화를 통해 보호해야 한다.”

---

💡 시험 대비 팁

• count++를 내부적으로는 load → inc → store 형태로 처리함을 반드시 기억!
• 사용자 모드 <-> 커널 모드 전환 시 interrupt/preempt가 발생하면 Race 발생 가능
• 해결책 구체적으로 제시할 수 있어야 함 (preempt 막기, lock 사용 등)

---

이 슬라이드는 운영체제의 실제 context switching과 interrupt/preemption 타이밍이 얼마나 위험할 수 있는지를 설명하는 핵심 예시야.
 
 
 
 

📄 OS에서의 Race Condition (2/3)

🧩 Preempt a process running in kernel?

---

🧠 핵심 개념

Race Condition이 발생하는 건 단순히 preemption 때문이 아니라,
"**공유 자원(Shared Data)**을 동시에 접근하면서도 Critical Section이 보호되지 않은 경우"에만 해당돼.

---

🧵 시나리오 요약

✦ 프로세스 Pₐ

• 사용자 모드 → 커널 모드 진입
• 커널에서 공유 자원(count++) 수행 중

✦ 그 순간, 프로세스 P_b가 system call 요청

• CPU를 선점받아 커널 진입
• 역시 공유 자원(count--) 수행
• 두 커널 모드가 동시에 커널 주소 공간을 공유
  → 이때 Race Condition 발생 위험 있음

---

📌 필기 내용 정리

• "여기서 c.s(Critical Section) 일어날 때 문제"
• "PA는 count++, PB는 count-- 중 → 둘 다 count 접근"
• "여기서는 context switch 일어나도 문제 X"
  → → user mode 중에는 address space가 분리되어 있어 문제 없음

---

⭐ 핵심 요점 비교

상황설명Race Condition 발생 여부

PA 커널 모드 중 preempt 됨	count++ 중간에 끼어들면 → PB가 count 수정	✅ 발생 위험
PA user mode일 때 preempt	각자 다른 address space → 공유 없음	❌ 없음

---

📌 슬라이드 하단 설명 정리

• * 사용자 address space는 공유되지 않음
• ** 하지만 system call 중에는 kernel address space를 공유하게 됨 (공유 자원 존재)
• *** → 그 상태에서 preempt가 발생하면 Race 발생 가능성 있음

---

✅ 암기 포인트

• Race Condition은 공유된 자원에 대해 비동기 접근이 있을 때 발생
• 커널 모드끼리는 주소 공간을 공유함 → 위험함
• user mode에서는 각자의 공간을 사용 → 안전함
• 해결법: critical section 보호 / 커널 모드 중 preempt 방지

---

✍️ 정리 문장

“커널 모드에서 system call 수행 중 preempt가 발생하면,
두 프로세스가 같은 커널 자원(count 등)을 접근하여 Race Condition이 발생할 수 있다.
반면 user mode에서는 주소 공간이 분리되어 있으므로 안전하다.”

 
 
 

📄 OS에서의 Race Condition (3/3)

🔁 Multiprocessor 환경에서의 경쟁 조건

---

📌 핵심 개념

Multiprocessor 시스템에서는 여러 CPU가 동시에 **공유 메모리(예: count 변수)**에 접근할 수 있음.
→ 한 CPU가 count++ 중일 때, 다른 CPU가 동시에 count--를 수행하면 Race Condition 발생.

---

🧵 상황 흐름 요약

CPU ①

• count++ 수행 중
• 내부 동작: LOAD(10) → INC(11) → STORE(11)

동시에 CPU ②

• count-- 수행
• 내부 동작: LOAD(10) → DEC(9) → STORE(9)

🧨 결과: 둘 다 동일한 초기 값 10을 읽고, 각각 덮어쓰기 → 결과가 꼬임

---

💥 문제 핵심

❗ 어떤 CPU가 마지막에 STORE를 했는가에 따라 count 결과가 달라짐
→ interrupt disable/enable만으로 해결 불가
(왜냐하면 CPU마다 별도 interrupt controller가 있음)

---

✍ 슬라이드 필기 요약

• “어떤 CPU가 마지막으로 store 했는가 → Race 발생 원인”
• “Multiprocessor는 interrupt 제어만으로는 해결 불가능”
• 방법 ①: “1개만 커널 진입 허용 → 비효율적”
• 방법 ②: “공유 데이터마다 lock/unlock 적용 → 정석적 해결”

---

🔐 해결 방법 2가지

해결 방법설명단점

방법 ①	한번에 1개의 CPU만 커널 진입 허용	커널 접근 속도 느림, 병렬성 저하
방법 ②	공유 자원에 대해 lock/unlock 사용	lock 설계 잘못하면 deadlock, starvation 가능

→ ✍ 필기: “lock 자체가 문제성 O”

---

💡 정리 문장

“Multiprocessor 환경에서는 공유 자원에 대한 동기화 없이 여러 CPU가 접근할 경우
Race Condition이 발생할 수 있으며, 이를 해결하기 위해서는 lock/unlock을 통한 보호가 필수적이다.”

---

✅ 암기 포인트

• count++, count--는 atomic operation이 아님!
• Multiprocessor 환경에서는 disable interrupt로는 보호 불가
• 반드시 lock 또는 atomic 연산 지원 기법 필요 (e.g., test-and-set, compare-and-swap 등)
• 실습/이론/코드 구현 전부에서 나올 수 있는 주제

---

이 슬라이드는 동기화의 필요성, 특히 Multiprocessor 환경에서의 구조적 Race Condition을 시각적으로 설명하는 마무리 장면이야.
"동시 접근 + 미보호 → 꼬임 발생" 공식처럼 외워둬도 좋아!
 
 

📄 Example of a Race Condition

(공유 자원에 대한 비동기 접근 문제)

---

🧠 핵심 개념

여러 프로세스가 동시에 하나의 공유 변수 X에 접근해서 값을 수정하는데,
작업 순서에 따라 결과가 달라지는 상황이 바로 Race Condition!

---

📌 슬라이드 구성

🧱 공유 변수

• X = 2 (초기값)

🔁 연산 목적

• P1: X = X + 1 → 기대값: 3
• P2: X = X - 1 → 기대값: 1

🧮 내부 연산 (P1 / P2)

Process내부 연산 (명령어 시퀀스)

P1	load X → reg1 inc reg1 store reg1 → X
P2	load X → reg2 dec reg2 store reg2 → X

---

💥 Race 발생 상황 예시

1. P1이 X=2를 reg1에 로드하고 아직 store 안 한 상태
2. 그 사이에 타이머 인터럽트(context switch) 발생 → P2가 CPU 점유
3. P2는 X를 읽고 감소 → X=1 저장
4. 다시 P1 복귀 → X=3 저장

🔻 결과: X = 2 → 1 → 3
→ P2의 변경 내용(1)이 사라짐 = Race Condition 발생

---

✍ 슬라이드 필기 요약

• “사용자 프로세스 P1 수행 중 timer interrupt가 발생하여 P2가 CPU를 얻게 되면?”
  → Critical Section 보호 없으면 P2의 작업이 무시될 수 있음

---

✅ 핵심 정리

항목내용

발생 조건	공유 자원(X)을 동시에 수정하는 두 프로세스가 있음
문제 원인	연산 단위(load–inc–store)가 **원자적(atomic)**이지 않음
해결 필요	연산 전체를 하나의 Critical Section으로 묶어야 함

---

🧩 해결 방안 요약

• Lock 사용: lock(X) → 연산 → unlock(X)
• Atomic 연산 도입: Test-and-set, Compare-and-swap 등
• 커널 레벨 보호: preempt disable, spinlock 등 사용

---

💡 암기용 문장

"Race Condition은 여러 프로세스가 공유 자원에 대해 비동기적으로 접근할 때 발생하며,
이를 방지하기 위해서는 연산을 Atomic하게 만들거나 Lock으로 보호해야 한다."

---

이 슬라이드는 Race Condition의 가장 기초적이고 자주 출제되는 형태이므로,
연산 단위 / context switch 시점 / 결과 꼬임 이유를 정확히 설명할 수 있어야 해!
 
 

📄 Algorithm 1 – Mutual Exclusion using turn only

🔑 핵심 아이디어

하나의 공유 변수 turn을 통해 둘 중 하나만 CS에 들어가도록 제어한다.

---

📌 사용 변수

c

코드 복사

int turn = 0;

• turn == 0: 프로세스 P₀가 진입 가능
• turn == 1: 프로세스 P₁가 진입 가능
• 즉, 한 번에 하나의 프로세스만 허용되며, CS를 빠져나온 쪽이 턴을 넘겨줌

---

🧱 알고리즘 구조

🔹 프로세스 P₀

c

코드 복사

do { while (turn != 0); // 상대의 턴이면 기다림 // Critical Section turn = 1; // 상대에게 턴 넘김 // Remainder Section } while (1);

🔹 프로세스 P₁

c

코드 복사

do { while (turn != 1); // 내 턴 아니면 기다림 // Critical Section turn = 0; // 턴 넘김 // Remainder Section } while (1);

---

📝 필기 요약 정리

• while(turn != i) 조건은 내 턴이 될 때까지 **무한 대기(loop)**함
• 필기에서 강조한 것처럼:
  • 둘 다 CS에 들어가려고 해도, turn은 하나만 열어주므로 Mutual Exclusion은 OK
  • 하지만 상대가 Remainder Section에 머물러도 내 턴이 아니면 나는 무조건 기다림
    • 이게 바로 Progress 조건을 위반하는 것

---

🔍 조건 평가

조건만족 여부설명

Mutual Exclusion	✅ 만족	동시에 CS 진입 불가
Progress	❌ 불만족	둘 다 CS 원해도 turn이 안 바뀌면 무한 대기
Bounded Waiting	❌ 불만족	턴이 영원히 돌아오지 않을 수 있음

---

📌 핵심 필기 해석

• * 단순하게 swap-turn 방식
• * P₀, P₁ 둘 다 critical section 원하면 turn이 안 바뀌어 멈춤
• * "이건 mutual exclusion만 만족하고 나머지는 불만족"
• ➤ 그래서 이 구조를 기반으로 **Peterson's Algorithm (Algorithm 3)**가 등장한 거야

---

✅ 암기 포인트

• turn 변수만 사용 → 상호배제 OK
• 진입 의도 표현 X → 진행성 문제 발생
• ➤ 서로 배려 없이 기다리기만 하면 교착 가능
• Peterson 알고리즘에서 이걸 개선 (flag + turn)

 
 

📄 Algorithm 2 - Mutual Exclusion (2-Process)

두 프로세스가 동시에 **Critical Section(CS)**에 들어가지 않도록 상호배제(Mutual Exclusion)를 보장

---

📌 사용 변수

c

코드 복사

boolean flag[2]; // 각 프로세스의 의사 표현 (CS 들어가겠다고 신호)

• 초기 상태: flag[0] = flag[1] = false
• flag[i] = true → 프로세스 Pi는 CS 진입을 원함
• flag[j] = true → 상대 프로세스가 CS에 들어가려고 한다고 인식됨

---

🧱 알고리즘 구조 (P_i 관점)

c

코드 복사

do { flag[i] = true; // CS에 들어가겠다고 선언 while (flag[j]); // 상대가 CS에 들어가려는 중이면 대기 // Critical Section flag[i] = false; // 나가면서 flag 내림 // Remainder Section } while (1);

---

📎 슬라이드 필기 해석

• flag[i] = true: 나 들어갈게
• while (flag[j]): 상대방도 들어갈 거라면 기다려라
• ❗ 서로 동시에 flag[0] = true, flag[1] = true 하게 되면 → 둘 다 기다리며 무한 루프 가능성 존재
  (→ progress 보장 실패)

---

🔍 만족 조건 분석

조건만족 여부설명

Mutual Exclusion	✅ 만족	둘 다 동시에 CS 못 들어감
Progress	❌ 불만족	둘 다 flag = true 설정 후 대기하면 진입 못하고 멈춤
Bounded Waiting	❌ 불만족	한 쪽이 계속 CS 들어가면 다른 쪽은 무한 대기 가능

---

❗ 페트erson's Algorithm이 왜 필요한지 암시

• 이 알고리즘은 Mutual Exclusion은 지키지만,
  **진행성(Progress)**과 **공정성(Bounded Waiting)**은 보장하지 못함.
• 이 문제를 해결하기 위해 **Peterson’s Algorithm (Algorithm 3)**가 등장함

---

✅ 요약 문장

Algorithm 2는 서로 양보하지 않으면 무한히 기다릴 수 있다는 한계를 가지며,
진입 순서를 관리해주는 별도 변수(turn)가 없어 진행성이 보장되지 않는다.

---

💡 암기 포인트

• flag[i] = true: 나 들어가고 싶어!
• while (flag[j]): 상대가 원하면 기다려야 함
• 서로 동시에 진입 의사를 표시할 경우 교착 상태 발생 가능
• Mutual Exclusion은 지키지만, 나머지 조건은 불충분

 
 
 
 
 

🧠 Peterson’s Algorithm – Algorithm 3

🔑 핵심 개념

• 두 개의 프로세스(P₀, P₁) 사이에서 Mutual Exclusion, Progress, Bounded Waiting 조건을 모두 만족하도록 설계된 알고리즘.
• flag[i]: 나의 진입 의도를 나타냄
• turn: 마지막으로 진입을 양보한 쪽을 기억 (상대방에게 기회를 주기 위함)

---

📌 사용 변수

c

코드 복사

boolean flag[2] = {false, false}; // 처음에는 아무도 CS 원하지 않음 int turn; // 마지막으로 상대에게 턴을 넘긴 쪽

---

🧱 프로세스 Pi 코드

c

코드 복사

do { flag[i] = true; // CS 진입 의사 표현 turn = j; // 상대방에게 먼저 기회를 줌 while (flag[j] && turn == j); // 상대도 원하고, 상대 턴이면 기다림 // Critical Section ... flag[i] = false; // CS 종료 후 의사 철회 // Remainder Section ... } while (true);

💡 여기서 i는 자기 번호, j는 상대 프로세스 번호 (0 또는 1)

---

✅ 만족 조건

조건만족 여부설명

Mutual Exclusion	✅ 만족	동시에 두 프로세스가 CS에 진입 불가
Progress	✅ 만족	진입 안하는 프로세스는 간섭 못 함
Bounded Waiting	✅ 만족	상대방이 계속 진입하지 못하도록 방지

---

🔍 필기 요약 해석

• flag[i] & turn==j 이 조건이 두 프로세스가 동시에 들어가는 걸 막음
• turn은 양보하는 변수, 둘 다 진입 원하면 최근 양보한 프로세스는 대기
• flag는 내가 진입 의사를 표현했는지 나타냄
• 필기 중:
  • Busy Waiting은 있음 (while 조건 무한 확인)
  • mutex + progress + bounded waiting 다 만족
  • Peterson은 알고리즘 1과 2를 조합한 구조
  • jump table 이슈 해결됨 (대기 순서 보장됨)

---

💬 암기 포인트 요약

• flag[i] = true: 나는 들어가고 싶어!
• turn = j: 네가 먼저 들어가
• while(flag[j] && turn == j): 네가 원하면 먼저 들어가
• flag[i] = false: 나 CS 끝났어
• ⇒ 이 구조가 세 조건 다 만족시킴

---

🚨 주의

• 두 개의 프로세스만을 위한 알고리즘 (n개에 일반화하려면 Filter Algorithm, Bakery Algorithm 필요)