Post

[OS] 세마포어(Semaphore)와 데드락(Deadlock) - 시험장용 완벽 정리

Posted Updated
By njngwn
13 min read
[OS] 세마포어(Semaphore)와 데드락(Deadlock) - 시험장용 완벽 정리

시험장에서 절대 안 틀리는 세마포어와 데드락의 정리! 이 두 개념만 제대로 알면 OS의 동기화 문제는 그냥 점수 자판기입니다.

1️⃣ 세마포어(Semaphore) 완벽 정리

🧠 용어를 쉬운 말로 번역하기

시험지에서 P나 down이 나오면 머릿속으로 이렇게 번역하세요.

down(S) = “확인하고 뺏기” (또는 기다리기)

  • “S가 0보다 커? 그럼 하나 가져가고 통과!”
  • “S가 0이야? 그럼 누가 채워줄 때까지 여기서 잠듦(Sleep).”

up(S) = “채워주고 깨우기”

  • “S를 하나 늘려준다.”
  • “혹시 자고 있는 애 있어? 야 일어나! 네 거 생겼어.”

🛠️ 문제 유형별 “초기값” 공식 (Init Rules)

세마포어 변수가 무엇을 위해 존재하는지만 파악하면 초기값은 정해져 있습니다.

1. 보디가드 (Mutex, Lock)

목적: “한 번에 한 명만 들어오게 하기”

초기값: 1

패턴: down으로 잠그고, 일하고, up으로 연다.

2. 신호등/바통 터치 (Synchronization)

목적: “A가 끝나야 B가 시작할 수 있음” (순서 정하기)

초기값: 0 (처음엔 빨간불)

패턴: 먼저 할 놈이 끝나면 up(초록불 켬), 기다리는 놈은 down(초록불 기다림).

3. 재고 관리 (Counting)

목적: “자리가 N개 있음” 또는 “물건이 0개 있음”

초기값: N (공간 크기) 또는 0 (물건 개수)

📝 코드 짜는 “3대 패턴” (이게 핵심!)

시험 문제는 99% 이 세 가지 패턴 중 하나, 혹은 이들의 조합입니다.

① 샌드위치 패턴 (Mutex)

가장 흔한 패턴입니다. 중요 코드를 mutex로 감쌉니다.

상황: 전역 변수 count를 여러 스레드가 건드린다.

1
2
3
4
5

down(mutex);   // 문 잠그기 (나만 들어갈래)
// --- [위험 구역] ---
count++;       // 지지고 볶고
// -------------------
up(mutex);     // 문 열기 (다음 사람~)

② 바통 터치 패턴 (Ordering)

순서를 강제할 때 씁니다.

상황: 엄마가 밥을 차려줘야(up) 아들이 밥을 먹는다(down).

엄마 (먼저 할 일):

1
2

밥_차리기();
up(spoon);  // "자, 숟가락(신호) 여기 있다!" (0 -> 1)

아들 (나중에 할 일):

1
2

down(spoon);  // "숟가락 올라왔나?" (0이면 대기, 1이면 식사)
밥_먹기();

③ 생산자-소비자 패턴 (Buffering)

샌드위치 안에 알맹이가 들어갑니다.

1
2
3
4
5
6
7
8
9
10

// 1. 재고 확인 (없으면 대기)
down(item);

// 2. 샌드위치 (잠그기)
down(mutex);
물건_꺼내기();
up(mutex);

// 3. 빈자리 알림
up(space);

💡 팁: mutex down은 항상 알맹이 작업 직전에 하세요! (재고 확인보다 먼저 잠그면 데드락 걸릴 위험이 큼)

⚡ 실전 문제 풀이 팁 (시험장용)

1. 변수 이름 먼저 봐라

  • mutex가 보인다? → “아, 이건 감싸는 용도(Lock)구나.” → down…up
  • empty/full이 보인다? → “아, 이건 생산자-소비자구나.” → down(내거)…up(남의거)
  • done, sync 같은 게 보인다? → “아, 이건 순서 맞추기(0 초기값)구나.”

2. down의 개수 = up의 개수

코드 전체에서 down을 한 횟수와 up을 한 횟수는 보통 균형이 맞아야 합니다. (내가 문을 잠갔으면 열어야 하고, 물건을 뺐으면 빈자리를 알려줘야 함)

3. 데드락(Deadlock) 함정 피하기

down이 연속으로 두 번 나올 때가 제일 위험합니다.

나쁜 예:

1
2
3

down(mutex);   // 1. 화장실 문부터 잠금 (열쇠 챙김)
down(item);    // 2. 근데 휴지가 없네? 기다리자... (잠든다)
// 결과: 열쇠를 주머니에 넣고 잠들어서, 휴지 채워줄 사람도 못 들어옴 -> 망함

좋은 예:

1
2

down(item);    // 1. 휴지 있나 확인 (없으면 밖에서 대기)
down(mutex);   // 2. 있으면 들어가서 문 잠금

국룰: mutex (보호막)는 가능한 가장 안쪽에서, 짧게 잡는 게 국룰입니다.

🎯 세마포어 한 줄 요약

“나한테 필요한 게 있는지 확인(down)하고, 일을 한 뒤에, 내가 만든 변화를 남에게 알린다(up).”

이 마음가짐으로 빈칸을 채우면 절대 틀리지 않습니다!

2️⃣ 데드락(Deadlock) 완벽 정리

🔒 데드락이란?

교착 상태(Deadlock): 두 개 이상의 프로세스가 서로가 가진 자원을 기다리면서 영원히 진행하지 못하는 상태입니다.

🚨 데드락이 발생하는 4가지 조건 (Coffman Conditions)

데드락이 발생하려면 4가지 조건이 동시에 성립해야 합니다. 이 중 하나라도 깨지면 데드락은 발생하지 않습니다.

철학자 식사 문제(젓가락)를 예시로 설명합니다.

1. 상호 배제 (Mutual Exclusion)

독일어: Wechselseitiger Ausschluss

의미: 자원은 한 번에 한 프로세스만 사용할 수 있다.

예시: 젓가락은 한 명이 쥐면 다른 사람은 못 씁니다. 공유 불가능한 자원이어야 합니다.

2. 점유 대기 (Hold and Wait)

독일어: Besitzen und Warten (oder Belegung und Anforderung)

의미: 자원을 최소한 하나 보유(Hold)한 상태에서, 다른 프로세스가 가진 자원을 기다리는(Wait) 상태여야 한다.

예시: “왼쪽 젓가락은 손에 꽉 쥐고(Hold), 오른쪽 젓가락이 나올 때까지 기다리는(Wait)” 상황입니다.

💡 핵심: 페트리 넷 방식(두 젓가락을 동시에 가져감)처럼 필요한 자원을 모두 한 번에 획득하도록 하면 이 조건이 깨집니다!

3. 비선점 (No Preemption)

독일어: Nicht-Entzug (oder Ununterbrechbarkeit)

의미: 다른 프로세스가 가진 자원을 강제로 빼앗을 수 없다. 자원을 가진 쪽이 스스로 내놓을 때까지 기다려야 한다.

예시: 옆 사람 손에 있는 젓가락을 힘으로 뺏어올 수 없습니다. 그 사람이 밥을 다 먹고 내려놓을 때까지 기다려야 합니다.

4. 순환 대기 (Circular Wait)

독일어: Zyklisches Warten

의미: 대기하는 프로세스들이 서로 꼬리를 물고 원형(Circle)을 이뤄야 한다.

예시:

  • 철학자 A는 B의 젓가락을 기다림
  • 철학자 B는 C의 젓가락을 기다림
  • 철학자 C는 D의 젓가락을 기다림
  • 철학자 D는 A의 젓가락을 기다림 → 뱅글뱅글 돈다!

🔥 데드락 방지 전략 (시험 꿀팁)

데드락을 막으려면? 이 4가지 중 하나만 박살 내면 됩니다.

1. 상호 배제 부정

자원을 공유하게 만듦 (읽기 전용 파일 등). 하지만 현실적으로 어려운 경우가 많습니다.

2. 점유 대기 부정 ⭐ 가장 실용적

필요하면 처음부터 다 가져가게 함. (페트리 넷 방식처럼 두 자원을 동시에 획득)

3. 비선점 부정

급하면 뺏어올 수 있게 함. (CPU 스케줄링, 메모리 관리 등)

4. 순환 대기 부정

자원에 번호를 매겨서 순서대로만 집게 함. (1번 집어야 2번 집을 수 있음)

📊 데드락 상황 분석 체크리스트

문제가 주어졌을 때:

  • 4가지 조건이 모두 성립하는가? → 데드락 발생
  • 하나라도 깨졌는가? → 데드락 없음
  • “동시에” 획득하는가? (점유 대기 깨짐) → 데드락 없음
  • 자원을 강탈할 수 있는가? (비선점 깨짐) → 데드락 없음
  • 순서가 정해져 있는가? (순환 대기 깨짐) → 데드락 없음

📚 정리표

개념초기값용도패턴
Mutex1Lockdown → 작업 → up
Synchronization0Ordering신호 대기
CountingN or 0재고/버퍼생산자-소비자
데드락 조건내용깨는 방법
상호 배제한 번에 한 프로세스만자원 공유
점유 대기하나 쥐고 다른 거 기다림모두 한 번에 획득 ⭐
비선점못 뺏어옴강제 회수
순환 대기원형으로 기다림순서 정하기

🎓 최종 정리

세마포어:

  • down = 확인 + 획득 (또는 대기)
  • up = 반납 + 신호
  • 3가지 패턴만 기억하면 됨

데드락:

  • 4가지 조건이 동시에 성립해야 발생
  • 하나만 깨도 안 생김
  • 시험에서는 “점유 대기” 부정이 가장 자주 출제됨

마지막 팁: 아무리 복잡한 세마포어 문제라도, “나 필요한 게 있는지 확인(down)하고, 써(up 신호)하고, 반환(up)한다”는 이 마음가짐만 유지하면 절대 틀리지 않습니다! 🚀

Computer Science, Operating Systems
semaphore deadlock mutex synchronization coffman conditions 운영체제
This post is licensed under CC BY 4.0 by the author.