[OS] 병행 프로세스, 임계구역, 상호배제 - 8

병행 프로세스, 임계구역, 상호배제 — 동기화 문제의 시작

병행성¹이란 여러 프로세스가 하나의 프로세서·메모리·I/O 장치를 공유하며 동시에 실행 상태에 있는 것이다. 이 상황에서 공유 자원에 동시 접근하는 임계구역² 문제가 발생하며, 이를 해결하는 원칙이 상호배제³다.

1. 병행 프로세스

두 개 이상의 프로세스가 동시에 실행 상태에 있는 것을 병행 프로세스라 한다. 두 가지 형태로 나뉜다.

프로세스 A

⟷

프로세스 B

독립적 — 서로 영향 없음

프로세스 A

↔

공유 자원

↔

프로세스 B

상호 협력 — 동시 접근 시 충돌 가능

독립적 병행 프로세스는 서로 관련 없이 각자 실행된다. 실행 순서가 달라져도 결과가 항상 같다.

상호 협력적 병행 프로세스는 공유 데이터를 함께 건드리기 때문에 실행 순서에 따라 결과가 달라질 수 있다. 동기화⁴ 문제가 여기서 시작된다.

💡 비동기 수행은 다른 작업이 끝날 때까지 기다리지 않고 수행하는 방식이고, 동기 수행은 수행 중인 작업이 끝날 때까지 기다린 후 다음 작업을 수행하는 방식이다. 병행 프로세스 환경에서는 비동기 수행이 기본이며, 이 때문에 실행 순서가 보장되지 않는다.

병행 프로세스가 존재하면 아래와 같은 문제들이 따라온다.

문제	설명
상호배제	공유 자원을 한 번에 하나의 프로세스만 사용하도록 보장
동기화	프로세스 간 작업 순서 및 진행을 조율
결정성	실행 순서와 관계없이 항상 같은 결과 보장
통신	프로세스 간 데이터 교환을 위한 메시지 전달
교착상태	프로세스들이 서로 자원을 점유한 채 무한히 대기하는 상태

2. 임계구역 (Critical Section)

공유 자원에 접근하는 코드 영역을 임계구역이라 한다. 공유 자원이란 CPU, 메모리, 디스크, I/O 장치, 버퍼 등을 의미한다.

왜 문제가 되는지 구체적으로 보자. 두 스레드가 동시에 count++를 실행한다고 하면, 이 코드는 내부적으로 세 단계로 나뉜다.

count++ 내부 동작

① count 읽기

→

② +1 연산

→

③ count 쓰기

⚠ 문제 상황

스레드 A가 ①을 실행한 직후 스케줄러가 스레드 B로 전환되면, B도 같은 값을 읽어서 증가시키고 쓴다. 그 뒤 A가 자신이 읽어둔 값으로 덮어쓰면 B의 결과가 사라진다. 두 번 증가시켰는데 한 번만 반영되는 것 — 이것이 레이스 컨디션⁵이다.

임계구역의 핵심 특성은 이렇다. 한 번에 하나의 프로세스만 접근할 수 있고, 점유 중인 프로세스가 끝나면 다른 프로세스가 접근할 수 있다. 특정 프로세스가 독점할 수 없으며, 처리는 신속하게 진행되어야 하고, 접근 요청은 일정 시간 내에 허락되어야 한다.

3. 상호배제 (Mutual Exclusion)

상호배제란 어떤 프로세스가 공유 자원을 사용 중일 때 다른 프로세스가 그 자원에 접근하지 못하도록 막는 기법이다. 임계구역에 들어가는 문에 자물쇠를 거는 것이다.

상호배제가 올바르게 동작하려면 세 가지 조건을 만족해야 한다.

조건	의미	어기면
상호배제 조건	두 개 이상의 프로세스가 동시에 임계구역에 있어선 안 된다	레이스 컨디션 발생
진행 조건	임계구역 밖의 프로세스가 다른 프로세스의 진입을 막으면 안 된다	불필요한 대기 발생
한계대기 조건	어떤 프로세스도 임계구역 접근이 무한히 거부되어선 안 된다	기아6(Starvation) 발생

4. 소프트웨어적 상호배제 알고리즘 — 그리고 현대의 변화

🕰 1965년

👨‍💻 김개발

"공유 변수에 두 프로세스가 동시에 접근하면 값이 이상해지더라고. 그래서 내가 직접 flag 변수 만들고, turn 변수 만들고, while 루프 돌려서 막았지. 하루 종일 이거 관리하는 거야."

// 상대가 나올 때까지 루프를 돌며 CPU를 점유
while (flag[1] == true) { } // CPU야 미안...
// 임계구역
flag[0] = false;
turn = 1;

🤔 "잠깐, 기다리는 동안 CPU가 while 루프만 돌리는 게 맞나?
대기 중에 CPU를 다른 스레드한테 양보하면 안 되나?"

✅ 2024년

👨‍💻 이개발

"하드웨어가 원자적으로 처리해주고, 대기 중엔 CPU를 다른 스레드에 양보해. OS가 뮤텍스·세마포어 제공하고, C#에선 lock 한 줄이면 끝."

private readonly object _lockObj = new object();

lock (_lockObj)
{
    count++; // 임계구역 — 한 번에 하나의 스레드만 진입
}

💡 그럼 왜 배우나?
소프트웨어 알고리즘들은 "상호배제를 보장하려면 무엇이 필요한가"를 가장 날것으로 보여준다. lock이 내부적으로 무엇을 해결하는 건지, 세 가지 조건이 왜 필요한지 이해하는 데 기반이 된다.

데커(Dekker) 알고리즘

최초의 소프트웨어 상호배제 알고리즘이다. 두 개의 프로세스를 대상으로 하며, flag와 turn 두 공유변수를 사용한다. flag[i]는 프로세스 i가 임계구역에 들어가려 한다는 의사 표시이고, turn은 누구 차례인지를 나타낸다.

핵심 동작 원리는 "의사표시 후, 충돌 시 능동적으로 물러서는" 구조다. 두 프로세스가 동시에 들어가려 할 때 어떻게 대화하는지 보자.

P0

"나 들어갈게" flag[0] = true

"나도 들어갈게" flag[1] = true

P1

⚡ 충돌! 둘 다 flag = true

P0

"turn 확인해보니 P1 차례네... 일단 내가 물러설게"
flag[0] = false → 대기 중...

😑 P0, turn이 바뀔 때까지 루프 대기 중 (busy-waiting⁷)

🔒 임계구역 사용 중...

P1

"다 썼어" flag[1] = false, turn = 0

P1

P0

"이제 내 차례네" flag[0] = true → 재시도

✅ P0 임계구역 진입

로직이 복잡한 이유가 바로 이 "물러섬 → 루프 대기 → 재시도" 구조 때문이다. 현대에는 OS와 언어 레벨의 뮤텍스·lock으로 추상화되어 직접 사용하지는 않지만, 상호배제 세 조건을 소프트웨어만으로 처음 구현한 알고리즘이라는 점에서 의미가 있다.

피터슨(Peterson) 알고리즘

데커와 마찬가지로 두 개의 프로세스용이며 flag, turn 두 변수를 사용한다. 그러나 구조가 훨씬 단순하다. 핵심 동작 원리는 "먼저 의사표시, 그리고 즉시 양보"다. 데커가 충돌 후에 물러서는 구조라면, 피터슨은 처음부터 상대에게 차례를 넘긴다.

P0

"나 들어갈게. 근데 P1 너 먼저 해도 돼"
flag[0] = true, turn = 1

"나도 들어갈게. P0 너 먼저 해도 돼"
flag[1] = true, turn = 0

P1

turn = 0 (마지막으로 양보한 쪽이 P1이므로 P0 우선)

P0

"turn이 내 차례가 아니거나 P1이 준비 안 됐으니 바로 진입"

✅ P0 임계구역 진입

😑 P0 나올 때까지 대기 중...

P1

P0

"다 썼어" flag[0] = false

✅ P1 임계구역 진입

데커와의 결정적 차이는 충돌 후 물러서는 게 아니라, 진입 전에 먼저 양보한다는 것이다. 그래서 루프가 단순하고 로직이 직관적이다. 마찬가지로 현대에서는 직접 쓰이지 않으며, 원리 이해용으로 의미가 있다.

Lamport의 빵집 알고리즘 (Bakery Algorithm)

데커와 피터슨은 2개 프로세스만 처리 가능하다. 3개 이상으로 확장하기 위해 Lamport가 고안한 알고리즘이다. 핵심 동작 원리는 "번호표를 받고, 작은 번호 순서로 입장한다"는 것이다.

① 번호표 발급
max(모든 번호)+1

→

② 모든 프로세스와 번호 비교

→

③ 내 번호가 가장 작은가?

→

④ 임계구역 진입

→

⑤ number[i] = 0
번호표 반납

세 가지 포인트가 중요하다.

첫째, choosing[i] 플래그가 필요한 이유는 번호표를 발급받는 도중 다른 프로세스가 끼어드는 상황을 막기 위해서다. 번호표를 받는 중인 프로세스는 비교 대상에서 잠깐 제외한다.

둘째, 번호가 같을 수 있기 때문에 동점일 때는 프로세스 번호(i, j)로 순서를 정한다. i가 작은 프로세스가 먼저 입장한다.

셋째, 번호표 순서가 곧 대기 순서이므로 기아가 발생하지 않는다. 세 알고리즘 중 유일하게 상호배제·진행·한계대기 세 조건을 모두 만족한다. 분산 처리 환경에서의 동기화 개념으로 이어지는 이론적 기반이기도 하다.

알고리즘	프로세스 수	핵심 원리	특징
데커	2개	의사표시 + 충돌 시 물러섬	최초의 소프트웨어 상호배제, 세 조건 만족
피터슨	2개	의사표시 + 즉시 양보	데커보다 단순, 세 조건 만족
빵집	N개 이상	번호표 발급 + 작은 번호 우선	N개 프로세스로 확장 가능, 기아 없음

📎 용어 설명

1. 병행성(Concurrency) — 여러 프로세스가 하나의 프로세서·메모리·I/O를 공유하며 동시에 실행되는 성질
2. 임계구역(Critical Section) — 다중 프로그래밍 시스템에서 공유 자원에 접근하는 코드 영역
3. 상호배제(Mutual Exclusion) — 한 프로세스가 공유 자원을 사용 중일 때 다른 프로세스의 접근을 막는 기법
4. 동기화(Synchronization) — 프로세스 간 작업 진행을 위한 통신을 조율하는 것
5. 레이스 컨디션(Race Condition) — 두 개 이상의 스레드/프로세스가 공유 자원에 동시 접근해 실행 순서에 따라 결과가 달라지는 문제
6. 기아(Starvation) — 특정 프로세스가 자원을 무한히 할당받지 못하는 상태
7. busy-waiting — 임계구역 진입 가능 여부를 루프로 계속 확인하며 대기하는 방식. 대기 중에도 CPU를 점유한다

운영체제 병행 프로세스 임계구역 상호배제 동기화 데커 알고리즘 피터슨 알고리즘 빵집 알고리즘