프로세스 스케줄링 완전 정리

🔷 프로세스 스케줄링 완전 정리: 컴퓨터는 어떻게 순서를 결정할까?

---

🔷 프로세스 스케줄링이란 무엇인가?

컴퓨터는 여러 프로그램을 동시에 실행하는 것처럼 보입니다.
하지만 CPU는 한 순간에 단 하나의 작업만 처리할 수 있습니다.

그렇다면 수십, 수백 개의 프로그램들은 어떻게 동시에 실행되는 것처럼 보이는 걸까요?
이 질문에 대한 답이 바로 프로세스 스케줄링(Process Scheduling)입니다.

프로세스 스케줄링이란,
운영체제(OS)가 실행 준비가 완료된 여러 프로세스 중에서
어떤 프로세스를 먼저, 얼마나 오래 CPU에 할당할지 결정하는 과정을 말합니다.

운영체제는 스케줄링을 통해 다음과 같은 목표를 달성하려고 합니다.

• 시스템 처리량(Throughput) 최대화
• 응답 시간(Response Time) 최소화
• 대기 시간(Waiting Time) 최소화
• 자원 사용률(Resource Utilization) 최적화
• 공정성(Fairness) 보장

---

🔷 프로세스 스케줄링이 필요한 이유

만약 운영체제가 프로세스 스케줄링을 하지 않는다면,

• 어떤 프로세스는 영원히 실행되지 못하고,
• 어떤 프로세스는 시스템 자원을 독점하게 됩니다.

결국 컴퓨터는 느려지고, 사용자 경험은 최악이 됩니다.

운영체제는 모든 프로세스가 공평하게 기회를 얻고,
전체 시스템 성능이 최대한 유지되도록 '순서'를 똑똑하게 조율해야 합니다.

---

🔷 프로세스 스케줄링의 종류

운영체제는 다양한 상황에 맞춰 여러 가지 스케줄링 알고리즘을 사용합니다.

이번 글에서는 다음 네 가지 주요 알고리즘을 깊이 있게 살펴보겠습니다.

• FCFS(First Come First Served)
• RR(Round Robin)
• HRN(Highest Response Ratio Next)
• MQ(Multilevel Queue)

각각의 알고리즘은
등장 배경 → 작동 원리 → 공식 → 구체적 예시 → 장단점 → 실제 활용
순서로, 자연스럽게 설명하겠습니다.

---

🔷 FCFS(First Come First Served) 스케줄링

컴퓨터가 가장 처음으로 사용한 스케줄링 방식은 바로 FCFS입니다.
은행 창구, 식당 대기열처럼 "먼저 온 손님 먼저" 원칙을 그대로 따릅니다.

✅ FCFS 스케줄링의 정의

FCFS 스케줄링이란,
준비 상태(Ready Queue)에 도착한 순서대로 프로세스에 CPU를 할당하는 방식입니다.

특징은 다음과 같습니다:

• 선입선출(First-In-First-Out) 구조
• 비선점형(Non-Preemptive)
• 대기열(Queue) 기반 처리

✅ FCFS 스케줄링의 등장 배경

초기 컴퓨터 시스템에서는
복잡한 자원 관리가 필요하지 않았습니다.

작업량도 적고, 사용자도 소수였기에
"먼저 도착한 프로세스부터 처리하면 되겠지" 하는 단순한 발상으로 출발했습니다.

당시에는 성능 이슈보다,
운영체제의 단순성과 신뢰성이 더 중요했기 때문입니다.

✅ FCFS 스케줄링의 작동 원리

• 프로세스가 준비 큐에 도착하면 큐에 추가합니다.
• 큐의 가장 앞에 있는 프로세스를 선택해 CPU를 할당합니다.
• 프로세스는 종료될 때까지 다른 프로세스에게 CPU를 양보하지 않습니다.

반응형

 

✅ FCFS 스케줄링 공식 및 직관적 예시

✔ 대기 시간 공식

\[ \text{대기 시간} = \text{시작 시간} - \text{도착 시간} \]

- 도착 시간: 프로세스가 준비 큐에 들어온 시점
- 시작 시간: 프로세스가 CPU를 점유하기 시작한 시점
- 대기 시간: 준비 큐에서 기다린 총 시간

✔ 간단한 수치 예시

프로세스	도착 시간	실행 시간
P1	0초	5초
P2	2초	3초
P3	4초	1초

진행 과정:
- P1: 0초 도착 → 즉시 실행 (0~5초)
- P2: 2초 도착 → P1이 끝난 뒤 실행 (5~8초)
- P3: 4초 도착 → P2가 끝난 뒤 실행 (8~9초)

✔ 대기 시간 계산

프로세스	도착 시간	시작 시간	대기 시간
P1	0초	0초	0초
P2	2초	5초	3초
P3	4초	8초	4초

평균 대기 시간:

\[ \text{평균 대기 시간} = \frac{0 + 3 + 4}{3} = 2.33초 \]

✅ FCFS 스케줄링의 장단점

장점	단점
구현이 매우 간단합니다.	긴 작업이 짧은 작업을 지연시키는 '호송 행렬 효과(Convoy Effect)'가 발생할 수 있습니다.

✅ FCFS 스케줄링의 문제 상황

호송 행렬 효과(Convoy Effect)란,
하나의 긴 작업이 시스템 자원을 오랫동안 점유하여
짧은 작업들이 불필요하게 기다리게 되는 현상을 의미합니다.
결국 전체 시스템 반응 속도가 저하되고, 사용자 경험이 나빠집니다.

✅ FCFS 스케줄링의 실제 활용

• 초기 UNIX 운영체제
• 단순 디스크 I/O 요청 처리
• 일괄 처리(Batch Processing) 작업

---

반응형

 

🔷 RR(Round Robin) 스케줄링

FCFS 스케줄링은 간단하지만 한 가지 심각한 문제를 갖고 있었습니다.
만약 하나의 긴 프로세스가 CPU를 점유하게 되면,
뒤에 있는 모든 짧은 프로세스들이 불필요하게 오래 기다려야 했습니다.

특히 사람과 상호작용하는 응용 프로그램(인터넷 브라우저, 채팅 프로그램 등)은
빠른 응답성을 필요로 합니다.
이러한 요구를 충족시키기 위해 등장한 것이 RR(Round Robin) 스케줄링입니다.

---

✅ RR 스케줄링의 정의

RR 스케줄링이란,
모든 준비된 프로세스에 대해 동일한 시간 할당량(Time Quantum)을 부여하고,
이 시간이 끝나면 CPU를 강제로 회수하여 다음 프로세스에 넘기는 선점형(Preemptive) 스케줄링 기법입니다.

운영체제는 빠르게 프로세스들을 순환시키며,
모든 프로세스가 짧은 시간 안에 CPU를 사용하도록 합니다.

✅ RR 스케줄링의 등장 배경

초기 컴퓨터 사용자들은 대화형 프로그램(터미널, 온라인 입력기 등) 사용이 많아졌습니다.
빠른 응답 속도가 필요했고,
사용자가 키보드를 치거나 마우스를 클릭했을 때
수 초 이상 기다려야 한다면, 이는 심각한 불편을 초래했습니다.

이를 해결하기 위해 운영체제는
모든 프로세스에게 공평하게 CPU를 짧은 시간 동안 나눠주는 방식을 채택하게 됩니다.

✅ RR 스케줄링의 작동 원리

• 준비 큐에 있는 프로세스에게 동일한 시간(Time Quantum)을 할당합니다.
• 프로세스는 Time Quantum 동안만 CPU를 사용할 수 있습니다.
• 사용 시간이 끝나거나 프로세스가 완료되면, CPU를 다음 프로세스에게 넘깁니다.
• 프로세스가 아직 완료되지 않았다면 큐 맨 뒤로 이동하여 다시 대기합니다.

✅ RR 스케줄링 공식 및 직관적 예시

✔ 핵심 개념

• 타임 퀀텀(Time Quantum): 프로세스가 연속적으로 사용할 수 있는 최대 시간
• 대기 시간: CPU를 기다린 총 시간
• 응답 시간: 프로세스가 처음으로 CPU를 할당받기까지 걸린 시간

✔ 간단한 수치 예시

가정:

• 타임 퀀텀 = 4초
• 프로세스 세 개:
• P1: 실행 시간 6초
• P2: 실행 시간 8초
• P3: 실행 시간 7초

진행 과정:
1. P1이 4초 실행 → 2초 남음
2. P2가 4초 실행 → 4초 남음
3. P3가 4초 실행 → 3초 남음
4. P1이 남은 2초 실행 → 완료
5. P2가 남은 4초 실행 → 완료
6. P3가 남은 3초 실행 → 완료

✔ 대기 시간 대략 계산

프로세스	총 실행 시간	대기 시간 (예시)
P1	6초	중간에 한번 양보(대기)
P2	8초	여러 번 양보(더 긴 대기)
P3	7초	비슷하게 여러 번 대기

**정확한 수치는 타임라인을 그려야 하지만,**
RR에서는 대기 시간이 분할되어 발생하고,
짧은 프로세스가 먼저 완료될 가능성이 높습니다.

✅ RR 스케줄링의 장단점

장점	단점
모든 프로세스가 공평하게 CPU를 사용할 수 있습니다.	타임 퀀텀 설정이 까다롭습니다. 너무 짧으면 오버헤드, 너무 길면 FCFS와 다를 바 없습니다.

✅ RR 스케줄링의 문제 상황

타임 퀀텀(Time Quantum) 선택은 매우 중요합니다.

• 너무 짧으면 CPU 컨텍스트 스위칭(context switching)이 잦아져 오히려 성능이 저하됩니다.
• 너무 길면 선점형 스케줄링의 이점이 사라지고 FCFS처럼 됩니다.

운영체제 설계자는 이 균형을 세심하게 조정해야 합니다.

✅ RR 스케줄링의 실제 활용

• 현대 리눅스 운영체제
• 대화형 시스템(터미널 서버, 웹 서버 등)
• 실시간 시스템 일부

---

🔷 HRN(Highest Response Ratio Next) 스케줄링

FCFS나 RR 스케줄링은 짧은 프로세스가 긴 프로세스에 비해 불이익을 당하거나,
모두에게 똑같은 시간만 부여하는 한계가 있습니다.

"오래 기다린 프로세스는 더 빨리 실행해줘야 하지 않을까?"
이런 고민에서 탄생한 방식이 바로 HRN(Highest Response Ratio Next) 스케줄링입니다.

---

✅ HRN 스케줄링의 정의

HRN 스케줄링이란,
대기 시간이 길거나,
남은 실행 시간이 짧은 프로세스에 우선순위를 높게 부여하여 실행하는 스케줄링 기법입니다.

우선순위는 응답 비율(Response Ratio)을 계산하여 결정합니다.

✅ HRN 스케줄링의 등장 배경

짧은 작업이 긴 작업에 밀려 무한정 기다리게 되는 상황(Starvation)을 해결하기 위해,
"기다린 시간에 비례해서 우선순위를 높이는" 접근이 필요해졌습니다.

HRN은 단순히 작업 크기에만 주목하지 않고,
대기 시간과 실행 시간을 모두 고려하여 공정성을 높이려고 합니다.

✅ HRN 스케줄링의 작동 원리

• 준비 큐에 있는 모든 프로세스에 대해 응답 비율을 계산합니다.
• 응답 비율이 가장 높은 프로세스를 선택하여 실행합니다.
• 프로세스가 완료될 때까지 실행합니다(비선점형).

✅ HRN 스케줄링 공식 및 직관적 예시

✔ 응답 비율 공식

\[ \text{응답 비율} = \frac{\text{대기 시간} + \text{서비스 시간}}{\text{서비스 시간}} \]

- 서비스 시간(Burst Time): 프로세스가 필요한 총 실행 시간
- 대기 시간(Waiting Time): 프로세스가 Ready Queue에서 대기한 시간

✔ 간단한 수치 예시

프로세스	도착 시간	서비스 시간
P1	0초	4초
P2	1초	3초
P3	2초	2초

처음에는:
- P1: 대기 시간 0초 → 응답 비율 = (0+4)/4 = 1.0
- P2: 아직 도착하지 않음
- P3: 아직 도착하지 않음
→ P1 실행

✔ HRN 스케줄링 수치 계산

프로세스	도착 시간	서비스 시간	대기 시간	응답 비율
P1	0	4	0	1.0
P2	1	3	3	2.0
P3	2	2	2	2.0

---

반응형

 

🔷 MQ(Multilevel Queue) 스케줄링

현실 세계에는 다양한 종류의 프로세스가 존재합니다.

• 사용자 입력을 빠르게 처리해야 하는 프로세스
• 대규모 데이터를 장시간 처리해야 하는 백그라운드 작업
• 시스템 자체를 유지보수하는 핵심 프로세스

이렇게 서로 다른 성격의 작업을 단일 규칙으로 관리하는 것은 비효율적입니다.

이를 해결하기 위해 등장한 것이 바로 다단계 큐 스케줄링(Multilevel Queue Scheduling, MQ)입니다.

---

✅ MQ 스케줄링의 정의

MQ 스케줄링이란,
성격이 다른 프로세스들을 구분하여 여러 개의 준비 큐(Ready Queue)로 분리하고,
각 큐마다 서로 다른 스케줄링 정책을 적용하는 방식입니다.

✅ MQ 스케줄링의 등장 배경

모든 프로세스를 하나의 큐에 담아 일괄 관리할 경우,
응답성이 필요한 프로세스와 장기 작업 프로세스 간의 갈등이 발생합니다.

따라서 프로세스 종류에 따라 별도의 큐를 만들어 관리하고,
중요도에 따라 다른 스케줄링 방식을 적용하는 것이 필요해졌습니다.

✅ MQ 스케줄링의 작동 원리

• 프로세스를 특성에 따라 분류하여 다른 큐에 넣습니다.
• 큐마다 스케줄링 정책(FIFO, RR 등)을 따로 적용합니다.
• 큐 간에도 우선순위를 정하여 CPU를 할당합니다.
  (예: 시스템 프로세스 큐 > 사용자 프로세스 큐)

✅ MQ 스케줄링 공식 및 직관적 예시

다단계 구조의 특징
- 큐1: 시스템 프로세스 (FCFS 방식)
- 큐2: 사용자 프로세스 (RR 방식, 타임 퀀텀 4초)

진행 방법:

• 항상 큐1이 비어야만 큐2로 넘어갑니다.
• 만약 큐1에 프로세스가 생기면 큐2 실행을 중단하고, 큐1을 우선 처리합니다.

✔ 간단한 수치 예시

- 시스템 프로세스 S1: 0초 도착, 4초 실행
- 사용자 프로세스 U1: 1초 도착, 5초 실행

진행:
- S1이 먼저 4초 동안 실행
- S1이 끝난 뒤 U1이 타임 퀀텀 4초 동안 실행하고, 남은 1초를 다시 수행

✅ MQ 스케줄링의 장단점

장점	단점
프로세스 특성에 맞는 유연한 스케줄링이 가능합니다.	잘못된 큐 분류나 비효율적인 우선순위 설정이 오히려 성능을 떨어뜨릴 수 있습니다.

✅ MQ 스케줄링의 문제 상황

• 큐 분류 기준이 명확하지 않거나 현실과 다르면, 프로세스가 부당하게 대기하거나 불공정한 처리가 발생할 수 있습니다.

✅ MQ 스케줄링의 실제 활용

• 실시간 운영체제(Real-Time Operating Systems)
• 복합적인 서비스를 제공하는 서버 시스템(웹 서버, 데이터베이스 서버 등)

---

반응형

 

🔷 전체 요약

✅ 프로세스 스케줄링 알고리즘 비교

알고리즘	기본 원리	장점	단점
FCFS	먼저 온 프로세스부터 실행	간단하고 직관적	긴 작업이 시스템을 지연시킬 수 있음
RR	시간 할당량 순환	공평한 자원 배분	타임 퀀텀 설정이 까다로움
HRN	대기 시간과 서비스 시간 고려	공정성 향상	계산 비용 증가
MQ	프로세스 특성별 큐 관리	유연한 대응 가능	큐 분류 오류 시 비효율 초래