CPU 스케줄링이란?

CPU 스케줄링이란, 컴퓨터 시스템에서 여러 프로세스가 CPU를 공유하고 실행되는 과정을 관리하는 방법입니다.
CPU 스케줄링의 목적은 CPU의 활용도를 높이고, 프로세스의 대기 시간과 응답 시간을 줄이고, 시스템의 처리량과 성능을 향상시키는 것입니다.

CPU 스케줄링에는 여러 종류의 알고리즘이 있습니다.
대표적인 예로는 선입선출(FIFO), 최단 작업 우선 스케줄링(SJF), 최소 잔류 시간 우선 스케줄링(SRTF), 우선순위(Priority), 라운드로빈(RR), 멀티 레벨 큐(Multilevel Queue), 멀티 레벨 피드백 큐(Multilevel Feedback Queue) 등이 있습니다.

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

CPU 스케줄링의 종류를 알아보기 전에 선점형 스케줄링과 비선점형 스케줄링이 뭔지 간단하게 알아보겠습니다.

선점형 스케줄링

실행 중인 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 강제로 빼앗을 수 있는 방식입니다.

예를 들어, 우선순위가 높은 프로세스나 시간이 적게 남은 프로세스가 CPU를 요청하면, 실행 중인 프로세스는 중단되고 다른 프로세스가 CPU를 할당받습니다.
이렇게 하면, 긴급한 작업이나 짧은 작업을 빠르게 처리할 수 있습니다. 하지만, 프로세스가 자주 교체되면 오버헤드가 발생하고, 실행 순서가 예측하기 어렵습니다.

선점형 스케줄링의 예로는 라운드로빈(RR), 우선순위(Priority) 기반 등이 있습니다.

비선점형 스케줄링

실행 중인 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 빼앗을 수 없는 방식입니다.

예를 들어, 실행 중인 프로세스가 입출력 작업을 요청하거나 종료될 때까지 CPU를 계속 사용합니다.
이렇게 하면, 프로세스의 교체가 적게 일어나서 오버헤드가 줄고, 실행 순서가 예측하기 쉽습니다. 하지만, 긴 작업이 CPU를 오랫동안 점유하면 다른 작업들이 오래 기다려야 합니다.

비전형 스케줄링의 예로는 선입선출(FIFO), 최단 작업 우선 스케줄링(SJF) 등이 있습니다.

선입선출 스케줄링(FCFS)

프로세스가 도착한 순서대로 CPU를 할당하는 가장 간단하고 공평한 스케줄링 알고리즘입니다. 비선점형 스케줄링이므로 프로세스가 자발적으로 CPU를 반납할 때 까지 CPU를 빼앗지 않습니다.

예를 들어, 프로세스 A, B, C가 각각 3초, 5초, 2초의 서비스 시간을 가지고 있고, A가 먼저 도착하고 B가 그 다음에 도착하고 C가 마지막에 도착한다면, FCFS 스케줄링은 다음과 같은 순서로 프로세스를 실행합니다.

프로세스	서비스 시간	대기 시간	응답 시간	반환 시간
A	3초	0초	0초	3초
B	5초	3초	3초	8초
C	2초	8초	8초	10초

이렇게 되면 평균 대기 시간은 (0 + 3 + 8) / 3 = 3.67초, 평균 응답 시간은 (0 + 3 + 8) / 3 = 3.67초, 평균 반환 시간은 (3 + 8 + 10) / 3 = 7초가 됩니다.

장점

• 구현이 쉽습니다.
• 선착순으로 처리하기 때문에 프로세스를 공평하게 처리할 수 있습니다.

단점

• 짧은 작업이 긴 작업보다 늦게 도착하면 긴 작업을 기다려야 하므로 평균 대기 시간이 증가할 수 있습니다. 이를 호위 효과(convoy effect)라고 합니다.

• FCFS 스케줄링은 비선점형(nonpreemptive) 방식이므로 한 프로세스가 CPU를 점유하고 있으면 다른 프로세스는 CPU를 빼앗을 수 없습니다. 이는 CPU 사용률을 낮추고 I/O 바운드 프로세스의 대기 시간을 증가시킬 수 있습니다.

FCFS 스케줄링은 간단하고 공평하지만 효율적이지는 않습니다. 따라서 실제 시스템에서는 보다 성능이 좋은 다른 스케줄링 알고리즘을 사용하는 경우가 많습니다.

최단 작업 우선 스케줄링(SJF)

SJF는 준비 큐에 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스를 먼저 실행시키는 방식입니다.

SJF는 평균 대기 시간과 평균 응답 시간을 최소화하는 최적의 알고리즘입니다.
SJF는 비선점형과 선점형 두 가지 방식으로 구현할 수 있습니다.

비선점형 SJF

비선점형 SJF는 이미 CPU를 할당받은 프로세스는 실행이 완료될 때까지 CPU를 빼앗기지 않습니다.

선점형 SJF

선점형 SJF는 새로운 프로세스가 준비 큐에 도착하면 현재 실행 중인 프로세스의 남은 실행 시간과 비교하여 새로운 프로세스의 실행 시간이 더 짧으면 CPU를 선점하여 새로운 프로세스에게 할당합니다.

장점

• 실행 시간을 미리 알아야 하기 때문에 실제 시스템에서 구현하기 어렵습니다.

단점

• 선점형 SJF에서 기아 현상이 생길 수 있습니다.
  실행 시간이 짧은 프로세스들이 새롭게 준비큐에 연속적으로 들어온다면 실행시간이 비교적 긴 프로세스는 영원히 CPU를 할당받지 못할 수 있습니다.

최소 잔류 시간 우선 스케줄링(SRTF)

최소 잔류 시간 우선 스케줄링(SRTF) 방식은 프로세스의 남은 실행 시간이 가장 짧은 것부터 우선적으로 처리하는 CPU 스케줄링 알고리즘입니다.

이 방식은 선점형 스케줄링이므로, 새로운 프로세스가 도착하거나 기존의 프로세스가 종료될 때마다 CPU를 재할당합니다.
SRTF 방식은 평균 대기 시간과 평균 응답 시간을 최소화할 수 있으므로, 시스템의 처리량을 높이고 사용자의 만족도를 향상시킬 수 있습니다.

하지만, 실행 시간이 긴 프로세스는 계속해서 선점당할 수 있어서 기아 현상이 일어날 수 있습니다.

우선순위 스케줄링(Priority)

우선순위 스케줄링이란 프로세스나 작업에 우선순위를 부여하여 실행 순서를 결정하는 스케줄링 방식입니다.

우선순위 스케줄링은 CPU의 효율성과 처리량을 높이기 위해 사용됩니다.

우선순위 스케줄링에는 선점/비선점 방식과 정적/동적 방식의 스케줄링이 있습니다.

정적 우선순위 스케줄링

정적 우선순위 스케줄링은 프로세스나 작업이 생성될 때 우선순위가 정해지고 변경되지 않는 방식입니다.

동적 우선순위 스케줄링

동적 우선순위 스케줄링은 프로세스나 작업의 상태에 따라 우선순위가 변화하는 방식입니다.

장점

• 중요한 작업을 빠르게 처리할 수 있습니다.

단점

• 낮은 우선순위의 작업이 계속 기다려야 하는 기아 현상이 발생할 수 있습니다.
  이는 에이징(Aging) 기법을 사용해 해결할 수 있습니다.

라운드로빈(Round-Robin)

라운드 로빈 스케줄링은 시분할 시스템에서 사용되는 선점형 스케줄링 알고리즘 중 하나입니다.
이 알고리즘은 프로세스들에게 우선순위를 부여하지 않고, 정해진 시간 단위(Time Quantum)만큼 순서대로 CPU를 할당합니다. 시간 단위는 보통 10ms에서 100ms 사이입니다.
시간 단위 동안 수행된 프로세스는 준비 큐의 맨 뒤로 이동하고, 다음 프로세스에게 CPU를 넘깁니다.

장점

• 응답 시간이 짧습니다.
• 모든 프로세스가 공정하게 CPU를 사용할 수 있습니다.
• 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적입니다.

단점

• 문맥 전환(Context Switching)의 오버헤드가 큽니다.
• 시간 단위를 적절하게 설정하지 않으면 효율성이 떨어질 수 있습니다.
• 시간 단위가 너무 길다면 FCFS와 같은 효과를 보일 수 있고 너무 짧다면 문맥 전환(Context Switching)의 오버헤드가 커집니다.

멀티레벨 큐(Multilevel Queue)

멀티레벨 큐 스케줄링이란 운영체제에서 프로세스를 여러 개의 큐로 분류하여 실행하는 방식입니다.
큐 자체에 대한 알고리즘과 각 큐의 자신만의 알고리즘을 스케줄링 해야합니다.

예를 들어, 대화형 작업을 담기 위한 전위 큐와 계산 위주의 작업을 담기 위한 후위 큐로 분할해 운영할 수 있습니다.

큐 자체에 대한 스케줄링으로 가장 쉽게 생각할 수 있는 방식은 고정 우선순위 방식입니다. 이 방식에서는 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스합니다. 전위 큐가 비어 있는 경우에만 후위 큐에 있는 프로세스에게 CPU가 할당될 수 있습니다.
타임 슬라이스(time slice) 방식을 사용하면 큐에 대한 기아 현상을 해소할 수 있습니다. 이 때는 각 큐에 CPU 할당 시간을 다르게 적용할 수 있습니다.

이렇게 하면 각 프로세스의 특성에 맞게 적절한 스케줄링을 할 수 있습니다.

장점

• 다양한 종류의 프로세스를 효율적으로 관리할 수 있다는 점입니다.
  예를 들어, CPU 바운드 프로세스와 입출력 바운드 프로세스를 구분하여 실행하면, CPU의 활용도를 높이고, 입출력 장치의 대기 시간을 줄일 수 있습니다.

• 우선순위가 높은 프로세스에게 더 많은 CPU 시간을 할당하여 응답성을 향상시킬 수 있습니다.

단점

• 복잡도가 높고, 별도의 메커니즘을 통해 큐 사이의 균형을 유지해야 합니다.
  예를 들어, 한 큐에 프로세스가 너무 많이 쌓이면, 다른 큐의 프로세스가 기아 현상을 겪을 수 있습니다. 따라서, 적절한 크기와 우선순위를 갖는 여러 개의 큐를 설계하고, 필요에 따라 프로세스를 재배치하는 것이 중요합니다.

멀티 레벨 피드백 큐(Multilevel Feedback Queue)

프로세스를 여러 개의 큐에 나누고, 각 큐는 다른 우선순위와 시간 할당량을 가집니다.
우선순위가 높은 큐에 있는 프로세스는 먼저 실행되고, 시간 할당량이 초과되면 다음 우선순위의 큐로 이동합니다. 이렇게 하면 프로세스의 응답 시간과 처리량을 균형있게 유지할 수 있습니다.

멀티레벨 큐와 다른 점은 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점입니다.

장점

• 프로세스의 특성에 따라 적절한 우선순위와 시간 할당량을 부여할 수 있습니다.

• CPU를 효율적으로 활용할 수 있습니다.

• 기아 현상을 방지할 수 있습니다.

  • aging 기법을 통해 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시킬 수 있습니다.

단점

• 큐의 수와 우선순위를 결정하는 것이 어렵습니다.

• 오버헤드가 발생할 수 있습니다.

• 선점형 스케줄링이므로 프로세스의 실행 순서를 예측하기 어렵습니다.

기아 현상

CPU 스케줄링에서 기아 현상이란 프로세스가 CPU를 할당받지 못하고 무한정 대기하는 상황을 말합니다. 이러한 상황은 CPU 스케줄링 알고리즘의 성능에 영향을 미치고, 프로세스의 응답 시간과 처리량을 저하시킬 수 있습니다.

기아 현상 해결 방법

기아 상태를 방지하기 위해서는 CPU 스케줄링 알고리즘에 우선순위를 부여하거나, 에이징(Aging) 기법을 사용하는 등의 방법이 있습니다.

1) 에이징(Aging)

기아 상태를 해결하기 위한 방법 중 하나는 에이징(Aging)이라고 합니다.
에이징은 프로세스가 대기 큐에서 기다릴수록 우선순위를 증가시켜주는 방식입니다. 이렇게 하면 오랫동안 기다린 프로세스가 결국에는 CPU를 할당받을 수 있습니다.
에이징은 우선순위 기반의 스케줄링 알고리즘에서 주로 사용됩니다.

2) 피드백(Feedback)

또 다른 방법은 피드백(Feedback)이라고 합니다.
피드백은 프로세스가 CPU를 사용할수록 우선순위를 감소시켜주는 방식입니다. 이렇게 하면 자주 CPU를 사용하는 프로세스가 낮은 우선순위로 밀려나게 되고, 오랫동안 기다린 프로세스가 높은 우선순위로 올라가게 됩니다.
피드백은 다단계 큐(Multilevel Queue)나 다단계 피드백 큐(Multilevel Feedback Queue)와 같은 스케줄링 알고리즘에서 주로 사용됩니다.

3) 페어 스케줄링(Fair Scheduling)

이 외에도 페어 스케줄링(Fair Scheduling)이라는 방법도 있습니다.
페어 스케줄링은 모든 프로세스에게 동일한 비율의 CPU 시간을 할당해주는 방식입니다.
예를 들어, 10개의 프로세스가 있다면 각각 10%의 CPU 시간을 받게 됩니다. 이렇게 하면 어떤 프로세스도 기아 상태에 빠지지 않습니다.
페어 스케줄링은 리눅스(Linux)와 같은 운영체제에서 사용되는 스케줄링 알고리즘입니다.

참고

운영체제와 정보기술의 원리 - 반효경