스케줄링 알고리즘

김재연·2024년 2월 4일

CS 쉽게 배우는 운영체제 운영체제

서론

이 글은 쉽게 배우는 운영체제를 읽고, 잊지 않기 위해 기록하는 글입니다.

스케줄링 알고리즘

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

비선점형은 뺏기지 않는 작업, 선점형은 뺏기는 작업입니다.

스케줄링 알고리즘의 선택 기준

알고리즘은 항상 효율을 중시합니다.

그렇기 때문에, 이를 판단할 요소들도 필요하죠.

스케줄링 알고리즘의 요소들은 아래 5가지가 있습니다.

CPU 사용률 : 전체 시스템의 동작 시간 중 CPU 가 사용된 시간을 측정하는 방법
처리량 : 시간당 작업을 마친 프로세스의 수
대기 시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간
응답 시간 : 작업을 요청한 프로세스가 첫번째 응답을 내기까지의 시간
반환 시간 : 작업을 요청한 프로세스가 종료되어 자원을 반환하는데까지 걸리는 시간

CPU 알고리즘의 효율성을 평가할 때 사용률과 처리량은 계산하기가 어렵습니다.

그렇기 때문에, 주로 대기시간, 응답시간, 반환시간을 계산합니다.

위 그림은 이 요소들을 나타낸 그림입니다.

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

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

이런 식으로 프로세스가 실행되었다고 했을 때, (p1 대기시간 + p2 대기시간 + p3 대기시간) / 3 을 하여 평균 대기시간을 계산하는 것이죠.

이제부터 평균 대기 시간을 보고, 대부분 판단할 예정인데, 이게 절대적인 성능 지표는 아니라는 것을 명심해야합니다.

FCFS 스케줄링

FCFS 스케줄링은 말 그대로 선입 선출입니다.

그렇기 때문에, 가장 단순하죠, 또한 비선점으로 이루어집니다.

즉, 프로세스가 한번 작업을 실행하기 시작하면 다른 프로세스는 cpu 를 선점할 수 없습니다.

FCFS 스케줄링의 성능을 평균 대기 시간으로 평가해보죠.

다음과 같은 표가 존재한다고 생각해봅시다.

대기시간을 계산해보면, 23 밀리초라는 시간이 나오게 됩니다.

FCFS 스케줄링은 단순하고 공평합니다.

하지만, 비선점형이기 때문에 처리 시간이 긴 프로세스가 CPU 를 차지하면 다른 프로세스들은 하염없이 기다려야 합니다.

이를 콘보이 효과라고 합니다.

또 다른 단점은 중간에 입출력 작업 요청을 하는 경우에는 CPU 에게 유휴시간이 발생하게 된다는 것도 있습니다.

SJF 스케줄링

이것도 비선점형 알고리즘이고, 대기하고 있는 프로세스 중 실행 시간이 가장 짧은 작업 부터 CPU 를 할당하는 비선점형 방식입니다.

최단 작업 우선 스케줄링이라고도 불립니다.

FCFS 에서 발생하는 콘보이 효과를 완화할 수 있습니다.

성능은 어떨까요?

FCFS 보다는 조금 더 빠르네요. 20 밀리초입니다.

이렇게 SJF 스케줄링은 작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아집니다.

먼저 도착한 큰 작업으로 인해 작은 작업이 지연되지 않아요.

하지만, 다음과 같은 단점이 있습니다.

운영체제가 프로세스의 종료 시간을 정화하게 예측하기 어렵다.

과거에는 사용자의 입력을 기다리는 것과 같은 상호작용을 하지 않았습니다.

그렇기 때문에 프로세스의 연산 개수만 계산하면 종료 시간을 추정할 수 있었는데요.

하지만, 현재는 프로그램 종료 시간을 파악하기 어렵습니다.

그렇기 때문에 사용하기가 굉장히 힘든 알고리즘입니다.

공평하지 못하다.

이는 해당 알고리즘의 특성으로 일어나게 됩니다.

짧은 프로세스를 먼저 실행하기 때문에, 당연하게 발생할 수 밖에 없겠죠.

위 2개는 해결방법이 전혀 없는 문제는 아닙니다.

자신의 작업 시간을 운영체제에 알려주어 해결할 수 있죠. (악의 적인 프로세스가 작업 시간을 속인다면 시스템의 효율성이 나빠지긴 합니다.)

또 두번째는 에이징으로 완화할 수 있습니다.

양보할 때마다 나이를 먹어 특정 나이 이상이 되면 cpu 에 할당되게끔 하는 것이죠.

하지만, 에이징 값을 어떤 기준으로 정할 것인지가 문제라 에이징에도 한계가 있습니다.

HRN 스케줄링

SJF 에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘입니다.

최고 응답률 우선 스케줄링이라고도 하는데요.

다음과 같이 우선순위를 결정하게 됩니다.

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

즉, 대기 시간이 길어질 수록 우선순위가 커지는 것입니다.

이렇게 위와 같이 실행되고, 대기시간은 20 밀리초가 되게 됩니다.

최대한 공평성을 높이기 위해 많이 사용되고 있지만, 아직 완전히 해결되지 않아 사용되지는 않는다고 합니다.

라운드 로빈 스케줄링

순환 순서 방식으로 번역되는 라운드 로빈 스케줄링은 그냥 FCFS 에 타임 슬라이스를 적용한 형식입니다.

다음과 같이 동작하게 되죠.

타임 슬라이스가 10밀리초인 시스템에서 이전에 표와 같은 프로세스가 실행될 때 라운드 로빈 스케줄링의 평균 대기 시간을 계산해봅시다.

조금 많이 복잡해졌는데, 대기 시간은 22.33 밀리초로 계산이 됩니다.

아무래도 콘베이 효과가 줄지만, FCFS 보다 무조건 좋은 알고리즘이라고 할 수 없습니다.

여기서 p2, p1 의 순서만 바꾸더라도 FCFS 와 대기시간이 동일하고, 이런 경우 문맥교환의 비용이 추가되어 더 비효율적인 알고리즘이 되기 때문입니다.

그렇기 때문에, 다음과 같이 장단점을 파악하여 타임 슬라이스를 잘 관리하여야 합니다.

타임 슬라이스가 큰 경우

이 경우, FCFS 와 가깝게 동작하게 되고, 또한 워드 프로세스와 비디오 플레이어가 동시에 실행되고 있을 때, 타임 슬라이스가 큰 경우 비디오가 엄청 끊겨 보이게 될 것입니다.

타임 슬라이스가 작은 경우

이 경우 사용자는 하나의 프로세스가 아니라, 여러개의 프로세스가 동시에 실행되는 것처럼 보일 것입니다.

물론 이 점은 좋지만 문맥교환이 문제입니다.

많은 문맥교환으로 인해 시스템 효율이 극으로 떨어지게 됩니다.

SRT 우선 스케줄링

최소 잔류 시간 우선 스케줄링입니다.

즉, SJF 스케줄링의 선점형 방식이라고 할 수 있습니다.

성능은 어떨까요?

대기시간이 15.66 밀리초로 지금까지의 알고리즘 중에 가장 짧은 것을 볼 수 있습니다.

하지만, 이는 무작정 좋은 것은 아닙니다.

남은 시간이 어느 것이 더 적은지 주기적으로 계산해주기 때문에, 이에서 오버헤드가 발생하게 되고, 아사 현상이 일어나기 쉽습니다.

우선순위 스케줄링

프로세스는 중요도에 따라 우선순위를 갖습니다.

이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링인데요.

이 때 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있습니다.

다음과 같은 우선순위가 있다고 가정해봅시다.

이렇게 되면 SJF 스케줄링과 평균 대기시간이 같습니다.

우선순위 알고리즘은 아래와 같은 알고리즘들에서 사용할 수 있습니다.

SJF 스케줄링 : 작업시간 짧은 것
HRN 스케줄링 : 작업, 대기 시간 긴 것에 따라 우선순위 부여
SRT 스케줄링 : 남은 시간이 짧은 프로세스

또한 우선순위가 계속 변경되느냐 아니느냐에 따라 아래 두가지로 나뉩니다.

고정 우선순위 알고리즘: 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정되기 때문에 단순하게 구현할 수 있지만, 아사현상이 일어나기 쉽고, 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어질 수 있다.
변동 우선순위 알고리즘: 일정 시간마다 우선순위가 변하게 됩니다. 위와 반대이죠.

단점으로는 공평성을 위배하고, CPU 작업 이외의 오버헤드가 발생한다는 점이 있지만, 프로세스의 우선순위는 시스템 효율성 뿐만아니라, 중요도도 기준에 있기 때문에 좋은 알고리즘이고 많이 사용된다. (커널 프로세스가 일반 프로세스보다 먼저 실행되어야 한다.)