CPU 스케줄링

운영체제의 CPU 배분 방법을 CPU 스케줄링이라고 한다. CPU 스케줄링 알고리즘은 이러한 CPU 스케줄링의 절차를 말하며, 이 CPU 스케줄링 알고리즘을 결정하고 수행하는 운영체제의 일부분을 CPU 스케줄러라고 한다.

• 프로세스뿐만 아니라 스레드도 CPU의 스케줄링 대상이다. 실행의 문맥을 가지고 있는 모든 것은 스케줄링을 할 수 있다.

우선순위

모든 프로세스는 CPU의 자원을 필요로 하기 때문에 운영체제는 공정하고 합리적인 방법으로 CPU의 자원을 프로세스에 할당해야 한다. 운영체제는 프로세스별 우선순위를 판단해 PCB에 명시하고, 우선순위가 높은 프로세스에는 CPU 자원을 더 빨리, 더 많이 할당한다.

﹡사용자가 일부 프로세스의 우선순위를 직접 높일 수도 있다.

운영체제가 우선순위를 할당하는 대표적인 고려 요소는 CPU 활용률이다. 운영체제는 가급적 CPU 활용률을 높게 유지할 수 있도록 우선순위를 할당한다.

CPU 활용률(CPU utilization): 전체 CPU 가동 시간 중 작업을 처리하는 시간의 비율

 

운영체제는 높은 CPU 활용률을 유지하기 위해 기본적으로 입출력 작업이 많은 프로세스의 우선순위를 높게 유지한다.

프로세스들은 CPU와 입출력장치를 모두 사용해 실행과 대기 상태를 오가며 실행되는데, 프로세스가 CPU를 이용하는 작업을 CPU 버스트(CPU brust)라고 하고, 입출력장치를 기다리는 작업을 입출력 버스트(I/O burst)라고 한다.

또한, 프로세스마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있는데, 복잡한 수학 연산이나 그래픽 처리 작업을 담당하는 프로세스처럼 CPU 작업이 많은 프로세스는 CPU 집중 프로세스(CPU bound process)라고 하고, 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스처럼 입출력 작업이 많은 프로세스를 입출력 집중 프로세스(I/O bound process)라고 한다.

 

입출력 집중 프로세스는 실행 상태보다 입출력을 위한 대기 상태에 더 많이 머무르지만, CPU 집중 프로세스는 대기 상태보다 실행 상태에 더 많이 머무른다. 그렇기 때문에 입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 CPU 자원을 요구했다면, 입출력 집중 프로세스를 가능한 빨리 실행시켜 끊임없이 입출력장치를 작동시킨 다음, CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 합리적이다.

이렇듯 모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다 상황에 맞게 CPU를 배분하는 것이 더 효율적이므로 운영체제는 프로세스마다 우선순위를 부여해 CPU를 할당한다.

---

스케줄링 큐

운영체제는 프로세스들에게 '자원을 이용하고 싶다면 줄을 서서 기다릴 것'을 요구한다. CPU를 이용하고 싶거나 메모리에 적재되고 싶은 프로세스, 대기 상태로 특정 입출력장치를 이용하고 싶은 프로세스 모두에 해당한다. 그리고 이 줄은 스케줄링 큐를 통해 구현된다.

운영체제가 관리하는 줄인 큐에는 다양한 종류가 있지만, 대표적으로 준비 큐와 대기 큐가 있다. 준비 큐(ready queue)는 CPU를 이용하고 싶은 프로세스의 PCB가 서는 줄을 의미하고, 대기 큐(waiting queue)는 대기 상태에 접어든 프로세스의 PCB가 서는 줄을 의미한다.

주로 입출력 작업을 수행 중일 경우, 대기 큐에서 대기 상태로 입출력 완료 인터럽트를 기다리게 된다. 준비 상태인 프로세스의 PCB는 준비 큐의 마지막에 삽입되어 CPU를 사용할 차례를 기다린다.

운영체제는 큐에 삽입된 순서대로 실행하되, 우선순위가 높은 프로세스부터 먼저 실행한다. 실행되는 프로세스가 할당받은 시간이 모두 소모할 경우(타이머 인터럽트를 받을 경우) 준비 큐로 다시 이동하고, 실행 도중 입출력 작업을 수행하는 등 대기 상태로 접어들어야 할 경우 대기 큐로 이동하게 된다.

 

 

같은 입출력장치를 요구한 프로세스들은 같은 대기 큐에서 기다린다. 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 이 PCB를 준비 상태로 변경한 뒤 큐에서 제거하고, 해당 PCB는 준비 큐로 이동한다.

---

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

스케줄링은 기본적으로 프로세스의 실행이 끝나면 이루어지지만, 프로세스가 종료되지 않았음에도 실행 도중 스케줄링이 수행되는 대표적인 두 시점이 있다.

1. 실행 상태에서 입출력 작업을 위해 대기 상태로 전환될 때
2. 실행 상태에서 타이머 인터럽트가 발생해 준비 상태로 변경될 때

1번과 2번 모든 상황에서 수행되는 스케줄링 유형을 선점형 스케줄링이라고 하고, 1번 상황에서만 수행되는 스케줄링을 비선점형 스케줄링이라고 한다.

 

선점형 스케줄링(preemptive scheduling): 현재 어떤 프로세스가 CPU를 할당받아 사용하고 있더라도 운영체제가 프로세스로부터 CPU 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식

• 프로세스마다 정해진 시간만큼만 CPU를 이용하고, 정해진 시간을 모두 소비하면 운영체제가 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에게 할당하는 방식이다.
• 언제든 더 급한 프로세스가 끼어들어 CPU를 사용할 수 있으므로 한 프로세스의 CPU 독점을 막고 여러 프로세스에 골고루 CPU 자원을 배분할 수 있다.
• 문맥 교환 과정에서 오버헤드가 발생할 수 있다.

비선점형 스케줄링(non-preemptive scheduling): 어떤 프로세스가 CPU를 사용하고 있을 때 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지는 다른 프로세스가 끼어들 수 없는 스케줄링 방식

• 비선점형 스케줄링으로 실행되는 프로세스가 있다면 다른 프로세스들은 그 프로세스의 CPU 사용이 모두 끝날 때까지 기다려야 한다.
• 문맥 교환의 횟수가 적어 상대적으로 오버헤드의 발생이 적다.
• 어떤 프로세스가 CPU를 사용 중이라면 당장 CPU를 사용해야 하는 프로세스라도 무작정 기다리는 수 밖에 없다.

---

CPU 스케줄링 알고리즘

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

준비 큐에 삽입된 순서대로 먼저 CPU를 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식이다.

• 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 있다. 먼저 삽입된 프로세스의 오랜 실행 시간으로 인해 나중에 삽입된 프로세스의 실행이 지연되는 문제를 호위 효과(convoy effect)라고 한다.

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

준비 큐에 삽입된 프로세스 중 CPU를 이용하는 시간의 길이가 가장 짧은 프로세스부터 먼저 실행하는 스케줄링 방식이다.

• 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 최소 잔여 시간 우선 스케줄링처럼 선점형으로 구현될 수도 있다.

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

선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식으로, 타임 슬라이스는 프로세스가 CPU를 사용하도록 정해진 시간을 의미한다.

즉, RR은 큐에 삽입된 프로세스들이 삽입된 순서대로 CPU를 이용하되, 정해진 타임 슬라이스만큼만 CPU를 이용하는 선점형 스케줄링이다.

• 프로세스가 정해진 시간을 모두 사용하고도 완료되지 않으면 문맥 교환이 발생해 다시 큐의 맨 뒤에 삽입된다.

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

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

우선순위 스케줄링(priority)

프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 방식이다.

• 우선순위가 높은 프로세스를 먼저 처리하는 방식이기 때문에 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었더라도) 우선순위가 높은 프로세스로 인해 계속해서 실행이 연기되는 기아(=아사, starvation) 현상이 발생할 수 있다.
• 이를 방지하기 위한 기법으로 에이징(aging)이 있다. 에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식으로, 에이징을 적용하면 우선순위가 낮아서 마냥 기다리기만 하는 프로세스가 없어지게 된다.

다단계 큐 스케줄링(multilevel queue)

우선순위 스케줄링의 발전된 형태로, 우선순위별로 여러 개의 준비 큐를 사용하는 스케줄링 방식이다. 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있게 되면, 그 다음으로 우선순위가 높은 큐에 있는 프로세스를 처리한다.

• 프로세스들이 큐 사이를 이동할 수 없기 때문에 우선순위가 낮은 프로세스의 작업이 계속해서 연기되는 기아 현상이 발생할 수 있다.

다단계 피드백 큐 스케줄링(multilevel feedback queue)

다단계 큐 스케줄링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있다는 점에서 차이가 있다. 다단계 피드백 큐 스케줄링에 새롭게 진입하는 프로세스는 먼저 우선순위가 가장 높은 우선순위 큐에 삽입되고, 타임 슬라이스 동안 실행된다. 만약 해당 큐에서 프로세스의 실행이 끝나지 않으면 다음 우선순위 큐에 삽입되어 실행된다.

• 비교적 CPU를 오래 사용해야 하는 'CPU 집중 프로세스'들의 우선순위는 낮아지고, 비교적 CPU를 적게 사용하는 '입출력 집중 프로세스'들은 우선순위가 높은 큐에서 실행이 끝나게 된다.
• 기아 현상을 예방하기 위해 낮은 우선순위 큐에서 오래 기다리고 있는 프로세스들을 높은 우선순위 큐로 이동시키는 에이징 기법을 적용할 수 있다.

---

리눅스 CPU 스케줄링

리눅스에서는 상황에 따라 다양한 스케줄링 알고리즘이 사용될 수 있다. 이는 리눅스 운영체제의 스케줄링 정책을 보면 알 수 있다.

스케줄링 정책	적용 상황
SCHED_FIFO	실시간성 프로세스에 적용되는 정책(매우 높은 우선순위를 할당함)
SCHED_RR
SCHED_NORMAL	일반적인 프로세스에 적용되는 정책
SCHED_BATCH	일반적인 프로세스만큼 자주 선점하지 않는 배치 작업에 적용되는 정책
SCHED_IDLE	우선순위가 매우 낮은 프로세스에 적용되는 정책(매우 낮은 우선순위를 할당함)

 

• SCHED_FIFO, SCHED_RR은 RT(Real-Time) 스케줄러에 의해 이뤄지는 스케줄링으로, 실시간성이 강조된 프로세스에 적용되는 스케줄링 정책이다.
• SCHED_NORMAL은 CFS라는 CPU 스케줄러에 의해 스케줄링이 이뤄진다. CFS(Completely Fair Scheduler)는 프로세스에 대해 완전히 공평한 CPU 시간 배분을 지향하는 CPU 스케줄러를 말한다.

리눅스에서는 프로세스마다 가상 실행 시간(vruntime)이라는 정보를 유지하는데, CFS는 이 vruntime이 가장 작은 프로세스부터 스케줄링한다. vruntime은 프로세스가 '실제로 실행된 시간'이 아닌, 프로세스의 '가중치(weight)'를 고려한 가상의 실행 시간이다.

즉, 프로세스의 가중치가 높아질수록 vruntime이 천천히 증가하고, 먼저 스케줄링될 확률이 높다.

vruntime = CPU를 할당받아 실행된 시간 * $\frac{평균 가중치(상수)}{프로세스의 가중치}$

 

CFS로 스케줄링되는 프로세스들의 타임 슬라이스는 프로세스의 가중치에 따라 결정된다. 프로세스의 우선순위가 높아질수록 가중치가 높아지고 타임 슬라이스도 크게 할당 받을 수 있다.

타임 슬라이스 = ($\frac{프로세스의 가중치}{CFS 큐에서 대기하는 프로세스들의 전체 가중치}$) * CFS 큐에서 대기하는 프로세스들의 타임 슬라이스 전체 합

---

참고 사이트

이것이 취업을 위한 컴퓨터 과학이다

이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접 | 강민철 - 교보문고