스케줄링 알고리즘

왜 배우는가: 스케줄링 알고리즘은 CPU라는 한정된 자원을 여러 프로세스와 태스크에 나누는 기준이며, 실시간 시스템의 데드라인 보장과 멀티프로세서 부하 분산을 결정한다. 기술사 시험에서는 RM, EDF, RR, MLQ, SQMS, MQMS 등이 용어형과 논술형으로 반복해서 출제되므로 정의와 비교 기준을 정확히 잡아 두어야 한다.

출제 이력: 제135회 3교시 4번, 제111회 1교시 1번, 제108회 1교시 6번

1. 한 줄 정의와 핵심 키워드

스케줄링 알고리즘은 준비 상태의 프로세스·태스크에 CPU를 배분하는 순서와 시점을 정하는 운영체제 정책이다.

• 스케줄링 알고리즘: 준비 큐에서 다음에 실행할 작업을 고르는 규칙
• 선점형 스케줄링: 실행 중인 작업을 강제로 중단하고 CPU를 넘기는 방식
• RM(Rate Monotonic): 주기가 짧은 태스크에 높은 정적 우선순위를 주는 실시간 알고리즘
• EDF(Earliest Deadline First): 마감 시각이 가장 가까운 태스크를 먼저 실행하는 동적 우선순위 알고리즘
• RR(Round Robin): 시간 할당량(Time Quantum)을 순서대로 나눠 주는 방식
• MLQ(Multi-Level Queue): 우선순위별 준비 큐를 나누고 큐마다 다른 알고리즘을 적용하는 방식
• SQMS / MQMS: 멀티프로세서에서 준비 큐를 하나로 쓰는지 CPU마다 나눠 쓰는지에 따른 구분

2. 개념 풀이

쉽게 말하면 스케줄러는 줄 선 작업 중 누구를 먼저 CPU에 올릴지 정하는 사람이다. 줄을 어떻게 세우고 언제 끼어들게 할지가 알고리즘마다 다르다.

정식으로는 n개의 작업이 주어졌을 때 응답시간, 처리율, 공정성, 마감 준수 같은 목표를 최대한 만족하도록 CPU 할당 순서를 정하는 정책을 말한다. 시험에서는 목표를 먼저 밝히고 알고리즘을 설명하는 것이 점수에 유리하다.

핵심 용어를 나누면 다음과 같다.

정적 우선순위는 작업이 실행되는 동안 우선순위가 바뀌지 않는 방식이다. RM이 여기에 해당한다. 우선순위는 주기로 미리 정해진다.

동적 우선순위는 실행 중 상황에 따라 우선순위가 바뀌는 방식이다. EDF는 매 스케줄링 시점마다 마감 시각을 비교해 우선순위를 다시 정한다.

선점(Preemption)은 더 높은 우선순위 작업이 도착하면 현재 실행 중인 작업을 중단시키는 것이다. RM과 EDF는 모두 선점형으로 동작한다.

시간 할당량(Time Quantum)은 한 작업이 CPU를 연속으로 쓸 수 있는 최대 시간이다. RR의 핵심 파라미터이며 시스템 특성에 맞게 설정한다. 너무 짧으면 문맥 전환 오버헤드가 커지고, 너무 길면 FCFS와 같아져 응답시간이 나빠진다.

CPU 이용률 상한은 작업들의 실행 시간 대비 주기 비율의 합이다. 실시간 스케줄 가능 여부를 판단하는 수치다. RM은 작업 수 n에 따라 달라지는 상한을 쓰고, EDF는 이론상 100%까지 쓸 수 있다.

3. 등장 배경과 필요성

초기 운영체제는 FCFS나 SJF처럼 단순한 정책을 썼지만, 대화형 시스템과 실시간 제어가 늘면서 응답시간과 마감 보장이 필요해졌다. 항공기 제어, 자동차 엔진 제어, 산업용 로봇처럼 정해진 시간 안에 결과를 내야 하는 시스템에서는 평균 성능보다 최악의 경우 응답시간이 중요하다.

1973년 Liu와 Layland가 주기적 실시간 태스크에 대한 정적 우선순위 이론인 RM을 제안하면서, 실시간 스케줄 가능성을 수학적으로 판정하는 길이 열렸다. 이후 동적 우선순위인 EDF가 함께 연구되어 이용률 한계 측면에서 비교 기준이 되었다.