운영체제 공룡책 - Chapter 5. CPU 스케줄링

Chapter 5. CPU 스케줄링

1. 기본 개념
2. 스케줄링 기준
3. 스케줄링 알고리즘
4. 스레드 스케줄링
5. 다중 처리기 스케줄링
6. 실시간 CPU 스케줄링
7. 운영체제 사례들
8. 알고리즘의 평가
9. 요약

 

Chapter 5. CPU 스케줄링

최신 운영체제에서는 실질적으로 운영체제는 프로세스가 아니라 커널 수준 스레드를 스케줄 한다.

 

5.1 기본 개념 -p220

어느 한 순간에 다수의 프로세스를 메모리 내에 유지한다. 어떤 프로세스가 대기해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다.

 

5.1.1 CPU-I/O 버스트 사이클 -p220

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다. 프로세스 실행은 CPU 버스트(burst)로 시작된다. 뒤이어 I/O 버스트가 발생한다. 결국 마지막 CPU 버스트는 또 다른 I/O 버스트가 뒤따르는 대신, 실행을 종료하기 위한 요청과 함께 끝난다.

 

5.1.2 CPU 스케줄러 -p220

CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중에서 하나를 선택해 실행해야 한다. 선택 절차는 CPU 스케줄러에 의해 수행된다.

 

5.1.3 선점 및 비선점 스케줄링 -p221

CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다.

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (예를 들어, I/O 요청이나 자식 프로세스가 종료되기를 기다리기 위해 wait()를 호출할 때)

2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 ( 예를 들어, 인터럽트가 발생할 때)

3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (예를 들어, I/O의 종료시 )

4. 프로세스가 종료할 때.

 

상황 1과 4의 경우, 스케줄링 면에서는 선택의 여지가 없다. 실행을 의해 새로운 프로세스 (준비 큐에 하나라도 존재할 경우) 가 반드시 선택되어야 한다. 그러나 상황2와 3을위해서는 선택의 여지가 있다.

 

상황 1과 4에서만 스케줄링이 발생할 경우, 우리는 이러한 스케줄링 방법을 비선점 ( nonpreemptive) 또는 협조적(cooperative) 이라고 한다. 그렇지 않으면, 그것은 선점(preemptive) 라고 한다.

 

5.1.4 디스패치 -p223

CPU 스케줄링 기능에 포함된 또 하나의 요소는 디스패처 ( dispatcher ) 이다. 디스패처는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며 다음과 같은 작업을 포함한다.

• 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동 (jump) 하는 일

디스패처는 모든 프로세스의 문맥 교환 시 호출 되므로, 가능한 한 최고로 빨리 수행되어야 한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간을 디스패치 지연 ( dispatch latency ) 이라고 한다.

 

 

5.2 스케줄링 기준 -p225

CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이 제시되었다. 비교하는 데 사용되는 특성에 따라서 최선의 알고리즘을 결정하는 데 큰 차이가 발생한다. 사용되는 기준은 다음을 포함한다.

 

1. CPU 이용률 ( utilization ):

실제 시스템에서는 40% 에서 (부하가 적은 시스템의 경우) 90%까지의 (부하가 큰 시스템의 경우) 범위를 가져야한다. (Linux, maxOS 및 UNIX 시스템에서 top 명령을 사용하여 CPU 이용률을 얻을 수 있다.)

 

2. 처리량 ( throughput ):

작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수다.

 

3. 총처리 시간 ( turnaround time) :

대기 시간은 준비 큐에서 대기하면서 보낸 시간의 합이다.

 

4. 응답 시간 ( response time ):

대화식 시스템 ( interactice system) 에서, 총처리 시간은 최선의 기준이 아닐 수도 있다. 프로세스가 어떤 출력을 매우 일찍 생성하고, 앞서의 결과가 사용자에게 출력되는 사이에 새로운 결과를 얻으려고 연산을 계속 하는 경우가 종종 있다.

따라서 또 다른 기준은 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간이다. 응답 시간이라고 하는 이 기준은 응답이 시작되는 데까지 걸리는 시간이지, 그 응답을 출력하는데 걸리는 시간은 아니다.

 

CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화 하는 것이 바람직하다.

 

 

5.3 스케줄링 알고리즘 -p226

대부분의 최신 CPU 아키텍처에는 여러 개의 처리 코어가 있지만 이러한 스케줄링 알고리즘을 처리 코어가 하나뿐이라고 가정하고 설명한다. 즉, 한 개의 처리 코어를 가진 CPU가 한 개인 시스템이므로 한 번에 하나의 프로세스만 실행할 수 있다.

5.3.1 선입 선처리 스케줄링 -p226

가장 간단한 CPU 스케줄링 알고리즘은 선입 선처리(FCFS) 스케줄링 알고리즘이다. CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 프로세스가 준비 큐에 진이하면, 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결한다. CPU가 가용상태가 되면, 준비 큐의 앞부분에 있는 프로세스에 할당된다. 

 

선입 선처리 스케줄링 알고리즘은 비선점형 이라는 것을 주의하자. 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료하든지 또는 I/O 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유한다.

 

5.3.2 최단 작업 우선 스케줄링 Shortest Job First Scheduling-p228

CPU가 이용 가능해지면, 가장 작은 다음 CPU 버스트를 가진 프로세스에 할당한다. SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균대기 시간을 가진다는 점에서 최적임을 증명할 수 있다.

SJF 알고리즘은 선점형이거나 또는 비선점형일 수 있다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수 있다.

 

5.3.3 라운드 로빈 스케줄링 Round-Robin Scheduling -p230

라운드 로빈 스케줄링 알고리즘은 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다.

시간할당량 또는 타임슬라이스라고 하는 작은 단위의 시간을 정의한다.

준비 큐는 원형 큐( circular queue ) 로 동작한다. CPU스케줄러는 준비큐를 돌면서 한 번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다. 새로운 프로세스들은 준비 큐의 꼬리에 추가된다. CPU 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머를 설정한 후, 프로세스를 디스패치 한다.

 

라운드 로빈 스케줄링 알고리즘에서는, 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두 번 이상의 시간 할당량을 할당받는 프로세스는 없다.

 

라운드 로빈 알고리즘의 성능은 시간 할당량의 크기에 매우 많은영향을 받는다. 극단적으로 시간 할당량이 매우 크면 선입선처리(FCFS) 정책과 같다.

반대로 매우 작으면(ex 1마이크로초) 라운드 로빈 정책은 매우 많은 문맥 교환을 야기 한다.

 

경험상 CPU 버스트의 80% 는 시간 할당량보다 짧아야 한다.

 

5.3.4 우선순위 스케줄링 Priority Scheduling -p233

우선순위가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다. 우선순위가 같은 프로세스들은 선입 선처리 순서로 스케줄된다. SJF 알고리즘은 우선순위가 다음 CPU 버스트의 역인 단순한 우선순위 알고리즘 이다.

 

우선순위는 내부적 또는 외부적으로 정의될 수 있다. 내부적으로 정의된 우선순위는 프로세스의 우선순위를 계산하기 위해 어떤 측정 갖능한 양들을 사용한다. 예를 들어,

• 시간 제한,
• 메모리 요구,
• 열린 파일의 수,
• 평균 I/O 버스트의 평균 CPU 버스트

에 대한 비율 등이 있다.

 

외부적 우선순위는 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양, 그 작업을 후원하는 부서 그리고 정치적인 요인 등이 있다.

 

우선순위 스케줄링은 선점형이거나 또는 비선점형이 될 수 있다. 프로세스가 준비 큐에 도착하면, 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선 순위와 비교한다.

 

선점형 우선순위 스케줄링 알고리즘은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점한다.

 

비선점형 우선순위 스케줄링 알고리즘은 단순히 준비완료 큐의 머리 부분에 새로운 프로세스를 넣는다.

 

우선순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄 (indefinite blocking) 또는 기아 상태 ( starvation )이다.

낮은 우선순위의 프로세스들이 무한히 봉쇄되는 문제에 대한 한 가지 해결 방안은 노화(aging)이다. 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가 시킨다.

 

5.3.5 다단계 큐 스케줄링  -p235

우선순위 스케줄링은 우선순위가 가장 높은 큐에서 프로세스를 스케줄 한다. 다단계 큐 라고 하는 이 방법은 우선순위 스케줄링이 라운드 로빈과 결합한 경우에도 효과적이다. 우선순위가 가장 높은 큐에 여러 프로세스가 있는 경우 라운드 로빈 순서로 실행된다.

 

5.3.6 다단계 피드백 큐 스케줄링 -p237

다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

 

일반적으로, 다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의된다.

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
• 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법

 

 

 

 

5.4 스레드 스케줄링 Thread Scheduling -p239

대부분의 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다. 이 절에서는 사용자 수준과 커널 수준 스레드의 스케줄링에 관한 쟁점을 탐구하고 Pthread의 스케줄링 사례를 제공한다.

 

5.4.1 경쟁 범위 Contention Scope -p239

다대일과 다대다 모델을 구현하는 시스템에서는 스레드 라이브러리는 사용자 수준 스레드를 가용한 LWP 상에서 스케줄한다. 이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스-경쟁-범위(process-contention scope, PCS)로 알려져 있다.

CPU상에 어느 커널 스레드를 스케줄 할 것인지 결정하기 위해서 커널은 시스템-경쟁-범위(system-contention scope, SCS)를 사용한다.

Windows와 Linux 같은 일대일 모델을 사용하는 시스템은 오직 SCS만을 사용하여 스케줄한다.

 

전형적으로 PCS는 우선순위에 따라 행해진다. 즉 스케줄러는 가장 높은 우선순위를 가진 실행 가능한 프로세스를 선택한다.

 

5.4.2 Pthread 스케줄링 -p240

Pthreads는 다음과 같은 범위의 값을 구분한다.

• PTHREAD SCOPE PROCESS 는 PCS 스케줄링을 사용하여 스레드를 스케줄한다.

• PTHREAD SCOPE SYSTEM 는 SCS 스케줄링을 사용하여 스레드를 스케줄한다.

 

5.5 다중 처리기 스케줄링 Multiple-Processor Scheduling -p242

다중 처리기라는 용어는 여러 개의 물리적 프로세서를 제공하는 시스템을 말하며, 각 프로세서에는 하나의 단일 코어 CPU가 포함되어 있다.

다중 처리기는 다음 시스템 아키텍처들에 사용할 수 있다.

• 다중 코어 CPU
• 다중 스레드 코어
• NUMA 시스템
• 이기종 다중처리

5.5.1 다중처리기 스케줄리에 대한 접근 방법 -p242

비대칭 다중 처리기 (asymmetric multiprocessing )는 오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다. 이 접근의 단점은 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 것이다.

다중 처리기를 지원하기 위한 표준 접근 방식은 대칭 다중 처리(symmetric multi-processing, SMP)이며 각 프로세서는 스스로 스케줄링 할 수 있다.

 

스케줄 대상이 되는 스레드를 관리하기 위한 두 가지 전략

• 모든 스레드가 공통 준비 큐에 있을 수 있다.
• 각 프로세서는 자신만의 스레드 큐를 가질 수 있다.

준비 큐의 구조

 

 

5.5.2 다중 코어 프로세서 Multicore Processor -p243

현대 컴퓨터 하드웨어는 동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착하여 다중 코어 프로세서 (multicore processor) 가 된다.

 

프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 소비하는 메모리 스톨(memory stall)이라고 하는 이 상황은 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 주로 발생한다. 이러한 상황을 해결하기 위해 최근의 많은 하드웨어 설계는 다중 스레드 처리 코어를 구현하였다. 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있다.

 

운영체제 관점에서 각 하드웨어 스레드는 명령어 포인터 및 레지스터 집합과 같은 구조적 상태를 유지하므로 소프트웨어 스레드를 실행할 수 있는 논리적 CPU로 보인다. 칩 다중 스레딩 (chip multi-threading, CMT) 로 알려져있다.

 

5.5.3 부하 균등화 Load Balacing - p247

부하 균등화(load balacing)는 SMP 시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 시도한다. 

 

부하균등화는 통상 각 처리기가 실행할 스레드를 위한 자기 자신만의 준비 큐를 가지고 있는 시스템에서만 필요한 기능이라는 것을 주의해야 한다. 공통의 실행 큐만 있는 시스템에서는 한 처리기가 쉬게 되면 곧바로 공통큐에서 새로운 프로세스를 선택하여  실행하기 때문에 부하 균등화는 필요하지 않다.

 

5.5.4 처리기 선호도 Processor Affinity-p247

스레드에 의해 가장 최근에 접근된 데이터가 그 처리기의 캐시를 채우게 된다. 그 결과 스레드에 의한 잇따른 메모리 접근은 캐시 메모리에서 만족한다. (warm cache 라고 함). 이제 스레드가 다른 처리기로 이주한다면 어떤 일이 일어날까. 첫 번째 프로세서의 캐시 메모리의 내용은 무효화 되어야 하며 두번째 프로세서의 캐시는 다시 채워져야 한다. 

 

캐시 무효화 및 다시 채우는 비용이 많이 들기 때문에 SMP를 지원하는 대부분의 운영체제는 스레드를 한 프로세서에서 다른 프로세서로 이주시키지 않고 대신 같은 프로세서에서 계속 실행시키면서 warm cache 를 이용하려고 한다. 이를 프로세서 선호도 라고 한다.

 

시스템의 메인 메모리 아키텍처는 프로세서 선호도 문제에도 영향을 줄 수 있다. 시스템 연결망을 통해 NUMA 시스템의 모든 CPU가 하나의 물리적 주소 공간을 공유할 수 있지만 CPU는 다른 CPU의 로컬 메모리 보다 자신의 로컬 메모리에 더 빠르게 액세스 할 수 있다.

 

흥미롭게도 부하 균등은 종종 프로세서 선호도의 이점을 상쇄한다. 즉, 동일한 프로세서에서 스레드를 계쏙 실행하면 스레드가 해당 프로세서의 캐시 메모리에 있는 데이터를 활용할 수 있다는 이점이 있다. 스레드를 한 프로세서에서 다른 프로세서로 이동히야 부하를 균등하게 조정하면 이러한 이점이 사라진다.

 

5.5.5 이기종 다중 처리 Heterogeneous Multiprocessing -p249

모바일 시스템에는 현재 다중 코어 아키텍처가 채택되어 있지만 일부 시스템은 동일한 명령어 집합을 실행하지만 전력 소비를 유휴 수준으로 조정하는 기능을 포함하여 클록 속도 및 전력 관리 측면에서 차이가 나는 코어를 사용하여 설계되었다. 이러한 시스템을 이기종 다중 처리 (heterogeneous multiprocessing, HMP)라고 한다.