[운영체제] CPU 스케줄링

용어 정리

CPU 스케줄링
: 운영체제가 CPU 자원을 배분하는 방법

CPU 스케줄링 알고리즘
: CPU 스케줄링의 절차

CPU 스케줄러
: CPU 스케줄링 알고리즘을 결정하고 수행하는 운영체제의 일부분

CPU 스케줄링 대상
: 실행의 문맥이 있다면 모두 스케줄링의 대상이다. 프로세스뿐만 아니라 스레드도 포함된다. 

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

CPU 버스트
: 프로세스가 CPU를 이용하는 작업

입출력 버스트
: 입출력장치를 기다리는 작업

선점형 스케줄링
: 운영체제가 프로세스로부터 CPU 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링
- CPU 자원을 골고루 배분할 수 있지만, 문맥 교환 과정에서 오버헤드가 발생

비선점형 스케줄링
: 프로세스가 종료되거나 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링
- 문맥 교환의 오버헤드는 적지만, CPU 자원 독점 문제가 발생

 

---

 

1. 우선순위

운영체제는 프로세스별 우선순위를 판단하여 PCB에 명시하고,
우선순위가높은 프로세스에는 CPU의 자원을 더 빨리, 많이 할당한다.  

 

- 할당 기준 중 대표적으로 CPU 활용률이 높은 프로세스에게 높은 우선순위를 할당한다.

 

- 입출력 집중 프로세스를 가능한 빨리 실행시켜 끊임없이 입출력장치를 작동시킨 다음, CPU 집중 프로세스에 집중적으로 CPU를 할당한다.

 

 

---

 

2. 스케줄링 큐

운영체제의 CPU 자원 할당을 위해 관리하는 큐

 

준비 큐(Ready Queue)
: CPU를 이용하고 싶은 프로세스의 PCB가 서는 줄.
실행되는 프로세스가 할당받은 시간을 모두 소비할 경우(타이머 인터럽트를 받을 경우) 준비 큐로 이동한다.

대기 큐(Waiting Queue)
: 대기 상태에 접어든 프로세스의 PCB가 서는 줄.
주로 입출력 작업을 수행 중일 경우, 대기 큐에서 대기 상태로 입출력 완료 인터럽트를 기다린다. 입출력 완료 인터럽트가 발생하면 이 PCB를 준비 큐로 이동시킨 후 대기 큐에서 제거한다.

 

---

 

3. CPU 스케줄링 알고리즘

3-1. 선입 선처리(First Come, First Served / FCFS)

 준비 큐에 삽입된 순서대로 CPU를 할당하는 스케줄링 방식

프로세스들이 기다리는 시간이 매우 길어질 수 있으며, 호위 효과가 발생할 수 있다.

(호위 효과 : 먼저 삽입된 프로세스의 오랜 실행 시간으로 인해 나중에 삽입된 프로세스의 실행이 지연되는 문제)

 

3-2. 최단 작업 우선(Shortest Job First / SJF)

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

시간의 길이가 긴 프로세스의 경우 아사 현상이 발생할 수 있다.

 

3-3. 라운드 로빈(Round Robin)

선입 선처리에 타임 슬라이스라는 개념이 더해진 스케줄링 방식

문맥 교환에 오버헤드가 발생할 수 있다.

(타임 슬라이스 : 프로세스가 CPU를 사용하도록 정해진 시간)

 

3-4. 최소 잔여 시간 우선(Shortest Remaining Time / SRT)

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

 

3-5. 우선순위 (Priority)

가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 방식

우선순위가 낮은 프로세스의 경우 아사 현상이 발생할 수 있다.

이를 방지하기 위한 방법으로 에이징을 활용하기도 한다.

(에이징 : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식)  

 

3-6. 다단계 큐(Multilevel Queue)

우선순위 스케줄링의 발전된 형태로, 우선순위별로 여러 개의 준비 큐를 사용하는 스케줄링 방식 

프로세스들이 큐 사이를 이동할 수 없기 때문에 우선순위가 낮은 프로세스의 경우 아사 현상이 발생할 수 있다.

 

3-7. 다단계 피드백 큐(Multilevel Feedback Queue)

프로세스들이 큐 사이를 이동할 수 있는 다단계 큐 스케줄링 방식

가장 높은 우선순위 큐에있는 프로세스가 작업을 실행한 후, 해당 작업을 모두 끝내지 못 할 경우 다음 우선순위 큐에 삽입된다. CPU 집중 프로세스들의 우선순위는 낮아지고, 입출력 집중 프로세스들의 우선순위가 자연스럽게 높아진다.

아사 현상을 예방하기 위해 낮은 우선순위 큐에서 대기한 프로세스들을 높은 우선순위 큐로 이동시키는 에이징 기법을 적용할 수도 있다. 

 

---

 

4. 리눅스 CPU 스케줄링

스케줄링 정책

1. SCHED_FIFO : 실시간성 프로세스에 적용되는 정책
2. SCHED_RR : 실시간성 프로세스에 적용되는 정책
3. SCHED_NORMAL : 일반적인 프로세스에 적용되는 정책
4. SCHED_BATCH : 일반적인 프로세스만큼 자주 선점하지 않는 배치 작업에 적용되는 정책
5. SCHED_IDLE : 우선순위가 매우 낮은 프로세스에 적용되는 정책

1,2가 매우 높은 우선순위를 할당하고, 3 다음 4, 5 순으로 우선순위가 적용된다.

 

4-1. FIFO, RR

RT(Real-Time) 스케줄러에 의해 이뤄지는 스케줄링

 

4-2. NORMAL

완전히 공평한 CPU 시간 배분을 지향하는 CFS(Completely Fair Scheduler)에 의해 이뤄지는 스케줄링

 

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

 

여기서 가중치란, 프로세스의 우선순위와 연관된 값으로 프로세스의 우선순위가 높아질수록 가중치도 높아진다. 프로세스의 가중치가 높아지면 타임 슬라이스도 높게 할당받을 수 있다.

 

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

 

time slice =

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

 

vruntime 최솟값 빠르게 골라내기

CFS 스케줄러는 프로세스 중 vruntime이 가장 작은 프로세스를 선별하기위해 RB 트리 자료구조를 활용한다.