CPU 스케줄링 심화와 프로세스 동기화 도입

운영체제(OS)의 핵심 기능 중 하나인 CPU 스케줄링과, 여러 프로세스가 협력하거나 경쟁할 때 발생하는 문제인 동기화(Synchronization)에 대해 알아보겠습니다. 이 글은 KOCW에 공개된 반효경 교수님의 운영체제 강의 중 CPU 스케줄링 파트 2와 프로세스 동기화 도입 부분을 바탕으로 정리했습니다.

참고 강의 링크: 이화여자대학교 반효경 교수 - 운영체제 (KOCW)

스케줄링, 왜 필요할까요? (FCFS의 한계)

운영체제 앞에는 다양한 종류의 작업(Job) 또는 프로세스(Process)들이 CPU를 사용하기 위해 줄을 서 있습니다. 가장 간단한 스케줄링 방법은 먼저 온 순서대로 처리하는 FCFS(First Come First Served)입니다. 하지만 이 방식에는 치명적인 단점이 있습니다.

FCFS의 문제점: 만약 실행 시간이 매우 긴 프로세스(예: 대규모 계산 작업)가 먼저 CPU를 점유하면, 그 뒤에 있는 짧고 사용자와 상호작용이 잦은 프로세스(예: 워드 프로세서, 웹 브라우저)들은 하염없이 기다려야 합니다. 이는 시스템 전체의 처리 효율을 떨어뜨리고, 특히 사용자 입장에서는 응답성(Responsiveness)이 매우 나빠지는 결과를 초래합니다. (이를 콘보이 효과(Convoy Effect)라고도 합니다.)

이런 비효율을 해결하고 모든 프로세스에게 공정한 기회를 제공하기 위해 더 발전된 스케줄링 기법이 필요합니다. 그 대표적인 예가 바로 라운드 로빈(Round Robin)입니다.

[Q&A]

Q: "FCFS는 간단한데 왜 현대 운영체제에서 잘 사용하지 않나요? 어떤 경우에 특히 문제가 되나요?"
A: FCFS는 구현이 매우 간단하지만, 평균 대기 시간(Average Waiting Time)이 길어질 수 있고 특히 대화형 시스템(Interactive System)에서는 사용자 경험을 크게 저하시킵니다. 짧은 작업을 처리하기 위해 키보드 입력에 바로 반응해야 하는 워드 프로세서 같은 프로그램이, 앞에서 실행 중인 몇 시간짜리 과학 계산 작업 때문에 멈춰있다고 상상해 보세요. 현대 OS는 다양한 종류의 작업을 효율적으로 처리해야 하므로 FCFS만으로는 부족합니다.

라운드 로빈 (Round Robin, RR): 공정한 기회의 분배

라운드 로빈은 시분할 시스템(Time-Sharing System)을 위해 설계된 가장 대표적이고 공정한 스케줄링 기법 중 하나입니다.

동작 방식:
1. 모든 프로세스에게 동일한 크기의 CPU 사용 시간 할당량(Time Quantum 또는 Time Slice)을 부여합니다. (보통 10-100ms)
2. 프로세스는 할당된 시간만큼 CPU를 사용합니다.
3. 시간이 만료되면(타이머 인터럽트 발생), 해당 프로세스는 CPU를 내놓고 준비 큐(Ready Queue)의 맨 뒤로 들어갑니다.
4. CPU 스케줄러는 준비 큐의 다음 프로세스에게 CPU를 할당합니다.
가능한 이유: 운영체제의 문맥 교환(Context Switching) 메커니즘 덕분입니다. 프로세스가 CPU를 내놓을 때 현재 상태(레지스터 값, PC 등)를 PCB(Process Control Block)에 저장하고, 새로 CPU를 받는 프로세스의 상태를 PCB에서 복구하여 실행을 이어갈 수 있습니다.
장점: 모든 프로세스가 CPU 시간을 공평하게 나눠 가지므로 응답성이 빠르고 기아(Starvation) 현상이 발생하지 않습니다.
단점: 정해진 시간마다 문맥 교환이 발생하므로 문맥 교환 오버헤드가 커질 수 있습니다. 타임 퀀텀 크기 설정이 중요합니다.

홍대에 "라운드 로빈식 화장실"이 있다는 도시괴담(?)이 있다고 합니다. 5분 안에 볼일을 마치지 못하면 문이 자동으로 열린다는..

[Q&A]

Q: "타임 퀀텀(Time Quantum) 크기는 어떻게 정해야 할까요? 너무 크거나 작으면 어떤 문제가 생기나요?"
A: 타임 퀀텀 크기는 시스템 성능에 큰 영향을 미칩니다.
- 너무 크면: FCFS와 비슷해져서 응답성이 나빠질 수 있습니다. 긴 프로세스가 한 번 CPU를 잡으면 오래 사용하게 됩니다.
- 너무 작으면: 문맥 교환이 너무 자주 발생하여 오버헤드가 커지고 실제 작업 처리 시간 비율이 줄어듭니다.
- 일반적으로 대부분의 CPU 버스트(Burst)가 타임 퀀텀 안에 끝날 수 있도록 설정하는 것이 좋습니다 (예: 80% 정도).
Q: "RR은 공정한데, 왜 다른 스케줄링 기법도 필요한가요?"
A: RR은 공정하지만 모든 프로세스를 동일하게 취급합니다. 하지만 실제 시스템에는 우선순위가 더 높은 작업(예: 시스템 프로세스)이나 특성이 다른 작업(CPU 집중 작업 vs I/O 집중 작업)이 혼재합니다. 이런 다양한 요구사항을 만족시키기 위해 더 복잡한 스케줄링 기법들이 필요합니다.

멀티레벨 큐 스케줄링 (Multi-Level Queue Scheduling, MLQ): 우선순위에 따른 차등 대우

프로세스들을 서로 다른 그룹(큐)으로 나누어 관리하는 방식입니다. 각 그룹은 고유한 우선순위를 가집니다.

구조:
- 준비 큐(Ready Queue)를 여러 개로 분할합니다.
- 각 큐는 서로 다른 우선순위를 가지며, 독립적인 스케줄링 알고리즘을 사용할 수 있습니다. (예: 상위 큐는 RR, 하위 큐는 FCFS)
- 예시 큐 분류:
  1. 시스템 프로세스 큐: 가장 높은 우선순위 (OS 커널 등)
  2. 대화형 프로세스 큐: 사용자 입력/출력이 잦은 프로세스 (편집기, 웹 브라우저 등)
  3. 백그라운드(배치) 프로세스 큐: CPU 계산 위주의 프로세스
  4. (농담) 학생 프로세스 큐?: 가장 낮은 우선순위... (실제 전공 서적에 이렇게 나와있다고 한다..)
특징:
- 프로세스는 생성될 때 자신의 특성(출신?)에 맞는 큐에 배정되며, 기본적으로 다른 큐로 이동하지 않습니다. (고정)
- 우선순위가 다른 프로세스들을 차별적으로 관리할 수 있습니다.
큐 간 스케줄링 방식:
- 고정 우선순위 스케줄링 (Fixed Priority Scheduling):
  - 무조건 우선순위가 가장 높은 큐에 있는 프로세스부터 실행합니다.
  - 상위 큐가 비어 있어야만 하위 큐의 프로세스가 실행될 기회를 얻습니다.
  - 단점: 하위 큐의 프로세스는 기아(Starvation) 상태에 빠질 수 있습니다.
- 타임 슬라이스 방식 (Time Slice):
  - 각 큐에 CPU 시간을 일정 비율로 할당합니다.
  - 예: 포그라운드(대화형) 큐에 80%, 백그라운드 큐에 20% 할당.
  - 하위 큐도 실행 기회를 보장받을 수 있습니다.

[Q&A]

Q: "프로세스를 왜 큐에 고정시키나요? 유연성이 떨어지지 않나요?"
A: 맞습니다. MLQ의 가장 큰 단점 중 하나가 유연성 부족입니다. 프로세스의 특성이 실행 중에 변할 수도 있는데(예: 처음엔 I/O 위주였다가 나중에 CPU 위주로), 큐를 이동할 수 없으면 비효율이 발생할 수 있습니다. 또한, 낮은 우선순위 큐의 기아 문제도 해결하기 어렵습니다. 이런 단점을 보완한 것이 멀티레벨 피드백 큐입니다.
Q: "고정 우선순위 스케줄링에서 기아(Starvation) 문제를 해결할 방법은 없나요?"
A: 에이징(Aging) 기법을 사용할 수 있습니다. 오랫동안 대기한 하위 큐의 프로세스 우선순위를 점진적으로 높여주어 언젠가는 실행될 기회를 얻도록 하는 방식입니다. 하지만 MLQ 자체의 특징은 큐 이동이 없다는 것이므로, 에이징은 보통 다음 설명할 MLFQ에서 더 적극적으로 활용됩니다.

멀티레벨 피드백 큐 (Multilevel Feedback Queue, MLFQ): 움직이는 우선순위

MLQ의 단점(고정된 우선순위, 기아 가능성)을 개선한, 현재 많은 운영체제에서 사용하는 가장 일반적인 스케줄링 방식 중 하나입니다.

핵심 특징:
- 프로세스가 큐 사이를 이동할 수 있습니다! (피드백)
- 프로세스의 최근 CPU 사용 패턴을 보고 동적으로 우선순위를 조정합니다.
동작 방식 (일반적인 예):
1. 새로운 프로세스는 가장 높은 우선순위 큐에 들어갑니다. (짧은 작업일 것이라 기대)
2. 높은 우선순위 큐에서는 짧은 타임 퀀텀의 RR 방식으로 실행됩니다.
3. 만약 프로세스가 할당된 타임 퀀텀을 다 사용하면 (CPU 위주 작업으로 판단), 한 단계 낮은 우선순위 큐로 강등됩니다. 낮은 큐는 보통 더 긴 타임 퀀텀을 갖거나 FCFS 방식으로 동작합니다.
4. 만약 프로세스가 타임 퀀텀을 다 쓰기 전에 I/O 작업 등으로 CPU를 스스로 반납하면 (대화형 작업으로 판단), 원래 우선순위를 유지하거나 높은 큐에 머뭅니다.
5. 에이징(Aging): 낮은 우선순위 큐에서 너무 오래 대기한 프로세스는 상위 큐로 승격시켜 기아를 방지합니다.
장점:
- CPU 버스트 시간이 짧은 프로세스(대화형)에 유리하여 응답성이 좋습니다.
- 별도로 CPU 버스트 시간을 예측할 필요가 없습니다(SJF의 단점 극복).
- 에이징을 통해 기아 문제를 해결할 수 있습니다.
단점: 설계 및 구현이 매우 복잡합니다. 성능은 다음 파라미터 설정에 크게 의존합니다.
- 큐의 개수
- 각 큐의 스케줄링 알고리즘
- 프로세스 승격(Aging) 조건
- 프로세스 강등 조건
- 프로세스가 처음 들어갈 큐 결정 기준

[Q&A]

Q: "MLFQ는 어떻게 SJF(Shortest Job First)의 장점을 가지면서 CPU 버스트 예측 문제를 해결하나요?"
A: MLFQ는 CPU 사용 시간을 피드백으로 삼아 프로세스의 특성을 추정합니다. 짧은 시간 안에 CPU를 반납하는 프로세스(아마도 짧은 버스트)는 높은 우선순위를 유지시켜 빨리 처리하고, CPU를 오래 사용하는 프로세스(아마도 긴 버스트)는 낮은 우선순위로 보내 나중에 처리합니다. 즉, 실행 이력을 바탕으로 짧은 작업을 간접적으로 선호하게 만들어 SJF와 유사한 효과(낮은 평균 대기 시간)를 내면서도, 미래의 버스트 시간을 미리 알 필요가 없는 것입니다.
Q: "승격/강등 조건은 어떻게 정하는 것이 가장 효과적일까요?"
A: 정답은 없습니다. 시스템의 목적(대화형 응답성 중시 vs 전체 처리량 중시)과 작업 부하 특성에 따라 달라집니다. 너무 자주 승격/강등하면 오버헤드가 크고, 너무 안 하면 MLFQ의 장점이 사라집니다. 일반적으로 타임 퀀텀 소진 여부, 대기 시간 등을 기준으로 하며, 실제 시스템에서는 경험적인 값과 튜닝을 통해 최적의 파라미터를 찾아갑니다.

다중 프로세서 스케줄링: 여러 개의 CPU를 효율적으로

여러 개의 CPU 코어를 가진 시스템에서의 스케줄링 문제입니다.

고려 사항:
- 프로세서 종류:
  - 동종 프로세서 (Homogeneous Processors): 모든 CPU가 동일한 성능과 기능을 가집니다. 프로세스를 아무 CPU에나 할당할 수 있어 유연합니다. (현재 대부분의 멀티코어 시스템)
  - 이종 프로세서 (Heterogeneous Processors): CPU마다 성능이나 기능이 다를 수 있습니다. 특정 작업은 특정 CPU에만 할당해야 할 수도 있습니다.
- 부하 공유/분산 (Load Sharing/Balancing): 특정 CPU에만 작업이 몰리지 않도록 여러 CPU에 작업을 균등하게 분배하는 것이 중요합니다.
  - 큐 구조:
    - 공용 준비 큐 (Common Ready Queue): 모든 CPU가 하나의 큐에서 작업을 가져갑니다. 구현이 간단하고 부하 분산이 자동적이지만, 큐 접근 시 동기화 문제(병목)가 발생할 수 있습니다.
    - CPU별 전용 큐 (Private Ready Queue): 각 CPU가 자신만의 큐를 가집니다. 동기화 문제는 적지만, CPU 간 부하 불균형이 발생할 수 있어 주기적인 부하 분산 작업이 필요할 수 있습니다.
스케줄링 방식:
- SMP (Symmetric Multiprocessing - 대칭적 다중 처리):
  - 가장 일반적인 방식. 모든 CPU가 동등한 입장에서 각자 알아서 준비 큐에서 프로세스를 가져와 실행합니다. 운영체제 커널 코드도 여러 CPU에서 동시에 수행될 수 있습니다.
- AMP (Asymmetric Multiprocessing - 비대칭적 다중 처리):
  - 하나의 CPU(마스터 CPU)가 시스템 전체의 스케줄링 및 데이터 접근을 책임지고, 나머지 CPU(슬레이브 CPU)는 마스터의 지시에 따라 작업을 수행합니다. 구현은 단순하지만 마스터 CPU에 병목이 생길 수 있습니다.

[Q&A]

Q: "CPU마다 별도의 큐를 두는 것과 공용 큐를 사용하는 것의 장단점은 무엇인가요?"
A:
- 공용 큐: 장점 - 구현 간단, 자동 부하 분산. 단점 - 큐 접근 시 락(Lock) 필요로 인한 병목 가능성, 캐시 효율성 저하(프로세스가 다른 CPU로 자주 이동 시).
- 전용 큐: 장점 - 큐 접근 병목 없음, 캐시 효율성 향상(프로세스가 특정 CPU에 머무를 가능성 높음 - Affinity). 단점 - 부하 불균형 발생 가능, 이를 해결하기 위한 추가적인 부하 분산 메커니즘 필요.
Q: "SMP 환경에서 스케줄링할 때 특별히 고려해야 할 점은 무엇인가요? (예: 캐시 일관성)"
A: SMP에서는 여러 CPU가 메모리를 공유하므로 캐시 일관성(Cache Coherency) 유지가 매우 중요합니다. 한 CPU가 데이터를 수정했을 때 다른 CPU의 캐시에 있는 이전 데이터가 무효화되어야 합니다. 스케줄링 관점에서는 프로세서 선호도(Processor Affinity)를 고려할 수 있습니다. 즉, 특정 프로세스를 가능하면 이전에 실행했던 CPU에 다시 할당하여 캐시된 데이터를 재활용함으로써 성능을 높이는 방식입니다(Soft Affinity). 반대로 특정 CPU에만 실행되도록 강제할 수도 있습니다(Hard Affinity). 또한, 여러 CPU가 커널 자료구조(예: 준비 큐)에 동시에 접근할 때 발생할 수 있는 동기화 문제를 해결해야 합니다.

실시간 스케줄링: 마감 시한은 반드시!

정해진 마감 시한(Deadline) 안에 반드시 작업을 완료해야 하는 시스템을 위한 스케줄링입니다.

리얼타임 시스템의 종류:
- 하드 리얼타임 (Hard Real-Time): 마감 시한을 절대로 놓쳐서는 안 되는 시스템. 데드라인을 어기면 치명적인 결과를 초래할 수 있습니다. (예: 원자력 발전소 제어, 항공기 제어 시스템, 미사일 유도 시스템)
- 소프트 리얼타임 (Soft Real-Time): 마감 시한을 지키는 것이 중요하지만, 가끔 어겨도 시스템 전체에 큰 문제가 발생하지는 않는 시스템. (예: 동영상 재생, 실시간 음성 통화 - 약간의 끊김은 발생할 수 있음)
스케줄링 목표: 일반 시스템과는 달리 처리율(Throughput)이나 평균 응답 시간보다는 마감 시한 준수가 최우선 목표입니다. 이를 위해 우선순위 기반 선점형 스케줄링(예: Rate Monotonic, Earliest Deadline First) 등이 사용됩니다.

[Q&A]

Q: "일반 운영체제 스케줄러와 리얼타임 스케줄러의 가장 큰 차이점은 무엇인가요?"
A: 가장 큰 차이는 목표와 예측 가능성입니다. 일반 스케줄러는 평균 성능(응답 시간, 처리율)과 공정성을 중시하지만, 리얼타임 스케줄러는 마감 시한 준수를 최우선으로 합니다. 따라서 리얼타임 스케줄러는 작업 수행 시간을 예측 가능하게 만들고, 우선순위 역전 같은 예기치 않은 지연 요소를 최소화하는 데 중점을 둡니다.

스레드 스케줄링: 프로세스 안의 작은 실행 단위들

현대 운영체제는 프로세스보다 더 작은 실행 단위인 스레드(Thread)를 지원합니다. 스레드는 프로세스 내의 코드, 데이터, 힙 영역을 공유하며 실행됩니다.

스케줄링 수준:
- 유저 레벨 스레드 (User-level Threads):
  - 커널은 스레드의 존재를 모릅니다. 스레드 생성, 스케줄링, 관리가 모두 사용자 공간의 라이브러리에 의해 이루어집니다. (예: 과거 Green Thread, Go 언어의 Goroutine)
  - 장점: 문맥 교환(라이브러리 함수 호출)이 매우 빠릅니다. 커널의 개입이 없습니다.
  - 단점: 하나의 스레드가 시스템 콜 등으로 커널에서 블록(Block)되면, 해당 프로세스 내의 모든 스레드가 같이 블록됩니다. (커널은 프로세스 단위로 스케줄링하므로) 멀티코어 CPU를 효율적으로 활용하기 어렵습니다.
  - 스케줄링: 라이브러리 수준에서 수행 (Local Scheduling).
- 커널 레벨 스레드 (Kernel-level Threads):
  - 커널이 직접 스레드의 존재를 인지하고 관리합니다. 스레드 생성, 스케줄링이 모두 커널에 의해 이루어집니다. (현재 대부분의 OS - Windows, Linux, macOS 등)
  - 장점: 하나의 스레드가 블록되어도 다른 스레드는 계속 실행될 수 있습니다. 멀티코어 CPU 환경에서 병렬 처리가 가능합니다.
  - 단점: 스레드 생성 및 문맥 교환 시 커널의 개입이 필요하므로 유저 레벨 스레드보다 오버헤드가 큽니다.
  - 스케줄링: 커널 스케줄러가 직접 수행 (Global Scheduling).

[Q&A]

Q: "User-level 스레드와 Kernel-level 스레드 중 어떤 것이 더 좋은 방식인가요? 상황에 따라 다른가요?"
A: 각각 장단점이 있어 상황에 따라 선택이 달라집니다. 커널 레벨 스레드는 진정한 병렬 처리와 블로킹 문제 해결에 유리하여 현재 대부분의 범용 운영체제에서 표준으로 사용됩니다. 유저 레벨 스레드는 문맥 교환 오버헤드가 매우 적어 매우 많은 수의 스레드를 생성하고 관리해야 하는 특정 애플리케이션(예: 고성능 비동기 I/O 서버, Go 언어)에서 효율적일 수 있습니다. 최근에는 두 방식의 장점을 결합한 하이브리드 모델(M:N 모델)도 연구/사용되고 있습니다.
Q: "하나의 프로세스에 여러 스레드가 있을 때, 이 스레드들은 어떻게 스케줄링되나요?"
A: 커널 레벨 스레드의 경우, 커널 스케줄러는 스레드를 독립적인 실행 단위로 간주하고 스케줄링합니다. 즉, 같은 프로세스 내의 스레드들이라도 CPU 시간을 얻기 위해 다른 프로세스의 스레드들과 경쟁합니다. OS 스케줄러는 프로세스 우선순위뿐만 아니라 스레드 우선순위도 고려할 수 있습니다. 유저 레벨 스레드는 커널이 아닌 사용자 라이브러리가 스케줄링하므로, 커널은 해당 프로세스 자체에 CPU 시간을 할당하고, 그 시간 안에서 라이브러리가 내부 스레드들을 번갈아 실행시키는 방식입니다.

스케줄링 알고리즘, 어떻게 평가할까?

다양한 스케줄링 알고리즘 중 어떤 것이 더 좋은지 평가하는 방법은 여러 가지가 있습니다.

큐잉 모델 (Queueing Models):
- 시스템을 도착률(Arrival Rate), 서비스율(Service Rate) 등을 가진 확률적 대기열 모델로 분석합니다.
- 수학 공식을 이용해 평균 대기 시간, 처리율 등을 이론적으로 예측합니다.
- 장점: 구현 없이 빠르게 결과를 얻을 수 있음.
- 단점: 실제 시스템의 복잡한 동작을 정확히 반영하기 어려움. 가정이 단순화될 수 있음.
구현 및 측정 (Implementation & Measurement):
- 실제 운영체제 커널에 새로운 스케줄링 알고리즘을 직접 구현합니다.
- 실제 작업 부하(Workload)를 시스템에 적용하여 성능 지표(CPU 활용률, 응답 시간 등)를 직접 측정하고 비교합니다.
- 장점: 가장 정확하고 신뢰성 있는 결과를 얻을 수 있습니다.
- 단점: 구현 및 테스트에 매우 많은 비용과 시간, 노력이 필요합니다. 진입 장벽이 높습니다.
시뮬레이션 (Simulation):
- 스케줄링 알고리즘의 동작을 프로그램 코드로 모의 구현(시뮬레이터)합니다.
- 실제 시스템에서 수집된 작업 부하 데이터(Trace Data)를 시뮬레이터에 입력하여 알고리즘의 성능을 모의 실험합니다.
- 장점: 구현/측정보다 비용과 시간이 적게 들면서도, 실제 트레이스 데이터를 사용하므로 큐잉 모델보다 현실적인 결과를 얻을 가능성이 높습니다. 다양한 알고리즘과 파라미터를 쉽게 비교 테스트할 수 있습니다.
- 단점: 시뮬레이션 모델의 정확성, 트레이스 데이터의 대표성에 결과가 의존합니다.

[Q&A]

Q: "세 가지 평가 방법 중 어떤 것이 가장 정확한가요? 각각의 장단점은 무엇인가요?"
A: 정확성 측면에서는 구현 및 측정이 가장 높습니다. 실제 시스템에서의 성능을 직접 보기 때문입니다. 하지만 비용과 노력이 가장 많이 듭니다. 시뮬레이션은 비용 대비 현실적인 결과를 얻을 수 있어 널리 사용되는 균형 잡힌 접근 방식입니다. 큐잉 모델은 초기 분석이나 이론적 비교에는 유용하지만 실제 성능과는 차이가 클 수 있습니다. 따라서 연구나 개발 목적에 따라 적절한 방법을 선택하거나 여러 방법을 조합하여 사용합니다.

프로세스 동기화 (Process Synchronization) 입문: 함께 일할 때 조심해야 할 것들

지금까지는 CPU를 어떻게 '잘 나눠 쓸까'에 집중했다면, 이제는 여러 프로세스(또는 스레드)가 '함께 일할 때' 발생할 수 있는 문제와 해결 방법에 대해 알아볼 차례입니다.

배경: 공유 자원과 동시 접근

현대 컴퓨터 시스템은 멀티태스킹, 멀티프로세싱 환경이 기본입니다. 여러 프로세스 또는 스레드가 동시에 실행되면서 공유 자원(Shared Resource)에 접근하는 경우가 많습니다. 여기서 공유 자원이란 메모리의 특정 변수, 파일, 커널 내부 데이터 구조 등을 의미합니다.

문제는 여러 실행 단위가 이러한 공유 자원에 동시에 접근하여 수정(Write)하려고 할 때 발생합니다. 특히 멀티프로세서(Multi-processor) 시스템이나 공유 메모리(Shared Memory) 구조에서는 이러한 동시 접근 가능성이 더욱 높아집니다.

경쟁 상태 (Race Condition): 누가 먼저 하느냐에 따라 결과가 달라진다!

정의: 두 개 이상의 프로세스(또는 스레드)가 동시에 공유 데이터에 접근하여 수정하려고 할 때, 접근(실행) 순서에 따라 실행 결과가 달라지는 예측 불가능한 상황을 의미합니다.
왜 발생할까? 우리가 코드 한 줄로 작성한 연산(예: x = x + 1)도 실제 기계어 수준에서는 여러 단계(명령어)로 나뉘어 실행됩니다. 이 명령어들 사이사이에 다른 프로세스의 명령어가 끼어들(Interleaving) 수 있기 때문입니다.

예시: x = x + 1 연산의 함정 (초기 x=5 가정)

이 코드는 실제로는 대략 다음과 같은 기계어 명령으로 변환될 수 있습니다.
1. load : 메모리에서 x 값을 레지스터(CPU 내 임시 저장 공간, 예: reg1)로 읽어온다.
2. inc : 레지스터(reg1) 값을 1 증가시킨다.
3. store: 레지스터(reg1)의 값을 다시 메모리 x에 저장한다.
시나리오: 프로세스 A와 B가 동시에 x = x + 1 실행

시간	프로세스 A (reg_A)	프로세스 B (reg_B)	메모리 x	설명
T1	load x (reg_A=5)		5	A가 x 로드
T2	inc reg_A (reg_A=6)		5	A가 레지스터 값 증가
T3		load x (reg_B=5)	5	Context Switch! B가 x 로드 (아직 A는 저장 안 함)
T4		inc reg_B (reg_B=6)	5	B가 레지스터 값 증가
T5		store reg_B (x=6)	6	B가 결과 저장
T6	store reg_A (x=6)		6	Context Switch! A가 결과 저장 (B의 결과를 덮어씀)

결과: 두 프로세스가 각각 1씩 증가시켰으므로 최종 결과는 7이 되어야 하지만, 경쟁 상태로 인해 6이라는 잘못된 결과가 나왔습니다! 실행 순서가 달라지면 7이 나올 수도 있습니다. 이것이 바로 Race Condition입니다.

[Q&A]

Q: "x = x + 1 연산이 왜 원자적(atomic)이 아닌가요? 기계어 수준에서는 어떻게 동작하나요?"
A: 원자적 연산이란 중간에 다른 작업이 끼어들 수 없이 한 번에 완료되는 연산을 의미합니다. 고급 언어에서 한 줄인 x = x + 1은 컴파일러에 의해 여러 개의 기계어 명령(메모리 로드, 레지스터 증가, 메모리 저장)으로 변환됩니다. CPU는 이 기계어 명령들을 하나씩 실행하는데, 각 명령어 실행 사이에는 인터럽트나 문맥 교환이 발생할 수 있습니다. 따라서 전체 x = x + 1 과정은 원자적이지 않아, 중간에 다른 프로세스가 끼어들어 공유 변수 x에 접근하면 문제가 생길 수 있는 것입니다. 일부 CPU는 특정 연산(예: 특정 조건 하의 증가)에 대해 원자적 명령어를 제공하기도 합니다.

경쟁 상태(Race Condition) 발생 사례

경쟁 상태는 다양한 상황에서 발생할 수 있습니다.

커널 코드 수행 중 인터럽트 발생:
- 커널이 공유 변수(예: 특정 자원의 개수를 세는 count)를 수정하는 코드(count++)를 실행하는 도중에 인터럽트가 발생합니다.
- 인터럽트 서비스 루틴(ISR)이 실행되면서 동일한 공유 변수 count를 수정(count--)합니다.
- 인터럽트 처리가 끝나고 원래 커널 코드로 복귀하여 나머지 작업을 수행하면, count 값이 예상과 달라질 수 있습니다. (위 x = x + 1 예시와 유사한 문제 발생 가능)
시스템 콜 수행 중 문맥 교환 발생 (커널 선점):
- 프로세스 A가 시스템 콜(예: read())을 호출하여 커널 모드에서 실행 중입니다. 커널 코드가 공유 데이터(예: 파일 관련 커널 자료구조)를 접근합니다.
- 이때 타임 퀀텀 만료 등으로 인해 CPU 스케줄러가 프로세스 A의 실행을 중단시키고(선점, Preemption) 프로세스 B에게 CPU를 넘깁니다.
- 프로세스 B도 시스템 콜을 호출하여 커널 모드에서 실행되며 동일한 공유 데이터를 수정합니다.
- 다시 프로세스 A에게 CPU가 돌아와 중단됐던 커널 코드부터 실행을 재개하면, 공유 데이터의 일관성이 깨져 있을 수 있습니다.
- 일반적인 해결책: 커널 모드에서 실행 중일 때는 임의의 선점(Preemption)을 금지합니다. 커널 작업이 끝나고 사용자 모드로 돌아가기 직전에만 선점이 가능하도록 허용하여 커널 데이터의 일관성을 유지합니다. (Non-preemptive Kernel의 경우) 또는 커널 내 공유 데이터 접근 시 짧은 시간 동안만 락(Lock)을 사용하는 방식도 있습니다 (Preemptive Kernel).
멀티프로세서(Multiprocessor) 환경:
- CPU가 여러 개이므로, 두 개 이상의 CPU가 동시에 커널 코드를 실행할 수 있습니다.
- 이 경우, 단순히 인터럽트를 비활성화하거나 커널 선점을 막는 것만으로는 동기화 문제를 해결할 수 없습니다. 왜냐하면 다른 CPU가 동시에 같은 공유 데이터에 접근할 수 있기 때문입니다.
- 근본적인 해결책: 여러 CPU가 공유 데이터에 접근하는 코드 영역(Critical Section)에 대해 락(Lock) 메커니즘을 사용하여 한 번에 하나의 CPU(또는 프로세스/스레드)만 접근하도록 명시적으로 제어해야 합니다.

[Q&A]

Q: "단일 CPU 환경에서 커널 모드 수행 중 선점(Preemption)을 막는 것만으로 동기화 문제가 완전히 해결되나요?"
A: 커널 선점으로 인한 경쟁 상태는 막을 수 있지만, 인터럽트로 인한 경쟁 상태는 여전히 발생할 수 있습니다. 커널이 공유 데이터를 조작하는 매우 민감한 코드(Critical Section)를 실행하는 동안에는 인터럽트까지 비활성화해야 완벽한 동기화를 보장할 수 있습니다. 하지만 인터럽트를 너무 오랫동안 비활성화하면 시스템 반응성이 떨어지므로, 꼭 필요한 최소한의 구간에서만 사용해야 합니다.
Q: "멀티프로세서 환경에서는 왜 인터럽트를 막는 것만으로는 부족한가요?"
A: 한 CPU에서 인터럽트를 막더라도, 다른 CPU는 여전히 동작하며 커널 코드에 진입하여 동일한 공유 메모리(데이터)에 접근할 수 있기 때문입니다. 즉, 여러 실행 흐름이 '물리적으로 동시에' 공유 자원에 접근 가능하므로, 인터럽트 제어만으로는 동시 접근 자체를 막을 수 없습니다. 반드시 락(Lock)과 같은 명시적인 동기화 기법이 필요합니다.

임계 구역 (Critical Section): 보호가 필요한 코드 영역

정의: 둘 이상의 프로세스(또는 스레드)가 **동시에 접근하면 안 되는 공유 자원(데이터 또는 장치)에 접근하는 코드 영역(부분)**을 의미합니다.
핵심 요구사항: 상호 배제 (Mutual Exclusion)
- 어떤 프로세스가 자신의 임계 구역에서 실행 중이라면, 다른 어떤 프로세스도 자신의 임계 구역에 진입할 수 없어야 합니다. 즉, 한 번에 하나의 프로세스만 임계 구역 내 코드를 실행할 수 있도록 보장해야 합니다.
예시:위 코드에서 x = x + 1;과 x = x - 1; 부분이 바로 임계 구역입니다. 이 두 부분이 동시에 실행되지 않도록 보호하는 메커니즘이 필요합니다.

// 공유 변수 x
int x = 0;

// 프로세스 P1
void process_P1() {
    // ... non-critical section ...
    // Entry Section (진입 허가 확인)
    { // --- Critical Section Start ---
        x = x + 1; // 공유 변수 접근
    } // --- Critical Section End ---
    // Exit Section (진입 허가 반납)
    // ... remainder section ...
}

// 프로세스 P2
void process_P2() {
    // ... non-critical section ...
    // Entry Section
    { // --- Critical Section Start ---
        x = x - 1; // 공유 변수 접근
    } // --- Critical Section End ---
    // Exit Section
    // ... remainder section ...
}

다음 강의에서는 이러한 임계 구역 문제를 해결하기 위한 다양한 동기화 알고리즘들 (피터슨 알고리즘, 세마포어, 모니터 등) 에 대해 자세히 다룰 예정입니다.

[Q&A]

Q: "모든 공유 데이터 접근 코드가 임계 구역인가요? 임계 구역을 어떻게 식별해야 하나요?"
A: 아닙니다. 읽기(Read)만 하는 경우는 여러 프로세스가 동시에 접근해도 문제가 발생하지 않습니다. 임계 구역은 주로 공유 데이터를 수정(Write) 하거나, 읽기와 수정이 혼재되어 일관성이 깨질 수 있는 코드 영역을 의미합니다. 임계 구역을 식별하려면 코드 내에서 어떤 자원이 공유되고, 그 자원에 대한 연산이 원자적이지 않아 동시 접근 시 문제가 발생할 수 있는지를 분석해야 합니다. 임계 구역은 가능한 짧게 유지하는 것이 시스템 성능에 유리합니다.

[마무리하며]

효율적인 CPU 스케줄링은 시스템의 성능과 응답성을 결정하는 중요한 요소이며, MLFQ와 같은 정교한 알고리즘들이 이를 위해 사용됩니다. 하지만 여러 프로세스가 동시에 실행되는 환경에서는 공유 자원에 대한 동시 접근 문제, 즉 경쟁 상태(Race Condition)가 발생할 수 있습니다. 이를 해결하기 위해 임계 구역(Critical Section) 개념이 등장했으며, 다음 단계에서는 이 임계 구역을 보호하기 위한 다양한 동기화 기법들을 배우게 될 것입니다.

'운영체제 > 반효경 교수' 카테고리의 다른 글

운영체제: 프로세스 동기화 - 모니터 (Monitor)를 이용한 병행 제어 (0)	2025.04.13
운영체제: 프로세스 동기화 - 고전적인 동기화 문제들 (세마포어 활용) (0)	2025.04.12
운영체제: 프로세스 동기화 - 세마포어 (Semaphore) (0)	2025.04.12
운영체제: 임계 구역(Critical Section) 문제와 해결 방법 소개 (0)	2025.04.11
CPU 스케줄링 이해하기 (1): 기본 개념부터 FCFS, SJF, Priority, RR 알고리즘까지 (0)	2025.04.10

절차탁마

CPU 스케줄링 심화와 프로세스 동기화 도입

스케줄링, 왜 필요할까요? (FCFS의 한계)

라운드 로빈 (Round Robin, RR): 공정한 기회의 분배

멀티레벨 큐 스케줄링 (Multi-Level Queue Scheduling, MLQ): 우선순위에 따른 차등 대우

멀티레벨 피드백 큐 (Multilevel Feedback Queue, MLFQ): 움직이는 우선순위

다중 프로세서 스케줄링: 여러 개의 CPU를 효율적으로

실시간 스케줄링: 마감 시한은 반드시!

스레드 스케줄링: 프로세스 안의 작은 실행 단위들

스케줄링 알고리즘, 어떻게 평가할까?

프로세스 동기화 (Process Synchronization) 입문: 함께 일할 때 조심해야 할 것들

배경: 공유 자원과 동시 접근

경쟁 상태 (Race Condition): 누가 먼저 하느냐에 따라 결과가 달라진다!

경쟁 상태(Race Condition) 발생 사례

임계 구역 (Critical Section): 보호가 필요한 코드 영역

'운영체제 > 반효경 교수' 카테고리의 다른 글

티스토리툴바

CPU 스케줄링 심화와 프로세스 동기화 도입

스케줄링, 왜 필요할까요? (FCFS의 한계)

라운드 로빈 (Round Robin, RR): 공정한 기회의 분배

멀티레벨 큐 스케줄링 (Multi-Level Queue Scheduling, MLQ): 우선순위에 따른 차등 대우

멀티레벨 피드백 큐 (Multilevel Feedback Queue, MLFQ): 움직이는 우선순위

다중 프로세서 스케줄링: 여러 개의 CPU를 효율적으로

실시간 스케줄링: 마감 시한은 반드시!

스레드 스케줄링: 프로세스 안의 작은 실행 단위들

스케줄링 알고리즘, 어떻게 평가할까?

프로세스 동기화 (Process Synchronization) 입문: 함께 일할 때 조심해야 할 것들

배경: 공유 자원과 동시 접근

경쟁 상태 (Race Condition): 누가 먼저 하느냐에 따라 결과가 달라진다!

경쟁 상태(Race Condition) 발생 사례

임계 구역 (Critical Section): 보호가 필요한 코드 영역

'운영체제 > 반효경 교수' 카테고리의 다른 글

관련글

티스토리툴바