CPU 스케줄링
기본 개념
다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있다.
다중 프로그래밍에서는 다수의 프로세스를 메모리에 유지하고, 어떤 프로세스가 대기해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 다른 프로세스에 할당한다. 이러한 패턴은 계속된다.
이러한 종류의 스케줄링은 운영체제의 기본적인 기능이다.
CPU-I/O 버스트 사이클
프로세스들은 CPU 실행과 I/O 대기의 사이클을 반복한다.
CPU 스케줄러
CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로스세 중에서 하나를 선택해 실행해야 한다. 선택 절차는 CPU 스케줄러에 의해 수행된다. 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.
선점 및 비선점 스케줄링
CPU가 스케줄링을 결정해야 하는 상황
- 프로세스가 실행 -> 대기 상태로 전환
- I/O 요청
- 프로세스가 실행 -> 준비 완료 상태로 전환
- 인터럽트 발생
- 프로스세가 대기 -> 준비 완료 상태로 전환
- I/O 종료
- 프로세스의 종료
1,4 번째 상황의 경우 스케줄링 면에서 선택의 여지가 없다. 실행을 위해 새로운 프로세스가 반드시 선택 되어야 한다. 2,3 번쨰 상황의 경우는 선택의 여지가 존재한다.
1,4 번쨰 상황에서만 스케줄링이 발생할 경우 비선점(nonpreemptive)라고 한다. 그렇지 않다면 선점(preemptive)이라고 한다.
비선점 스케줄링에서는 CPU가 한 프로세스에 할당되면 프로세스가 종료되거나, 대기 상태로 전환해 CPU를 방출할 때 까지 CPU를 점유한다.(선점은 반대)
- 1,4 번째 상황에서만 스케줄링이 발생 -> CPU를 끝까지 점유한다.
대부분의 최신 운영체제는 선점 스케줄링 알고리즘을 사용한다.
선점 스케줄링은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있다.
- 두 프로세스가 같은 자료를 공유할 때, 한 프로세스가 자료를 수정 할 때 선점되어 다른 프로세스가 자료룰 읽으면 일관성이 깨진 상태가 된다.
디스패처
디스패처(dispatcher)
- CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈
디스패처가 하는 일
- 한 프로세스에서 다른 프로세스로 문맥을 교환한다.
- 사용자 모드로 전환
- 프로그램을 다시 시작하기 위해 사용자 프로그램을 적절한 위치로 이동 하는 일
디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 빨리 수행 되어야 한다.
디스패처 지연(dispatcher latency)
- 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 소요되는 시간
스케줄링 기준
CPU 스케줄링 알고리즘을 비교하기 위한 여러가지 기준이 존재한다.
- CPU 이용률(utilization)
- CPU의 이용률 개념상 0% ~ 100% 까지 존재한다.
- 처리량(throughput)
- 단위 시간당 완료된 프로세스의 개수
- 총처리 시간(turnaround time)
- 프로세스의 제출 시간과 완료 시간의 간격
- 준비 큐에서 대기한 시간 + CPU에서 실행하는 시간 + I/O 시간
- 대기 시간(wating time)
- 준비 큐에서 대기 하면서 보낸 시간의 합
- 응답 시간(response time)
- 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간
스케줄링 알고리즘
선입 선처리 스케줄링
선입 선처리(FCFS, First-Come, First-Served) 스케줄링 알고리즘은 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다.
선입 선처리를 위한 코드는 작성되기 쉽고 이해하기 쉽지만, CPU 버스트가 시간이 긴 프로세스가 먼저 CPU를 할당받으면 평균 대기시간이 길어질 수 있다.
평균 대기 시간은 (0 + 24 + 27) / 3 = 17 밀리초 이다.
평균 대기 시간은 (6 + 0 + 3) / 3 = 3 밀리초이다.
모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라고 한다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때 보다 CPU와 장치 이용률이 저하되는 결과를 낳는다.
선입 선처리 스케줄링 알고리즘은 비선점형이다. 프로세스가 종료 또는 I/O 처리를 요구하기 전까지 CPU를 점유한다.
최단 작업 우선 스케줄링
최단 작업 우선(shortest-job-first, SJF) 알고리즘은 가장 작은 CPU 버스트를 가진 프로세스에 CPU를 할당한다.
평균 대기시간은 (3 + 16 + 9 + 0) / 4 = 7 밀리초이다.
SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가질 수 있다. SJF 알고리즘은 최적이지만, 다음 CPU 버스트의 길이를 알 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현할 수 없다. 대신 CPU 버스트 길이의 근삿값을 계산해서 가장 짧은 예상 CPU 버스트를 가진 프로세스를 선택할 수 있다.
SJF 스케줄링 알고리즘은 선점형일수도, 비선점형일수도 있다.
아래는 선점형 방식의 예시이다.
평균 대기시간은 ((10 - 1) + (1 - 1) + (17 - 2) + (5 - 3)) / 4 = 26 / 4 = 6.5 밀리초 이다.
비선점형일 경우 7.75 밀리초가 될 것이다.
- (0 + (8 - 1) + (12 - 3) + (17 - 2)) / 4 = 7.75
라운드 로빈 스케줄링
라운드 로빈(RR, Round-Robin) 스케줄링 알고리즘은 시간 할당량(time quantum) 동안 CPU를 할당한다. 시간 할당량 동안 프로세스가 작업을 완료하지 못하면 선점되어 대기큐의 마지막에 들어간다.(선점형 방식)
프로세스의 CPU 버스트가 시간 할당량보다 적으면 CPU를 자발적으로 방출하고, CPU 버스트 시간이 길면 타이머가 끝나고 운영체제에 인터럽트를 발생시킬 것이다.
시간 할당량이 4밀리초면, 평균 대기시간은 ((10 - 4) + 4 + 7) / 3 = 5.66 밀리초이다.
라운드 로빈 스케줄링 알고리즘 사용시 시간 할당량이 크면 FCFS 정책과 같게 된다. 만약 시간 할당량이 작으면 문맥 교환을 자주 발생시킬 수 있다.
우선순위 스케줄링
CPU가 가장 높은 우선순위를 가진 프로세스에 먼저 할당된다. 우선순위가 같은 프로세스들은 선입 선처리(FCFS)로 스케줄링 된다.
우선순위 스케줄링 알고리즘은 선점형이거나 비선점형이 될 수 있다.
- 선점형 : 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점한다.
- 비선점 : 준비완료 큐의 머리 부분에 새로운 프로세스를 넣는다.
우선순위 스케줄링 알고리즘을 사용하면 무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)이 발생할 수 있다.
- 실행 준비는 되었으나 우선순위가 낮아서 CPU를 무한정 대기하는 상태
무한 봉쇄 또는 기아 상태를 해결하는 방법
- 노화(aging) 기법 사용
- 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
- 라운드 로빈과 우선순위 스케줄링을 결합
- 우선순위가 가장 높은 프로세스를 실행하고 우선순위가 같은 프로세스들은 라운드 로빈 스케줄링을 사용하여 스케줄링 하는 방법
다단계 큐 스케줄링
라운드 로빈과 우선순위 스케줄링이 결합되었지만, 우선순위마다 별도의 큐를 갖는 스케줄링 방식이다.
우선순위가 각 프로세스에 정적으로 할당되며 프로세스는 실행시간 동안 동일한 큐에 남아있다.
각각의 큐는 별도의 스케줄링 알고리즘을 사용할 수 있다. 백그라운드 큐(배치)는 FCFS 알고리즘에 의해 스케줄링 되고, 포그라운드 큐(대화형)는 RR 알고리즘에 의해 스케줄링 될 수 있다.
큐와 큐 사이에 스케줄링도 있어야 하며, 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현된다.
각 큐는 낮은 우선수위의 큐보다 절대적인 우선순위를 가진다. 각 큐는 상위 우선순위의 큐가 비어있지 않으면 실행될 수 없다.
다른 방법으로 큐들 사이에 시간을 나누어 사용하는 방법이 있다.(CPU 시간의 일정량을 할당 받아서 사용)
다단계 피드백 큐 스케줄링
다단계 큐 스케줄링 알고리즘은 프로세스들이 큐에서 큐 사이로 이동하지 않는다.(프로세스들이 자신의 특성을 바꾸지 않기 때문에)
다단계 피드백 큐는 프로세스가 큐들 사이를 이동하는것을 허용한다. 이 방식에서 프로세스들을 CPU 버스트 성격에 따라 구분한다.
- CPU 시간을 많이 사용하면 낮은 우선수위의 큐로 이동한다.
- I/O 중심의 대화형 프로세스들이 높은 우선순위를 할당 받음
위의 그림에서 번호가 0,1,2인 세 개의 큐를 가진 다단계 피드백 큐 스케줄러를 보면 각각의 큐는 상위의 우선순위를 가진 큐가 비어있을 때만 프로세스들이 실행된다.
새 프로세스가 진입했을 때 0번 큐에 넣어지고 8밀리초동안 작업을 완료하지 못하면 1번 큐에 끝에 넣어진다. 1번 큐에서 16밀리초 동안 작업을 완료하지 못하면 2번 큐의 끝에 넣어진다. 2번 큐는 프로세스를 FCFS(선입 선처리) 방식으로 처리한다. 기아를 방지하기 위해 우선순위가 낮은 큐에서 너무 오래 대기하는 프로세스가 점차 우선순위가 높은 프로세스로 이동될 수 있다.
다단계 피드백 큐 스케줄러를 정의하기 위한 매개변수
- 큐의 개수
- 각 큐를 위한 스케줄링 알고리즘
- 한 프로세스를 높은 우선순위 큐로 승격시키는 시기를 결정하는 방법
- 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
- 프로세스가 들어갈 큐를 결정하는 방법
