[운영체제] CPU 스케줄링

CPU 스케줄링이란?

 CPU의 활용률을 극대화하여 컴퓨터의 성능을 극대화 하기 위해 실행 대기 중인 프로세스 중 하나를 선택하는 과정

 

과거에는 프로세스만 다루는 운영체제에서 프로세스 기반의 스케줄링이 주를 이뤘지만,

오늘날에는 대부분 멀티스레드 운영체제에서 스레드만 스케줄링하는 형식이다. 

대부분 멀티 코어 CPU를 사용하는 만큼 한 컴퓨터 내의 여러 프로세서에 스레드 스케줄링이 필요하다.

 

컴퓨터 시스템마다 서로 다른 관점의 성능을 추구한다. 그러므로 스케줄링은 목표나 평가 지표에 의해 기준이 나눠진다.

CPU 스케줄링의 기준은 다음과 같다.

• CPU 활용률(CPU utilization)
• 처리율(throughput)
• 응답 시간(response time)
• 대기 시간(waiting time)
• 소요 시간(turnaround time)
• 공정성(fairness)
• 시스템 정책(policy enforcement)
• 자원 효율성(resource efficiency) 

 스케줄링 기준들은 서로 상충되는 면이 있다.

 CPU 활용률 <-> 공정성, 처리율 <-> 응답시간, 시스템 정책 시행 <-> 처리율 등등

 

CPU 스케줄링은 강제 중단 여부에 따라서 선점 스케줄링과 비선점 스케줄링으로 나눠진다.

선점 스케줄링 (Preemptive scheduling)

현재 실행중인 프로세스가 있을 때, 우선 순위가 높은 프로세스가 현재 실행중인 프로세스를 강제로 중단하고 CPU를 할당 하는 스케줄링 방식이다.

- 특징

• 우선 순위가 높은 프로세스를 빠르게 처리해야할 경우에 유용하다.
• 시분할 시스템의 기본 스케줄링 방식이다.
• 선점이 일어날 경우, 오버헤드가 발생하며 처리시간을 예측하기 힘들다.
• 현대의 운영체제 대부분 선점 스케줄링 방식을 사용한다.

- 속하는 스케줄링 알고리즘 

1.  SRT(Shortest Remaining Time) 스케줄링 
2.  라운드로빈(Round-Robin) 스케줄링
3.  다단계 큐(Multi-level Queue) 스케줄링
4.  다단계 피드백 큐 스케줄링

 

 

 

비선점 스케줄링 (Non-Preemptive scheduling)

 선점 스케줄링과 반대로 프로세스가 작업이 완료되는 시점에만 스케줄링이 일어난다.

- 속하는 스케줄링 알고리즘

1.  HRN(Highest response ratio next) 스케줄링
2.  SJF(Shortest Job First) 스케줄링
3.  우선순위(priority) 스케줄링
4.  기한부(deadline) 스케줄링
5.  FIFO(First in first out) 스케줄링

기본적인 스케줄링 알고리즘 

 1. FIFO 스케줄링 : FCFS 라고도 한다. 도착하는 프로세스 순으로 큐에 삽입한 후 프로세스가 끝날 때, 다음 프로세스를 선택하는 방식이다. 

 2. SJF 스케줄링 : 큐 안에 있는 프로세스 중 수행시간이 짧은 것을 먼저 수행하는 방식으로, 평균 대기 시간을 감소시키는 장점이 있는 반면, 실행 시간이 예측 가능한 시스템에서만 사용이 가능하여 현실에서는 거의 사용되지 않는다.

 3. SRT 스케줄링 : SJF의 Preemprtive 버전으로 남은 처리시간이 더 짧은 프로세스가 큐에 들어오면 그 프로세스로 선점되는 방식이다.

 4. 라운드 로빈 스케줄링 : 각 프로세스는 같은 크기의 CPU 시간을 할당 받고 선입선출에 의해 행된다. 할당 된 시간이 지나거나 프로세스가 종료되면 켄텍스트 스위칭이 일어난다.

 5. Fixed priority 스케줄링 : 모든 프로세스에 고정 우선 순위를 할당하여, 우선 순위가 높은 순으로 스케줄링한다. 현재 실행중인 프로세스보다 더 높은 우선순위의 프로세스가 도착하면, 컨텍스트 스위칭이 일어난다.

 6. 다단계 큐 스케줄링 : 큐를 여러개 사용하는 방법으로 각각의 큐가 자신의 스케줄링 알고리즘을 수행하며, 큐와 큐 사이에도 우선순위를 부여한다.

 

CFS(Completely Fair Scheduling) 알고리즘

 데스크톱에서 대화식 어플리케이션에 적합한 스케줄링 방법으로 모든 프로세스들이 공평하게 스케줄링된다.

공평성을 위한 4가지 요소가 필요한데, 다음과 같다.

 1. virtual runtime(가상 실행 시간) : vruntime 으로 표기, 실제 CPU 사용 시간과 가중치를 고려하여 계산된 시간이다. 

                                              작을수록 더 높은 스케줄링 순위를 배치받는다.

 2. run queue : 대기중인 프로세스들이 들어 있는 큐, 트리로 구성, vruntime이 적은 순으로 정렬된 트리.

 3. time slice(시간 할당 값) : 한번 스케줄되어, 강제 중단 없이 실행을 보장받는 시간

 4. weight(가중치) : 스케줄링 우선순위에 영향을 미치는 값. nice(우선순위가 낮은 상대치)값에 따라 결정. 

                          클수록 vruntime이 작게 계산된다.