CPU 스케줄링 알고리즘 완벽 가이드 (1)

운영체제의 핵심인 CPU 스케줄링 알고리즘을 초급 개발자도 쉽게 이해할 수 있도록 설명합니다. FCFS부터 HRRN까지, 각 알고리즘의 동작 원리와 장단점을 실무 스토리와 함께 배워봅니다.

1. FCFS (First Come First Served)

어느 날 김개발 씨가 운영체제 수업을 듣다가 교수님께 질문을 받았습니다. "CPU가 여러 프로세스를 어떻게 처리할지 결정하는 가장 단순한 방법이 뭘까요?" 김개발 씨는 잠시 생각하다가 "먼저 온 순서대로요?"라고 대답했습니다.

**FCFS(First Come First Served)**는 말 그대로 먼저 도착한 프로세스를 먼저 처리하는 방식입니다. 마치 은행 창구에서 번호표를 뽑고 순서대로 기다리는 것과 같습니다.

구현이 가장 단순하지만, 그만큼 효율성 문제가 있을 수 있습니다.

다음 코드를 살펴봅시다.

from collections import deque

class FCFSScheduler:
    def __init__(self):
        self.ready_queue = deque()  # 준비 큐 (FIFO)

    def add_process(self, process):
        # 도착한 순서대로 큐에 추가
        self.ready_queue.append(process)

    def schedule(self):
        # 가장 먼저 도착한 프로세스를 꺼냄
        if self.ready_queue:
            return self.ready_queue.popleft()
        return None

# 사용 예시
scheduler = FCFSScheduler()
scheduler.add_process({"pid": 1, "burst_time": 24})
scheduler.add_process({"pid": 2, "burst_time": 3})
next_process = scheduler.schedule()  # pid 1이 먼저 실행

김개발 씨는 입사 3개월 차 주니어 개발자입니다. 오늘은 운영체제의 기초를 다시 공부하기로 마음먹었습니다.

첫 번째 주제는 바로 CPU 스케줄링입니다. 선배 개발자 박시니어 씨가 옆에서 설명을 시작합니다.

"스케줄링이 뭔지 알아? 쉽게 말하면 CPU라는 일꾼에게 어떤 일을 먼저 시킬지 정하는 거야." 그렇다면 FCFS란 정확히 무엇일까요?

쉽게 비유하자면, FCFS는 마치 놀이공원 매표소와 같습니다. 사람들이 줄을 서면 먼저 온 사람부터 차례대로 표를 삽니다.

중간에 끼어들기는 없습니다. 아무리 급한 사람이 있어도 순서는 바뀌지 않습니다.

CPU 스케줄링에서도 마찬가지입니다. 프로세스가 준비 큐에 도착한 순서대로 CPU를 할당받습니다.

FCFS의 가장 큰 장점은 구현이 매우 단순하다는 것입니다. 단순히 큐(Queue) 자료구조만 있으면 됩니다.

새 프로세스가 도착하면 큐의 맨 뒤에 넣고, CPU가 비면 큐의 맨 앞에서 꺼내면 그만입니다. 복잡한 계산이나 비교 연산이 필요 없습니다.

또한 공정성이 보장됩니다. 모든 프로세스가 도착한 순서대로 처리되므로, 어떤 프로세스도 영원히 무시당하는 일이 없습니다.

기아(Starvation) 현상이 발생하지 않는 것이죠. 은행에서 번호표를 받으면 언젠가는 반드시 차례가 오는 것처럼 말입니다.

위의 코드를 살펴보겠습니다. deque를 사용한 이유는 FIFO(First In First Out) 구조를 효율적으로 구현하기 위해서입니다.

append 메서드로 뒤에 추가하고, popleft 메서드로 앞에서 꺼냅니다. 이 두 연산 모두 O(1) 시간 복잡도를 가집니다.

하지만 FCFS에는 심각한 단점이 있습니다. 만약 실행 시간이 24초인 프로세스가 먼저 도착하고, 그 뒤에 실행 시간이 3초인 프로세스가 도착했다면 어떻게 될까요?

3초짜리 프로세스는 24초를 기다려야 합니다. 이것이 바로 Convoy Effect인데, 뒤에서 자세히 다루겠습니다.

다시 김개발 씨의 이야기로 돌아가 봅시다. 박시니어 씨가 물었습니다.

"그럼 FCFS는 언제 쓰면 좋을까?" 김개발 씨는 고개를 끄덕이며 대답했습니다. "프로세스들의 실행 시간이 비슷하거나, 단순함이 중요한 배치 시스템에서요!" FCFS는 가장 기본적인 스케줄링 알고리즘이지만, 그 한계를 정확히 이해하는 것이 중요합니다.

실전 팁

💡 - FCFS는 비선점형 스케줄링입니다. 한 번 CPU를 잡으면 작업이 끝날 때까지 놓지 않습니다.

평균 대기 시간이 프로세스 도착 순서에 따라 크게 달라질 수 있습니다.

2. SJF (Shortest Job First)

김개발 씨가 FCFS의 문제점을 듣고 나서 이렇게 물었습니다. "그럼 짧은 작업을 먼저 처리하면 되지 않나요?" 박시니어 씨가 미소를 지으며 답했습니다.

"바로 그게 SJF야. 근데 문제가 있어."

**SJF(Shortest Job First)**는 실행 시간이 가장 짧은 프로세스를 먼저 처리하는 알고리즘입니다. 마치 마트 계산대에서 물건이 적은 손님을 먼저 계산해주는 것과 같습니다.

이론적으로 평균 대기 시간을 최소화하는 최적의 알고리즘이지만, 실제 구현에는 난관이 있습니다.

다음 코드를 살펴봅시다.

import heapq

class SJFScheduler:
    def __init__(self):
        self.ready_queue = []  # 최소 힙 (burst_time 기준)

    def add_process(self, process):
        # burst_time을 기준으로 힙에 추가
        heapq.heappush(self.ready_queue,
                       (process["burst_time"], process["pid"], process))

    def schedule(self):
        # 실행 시간이 가장 짧은 프로세스를 꺼냄
        if self.ready_queue:
            _, _, process = heapq.heappop(self.ready_queue)
            return process
        return None

# 사용 예시
scheduler = SJFScheduler()
scheduler.add_process({"pid": 1, "burst_time": 6})
scheduler.add_process({"pid": 2, "burst_time": 2})
scheduler.add_process({"pid": 3, "burst_time": 8})
next_process = scheduler.schedule()  # pid 2 (burst_time: 2)가 먼저

점심시간, 김개발 씨는 회사 근처 식당에서 줄을 서고 있었습니다. 앞에 있는 손님이 메뉴를 한참 고르는 동안, 뒤에는 이미 주문할 메뉴가 정해진 사람들이 기다리고 있었습니다.

"저 사람만 아니면 빨리 주문할 수 있을 텐데..." 문득 아침에 배운 FCFS의 문제점이 떠올랐습니다. SJF는 바로 이런 상황을 해결하기 위해 등장했습니다.

SJF의 핵심 아이디어는 간단합니다. 실행 시간이 짧은 프로세스를 먼저 처리하자. 마치 편의점에서 물건 하나만 사는 손님을 먼저 계산해주는 것처럼요.

이렇게 하면 전체적인 대기 시간이 줄어듭니다. 왜 평균 대기 시간이 줄어들까요?

수학적으로 증명할 수 있습니다. 짧은 작업을 먼저 처리하면, 그 뒤에 있는 모든 프로세스의 대기 시간이 줄어듭니다.

반대로 긴 작업을 먼저 처리하면, 뒤에 있는 모든 프로세스가 오래 기다려야 합니다. 따라서 SJF는 이론적으로 평균 대기 시간을 최소화하는 최적의 알고리즘입니다.

위의 코드를 살펴보겠습니다. **최소 힙(min-heap)**을 사용한 것이 핵심입니다.

Python의 heapq 모듈은 기본적으로 최소 힙을 구현합니다. 튜플의 첫 번째 요소인 burst_time을 기준으로 정렬되므로, 항상 실행 시간이 가장 짧은 프로세스가 먼저 나옵니다.

그런데 박시니어 씨는 왜 "문제가 있다"고 했을까요? 현실에서는 프로세스의 실행 시간을 미리 알 수 없습니다.

프로그램이 얼마나 오래 실행될지 어떻게 알겠습니까? CPU가 미래를 볼 수 있는 것도 아니고요.

이것이 SJF의 가장 큰 한계입니다. 그래서 실제로는 과거의 실행 패턴을 분석해서 다음 실행 시간을 예측하는 방식을 사용합니다.

또 다른 심각한 문제가 있습니다. 실행 시간이 긴 프로세스는 영원히 실행되지 않을 수 있습니다.

짧은 프로세스가 계속 들어오면, 긴 프로세스는 영원히 뒤로 밀려납니다. 이것을 기아(Starvation) 현상이라고 합니다.

마치 편의점에서 물건을 많이 든 손님이 영원히 계산을 못 하는 것과 같습니다. 김개발 씨가 물었습니다.

"그럼 SJF는 실제로 쓸 수 없는 건가요?" 박시니어 씨가 대답했습니다. "순수한 SJF는 어렵지만, 이 아이디어를 발전시킨 알고리즘들은 많이 쓰여.

다음에 배울 SRTF도 그중 하나야."

실전 팁

💡 - SJF도 기본적으로 비선점형입니다. 실행 중인 프로세스는 끝까지 실행됩니다.

실행 시간 예측에는 지수 평균(Exponential Averaging) 기법이 자주 사용됩니다.

3. SRTF (Shortest Remaining Time First)

박시니어 씨가 화이트보드에 그림을 그리며 설명합니다. "SJF가 비선점형이라고 했잖아.

그런데 만약 실행 중에 더 짧은 작업이 들어오면 어떻게 할까?" 김개발 씨의 눈이 반짝입니다. "멈추고 그걸 먼저 처리하면요?"

**SRTF(Shortest Remaining Time First)**는 SJF의 선점형 버전입니다. 현재 실행 중인 프로세스보다 남은 실행 시간이 더 짧은 프로세스가 도착하면, 즉시 CPU를 빼앗아 새 프로세스에게 할당합니다.

마치 응급실에서 더 급한 환자가 오면 우선순위가 바뀌는 것과 같습니다.

다음 코드를 살펴봅시다.

import heapq

class SRTFScheduler:
    def __init__(self):
        self.ready_queue = []
        self.current_process = None

    def add_process(self, process, current_time):
        # 새 프로세스 도착 시 선점 여부 결정
        if self.current_process:
            remaining = self.current_process["remaining_time"]
            if process["burst_time"] < remaining:
                # 현재 프로세스를 큐에 다시 넣고 선점
                heapq.heappush(self.ready_queue,
                    (remaining, self.current_process["pid"], self.current_process))
                self.current_process = process
                self.current_process["remaining_time"] = process["burst_time"]
                return True  # 선점 발생
        heapq.heappush(self.ready_queue,
            (process["burst_time"], process["pid"], process))
        return False

    def tick(self):
        # 1단위 시간 실행
        if self.current_process:
            self.current_process["remaining_time"] -= 1

김개발 씨는 SRTF를 이해하기 위해 실생활의 예를 떠올려 보았습니다. 응급실을 생각해봅시다.

의사가 환자를 치료하고 있는데, 갑자기 더 위급한 환자가 실려 옵니다. 이때 의사는 현재 환자의 치료를 잠시 멈추고 새로 온 환자를 먼저 봅니다.

이것이 바로 **선점(Preemption)**의 개념입니다. SRTF는 이 개념을 CPU 스케줄링에 적용한 것입니다.

SJF에서는 일단 프로세스가 실행을 시작하면 끝날 때까지 CPU를 놓지 않았습니다. 하지만 SRTF에서는 다릅니다.

새 프로세스가 도착했을 때, 그 프로세스의 실행 시간이 현재 남은 실행 시간보다 짧으면 바로 교체합니다. 여기서 핵심은 **"남은 실행 시간"**입니다.

처음 실행 시간이 10초인 프로세스가 이미 6초를 실행했다면, 남은 시간은 4초입니다. 이때 실행 시간이 3초인 새 프로세스가 도착하면, 3초가 4초보다 짧으므로 새 프로세스가 CPU를 가져갑니다.

원래 프로세스는 다시 준비 큐로 돌아가 자기 차례를 기다립니다. 위의 코드에서 remaining_time 필드를 주목해주세요.

각 프로세스는 자신의 남은 실행 시간을 기억하고 있습니다. tick 메서드가 호출될 때마다 1씩 감소합니다.

새 프로세스가 도착하면 add_process에서 현재 프로세스의 남은 시간과 비교하여 선점 여부를 결정합니다. SRTF는 SJF보다 평균 대기 시간을 더 줄일 수 있습니다.

왜냐하면 긴 작업이 실행 중이더라도 짧은 작업이 오면 바로 처리할 수 있기 때문입니다. 짧은 작업들이 불필요하게 오래 기다리지 않아도 됩니다.

하지만 대가가 있습니다. 컨텍스트 스위칭(Context Switching) 비용이 발생합니다.

CPU가 프로세스를 교체할 때마다 현재 상태를 저장하고 새 프로세스의 상태를 불러와야 합니다. 이 과정은 공짜가 아닙니다.

선점이 너무 자주 일어나면 오히려 전체 성능이 떨어질 수 있습니다. 그리고 SJF의 문제점이 그대로 남아있습니다.

실행 시간을 미리 알아야 하고, 긴 프로세스는 여전히 기아 현상에 시달릴 수 있습니다. 짧은 프로세스가 계속 들어오면 긴 프로세스는 영원히 밀려날 수 있습니다.

김개발 씨가 고개를 끄덕입니다. "선점형이 무조건 좋은 건 아니군요." 박시니어 씨가 맞장구칩니다.

"그래, 상황에 따라 적절한 알고리즘을 선택하는 게 중요해."

실전 팁

💡 - SRTF는 선점형이므로 컨텍스트 스위칭 오버헤드를 고려해야 합니다.

실시간 시스템에서는 SRTF보다 더 예측 가능한 스케줄링이 필요할 수 있습니다.

4. HRRN (Highest Response Ratio Next)

김개발 씨가 걱정스러운 표정으로 물었습니다. "SJF랑 SRTF는 긴 프로세스가 굶어 죽을 수 있다고 했잖아요.

그걸 해결할 방법은 없나요?" 박시니어 씨가 흐뭇한 표정을 지었습니다. "좋은 질문이야.

HRRN이라는 게 있어."

**HRRN(Highest Response Ratio Next)**은 SJF의 기아 문제를 해결하기 위해 고안된 알고리즘입니다. 단순히 실행 시간만 보는 것이 아니라, 대기 시간도 함께 고려합니다.

응답 비율이라는 공식을 통해 오래 기다린 프로세스에게 높은 우선순위를 부여합니다.

다음 코드를 살펴봅시다.

class HRRNScheduler:
    def __init__(self):
        self.ready_queue = []

    def calculate_response_ratio(self, process, current_time):
        # 응답 비율 = (대기 시간 + 실행 시간) / 실행 시간
        waiting_time = current_time - process["arrival_time"]
        burst_time = process["burst_time"]
        return (waiting_time + burst_time) / burst_time

    def add_process(self, process):
        self.ready_queue.append(process)

    def schedule(self, current_time):
        if not self.ready_queue:
            return None
        # 응답 비율이 가장 높은 프로세스 선택
        best_process = max(self.ready_queue,
            key=lambda p: self.calculate_response_ratio(p, current_time))
        self.ready_queue.remove(best_process)
        return best_process

# 사용 예시
scheduler = HRRNScheduler()
scheduler.add_process({"pid": 1, "burst_time": 10, "arrival_time": 0})
scheduler.add_process({"pid": 2, "burst_time": 2, "arrival_time": 1})
next_process = scheduler.schedule(current_time=5)

박시니어 씨가 화이트보드에 공식을 적습니다. 응답 비율 = (대기 시간 + 실행 시간) / 실행 시간 김개발 씨가 공식을 유심히 바라봅니다.

처음에는 복잡해 보였지만, 찬찬히 뜯어보니 의미가 보이기 시작했습니다. 이 공식의 핵심은 대기 시간이 길어질수록 응답 비율이 높아진다는 것입니다.

예를 들어봅시다. 실행 시간이 10초인 프로세스가 있습니다.

막 도착했을 때(대기 시간 0초)의 응답 비율은 (0+10)/10 = 1입니다. 하지만 20초를 기다렸다면 응답 비율은 (20+10)/10 = 3으로 높아집니다.

반면, 실행 시간이 2초인 짧은 프로세스는 막 도착해도 응답 비율이 (0+2)/2 = 1입니다. 이것이 어떤 의미일까요?

처음에는 짧은 프로세스가 유리합니다. SJF처럼요.

하지만 시간이 지날수록 오래 기다린 프로세스의 응답 비율이 올라갑니다. 어느 순간 긴 프로세스의 응답 비율이 짧은 프로세스보다 높아지면, 긴 프로세스가 선택됩니다.

이것이 바로 에이징(Aging) 기법입니다. 나이가 들면(오래 기다리면) 우선순위가 높아지는 것이죠.

마치 경로우대처럼요. 오래 기다린 사람에게는 먼저 서비스할 기회를 주는 것입니다.

위의 코드에서 calculate_response_ratio 함수를 살펴보세요. 현재 시간에서 도착 시간을 빼서 대기 시간을 계산합니다.

그리고 공식대로 응답 비율을 구합니다. schedule 함수에서는 모든 프로세스의 응답 비율을 계산하여 가장 높은 것을 선택합니다.

HRRN의 장점은 명확합니다. SJF의 효율성을 유지하면서도 기아 현상을 방지합니다.

짧은 프로세스는 여전히 빨리 처리되고, 긴 프로세스도 언젠가는 반드시 실행됩니다. 두 마리 토끼를 모두 잡은 셈이죠.

하지만 단점도 있습니다. 매번 스케줄링할 때마다 모든 프로세스의 응답 비율을 계산해야 합니다.

준비 큐에 프로세스가 많으면 오버헤드가 커질 수 있습니다. 또한 HRRN도 비선점형이라서, 한 번 실행이 시작되면 끝날 때까지 기다려야 합니다.

김개발 씨가 감탄합니다. "공식 하나로 두 가지 문제를 해결하다니, 정말 똑똑한 방법이네요!" 박시니어 씨가 고개를 끄덕입니다.

"알고리즘 설계의 묘미지. 단순해 보이지만 깊은 통찰이 담겨 있어."

실전 팁

💡 - HRRN은 비선점형이며, 스케줄링 시점에 응답 비율을 계산합니다.

응답 비율 계산 오버헤드가 있으므로 프로세스 수가 적을 때 더 효과적입니다.

5. Convoy Effect 문제

김개발 씨가 출근길 지하철에서 경험한 일입니다. 캐리어를 끄는 사람이 좁은 통로를 천천히 걸어가자, 뒤에 있는 모든 사람이 발을 맞춰 느리게 걸어야 했습니다.

사무실에 도착해서 그 이야기를 하자, 박시니어 씨가 말했습니다. "그게 바로 Convoy Effect야."

Convoy Effect는 실행 시간이 긴 프로세스가 CPU를 점유하는 동안, 짧은 프로세스들이 줄지어 기다리는 현상입니다. 마치 느린 트럭 뒤에 빠른 차들이 줄지어 서행하는 것과 같습니다.

FCFS 알고리즘에서 특히 심각하게 발생하며, 전체 시스템의 효율성을 크게 떨어뜨립니다.

다음 코드를 살펴봅시다.

def simulate_convoy_effect():
    # FCFS 스케줄링 시뮬레이션
    processes = [
        {"pid": 1, "burst_time": 100, "arrival_time": 0},  # CPU 집약적
        {"pid": 2, "burst_time": 5, "arrival_time": 1},    # I/O 집약적
        {"pid": 3, "burst_time": 3, "arrival_time": 2},    # I/O 집약적
        {"pid": 4, "burst_time": 2, "arrival_time": 3},    # I/O 집약적
    ]

    current_time = 0
    total_waiting = 0

    for p in processes:
        waiting = max(0, current_time - p["arrival_time"])
        total_waiting += waiting
        print(f"PID {p['pid']}: 대기 {waiting}초, 실행 {p['burst_time']}초")
        current_time += p["burst_time"]

    print(f"평균 대기 시간: {total_waiting / len(processes):.1f}초")
    # 결과: PID 2,3,4는 100초 가까이 대기!

simulate_convoy_effect()

김개발 씨는 고속도로를 떠올렸습니다. 편도 1차선 도로에 대형 트럭이 시속 60km로 달리고 있습니다.

뒤에는 시속 100km로 달릴 수 있는 승용차들이 줄지어 있습니다. 추월이 불가능하니, 모든 차가 시속 60km로 갈 수밖에 없습니다.

이것이 바로 Convoy Effect의 본질입니다. CPU 스케줄링에서도 마찬가지 상황이 발생합니다.

FCFS 알고리즘에서 실행 시간이 100초인 CPU 집약적 프로세스가 먼저 도착했다고 가정합시다. 그 직후에 실행 시간이 2초, 3초, 5초인 I/O 집약적 프로세스들이 도착합니다.

이 프로세스들은 모두 100초를 기다려야 합니다. 위의 코드 실행 결과를 보면 충격적입니다.

PID 1은 대기 시간 0초에 100초를 실행합니다. 하지만 PID 2는 99초를 기다리고, PID 3은 101초를, PID 4는 103초를 기다립니다.

실행 시간이 고작 2~5초인 프로세스들이 100초 넘게 기다리는 것입니다. 평균 대기 시간이 급격히 늘어납니다.

왜 이것이 문제일까요? 시스템 전체의 활용도가 떨어집니다. I/O 집약적 프로세스는 CPU를 잠깐 쓰고 I/O 작업을 하러 갑니다.

그동안 다른 프로세스가 CPU를 쓸 수 있죠. 하지만 Convoy Effect로 인해 I/O 장치는 놀고, CPU만 한 프로세스가 독점합니다.

실제 시스템에서는 더 심각합니다. 웹 서버를 생각해봅시다.

대부분의 요청은 빠르게 처리됩니다. 하지만 가끔 무거운 요청이 들어옵니다.

이 무거운 요청이 CPU를 점유하는 동안, 가벼운 요청들이 모두 기다립니다. 사용자들은 간단한 페이지 조회에도 오랜 시간을 기다려야 합니다.

해결책은 무엇일까요? 가장 직접적인 해결책은 SJF나 SRTF를 사용하는 것입니다.

짧은 프로세스를 먼저 처리하면 Convoy Effect를 피할 수 있습니다. 또는 라운드 로빈(Round Robin) 방식을 사용하여 시간을 나눠 쓰게 할 수도 있습니다.

박시니어 씨가 정리합니다. "Convoy Effect는 FCFS의 대표적인 단점이야.

그래서 현대 운영체제는 더 정교한 스케줄링 알고리즘을 사용하지." 김개발 씨가 고개를 끄덕입니다. 아침에 지하철에서 겪었던 불편함이 이제 알고리즘 문제로 다가왔습니다.

실전 팁

💡 - Convoy Effect는 비선점형 스케줄링에서 주로 발생합니다.

I/O 집약적 프로세스와 CPU 집약적 프로세스가 섞여 있을 때 특히 심각해집니다.

6. 기아 현상과 해결책

김개발 씨가 점심 식당에서 또 한 번 경험을 합니다. 항상 급한 손님에게 먼저 음식을 주는 식당에서, 느긋하게 앉아 있던 손님이 두 시간이 지나도 음식을 받지 못했습니다.

박시니어 씨가 말합니다. "그게 바로 기아 현상이야.

컴퓨터에서도 똑같은 일이 벌어져."

기아(Starvation) 현상은 특정 프로세스가 CPU를 할당받지 못하고 무한히 대기하는 상황입니다. 우선순위 기반 스케줄링이나 SJF에서 발생할 수 있습니다.

해결책으로는 에이징(Aging) 기법이 대표적이며, HRRN 알고리즘이 이를 구현한 예입니다.

다음 코드를 살펴봅시다.

class AgingScheduler:
    def __init__(self, aging_factor=1):
        self.ready_queue = []
        self.aging_factor = aging_factor  # 시간당 우선순위 증가량

    def add_process(self, process):
        process["effective_priority"] = process["base_priority"]
        process["wait_start"] = 0
        self.ready_queue.append(process)

    def apply_aging(self, current_time):
        # 대기 중인 모든 프로세스의 우선순위 증가
        for p in self.ready_queue:
            wait_time = current_time - p["wait_start"]
            p["effective_priority"] = p["base_priority"] + (wait_time * self.aging_factor)

    def schedule(self, current_time):
        if not self.ready_queue:
            return None
        self.apply_aging(current_time)
        # 가장 높은 유효 우선순위 선택
        best = max(self.ready_queue, key=lambda p: p["effective_priority"])
        self.ready_queue.remove(best)
        return best

# 낮은 우선순위 프로세스도 시간이 지나면 실행됨

기아 현상을 이해하기 위해 비유를 들어봅시다. 놀이공원의 롤러코스터를 상상해보세요.

VIP 패스를 가진 손님은 항상 먼저 탑니다. 일반 손님은 VIP가 없을 때만 탈 수 있습니다.

그런데 VIP 손님이 끊임없이 온다면? 일반 손님은 영원히 롤러코스터를 타지 못합니다.

이것이 바로 **기아(Starvation)**입니다. 컴퓨터에서도 똑같습니다.

SJF에서는 실행 시간이 짧은 프로세스가 계속 도착하면, 긴 프로세스는 영원히 실행되지 못할 수 있습니다. 우선순위 스케줄링에서는 높은 우선순위 프로세스가 계속 오면, 낮은 우선순위 프로세스가 굶어 죽습니다.

기아 현상이 왜 문제일까요? 시스템의 **공정성(Fairness)**이 무너집니다.

모든 프로세스는 어느 정도의 서비스를 받을 권리가 있습니다. 특정 프로세스가 영원히 무시당하는 것은 운영체제 설계 원칙에 어긋납니다.

또한 예측 불가능성도 문제입니다. 언제 실행될지 알 수 없으면 시스템을 신뢰할 수 없습니다.

해결책의 핵심은 **에이징(Aging)**입니다. 에이징은 간단한 아이디어입니다.

오래 기다린 프로세스의 우선순위를 점진적으로 높여주는 것입니다. 아무리 낮은 우선순위로 시작해도, 시간이 지나면 우선순위가 올라갑니다.

언젠가는 가장 높은 우선순위가 되어 반드시 실행됩니다. 위의 코드에서 apply_aging 함수를 보세요.

대기 시간에 aging_factor를 곱해서 유효 우선순위에 더합니다. 기본 우선순위가 1인 프로세스도, 100초를 기다리면 유효 우선순위가 101이 됩니다.

기본 우선순위가 50인 프로세스보다 높아지는 것이죠. 앞서 배운 HRRN이 바로 에이징을 적용한 예입니다.

HRRN의 응답 비율 공식을 다시 보면, 대기 시간이 분자에 들어갑니다. 대기 시간이 길어질수록 응답 비율이 높아지고, 결국 그 프로세스가 선택됩니다.

수학적으로 에이징을 구현한 것입니다. 다른 해결책도 있습니다.

**라운드 로빈(Round Robin)**은 모든 프로세스에게 동일한 시간을 할당합니다. 우선순위와 관계없이 순서대로 조금씩 실행합니다.

기아가 발생할 수 없는 구조입니다. **다단계 피드백 큐(Multilevel Feedback Queue)**는 더 정교한 방식으로, 프로세스의 행동에 따라 우선순위를 동적으로 조절합니다.

김개발 씨가 정리합니다. "결국 공정성과 효율성 사이에서 균형을 찾는 거군요." 박시니어 씨가 미소 짓습니다.

"바로 그거야. 운영체제 설계의 핵심이지." 오늘 배운 스케줄링 알고리즘들은 모두 이 균형을 찾기 위한 시도입니다.

각각의 장단점을 이해하고, 상황에 맞게 선택하는 것이 중요합니다.

실전 팁

💡 - 에이징 계수(aging factor)를 너무 크게 설정하면 우선순위의 의미가 사라질 수 있습니다.

현대 운영체제는 여러 기법을 조합한 다단계 피드백 큐를 주로 사용합니다.

이상으로 학습을 마칩니다. 위 내용을 직접 코드로 작성해보면서 익혀보세요!

#OperatingSystem#CPUScheduling#FCFS#SJF#ProcessManagement#Operating System

CPU 스케줄링 알고리즘 완벽 가이드 (1)

# CPU 스케줄링 알고리즘 완벽 가이드 (1) 운영체제의 핵심인 CPU 스케줄링 알고리즘을 초급 개발자도 쉽게 이해할 수 있도록 설명합니다. FCFS부터 HRRN까지, 각 알고리즘의 동작 원리와 장단점을 실무 스토리와 함께 배워봅니다. --- ## 목차 1. [FCFS (First Come First Served)](#fcfs-(first-come-first-served)) 2. [SJF (Shortest Job First)](#sjf-(shortest-job-first)) 3. [SRTF (Shortest Remaining Time First)](#srtf-(shortest-remaining-time-first)) 4. [HRRN (Highest Response Ratio Next)](#hrrn-(highest-response-ratio-next)) 5. [Convoy Effect 문제](#convoy-effect-문제) 6. [기아 현상과 해결책](#기아-현상과-해결책) --- ## 1. FCFS (First Come First Served) 어느 날 김개발 씨가 운영체제 수업을 듣다가 교수님께 질문을 받았습니다. "CPU가 여러 프로세스를 어떻게 처리할지 결정하는 가장 단순한 방법이 뭘까요?" 김개발 씨는 잠시 생각하다가 "먼저 온 순서대로요?"라고 대답했습니다. **FCFS(First Come First Served)**는 말 그대로 먼저 도착한 프로세스를 먼저 처리하는 방식입니다. 마치 은행 창구에서 번호표를 뽑고 순서대로 기다리는 것과 같습니다. 구현이 가장 단순하지만, 그만큼 효율성 문제가 있을 수 있습니다. 다음 코드를 살펴봅시다. ```python from collections import deque class FCFSScheduler: def __init__(self): self.ready_queue = deque() # 준비 큐 (FIFO) def add_process(self, process): # 도착한 순서대로 큐에 추가 self.ready_queue.append(process) def schedule(self): # 가장 먼저 도착한 프로세스를 꺼냄 if self.ready_queue: return self.ready_queue.popleft() return None # 사용 예시 scheduler = FCFSScheduler() scheduler.add_process({"pid": 1, "burst_time": 24}) scheduler.add_process({"pid": 2, "burst_time": 3}) next_process = scheduler.schedule() # pid 1이 먼저 실행 ``` 김개발 씨는 입사 3개월 차 주니어 개발자입니다. 오늘은 운영체제의 기초를 다시 공부하기로 마음먹었습니다. 첫 번째 주제는 바로 CPU 스케줄링입니다. 선배 개발자 박시니어 씨가 옆에서 설명을 시작합니다. "스케줄링이 뭔지 알아? 쉽게 말하면 CPU라는 일꾼에게 어떤 일을 먼저 시킬지 정하는 거야." 그렇다면 **FCFS**란 정확히 무엇일까요? 쉽게 비유하자면, FCFS는 마치 **놀이공원 매표소**와 같습니다. 사람들이 줄을 서면 먼저 온 사람부터 차례대로 표를 삽니다. 중간에 끼어들기는 없습니다. 아무리 급한 사람이 있어도 순서는 바뀌지 않습니다. CPU 스케줄링에서도 마찬가지입니다. 프로세스가 준비 큐에 도착한 순서대로 CPU를 할당받습니다. FCFS의 가장 큰 장점은 **구현이 매우 단순하다**는 것입니다. 단순히 큐(Queue) 자료구조만 있으면 됩니다. 새 프로세스가 도착하면 큐의 맨 뒤에 넣고, CPU가 비면 큐의 맨 앞에서 꺼내면 그만입니다. 복잡한 계산이나 비교 연산이 필요 없습니다. 또한 **공정성**이 보장됩니다. 모든 프로세스가 도착한 순서대로 처리되므로, 어떤 프로세스도 영원히 무시당하는 일이 없습니다. 기아(Starvation) 현상이 발생하지 않는 것이죠. 은행에서 번호표를 받으면 언젠가는 반드시 차례가 오는 것처럼 말입니다. 위의 코드를 살펴보겠습니다. **deque**를 사용한 이유는 FIFO(First In First Out) 구조를 효율적으로 구현하기 위해서입니다. **append** 메서드로 뒤에 추가하고, **popleft** 메서드로 앞에서 꺼냅니다. 이 두 연산 모두 O(1) 시간 복잡도를 가집니다. 하지만 FCFS에는 심각한 단점이 있습니다. 만약 실행 시간이 24초인 프로세스가 먼저 도착하고, 그 뒤에 실행 시간이 3초인 프로세스가 도착했다면 어떻게 될까요? 3초짜리 프로세스는 24초를 기다려야 합니다. 이것이 바로 **Convoy Effect**인데, 뒤에서 자세히 다루겠습니다. 다시 김개발 씨의 이야기로 돌아가 봅시다. 박시니어 씨가 물었습니다. "그럼 FCFS는 언제 쓰면 좋을까?" 김개발 씨는 고개를 끄덕이며 대답했습니다. "프로세스들의 실행 시간이 비슷하거나, 단순함이 중요한 배치 시스템에서요!" FCFS는 가장 기본적인 스케줄링 알고리즘이지만, 그 한계를 정확히 이해하는 것이 중요합니다. **실전 팁** 💡 - FCFS는 **비선점형** 스케줄링입니다. 한 번 CPU를 잡으면 작업이 끝날 때까지 놓지 않습니다. - 평균 대기 시간이 프로세스 도착 순서에 따라 크게 달라질 수 있습니다. --- ## 2. SJF (Shortest Job First) 김개발 씨가 FCFS의 문제점을 듣고 나서 이렇게 물었습니다. "그럼 짧은 작업을 먼저 처리하면 되지 않나요?" 박시니어 씨가 미소를 지으며 답했습니다. "바로 그게 SJF야. 근데 문제가 있어." **SJF(Shortest Job First)**는 실행 시간이 가장 짧은 프로세스를 먼저 처리하는 알고리즘입니다. 마치 마트 계산대에서 물건이 적은 손님을 먼저 계산해주는 것과 같습니다. 이론적으로 평균 대기 시간을 최소화하는 최적의 알고리즘이지만, 실제 구현에는 난관이 있습니다. 다음 코드를 살펴봅시다. ```python import heapq class SJFScheduler: def __init__(self): self.ready_queue = [] # 최소 힙 (burst_time 기준) def add_process(self, process): # burst_time을 기준으로 힙에 추가 heapq.heappush(self.ready_queue, (process["burst_time"], process["pid"], process)) def schedule(self): # 실행 시간이 가장 짧은 프로세스를 꺼냄 if self.ready_queue: _, _, process = heapq.heappop(self.ready_queue) return process return None # 사용 예시 scheduler = SJFScheduler() scheduler.add_process({"pid": 1, "burst_time": 6}) scheduler.add_process({"pid": 2, "burst_time": 2}) scheduler.add_process({"pid": 3, "burst_time": 8}) next_process = scheduler.schedule() # pid 2 (burst_time: 2)가 먼저 ``` 점심시간, 김개발 씨는 회사 근처 식당에서 줄을 서고 있었습니다. 앞에 있는 손님이 메뉴를 한참 고르는 동안, 뒤에는 이미 주문할 메뉴가 정해진 사람들이 기다리고 있었습니다. "저 사람만 아니면 빨리 주문할 수 있을 텐데..." 문득 아침에 배운 FCFS의 문제점이 떠올랐습니다. **SJF**는 바로 이런 상황을 해결하기 위해 등장했습니다. SJF의 핵심 아이디어는 간단합니다. **실행 시간이 짧은 프로세스를 먼저 처리하자.** 마치 편의점에서 물건 하나만 사는 손님을 먼저 계산해주는 것처럼요. 이렇게 하면 전체적인 대기 시간이 줄어듭니다. 왜 평균 대기 시간이 줄어들까요? 수학적으로 증명할 수 있습니다. 짧은 작업을 먼저 처리하면, 그 뒤에 있는 모든 프로세스의 대기 시간이 줄어듭니다. 반대로 긴 작업을 먼저 처리하면, 뒤에 있는 모든 프로세스가 오래 기다려야 합니다. 따라서 SJF는 **이론적으로 평균 대기 시간을 최소화하는 최적의 알고리즘**입니다. 위의 코드를 살펴보겠습니다. **최소 힙(min-heap)**을 사용한 것이 핵심입니다. Python의 **heapq** 모듈은 기본적으로 최소 힙을 구현합니다. 튜플의 첫 번째 요소인 **burst_time**을 기준으로 정렬되므로, 항상 실행 시간이 가장 짧은 프로세스가 먼저 나옵니다. 그런데 박시니어 씨는 왜 "문제가 있다"고 했을까요? 현실에서는 **프로세스의 실행 시간을 미리 알 수 없습니다**. 프로그램이 얼마나 오래 실행될지 어떻게 알겠습니까? CPU가 미래를 볼 수 있는 것도 아니고요. 이것이 SJF의 가장 큰 한계입니다. 그래서 실제로는 과거의 실행 패턴을 분석해서 다음 실행 시간을 **예측**하는 방식을 사용합니다. 또 다른 심각한 문제가 있습니다. 실행 시간이 긴 프로세스는 **영원히 실행되지 않을 수 있습니다**. 짧은 프로세스가 계속 들어오면, 긴 프로세스는 영원히 뒤로 밀려납니다. 이것을 **기아(Starvation) 현상**이라고 합니다. 마치 편의점에서 물건을 많이 든 손님이 영원히 계산을 못 하는 것과 같습니다. 김개발 씨가 물었습니다. "그럼 SJF는 실제로 쓸 수 없는 건가요?" 박시니어 씨가 대답했습니다. "순수한 SJF는 어렵지만, 이 아이디어를 발전시킨 알고리즘들은 많이 쓰여. 다음에 배울 SRTF도 그중 하나야." **실전 팁** 💡 - SJF도 기본적으로 **비선점형**입니다. 실행 중인 프로세스는 끝까지 실행됩니다. - 실행 시간 예측에는 **지수 평균(Exponential Averaging)** 기법이 자주 사용됩니다. --- ## 3. SRTF (Shortest Remaining Time First) 박시니어 씨가 화이트보드에 그림을 그리며 설명합니다. "SJF가 비선점형이라고 했잖아. 그런데 만약 실행 중에 더 짧은 작업이 들어오면 어떻게 할까?" 김개발 씨의 눈이 반짝입니다. "멈추고 그걸 먼저 처리하면요?" **SRTF(Shortest Remaining Time First)**는 SJF의 선점형 버전입니다. 현재 실행 중인 프로세스보다 남은 실행 시간이 더 짧은 프로세스가 도착하면, 즉시 CPU를 빼앗아 새 프로세스에게 할당합니다. 마치 응급실에서 더 급한 환자가 오면 우선순위가 바뀌는 것과 같습니다. 다음 코드를 살펴봅시다. ```python import heapq class SRTFScheduler: def __init__(self): self.ready_queue = [] self.current_process = None def add_process(self, process, current_time): # 새 프로세스 도착 시 선점 여부 결정 if self.current_process: remaining = self.current_process["remaining_time"] if process["burst_time"] < remaining: # 현재 프로세스를 큐에 다시 넣고 선점 heapq.heappush(self.ready_queue, (remaining, self.current_process["pid"], self.current_process)) self.current_process = process self.current_process["remaining_time"] = process["burst_time"] return True # 선점 발생 heapq.heappush(self.ready_queue, (process["burst_time"], process["pid"], process)) return False def tick(self): # 1단위 시간 실행 if self.current_process: self.current_process["remaining_time"] -= 1 ``` 김개발 씨는 SRTF를 이해하기 위해 실생활의 예를 떠올려 보았습니다. 응급실을 생각해봅시다. 의사가 환자를 치료하고 있는데, 갑자기 더 위급한 환자가 실려 옵니다. 이때 의사는 현재 환자의 치료를 잠시 멈추고 새로 온 환자를 먼저 봅니다. 이것이 바로 **선점(Preemption)**의 개념입니다. **SRTF**는 이 개념을 CPU 스케줄링에 적용한 것입니다. SJF에서는 일단 프로세스가 실행을 시작하면 끝날 때까지 CPU를 놓지 않았습니다. 하지만 SRTF에서는 다릅니다. 새 프로세스가 도착했을 때, 그 프로세스의 실행 시간이 현재 **남은 실행 시간**보다 짧으면 바로 교체합니다. 여기서 핵심은 **"남은 실행 시간"**입니다. 처음 실행 시간이 10초인 프로세스가 이미 6초를 실행했다면, 남은 시간은 4초입니다. 이때 실행 시간이 3초인 새 프로세스가 도착하면, 3초가 4초보다 짧으므로 새 프로세스가 CPU를 가져갑니다. 원래 프로세스는 다시 준비 큐로 돌아가 자기 차례를 기다립니다. 위의 코드에서 **remaining_time** 필드를 주목해주세요. 각 프로세스는 자신의 남은 실행 시간을 기억하고 있습니다. **tick** 메서드가 호출될 때마다 1씩 감소합니다. 새 프로세스가 도착하면 **add_process**에서 현재 프로세스의 남은 시간과 비교하여 선점 여부를 결정합니다. SRTF는 SJF보다 평균 대기 시간을 더 줄일 수 있습니다. 왜냐하면 긴 작업이 실행 중이더라도 짧은 작업이 오면 바로 처리할 수 있기 때문입니다. 짧은 작업들이 불필요하게 오래 기다리지 않아도 됩니다. 하지만 대가가 있습니다. **컨텍스트 스위칭(Context Switching)** 비용이 발생합니다. CPU가 프로세스를 교체할 때마다 현재 상태를 저장하고 새 프로세스의 상태를 불러와야 합니다. 이 과정은 공짜가 아닙니다. 선점이 너무 자주 일어나면 오히려 전체 성능이 떨어질 수 있습니다. 그리고 SJF의 문제점이 그대로 남아있습니다. 실행 시간을 미리 알아야 하고, 긴 프로세스는 여전히 기아 현상에 시달릴 수 있습니다. 짧은 프로세스가 계속 들어오면 긴 프로세스는 영원히 밀려날 수 있습니다. 김개발 씨가 고개를 끄덕입니다. "선점형이 무조건 좋은 건 아니군요." 박시니어 씨가 맞장구칩니다. "그래, 상황에 따라 적절한 알고리즘을 선택하는 게 중요해." **실전 팁** 💡 - SRTF는 **선점형**이므로 컨텍스트 스위칭 오버헤드를 고려해야 합니다. - 실시간 시스템에서는 SRTF보다 더 예측 가능한 스케줄링이 필요할 수 있습니다. --- ## 4. HRRN (Highest Response Ratio Next) 김개발 씨가 걱정스러운 표정으로 물었습니다. "SJF랑 SRTF는 긴 프로세스가 굶어 죽을 수 있다고 했잖아요. 그걸 해결할 방법은 없나요?" 박시니어 씨가 흐뭇한 표정을 지었습니다. "좋은 질문이야. HRRN이라는 게 있어." **HRRN(Highest Response Ratio Next)**은 SJF의 기아 문제를 해결하기 위해 고안된 알고리즘입니다. 단순히 실행 시간만 보는 것이 아니라, 대기 시간도 함께 고려합니다. 응답 비율이라는 공식을 통해 오래 기다린 프로세스에게 높은 우선순위를 부여합니다. 다음 코드를 살펴봅시다. ```python class HRRNScheduler: def __init__(self): self.ready_queue = [] def calculate_response_ratio(self, process, current_time): # 응답 비율 = (대기 시간 + 실행 시간) / 실행 시간 waiting_time = current_time - process["arrival_time"] burst_time = process["burst_time"] return (waiting_time + burst_time) / burst_time def add_process(self, process): self.ready_queue.append(process) def schedule(self, current_time): if not self.ready_queue: return None # 응답 비율이 가장 높은 프로세스 선택 best_process = max(self.ready_queue, key=lambda p: self.calculate_response_ratio(p, current_time)) self.ready_queue.remove(best_process) return best_process # 사용 예시 scheduler = HRRNScheduler() scheduler.add_process({"pid": 1, "burst_time": 10, "arrival_time": 0}) scheduler.add_process({"pid": 2, "burst_time": 2, "arrival_time": 1}) next_process = scheduler.schedule(current_time=5) ``` 박시니어 씨가 화이트보드에 공식을 적습니다. **응답 비율 = (대기 시간 + 실행 시간) / 실행 시간** 김개발 씨가 공식을 유심히 바라봅니다. 처음에는 복잡해 보였지만, 찬찬히 뜯어보니 의미가 보이기 시작했습니다. 이 공식의 핵심은 **대기 시간이 길어질수록 응답 비율이 높아진다**는 것입니다. 예를 들어봅시다. 실행 시간이 10초인 프로세스가 있습니다. 막 도착했을 때(대기 시간 0초)의 응답 비율은 (0+10)/10 = 1입니다. 하지만 20초를 기다렸다면 응답 비율은 (20+10)/10 = 3으로 높아집니다. 반면, 실행 시간이 2초인 짧은 프로세스는 막 도착해도 응답 비율이 (0+2)/2 = 1입니다. 이것이 어떤 의미일까요? 처음에는 짧은 프로세스가 유리합니다. SJF처럼요. 하지만 시간이 지날수록 오래 기다린 프로세스의 응답 비율이 올라갑니다. 어느 순간 긴 프로세스의 응답 비율이 짧은 프로세스보다 높아지면, 긴 프로세스가 선택됩니다. 이것이 바로 **에이징(Aging)** 기법입니다. 나이가 들면(오래 기다리면) 우선순위가 높아지는 것이죠. 마치 경로우대처럼요. 오래 기다린 사람에게는 먼저 서비스할 기회를 주는 것입니다. 위의 코드에서 **calculate_response_ratio** 함수를 살펴보세요. 현재 시간에서 도착 시간을 빼서 대기 시간을 계산합니다. 그리고 공식대로 응답 비율을 구합니다. **schedule** 함수에서는 모든 프로세스의 응답 비율을 계산하여 가장 높은 것을 선택합니다. HRRN의 장점은 명확합니다. SJF의 효율성을 유지하면서도 기아 현상을 방지합니다. 짧은 프로세스는 여전히 빨리 처리되고, 긴 프로세스도 언젠가는 반드시 실행됩니다. 두 마리 토끼를 모두 잡은 셈이죠. 하지만 단점도 있습니다. 매번 스케줄링할 때마다 모든 프로세스의 응답 비율을 계산해야 합니다. 준비 큐에 프로세스가 많으면 오버헤드가 커질 수 있습니다. 또한 HRRN도 **비선점형**이라서, 한 번 실행이 시작되면 끝날 때까지 기다려야 합니다. 김개발 씨가 감탄합니다. "공식 하나로 두 가지 문제를 해결하다니, 정말 똑똑한 방법이네요!" 박시니어 씨가 고개를 끄덕입니다. "알고리즘 설계의 묘미지. 단순해 보이지만 깊은 통찰이 담겨 있어." **실전 팁** 💡 - HRRN은 **비선점형**이며, 스케줄링 시점에 응답 비율을 계산합니다. - 응답 비율 계산 오버헤드가 있으므로 프로세스 수가 적을 때 더 효과적입니다. --- ## 5. Convoy Effect 문제 김개발 씨가 출근길 지하철에서 경험한 일입니다. 캐리어를 끄는 사람이 좁은 통로를 천천히 걸어가자, 뒤에 있는 모든 사람이 발을 맞춰 느리게 걸어야 했습니다. 사무실에 도착해서 그 이야기를 하자, 박시니어 씨가 말했습니다. "그게 바로 Convoy Effect야." **Convoy Effect**는 실행 시간이 긴 프로세스가 CPU를 점유하는 동안, 짧은 프로세스들이 줄지어 기다리는 현상입니다. 마치 느린 트럭 뒤에 빠른 차들이 줄지어 서행하는 것과 같습니다. FCFS 알고리즘에서 특히 심각하게 발생하며, 전체 시스템의 효율성을 크게 떨어뜨립니다. 다음 코드를 살펴봅시다. ```python def simulate_convoy_effect(): # FCFS 스케줄링 시뮬레이션 processes = [ {"pid": 1, "burst_time": 100, "arrival_time": 0}, # CPU 집약적 {"pid": 2, "burst_time": 5, "arrival_time": 1}, # I/O 집약적 {"pid": 3, "burst_time": 3, "arrival_time": 2}, # I/O 집약적 {"pid": 4, "burst_time": 2, "arrival_time": 3}, # I/O 집약적 ] current_time = 0 total_waiting = 0 for p in processes: waiting = max(0, current_time - p["arrival_time"]) total_waiting += waiting print(f"PID {p['pid']}: 대기 {waiting}초, 실행 {p['burst_time']}초") current_time += p["burst_time"] print(f"평균 대기 시간: {total_waiting / len(processes):.1f}초") # 결과: PID 2,3,4는 100초 가까이 대기! simulate_convoy_effect() ``` 김개발 씨는 고속도로를 떠올렸습니다. 편도 1차선 도로에 대형 트럭이 시속 60km로 달리고 있습니다. 뒤에는 시속 100km로 달릴 수 있는 승용차들이 줄지어 있습니다. 추월이 불가능하니, 모든 차가 시속 60km로 갈 수밖에 없습니다. 이것이 바로 **Convoy Effect**의 본질입니다. CPU 스케줄링에서도 마찬가지 상황이 발생합니다. FCFS 알고리즘에서 실행 시간이 100초인 CPU 집약적 프로세스가 먼저 도착했다고 가정합시다. 그 직후에 실행 시간이 2초, 3초, 5초인 I/O 집약적 프로세스들이 도착합니다. 이 프로세스들은 모두 100초를 기다려야 합니다. 위의 코드 실행 결과를 보면 충격적입니다. PID 1은 대기 시간 0초에 100초를 실행합니다. 하지만 PID 2는 99초를 기다리고, PID 3은 101초를, PID 4는 103초를 기다립니다. 실행 시간이 고작 2~5초인 프로세스들이 100초 넘게 기다리는 것입니다. 평균 대기 시간이 급격히 늘어납니다. 왜 이것이 문제일까요? **시스템 전체의 활용도가 떨어집니다.** I/O 집약적 프로세스는 CPU를 잠깐 쓰고 I/O 작업을 하러 갑니다. 그동안 다른 프로세스가 CPU를 쓸 수 있죠. 하지만 Convoy Effect로 인해 I/O 장치는 놀고, CPU만 한 프로세스가 독점합니다. 실제 시스템에서는 더 심각합니다. 웹 서버를 생각해봅시다. 대부분의 요청은 빠르게 처리됩니다. 하지만 가끔 무거운 요청이 들어옵니다. 이 무거운 요청이 CPU를 점유하는 동안, 가벼운 요청들이 모두 기다립니다. 사용자들은 간단한 페이지 조회에도 오랜 시간을 기다려야 합니다. 해결책은 무엇일까요? 가장 직접적인 해결책은 **SJF나 SRTF를 사용**하는 것입니다. 짧은 프로세스를 먼저 처리하면 Convoy Effect를 피할 수 있습니다. 또는 **라운드 로빈(Round Robin)** 방식을 사용하여 시간을 나눠 쓰게 할 수도 있습니다. 박시니어 씨가 정리합니다. "Convoy Effect는 FCFS의 대표적인 단점이야. 그래서 현대 운영체제는 더 정교한 스케줄링 알고리즘을 사용하지." 김개발 씨가 고개를 끄덕입니다. 아침에 지하철에서 겪었던 불편함이 이제 알고리즘 문제로 다가왔습니다. **실전 팁** 💡 - Convoy Effect는 **비선점형 스케줄링**에서 주로 발생합니다. - I/O 집약적 프로세스와 CPU 집약적 프로세스가 섞여 있을 때 특히 심각해집니다. --- ## 6. 기아 현상과 해결책 김개발 씨가 점심 식당에서 또 한 번 경험을 합니다. 항상 급한 손님에게 먼저 음식을 주는 식당에서, 느긋하게 앉아 있던 손님이 두 시간이 지나도 음식을 받지 못했습니다. 박시니어 씨가 말합니다. "그게 바로 기아 현상이야. 컴퓨터에서도 똑같은 일이 벌어져." **기아(Starvation) 현상**은 특정 프로세스가 CPU를 할당받지 못하고 무한히 대기하는 상황입니다. 우선순위 기반 스케줄링이나 SJF에서 발생할 수 있습니다. 해결책으로는 에이징(Aging) 기법이 대표적이며, HRRN 알고리즘이 이를 구현한 예입니다. 다음 코드를 살펴봅시다. ```python class AgingScheduler: def __init__(self, aging_factor=1): self.ready_queue = [] self.aging_factor = aging_factor # 시간당 우선순위 증가량 def add_process(self, process): process["effective_priority"] = process["base_priority"] process["wait_start"] = 0 self.ready_queue.append(process) def apply_aging(self, current_time): # 대기 중인 모든 프로세스의 우선순위 증가 for p in self.ready_queue: wait_time = current_time - p["wait_start"] p["effective_priority"] = p["base_priority"] + (wait_time * self.aging_factor) def schedule(self, current_time): if not self.ready_queue: return None self.apply_aging(current_time) # 가장 높은 유효 우선순위 선택 best = max(self.ready_queue, key=lambda p: p["effective_priority"]) self.ready_queue.remove(best) return best # 낮은 우선순위 프로세스도 시간이 지나면 실행됨 ``` 기아 현상을 이해하기 위해 비유를 들어봅시다. 놀이공원의 롤러코스터를 상상해보세요. VIP 패스를 가진 손님은 항상 먼저 탑니다. 일반 손님은 VIP가 없을 때만 탈 수 있습니다. 그런데 VIP 손님이 끊임없이 온다면? 일반 손님은 영원히 롤러코스터를 타지 못합니다. 이것이 바로 **기아(Starvation)**입니다. 컴퓨터에서도 똑같습니다. **SJF**에서는 실행 시간이 짧은 프로세스가 계속 도착하면, 긴 프로세스는 영원히 실행되지 못할 수 있습니다. **우선순위 스케줄링**에서는 높은 우선순위 프로세스가 계속 오면, 낮은 우선순위 프로세스가 굶어 죽습니다. 기아 현상이 왜 문제일까요? 시스템의 **공정성(Fairness)**이 무너집니다. 모든 프로세스는 어느 정도의 서비스를 받을 권리가 있습니다. 특정 프로세스가 영원히 무시당하는 것은 운영체제 설계 원칙에 어긋납니다. 또한 **예측 불가능성**도 문제입니다. 언제 실행될지 알 수 없으면 시스템을 신뢰할 수 없습니다. 해결책의 핵심은 **에이징(Aging)**입니다. 에이징은 간단한 아이디어입니다. **오래 기다린 프로세스의 우선순위를 점진적으로 높여주는 것**입니다. 아무리 낮은 우선순위로 시작해도, 시간이 지나면 우선순위가 올라갑니다. 언젠가는 가장 높은 우선순위가 되어 반드시 실행됩니다. 위의 코드에서 **apply_aging** 함수를 보세요. 대기 시간에 **aging_factor**를 곱해서 유효 우선순위에 더합니다. 기본 우선순위가 1인 프로세스도, 100초를 기다리면 유효 우선순위가 101이 됩니다. 기본 우선순위가 50인 프로세스보다 높아지는 것이죠. 앞서 배운 **HRRN**이 바로 에이징을 적용한 예입니다. HRRN의 응답 비율 공식을 다시 보면, 대기 시간이 분자에 들어갑니다. 대기 시간이 길어질수록 응답 비율이 높아지고, 결국 그 프로세스가 선택됩니다. 수학적으로 에이징을 구현한 것입니다. 다른 해결책도 있습니다. **라운드 로빈(Round Robin)**은 모든 프로세스에게 동일한 시간을 할당합니다. 우선순위와 관계없이 순서대로 조금씩 실행합니다. 기아가 발생할 수 없는 구조입니다. **다단계 피드백 큐(Multilevel Feedback Queue)**는 더 정교한 방식으로, 프로세스의 행동에 따라 우선순위를 동적으로 조절합니다. 김개발 씨가 정리합니다. "결국 공정성과 효율성 사이에서 균형을 찾는 거군요." 박시니어 씨가 미소 짓습니다. "바로 그거야. 운영체제 설계의 핵심이지." 오늘 배운 스케줄링 알고리즘들은 모두 이 균형을 찾기 위한 시도입니다. 각각의 장단점을 이해하고, 상황에 맞게 선택하는 것이 중요합니다. **실전 팁** 💡 - 에이징 계수(aging factor)를 너무 크게 설정하면 우선순위의 의미가 사라질 수 있습니다. - 현대 운영체제는 여러 기법을 조합한 **다단계 피드백 큐**를 주로 사용합니다. --- 이상으로 학습을 마칩니다. 위 내용을 직접 코드로 작성해보면서 익혀보세요!

카테고리: Operating System

언어: Python

태그: OperatingSystem, CPUScheduling, FCFS, SJF, ProcessManagement, Operating System

작성자: AI Generated

프리미엄 콘텐츠 - 3개월 무료 체험 가능

CodeDeck

CPU 스케줄링 알고리즘 완벽 가이드 (1)

목차

1. FCFS (First Come First Served)

2. SJF (Shortest Job First)

3. SRTF (Shortest Remaining Time First)

4. HRRN (Highest Response Ratio Next)

5. Convoy Effect 문제

6. 기아 현상과 해결책

댓글 (0)

함께 보면 좋은 카드 뉴스

교착 상태 (Deadlock) 완벽 가이드

동기화 도구 완벽 가이드

프로세스 동기화 완벽 가이드

CPU 스케줄링 알고리즘 (2)

CPU 스케줄링 기초 완벽 가이드