CPU 스케줄링(CPU Scheduling)

CPU 스케줄링(CPU Scheduling)이란 운영체제가 프로세스에 합리적으로 CPU 자원을 할당하는 정책을 만드는 것을 말합니다.

앞서 말했듯이 멀티태스킹을 위해서는 운영체제가 CPU의 가동시간을 적절히 나누어 프로세스에게 사용시간을 분배합니다. 이때 시스템과 사용자의 입장에서 CPU 성능에 대한 척도가 다를 수 있습니다.

1. 시스템 입장에서의 성능 척도

• CPU 사용률(CPU Utilization): 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
• 처리량(Throughput): CPU가 단위 시간당 처리하는 프로세스의 개수

2. 사용자 입장에서의 성능 척도

• 대기시간(Waiting Time): 프로세스가 준비 상태에서 CPU를 할당 받을 때까지 대기한 시간
• 응답시간(Response Time): 프로세스의 명령 요청 후 응답이 올 때까지의 시간
• 반환시간(Turnaround Time): 프로세스가 시작해서 끝날 때까지 걸리는 시간

시스템 입장에서는 CPU를 쉬지않고 최대한 많이 가동시키는 것이 중요하고, 사용자 입장에서는 요청한 작업이 빨리 처리되는 것이 중요하므로 운영체제는 상황에 맞게 CPU 스케줄링을 설계할 필요가 있습니다.

CPU 스케줄링은 스케줄링 방식에 따라 선점형과 비선점형으로 나눌 수 있습니다.

선점(preemptive)이란 빼앗을 수 있음을 의미합니다. 즉, 선점형 스케줄링의 경우 운영체제가 필요하다고 판단하면 실행중인 프로세스를 중단하고 다른 프로세스에게 CPU 자원을 할당하여 실행시킬 수 있습니다. 반대로 비선점형 스케줄링은 프로세스에게 할당된 CPU를 강제로 빼앗을 수 없고 프로세스의 사용이 끝난 이후 다른 프로세스에게 CPU의 자원을 할당할 수 있습니다.

선점형 스케줄링이 경우 하나의 프로세스가 자원 독점하지 못하도록 막을 수 있지만 문맥교환 과정에서 오버헤드가 발생할 수 있습니다. 반대로 비선점형 스케줄링의 경우 문맥교환에 대한 오버헤드가 없지만 전체 시스템의 처리율이 떨어질 수 있습니다.

운영체제는 PCB를 스케줄링 큐(Queue)에서 리스트 형태로 관리합니다. 보통 큐는 선입선출의 방식을 따르는 자료 구조이지만 스케줄링 큐는 스케줄링 전략에 따라 다른 자료구조를 가질 수도 있습니다. 스케줄링 큐는 프로세스 상태에 따라 준비 큐(Ready Queue), 대기 큐(Waitubg Queue) 등 여러 큐가 존재합니다.

비선점형 스케줄링

선입 선처리(First Come First Served, FCFS) 알고리즘

FCFS 알고리즘은 프로세스 도착순으로 CPU를 할당하는 CPU 스케줄링 알고리즘 입니다. 즉, 준비 큐에 도착한 순서대로 CPU에 자원을 할당합니다. 직관적이고 단순한 알고리즘 이지만 평균 대기시간이 길어지는 호위 효과(Convoy Effect) 문제가 있습니다.

위에 그림을 보면 P₁은 20초, P₂는 3초, P₃은 7초, P₄는 5초의 실행시간을 추정할 수 있습니다.

도착시간이 0초로 모두 동일하다고 가정하면 FCFS 알고리즘의 경우 P₁ → P₂ → P₃ → P₄ 순서로 실행되며, P₁은 0초, P₂는 20초, P₃은 23초, P₄는 30초의 대기시간을 가지게 되어 평균 대기시간은 18.25초가 됩니다. [(0 + 20 + 23 + 30) / 4 = 18.25]

이는 아래 알고리즘과 비교하면 긴 대기시간을 가집니다.

최단 작업 우선(Shortest Job First, SJF) 알고리즘

SJF 스케줄링은 FCFS 알고리즘을 보완하여 실행시간이 짧다고 추정되는 프로세스에게 먼저 자원을 할당하는 CPU 스케줄링 알고리즘 입니다.

도착시간이 0초로 모두 동일하다고 가정하면 SJF 알고리즘의 경우 P₂ → P₄ → P₃ → P₁ 순서로 실행되며, P₂는 0초, P₄는 3초, P₃은 8초, P₁은 15초의 대기시간을 가지게 되어 평균 대기시간은 6.5초가 됩니다. [(0 + 3 + 8 + 15) / 4 = 6.5]

SJF 알고리즘은 호위효과 문제가 해결되었지만 실행시간이 긴 프로세스의 경우 영원히 CPU를 할당받지 못하는 기아(Starvation) 현상이 발생할 수 있습니다.

최고 응답률 우선(Highest Response-ratio Next, HRN) 알고리즘

HRN 알고리즘은 점유의 불평등 현상이 발생하는 SJF 알고리즘을 보완하여 응답률이 높은 프로세스에게 먼저 자원을 할당하는 CPU 알고리즘이며, 다음과 같은 계산을 통해 프로세스의 우선순위를 결정합니다.

우선순위 = (대기시간 + 실행시간) / 실행시간

도착시간이 0초로 모두 동일하고 실행시간이 짧은 P₂가 처음 실행되었다고 가정하면 나머지 프로세스의 우선순위를 다음과 같이 계산할 수 있습니다.

• P₁: (3 + 20) / 20 = 1.15
• P₃: (23 + 7) / 7 = 4.3
• P₄: (30 + 5) / 5 = 7

그러므로 P₂ 다음으로 우선순위가 높은 P₄ → P₃ → P₁ 순서로 프로세스가 실행됩니다. 대기 시간이 길어질수록 우선순위가 높아지므로 P₄의 기아현상도 해소할 수 있습니다.

선점형 스케줄링

라운드 로빈(Round Robin, RR) 알고리즘

RR 알고리즘은 FCFS 알고리즘을 선점형으로 변형한 알고리즘 입니다. 선점형 스케줄링의 경우 프로세스가 정해진 시간만큼 돌아가면서 CPU를 사용하며, 해당 시간을 초과하면 타임아웃 인터럽트에 의해 CPU 점유를 빼앗기고 준비 큐에 들어가게 됩니다.

이 정해진 시간을 타임 슬라이스(Time Slice)라고 하며, 선점형 스케줄링 알고리즘에서는 타임 슬라이스의 크기가 중요합니다. 타임 슬라이스가 너무 크면 선점형과 다를바 없어져 호위 효과 문제가 발생할 수 있으며, 타임 슬라이스가 너무 작으면 잦은 문맥 교환으로 인한 오버헤드가 발생하여 CPU 성능이 떨어질 수 있습니다.

도착시간이 0초로 모두 동일하고 타임 슬라이스는 5초라고 가정하면, P₁과 P₃은 타임슬라이스를 초과하여 문맥 교환이 발생합니다. 그러므로 P₁ → (문맥교환) → P₂ → P₃ → (문맥교환) → P₄ → P₁ → (문맥교환) → P₃ → P₁ 순서로 실행됩니다.

최소 잔여 시간 우선(Sortest Remaining Time, SRT) 알고리즘

SRT 알고리즘은 SJF 알고리즘을 선점형으로 변형한 알고리즘입니다. 프로세스는 정해진 시간만큼 CPU를 사용하며, 남은 실행시간이 짧다고 추정되는 프로세스에게 먼저 자원을 할당하는 CPU 스케줄링 알고리즘 입니다.

도착시간이 0초로 모두 동일하고 타임 슬라이스는 5초라고 가정하면 P₂ → P₄ → P₃ → (문맥교환) → P₁ → (문맥교환) → P₃ → P₁ 순서로 실행됩니다.

다단계 큐(Multi-level Queue, MQ) 알고리즘

MQ 알고리즘은 프로세스의 특성별로 준비 큐를 여러 개 두어 우선순위를 부여하고, 높은 우선순위의 큐에 있는 프로세스들에게 먼저 자원을 할당하는 CPU 스케줄링 알고리즘 입니다.

이 알고리즘은 큐 별로 서로 다른 CPU 스케줄링 알고리즘을 적용할 수 있지만, 프로세스가 큐 간의 이동을 할 수 없기 때문에 우선순위가 낮은 큐에 있는 프로세스들은 기아 현상이 발생할 수 있습니다.

다단계 피드백 큐(Multi-level Feedback Queue, MFQ) 알고리즘

MFQ 알고리즘은 MQ 알고리즘이 발전된 형태로, 프로세스가 큐 간의 이동이 가능한 CPU 스케줄링 알고리즘 입니다. MQ 알고리즘은 정해진 시간동안 작업을 처리하지 못하면 동일한 우선순위의 준비 큐에 들어가지만, MFQ 알고리즘의 경우 우선순위가 낮은 큐에 들어감으로써 프로세스의 기아 현상을 해결할 수 있습니다. 이 기법을 에이징(aging)이라고 합니다.