[ComputerScience] CPU 스케줄링
CPU 스케줄링
CPU 스케줄링(CPU Scheduling)은 운영체제가 여러 실행 단위(프로세스 또는 스레드) 중에서 어떤 실행 단위를 언제 CPU에 할당할지 결정하는 과정입니다.
CPU는 한 번에 하나의 실행 단위만 처리할 수 있기 때문에, 다수의 프로세스나 스레드가 동시에 실행될 수 있는 환경에서는 스케줄링 정책이 필수적입니다.
CPU 스케줄링의 대상은 실행 문맥(Context)을 가진 모든 단위라고 할 수 있습니다.
일반적으로 프로세스를 기준으로 표현하지만 스레드도 독립적인 스케줄링 단위로 고려됩니다.
우선순위
운영체제에서 우선순위(Priority)는 CPU를 할당할 때 프로세스 간의 상대적인 중요도를 나타내는 값입니다.
PCB에 기록되며, CPU 스케줄링 결정 시 참조됩니다.
정적 우선순위
정적 우선순위(Static Priority)는 프로세스 생성 시 우선순위가 정해지고, 실행 중에는 변하지 않는 우선순위입니다.
우선순위가 변하지 않기 때문에 스케줄링 결과를 예측하기 쉽습니다.
그로인해 실시간 시스템이나 일정한 응답시간이 중요한 시스템에서 유리합니다.
프로세스가 언제 CPU를 차지할지 계산이 단순하고, 스케줄러가 관리하기 쉽기 때문에 구현이 단순합니다.
프로세스의 상태(CPU 집중, I/O 집중 등)에 따라 우선순위를 조정하지 않기 때문에 스케줄링 방식에 따라 CPU가 불필요하게 I/O 집중 프로세스에서 대기하거나 CPU 집중 프로세스가 오랫동안 기다리는 상황이 발생할 수 있습니다.
대표적으로 운영체제에서 특정 시스템 프로세스나 중요한 서비스 프로세스에 높은 우선순위를 부여하고, 일반 사용자 프로세스에는 낮은 우선순위를 고정합니다.
동적 우선순위
동적 우선순위(Dynamic Priority)는 프로세스 실행 상태, 대기 시간, I/O 혹은 CPU 사용량 등에 따라 우선순위가 변하는 우선순위입니다.
예를 들어, 입출력 집중 프로세스는 실행 상태보다 대기 상태에, CPU 집중 프로세스는 대기 상태보다 실행 상태에 머무르는 시간이 많습니다.
주로 머무르는 상태가 다르기 때문에 모든 프로세스 동일한 빈도로 CPU를 사용하는 건 비합리적이기 때문에 우선순위가 변동됩니다.
만약, 두 집중 프로세스가 동시에 CPU의 자원을 요구하는 경우 입출력 집중 프로세스를 우선 실행시켜 입출력장치를 작동시킨 후, CPU 집중 프로세스에 CPU를 할당하게 됩니다.
사용자가 일부 프로세스의 우선순위를 직접 높일 수도 있습니다.
스케줄링 큐
스케줄링 큐(Scheduling Queue)는 특정 자원을 이용하고 싶은 프로세스 PCB(프로세스 제어 블록)가 기다리는 큐입니다.
대표적인 큐는 다음과 같습니다.
- 준비 큐(Ready Queue): CPU를 이용하고 싶은 프로세스 PCB가 기다리는 큐
- 대기 큐(Waiting Queue): 대기 상태에 접어든 프로세스 PCB가 기다리는 큐
스케줄링 큐의 작동 순서는 다음과 같습니다.
- 같은 입출력장치를 요구한 프로세스들은 같은 대기 큐에서 기다립니다.
- 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 해당 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거합니다.
- 대기 큐에서 제거된 PCB는 준비 큐로 이동됩니다.
스케줄링 큐 이동만으로 CPU의 할당이 결정되지는 않습니다.
선점형 스케줄링과 비선점형 스케줄링
운영체제의 프로세스 스케줄링은 크게 선점형과 비선점형 방식으로 나눌 수 있습니다.
프로세스가 종료되지 않았음에도 실행 도중 스케줄링이 수행될 수 있습니다.
대표적인 수행 시점으로 대기 상태로 전환 되는 시점과 준비 상태로 전환되는 시점이 있습니다.
선점형 스케줄링
선점형 스케줄링(Preemptive Scheduling)은 운영체제가 강제로 프로세스의 CPU 점유를 중단시킬 수 있는 방식입니다.
더 높은 우선순위의 프로세스가 도착하거나, 시간 할당량(Time Quantum)이 만료되면 CPU를 빼앗아 다른 프로세스에 할당합니다.
대기 상태로 전환되거나 준비 상태로 전환되는 시점에서 수행되는 스케줄링 유형입니다.
응답 시간이 짧아지고, 시분할 시스템(Time-sharing System)에서 필수적으로 사용됩니다.
하지만 프로세스 전환이 자주 발생하므로 문맥 전환 오버헤드가 증가할 수 있습니다.
사용자와의 빠른 상호작용이 필요한 환경에 적합합니다.
비선점형 스케줄링
비선점형 스케줄링(Non-preemptive Scheduling)은 한 프로세스가 CPU를 할당 받으면 자발적으로 CPU를 반납할 때까지 다른 프로세스가 CPU를 빼앗을 수 없는 방식입니다.
즉, 프로세스가 종료되거나 대기 상태로 전환되기 전까지는 CPU를 계속 점유합니다.
대기 상태로 전환될 때에만 수행되는 스케줄링 유형입니다.
프로세스가 CPU를 계속 사용하므로 문맥 전환 오버헤드가 적습니다.
하지만 한 프로세스가 오래 CPU를 점유하면 대기 프로세스들의 응답 시간이 길어져 효율이 떨어질 수 있습니다.
응답 시간이 중요한 시스템(실시간 반응)이 아닌 경우 적합합니다.
스케줄링 알고리즘
FCFS
선입 선처리(FCFS, First-Come First-Served) 스케줄링은 큐에 삽입된 순서대로 프로세스를 관리하며, CPU를 할당하는 알고리즘입니다.
프로세스들이 기다리는 시간이 매우 길어질 수 있습니다.
호위 효과(Convoy effect)가 발생할 수 있습니다.
호위 효과는 먼저 삽입된 프로세스의 오랜 실행 시간으로 나중에 삽입된 프로세스의 실행이 지연되는 문제입니다.
비선점형 스케줄링에 사용됩니다.
SJF
최단 작업 우선(SJF, Shortest Job First) 스케줄링은 준비 큐에 삽입된 프로세스 중 실행 시간이 가장 짧은 프로세스를 먼저 처리하는 알고리즘입니다.
기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수 있습니다.
이 경우 최소 잔여 시간 우선 스케줄링입니다.
Round Robin
라운드 로빈 (RR, Round Robin) 스케줄링은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해져 모든 프로세스에 동일한 시간 할당량을 주고 순환하며 실행하는 알고리즘입니다.
타임 슬라이스(Time Slice)는 프로세스가 CPU를 사용하도록 정해진 시간을 의미합니다.
만약, 프로세스가 정해진 시간을 모두 사용하고도 완료되지 않으면 문맥 교환이 발생합니다.
선점형 스케줄링에 사용됩니다.
SRTF
최소 잔여 시간 우선(SRTF, Shortest Remaining Time First) 스케줄링은 남은 실행 시간이 가장 짧은 프로세스에 CPU를 할당하는 알고리즘입니다.
최단 작업 우선(SJF)이 선점형으로 구현된 형태입니다.
선점형 스케줄링에 사용됩니다.
우선순위 스케줄링
우선순위 스케줄링(Preemptive Priority Scheduling)은 더 높은 우선순위를 가진 프로세스가 도착하면 현재 프로세스를 중단하고 실행하는 알고리즘입니다.
아사(Starvation) 현상이 발생할 수 있습니다.
아사 현상은 우선순위가 낮은 프로세스는 계속해서 실행이 연기되는 상태입니다.
아사 현상을 방지하기 위해 에이징(Aging) 기법을 사용하기도 합니다.
에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식입니다.
선점형 스케줄링에 사용됩니다.
다단계 큐
다단계 큐(Multilevel Queue) 스케줄링은 우선순위별로 여러 개의 준비 큐를 사용하여 우선순위가 가장 높은 큐에 있는 프로세스를 처리하고, 다음 우선순위가 높은 큐에 있는 프로세스를 처리합니다.
우선순위 스케줄링의 발전된 형태를 가집니다.
우선순위 스케줄링과 같이 아사 현상이 발생할 수 있습니다.
하지만 해당 알고리즘에서는 우선순위 큐를 이동할 수 없습니다.
선점형과 비선점형 스케줄링 모두 사용 가능하지만, 주로 선점형으로 사용됩니다.
다단계 피드백 큐
다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링은 다단계 큐 스케줄링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있는 알고리즘입니다.
프로세스는 우선순위가 가장 높은 우선순위 큐에 삽입되고, 타임 슬라이스동안 실행됩니다.
만약, 타임 슬라이스동안 실행되지 못한다면, 우선순위가 한 단계씩 낮아지게 됩니다.
그리하여 CPU를 오래 사용하는 CPU 집중 프로세스들의 우선순위를 낮추고, CPU를 적게 사용하는 입출력 집중 프로세스들은 우선순위가 높아집니다.
에이징 기법이 적용 가능합니다.
선점형과 비선점형 스케줄링 모두 사용 가능하지만, 주로 선점형으로 사용됩니다.
댓글남기기