[공룡책] Ch 5. CPU 스케줄링

---

이 글은 공룡책을 읽고 정리한 글입니다.

---

 

 

 

0. 소개

---

CPU 스케줄링은 다중 프로그램 운영체제의 기본이다. CPU 스케줄링을 통해 보다 더 효율적으로 CPU를 사용할 수 있다.

그래서 이 장에서는 스케줄링 개념과 여러 스케줄링 알고리즘을 소개한다. 그리고 일반적인 스케줄링을 논의하는 경우에는 프로세스 스케줄링이라는 단어를 사용하고, 스레드에 국한된 개념에는 스레드 스케줄링이라는 단어를 사용한다.

---

 

 

 

1. 기본 개념

---

코어가 하나인 시스템에서는 한순간에 오직 하나의 프로세스만이 실행될 수 있다. 나머지 프로세스는 CPU의 코어가 가용(available) 상태가 되어 다시 스케줄 될 수 있을 때까지 기다려야 한다. 다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행중인 프로세스를 가지게 하는데 있다.

---

CPU 버스트, I/O 버스트 반복

1) CPU - I/O Burst Cycle

프로세스 실행은 CPU 버스트와 I/O 버스트가 계속 반복된다. 

---

2) CPU 스케줄러

CPU가 유후 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중에서 하나를 선택해 실행해야 한다. 선택 절차는 CPU 스케줄러에 의해 수행된다. 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다. 그리고 준비 큐는 반드시 선입선출(FIFO) 방식의 큐가 아니어도 되는 것에 유의한다. (큐에 있는 레코드들은 PCB들이다)

---

3) 선점 및 비선점 스케줄링

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

 

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

2. 프로세스가 실행 상태에서 준비 상태로 전환될 때 (ex. 인터럽트 발생)

3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 떄(ex. I/O 종료시)

4. 프로세스가 종료할 때

 

상황 1과 4의 경우엔 스케줄링 면에서는 실행을 위해 새로운 프로세스를 반드시 선택해야 하지만, 상황 2와 3의 경우에는 선택의 여지가 있다.

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

 

비선점 스케줄링에서는 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하거나, 대기 상태로 전환해 CPU를 방출할 때까지 점유한다. 하지만 모든 최신 운영체제에서는 선점 스케줄링 알고리즘을 사용한다. 선점 스케줄링은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있다.

---

디스패처 지연

4) 디스패처 (Dispatcher)

디스패처는 CPU 스케줄링 기능에 포함된 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이다. 디스패처는 아래와 같은 작업을 한다.

 

- 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일

- 사용자 모드로 전환하는 일

- 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

 

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

---

 

 

 

2. 스케줄링 기준

---

CPU 스케줄링 알고리즘은 서로 다른 특성을 가지고 있기 때문에, CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이 제시되었다.

 

1. CPU 이용률

CPU를 최대한 바쁘게 유지해야 한다. 실제 시스템에서는 CPU 이용률을 40% ~ 90%까지 사용할 수 있게 한다.

 

2. 처리량

처리량은 단위 시간당 완료된 프로세스의 개수로 구할 수 있다.

 

3. 총처리 시간

프로세스의 입장에서 생각하면, 프로세스를 실행하는데 소요되는 시간을 중요하게 생각할 것이다.

총처리 시간은 준비 큐에서 대기한 시간, CPU에서 실행하는 시간, I/O 시간의 합으로 구한다.

 

4. 대기 시간

CPU 스케줄링 알고리즘은 프로세스가 준비 큐에서 대기하는 시간의 양에만 영향을 미치기 때문에 준비 큐에 대기하면서 보낸 시간의 합으로 대기 시간을 구한다.

 

5. 응답 시간

대화식 시스템에서는 총처리 시간을 기준으로 판단하는 것이 최선의 판단이 아니기 때문에 요구를 제출한 후 응답이 나올 때까지의 시간을 구하여 기준을 정한다. 이때 응답 시간은 응답이 시작되는 때를 말하는 것이지 응답을 출력하는데 걸리는 시간을 구하는 것이 아니다.

 

이때 CPU 이용률과 처리량을 최대화하고, 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 좋다. 하지만 현실에서는 평균 측정 시간을 최적화하려고 한다. 

---

 

 

 

3. 스케줄링 알고리즘

---

CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정하는 문제를 다룬다. 그리고 여기에 여러 가지 다른 스케줄링 알고리즘들이 있으므로 각각의 알고리즘에 대해 설명한다.

---

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

가장 간단한 CPU 스케줄링 알고리즘이다. 이것은 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 것이다. 이것은 선입선출 큐로 쉽게 관리할 수 있다. 하지만 이 스케줄링 알고리즘은 평균 대기 시간이 굉장히 길어질 수 있고, 선입 선처리는 평균 대기 시간이 일반적으로 최소가 아니게 된다.

 

ex) 프로세스 P1 - 버스트 시간 24, 프로세스 P2 - 버스트 시간 3, 프로세스 P3 - 버스트 시간 3인 경우

이 경우 P1의 대기 시간은 0ms이고, P2의 대기 시간은 24ms, P3의 대기 시간은 27ms이다. 그러므로 평균 대기 시간은 17ms이다.

평균 대기 시작이 제일 짧은 경우는 위 사진으로 P1의 대기 시간은 6ms, P2의 대기 시간은 0ms, P3의 대기 시간은 3ms로 평균 대기 시간은 3ms이다. 

 

모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라고 한다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 나온다.

---

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

이 스케줄링은 버스트 길이가 작은 프로세스부터 CPU를 먼저 할당 받는 것이다. 이때 버스트 길이가 같다면 선입 선처리 스케줄링으로 순서를 정한다. 

SJF 알고리즘은 최소의 평균 대기 시간을 가진다는 점에서 최적임을 증명할 수 있지만, 다음 CPU 버스트의 길이를 알 수 있는 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현이 불가능하다.

그래서 SJF 스케줄링과 근사한 방법을 사용하는데, 다음 CPU 버스트의 길이가 이전의 버스트와 길이가 비슷하다고 생각하여 다음 CPU 버스트 길이의 근삿값을 구해 유추하는 것이다. 

---

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

라운드 로빈 스케줄링은 선입 선처리 스케줄링과 유사하지만, 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다. 이때 시간 할당량(time quantum), 타임슬라이스(time slice)라고 하는 작은 단위의 시간을 정의한다.(10ms ~ 100ms) 준비 큐는 원형 큐로 동작하여 CPU 스케줄러는 준비 큐를 돌면서 한 번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다.

 

라운드 로빈 스케줄링을 구현하려면 준비 큐를 선입선출 큐로 만들고, CPU 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택한다. 그다음 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머를 설정한 후, 프로세스를 디스패치 한다.

이러면 아래 중 하나의 상황이 발생하게 된다.

 

1. 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작을 경우

→ 프로세스 자신이 CPU를 방출한다.

2. 현재 실행중인 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 긴 경우

→ 운영체제에 인터럽트를 발생, 문맥 교환이 일어나고 해당 프로세스는 준비 큐의 꼬리에 넣어진다.

 

 ex) 프로세스 P1 - 버스트 시간 24, 프로세스 P2 - 버스트 시간 3, 프로세스 P3 - 버스트 시간 3인 경우

이때 시간 할당량이 4ms라면 프로세스 P1은 우선 4ms를 사용하고, 준비 큐의 꼬리에 넣어진다. 이후 프로세스 P2에 CPU를 할당하는데, 시간 할당량보다 작으니 3ms에서 P2가 CPU를 방출시킨다. P3도 마찬가지로 3ms에서 CPU를 방출하고 P1이 들어오면 4ms를 수행하고 다시 준비 큐에 넣는 작업을 반복한다.

평균 대기 시간은 P1은 6ms이고, P2는 4ms, P3은 7ms로 평균 대기 시간은 5.66ms가 될 수 있다.

 

RR 알고리즘의 성능은  시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적으로 시간 할당량이 매우 크다면 선입 선처리 스케줄링과 같다. 이와 반대로 시간 할당량이 매우 작다면 문맥 교환이 많이 일어난다.

그래서 시간 할당량은 문맥 교환 시간과 비교하여 더 크게 만들어준다.

---

4) 우선순위 스케줄링 (Priority)

SJF 알고리즘은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우이다.

여기서 우선순위는 여러가지 기준으로 측정될 수 있으며, 이때 같은 우선순위를 가지면 선입 선처리로 순서를 정한다.

 

우선순위 스케줄링의 문제는 무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation) 부르는 문제이다.

실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리다가 봉쇄된 것으로 간주한다.

이때 우선순위가 낮은 프로세스는 CPU를 무한히 대기하는 경우가 발생하여 무한 봉쇄가 될 수 있다. 이것은 우선순위가 낮은 프로세스가 CPU를 얻지 못하므로 기아 상태라고 말할 수도 있다.

 

이것에 대한 해결 방법은 노화(aging)이다. 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.

다른 방법은 라운드 로빈과 우선순위 스케줄링을 결합하는 방법이다. 일단 우선순위가 큰 것부터 큐에 쌓아두고 라운드 로빈처럼 시간 할당량만큼 실행하는 것이다.

---

5) 다단계 큐 스케줄링 (Multilevel Queue)

다단계 큐는 우선순위마다 큐를 가지고 있는 것이다. 이것은 우선순위 알고리즘이 라운드 로빈 알고리즘과 결합한 경우에도 효과적이다.

다단계 큐는 프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해서도 사용된다. 예를 들어 흔히 포그라운드(대화형) 프로세스와 백그라운드(배치) 프로세스로 구분한다. 포그라운드 프로세스는 라우드 로빈 알고리즘을 사용하며, 포그라운드 프로세스는 선입 선처리 알고리즘을 사용한다.

그리고 큐와 큐 사이에 스케줄링도 존재해야 하며, 일반적으로 아래와 같은 우선 순위를 가지게 된다.

---

6) 다단계 피드백 큐 스케줄링

다단계 큐 스케줄링 알고리즘은 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당되어 다른 큐로 이동하지 않는다. 이런 방식은 스케줄링 오버헤드가 낮다는 장점이 있지만, 융통성이 적다.

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

아이디어는 프로세스들을 CPU 버스트 성격에 따라서 구분하는 것이다. 어떤 프로세스가 CPU를 너무 길게 사용하면 낮은 우선순위의 큐로 이동하고, CPU를 짧게 사용하는 I/O 중심의 프로세스와 대화형 프로세스는 높은 우선 순위 큐에 넣는 것이다. 

---

 

 

 

4. 다중 처리기 스케줄링

---

여러 개의 CPU가 사용 가능하면, 여러 스레드가 병렬로 실행될 수 있으니 부하 공유(load sharing)가 가능해진다. (부하를 분산 처리)

다중 처리기는 여러 개의 물리적 프로세서를 제공하는 시스템을 말하며, 각 프로세서에는 하나의 단일 코어 CPU가 포함되어 있다. 다중 처리기 스케줄링 문제는 더욱 복잡해진다는 단점이 존재한다.

---

1) 다중 처리기 스케줄링에 대한 접근 방법

다중 처리기 시스템의 CPU 스케줄링에 관한 한 가지 해결 방법은 마스터 서버라는 하나의 처리기가 모든 스케줄링 결정, I/O 처리, 다른 시스템의 활동을 취급하는 것이다. 이러면 나머지 처리기는 사용자 코드만을 수행한다. 

이것을 비대칭 다중 처리(asymmetric multiprocessing)이라 하는데, 오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다.

하지만 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 단점이 있다.

 

다중 처리기를 지원하는 표준 접근 방식은 대칭 다중 처리(SMP, symmetric multiprocessing)이며 각 프로세스는 스스로 스케줄링을 할 수 있는 방식이다. 이때 각 프로세스의 스케줄러는 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링을 진행한다.

---

2) 다중 코어 프로세서

현대 컴퓨터 하드웨어는 동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착하여 다중 코어 프로세서(multicore processor)가 된다. 이때 각 코어는 구조적인 상태를 유지하고 있어서 운영체제에서는 개별적인 논리적 CPU처럼 보이게 된다.

 

메모리 스톨

다중 코어 프로세서는 스케줄링 문제를 복잡하게 하는데, 프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비하는 메모리 스톨(memory stall)이라는 상황이 발생한다.

메모리 스톨은 최신 프로세서가 메모리보다 빠르게 작동하기 때문에 주로 발생하고, 캐시 미스로 인해 메모리 스톨이 발생할 수도 있다.

 

다중 스레딩 다중 코어 시스템

메모리 스톨을 해결하기 위해 하나의 코어에 2개 이상의 하드웨어 스레드가 할당된다. 이러면 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면, 코어가 다른 스레드로 전환할 수 있다.

위 사진에서 스레드 0이 메모리 스톨 사이클일 때, 코어가 스레드 1로 전환하여 계산 사이클을 진행하는 것을 알 수 있다. 이후 스레드 1이 메모리 스톨 사이클이면 스레드 0으로 전환하여 계산하는 것을 반복한다.

---

3) 부하 균등화 (Load Balancing)

대칭 다중 처리(SMP) 시스템에서 처리기가 하나 이상이라는 것을 최대한 활용하려면, 부하를 모든 처리기에 균등하게 배분하는 것이 중요하다. 그래서 부하 균등화는 SMP 시스템의 모든 처리기 사이에 부하가 균등하게 배분되도록 시도한다.

이때 부하 균등화는 각 CPU가 실행할 스레드를 위한 자기 자신만의 큐를 가지고 있는 시스템에서만 필요한 기능임을 주의해야 한다.

 

부하 균등화를 위해서는 push 이주와 pull 이주 방식의 접근법이 있다.

 

push 이주는 특정 태스크가 주기적으로 각 CPU의 부하를 검사하고, 만일 불균형 상태로 밝혀지면 과부하인 CPU에서 쉬고 있거나 덜 바쁜 CPU로 스레드를 이동시킴으로써 부하를 분배한다.

pull 이주는 쉬고 있는 CPU가 바쁜 CPU를 기다리고 있는 프로세스를 pull할 때 일어난다.

---

 

 

 

5. 실시간 CPU 스케줄링

---

실시간 CPU 스케줄링은 연성 실시간 시스템(soft realtime system)과 경성 실시간 시스템(hard readtime system)으로 구분한다.

 

연성 실시간 시스템은 중요한 실시간 프로세스가 스케줄 되는 시점에 관해 아무런 보장을 하지 않는다. 그리고 오직 중요 프로세스가 중요하지 않은 프로세스에 비해 우선권을 가진다는 것만 보장한다.

 

경성 실시간 시스템은 더 엄격한 요구조건으로 태스크는 반드시 마감시간까지 서비스를 받아야 하며, 마감시간이 지난 이후에 서비스를 받는 것은 서비스를 전혀 받지 않는 것과 동일한 결과를 낳는다.

---

1) 지연시간 최소화

시스템은 일반적으로 실시간으로 발생하는 이벤트를 기다린다. 이벤트가 발생하면 시스템은 가능한 빨리 응답을 하고, 그에 맞는 동작을 수행한다. 이때 이벤트 지연시간은 이벤트가 발생하여 그에 맞는 서비스가 수행될 때까지의 시간을 말한다.

 

아래 두 가지의 유형의 지연시간이 실시간 시스템의 성능을 좌우한다.

1. 인터럽트 지연시간 (interrupt latency)

2. 디스패치 지연시간 (dispatch latency)

 

인터럽트 지연시간

인터럽트 지연시간은 CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기까지의 시간을 말한다. 인터럽트가 발생하면 운영체제는 우선 수행중인 명령어를 완수하고, 발생한 인터럽트의 종류를 결정한다. 그리고 해당되는 인터럽트 서비스 루틴(ISR)을 사용하여 인터럽트를 처리하기 전에 현재 수행 중인 프로세스의 상태를 저장해 놓아야만 한다. 이런 작업을 모두 수행하는게 인터럽트 지연시간이다.

 

디스패치 지연시간

 

디스패치 지연시간은 스케줄링 디스패처가 하나의 프로세스를 블록시키고, 다른 프로세스를 시작하는데까지 걸리는 시간을 말한다. CPU를 즉시 사용해야 하는 실시간 태스크가 있다면, 운영체제는 이 지연 시간을 최소화해야 한다. 이때 디스패치 지연시간을 최소화하는 가장 효과적인 방법은 선점형 커널이다.

 

디스패치 지연시간은 충돌과 디스패치로 이루어져 있다. 이때 충돌은 아래 두가지 요소로 구성되어 있다.

1. 커널에서 동작하는 프로세스에 대한 선점

2. 높은 우선순위의 프로세스가 필요한 자원을 낮은 우선순위 프로세스 자원이 방출

---