공룡책과 함께 OS를 배워보자 5일차 - CPU 스케줄링
본 포스트는 공룡책이라 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 을 바탕으로 작성하였습니다.
Ch 5. CPU Scheduling
CPU 스케줄링은 다중 프로그램 운영체제의 기본이다. 운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만든다.
이번 장에서는 기본 스케줄링 개념과 여러 스케줄링 알고리즘을 소개한다.
5.1 기본 개념들
1) 프로세스 실행은 CPU 버스트와 I/O 버스트의 반복이다.
2) CPU 스케줄러
CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중 하나를 선택해 실행해야 한다.
선택 절차는 CPU 스케줄러에 의해 수행된다. (주의점은 선입선출 방식의 큐가 아니어도 된다는 점이다.)
3) 선점 및 비선점 스케줄링
CPU 스케줄링 결정은 아래 4가지 상황에서 발생할 수 있다.
- 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (ex. I/O 요청이나 자식 프로세스가 종료되기를 기다리기 위해 wait()를 호출할 때)
- 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (ex. 인터럽트가 발생할 때)
- 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (ex. I/O 종료 시)
- 프로세스가 종료할 때
1,4번의 경우 스케줄링 면에서 선택의 여지가 없다. 실행을 위해 새로운 프로세스가 반드시 선택되어야 한다.
하지만 2,3번의 경우 선택의 여지가 있다.
만약 1,4번에서만 스케줄링이 발생할 경우, 비선점 또는 협조적이라고 한다.
그렇지 않으면, 그것은 선점이라고 한다.
비선점 스케줄링에서는 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때까지 점유한다. 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.
선점 스케줄링은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있다.
4) 디스패처
디스패처는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며 다음과 같은 작업을 포함한다.
- 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
- 사용자 모드로 전환하는 일
- 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일
디스패처는 모든 프로세스의 문맥 교환 시 호출된다.
디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 디스패치 지연(dispatch latency)이라고 한다.
5.2 스케줄링 기준 (Scheduling Criteria)
서로 다른 CPU 스케줄링 알고리즘들은 다른 특성을 가진다. 이는 여러 기준에 따라 달라지는데, 사용되는 기준은 다음과 같다.
1) CPU 이용률(utilization)
앞서 계속 언급했듯, CPU를 최대한 바쁘게 유지시키는 것은 중요한 기준이 된다.
2) 처리량(throughput)
CPU 작업량 측정의 한 방법으로, 단위 시간당 완료된 프로세스의 개수를 의미한다.
3) 총 처리 시간(turnaround time)
프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라고 한다.
총처리 시간은 (1) 준비 큐에서 대기한 시간, (2) CPU에서 실행하는 시간, (3) I/O 시간을 합한 시간이다.
4) 대기 시간(waiting time)
대기 시간은 준비 큐에서 대기하면서 보낸 시간의 합이다.
5) 응답 시간(response time)
응답이 시작되는 데까지 걸리는 시간이다. 즉, 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간을 말한다.
5.3 스케줄링 알고리즘
CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정하는 문제를 다룬다.
* 선입 선처리 스케줄링 (First-Come First-Served, FCFS)
가장 간단한 CPU 스케줄링 알고리즘으로, CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다.
간단히 선입선출 큐로 관리할 수 있다.
단점은 선입 선출 과정에서 프로세스의 평균 대기 시간은 상당히 길어질 수 있다는 점이다.
다음과 같은 프로세스들이 대기 큐에 있다고 가정해보자.
| 프로세스 | 버스트 시간 |
| P1 | 24 ms |
| P2 | 3 |
| P3 | 3 |
만약 프로세스들이 P1 ~ P3 순으로 선입 선출 방식이 적용된다면, 각 프로세스의 대기 시간은 다음과 같다.
P1 = 0 ms, P2 = 24 ms, P3 = 27 ms -> 평균 17 ms
그러나 프로세스들이 P2, P3, P1 순으로 도착하면, 각 프로세스들의 대기 시간은 다음과 같다.
P1 = 6, P2 = 0, P3 = 3 -> 평균 3 ms
따라서 선입 선처리 스케줄링의 평균대기 시간은 일반적으로 최소가 아니다.
호위 효과(convoy effect)
모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과라고 한다.
이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때 이득이다.
* 최단 작업 우선 스케줄링
우선순위 큐(min heap)를 사용하는 것 같은 개념이다.
즉, 바로 위의 "호위 효과"를 최소화하기 위해 가장 짧은 시간을 갖는 프로세스 우선으로 서비스한다는 의미이다.
그러나 CPU 버스트의 길이를 알 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현할 수 없다.
다만 한 가지 접근 방식은 그 값을 예측할 수 있다는 것이다. 예를 들어 P1, P2가 순서대로 있고 P1의 버스트 길이를 안다면, P2의 버스트가 P1 버스트의 길이와 비슷하다고 기대하는 것이다.
* 라운드 로빈 스케줄링
라운드 로빈 스케줄링 알고리즘은 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다.
여기서는, 시간 할당량(time quan-tum) 또는 타임슬라이스라고 하는 작은 단위의 시간을 정의한다.
기본 베이스는 준비 큐가 선입선출 큐로 동작하게 만든다. 그 후 CPU 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머를 설정한 후, 프로세스를 디스패치 한다.
이때 두 가지 상황이 발생할 수 있다.
- 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작다 -> 프로세스 스스로 CPU를 방출하게 되고, 다음 프로세스로 이동
- 한 번의 시간 할당량보다 긴 경우 -> 인터럽트가 발생하고, 실행하던 프로세스는 준비 큐의 꼬리에 넣어진다.
다음과 같은 프로세스들이 대기 큐에 있다고 가정해보자.
| 프로세스 | 버스트 시간 |
| P1 | 24 ms |
| P2 | 3 |
| P3 | 3 |
만약 시간 할당량을 4 ms로 한다면, P1은 처음 4 ms 사용 후 나머지 20 ms는 맨 뒤로 가고, P2, P3는 바로 실행 후 종료한다.
라운드 로빈 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다.
극단적인 경우, 시간 할당량이 매우 크면, 선입 선처리 정책과 다를 바 없다.
반대로 시간 할당량이 매우 적다면, 매우 많은 문맥 교환을 야기할 수 있다.
따라서 일반적으로 시간 할당량이 문맥 교환 시간과 비교해 더 크도록 설정한다.
* 우선순위 스케줄링
이번에 설명할 우선순위는 앞서 설명한 최단 작업 스케줄링을 포함하는 개념이다.
여러 가지 요소로 우선순위를 측정할 수 있는데, 예를 들어 시간제한, 메모리 요구, 열린 파일의 수 등이 우선순위 계산에 사용된다.
또한 외부적으로 가격, 후원 부서, 정치적 요인도 우선순위가 될 수 있다.
우선순위 스케줄링의 주요 문제는 무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)이다.
이는 우선순위 스케줄링 알고리즘 상 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우를 말한다.
이런 문제점의 해결 방안은 노화(aging)인데, 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
* 다단계 큐 스케줄링
다단계 큐 스케줄링 알고리즘은 우선순위마다 별도의 큐를 두는 것이다.
각 큐들은 자신의 스케줄링 알고리즘을 가질 수 있는데, 예를 들어 백그라운드 큐는 선입선출, 포그라운드는 라운드 로빈 알고리즘을 사용하는 경우이다.
또한, 큐와 큐 사이에도 스케줄링이 반드시 있어야 하는데, 보통의 우선순위는 실시간 -> 시스템 -> 대화형 -> 배치 순서이다.
* 다단계 피드백 큐 스케줄링
다단계 피드백 큐 스케줄링 알고리즘은 프로세스가 큐들 사이를 이동하는 것을 허용한다.
만약 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동하는 식이다.
마찬가지로 너무 오래 기다린 프로세스들은 높은 우선순위의 큐로 이동할 수도 있다.
5.4 다중 처리기 스케줄링 (Multi Processor Scheduling)
만약 여러 개의 CPU가 사용 가능하다면, 여러 스레드가 병렬로 실행될 수 있으므로 부하 공유(load sharing)가 가능해진다.
이번에는 다중 처리기 스케줄링 관련 문제에 관해 다룬다.
* 다중 처리기 스케줄링에 대한 접근 방법
다중 처리기 시스템의 CPU 스케줄링에 관한 한 가지 해결 방법은 마스터 서버(master server)라는 하나의 프로세서가 모든 스케줄링 결정과 I/O 처리, 다른 시스템의 활동을 취급하게 하는 것이다.
이러한 비대칭 다중 처리(asymmetric multiprocessing)는 오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다. 반면 단점은 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 것이다.
표준 접근 방식은 대칭 다중 처리(symmetric multiprocessing)이다. 이때 각 프로세서는 스스로 스케줄링할 수 있다.
각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행된다.
* 다중 코어 프로세서 (Multicore Processors)
현대 컴퓨터 하드웨어는 동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착하여 다중 코어 프로세서가 된다.
각 코어는 운영체제 입장에서는 개별적인 논리적 CPU처럼 보이게 된다.
이 프로세서는 스케줄링 문제를 더 복잡하게 하는데, 바로 메모리 스톨(memory stall) 현상이 발생하기 때문이다.
메모리 스톨은 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 주로 발생한다.
이러한 상황을 해결하기 위해서 하나의 코어에 2개 이상의 하드웨어 스레드가 할당된다.
이렇게 하면 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있다.
* 부하 균등화 (Load Balancing)
여러 개의 프로세서를 최대한 활용하려면, 부하를 모든 프로세서에 균등하게 배분하는 것이 매우 중요하다.
부하 균등화는 통상 각 프로세서가 실행할 스레드를 위한 자기 자신만의 준비 큐를 가지고 있음을 가정한다.
부하 균등화를 위해서는 push 이주와 pull 이주 두 가지 접근이 있다.
push 이주는 특정 태스크가 주기적으로 각 프로세서의 부하를 검사하고, 만일 불균형 상태로 밝혀지면 과부하인 처리기에서 쉬고 있거나 덜 바쁜 처리기로 스레드를 이동시킴으로써 부하를 분배한다.
pull 이주는 쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 pull 할 때 일어난다.
균등 부하에는 두 가지 관점이 존재하는데, 한 가지는 "모든 큐에 대략 같은 수의 스레드가 있어야 할 것"과 나머지 하나는 "모든 큐에 스레드 우선순위를 균등하게 분배해야 한다는 것"이다.
5.5 실시간 CPU 스케줄링
실시간 CPU 스케줄링은 일반적으로 연성(soft) 실시간 시스템과 경성(hard) 실시간 시스템으로 구분한다.
(밑에서는 책의 "연성", "경성" 표현이 너무.. 와닿지 않아 영문으로 표기하겠다.)
soft real-time system은 실시간 프로세스가 스케줄 되는 시점에 관해 아무런 보장을 하지 않는다. 오직 중요한 프로세스가 그렇지 않은 프로세스들에 비해 우선권을 가진다는 것만 보장한다.
hard real-time system은 반드시 마감시간까지 서비스를 받아야 하며, 그렇지 않으면 서비스를 전혀 받지 않은 것과 동일한 결과를 낳는다.
* 지연시간 최소화
시스템은 일반적으로 실시간으로 발생하는 이벤트를 기다린다.
이벤트가 발생하면, 시스템은 가능한 한 빨리 그에 응답을 하고 그에 맞는 동작을 수행하여야 한다. 이벤트 지연시간은 이벤트가 발생해서 그에 맞는 서비스가 수행될 때까지의 시간을 말한다.
이벤트 지연에는 두 가지 지연시간이 실시간 시스템의 성능을 좌우한다.
1) 인터럽트 지연시간
인터럽트 지연시간은 CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기까지의 시간을 말한다.
인터럽트가 발생하면 운영체제는 우선 수행 중인 명령어를 완수하고 발생한 인터럽트의 종류를 결정한다.
해당 인터럽트 서비스 루틴(ISR)을 사용하여 인터럽트를 처리하기 전에 현재 수행 중인 프로세스의 상태를 저장해 놓아야만 한다.
-> 이러한 작업을 모두 수행하는 데 걸리는 시간이 인터럽트 지연시간이다.
2) 디스패치 지연시간
디스패치 지연시간은 스케줄링 디스패처가 하나의 프로세스를 블록 시키고 다른 프로세스를 시작하는 데까지 걸리는 시간을 말한다.
디스패치 지연시간을 최소화하는 가장 효과적인 방법은 선점형 커널이다.
