CPU 스케줄링 CPU Scheduling

1. CPU 스케줄링

1.1. 정의

CPU 스케줄링은 다중 프로그래밍(Multi-programming) 운영체제에서, 실행 준비가 된 여러 프로세스(혹은 스레드) 중 어떤 프로세스에게 CPU를 할당할지를 결정하는 핵심적인 메커니즘이다. CPU 스케줄링의 주된 목표는 시스템의 성능을 최적화하는 것이며, 평가 지표는 다음과 같다.

• CPU 이용률 (CPU Utilization): 전체 시스템 시간 중 CPU가 실제로 작업을 수행한 시간의 비율. CPU를 최대한 쉬지 않고 바쁘게 유지하는 것을 목표로 한다.
• 처리량 (Throughput): 단위 시간당 완료된 프로세스의 수. 시스템이 얼마나 많은 일을 처리하는지를 나타내는 척도다.
• 총 처리 시간 (Turnaround Time): 프로세스가 시스템에 제출된 순간부터 완료될 때까지 걸린 총 시간. (대기 시간 + 실행 시간 + I/O 시간)
• 대기 시간 (Waiting Time): 프로세스가 준비 큐(Ready Queue)에서 자신의 차례를 기다리며 보낸 시간의 총합.
• 응답 시간 (Response Time): 사용자가 요청을 보낸 후, 첫 번째 결과(응답)가 출력되기까지 걸리는 시간. 대화형 시스템에서 특히 중요한 지표다.

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

• 비선점형 (Non-preemptive) 스케줄링: 한 프로세스가 CPU를 할당받으면, 그 프로세스가 스스로 CPU를 놓아줄 때(I/O 요청 또는 실행 완료)까지 다른 프로세스가 CPU를 빼앗을 수 없다.
  • 장점: 문맥 교환(Context Switching)이 적게 일어나므로 오버헤드가 작다.
  • 단점: 실행 시간이 긴 프로세스가 CPU를 독점하면 다른 프로세스들이 무한정 기다릴 수 있어, 평균 응답 시간이 길어질 수 있다. (e.g., FCFS, SJF)
• 선점형 (Preemptive) 스케줄링: 한 프로세스가 CPU를 사용하고 있더라도, 우선순위가 더 높은 프로세스가 도착하거나 현재 프로세스의 할당 시간이 만료되면 운영체제가 강제로 CPU를 빼앗아 다른 프로세스에 할당할 수 있다.
  • 장점: 중요한 작업이나 짧은 작업을 먼저 처리할 수 있어 전체 시스템의 응답성이 향상된다.
  • 단점: 잦은 문맥 교환으로 인해 오버헤드가 발생할 수 있다. 특정 조건에서는 기아 현상(Starvation)이 발생할 수 있다. (e.g., RR, SRTF, Priority)

---

2. 스케줄러의 종류와 동작 계층

CPU 스케줄링은 프로세스의 상태 변화에 따라 여러 단계의 스케줄러에 의해 계층적으로 이루어진다.

• 장기 스케줄러 (Long-term Scheduler / Job Scheduler)
  • 디스크(Job Pool)에 있는 여러 작업 중 어떤 것을 시스템으로 가져와 메모리에 적재하고 준비(Ready) 상태로 만들지 결정한다.
  • 시스템의 전체 프로세스 수, 즉 다중 프로그래밍의 정도(Degree of Multiprogramming)를 제어한다.
  • 현대의 시분할 시스템에서는 거의 사용되지 않거나, 사용자가 프로그램을 시작하는 행위 자체가 장기 스케줄링의 역할을 대신한다.
• 단기 스케줄러 (Short-term Scheduler / CPU Scheduler)
  • 메모리의 준비 큐(Ready Queue)에 있는 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정한다.
  • 밀리초(ms) 단위로 매우 빈번하게 호출되므로, 속도가 매우 빨라야 한다. 우리가 일반적으로 'CPU 스케줄링'이라고 할 때 지칭하는 대상이다.
• 중기 스케줄러 (Medium-term Scheduler / Swapper)
  • 메모리가 부족해지면, 일부 프로세스를 일시적으로 메모리에서 디스크로 내쫓아(스왑 아웃, Swap-out) 다중 프로그래밍의 정도를 동적으로 조절한다.
  • 이후 메모리에 여유가 생기면 디스크로 쫓겨났던 프로세스를 다시 메모리로 가져온다(스왑 인, Swap-in).
  • 이를 통해 시스템의 과부하를 막고 자원 활용을 최적화한다.

---

3. 스케줄링 알고리즘

3.1. 비선점형 알고리즘

3.1.1. FCFS (First-Come, First-Served)

• 준비 큐에 도착한 순서대로 CPU를 할당하는 가장 간단한 방식. FIFO라고도 한다.
• 장점: 구현이 쉽고, 모든 프로세스가 공평하게 기회를 얻는다.
• 단점: Convoy Effect가 발생할 수 있다. 실행 시간이 매우 긴 프로세스가 먼저 도착하면, 그 뒤의 짧은 프로세스들이 모두 해당 프로세스가 끝날 때까지 기다려야 하므로 평균 대기 시간이 급격히 늘어난다.

3.1.2. SJF (Shortest Job First)

• 실행 시간이 가장 짧을 것으로 예상되는 프로세스에게 CPU를 먼저 할당한다.
• 장점: 모든 스케줄링 알고리즘 중 평균 대기 시간을 최소화하는 최적의 알고리즘임이 수학적으로 증명되었다.
• 단점:
  • 기아 현상(Starvation): 실행 시간이 긴 프로세스는 계속해서 들어오는 짧은 프로세스들 때문에 CPU를 할당받지 못하고 무한정 기다릴 수 있다.
  • 실행 시간 예측의 어려움: 실제 실행 시간은 프로세스가 끝나기 전까지 알 수 없으므로, 과거의 실행 기록 등을 통해 예측해야만 한다.

3.2. 선점형 알고리즘

3.2.1. SRTF (Shortest Remaining Time First)

• 선점형 SJF 알고리즘. 현재 실행 중인 프로세스의 남은 시간보다 더 짧은 실행 시간을 가진 새로운 프로세스가 준비 큐에 도착하면, CPU를 빼앗아 새로운 프로세스에 할당한다.
• 장점: SJF의 장점을 가지면서, 새로운 짧은 작업에 더 빠르게 반응하여 평균 대기 시간을 더욱 줄일 수 있다.
• 단점: 잦은 선점으로 인해 문맥 교환 오버헤드가 커질 수 있으며, SJF와 마찬가지로 기아 현상이 발생할 수 있다.

3.2.2. 라운드 로빈 (RR, Round Robin)

• FCFS에 타임 퀀텀(Time Quantum) 또는 타임 슬라이스(Time Slice)라는 시간 할당량 개념을 추가한 방식.
• 모든 프로세스는 타임 퀀텀만큼 CPU를 사용한 후, 작업이 끝나지 않았으면 준비 큐의 맨 뒤로 돌아가 다음 차례를 기다린다.
• 장점:
  • 모든 프로세스가 공평하게 CPU 시간을 할당받아 응답 시간이 짧아진다. 대화형 시스템에 매우 적합하다.
  • 기아 현상이 발생하지 않는다.
• 단점:
  • 타임 퀀텀 크기 설정이 매우 중요하다.
    • 너무 크면: FCFS처럼 동작하여 응답성이 떨어진다.
    • 너무 작으면: 문맥 교환이 너무 빈번하게 발생하여 오버헤드로 인해 시스템 성능이 저하된다.

3.2.3. 우선순위 스케줄링 (Priority Scheduling)

• 각 프로세스에 우선순위를 부여하고, 우선순위가 가장 높은 프로세스에게 CPU를 할당한다. (선점형, 비선점형 모두 구현 가능)
• 장점: 시스템의 중요한 작업을 먼저 처리하도록 설정할 수 있다.
• 단점: 기아 현상이 발생하기 쉽다. 낮은 우선순위의 프로세스는 높은 우선순위 프로세스들 때문에 영원히 실행되지 못할 수 있다.
• 해결책: 노화(Aging) 기법. 오래 기다린 프로세스의 우선순위를 점차 높여주어 언젠가는 실행될 수 있도록 보장한다.

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

• 준비 큐를 여러 개의 독립적인 큐로 분할하여 사용하는 방식. 각 큐는 자신만의 스케줄링 알고리즘을 가질 수 있다.
• 예: 전위 큐(Foreground Queue)는 응답성이 중요한 대화형 작업을 위해 RR 방식을, 후위 큐(Background Queue)는 일괄 처리 작업을 위해 FCFS 방식을 사용.
• 큐들 사이에도 우선순위가 있어, 전위 큐가 모두 비어야만 후위 큐의 작업이 실행될 수 있다.
• 장점: 프로세스의 유형에 따라 다른 스케줄링 정책을 적용하여 시스템 요구사항을 만족시키기 용이하다.
• 단점: 큐 간의 이동이 불가능하여 유연성이 떨어진다. 하위 큐의 프로세스들은 상위 큐에 작업이 계속 들어오면 기아 현상을 겪을 수 있다.

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

• 다단계 큐에서 한 단계 더 나아가, 프로세스가 큐 사이를 이동할 수 있도록 허용한 가장 진보된 방식. 현대 대부분의 운영체제(Unix, Windows 등)가 이 방식을 채택 및 변형하여 사용한다.
• 동작 방식 예시:
  1. 새로운 프로세스는 가장 우선순위가 높은 큐(가장 작은 타임 퀀텀)에 들어간다.
  2. 할당된 시간 내에 작업을 마치지 못하면, 우선순위가 한 단계 낮은 큐(더 긴 타임 퀀텀)로 강등된다.
  3. CPU를 많이 사용하는 CPU-bound 프로세스는 점차 아래 큐로 내려가고, I/O 작업이 잦은 I/O-bound 프로세스는 CPU를 잠깐 쓰고 반납하므로 상위 큐에 머무르며 높은 응답성을 유지한다.
  4. 특정 큐에서 너무 오래 대기하는 프로세스는 상위 큐로 승격시켜(노화) 기아 현상을 방지한다.
• 장점: 매우 유연하여 특정 시스템에 맞게 최적화하기 용이하며, 기아 현상 등 여러 문제를 종합적으로 해결할 수 있다.
• 단점: 설계와 파라미터(큐의 수, 각 큐의 스케줄링 알고리즘, 타임 퀀텀 등) 설정이 매우 복잡하다.

---

4. 알고리즘 비교 요약

알고리즘	방식	장점	단점	기아 현상
FCFS	비선점	간단, 공평	호위 효과, 평균 대기 시간 김	없음
SJF	비선점	평균 대기 시간 최소화 (최적)	실행 시간 예측 어려움	발생 가능
SRTF	선점	평균 대기 시간 최소화	잦은 문맥 교환, 실행 시간 예측	발생 가능
RR	선점	응답 시간 짧음, 공평	문맥 교환 오버헤드 (퀀텀 의존)	없음
Priority	선점/비선점	중요도에 따른 처리	우선순위 설정 복잡	발생 가능 (노화로 해결)
MLFQ	선점	유연성, 적응성 높음 (최고 성능)	설계 및 튜닝 매우 복잡	해결 가능

---

5. 요약

 CPU 스케줄링은 여러 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정하는 운영체제의 정책입니다. 주된 목표는 CPU 이용률과 처리량을 높이고, 사용자의 응답 시간이나 프로세스의 대기 시간을 줄여 시스템 성능을 최적화하는 것입니다.

 대표적인 알고리즘으로는 먼저 온 순서대로 처리하는 FCFS, 실행 시간이 짧은 작업을 먼저 처리해 평균 대기 시간을 줄이는 SJF가 있습니다. 하지만 FCFS는 긴 작업이 앞을 막는 '콘보이 효과'가 있고, SJF는 긴 작업이 계속 밀리는 '기아 현상'이 발생할 수 있습니다.

이를 보완하기 위해 선점형 방식들이 사용됩니다. 라운드 로빈(RR)은 모든 프로세스에게 '타임 퀀텀'이라는 짧은 시간을 공평하게 할당하여 응답 시간을 줄이는 방식으로, 대화형 시스템에 적합합니다. 우선순위 스케줄링은 중요한 작업을 먼저 처리하지만, 낮은 순위 작업이 무한정 기다리는 기아 현상을 막기 위해 '노화' 기법을 함께 사용하기도 합니다.

 현대 운영체제는 이들을 결합한 다단계 피드백 큐(MLFQ)를 주로 사용합니다. 여러 개의 우선순위 큐를 두고, 프로세스의 특성에 따라 큐 사이를 이동시키는 동적인 방식입니다. 예를 들어, CPU를 오래 쓰는 작업은 낮은 우선순위 큐로 내리고, I/O 작업처럼 대기가 잦은 작업은 높은 우선순위 큐에 두어 응답성을 높이는 등, 가장 유연하고 효율적으로 시스템을 관리할 수 있는 알고리즘입니다.