스케쥴링 알고리즘은 크게 비선점형 알고리즘(non-preemptive algorism)과 선점형 알고리즘(preemptive algorism) 으로 나뉜다.
비선점형 알고리즘은 프로세스가 CPU를 할당받으면 작업이 끝이 날 때까 CPU를 놓지 않아 효율이 떨어져 지금은 거의 사용되지 않는다.
선점형 알고리즘은 시분할 시스템을 고려하여 만들어진 알고리즘으로, 어떤 프로세스가 CPU를 할당 받아 실행중이라도 운영체제가 CPU를 강제로 빼앗을 수 있다.
스케쥴링 알고리즘의 선택 기준
스케쥴링 알고리즘이 효율적인지 판단하려면 다음과 같은 기준을 고려한다.
-
CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
-
처리량 : 단위 시간 당 작업을 마친 프로세스의 수
-
대기 시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간
-
응답 시간 : 대화형 시스템에서 사용자의 요구에 얼마 만에 반응하는지로 프로세스 시작 후, 첫 번째 출력 또는 반응이 나올 떄까지 걸리는 시간
-
반환 시간 : 프로세스가 생성된 후, 종료되어 사용하던 자원을 모두 반환하는데 걸리는 시간
CPU 알고리즘의 효율성을 평가 할 때는 사용률과 처리량은 계산하기 어려우므로 주로 대기 시간, 응답 시간, 반환 시간을 계산한다.
-
대기 시간 : 프로세스가 생성된 후, 실행되기 전까지 대기하는 시간
-
응답 시간 : 첫 작업을 시작한 후, 첫 번째 출력(응답) 이 나오기까지의 시간
-
실행 시간 : 프로세스 작업이 시작된 후, 종료되기까지의 시간
-
반환 시간 : 대기 시간을 포함하여 실행이 종료될 떄까지의 시간
스케쥴링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 본다.
평균 대기 시간 = 모든 프로세스의 대기 시간 총합 / 프로세스의 수
FCFS 스케쥴링
First Come First Service
준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식, 선입선출이라고도 한다.
한 번 실행되면, 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있는데 큐가 하나라 모든 프로세스는 우선순위가 동일하다.
성능을 평가해보자. 아래와 같다면
평균 대기시간은
P1 대기시간 = 0 (처음 도착하고 바로 시작)
P2 대기시간 = 27 (P1의 끝날 때까지 대기한 후, P1 작업시간에서 P2 도착시간을 제외)
P3 대기시간 = 42 (P1, P2의 총 작업 시간이 끝나고, P3 도착시간을 제외)
이므로 평균 대기 시간은 약 23 밀리초가 된다.
단순하고 공평해보이지만 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어지는 문제가 있다. 이를 콘보이 효과(convoy effect) 혹은 호위 효과 라고 한다.
SJF 스케쥴링
Shorted Job First
준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식, 최단 작업 우선 스케쥴링이라고도 한다.
비선점 스케쥴링임을 잊지말자.
P1의 대기 시간 = 0
P2의 대기 시간 = 30 + 9 - 3 = 36
P3의 대기 시간 = (P2보다 먼저 실행 된다) 30 - 6 = 24
평균 대기 시간은 = (0 + 24 + 36) = 20밀리초가 된다.
현대의 프로세스는 사용자와의 상호작용이 빈번히 발생하기 때문에 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려워, SJF 스케쥴링은 사용하기가 힘들다.
또, P2의 작업이 계속 연기되었는데 이를 아사(starvation) 현상 이라고 한다. 작업 시간이 길다는 이유만으로 계속 뒤로 밀렸다.
위를 해결하기 위해서는
프로세스가 자신의 작업 시간을 운영체제 알려주어 해결하거나 에이징으로 해결할 수 있으나
악의적인 프로세스가 작업 시간을 속이거나, 어떤 기준으로 에이징을 해야 하는지에 대해 한계가 있어
결론적으로 잘 사용하지 않는다.
HRN 스케쥴링
Highest Response Ratio Next
SJF 스케쥴링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘으로
최고 응답률 우선 스케쥴링이라고 한다.
서비스를 받기 위해 기다린 시간과 CPU 사용 시간(작업 시간)을 고려하여 스케쥴링을 하는 방식으로
프로세스 우선순위를 결정하는 기준은 다음과 같다.
우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간
이로 평가하면 다음과 같다.
SJF 스케쥴링에 비하면 대기 시간이 긴 프로세스의 우선순위를 높이므로 아사 현상을 완화한거 같으나 여전히 공평성이 위배되어 많이 사용되지 않는다.
라운드 로빈 스케쥴링
Round Robin, RR
한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.
가장 단순하고 대표적인 방식으로 프로세스들이 작업을 완료할 때까지 계속 순환하면 실행된다.
FCFS와 유사하지만, 각 프로세스마다 CPU를 사용할 수 있는 최대 시간이 있다는 것이다.
우선순위가 적용되지 않은 가장 단순한 !!선점형!! 스케쥴링 방식이다.
성능을 평가해보자. 타임 슬라이스를 10밀리초라고 가정 할 경우,
P1 대기 시간 = 0 + 19 + 8 = 27
P2 대기 시간 = 7(10-3) + 9 + 10 = 26
P3 대기 시간 = 14(20-6)
로 평균 대기시간은 67/3 으로 22.33 밀리초이다.
FCFS와 비교했을 때 FCFS 는 23밀리초 이므로 와~ 라운드 로빈이 더 낫네 이걸 쓰자 라고 할 수가 없다.
라운드 로빈 스케쥴링은 선점형 방식 이므로 문맥 교환 시간이 추가된다.
라운드 로빈 스케쥴링이 효과적으로 작동하려면 문맥 교환에 따른, 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 한다. 타임 슬라이스의 크기는 프로세스의 반응 시간에 영향을 미칠 뿐만 아니라 시스템 전체의 성능에도 영향을 미친다.
참조한 책 및 사이트
쉽게 배우는 운영체제
https://yansigit.github.io/blog/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-cpu-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/