[OS] 스케줄링 알고리즘

 

 

스케줄링 알고리즘

.

 

 

스케줄링 알고리즘은 크게 비선점형 알고리즘과 선점형 알고리즘으로 나뉜다.

 

명칭 그대로 다른 프로세스가 사용 중인 CPU를 강제로 선점할 수 있냐 없냐인데

 

우선순위가 높은 프로세스 등의 효율성을 고려해 선점형을 선호한다.

 

아래 표는 스케줄링 알고리즘의 종류를 분류해 놓은 것이다.

 

 

 

스케줄링 알고리즘의 효율성을 평가할 때

CPU 사용률, 처리량, 대기 시간, 응답시간, 반환시간을 기준으로 하며

사용률과 처리량은 계산하기 어려워 주로 대기 시간, 응답 시간, 반환 시간을 계산한다.

 

 

 

 

스케줄링 알고리즘의 성능을 비교할 때 주로 평균 대기 시간을 본다.

평균 대기 시간은 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값이다.

 

 

 

 

여기서 알 수 있는 것은 작업 패턴을 바꾸어 평균 대기 시간이 달라질 수 있다는 것이다.

 

 

그럼 CPU 스케줄링 결정은 언제 발생할까?

 

한 프로세스가 I/O 요청 등의 인터럽트로 실행 상태에서 대기 상태로 전환될 때,

프로세스가 I/O요청 등의 작업을 완료 후 대기 상태에서 준비 완료 상태로 전환될 때 등이 있다.

 

CPU가 유휴 상태일 때 CPU 작업이 필요한 프로세스에게 CPU를 할당해 주어야 한다.

또한 긴급하게 처리되어야 하는 프로세스에게 CPU를 할당해 주어야 할 때도 있을 것이다.

 

프로세스들은 자기가 CPU를 할당 받으려 경쟁을 할 것이다.

하여 먼저 할당해 줄 프로세스를 결정해 주어야 한다.

 

 

그럼 프로세스 순서를 정하는 스케줄링 알고리즘의 종류에 대해 알아보자.

 

 

1. FCFS 스케줄링

.

 

선입선출 스케줄링(First Come First Served), 뜻대로 도착한 순서대로 CPU를 할당하는 비선점형 알고리즘이다.

 

선입선출 큐로 쉽게 관리할 수 있고, 코드는 작성하기 쉽고 이해하기도 쉽다.

하지만 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있어 평균 대기 시간이 길어질 수 있다.

 

예로 I/O 요청이 들어왔을 때 I/O 작업이 완료될 때까지 CPU는 쉬고 있어 작업 효율이 떨어진다.

 

이처럼 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려야 하고

시스템의 효율성이 떨어지는 문제를 '호위 효과'라고 한다.

 

 

 

 

2. SJF 스케줄링

.

 

Shortest Job First, 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터

CPU를 할당하는 비선점형 알고리즘이다.

 

간단한 작업을 먼저 처리할 수 있어 FCFS의 '호위 효과'를 완화할 수 있다.

하지만 I/O 같은 작업은 언제 끝날지 예측을 할 수 없어 사용의 어려움이 있다.

또한 자신보다 짧은 작업이 계속 들어오면 계속 연기되고 이를 '무한 봉쇄 현상'이라 한다.

 

 

 

 

위의 두가지 알고리즘의 문제를 '노화현상(Aging)'으로 완화할 수 있다.

'노화현상(Aging)'은 프로세스가 양보할 수 있는 상한선을 정하는 방식이다.

 

자신의 순서를 양보할 때마다 우선순위를 높여 상한선에 도달하면 무조건 실행되도록 하는 것이다.

 

 

3. HRN 스케줄링

.

 

최고 응답률 우선 스케줄링(Highest Response Ratio Next),

SJF 스케줄링에서 아사 현상을 해결하기 위해 만든 비선점형 알고리즘이다.

 

프로세스의 우선순위를 결정하는 기준은 아래와 같이 대기 시간을 고려함으로써 아사 현상을 완화한다.

 

우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간

 

 

 

 

4. 라운드 로빈 스케줄링

.

 

Round Robin(RR), 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가

작업을 완료하지 못하면 준비 큐의 맨 뒤로 가는 선점형 스케줄링 방식이다.

 

문맥 교환이 발생하여 문맥 교환 시간을 고려하여 타임 슬라이스 크기를 정해야 한다.

큰 경우에는 FCFS 스케줄링이 되고, 작은 경우에는 문맥 교환에 많은 시간을 낭비하게 된다.

 

 

 

 

5. SRT 우선 스케줄링

.

 

최소 잔류 시간 우선 스케줄링(Shortest Remaining Time),

SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식의 선점형 스케줄링 방식이다.

 

기본적으로 라운드 로빈 스케줄링을 사용하지만,

CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다.

 

 

 

 

6. 우선순위 스케줄링

.

 

프로세스는 중요도에 따라 우선순위를 갖는데 이 우선순위를 반영한 스케줄링 알고리즘이며,

비선점형 방식과 선점형 방식 모두 적용할 수 있다.

 

우선순위를 어떤 기준으로 정하느냐에 따라 다양하게 구현 가능하다.

 

우선순위 스케줄링은 순서를 무시하고 CPU를 할당하므로 아사 현상을 일으키고,

우선순위를 매번 바꿔야 하므로 오버헤드가 발생하여 효율성을 떨어뜨린다.

 

예로 작업 시간이 짧은 프로세스의 우선순위를 높게 설정하면 아래와 같다.

 

 

 

 

(추가) 우선순위를 정하는 방법은 기준을 어떻게 정하느냐에 따라 다르다고 했다!

라운드 로빈과 우선순위 스케줄링을 결합하는 방법도 있다..!

 

우선순위가 가장 높은 프로세스를 실행하고 우선순위가 같은 프로세스들은 라운드 로빈 스케줄링을 사용하는 것이다.

 

 

 

위 그림에서 도착시간 기준으로 우선순위를 잡으면

P4가 우선순위가 가장 높고, (P2, P3)은 두번째로 동일하게 높고, (P4, P5)가 동일하게 마지막 우선순위를 갖는다.

 

시간 할달량을 2밀리초로 했을 경우

우선순위가 가장 높은 P4가 모든 수행을 마치고,

동일한 우선순위를 가진 P2와 P3가 시간 할당량 2밀리초만큼 번갈아 수행한다.

 

라운드 로빈 스케줄링도 처리 방식을 여러 방법으로 변형 가능한데

한 가지 예로 시간이 지남에 따라 우선순위를 높이는 '에이징 기법'을 사용하는 것을

'이기적인 라운드 로빈 스케줄링'이라 한다.

 

 

7. 다단계 큐 스케줄링

.

 

우선순위에 따라 준비 큐를 여러 개 사용하는 비선점형 알고리즘 방식이다.

 

상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

 

하여 우선순위가 가장 높은 1번 큐에 있는 프로세스의 작업이 끝날 때까지 하위 큐의 프로세스들은 기다려야 한다.

이를 해결하기 위한 방법이 다단계 피드백 큐 스케줄링이다.

 

 

 

 

8. 다단계 피드백 큐 스케줄링

.

 

다단계 큐 스케줄링을 보완해 각 단계의 큐에 라운드 로빈 방식을 사용하고

CPU를 사용한 프로세스는 우선순위가 하나 낮은 큐의 끝으로 들어간다.

또한, 우선순위에 따라 타임 슬라이스의 크기가 다르다.

 

 

 

 

 

 

 

 

 

 

* 해당 글은 '쉽게 배우는 운영체제'와 '운영체제' 책을 참고하여 작성하였습니다. 출처: 쉽게 배우는 운영체제 (조성호), 운영체제 10판 (Abraham Silberschatz)