01 교착 상태(Deadlock)란?

서로의 자원을 기다리며 영원히 멈춰버린 프로세스들

📖 핵심 개념
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 더 이상 작업을 진행하지 못하는 상태입니다. 다중 프로그래밍 시스템에서 결코 일어나지 않을 사건(event)을 기다리는 셈입니다. 프로세스가 교착 상태에 빠지면 작업이 정지되어 더는 명령을 진행할 수 없으며, 운영체제가 해결하지 못하면 시스템 운영자나 사용자가 작업을 강제 종료하는 외부 간섭으로 해결해야 합니다.

⚠️ 왜 더 심각한 문제인가
교착 상태는 시스템 자원에 대한 요구가 뒤엉킨 상태로, 두 프로세스가 서로 사용 중인 자원을 기다리고 있을 때 발생합니다. 하나 이상의 작업에 영향을 주기 때문에 무한 대기나 기아 상태보다 더 심각한 문제를 야기합니다. 자원 해제 요청이 받아들여질 때까지 프로세스들은 작업을 진행할 수 없고, 현재 보유한 자원도 해제할 수 없습니다.

교착 상태가 발생하는 대표 사례

02 교착 상태의 발생 원인 & 자원 할당 그래프

시스템 자원, 공유 변수, 응용 프로그램에서 비롯되는 문제들

📊 자원 할당 그래프 (Resource Allocation Graph)
프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것입니다. 이 그래프를 사용하면 어떤 프로세스에 자원이 할당되어 있는지, 어떤 프로세스가 자원을 기다리고 있는지를 한눈에 파악할 수 있습니다.

· 자원 2개 이상의 프로세스를 동시에 허용하는 경우도 있음
· 여러 프로세스가 하나의 자원을 동시에 사용하면 이를 다중 자원이라 함
· 다중 자원은 수용 가능한 프로세스 수를 사각형 안에 작은 동그라미로 표현

💡 시험 단골 함정 — 사이클이 곧 교착 상태일까?
자원당 인스턴스가 1개뿐이라면 사이클 발생 = 교착 상태가 맞습니다. 하지만 다중 자원(인스턴스가 여러 개)인 경우, 사이클이 존재하더라도 다른 프로세스가 자원을 반납해 사이클이 깨질 수 있으므로 교착 상태일 수도 있고 아닐 수도 있습니다.

03 교착 상태의 4가지 필요조건

네 조건을 동시에 충족해야만 교착 상태가 발생한다

① 상호 배제 (Mutual Exclusion)
한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 합니다. 자원을 최소 하나 이상 비공유, 즉 한 번에 프로세스 하나만 해당 자원을 사용할 수 있어야 합니다. 사용 중인 자원을 다른 프로세스가 사용하려면 자원이 해제될 때까지 대기해야 합니다.

② 비선점 (Non-preemption)
한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 합니다. 자원을 강제로 빼앗을 수 없고, 자원을 점유하고 있는 프로세스가 끝나야만 자원이 해제됩니다.

③ 점유와 대기 (Hold and Wait)
프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 합니다. 자원을 최소한 하나 정도 보유하면서, 다른 프로세스에 할당된 자원을 얻으려고 대기하는 프로세스가 있어야 합니다.

④ 원형 대기 (Circular Wait)
점유와 대기를 하는 프로세스 간의 관계가 원형을 이루어야 합니다. 단순히 점유와 대기를 한다고 모두 교착 상태에 빠지는 것은 아니며, 프로세스들이 서로 방해하는 방향이 원을 이루어 서로 양보하지 않을 때 교착 상태가 발생합니다.

💡 조건의 두 가지 성격
· 상호 배제 + 비선점 : 자원이 어떤 특징을 가지는지 나타내는 조건. 동시 공유도 안 되고 중간에 빼앗을 수도 없다면 자원을 가진 프로세스가 내놓을 때까지 무작정 기다리게 됨
· 점유와 대기 + 원형 대기 : 프로세스가 어떤 행위를 하는지 나타내는 조건. 점유·대기 상태에서 방해하는 방향이 원을 이루면 서로 양보하지 않아 교착 상태 발생

04 교착 상태 해결 방법 — 예방 · 회피 · 검출 · 회복

네 가지 접근법과 각각의 현실적 한계

① 교착 상태 예방 — 네 조건을 하나씩 무력화

❌ 점유와 대기 예방의 추가 단점
· 프로세스가 자신이 사용할 모든 자원을 자세히 알기 어려움
· 앞으로 사용할 자원까지 미리 선점해버려 다른 프로세스의 작업이 지연됨
· 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함

② 교착 상태 회피 — 자원 할당량 조절

📖 핵심 개념
어느 수준 이상의 자원을 나누어 주면 교착 상태가 발생하는지 파악하여, 그 수준 이하로만 자원을 할당하는 방법입니다. 교착 상태가 발생할 범위에 있는 프로세스는 대기시킵니다.

문제점
· 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
· 시스템의 전체 자원 수가 고정적이어야 함
· 자원이 낭비됨

🏦 대표 알고리즘 — 은행원 알고리즘 (Banker's Algorithm)
교착 상태 회피의 대표적인 방법은 다익스트라(Dijkstra)가 제안한 은행원 알고리즘입니다. 시스템을 안전 상태(Safe State)와 불안전 상태(Unsafe State)로 나누고, 자원을 할당한 후에도 시스템이 안전 상태를 유지할 수 있을 때만 자원을 빌려주는(할당하는) 보수적인 방식입니다.

③ 교착 상태 검출 — 발생 여부를 계속 주시

④ 교착 상태 회복 — 강제 종료로 마무리

📖 핵심 개념
교착 상태가 검출된 후, 이를 푸는 후속 작업입니다. 회복 기법은 크게 두 가지 축으로 나뉩니다.

① 프로세스 종료 (Process Termination)
교착 상태를 유발한 프로세스를 강제로 종료합니다.
· 교착 상태를 일으킨 모든 프로세스를 동시에 종료하는 방법
· 교착 상태를 일으킨 프로세스 중 하나씩 순서대로 종료하는 방법

② 자원 선점 (Resource Preemption)
교착 상태가 깨질 때까지 특정 프로세스(희생자)의 자원을 강제로 빼앗아 다른 프로세스에게 할당하는 방식입니다.

✓ 실무적 결론
예방과 회피는 자원 활용성 저하·실효성 부족 문제로 잘 사용되지 않습니다. 교착 상태를 검출한 후 회복시키는 방식이 결론적으로 교착 상태를 해결하는 가장 현실적인 접근 방법입니다.

📌 핵심 정리

· 교착 상태 : 2개 이상의 프로세스가 서로의 자원 해제만 기다리며 정지된 상태
· 교착 상태 vs 기아 상태 : 교착은 대기 상태(자원 대기), 기아는 준비 상태(CPU 대기)
· 자원 할당 그래프 : 프로세스의 자원 점유·대기 관계를 방향성 그래프로 표현
· 필요조건 4가지 : 상호 배제 + 비선점 + 점유와 대기 + 원형 대기 (모두 충족 시 발생)
· 예방 : 네 조건 중 하나를 무력화 — 실효성 낮음
· 회피 : 자원 할당량을 조절 — 은행원 알고리즘(안전 상태 유지)이 대표적, 자원 낭비 발생
· 검출 : 타임아웃 또는 자원 할당 그래프로 발생 여부 모니터링
· 회복 : 프로세스 종료 또는 자원 선점(희생자 선택) — 검출+회복이 가장 현실적
· 사이클 vs 교착 : 단일 인스턴스 자원이면 사이클=교착, 다중 자원이면 사이클≠교착일 수 있음

태그 : 교착상태란데드락 발생 조건교착상태 기아상태 차이자원 할당 그래프상호배제 비선점이란원형대기 점유와대기교착상태 예방 회피 차이교착상태 검출 회복운영체제 데드락 정리운영체제 교착상태 해결

운영체제에서 유난히 헷갈려하는 단원 중 하나가 바로 프로세스 동기화입니다. 프로세스들이 왜 서로 통신을 해야 하는지, 그 통신은 또 어떻게 나뉘는지, 그리고 여러 프로세스가 동시에 같은 자원에 접근했을 때 생기는 문제는 어떻게 풀어내는지까지 차근차근 정리해보겠습니다. 강의노트 3개 분량(프로세스 간 통신 → 통신의 종류 → 공유 자원과 임계구역)을 순서대로 따라가면 어렵지 않게 흐름이 잡힐 것입니다.

01 프로세스 간 통신(IPC)이란 무엇일까

독립적으로 움직이는 프로세스들이 데이터를 주고받는 방법

📖 프로세스 간 통신(Inter-Process Communication, IPC)
프로세스는 시스템 안에서 혼자 독립적으로 실행되기도 하지만, 때로는 다른 프로세스와 데이터를 주고받기도 합니다. 이렇게 프로세스가 다른 프로세스와 데이터를 주고받는 것을 프로세스 간 통신(IPC)이라고 부릅니다.

IPC는 통신이 일어나는 범위에 따라 세 가지로 나눌 수 있습니다. 같은 프로세스 안의 스레드끼리인지, 같은 컴퓨터 안의 다른 프로세스끼리인지, 아니면 네트워크로 연결된 다른 컴퓨터의 프로세스끼리인지에 따라 쓰는 방식이 달라집니다. 아래 표로 정리해보겠습니다.

02 통신 방향에 따른 분류

데이터가 양쪽으로 가는지, 한쪽으로만 가는지에 따른 구분

이번에는 데이터가 어느 방향으로 흐르는지를 기준으로 나눠보겠습니다. 양방향, 반양방향, 단방향 통신, 이렇게 세 가지로 구분되는데, 일상에서 쓰는 비유로 생각하면 훨씬 쉽게 와닿을 것입니다.

03 동기화 여부에 따른 분류

대기가 있는 통신 vs 대기가 없는 통신

전역 변수를 사용하는 통신에는 큰 문제가 하나 있습니다. 받는 쪽이 데이터가 언제 도착할지 전혀 알 수 없다는 점입니다. 그래서 받는 쪽은 전역 변수의 값을 계속 반복해서 확인해야 하는데, 이렇게 상태가 바뀌었는지 보려고 반복문을 무한히 돌리며 기다리는 것을 바쁜 대기(busy waiting)라고 합니다.

⚠️ 바쁜 대기(Busy Waiting)란
데이터가 도착했는지 확인하려고 CPU가 반복문을 계속 돌리며 점검하는 것입니다. 메신저 알림이 없어서 새 메시지가 왔는지 계속 새로고침하는 모습과 비슷하다고 생각하면 됩니다. 이렇게 하면 CPU 자원을 낭비하게 된다는 점이 단점입니다.

이 문제를 해결하려고 등장한 개념이 바로 동기화(synchronization)입니다. 메신저에서 새 메시지가 왔다고 알려주는 알림 기능이 동기화의 대표적인 예라고 보면 됩니다. 그리고 이 동기화 기능을 지원하느냐에 따라 IPC는 다시 두 가지로 나뉩니다.

대기가 없는 통신은 통신 오버헤드(추가로 드는 처리 부담)는 적지만, 바쁜 대기처럼 직접 처리해야 할 작업이 많다는 단점이 있습니다. 전역 변수처럼 공유 메모리를 이용해도 보내는 쪽과 받는 쪽이 자동으로 동기화되는 것은 아니라는 점도 기억해 둘 필요가 있습니다.

04 실제로 쓰이는 IPC의 종류

전역 변수 · 파일 · 파이프 · 소켓

지금까지 살펴본 분류를 실제 구현 방식으로 옮겨보면 아래 네 가지로 정리할 수 있습니다. 각각 방향성과 동기화 지원 여부가 다르다는 점에 주목하면서 보면 훨씬 외우기 쉬울 것입니다.

📖 시험·면접에 자주 나오는 IPC 방식 — 강의노트 외 보완
여기서 잠깐 짚어보겠습니다. 강의노트에는 없지만 시험이나 면접에서 자주 물어보는 방식이 두 가지 있습니다.
· 공유 메모리(Shared Memory) : 프로세스들이 메모리의 특정 구간을 함께 쓰는 방식입니다. 운영체제(중개자) 없이 직접 접근하기 때문에 속도가 가장 빠르지만, 충돌을 막기 위한 동기화 작업은 직접 신경 써야 합니다.
· 메시지 큐(Message Queue) : 커널이 제공하는 큐를 통해 메시지 단위로 데이터를 주고받는 방식입니다. 운영체제가 동기화를 알아서 처리해주기 때문에 비교적 안전합니다.

📖 이름 없는 파이프 vs 이름 있는 파이프
보통 '파이프'라고 하면 이름 없는 파이프를 가리킵니다. 부모-자식 프로세스처럼 서로 관련 있는 프로세스 간 통신에 쓰입니다. 반면 이름 있는 파이프는 FIFO라는 특수 파일을 이용하는데, 서로 관련 없는 프로세스끼리도 통신할 수 있다는 점이 다릅니다.

참고로 전역 변수는 동기화 기능이 없어서 open()·close() 같은 함수를 쓸 필요가 없습니다. 하지만 파일·파이프·소켓 같은 나머지 통신 방식은 모두 open()으로 준비하고 close()로 마무리하는 절차를 거친다는 점도 기억해 둘 필요가 있습니다.

05 프로세스 동기화와 공유 자원, 임계구역

왜 동시에 접근하면 문제가 생길까

📖 프로세스 동기화(Process Synchronization)
프로세스들이 서로 동작을 맞추는 것, 다시 말해 프로세스들이 서로 정보를 공유하는 것을 뜻합니다. 다중 프로그래밍 시스템에는 여러 프로세스가 동시에 존재하면서 서로 독립적으로 움직이는데, 이때 서로의 상태를 전혀 모르는 채로 두면(비동기적 프로세스) 문제가 생길 수 있습니다.

공유 자원과 임계구역

공유 자원(shared resource)은 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말합니다. 같이 쓰는 자원이다 보니, 누가 언제 읽고 쓰느냐에 따라 결과가 달라질 수 있습니다. 이렇게 접근 순서에 따라 실행 결과가 달라지는 프로그램 영역을 임계구역(critical section)이라고 부릅니다.

대표적인 예로 은행 계좌를 들 수 있습니다. 잔액을 확인하고, 입금을 처리하고, 새 잔액을 저장하는 이 일련의 과정이 바로 임계구역입니다.

❌ 동시 접근 시 생기는 문제
① 잔액 확인 후 ② 입금 처리 사이에 다른 프로세스가 끼어들어 같은 잔액을 읽고 다른 입금을 처리하면, ③ 저장 단계에서 한쪽 입금 내용이 사라질 수 있습니다. 그래서 임계구역에서는 프로세스들이 동시에 작업하면 안 되며, 한 프로세스가 들어가 있으면 다른 프로세스는 밖에서 기다려야 합니다.

06 임계구역, 어떻게 해결할까

해결 조건 3가지와 대표 알고리즘

임계구역 문제를 제대로 해결했다고 말하려면 아래 세 가지 조건을 모두 만족해야 합니다.

이 조건들을 만족시키기 위한 알고리즘들은 시간이 지나면서 점점 발전해왔습니다. 하나씩 살펴보겠습니다.

📖 뮤텍스(Mutex) vs 세마포어(Semaphore) — 강의노트 외 보완
· 뮤텍스 : 임계구역에 오직 1개의 프로세스만 들어갈 수 있게 하는 상호 배제용 락(lock)입니다. 화장실 칸이 1개뿐이라 열쇠를 가진 사람만 들어가고, 나오면서 다음 사람에게 열쇠를 넘겨주는 방식과 같습니다.
· 세마포어 : 지정한 변수(카운터)만큼 여러 프로세스가 동시에 들어갈 수 있습니다. 칸이 여러 개라 빈 칸 수를 전광판으로 알려주는 방식에 가깝습니다.
→ 둘 다 동기화 도구지만, 뮤텍스는 '딱 하나만', 세마포어는 '정해진 개수만큼' 허용한다는 점이 핵심 차이입니다.

✓ 세마포어를 쉽게 떠올리는 법
화장실 칸이 여러 개 있고, 입구에 '빈 칸 개수'를 보여주는 전광판이 달려 있다고 생각하면 됩니다. 누군가 들어가면 숫자가 하나 줄고, 나오면 다시 하나 늘어납니다. 기다리는 사람은 문을 일일이 두드릴 필요 없이 전광판 숫자만 보면 되므로 바쁜 대기를 하지 않아도 됩니다.

📌 핵심 정리

· 프로세스 간 통신(IPC) : 프로세스가 다른 프로세스와 데이터를 주고받는 것, 범위에 따라 내부·간·네트워크 통신으로 구분
· 통신 방향 : 양방향(소켓), 반양방향(무전기), 단방향(전역 변수·파이프)
· 동기화 여부 : 대기가 있는 통신(파이프·소켓) vs 대기가 없는 통신(전역 변수·파일)
· 공유 자원·임계구역 : 공동으로 쓰는 자원에 접근하는 코드 영역, 접근 순서에 따라 결과가 달라짐
· 임계구역 해결 조건 : 상호 배제·한정 대기·진행
· 해결 알고리즘 : 데커 → 피터슨 → 세마포어 → 모니터로 발전

태그 : 프로세스 간 통신이란IPC 종류 정리임계구역이란상호배제 한정대기 진행의융통성세마포어란데커 알고리즘 피터슨 알고리즘파이프 소켓 차이동기화 비동기화 통신 차이공유자원 임계구역운영체제 프로세스 동기화