프로세스 동기화와 데드락

https://www.inflearn.com/course/운영체제-기술면접-비전공자?cid=337649

본 포스트는 인프런 “[CS 기술면접 2] 말이 트이는 운영체제” 강의를 학습하며 정리한 내용을 다룹니다.

경쟁 상태(Race Condition)란?

앞서 멀티스레딩은 하나의 프로세스에서 여러 스레드가 코드, 데이터, 힙 영역 등을 공유하며 실행하는 방식이라고 배웠습니다.

그런데 여러 스레드가 동일한 데이터를 동시에 변경하면 어떻게 될까요? 각 스레드가 실행되는 순서에 따라 예상과 다른 결과가 발생할 수 있습니다.

이러한 문제를 경쟁 상태(Race Condition)라고 합니다.

두 개 이상의 연산이 동시에 공유 자원에 접근할 때 결과의 일관성을 보장받지 못하는 상태
Race Condition이 발생하기 위한 두 가지 조건
- 공유 자원
  - 여러 스레드 또는 프로세스가 동일한 자원(변수, 메모리 등)을 동시에 사용
  - 예: 전역 변수, 파일, 데이터베이스 등
- 동시성
  - 두 스레드 또는 프로세스가 동시에 실행되며, 실행 순서에 따라 결과가 달라질 수 있는 상황
  - 예: 문맥 교환으로 스레드의 작업이 중단되었다가 다시 실행되는 상황

Race Condition의 Race는 경주라는 의미입니다. 여러 프로세스나 스레드가 공유 자원에 먼저 접근해 작업을 완료하려고 경쟁하는 상황을 비유적으로 표현한 것으로, 우리말로는 '경쟁 상태'라고 부릅니다.

경쟁 상태 발생 예시

두 개의 스레드가 하나의 은행 계좌에 입금과 출금을 수행한다고 가정하겠습니다.

문제 상황

초기 은행 계좌 잔액: 100원
스레드 A: 50원 입금
스레드 B: 30원 출금
공유 자원: 은행 계좌
동시성: 두 스레드의 입출금 작업이 동시에 진행되는 상황

정상적으로 처리된다면 최종 잔액은 100 + 50 - 30 = 120원이어야 합니다.

하지만 두 스레드가 동시에 잔액을 읽고 변경하면 다음과 같은 문제가 발생할 수 있습니다.

1. 읽기(Read)

스레드 A: 계좌 잔액 100원 읽기
스레드 B: 계좌 잔액 100원 읽기

2. 업데이트(Update)

스레드 A: 50원 입금 → 100 + 50 = 150원
스레드 B: 30원 출금 → 100 - 30 = 70원

3. 저장(Write)

스레드 A: 변경된 잔액 150원 저장
스레드 B: 변경된 잔액 70원 저장

최종 결과

스레드 A가 저장한 150원을 스레드 B가 저장한 70원으로 덮어쓰기
최종 잔액이 120원이 아닌 70원으로 저장되는 문제 발생

이처럼 하나의 작업이 읽기, 계산, 저장 등 여러 단계로 나뉘어 있을 때, 중간에 다른 스레드가 동일한 데이터에 접근하면 경쟁 상태가 발생할 수 있습니다.

경쟁 상태의 발생 상황과 해결 방법

경쟁 상태는 일반적인 프로그램뿐만 아니라 운영체제의 커널에서도 발생할 수 있습니다.

1. 커널 작업 중 인터럽트 발생

커널 모드에서 데이터를 읽고 수정하는 도중 인터럽트가 발생하면, 인터럽트 처리 과정에서도 동일한 데이터에 접근할 수 있습니다.

발생 상황: 커널 모드에서 데이터를 처리하던 중 인터럽트가 발생하고, 인터럽트 처리 루틴이 동일한 데이터에 접근하는 경우
해결 방법 — 인터럽트 지연 처리: 중요한 공유 데이터에 접근하는 동안 인터럽트 처리를 지연시키고, 작업이 끝난 후 인터럽트 처리

2. 커널 모드에서 문맥 교환(context switching) 발생

프로세스가 커널 모드에서 실행 중일 때 문맥 교환이 발생하면, 다른 프로세스가 같은 커널 주소 공간(메모리)의 데이터(PCB, ready queue 등)를 사용할 수 있습니다.

발생 상황: 커널 모드에서 문맥 교환이 발생하여 다른 프로세스가 동일한 커널 데이터에 접근하는 경우
해결 방법 — 커널 모드에서 문맥 교환 방지: 커널 모드에서 실행 중일 때 CPU를 빼앗기지 않도록 하고, 사용자 모드로 돌아갈 때 CPU 반납

커널 모드에서 문맥 교환 시, Race Condition이 발생하는 예시

CPU 코어가 하나이고, 커널이 공유 변수 count = 5를 관리한다고 가정하겠습니다.

프로세스 A 실행 (커널 모드)

count = 5를 CPU 레지스터로 읽음
5 + 1 = 6 계산
아직 메모리에 저장하지 않은 상태

문맥 교환 발생 (A → B)

프로세스 A가 CPU를 빼앗김
운영체제가 A의 CPU 레지스터 상태를 저장
프로세스 B의 실행 상태를 복구하여 실행

프로세스 B 실행 (커널 모드)

동일한 커널 변수 count = 5를 읽음
5 + 1 = 6 계산
count = 6을 메모리에 저장

문맥 교환 발생 (B → A)

프로세스 A의 CPU 레지스터 상태 복구
A는 이전에 계산한 값 6을 메모리에 저장
최종 결과는 7이 아닌 6

3. 다중 CPU 환경

여러 CPU가 동시에 동일한 공유 데이터에 접근하는 경우에도 경쟁 상태가 발생할 수 있습니다.

발생 상황: 여러 CPU가 동일한 공유 데이터에 동시에 접근하는 경우
해결 방법 — 락(Lock) 사용: 커널 내부 공유 데이터에 접근할 때 Lock을 설정하고, 작업이 완료되면 Unlock하여 다른 접근 허용

크리티컬 섹션(Critical Section)

앞서 살펴본 경쟁 상태는 여러 스레드가 동일한 공유 자원에 동시에 접근하면서 발생하는 문제였습니다. 이러한 문제를 해결하려면 공유 자원에 접근하는 코드가 동시에 실행되지 않도록 제어할 필요가 있습니다.

이때 두 개 이상의 프로세스나 스레드가 동시에 접근하면 안 되는 공유 자원을 사용하는 코드 영역을 크리티컬 섹션(Critical Section, 임계 구역)이라고 합니다.

두 개 이상의 프로세스 또는 스레드가 동시에 접근하면 안 되는 공유 자원을 사용하는 코드 영역
공유 자원의 데이터 일관성을 보장하기 위해 한 번에 하나의 프로세스 또는 스레드만 크리티컬 섹션을 실행하도록 제어

크리티컬 섹션 문제(Critical Section Problem)

여러 프로세스가 동시에 크리티컬 섹션에 접근하면 앞서 살펴본 Race Condition이 발생할 수 있습니다.

이를 방지하기 위해서는 다음 세 가지 조건을 만족하도록 설계해야 합니다.

1. 상호 배제(Mutual Exclusion)

한 번에 하나의 프로세스만 크리티컬 섹션에 진입 가능
조건 불충족 예시: 여러 프로세스가 동시에 은행 계좌에 입출금을 수행하여 데이터 일관성이 깨지는 상황

2. 진행 조건(Progress)

크리티컬 섹션에 프로세스가 없다면 대기 중인 프로세스가 진입할 수 있어야 하는 조건
조건 불충족 예시: 프로세스 A와 B가 모두 대기 중이고 크리티컬 섹션은 비어 있지만, 운영체제가 이를 제대로 처리하지 못해 누구도 진입하지 못하고 자원이 낭비되는 상황

3. 유한 대기(Bounded Waiting)

크리티컬 섹션에 진입하기 위해 대기하는 프로세스가 무한정 기다리지 않도록 보장
조건 불충족 예시: 우선순위에 따라 접근 순서를 정하는 방식에서 높은 우선순위의 프로세스가 계속 도착하여 특정 프로세스가 무한정 기다리는 상황

크리티컬 섹션 문제 해결 — 세마포어(Semaphore)

크리티컬 섹션에서는 여러 프로세스가 동시에 공유 자원에 접근하지 못하도록 제어해야 합니다.

이를 구현하는 대표적인 동기화 기법 중 하나가 세마포어(Semaphore)입니다.

여러 프로세스나 스레드가 공유 자원에 접근하는 것을 동기화하기 위해 사용하는 기술
정수 값을 사용하여 공유 자원의 접근 가능 여부 제어
허용된 자원 개수만큼 프로세스가 공유 자원에 접근할 수 있도록 제한

세마포어의 특징

1. 세마포어 값

세마포어는 정수 값을 사용하여 이용 가능한 자원 개수를 관리
값이 0보다 크면 자원 사용 가능
값이 0이면 모든 자원이 사용 중인 상태

2. 작업 단위

P(S) 연산: 자원 획득을 위해 세마포어 값을 1 감소시키는 연산으로, 사용 가능한 자원이 없으면 대기
V(S) 연산: 자원을 반납하기 위해 세마포어 값을 1 증가시키는 연산

3. 동기화 보장

이진 세마포어 등을 이용해 한 번에 하나의 프로세스만 크리티컬 섹션에 접근하도록 제어
자원 개수를 기준으로 동시에 접근할 수 있는 프로세스 수 제한

세마포어 동작 예시

공유 자원을 사용하는 프로세스 A, B, C가 있고, 사용 가능한 자원은 2개만 존재한다고 가정하겠습니다.

문제 상황

공유 자원을 사용하려는 프로세스: A, B, C
사용 가능한 공유 자원: 2개
초기 세마포어 값: 2

동작 과정

초기 세마포어 값 = 2 → 자원 2개 사용 가능
프로세스 A가 P(S) 호출 → 세마포어 값 2에서 1로 감소, 자원 사용
프로세스 B가 P(S) 호출 → 세마포어 값 1에서 0으로 감소, 자원 사용
프로세스 C가 P(S) 호출 → 사용 가능한 자원이 없으므로 대기 상태로 전환
프로세스 A가 V(S) 호출 → 자원 반납 및 세마포어 값 증가, 대기하던 프로세스 C가 자원 사용

이처럼 세마포어는 자원의 개수를 관리하면서 허용된 수만큼의 프로세스만 공유 자원에 접근하도록 제어합니다.

세마포어의 종류

1. 카운팅 세마포어(Counting Semaphore)

카운팅 세마포어는 여러 개의 공유 자원이 존재할 때 사용할 수 있는 방식입니다.

0 이상의 정수 값을 사용하며, 동시에 접근 가능한 자원의 개수 관리
예: 프린터가 3대 존재하는 경우 최대 3개의 프로세스가 동시에 프린터 사용 가능

2. 이진 세마포어(Binary Semaphore)와 뮤텍스(Mutex)

이진 세마포어는 값이 0 또는 1인 세마포어로, 하나의 공유 자원에 대한 동시 접근을 제한할 때 사용합니다. 이러한 상호 배제 용도로 뮤텍스(Mutex)도 사용됩니다.

0 또는 1의 값만 사용
한 번에 하나의 프로세스만 공유 자원에 접근 가능

세마포어의 대기 상태 처리 방식

세마포어를 사용하더라도 모든 프로세스가 즉시 자원을 사용할 수 있는 것은 아닙니다. 이미 다른 프로세스가 자원을 사용 중이라면 해당 프로세스는 자원이 반환될 때까지 기다려야 합니다.

이때 대기 상태를 처리하는 방법은 크게 Busy-Wait와 Block-Wakeup 두 가지로 구분됩니다.

1. Busy-Wait

Busy-Wait는 공유 자원을 사용할 수 있는지 반복해서 확인하는 방식입니다.

프로세스가 자원을 사용하기 위해 세마포어 값을 계속 확인하며 대기하는 방식
자원을 사용할 수 있을 때까지 CPU를 사용하여 반복문 실행

2. Block-Wakeup

Block-Wakeup은 자원을 사용할 수 없을 때 프로세스를 Blocked 상태로 전환하고, 자원이 반환되면 다시 깨우는 방식입니다.

자원이 사용 중이면 프로세스를 Blocked 상태로 전환하고, 자원을 사용할 수 있게 되면 Wakeup하여 실행을 재개하는 방식
자원을 기다리는 동안 CPU를 낭비하지 않아 효율적인 대기 가능

동작 방식

P(S) 호출
- 세마포어 값을 1 감소시킨 뒤 값이 0 미만(음수)이면 block() 호출
- 운영체제가 해당 프로세스를 세마포어의 Wait Queue에 추가하고 CPU 제어권 회수
V(S) 호출
- 세마포어 값을 1 증가
- 대기 중인 프로세스가 존재하면 Wait Queue에서 해당 프로세스를 깨워 실행 가능 상태로 전환

이 구현에서는 세마포어 값이 음수라면 그 절댓값을 통해 Wait Queue에서 대기 중인 프로세스의 수를 나타낼 수 있습니다.

Busy-Wait와 Block-Wakeup 중 어떤 방식이 더 효율적일까?

Block-Wakeup은 CPU를 사용하지 않고 대기할 수 있다는 장점이 있지만, 항상 Busy-Wait보다 효율적인 것은 아닙니다.

크리티컬 섹션의 실행 시간이 짧으면 Block-Wakeup 과정의 오버헤드가 더 커질 수 있음
예: 공유 변수의 잠금이 1μs(마이크로초) 만에 해제되는 경우, 프로세스를 재우고 깨우는 데 더 오랜 시간이 필요할 수 있음
이러한 상황에서는 Busy-Wait 방식이 더 효율적일 수 있음

데드락(Deadlock, 교착 상태)

앞서 세마포어와 락을 통해 여러 프로세스가 공유 자원에 접근하는 것을 제어하는 방법을 살펴봤습니다. 그런데 프로세스가 여러 자원을 사용하다 보면 서로가 점유한 자원을 기다리면서 더 이상 작업을 진행하지 못하는 상황이 발생할 수 있습니다.

이러한 문제를 데드락(Deadlock, 교착 상태)이라고 합니다.

두 개 이상의 프로세스가 서로 점유한 자원을 요청하며 대기 상태에 빠져 더 이상 실행을 진행할 수 없는 상황
공유 자원이나 동기화 기법을 잘못 설계했을 때 발생 가능

데드락 발생 예시

프로세스 P1과 P2가 있고, 각각 공유 자원 A와 B가 필요하다고 가정하겠습니다.

프로세스 P1: 자원 A를 점유한 상태에서 자원 B 요청
프로세스 P2: 자원 B를 점유한 상태에서 자원 A 요청
P1은 P2가 자원 B를 반환하기를 대기
P2는 P1이 자원 A를 반환하기를 대기

두 프로세스 모두 상대방이 자원을 반환해야 다음 작업을 수행할 수 있기 때문에 더 이상 실행을 진행하지 못하게 됩니다.

데드락 발생 조건

데드락이 발생하려면 다음 네 가지 조건이 동시에 충족되어야 합니다.

1. 상호 배제(Mutual Exclusion)

자원은 한 번에 하나의 프로세스만 사용 가능
예: 프린터, 파일 접근 등

2. 점유 대기(Hold and Wait)

프로세스가 이미 할당받은 자원을 점유한 상태에서 다른 자원을 추가로 요청하며 대기

3. 비선점(No Preemption)

이미 할당된 자원은 해당 프로세스가 작업을 끝낼 때까지 강제로 회수할 수 없는 상태

4. 순환 대기(Circular Wait)

프로세스들이 순환 형태로 서로의 자원을 요청하며 대기
예: 프로세스 A가 B의 자원을 요청하고, 프로세스 B가 A의 자원을 요청하는 상황

사이클이 있으면 무조건 데드락이 발생할까?

데드락을 설명할 때 자주 등장하는 것이 자원 할당 그래프의 사이클(Cycle)입니다. 하지만 자원 할당 그래프에 사이클이 존재한다고 해서 반드시 데드락이 발생하는 것은 아닙니다.

특정 공유 자원이 여러 개 존재한다면 사이클이 있더라도 데드락이 발생하지 않을 수 있음
예: 공유 자원 A가 2개라면 하나의 자원이 다른 프로세스에 점유되어 있더라도, 나머지 자원을 사용하여 프로세스 P2가 작업을 진행할 수 있는 상황

데드락 해결 방법

데드락을 해결하는 방법은 크게 예방(Prevention), 회피(Avoidance), 탐지 및 회복(Detection & Recovery)으로 구분할 수 있습니다.

세 가지 방법은 데드락을 방지하는 정도와 접근 방식에 차이가 있습니다. 예방은 발생 조건 자체를 제거하고, 회피는 자원 할당 전에 안전성을 검사하며, 탐지 및 회복은 데드락 발생 후 문제를 해결합니다.

1. 예방(Prevention)

데드락은 상호 배제, 점유 대기, 비선점, 순환 대기라는 네 가지 조건이 동시에 만족할 때 발생합니다.

따라서 네 가지 조건 중 하나 이상이 충족되지 않도록 설계하면 데드락을 예방할 수 있습니다.

상호 배제 방지

공유 자원을 여러 프로세스가 동시에 사용할 수 있도록 설계
예: 읽기 전용 데이터에 대한 동시 접근 허용
제한 사항: 쓰기 작업에서는 여전히 상호 배제가 필요할 수 있음

점유 대기 방지

프로세스가 이미 점유 중인 자원을 가진 상태에서 추가 자원을 요청하며 대기하지 않도록 설계
필요한 모든 자원을 한꺼번에 요청하도록 강제
단점: 아직 필요하지 않은 자원을 미리 점유하여 자원 낭비 가능

비선점 방지

다른 프로세스가 점유한 자원을 강제로 회수하여 다른 프로세스가 사용할 수 있도록 설계
단점: 데이터 일관성 문제와 오버헤드 발생 가능

순환 대기 방지

각 자원에 번호를 부여하고 항상 번호가 증가하는 순서로 자원을 요청하도록 설계
예: 자원 1 → 자원 2 → 자원 3 순서로만 자원 요청 허용
단점: 자원 요청 순서를 엄격하게 지켜야 하므로 유연성 저하

2. 회피(Avoidance)

데드락 예방이 발생 조건 자체를 제거하는 방식이라면, 회피는 현재 시스템 상태를 확인하고 안전할 때만 자원을 할당하는 방식입니다.

시스템의 현재 상태를 평가하여 데드락이 발생하지 않을 것으로 판단되는 경우에만 자원 할당
프로세스가 사용할 최대 자원 요구량을 사전에 파악할 필요
자원을 할당한 이후에도 시스템이 안전 상태(Safe State)를 유지하는지 확인
- 안전 상태(Safe State): 모든 프로세스가 특정 실행 순서에 따라 필요한 자원을 할당받고 작업을 완료할 수 있는 상태

동작 과정

프로세스가 필요한 자원을 요청
요청한 자원을 할당한 이후의 시스템 상태를 시뮬레이션
할당 이후에도 시스템이 안전 상태라면 자원 할당
안전 상태가 아니라면 자원 할당 요청 거절

장점

데드락 발생 가능성 최소화

단점

각 프로세스가 사용할 자원의 최대 요구량을 사전에 파악할 필요
시스템의 안전 상태를 검사하기 위한 계산 비용 증가

3. 탐지 및 회복(Detection & Recovery)

탐지 및 회복은 데드락 발생을 미리 막는 것이 아니라, 실제로 데드락이 발생했는지 확인하고 문제가 발생했다면 복구하는 방식입니다.

탐지(Detection)

데드락이 발생했는지 주기적으로 검사
자원 할당 그래프를 사용하여 데드락 상태와 사이클 존재 여부 확인

회복(Recovery)

데드락을 탐지한 이후 문제를 해결하기 위한 조치 수행

회복 방법 1 — 프로세스 종료

데드락을 유발하는 프로세스를 하나 이상 종료
예: 데드락에 관련된 모든 프로세스 종료
예: 우선순위가 낮은 프로세스부터 하나씩 종료

회복 방법 2 — 자원 선점

특정 프로세스가 점유 중인 자원을 강제로 회수
예: 다른 프로세스가 작업을 완료할 수 있도록 자원을 선점
예: 자원을 회수당한 프로세스를 나중에 다시 실행

단점

강제적인 프로세스 종료나 자원 회수 과정에서 데이터 일관성 문제 발생 가능

데드락 무시 전략

예방, 회피, 탐지 및 회복 외에도 데드락 문제를 별도로 처리하지 않는 방법이 있습니다.

이를 데드락 무시 전략이라고 합니다.

데드락 예방과 탐지에는 복잡한 알고리즘과 추가적인 비용이 필요
실제 시스템에서 데드락 발생 확률이 낮다고 판단되는 경우 별도의 처리 없이 무시하는 전략 사용
데드락이 발생하면 사용자가 수동으로 문제 해결
- 예: 프로세스 종료 및 재시작