운영체제(5)-CPU 스케줄링

업데이트: January 22, 2020

책 <운영체제와 정보기술의 원리>, 반효경 을 읽고 정리한 내용입니다

이미지 출처 : 종난아 공부하자! 블로그

운영체제(1) - 개요

운영체제(2) - 컴퓨터 시스템의 동작 원리

운영체제(3) - 인터럽트의 원리

운영체제(4) - 프로세스 관리

프로그램이 시작되어 메모리에 올라가면, 프로그램 카운터(PC)라는 이름의 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가지고 있게 된다. 그러면 CPU는 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행하게 된다.

기계어 명령은 크게 세가지로 나눌 수 있다.

CPU내에서 실행되는 명령
- ex. ADD
- 명령의 수행 속도가 매우 빠르다
- 일반 명령
메모리 접근을 필요로 하는 명령
- ex. Load / Store
- CPU내에서 수행되는 명령보다는 시간이 걸리지만, 비교적 짧은 시간에 수행할 수 있는 명령
- 일반 명령
입출력을 동반하는 명령
- CPU나 메모리 접근 명령보다 꽤 많은 시간이 소요된다.
- 특권 명령

사용자 프로그램이 수행되는 과정은 CPU작업과 I/O 작업의 반복으로 구성된다.

CPU 버스트

사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계

I/O 버스트

I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계

각 프로그램마다 CPU 버스트와 I/O 버스트가 차지하는 비율이 균일하지는 않다.

CPU 바운드 프로세스

I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스
계산 위주의 프로그램

I/O 바운드 프로세스

I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
대화형 프로그램

CPU버스트가 균일하지 않은 다양한 프로그램이 공존하므로 효율적인 CPU 스케줄링 기법이 반드시 필요하다.

컴퓨터 시스템 내에서는 CPU를 한번에 오래 사용하기보다는 잠깐 사용하고 I/O 작업을 수행하는 프로세스들이 많다. (대화형 작업)

이러한 대화형 작업은 CPU의 빠른 서비스를 필요로 한다. 따라서 CPU 스케줄링 시 CPU 버스트가 짧은 프로세스. 즉 I/O 바운드 프로세스에게 우선순위를 높여주는 것이 바람직하다. 이러한 스케줄링은 I/O 장치의 효율성을 높이는 효과도 얻을 수 있다.

CPU 스케줄러

준비 상태에 있는 프로세스 중 어떠한 프로세스에게 CPU를 할당할지를 결정하는 운영체제의 코드.

CPU 스케줄링의 발생 상황

run state에 있던 프로세스가 I/O 요청 등에 의해 Blocked State로 바뀌는 경우

비선점형 스케줄링
run state에 있던 프로세스가 타이머 인터럽트 발생에 의해 ready state로 바뀌는 경우

선점형 스케줄링
I/O 요청으로 blocked state에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 ready state로 바뀌는 경우(직전 프로세스가 아닌 I/O가 완료된 프로세스에게 CPU할당하는 문맥교환이 일어나는 경우.)

선점형 스케줄링
CPU에서 run state에 있는 프로세스가 terminated 되는 경우

비선점형 스케줄링

비선점형 스케줄링 : CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는다.

선점형 스케줄링 : 프로세스가 CPU를 계속 사용하기 원하더라도 강제로 빼앗을 수 있다.

디스패처

CPU 스케줄러를 통해 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경 설정을 하는 커널 모듈

디스패처는 현재 수행중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.

디스패치 지연 시간

디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간.
대부분은 문맥 교환 오버헤드에 해당된다.

스케줄링의 성능 평가

시스템 관점의 지표로는 CPU활용도와 처리량이 있으며, 사용자 관점의 지표로는 소요 시간, 대기 시간, 응답 시간 등이 있다. 지표의 정의는 다음과 같다.

CPU 활용도 (CPU utilization)
- 전체 시간 중 CPU가 명령을 수행한 시간의 비율
처리량 (throughput)
- 주어진 시간 동안 CPU 버스트를 완료한 프로세스의 개수
- CPU 버스트가 짧은 프로세스에게 우선 CPU 할당하면 처리량은 증가한다.
소요 시간 (turnaround time)
- 프로세스가 CPU 요청한 시점부터 CPU 버스트가 끝날 때까지 걸린 시간
- CPU버스트가 준비 큐에서 기다린 시간과 실제 CPU를 사용한 시간의 합
- 소요 시간은 프로그램 전체가 아닌 CPU 버스트의 수만큼 각각 별도로 측정
대기 시간 (waiting time)
- 프로세스가 CPU 버스트 기간 중 준비 큐에서 기다린 시간의 합
- 한 번의 CPU 버스트 중에도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있다.(시분할 시스템)
응답 시간 (response time)
- 프로세스가 CPU요청 시점부터 처음으로 CPU를 얻을 때까지 기다린 시간
- 타이머 인터럽트가 빈번히 발생할수록 응답 시간이 향상된다.
- 대화형 시스템에 적합한 성능 척도

중국집 예시

활용도 - 전체 시간 중 주방장이 일한 시간의 비율

처리량 - 주방장이 주어진 시간 동안 몇 명의 손님에게 요리를 주었는지

소요시간 - 손님이 중국집에 들어와 음식을 다 먹고 나가기까지 소요된 총 시간

대기시간 - 중국집에 들어와 순수하게 음식을 기다린 시간, 음식이 조금씩 여러번 나왔다면 각각의 음식이 나오기까지 기다린 시간을 합한 것

응답시간 - 최초의 음식이 나오기까지 기다린 시간

스케줄링 알고리즘

FCFS

First-Come First-Served

프로스세가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식을 말한다.

CPU를 선점하지 않는다.

문제점

CPU 버스트가 긴 프로세스 하나가 CPU버스트가 짧은 프로세스 여러개보다 먼저 도착한다면
다수의 프로세스들이 앞의 긴 작업 하나 때문에 계속 기다려야 하므로 평균 대기 시간이 길어지게 된다. (Convoy Effect)
I/O 장치의 활용도 또한 하락한다.

프로세스	CPU 버스트 시간
P1	12
P2	3
P3	3

프로세스의 도착 순서가 P1, P2, P3일 때

대기 시간
- P1 = 0, P2 = 12, P3 = 15
평균 대기 시간
- (0+12+15) / 3 = 9

도착 순서가 P2, P3, P1일 때

대기 시간
- P1 = 6, P2 = 0, P3 = 3
평균 대기 시간
- (6+0+3) / 3 =3

프로세스 간에 대기 시간이나 소요 시간의 편차가 매우 커진다.

SJF

Shortest Job First

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식

평균 대기 시간을 가장 짧게 하는 최적의 알고리즘

비선점형 방식

CPU를 획득하면 자진 반납하기 전까지는 CPU를 선점당하지 않는 방식

선점형 방식

프로세스가 CPU를 점유해도 CPU버스트가 더 짧은 프로세스가 도착하면 해당 프로세스에게 CPU를 할당

SRTF (Shortest Remaining Time First)

평균 대기 시간을 가장 많이 줄일 수 있는 방식

프로세스	도착 시각	CPU 버스트 시간
P1	0	14
P2	4	8
P3	8	2
P4	10	8

SJF 비선점형 스케줄링

평균 대기 시간
- (0+12+6+14) / 4 = 8

SJF 선점형 스케줄링

평균 대기 시간
- (18+2+0+4) / 4 = 6

실제 프로세스의 CPU 버스트 시간을 미리 알 수 없기 때문에, 예측을 통해 CPU버스트 시간을 구한 후 예측치가 가장 짧은 프로세스에게 CPU를 할당하게 된다.

$(n+1)$ 번째 CPU 버스트의 예측 시간 $T_{n+1}$은 다음과 같다. ( $t_n$: 실제 CPU 버스트 시간, $\alpha$ : 매개변수) $T_{n+1} = \alpha*t_n +(1-\alpha)*T_n$ $\alpha = 0$일 경우 $T_{n+1} = T_n$, 이전의 예측 시간을 그대로 사용

$\alpha = 1$일 경우 $T_{n+1} = t_n$, 이전의 실제 CPU버스트 시간을 그대로 사용 $T_{n+1} = \alpha t_n +(1-\alpha)\alpha T_{n-1} + ...+(1-\alpha)^j\alpha t_{n-j}+...$ 즉, 더 오래된 과거일수록 영향력이 적어지도록 반영하는 방식이다

기아 현상

CPU버스트가 짧은 프로세스가 계속해서 도착할 경우, CPU버스트 시간이 긴 프로세스는 영원히 CPU를 할당받지 못하게 된다.

우선순위 스케줄링

준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식

CPU버스트 시간이 우선순위라면, SJF 알고리즘과 같다.

비선점형 방식과 선점형 방식 둘 다 구현할 수 있다.

우선순위가 낮은 프로세스는 계속 기다려야 하는 기아 현상이 발생할 수 있다.

기아 현상을 해결하기 위해 노화(aging)기법을 사용할 수 있다.

기다리는 시간이 길어지면 우선순위를 높인다.

라운드 로빈 스케줄링

각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 특정 시간(할당 시간, time quantum)으로 제한한다.

할당 시간이 경과하면 CPU를 회수해 준비 큐에 있는 다른 프로세스에게 CPU를 할당한다.

원래 프로세스는 준비 큐의 가장 뒤로 가서 다음 차례를 기다린다.

할당 시간이 너무 길면, FCFS알고리즘과 같아진다.

할당 시간이 너무 짧으면, CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥 교환의 오버헤드가 증가한다.

n개의 프로세스가 준비 큐에 있고 할당 시간이 q라고 할 때, 모든 프로세스는 (n-1)q 시간 이내에 적어도 한번은 CPU를 할당받을 수 있다.

대화형 프로세스의 빠른 응답 시간을 보장한다.

CPU를 많이 쓰는 프로세스는 대기 시간이 길어지고

CPU를 적게 쓰는 프로세스는 대기 시간이 짧아진다.

프로세스	CPU 버스트 시간
P1	24
P2	17
P3	3

프로세스는 P1, P2, P3순으로 도착했고, 할당 시간이 10이라고 하면 결과는 다음과 같다.

0~ 10 : P1 (14남음)
10~20 : P2 (7남음)
20~23 : P3 (완료)
23~33 : P1 (4남음)
33~40 : P2 (완료)
40~44 : P1 (완료)

SJF와 비교

일반적으로 SJF 방식보다 평균 대기 시간은 길지만, 응답 시간은 더 짧다.

CPU버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU 버스트가 긴 프로세스가 불이익을 당하지 않도록 한다.

FCFS와 비교

FCFS는 라운드 로빈보다 평균 대기 시간이나 평균 소요 시간 측면에서는 좋은 결과를 얻는다. 그러나, 프로세스 간 대기 시간이나 소요 시간의 편차가 매우 크며, 평균 응답 시간이 지나치게 길어지는 문제점이 있다.

라운드 로빈 스케줄링에서 할당 시간을 극단적으로 짧게 설정하면, 프로세스들이 거의 동시에 자신의 CPU 버스트를 끝마치게 된다. 따라서, 평균 응답 시간이 짧으며 대기 시간이나 처리 시간의 편차가 크지 않다. 그러나, 평균 대기 시간과 평균 소요 시간은 FCFS보다 비효율적이다.

멀티 레벨 큐

준비 큐를 여러개로 분할해 관리하는 스케줄링 기법

성격이 다른 프로세스들을 별도로 관리하고 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두게 된다.

프로세스를 어느 큐에 넣어야 할까?

전위 큐

대화형 프로세스를 담기 위한 큐
응답 시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용한다.

후위 큐

계산 위주의 프로세스를 담기 위한 큐
FCFS를 사용해 문맥 교환 오버헤드를 줄인다.

어느 큐에 먼저 CPU를 할당하지?

고정 우선순위 방식

큐에 고정적인 우선순위를 부여한다.
우선순위가 낮은 큐는 높은 큐가 비어있을 때만 실행한다.

타임 슬라이스 방식

각 큐에 CPU시간을 적절한 비율로 할당한다.
큐에 대한 기아 현상을 해소할 수 있다.

멀티 레벨 피드백 큐

프로세스가 하나의 큐에서 다른 큐로 이동 가능하다!

노화 기법 : 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 높은 큐로 승격시킨다.

그림에서 상위 큐일수록 우선순위가 높다.

결과적으로 작업 시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하고, 작업 시간이 긴 프로세스에 대해서는 문맥 교환 없이 CPU 작업에만 열중할 수 있는 FCFS방식을 채택한다.

다중 처리기 스케줄링

CPU가 여러개인 시스템을 다중 처리기 시스템(multi-processor system)이라고 부른다.

프로세스를 한 줄로 세워 CPU가 알아서 프로세스를 꺼내는 방법과

각 CPU별로 줄세우는 방법이 있다.

일부 CPU에 작업이 편중될 수 있다.
CPU별 부하분산을 하는 Load Balancing 매커니즘이 필요하다.

다중 처리기 스케줄링 방식

대칭형 다중 처리

CPU가 각자 알아서 스케줄링을 결정한다.

비대칭형 다중 처리

하나의 CPU가 다른 CPU들의 스케줄링 및 데이터의 접근을 책임진다.

실시간 스케줄링

실시간 시스템에서는 데드라인 안에 반드시 작업을 처리해야 한다.

경성(hard) 실시간 시스템

정해진 시간 안에 반드시 작업이 완료되어야 한다.
원자로 제어, 미사일 발사

연성(soft) 실시간 시스템

멀티미디어 스트리밍 시스템

데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링 또는

데드라인이 존재하는 프로세스에게 일반 프로세스보다 높은 우선순위를 할당하는 방식을 사용한다.

스케줄링 알고리즘의 평가

큐잉 모델

이론적 방식. 수학적 계산을 통해 각종 성능 지표를 계산한다.

시뮬레이션

실제 시스템에서 수행하지 않고 가상으로 CPU 스케줄링 프로그램을 작성하는 방법

구현 및 실측

실제 커널의 스케줄링 소스코드를 수정해서 시스템에 설치한 뒤 실행 시간을 측정

남궁찬