[운영체제] 5. CPU 스케줄링

 본 내용들은 전공수업으로 배운 내용들을 스스로 리마인드하기 위한 목적으로 작성되었으며, 누군가에게 지식을 전달하기 위한 목적으로 작성한 것이 아닙니다. 대부분의 내용은 제가 수강했던 전공수업 및 Operating System Concepts, 10th Edition에 근거하고 있습니다. 

 

 

1. 개념

- CPU 스케줄링은 멀티 프로그래밍과 함께 CPU 이용률을 극대화하기 위해 등장했다. 기본적으로 프로세스는 CPU burst와 I/O burst의 사이클로 동작하게 되며, CPU burst를 어떻게 배분하느냐가 주요한 고민거리이다.

- 이런 CPU burst의 경우 short burst가 많은 부분을 차지 하고 있으며, longer burst는 그 비율이 훨씬 낮다.

 

- 프로세스 상태를 running, ready, waiting으로 나누어 생각했을 때, 두 가지 경우에 CPU 스케줄링이 필수적이다. running 상태에 있던 프로세스가 종료되는 경우와 running 상태에 있던 프로세스가 I/O 요청을 해 waiting 상태가 되는 경우다. 이 때는 프로세스가 할당된 CPU 사이클을 모두 소모하교 교체되는 것이 아니기 때문에, ready 큐에서 적절한 프로세스를 다시 선택해야 한다. 다른 프로세스 상태 변화에도 스케줄링을 적용할 수 있지만, 이 때는 필수적이지는 않다. 미리 스케줄링 된대로 정상진행하면 되기 때문이다.

- ready 큐에서 CPU에 할당할 적절한 프로세스를 선택해 주는 도구 혹은 로직이 CPU 스케줄러다.

 

- 선점형(preemptive)과 비선점형(nonpreemptive)가 이 챕터에 있어서 중요한 개념인데, 먼저 선점형은 프로세스가 실행 중인 상태여도 임의의 조건에 의해(우선순위가 높은 프로세스가 대기 중이라든지, 할당된 시간이 지났다든지 등) 현재 실행 중인 프로세스를 도중에 릴리즈하고, 다른 프로세스를 할당할 수 있는 컨셉이다. 그리고 비선점형은 이와 반대로 ready 큐에 있는 프로세스들은 무조건 현재 실행 중인 프로세스의 실행이 종료될 때까지 기다리게 된다.

- 따라서 현대의 OS들은 선점형 스케줄링 알고리즘을 사용하고 있다.

- 하지만 그렇다고 선점형 스케줄링에 문제가 없는 것은 아닌데, 여러 프로세스 간 데이터가 공유되고 있을 경우 race condition 문제가 발생할 수 있다. race condition에 대해서는 다른 챕터에서 깊게 다루게 될 것이다.

 

- 디스패처(Dispatcher)는 스케줄러에 의해 선택된 프로세스에게 CPU를 할당해주는 역할을 하며, 일련의 context switching 과정을 도맡고 있다. 레지스터 값들을 저장하고, 로드하며, 모드 비트를 변경하고, 유저 프로그램이 재시작되어야 할 부분으로 적절하게 이동하는 것 등이다.

- 이 때, 저 일련의 스위칭 과정에서 발생하는 지연을 dispatch latency라고 한다.

 

2. 스케줄링 기준

개념

- CPU 이용률(CPU utilization): 높을수록 좋은 명백한 지표, (시스템 가동시간-CPU 유휴시간)/시스템 가동시간 * 100으로 계산한다.

- 처리량(Throughput): 단위 시간 당 실행을 마치는 프로세스 수

- 처리 시간(Turnaround Time): 특정 프로세스가 실행을 마칠 때까지 걸린 전체 시간, 그러니까 ready 큐에서 대기한 시간, CPU에서 실행된 시간, I/O를 처리한 시간 등을 모두 합한 값이다

- 대기 시간(Waiting Time): 프로세스가 ready 큐에서 대기한 시간

- 반응 시간(Response Time): 이벤트와 같은 요청이 발생했을 때, 첫 응답을 생산하기까지 걸린 시간

 

스케줄링 알고리즘의 최적화 기준

- CPU 이용률 극대화, 처리량 극대화: 대부분의 알고리즘이 우선적으로 추구한다

- 최소 처리 시간, 최소 대기 시간: 보통 이 시간들이 길어지면, 반응과는 별개로 처리가 늘어진다

- 최소 반응 시간: UI 처리 등 이벤트 발생 처리가 중요한 경우

 

3. 스케줄링 알고리즘

- 간트 차트(Gantt Chart): 프로젝트 일정 관리를 위한 bar 형태의 도구이며, 프로세스 스케줄링 도구로도 사용된다. 프로세스별 시작과 끝을 표시하여 전체 스케줄링 상태를 한 눈에 파악하기 용이하며, 프로세스 간의 관계 파악에도 유리하다. 여기서 자세하게 다루진 않을 거지만, 나는 스케줄링 알고리즘을 공부할 때 이를 직접 그려보면서 했었고, 학교 시험에서도 나왔었다.

 

스케줄링 알고리즘 종류

- FCFS(First-Come, First-Served, 선입 선처리)

• 말 그대로, 먼저 도착한 프로세스를 먼저 할당하게 된다.
• 공평한 알고리즘이지만, Convoy effect로 인해서 비효율적인 경우가 많이 발생한다.

- SJF(Shortest Job First, 최단작업 우선)

• 각 프로세스의 다음 CPU burst 길이를 이용해, 가장 짧은 프로세스를 우선적으로 할당한다.
• FCFS와 달리 optimal하다. 각 프로세스들의 대기 시간 평균이 최소가 되는 방법이다.
• 다만 비선점형 기법이고, 이 방법의 선점형 방식은 아래에 나올 SJF다.
• 이상적인 방식이지만, 치명적인 문제가 있는데 다음 CPU burst 길이를 알아내는 것은 불가능하다. 물론 유저에 의해 정의된 길이를 받아서 사용하거나, 예측 값을 사용할 순 있겠지만 당연히 이 두 방법은 정확하지 않다.
• 일반적으로 예측 값은 exponential averaging을 사용해서 계산하며, 가중치 알파 값은 보통 2분의 1로 설정된다.

- SRTF(Shortest Remaining Time First, 최소 잔여시간 우선)

• SJF의 선점형 형태이다.
• 선점형이므로, 이름대로 잔여 burst 시간이 짧은 프로세스를 우선적으로 CPU에 할당한다. 따라서 프로세스가 실행 도중에, 새롭게 들어온 프로세스에 의해 선점당하는 것도 가능하다.

- RR(Round Robin, 라운드 로빈)

• 각각의 프로세스는 단위 시간만큼의 CPU 사용 시간을 할당 받게 되며, 이 단위 시간 값을 time quantum q라고 둔다. 교재에 나와있는 기준으로 보통 10~100ms 정도이다. 부여 받은 시간이 경과되면, 프로세스는 완료 여부와 관계 없이 다음 프로세스에게 CPU 자원을 내어주게 된다.
• q 값이 너무 크면 FCFS와 다를 바 없어지고, q 값이 너무 작으면 context switch가 과하게 많이 발생하며 오버헤드 총합이 커진다.
• 보통 처리 시간 평균 값이 SJF보다 조금 높지만, 훨씬 반응성이 좋다.
• 적절한 q 값을 찾는 것은 어려운 일이며, 일반적으로 대부분의 프로세스가 single time quantum 내에 다음 CPU burst를 완료할 수 있다면 처리 시간이 개선된다. 상기한 이유로 context switch time보다는 커야하지만, 너무 커지면 FCFS가 되므로 적당히 긴 시간이 좋다.
• 경험적으로 CPU burst들의 80%는 q보다 짧아야 한다고 알려져 있다. 

- Priority Scheduling(우선순위 스케줄링)

• 말그대로 각 프로세스에 우선순위를 부여하는 방법. 이 때 다양한 값이 기준이 될 수 있는데, 프로세스 내부적으로는 시간 제한, 메모리 요구량, 열린 파일 수, CPU burst와 I/O burst 비율 등이 있고, 외부적으로는 임의로 부여한 프로세스의 중요도 값, 컴퓨터 사용에 지불되는 재화의 타입과 양, 작업을 후원하는 부서, 정책적 요인 등이 있다.
• CPU는 우선순위를 나타내는 숫자가 낮은 숫자에 높은 우선순위를 부여하며, 대부분 선점형으로 사용한다.
• 기아(Starvation)은 이 때 나타날 수 있는 대표적인 문제이며, 우선순위가 낮은 프로세스가 무한히 대기하는 경우가 생길 수 있다. 이를 해결하려면 보통 에이징(Aging) 기법을 사용하며, ready 큐에 머문 시간만큼 우선 순위를 높여주는 방식을 채택한다.

- MLQ(Multi-Level Queue, 다단계 큐)

• Priority Scheduling 방식을 사용할 때, 각 우선순위를 각각의 구분된 큐로 나누어 사용하는 것. 프로세스는 일반적으로 위치할 수 있는 가장 높은 우선순위를 가진 큐에 할당된다.
• 이런 우선순위는 보통 프로세스 타입에 기반하며 real-time process라면 최상위 우선순위를, batch process라면 최하위 우선순위를 할당받는 식이다.
• 보통 ready 큐부터가 foreground, background 등의 여러 큐로 분할되어 있으며, 각 큐는 각자의 스케줄링 알고리즘이 정해져 있다. 이를테면 foreground 큐의 프로세스들은 짧은 반응 시간을 기대하므로 RR을 사용한다.
• 한 번 정해진 큐 내에서 프로세스는 계속 순환하게 된다.
• 또한 큐와 큐 사이의 스케줄링도 정해야 하는데, 고정 우선순위를 사용하면 기아 문제가 발생할 수 있고, 큐 별로 일정량의 CPU 시간을 할당 받는 시간 할당 방식을 사용한다. 

- MFQ(Multi-Level Feedback Queue, 다단계 피드백 큐)

• MLQ와 다르게 프로세스가 다양한 큐에 소속될 수 있는 방법. CPU 시간을 너무 많이 사용하는 프로세스는 우선순위를 낮춘다든지, 낮은 우선순위에서 너무 오래 대기하는 프로세스는 높은 우선순위로 에이징 한다든지.
• MFQ를 통해 에이징을 구현하기 좋으며, 이런 MFQ를 사용하는 스케줄러는 큐의 개수, 각 큐에 사용하는 알고리즘, 어떤 프로세스의 우선순위를 높이고 낮출지를 결정하는 메소드 등을 정의한다.

 

4. 스레드 스케줄링

- 이전 챕터에서 봤던 것처럼 유저 스레드와 커널 스레드는 구분되어 있다.

- 최신 OS에서는 스케줄 되는 최소 단위가 프로세스 단위보다는 커널 스레드 단위다.

- Many-to-One이나 Many-to-Many 모델에서는, 스레드 라이브러리가 유저 스레드들을 LWP 위에서 실행한다. 이런 방법은 동일한 프로세스 내의 스레들 사이에서 CPU를 경쟁하며 이를 PCS(process-contention scope) 경쟁이라고 한다. 그리고 그 우선순위는 보통 유저에 의해 설정된다.

- 커널 스레드가 실제로 이용가능한 CPU 스케줄 되는 것은 SCS(system-contention scope) 경쟁이며, 시스템 내의 모든 커널 스레드가 경쟁하게 된다.

- Pthread와 같은 API를 확인해보면, PCS 혹은 SCS를 지정할 수 있게 해뒀으며, 이 때 SCS 스레드를 생성한다는 것은 여전히 유저 스레드를 생성하는 것이고 단지 커널 스레드와 1:1 매핑되어 동작하는 개념이다.

 

5. 멀티 프로세서 스케줄링

- 여러 CPU를 사용해 스케줄링을 할 수 있다면, 스레드들을 병렬로 실행해 로드 밸런싱이 가능하게 되지만 스케줄링 문제가 훨씬 복잡해진다

- 멀티코어 CPU, 멀티스레드 코어, NUMA(Non-Uniform Memory Access), Heterogeneous multiprocessing 등의 아키텍처에서 멀티 프로세서 스케줄링을 도입할 수 있다.

 

스케줄링 접근 방법

- 일반적으로 각각의 프로세서가 스스로 스케줄링하도록 하는 SMP(Symmetric multiprocessing, 대칭 멀티 프로세싱)을 채택한다. 이 때 모든 프로세서가 하나의 공통 스레드 ready 큐를 이용하는 것과 각각 스레드 ready 큐를 이용하는 방법을 생각할 수 있는데, 전자의 경우 race condition 문제가 발생해 locking을 도입해야 하고 이에 대한 경쟁은 매우 심할 것이다. 따라서 성능 상의 이유로 보통은 후자의 방식이 채택된다.

- 현대의 CPU들은 동일한 물리 칩 내에 여러 개의 프로세서 코어를 넣는다. 이는 빠르고 전력 소모도 적은 방식이며, 코어 당 스레드도 지속해서 증가해왔다. 이는 메모리 스톨 문제에 있어서 이점을 가진다. 메모리 스톨 문제는 현대의 프로세서들의 속도가 메모리보다 훨씬 빠르게 동작하면서 발생하는 문제이며, 물리적 스레드의 도입은 메모리 스톨이 발생했을 때 다른 스레드를 바로 프로세싱할 수 있어 낭비되는 CPU 사이클을 줄인다.

- 이런 다중 물리적 스레드 혹은 하드웨어 스레드를 이용하는 기술은 CMT(Chip-MultiThreading)이라고 불리며, 각 하드웨어 스레드는 자체 레지스터 및 execution resources 세트가 있어 스레드 간의 빠른 전환을 가능케 한다.
- 만약 쿼드코어 시스템에서 각 코어 당 2개의 물리적 스레드가 존재한다면, OS는 8개의 논리적 프로세스를 가진 것으로 간주한다.

- 이런 구조에서 스케줄링은 두 단계로 일어난다. 첫째는 각 논리적 CPU(즉, 물리적 스레드 단위)에서 어떤 소프트웨어 스레드가 실행될 지 OS에 의해 결정되는 것이며, 둘째는 각 코어가 어떤 어떤 물리적 스레드를 처리할 지 스케줄링 하는 것이다.

로드 밸런싱

- SMP라면, 부하가 모든 CPU에 균등하게 배분하는 것이 중요하다.
- 로드 밸런싱은 작업 부하가 균등하게 분배되도록 하는 것이다. 일반적으로 Push migration 방식과 Pull migration 방식을 사용한다. 두 방식은 상호배타적이지는 않고, 함께 채택될 수 있다.

- Push migration: 주기적으로 각 프로세서의 부하를 체크하고, 과부하 상태의 프로세서가 가진 작업을 덜 바쁜 프로세서로 옮긴다.

- Pull migration: 유후 프로세서가 바쁜 프로세서의 작업을 pull하는 방식이다.

프로세서 선호도(Processor Affinity)

- 스레드가 한 프로세서에서 실행되었을 때, 스레드에 의해 최근에 접근된 데이터들이 프로세서의 캐시를 채운다.

- 따라서 로드 밸런싱 등의 이유로 스레드가 다른 프로세서로 옮겨지게 된다면, 캐시 메모리는 다시 로드되어야 하며 이는 비효율적이다. 따라서 대부분의 OS는 스레드를 계속 같은 프로세서에 할당하려고 하며, 이것이 프로세서 선호도다.

- Soft affinity와 Hard affinity가 존재하며, 전자는 되도록 같은 프로세서를 유지하려고 하지만 이를 무조건 보장하지는 않는 것이고, 후자는 시스템 콜을 통해 실행될 프로세서 집합을 명시하는 것이다. 많은 시스템이 두 가지 선호도 시스템을 모두 지원한다.

- 시스템의 메모리 아키텍처 또한 이에 영향을 줄 수 있는데, NUMA 아키텍처가 그 예시다. CPU의 가까운 메모리에 스레드를 할당해, 빠른 액세스를 제공한다.

 

6. 리얼타임 CPU 스케줄링

- 리얼타임은 일정시간 이내에 응답을 보장하는 시스템이다.

- Soft real-time system은 리얼타임 작업에 높은 우선 순위를 부여하고, 우선순위가 낮은 작업들보다 우선권을 가진다는 것만 보장한다.

- Hard real-time system은 작업이 엄격한 데드라인을 준수해 실행될 수 있도록 강제한다.

 

레이턴시 최소화

- 리얼타임 CPU 스케줄링을 위해서는 이벤트 레이턴시를 줄이는 것이 중요하며, 이벤트 레이턴시는 이벤트가 발생한 시점부터 그것이 서비스될 때까지 경과되는 시간을 의미한다.
- 보통 두 가지 타입의 레이턴시가 퍼포먼스에 영향을 미치는데, 인터럽트 레이턴시와 디스패치 레이턴시다.

 

- 인터럽트 레이턴시: 인터럽트 도착 후 인터럽트 서비스 루틴(ISR)이 시작될 때까지의 시간

- 명령어 처리 파이프라인 중 인터럽트 여부 확인까지의 시간, 인터럽트 유형 확인, ISR 실행을 위한 context swtich 등으로 구성되어 있다.

- 리얼타임 OS에서는 인터럽트 비활성화를 매우 짧은 시간 동안만 지정해야 한다.

 

- 디스패치 레이턴시는 스케줄러가 현재 프로세스를 중지하고 다른 프로세스를 시작하는데 필요한 시간

- 충돌 페이즈와 디스패치 페이즈로 이뤄져있다. 충돌 페이즈는 커널 동작 프로세스에 대한 선점과 높은 우선순위의 프로세스가 필요로 하는 리소스를 낮은 우선순위 프로세스가 릴리즈하는 두 요소로 이뤄져있는 단계다. 디스패치 페이즈는 우선순위 높은 프로세를 사용 가능한 CPU에 스케줄링하는 단계다.

 

우선순위 기반 스케줄링

- 리얼타임 스케줄링을 위해서는, 스케줄러가 선점 방식과 우선순위 기반 스케줄링을 지원해야 한다. 하지만 그것만으로는 soft real-time만 지원할 수 있으며 hard real-time을 지원하기 위해서는 데드라인 준수를 위한 작업이 필요하다.

- 이를 위해, 프로세스는 CPU를 상수 간격으로 요구하는 주기성을 가져야 한다. 각각의 주기 프로세스들은 고정된 프로세싱 시간 t와 데드라인 d, 그리고 주기 p가 정해져있다. 이 관계는 0<=t<=d<=p의 관계를 가지며, 실행 빈도는 1/p가 된다.

- 실시간 스케줄러는 위 값들을 이용해, 프로세스를 승인하고 제시간에 완료되도록 보장하거나, 데드라인 준수가 불가능할 경우 요청을 거부한다.

 

Rate-Monotonic 스케줄링

- 주기가 짧은 작업에 더 높은 우선순위를 부여하고 긴 작업에 낮은 우선순위를 부여한다.

- CPU를 더 자주 요구하는 작업에 더 높은 우선순위를 할당하기 위함이다.

- 주기와 프로세싱 시간을 가지고 계산하게 되며 총 CPU 이용률을 미리 계산해서 스케줄링 가능 여부를 판단한다. N개 프로세스 스케줄링 시 worst-case CPU 이용률은 N(2^(1/N)-1)에 해당한다.

 

Earliest Deadline First Scheduling(EDF) 스케줄링

- 우선순위가 데드라인에 의해 결정된다. 프로세스가 실행 가능 상태가 되면 스케줄러에 데드라인을 알려야 하며, 이 때 데드라인이 가장 가까운 프로세스를 우선적으로 스케줄링한다.

 

Proportional Share Scheduling

- 총 단위시간을 기준으로 프로세스 별로 각자의 몫을 할당받는 방식. 

- 할당받은 몫/총 단위시간에 의해 프로세서 시간을 보장받으며, 만약 현재 남아있는 몫보다 더 큰 몫을 요구하는 프로세스가 공유를 요청하면 이를 거부한다.