[운영체제 공룡책] CPU 스케줄링
Posted: Updated:
운영체제 스터디를 하며 ‘운영체제 공룡책’ 교재를 정리한 글입니다.
CPU 스케줄링
다중 프로그래밍에서 다수의 프로세스를 메모리 내에 유지하여 어떠한 프로세스가 대기해야 할 경우, 운영체제가 CPU를 회수하여 다른 프로세스에 할당하는 패턴을 반복한다.
CPU 이용률을 극대화하기 위해 항상 실행중인 프로세스를 가지게 하도록 스케줄링하는 것이 핵심이다.
CPU-I/O 버스트 사이클
프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.
I/O 중심 프로그램은 짧은 CPU 버스트를 많이 가지고, CPU 지향 프로그램은 다수의 긴 CPU 버스트를 가질 수 있다.
CPU 스케줄러
CPU가 유휴 상태가 되면 운영체제는 준비 큐의 프로세스 중 하나를 선택해 실행한다.
이때, CPU 스케줄러가 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 하나를 선택해 CPU를 할당한다.
선점 및 비선점 스케줄링
비선점(nonpreemptive) 스케줄링
한 프로세스가 I/O 요청 또는 자식 프로세스를 기다리기 위해 wait()을 호출하여 실행 상태에서 대기 상태로 전환될 때, 종료할 때만 스케줄링이 발생할 경우 비선점 또는 협조적(cooperative)이라고 한다.
이 경우 CPU에 할당될 경우 종료되거나 CPU를 방출할 때까지 점유한다.
선점(preemptive) 스케줄링
한 프로세스가 I/O 요청 또는 자식 프로세스를 기다리기 위해 wait()을 호출하여 실행 상태에서 대기 상태로 전환될 때, 종료할 때 뿐 아니라, 인터럽트 발생 등으로 인해 실행 상태에서 준비 완료 상태로 전환될 때, I/O 종료 등으로 인해 대기 상태에서 준비 완료 상태로 전환될 때에도 스케줄링이 발생하면 선점이라고 한다.
Windows, macOS, Linux 및 UNIX 포함 거의 모든 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.
두 프로세스가 자료를 공유하는 경우 경쟁 조건을 초래할 수 있으며, 커널이 동일한 구조를 읽거나 변경할 경우 문제가 생길 수 있다.
디스패처(dispathcer)
CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이다.
한 프로세스에서 다른 프로세스로 문맥을 교환하거나, 사용자 모드로 전환하는 일을 한다.
또한, 프로그램 재시작을 위해 사용자 프로그램의 적절한 위치로 이동하는 일을 한다.
모든 프로세스의 문맥 교환 시 호출되므로, 가능한 한 빨리 수행되어야 한다.
디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데 소요되는 시간을 디스패치 지연(dispatch latency)이라고 한다.
스케줄링 기준
- CPU 이용률(utiliation)
- 처리량(throughput): 단위 시간당 완료된 프로세스 개수
- 총처리 시간(turnaround time): 준비 큐에서 대기한 시간, CPU에서 실행한 시간, I/O 시간을 합한 시간
- 대기 시간(waiting time): 준비 큐에서 대기하면서 보낸 시간의 합
- 응답 시간(reponse time): 응답이 시작되는 데까지 걸리는 시간
CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.
스케줄링 알고리즘
선입 선처리(FCFS) 스케줄링
CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다.
선입선출(FIFO) 큐로 쉽게 관리할 수 있으며, 프로세스가 준비 큐에 진입하면 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결한다.
모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하길 기다리는 것을 호위 효과(convoy effect)라고 한다.
선입 선처리 스케줄링 알고리즘은 비선점형이므로, 한 프로세스가 지나치게 오랫동안 CPU를 점유하면 손해가 클 수 있다.
최단 작업 우선(shortest-job-first, SJF) 스케줄링
CPU가 사용 가능해지면 가장 작은 다음 CPU 버스트를 가진 프로세스에 할당한다.
두 프로세스가 동일한 길이의 다음 CPU 버스트를 가지면, 순위를 정하기 위해 선입 선처리 스케줄링을 적용한다.
다음 CPU 버스트의 길이를 알 수는 없으므로 CPU 스케줄링 수준에서 구현할 수는 없지만, 다음 CPU 버스트 길이의 근사값을 계산해 가장 짧은 예상 CPU 버스트를 가진 프로세스를 선택한다.
비선점형 SJF 알고리즘은 새로운 프로세스가 준비 큐에 도착하더라도 현재 실행중인 프로세스가 CPU 버스트를 끝낼 수 있도록 한다.
선점형 SJF 알고리즘은 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다 짧은 CPU 버스트를 가지면 선점할 것이다.
선점형 SJF 알고리즘은 최소 잔여 시간 우선(shortest remaining time first) 스케줄링이라고 불린다.
라운드 로빈(Round-Robin) 스케줄링
라운드 로빈(RR) 스케줄링은 선입 선처리 스케줄링과 유사하지만 선점이 추가되었다.
시간 할당량(time quantum) 혹은 타임 슬라이스(time slice) 라고 하는 단위 시간을 정의하고, CPU 스케줄러는 준비 큐를 돌면서 한 번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다.
새로운 프로세스는 준비 큐의 꼬리에 추가되고, CPU는 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머를 설정하고 프로세스를 디스패치한다.
프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작다면, CPU를 자발적으로 방출하고 다음 프로세스를 진행한다.
CPU 버스트가 시간 할당량보다 길다면 인터럽트가 발생하여 문맥 교환이 일어나고, 실행하던 프로세스는 준비 큐의 꼬리에 넣어진다.
성능이 시간 할당량의 크기에 많은 영향을 받는다.
시간 할당량이 매우 큰 경우 선입 선처리 정책과 같으며, 시간 할당량이 매우 적으면 잦은 문맥 교환이 필요하므로 프로세스의 실행이 느려진다.
총처리 시간(turnaround time)도 시간 할당량의 크기에 영향을 받는다.
시간 할당량의 크기가 증가해도 평균 총처리 시간이 개선되지는 않지만, 대부분의 프로세스가 단일 시간 할당량 안에 다음 CPU 버스트를 끝낸다면 평균 총처리 시간은 개선된다.
따라서 시간 할당량은 문맥 교환 시간에 비해 커야하지만 너무 커서는 안된다.
CPU 버스트의 80%는 시간 할당량보다 짧아야 한다.
우선순위(priority) 스케줄링
우선순위가 각 프로세스에 연관되어 있고, CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다.
우선순위가 같은 프로세스들은 선입 선처리(FCFS) 순서로 스케줄된다.
SJF 알고리즘은 CPU 버스트를 기준으로 하는 단순한 우선순위 알고리즘이다.
우선순위는 내부적 또는 외부적으로 정의될 수 있다.
내부적으로 정의된 우선순위의 계산에는 시간 제한, 메모리 요구, 열린 파일 수, 평균 I/O 버스트의 평균 CPU 버스트에 대한 비율 등을 사용한다.
외부적 우선순위는 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양, 작업을 후원하는 부서, 정치적 요인 등 운영체제의 외부적 기준에 의해 결정된다.
프로세스가 준비큐에 도착하면 새로 도착한 프로세스의 우선순위를 현재 실행중인 프로세스의 우선순위와 비교한다.
비선점형 우선순위 스케줄링 알고리즘은 새로 도착한 프로세스의 우선순위가 높다면 준비완료 큐의 머리 부분에 새로운 프로세스를 넣는다.
선점형 우선순위 스케줄링 알고리즘은 새로 도착한 프로세스의 우선순위가 높다면 CPU를 선점한다.
실행 준비가 되어 있으나 CPU를 사용하지 못하는 프로세스가 CPU를 기다리면서 봉쇄될 수 있다.
낮은 우선순위의 프로세스들이 CPU를 무한히 대기하는 경우가 발생할 수 있다.
이를 기아 상태(starvation)라고 한다.
낮은 우선순위의 프로세스들이 무한히 봉쇄되는 문제는 노화(aging)으로 해결할 수 있다.
노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
혹은 라운드 로빈과 우선순위 스케줄링을 결합하여, 우선 순위가 가장 높은 프로세스를 실행하고 우선순위가 같으면 라운드 로빈 스케줄링을 활용하여 스케줄 할 수 있다.
다단계 큐(multilevel queue) 스케줄링
우선순위마다 별도의 큐를 가지도록 하여 우선순위가 가장 높은 큐에서 프로세스를 스케줄하는 방식이다.
우선순위가 가장 높은 큐에 여러 프로세스가 있다면 라운드 로빈 순서로 진행하면 효과적이다.
프로세스 유형에 따라 프로세스를 개별 큐로 분할하기 위해 사용할 수 있다.
흔히 포그라운드(대화형) 프로세스와 백그라운드(배치) 프로세스로 구분할 수 있으며, 각각의 큐에서는 자체 스케줄링 알고리즘이 있을 수 있다.
큐와 큐 사이에는 고정 우선순위의 선점형 스케줄링으로 구현한다.
- 실시간 프로세스
- 시스템 프로세스
- 대화형 프로세스
- 배치 프로세스
각 큐는 절대적인 우선순위를 가지며, 상위 큐가 비어있지 않으면 하위 큐는 실행될 수 없다.
혹은 포그라운드에는 CPU 시간의 80%, 백그라운드 큐에는 20%를 할당하는 것처럼 각 큐마다 시간을 나누어 사용할 수 있다.
다단계 피드백 큐(multilevel feedback queue) 스케줄링
다단계 큐에서는 프로세스가 큐 사이를 이동할 수 없지만, 다단계 피드백 큐에서는 프로세스가 큐들 사이를 이동할 수 있다.
어떤 프로세스가 CPU 시간을 너무 많이 사용하면 낮은 우선순위의 큐로 이동한다.
낮은 우선 순위에서 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다.
이러한 노화(aging) 기법으로 기아 상태를 해결한다.
다단계 피드백 큐는 아래 매개변수에 의해 정의될 수 있다.
- 큐의 개수
- 각 큐를 위한 스케줄링 알고리즘
- 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
- 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
- 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 정하는 방법
이 스케줄링 알고리즘이 가장 일반적인 CPU 알고리즘이지만, 가장 복잡한 알고리즘이기도 하다.
댓글남기기