운영체제 파헤치기4 - CPU 스케줄링

CPU 스케줄러

CPU는 메모리에 적재된 모든 프로그램을 동시에 실행할 수 없습니다. 한정된 자원인 CPU를 효율적으로 활용하기 위해, 운영체제는 실행 중인 프로그램들이 공정하고 합리적으로 CPU를 할당받도록 CPU의 할당 순서와 사용 시간을 결정합니다. CPU 스케줄링 알고리즘은 CPU 스케줄링의 절차를 말하며, 이 CPU 스케줄링 알고리즘을 결정하고 수행하는 운영체제의 일부분을 CPU 스케줄러라고 합니다.

프로세스와 스레드는 모두 CPU 스케줄링의 대상이 된다.

 

운영체제는 프로세스별 우선순위를 판단하여 PCB(Process Control Block)에 기록하고, 우선순위가 높은 프로세스에 CPU 자원을 더 빠르고 많이 할당합니다.

 

운영 체제는 어떤 기준으로 프로세스의 우선순위를 결정하는가?

대표적인 고려 요소 중 하나는 CPU 활용률(CPU Utilization) 입니다. CPU 활용률이란 전체 CPU 가동 시간 중 실제 작업을 처리하는 시간의 비율을 의미합니다. 운영체제는 CPU 활용률을 높이기 위해, 일반적으로 입출력(I/O) 작업이 많은 프로세스의 우선순위를 높게 설정합니다. 대부분의 프로세스는 CPU와 입출력 장치를 모두 사용해 실행과 대기 상태를 오가며 실행됩니다. CPU를 사용하는 시간을 CPU 버스트(CPU Burst)라고 하며, 입출력 작업을 기다리는 시간을 입출력 버스트(I/O Burst)라고 합니다.

비디오 재생이나 디스크 백업과 같은 작업은 입출력 작업이 많아 입출력 집중 프로세스(I/O Bound Process)에 해당하며, 복잡한 수학 연산이나 그래픽 렌더링과 같은 작업은 CPU 작업이 많아 CPU 집중 프로세스(CPU Bound Process)라고 합니다. 

입출력 집중 프로세스와 CPU 집중 프로세스가 동일한 빈도로 CPU를 사용하는 것은 비효율적입니다. 입출력 집중 프로세스는 대기 시간이 많기 때문에, 입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 CPU 자원을 요구할 경우, 입출력 집중 프로세스를 우선적으로 실행시켜 끊임없이 입출력장치를 작동시킨 다음, CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적입니다. 이러한 이유로 입출력 집중 프로세스는 일반적으로 CPU 집중 프로세스보다 우선순위가 높게 설정됩니다.

 

스케줄링 큐

• 준비 큐(Ready Queue): CPU 사용을 기다리는 프로세스의 PCB가 저장되는 큐
• 대기 큐(Waiting Queue): 대기 상태에 접어든 프로세스의 PCB가 저장되는 큐. 주로 입출력 작업을 수행 중일 경우, 대기 큐에서 대기 상태로 입출력 완료 인터럽트를 기다림.

운영체제는 큐에 삽입된 프로세스를 순서대로 실행하되, 우선순위(priority)가 높은 프로세스를 먼저 실행합니다.

자료구조에서 큐는 일반적으로 선입선출(FIFO, First In First Out) 구조를 따르지만, 스케줄링 큐는 반드시 선입선출일 필요는 없다.

실행 중인 프로세스가 할당된 CPU 시간을 모두 소모(타이머 인터럽트 발생)하면 다시 준비 큐로 이동하고, 실행 도중 입출력 작업을 수행하는 등 대기 상태로 접어들어야 할 경우 대기 큐로 이동하게 됩니다.

대기 큐는 여러 개 존재하며, 같은 입출력 장치를 요청한 프로세스들은 같은 대기 큐에서 기다립니다.

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

선점형 스케줄링(Preemptive Scheduling)은 운영체제가 CPU를 사용 중인 프로세스로부터 강제로 CPU를 회수하여 다른 프로세스에 할당하는 방식입니다. 타이머 인터럽트를 사용하여 프로세스마다 정해진 시간 동안만 CPU를 할당하고, 시간이 만료되면 CPU를 회수하여 다른 프로세스에게 할당합니다.

• 장점: 여러 프로세스에 공정하게 CPU 자원을 배분할 수 있음
• 단점: 문맥 교환(context switching)이 자주 발생하여 오버헤드가 발생할 수 있음

비선점형 스케줄링(Non-preemptive scheduling)은 CPU를 사용 중인 프로세스가 종료하거나 스스로 대기 상태로 전환될 때까지 다른 프로세스가 CPU를 사용할 수 없는 방식입니다. 

• 장점: 문맥 교환 횟수가 적어 오버헤드가 낮음
• 단점: 긴 실행 시간이 필요한 프로세스가 CPU를 독점할 가능성이 있음  → 다른 프로세스는 무작정 대기해야 함

 

CPU 스케줄링 알고리즘

운영체제가 프로세스에 CPU를 배분하는 방법을 CPU 스케줄링 알고리즘이라고 합니다.

 

1. 선입 선처리 스케줄링 (FCFS, First Come First Served)

준비 큐에 삽입된 순서대로 CPU를 할당하는 방식입니다. 실행 시간이 긴 프로세스가 먼저 삽입되면, 이후의 삽입된 프로세스들이 오래 대기해야하는 부작용이 있으며, 이를 호위 효과(convoy effect)라고 합니다.

 

2. 최단 작업 우선 스케줄링 (SJF, Shortest Job First)

준비 큐에 삽입된 프로세스 중 CPU 실행 시간이 가장 짧은 프로세스부터 실행하는 방식입니다. 비선점형 스케줄링 알고리즘으로 분류되지만, ‘최소 잔여 시간 우선 스케줄링’처럼 선점형으로 구현될 수도 있다.

 

3. 라운드 로빈 스케줄링 (RR, Round Robin)

큐에 삽입된 프로세스들이 삽입된 순서대로 CPU를 이용하되, 정해진 타임 슬라이스(time slice)만큼만 CPU를 할당하는 선점형 스케줄링 방식입니다. 프로세스가 정해진 시간을 모두 사용하고도 완료되지 않으면 문맥 교환(context switching)이 발생해 다시 큐의 맨 뒤에 삽입된다.

 

4. 최소 잔여 시간 우선 스케줄링 (SRT, Shortest Remaining Time)

최단 작업 우선 스케줄링(SJF)과 라운드 로빈(RR) 스케줄링을 결합한 스케줄링 방식입니다. 프로세스로 하여금 정해진 타임 슬라이스만큼 CPU를 이용하되, 남아 있는 작업시간이 가장 적은 프로세스를 다음으로 CPU를 이용할 프로세스로 선택합니다.

 

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

각 프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행하는 방식입니다. 우선순위가 높은 프로세스를 먼저 처리하는 방식이기 때문에 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스로 인해 계속해서 실행이 연기될 수 있습니다. 이를 기아(Starvation)라고 합니다. 이를 방지하기 위한 방법으로 에이징(Aging) 기법을 적용하여 오랫동안 대기한 프로세스의 우선순위를 점진적으로 높이는 방식이 있습니다.

 

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

우선순위 스케줄링의 발전된 형태로, 우선순위별로 여러 개의 준비 큐를 사용하는 스케줄링 방식입니다. 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있게 되면, 그 다음으로 우선순위가 높은 큐에 있는 프로세스를 처리합니다. 마찬가지로 기아 현상이 발생할 수 있다. 이를 보완하는 스케줄링 알고리즘이 다단계 피드백 큐 스케줄링입니다.

 

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

다단계 큐 스케줄링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있습니다. 새롭게 진입하는 프로세스는 먼저 우선순위가 가장 높은 우선순위 큐에 삽입되고, 타임 슬라이스 동안 실행됩니다. 만약 해당 큐에서 실행이 끝나지 않으면 다음 우선순위 큐에 삽입되어 실행됩니다. 결국 오래 CPU를 사용해야 하는 프로세스의 우선순위가 점차 낮아지게 됩니다. 아사 현상이 발생할 수 있지만, 에이징 기법을 적용할 수 있습니다.

실제 운영체제에서는 프로세스의 가중치에 따라 타임 슬라이스가 다르게 할당될 수도 있다.

 

리눅스 CPU 스케줄링

많은 운영체제들이 다단계 피드백 큐 스케줄링을 사용하고 있습니다.

 

리눅스에서는 상황에 따라 서로 다른 CPU 스케줄링 알고리즘이 사용됩니다.

1. 실시간(Real-Time) 정책 스케줄링(매우 높은 우선순위를 할당)

• SCHED_FIFO: 선입 선처리
• SCHED_RR: 라운드로빈

SCHED_FIFO와 SCHED_RR은 RT(Real-Time) 스케줄러에 의해 이뤄지는 스케줄링으로, 실시간 프로세스에 적용되는 스케줄링 정책입니다.

실시간 프로세스: 어떤 프로세스들은 주어진 기간 내에 스케줄을 받지 못하면 치명적인 일이나 오류가 발생하는데 이들을 실시간 프로세스라고 한다. 그렇기에 일반 프로세스보다 스케줄링의 우선순위가 매우 높게 측정된다. 정밀 제어, 군용 무기 제어 등이 실시간 프로세스의 부류에 속한다.

 

2. 일반 정책 스케줄링

• SCHED_NORMAL: 일반적인 프로세스에 적용
• SCHED_BATCH: 일반적인 프로세스만큼 자주 선점하지 않는 배치 작업에 적용
• SCHED_IDLE: 우선순위가 매우 낮은 프로세스에 적용

SCHED_NORMAL은 일반적인 프로세스에 적용되는 스케줄링 정책으로, 리눅스 2.6.23 버전부터는 CFS라는 CPU 스케줄러에 의해 스케줄링이 이뤄집니다. CFS(Completely Fair Scheduler)란 프로세스에 대해 완전히 공평한 CPU 시간 배분을 지향하는 CPU 스케줄러를 말합니다.

리눅스에서는 프로세스마다 가상 실행 시간(vruntime)라는 정보를 유지하는데, CFS는 이 vruntime이 가장 작은 프로세스부터 스케줄링합니다. vruntime은 프로세스가 실제로 실행된 시간(runtime)이 아닌, 프로세스의 가중치를 고려한 가상의 실행 시간입니다. 가중치란 프로세스의 우선순위와 연관된 값으로, 프로세스의 우선순위가 높아질수록 가중치도 높아집니다.

CFS로 스케줄링되는 프로세스들의 타임 슬라이스도 다릅니다. 프로세스의 가중치가 높아지면 타임 슬라이스도 크게 할당받을 수 있습니다.

 

참고

강민철. 『 이것이 취업을 위한 컴퓨터 과학이다 』