시스매

운영체제의 지휘자 프로세스 스케줄링 완벽 정복 핸드북

21 min read

2025-09-22 23:45

  • 운영체제(OS)의 핵심 기능인 프로세스 스케줄링은 한정된 CPU 자원을 여러 프로세스에 효율적으로 분배하는 규칙이자 정책이다.

  • 스케줄링 알고리즘은 FCFS, SJF, 라운드 로빈 등 다양하며, 시스템의 목표(응답 시간, 처리량 등)에 따라 적합한 방식을 선택해야 한다.

  • 현대 운영체제는 다단계 큐와 같은 복합적인 알고리즘을 사용하여 사용자와 시스템 프로세스 모두를 만족시키는 정교한 스케줄링을 수행한다.

운영체제의 지휘자 프로세스 스케줄링 완벽 정복 핸드북

컴퓨터의 두뇌인 CPU는 한 번에 하나의 작업만 처리할 수 있다. 하지만 우리는 동시에 웹서핑을 하고, 음악을 들으며, 문서를 작성한다. 어떻게 이런 마법 같은 일이 가능할까? 그 비밀의 중심에는 바로 **프로세스 스케줄링(Process Scheduling)**이 있다. 프로세스 스케줄링은 운영체제(OS)의 심장과 같은 역할로, 어떤 프로세스에게 CPU를 할당할지 결정하는 정교한 정책이자 규칙의 집합이다.

이 핸드북은 컴퓨터 공학의 근간을 이루는 프로세스 스케줄링의 모든 것을 탐험한다. 왜 스케줄링이 탄생했는지, 어떤 구조로 동작하는지, 그리고 다양한 스케줄링 알고리즘들이 어떻게 각자의 장단점 속에서 최적의 시스템 성능을 이끌어내는지 심도 있게 알아볼 것이다.

1. 프로세스 스케줄링의 탄생 배경 왜 필요한가

초기 컴퓨터는 한 번에 하나의 프로그램만 실행하는 일괄 처리(Batch Processing) 시스템이었다. 사용자가 작업을 제출하면, 컴퓨터는 그 작업이 끝날 때까지 다른 어떤 일도 할 수 없었다. 이는 CPU가 입출력(I/O) 작업을 기다리며 아무 일도 하지 않고 노는 시간이 많아지는 엄청난 비효율을 낳았다.

이 문제를 해결하기 위해 **시분할(Time-Sharing)**과 다중 프로그래밍(Multi-programming) 개념이 등장했다. 여러 개의 프로그램을 메모리에 동시에 올려놓고(다중 프로그래밍), CPU의 처리 시간을 아주 짧은 단위로 쪼개어 여러 프로그램에 번갈아 할당하는(시분할) 것이다. 이렇게 함으로써 CPU는 한 프로세스가 입출력을 기다리는 동안 다른 프로세스의 작업을 처리하며 쉴 틈 없이 일하게 되었다.

바로 이 지점에서 “누구에게, 언제, 얼마만큼 CPU를 할당할 것인가?”라는 근본적인 질문이 생겨났고, 이 질문에 대한 답을 내리는 규칙이 바로 프로세스 스케줄링이다.

쉽게 비유하자면, 인기 레스토랑에 최고의 셰프(CPU)가 한 명뿐인 상황과 같다. 주문서(프로세스)는 계속해서 밀려들어 온다. 셰프는 어떤 주문을 먼저 처리해야 할까? 간단한 샐러드 주문을 먼저 처리해 많은 손님을 빨리 내보낼까? 아니면 오래 걸리는 스테이크 주문을 먼저 시작할까? 혹은 모든 테이블의 주문을 조금씩 번갈아 가며 요리할까? 이 결정을 내리는 주방 관리자의 역할이 바로 운영체제의 스케줄러다.

2. 프로세스 스케줄링의 구조와 목표

프로세스 스케줄링은 단순히 아무 프로세스나 선택하는 것이 아니라, 명확한 목표와 체계적인 구조하에 동작한다.

스케줄러의 종류

스케줄러는 역할과 실행 주기에 따라 세 가지로 나눌 수 있다.

구분역할실행 주기비유
장기 스케줄러 (Long-term Scheduler)어떤 프로세스를 시스템에 제출할지 결정. 즉, 디스크에 있는 프로그램을 메모리로 가져와 ‘준비(Ready)’ 상태 큐에 넣을지 결정한다.상대적으로 길다 (수 초 ~ 수 분)대학의 입학 사정관. 어떤 학생(프로그램)을 학교(메모리)에 입학시킬지 결정.
단기 스케줄러 (Short-term Scheduler)‘준비’ 상태의 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정.매우 짧다 (수 밀리초)강의실의 교수. 손을 든 학생(준비된 프로세스) 중 누구에게 발표 기회(CPU)를 줄지 결정.
중기 스케줄러 (Medium-term Scheduler)메모리에 적재된 프로세스 중 일부를 일시적으로 디스크로 내보내(Swap-out) 메모리 공간을 확보한다.장기와 단기의 중간기숙사 사감. 기숙사(메모리)가 꽉 찼을 때 일부 학생을 잠시 집으로 보내(Swap-out) 공간을 마련.

선점형 vs 비선점형 스케줄링

스케줄링 방식은 크게 두 가지로 나뉜다.

  • 비선점형 (Non-preemptive): 한 프로세스가 CPU를 할당받으면, 해당 프로세스가 스스로 CPU를 반납할 때까지(작업이 끝나거나 I/O 대기 상태가 될 때까지) 다른 프로세스가 CPU를 빼앗을 수 없는 방식. 모든 프로세스가 공정하게 CPU 시간을 보장받지만, 긴 작업을 하는 프로세스 하나가 전체 시스템의 응답성을 떨어뜨릴 수 있다.

  • 선점형 (Preemptive): 한 프로세스가 CPU를 사용하고 있더라도, 더 높은 우선순위의 프로세스가 도착하거나 현재 프로세스의 할당 시간이 다 되면 운영체제가 강제로 CPU를 빼앗아 다른 프로세스에게 할당할 수 있는 방식. 빠른 응답성이 중요한 시분할 시스템에 적합하지만, 잦은 문맥 교환(Context Switching)으로 인한 오버헤드가 발생할 수 있다.

성능 평가 척도

좋은 스케줄링 알고리즘이란 무엇일까? 이는 시스템의 목표에 따라 달라지며, 다음과 같은 척도로 평가할 수 있다.

척도설명목표 방향
CPU 이용률 (CPU Utilization)전체 시간 중 CPU가 일한 시간의 비율.최대화 (Maximize)
처리량 (Throughput)단위 시간당 완료된 프로세스의 개수.최대화 (Maximize)
총처리 시간 (Turnaround Time)프로세스가 시스템에 제출된 순간부터 완료될 때까지 걸린 총 시간. (대기 시간 + 실행 시간)최소화 (Minimize)
대기 시간 (Waiting Time)프로세스가 준비 큐에서 CPU를 기다리며 보낸 시간의 총합.최소화 (Minimize)
응답 시간 (Response Time)사용자가 요청을 보낸 후 첫 번째 응답을 받을 때까지 걸린 시간.최소화 (Minimize)

이 척도들은 서로 상충 관계에 있는 경우가 많다. 예를 들어, 응답 시간을 줄이기 위해 문맥 교환을 자주 하면 오버헤드가 늘어나 처리량이 감소할 수 있다. 따라서 시스템의 목적(예: 일괄 처리 시스템 vs. 대화형 시스템)에 맞는 적절한 균형점을 찾는 것이 중요하다.

3. 핵심 스케줄링 알고리즘 완전 분석

이제 여러 가지 스케줄링 알고리즘의 동작 방식과 특징을 구체적인 예시와 함께 살펴보자. (예시: 프로세스 P1, P2, P3가 있고, 실행 시간은 각각 24, 3, 3이며, 동시에 도착했다고 가정)

1. FCFS (First-Come, First-Served) 선입선출

  • 동작 방식: 준비 큐에 도착한 순서대로 CPU를 할당하는 가장 단순한 비선점형 알고리즘. 마치 은행 창구에서 번호표 순서대로 업무를 보는 것과 같다.

  • 예시: P1, P2, P3 순으로 도착했다면, P1(24) → P2(3) → P3(3) 순으로 실행된다.

    • 간트 차트(Gantt Chart):

      | P1 (0-24) | P2 (24-27) | P3 (27-30) |

    • 평균 대기 시간: (0+24+27)/3=17

  • 장단점:

    | 장점 | 단점 |

    | :--- | :--- |

    | 구현이 매우 간단하고 직관적이다. | **호위 효과(Convoy Effect)**가 발생할 수 있다. 실행 시간이 긴 프로세스가 먼저 도착하면 뒤따르는 짧은 프로세스들이 하염없이 기다려야 해서 전체 평균 대기 시간이 길어진다. |

    | 특정 프로세스가 차별받지 않는다. | 비선점형이므로 응답 시간이 중요한 대화형 시스템에는 부적합하다. |

2. SJF (Shortest-Job-First) 최단 작업 우선

  • 동작 방식: 준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당한다. 평균 대기 시간을 최소화하는 데 있어 최적의 알고리즘으로 증명되었다.

  • 예시: P2(3), P3(3), P1(24) 순으로 실행된다.

    • 간트 차트:

      | P2 (0-3) | P3 (3-6) | P1 (6-30) |

    • 평균 대기 시간: (6+0+3)/3=3 (FCFS의 17에 비해 극적으로 감소)

  • 장단점:

    | 장점 | 단점 |

    | :--- | :--- |

    | 평균 대기 시간을 최소화하여 시스템의 효율을 높인다. | 프로세스의 실행 시간을 미리 알 수 없다는 치명적인 문제가 있다. (현실적으로 적용 불가능) |

    | | **기아 현상(Starvation)**이 발생할 수 있다. 실행 시간이 긴 프로세스는 계속해서 들어오는 짧은 프로세스들에 밀려 영원히 CPU를 할당받지 못할 수 있다. |

  • 파생 알고리즘: SRTF (Shortest-Remaining-Time-First)

    SJF의 선점형 버전. 현재 실행 중인 프로세스의 남은 시간보다 더 짧은 실행 시간을 가진 프로세스가 도착하면, CPU를 빼앗아 새로운 프로세스에게 할당한다.

3. Priority Scheduling 우선순위

  • 동작 방식: 각 프로세스에 우선순위(Priority)를 부여하고, 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당한다. SJF는 우선순위를 ‘예상 실행 시간’으로 간주한 특별한 경우라고 볼 수 있다.

  • 장단점:

    | 장점 | 단점 |

    | :--- | :--- |

    | 시스템의 중요한 작업을 먼저 처리하도록 보장할 수 있다. | SJF와 마찬가지로 기아 현상이 발생할 수 있다. 낮은 우선순위의 프로세스는 영원히 실행되지 않을 수 있다. |

    | 우선순위를 동적으로 조정하여 시스템 목표에 맞게 유연하게 운영할 수 있다. | |

  • 기아 현상 해결책: 노화(Aging)

    오랜 시간 대기한 프로세스의 우선순위를 점진적으로 높여주는 기법. 결국에는 어떤 프로세스든 언젠가는 가장 높은 우선순위를 갖게 되어 실행을 보장받는다.

4. Round Robin (RR) 라운드 로빈

  • 동작 방식: FCFS에 **시간 할당량(Time Quantum 또는 Time Slice)**이라는 개념을 추가한 선점형 알고리즘. 각 프로세스는 최대 시간 할당량만큼만 CPU를 사용하고, 시간이 다 되면 준비 큐의 맨 뒤로 이동한다. 현대 시분할 시스템의 근간이 되는 방식이다.

  • 예시: 시간 할당량이 4라고 가정.

    • 간트 차트:

      | P1 (0-4) | P2 (4-7) | P3 (7-10) | P1 (10-14) | P1 (14-18) | ... |

  • 특징:

    • 시간 할당량의 크기가 성능에 큰 영향을 미친다.

      • 크면? FCFS와 비슷하게 동작하며, 긴 프로세스가 끝날 때까지 다른 프로세스의 응답이 늦어진다.

      • 작으면? 응답 시간은 빨라지지만, 잦은 문맥 교환으로 인한 오버헤드가 커져 시스템 전체 성능이 저하된다. (일반적으로 10~100ms 사이로 설정)

  • 장단점:

    | 장점 | 단점 |

    | :--- | :--- |

    | 모든 프로세스가 공평하게 CPU 시간을 보장받는다. | 시간 할당량 설정이 중요하다. |

    | 응답 시간이 빨라 대화형 시스템에 적합하다. | 평균 총처리 시간은 SJF보다 긴 경향이 있다. |

4. 심화 탐구 현대적인 스케줄링 기법

현대 운영체제는 위에서 설명한 단순한 알고리즘 하나만 사용하지 않는다. 여러 알고리즘을 결합하여 훨씬 더 정교하고 복잡한 스케줄링을 수행한다.

1. 다단계 큐 스케줄링 (Multilevel Queue Scheduling)

준비 큐를 여러 개의 독립적인 큐로 분리하는 방식. 각 큐는 자신만의 스케줄링 알고리즘을 가질 수 있다.

  • 예시:

    • 전위(Foreground) 큐: 사용자와 상호작용이 잦은 대화형 프로세스들을 위한 큐. 응답성이 중요하므로 라운드 로빈(RR) 방식을 사용.

    • 후위(Background) 큐: 사용자와 상호작용이 없는 일괄 처리 프로세스들을 위한 큐. 응답성보다 처리 효율이 중요하므로 FCFS 방식을 사용.

큐와 큐 사이의 스케줄링도 필요하다. 보통 전위 큐에 절대적인 우선권을 부여하는 고정 우선순위 방식을 사용한다. 즉, 전위 큐가 비어 있을 때만 후위 큐의 프로세스를 실행한다.

2. 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

다단계 큐에서 한 단계 더 나아가, 프로세스가 큐 사이를 이동할 수 있도록 허용한 방식이다. 가장 일반적이고 복잡하며, 많은 운영체제에서 채택하고 있다.

  • 동작 원리:

    1. 프로세스는 처음에 가장 우선순위가 높은 큐(가장 짧은 시간 할당량)에 들어간다.

    2. 자신의 시간 할당량을 다 사용하고도 작업이 끝나지 않으면, 한 단계 낮은 우선순위의 큐(더 긴 시간 할당량)로 이동한다.

    3. 가장 낮은 우선순위 큐에서는 보통 FCFS 방식으로 처리된다.

    4. 특정 큐에서 너무 오래 대기하는 프로세스는 노화 기법을 통해 더 높은 우선순위의 큐로 이동시켜 기아 현상을 방지한다.

이 방식은 CPU 위주(CPU-bound)의 프로세스는 자연스럽게 낮은 우선순위 큐로, 입출력 위주(I/O-bound)의 프로세스는 짧게 CPU를 쓰고 대기 상태로 빠지므로 높은 우선순위 큐에 계속 머물게 하는 효과가 있다. 즉, 프로세스의 특성을 자동으로 구분하여 그에 맞는 스케줄링을 적용하는 매우 지능적인 방법이다.

결론 가장 좋은 알고리즘이란?

지금까지 살펴본 것처럼, “가장 좋은” 단 하나의 스케줄링 알고리즘은 존재하지 않는다.

  • 일괄 처리 시스템처럼 처리량이 중요하다면 FCFS나 SJF 계열이 유리할 수 있다.

  • 대화형 시스템처럼 응답 시간이 중요하다면 라운드 로빈이나 다단계 피드백 큐가 필수적이다.

프로세스 스케줄링은 운영체제가 주어진 자원을 가지고 최상의 사용자 경험과 시스템 효율을 만들어내기 위한 끊임없는 고민의 산물이다. 우리가 컴퓨터 앞에서 느끼는 쾌적함과 빠릿함은 보이지 않는 곳에서 쉴 새 없이 돌아가는 이 정교한 ‘지휘자’ 덕분이라는 것을 기억하자. 이 핸드북이 그 복잡하고 아름다운 오케스트라의 움직임을 이해하는 데 훌륭한 안내서가 되었기를 바란다.

그래프 뷰