[OS] CPU 스케줄링 알고리즘

안녕하세요 배트맨🦇 입니다 :)

이번 포스팅에서는 스케줄링 알고리즘에 대해서 다뤄보겠습니다.

CPU 스케줄링에 관해서는 이전 포스팅을 참고해 주세요 !

[OS] CPU 스케줄링

---

스케줄링 알고리즘

CPU 스케줄링 알고리즘은 크게 비선점형과 선점형 두 범주로 나눌 수 있습니다.

여기 분류된 다양한 알고리즘의 개념과 장단점을 알아보겠습니다.

CPU 알고리즘의 효율을 평가할 때는 주로 대기 시간, 응답 시간, 반환 시간을 계산합니다. CPU 사용률, 단위 시간당 작업을 마친 프로세스 수 등 다른 요소도 있지만 계산하기 까다롭기 때문에 잘 사용하지 않습니다.

대기 시간 : 프로세스가 생성된 후 실행되기 전까지 대기하는 시간

응답 시간 : 첫 작업을 시작한 후 첫 번째 반응까지의 시간

실행 시간 : 프로세스 작업이 시작된 후 종료까지의 시간

반환 시간 : 대기 시간을 포함하여 종료될 때까지의 시간

평균 대기 시간 : 모든 프로세스의 대기 시간을 합하여 프로세스의 수로 나는 값

위 그림에서는 (P1, P2, P3의 대기 시간의 합) ÷ 3 이 평균 대기 시간이 됩니다.

---

FCFS 스케줄링

First Come First Served의 약자로 큐에 도착한 순서대로 CPU를 할당하는 비선점형 알고리즘입니다. 비선점형이기 때문에 한 번 프로세스가 실행되면 해당 프로세스가 끝나야만 다음 프로세스를 실행합니다. 따라서 모든 프로세스의 우선순위는 동일합니다.

 

알고리즘 평가

• FCFS 알고리즘은 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스는 계속 기다려야 한다는 단점이 있습니다. 
• 현재 작업 중인 프로세스가 입출력 대기에 걸리는 경우 CPU가 쉬는 시간이 길어져 작업 효율이 떨어집니다.

 

SJF 스케줄링

Short Job First의 약자로 준비큐에 대기 중인 프로세스들 중 실행 시간이 짧은 작업부터 CPU를 할당하는 비선점형 방식의 알고리즘입니다.

알고리즘 평가

• 프로세스의 종료 시간을 운영체제가 예측하기 어렵다는 힘듦이 있습니다.
• 작업 시간이 긴 프로세스는 계속 연기되기 때문에 공평성이 떨어집니다.
  • 에이징 방법으로 완화할 수 있습니다. 에이징은 프로세스가 양보할 때마다 나이를 먹는 방식으로 나이에 상한선을 정해놓는 방법입니다.

위 두 가지 단점으로 인해 잘 사용되지 않습니다.

 

HRN 스케줄링

Highest Response Ratio Next의 약자로 실행 시간과 대기 시간을 모두 고려하는 비선점형 알고리즘입니다. 위 SJF 스케줄링의 공평성을 보완하기 위해 만들어졌습니다. 우선순위 계산법은 (대기 시간+처리 시간) ÷ 처리시간 입니다. 계산한 우선순위의 숫자가 클수록 먼저 실행됩니다.

 

알고리즘 평가

• SJT의 공평성 문제를 완화했지만 여전히 공평성이 위배된다는 평가가 있습니다.

따라서 많이 사용되지 않습니다.

 

라운드 로빈 스케줄링

순환 순서 방식이라고도 하며 정해진 시간(타임 슬라이스) 만큼 작업하다가 완료되지 못한 프로세스는 큐의 맨뒤로 가서 대기하는 선점형 알고리즘입니다. 프로세스들이 작업을 완료할 때까지 계속 순환하며 실행됩니다.

 

알고리즘 평가

• 타임슬라이스 크기가 너무 작으면 문맥 교환 시간이 길어지고, 타임슬라이스가 너무 크면 하나의 작업이 끝나고 다음 작업이 시작되는 FCFS와 큰 차이가 없기 때문에 잘 고려하여 타임 슬라이스 크기를 적당하게 설정해야 합니다.
  • 실제 사용되는 타임 슬라이스는 10~200 밀리초 사이라고 합니다.

 

SRT 스케줄링

SR Train...의 약자..

Shortest Remaining Time의 약자로 라운드 로빈 스케줄링을 기반으로 남아 있는 작업 시간이 가장 적은 프로세스를 다음 프로세스로 정하는 선점형 알고리즘입니다.

 

알고리즘 평가

• 현재 남아 있는 프로세스의 남은 작업 시간을 주기적으로 계산하고, 문맥 교환이 자주 발생합니다.

따라서 좋은 알고리즘이 아니며 잘 사용되지 않습니다.

 

우선순위 스케줄링

우선순위 스케줄링은 우선순위를 어떻게 정하느냐에 따라 다양하게 구현됩니다. 앞서 있었던 알고리즘의 예시를 보면

SJF는 작업 시간이 짧은 프로세스에 높은 우선순위,

HRN은 우선순위 계산법에 따라 숫자가 큰 프로세스에 높은 우선순위,

SRT는 남은 시간이 짧은 프로세스에 높은 우선순위를 부여한 것입니다.

우선순위는 우선순위가 변동될 수 있는지 여부에 따라 고정 우선순위 알고리즘과 변동 우선순위 알고리즘으로 구분합니다.

고정 우선순위 알고리즘은 단순하게 구현할 수 있는 장점에 반해 시시각각 변하는 중요도를 반영하지 못해 효율성이 떨어진다는 단점이 있습니다.

변동 우선순위 알고리즘은 시스템의 상황을 잘 반영할 수 있는 장점이 있지만, 일정 시간마다 우선순위를 계속 새로 매겨야 해서 복잡하다는 단점이 있습니다.

 

알고리즘의 평가

• 공평성을 위배합니다.
• 프로세스의 우선순위를 매번 계산해야 하므로 시스템 효율을 떨어뜨립니다.

 

다단계 큐 스케줄링

우선순위에 따라 여러 개의 큐를 사용하는 방법입니다.

높은 우선순위의 큐에 있는 작업을 모두 끝내야 하단의 큐로 이동합니다. 이렇게 되면 낮은 우선순위 프로세스의 대기 시간이 상당히 길어지고 공평성에 위배되기 때문에 이것을 보완하기 위해 다단계 피드백 큐 스케줄링 방식이 도입됩니다.

 

다단계 피드백 큐 스케줄링

다단계 큐 스케쥴링을 기반으로

1. 각 단계의 큐에 라운드 로빈 방식을 사용합니다.
2. CPU를 사용한 프로세스는 원래 큐가 아닌 우선순위가 하나 낮은 큐에 들어갑니다.
3. 커널 프로세스가 일반 프로세스 큐에 삽입되지는 않습니다.
4. 마지막 큐에서는 타임 슬라이스가 무한대로 작업을 마칠 때까지 CPU를 빼앗기지 않습니다.

 

다단계 피드백 큐 스케줄링은 오늘날 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식입니다.