OS 스케줄링 알고리즘 종류 및 작동 방식 완벽 가이드

OS 스케줄링 알고리즘 종류 및 작동 방식 완벽 가이드

 

운영체제에서 프로세스 스케줄링은 CPU 자원을 효율적으로 관리하는 핵심 기능입니다.

다양한 스케줄링 알고리즘을 이해하면 시스템 성능 최적화와 멀티태스킹 환경에서의 프로세스 관리를 더욱 효과적으로 할 수 있습니다.

이 글에서는 주요 OS 스케줄링 알고리즘의 종류와 작동 방식을 상세히 알아보겠습니다.

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

프로세스 스케줄링은 운영체제가 여러 프로세스 중에서 어떤 프로세스가 CPU를 사용할지 결정하는 과정입니다.

현대의 멀티태스킹 환경에서는 동시에 실행되는 여러 프로세스가 존재하지만, CPU는 한 번에 하나의 프로세스만 실행할 수 있습니다.

따라서 스케줄러가 프로세스들 사이에서 CPU 시간을 공정하고 효율적으로 배분하는 역할을 담당합니다.

스케줄링의 주요 목표

• CPU 이용률 최대화: CPU가 유휴 상태에 있는 시간을 최소화
• 처리량 향상: 단위 시간당 완료되는 프로세스 수 증가
• 응답 시간 단축: 사용자 요청에 대한 빠른 응답 제공
• 대기 시간 최소화: 프로세스가 준비 큐에서 대기하는 시간 감소
• 공정성 보장: 모든 프로세스가 적절한 CPU 시간을 할당받도록 보장

선입선출(FCFS) 스케줄링 알고리즘

First Come First Served(FCFS) 스케줄링은 가장 단순한 CPU 스케줄링 알고리즘입니다.

프로세스가 준비 큐에 도착한 순서대로 CPU를 할당받는 비선점형 스케줄링 방식입니다.

FCFS 스케줄링 작동 원리

프로세스 | 도착시간 | 실행시간
P1      | 0       | 24
P2      | 1       | 3  
P3      | 2       | 3

실행 순서: P1 → P2 → P3
간트 차트: [P1: 0-24] [P2: 24-27] [P3: 27-30]

이 예제에서 P1이 먼저 도착했으므로 24ms 동안 실행됩니다.

P1이 완료된 후 P2가 3ms 실행되고, 마지막으로 P3가 3ms 실행됩니다.

FCFS의 장단점

장점:

• 구현이 매우 간단하고 직관적
• 기아 상태(starvation) 발생하지 않음
• 공정한 처리 순서 보장

단점:

• 호위 효과(convoy effect) 발생 가능
• 평균 대기 시간이 길어질 수 있음
• 대화형 시스템에 부적합

최단 작업 우선(SJF) 스케줄링 알고리즘

Shortest Job First(SJF) 스케줄링은 실행 시간이 가장 짧은 프로세스에게 우선적으로 CPU를 할당하는 알고리즘입니다.

이론적으로 평균 대기 시간을 최소화할 수 있는 최적의 스케줄링 알고리즘으로 알려져 있습니다.

SJF 스케줄링 예제

프로세스 | 도착시간 | 실행시간
P1      | 0       | 6
P2      | 1       | 8
P3      | 2       | 7
P4      | 3       | 3

비선점 SJF 실행 순서: P1 → P4 → P1 → P3 → P2
선점 SJF(SRTF) 실행: 더 짧은 작업이 도착하면 현재 작업 중단

선점형 SJF는 SRTF(Shortest Remaining Time First)라고도 불리며, 새로운 프로세스가 도착했을 때 남은 실행 시간을 비교하여 더 짧은 프로세스로 전환합니다.

SJF의 특징과 한계

장점:

• 평균 대기 시간 최소화
• 짧은 프로세스의 빠른 처리

단점:

• 실행 시간 예측의 어려움
• 긴 프로세스의 기아 상태 발생 가능
• 구현 복잡성 증가

라운드 로빈(RR) 스케줄링 알고리즘

Round Robin(RR) 스케줄링은 시분할 시스템을 위해 설계된 선점형 스케줄링 알고리즘입니다.

각 프로세스에게 동일한 크기의 시간 할당량(time quantum)을 부여하고, 이 시간이 경과하면 다음 프로세스로 전환합니다.

라운드 로빈 스케줄링 동작 과정

프로세스 | 실행시간 | 시간 할당량: 4ms
P1      | 24      
P2      | 3       
P3      | 3       

실행 순서:
[P1: 0-4] [P2: 4-7] [P3: 7-10] [P1: 10-14] [P1: 14-18] [P1: 18-22] [P1: 22-26]

이 예제에서 각 프로세스는 4ms의 시간 할당량을 받습니다.

P1이 4ms 실행된 후 P2로 전환되고, P2가 완료되면 P3로 전환됩니다.

P3 완료 후 다시 P1으로 돌아가서 남은 작업을 계속 처리합니다.

시간 할당량 설정의 중요성

시간 할당량의 크기는 라운드 로빈 스케줄링의 성능에 큰 영향을 미칩니다.

• 너무 큰 할당량: FCFS와 유사하게 동작
• 너무 작은 할당량: 컨텍스트 스위칭 오버헤드 증가
• 적절한 할당량: 응답 시간과 처리량의 균형 달성

일반적으로 10-100ms 범위에서 시간 할당량을 설정하며, 시스템의 특성과 요구사항에 따라 조정합니다.

우선순위 스케줄링 알고리즘

Priority Scheduling은 각 프로세스에 우선순위를 할당하고, 우선순위가 높은 프로세스부터 CPU를 할당하는 알고리즘입니다.

우선순위는 내부적 요소(메모리 요구량, 파일 사용량)나 외부적 요소(중요도, 사용료)에 의해 결정됩니다.

우선순위 스케줄링 구현 방식

선점형 우선순위 스케줄링:
새로운 프로세스가 도착했을 때 현재 실행 중인 프로세스보다 우선순위가 높으면 즉시 전환합니다.

비선점형 우선순위 스케줄링:
현재 실행 중인 프로세스가 완료될 때까지 기다린 후 우선순위에 따라 다음 프로세스를 선택합니다.

우선순위 스케줄링 예제

프로세스 | 실행시간 | 우선순위 (낮은 숫자 = 높은 우선순위)
P1      | 10      | 3
P2      | 1       | 1
P3      | 2       | 4
P4      | 1       | 5
P5      | 5       | 2

실행 순서: P2 → P5 → P1 → P3 → P4

기아 상태 해결책

우선순위 스케줄링의 주요 문제점인 기아 상태를 해결하기 위해 에이징(Aging) 기법을 사용합니다.

시간이 지남에 따라 오래 대기한 프로세스의 우선순위를 점진적으로 증가시켜 결국 실행될 수 있도록 보장합니다.

다단계 큐 스케줄링 알고리즘

Multilevel Queue Scheduling은 프로세스를 여러 개의 별도 큐로 분할하여 관리하는 스케줄링 알고리즘입니다.

각 큐는 고유한 스케줄링 알고리즘을 가지며, 큐 간에도 스케줄링이 존재합니다.

다단계 큐 구조 예제

우선순위 순서:
1. 시스템 프로세스 큐 (높은 우선순위)
2. 대화형 프로세스 큐 
3. 대화형 편집 프로세스 큐
4. 배치 프로세스 큐 (낮은 우선순위)
5. 학생 프로세스 큐

각 큐의 스케줄링:
- 시스템/대화형: 라운드 로빈
- 배치: FCFS

다단계 큐의 특징

장점:

• 프로세스 유형별 최적화된 스케줄링 적용
• 시스템 프로세스와 사용자 프로세스 구분 관리
• 각 큐마다 다른 시간 할당량 설정 가능

단점:

• 낮은 우선순위 큐의 기아 상태 발생 가능
• 프로세스 특성 변화에 대한 적응성 부족

다단계 피드백 큐 스케줄링 알고리즘

Multilevel Feedback Queue Scheduling은 다단계 큐의 개선된 형태로, 프로세스가 큐 간에 이동할 수 있는 동적 스케줄링 알고리즘입니다.

프로세스의 실행 특성에 따라 우선순위가 조정되며, 적응적인 스케줄링을 제공합니다.

다단계 피드백 큐 동작 원리

큐 구조:
Q0 (최고 우선순위) - 시간 할당량: 8ms
Q1 (중간 우선순위) - 시간 할당량: 16ms  
Q2 (최저 우선순위) - FCFS

프로세스 이동 규칙:
- 새 프로세스 → Q0 진입
- Q0에서 할당량 초과 → Q1으로 강등
- Q1에서 할당량 초과 → Q2로 강등
- I/O 완료 후 → 상위 큐로 승격

다단계 피드백 큐의 장점

적응성: 프로세스의 실행 패턴에 따라 동적으로 우선순위 조정

공정성: 짧은 프로세스와 긴 프로세스 모두에게 적절한 서비스 제공

효율성: CPU 집약적 작업과 I/O 집약적 작업을 구분하여 최적화

이 알고리즘은 현대 운영체제에서 가장 널리 사용되는 스케줄링 방식 중 하나입니다.

실시간 스케줄링 알고리즘

실시간 시스템에서는 작업의 완료 시간이 매우 중요합니다.

실시간 스케줄링 알고리즘은 데드라인을 만족시키는 것을 최우선 목표로 합니다.

주요 실시간 스케줄링 알고리즘

Rate Monotonic (RM) 스케줄링:
주기가 짧은 태스크에게 높은 우선순위를 부여하는 정적 우선순위 알고리즘입니다.

태스크 | 주기 | 실행시간 | 우선순위
T1    | 50ms | 20ms    | 높음
T2    | 100ms| 35ms    | 낮음

스케줄링 가능 조건: CPU 이용률 ≤ n(2^(1/n) - 1)

Earliest Deadline First (EDF) 스케줄링:
데드라인이 가장 빠른 태스크부터 실행하는 동적 우선순위 알고리즘입니다.

이론적으로 최적의 실시간 스케줄링 성능을 제공합니다.

멀티프로세서 스케줄링 고려사항

현대의 멀티코어 시스템에서는 여러 CPU에서 동시에 프로세스를 실행할 수 있어 스케줄링이 더욱 복잡해집니다.

멀티프로세서 스케줄링 방식

대칭적 멀티프로세싱 (SMP):
모든 프로세서가 동등한 역할을 수행하며, 공통 준비 큐를 공유하거나 각자의 준비 큐를 관리합니다.

프로세서 친화성 (Processor Affinity):
프로세스가 특정 프로세서에서 계속 실행되도록 하여 캐시 효율성을 높입니다.

부하 균형 (Load Balancing):
프로세서 간 작업 부하를 균등하게 분산시켜 전체 시스템 성능을 최적화합니다.

스케줄링 알고리즘 성능 평가 지표

다양한 스케줄링 알고리즘의 성능을 객관적으로 비교하기 위해 여러 지표를 사용합니다.

주요 성능 지표

평균 대기 시간: 프로세스가 준비 큐에서 대기하는 평균 시간

평균 반환 시간: 프로세스 제출부터 완료까지의 평균 시간

평균 응답 시간: 요청 제출부터 첫 번째 응답까지의 평균 시간

처리량: 단위 시간당 완료되는 프로세스의 개수

CPU 이용률: 전체 시간 중 CPU가 실제로 사용된 시간의 비율

벤치마킹과 시뮬레이션

실제 시스템에서 스케줄링 알고리즘의 성능을 평가하기 위해 다음과 같은 방법을 사용합니다:

• 결정론적 모델링: 특정 워크로드에 대한 수학적 분석
• 큐잉 모델: 확률적 분석을 통한 성능 예측
• 시뮬레이션: 다양한 시나리오에 대한 가상 실험
• 구현 및 측정: 실제 시스템에서의 성능 측정

현대 운영체제의 스케줄링 동향

최신 운영체제들은 복합적인 스케줄링 기법을 사용하여 다양한 워크로드에 최적화된 성능을 제공합니다.

Linux CFS (Completely Fair Scheduler)

Linux 커널 2.6.23부터 도입된 CFS는 가상 런타임을 기반으로 한 공정한 스케줄링을 제공합니다.

Red-Black 트리를 사용하여 O(log N) 시간 복잡도로 효율적인 스케줄링을 구현합니다.

Windows 스케줄러

Windows는 32개의 우선순위 레벨을 가진 다단계 피드백 큐 시스템을 사용합니다.

동적 우선순위 조정과 CPU 친화성을 통해 성능을 최적화합니다.

모바일 운영체제 최적화

Android와 iOS는 배터리 효율성과 사용자 경험을 고려한 특별한 스케줄링 기법을 사용합니다.

백그라운드 앱의 CPU 사용을 제한하고, 사용자 인터랙션에 높은 우선순위를 부여합니다.

마치며

OS 스케줄링 알고리즘은 컴퓨터 시스템의 성능과 사용자 경험에 직접적인 영향을 미치는 핵심 기술입니다.

각 알고리즘은 고유한 특성과 장단점을 가지고 있으며, 시스템의 목적과 요구사항에 따라 적절한 알고리즘을 선택해야 합니다.

현대의 운영체제는 여러 스케줄링 기법을 조합하여 다양한 워크로드에 최적화된 성능을 제공하고 있습니다.

개발자와 시스템 관리자는 이러한 스케줄링 원리를 이해함으로써 더 효율적인 시스템 설계와 성능 최적화를 달성할 수 있습니다.

앞으로도 멀티코어, 클라우드 컴퓨팅, IoT 등 새로운 컴퓨팅 환경의 발전에 따라 스케줄링 알고리즘은 계속해서 진화할 것입니다.