1. 스케줄링 알고리즘 성능 척도
- CPU 사용률(CPU utilization), 처리량(Throughtput) : CPU 사용률이 높을수록, 처리량이 많을수록 효율이 좋음.
- 대기시간(Waiting time), 응답시간(Response time), 반환시간(Turnaround time) : 사용자 입장에서는 시간이 짧을 수록 좋음.
- 평균대기시간 : 모든 프로세스의 대기시간의 합 / 프로세스의 수.
- 스케줄링 알고리즘 성능을 비교할때는 주로 '평균대기시간'을 이용함. 그러나 작업패턴을 바꾸면 평균대기 시간이 역전되기도 함. 따라서 평균대기시간을 알고리즘의 절대적인 성능을 지표로 보지 않고, 알고리즘이 어떻게 작동하는지 파악하는 도구정도로만 여겨야함.
2. 스케줄링 알고리즘의 종류
(1) FCFS 스케줄링 (First Come First Served, 선입선출 스케줄링)
- 준비 큐에 도착한 순서대로 CPU 할당.
- 비선점형.
- 큐가 1개, 모든 프로세스의 우선순위가 동일.
- 단순하고 공평.
- 콘보이 효과(convoy effect, 호위 효과) : short process behind long process. 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어짐.
- CPU가 작업하지않고 쉬는 시간이 많아 작업 효율이 떨어짐. (일괄 작업 시스템)
(2) SJF 스케줄링 (Shorted Job First, 최단 작업 우선 스케줄링)
- CPU burst time이 가장 짧은 프로세스부터 CPU 할당.
- 비선점형 : CPU를 할당 받으면 CPU burst time이 끝날때까지 다른 프로세스에게 선점당하지 않음.
- 선점형 : 현재 수행중인 프로세스의 남은 CPU burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착했을경우 CPU를 선점 당함. 가장 짧은 평균대기시간 보장. (Shorted Remaining Time First, SRTF 스케줄링)
- 작은 작업 먼저 실행해 시스템의 효율성이 좋음.
- 아사 현상(starvation) : 우선권이 낮은 프로세스는 영원히 실행되지 못함. 불공평.
- 에이징(aging) : 아사 현상의 해결방법. 프로세스가 양보할 수 있는 상한선을 정하는 방식. 그러나 에이징 값을 어떤 기준으로 정할지도 문제.
- 운영체제가 프로세스의 CPU burst time을 정확하게 예측하기 어려움.
예측은 어려우나 과거의 CPU burst time을 이용해 추정은 가능. (Exponential Averaging)
α와 (1-α)가 둘다 1 이하이므로 후속 term이 선행 term보다 더 적은 가중치 값을 가짐.
- 프로세스가 자신의 작업시간을 운영체제에게 알려주는 방법도 있으나, 작업시간을 정확히 알기도 어렵고, 일부 악의적인 프로세스가 작업시간을 속일경우 시스템의 효율성이 나빠짐.
(3) HRN 스케줄링 (Highest Response Ratio Next, 최고 응답률 우선 스케줄링)
- 대기 시간을 고려해 SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어짐.
- 비선점형.
- 우선 순위 = (대기시간 + CPU 사용시간) / CPU 사용시간. (숫자가 클수록 우선순위가 높음)
- 아사 현상을 완화시키지만 여전히 공평성 위배.
(4) RR 스케줄링 (Round Robin, 순환 순서 방식)
- 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 시간내 완료하지 못하면 준비 큐의 맨 뒤(tail)로 가서 자기 차례를 기다리는 방식.
- 선점형.
- 준비 큐에 n개의 프로세스가 있고, 타임 슬라이스가 q인 경우, 어떤 프로세스도 (n-1)q 이상 기다리지 않음.
- 타임 슬라이스의 크기는 프로세스의 반응 시간에 영향을 미칠뿐 아니라 시스템 전체 성능에도 영향을 미침. 짧은 작업의 프로세스와 긴 작업의 프로세스가 섞여있을때 가장 효율적.
- 타임 슬라이스가 너무 크면, FCFS 스케줄링. RR과 FCFS의 평균대기시간이 같다면 문맥교환 시간이 추가되기 때문에 RR이 더 비효율적.
- 타임 슬라이스가 너무 작으면, 문맥교환 시간이 길어 오버헤드가 발생. (오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 처리시간, 메모리 등)
- 비교적 공평. 긴 작업일수록 많이 기다림. 콘베이 효과 완화.
(5) SRT 스케줄링 (Shorted Remaining Time, 최소 잔류 시간 우선 스케줄링)
- SJF와 RR을 혼합한 방식으로, RR은 스케줄링이 큐에 있는 순서대로 CPU를 할당한다면, SRT는 남아 있는 시간이 적은 프로세스에 CPU를 먼저 할당.
- 현재 실행중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환 해야 하므로 SJF에는 없는 작업이 추가.
- 운영체제가 프로세스의 종료 시간을 예측하기 어려움.
- 아사 현상.
- SRTF는 타임 슬라이스가 없고, SRT는 타임 슬라이스가 존재.
(6) 우선순위 스케줄링 (Priority)
- 우선순위를 반영해 CPU 할당.
- 시스템의 효율성보다 프로세스의 중요도에 따라 정해짐.
- 비선점형 : SJF(작업시간 짧음), HRN(대기시간이 길거나 작업시간이 짧음).
- 선점형 : SRT(남은 시간이 짧음).
- 고정 우선순위 알고리즘 : 한 번 우선순위를 부여받으면 종료 될때까지 우선순위가 고정됨. 단순하게 구현가능하나 효율성 떨어짐.
- 변동 우선순위 알고리즘 : 일정시간마다 우선순위가 변함. 시스템이 복잡하나 효율적 운영 가능.
- 준비 큐에 있는 프로세스의 순서를 무시해 아사현상 발생.
- 우선순위를 매번 바꿔야해 오버헤드가 발생하여 시스템의 효율성이 떨어짐.
(7) 다단계 큐 스케줄링 (Multilevel queue)
- 우선순위에 따라 준비 큐를 여러개 사용하는 방식.
- RR방식의 큐가 다단계로 나눠져 있고, 상단의 큐에 있는 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작.
- 고정형 우선순위 알고리즘.
- 선점형방식. 타임슬라이스를 조절하여 작업효율 높일 수 있음. 예를들어, 전면 프로세스는 타임슬라이스를 작게 하고 (interative, RR), 후면 프로세스는 타임슬라이스를 크게 함 (batch, long job, no human interaction, FCFS).
- 각 큐는 독립적인 스케줄링 알고리즘을 가짐. 그러나 타임슬라이스가 너무 커서 FCFS방식을 이용할 경우 아사 현상이 발생할 수 있음으로 각 큐에 CPU burst time을 적절한 비율로 할당. 예를 들어, 전면 프로세스(RR)에 80%, 후면 프로세스(FCFS)에 20%.
(8) 다단계 피드백 큐 스케줄링 (Multilevel feedback queue)
- 다단계 큐 스케줄링은 각 단계의 큐에 RR방식 사용하고 우선순위에 변화가 없는데, 다단계 피드백 큐 스케줄링은 CPU를 사용하고 난 프로세스의 우선순위가 낮아짐. 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어감.
- 그러나, 커널프로세스가 일반 프로세스의 큐로 삽입되지는 않음.
- 어렵게 얻은 CPU는 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮은 큐의 타임 슬라이스를 크게 설정. 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스를 얻음(FCFS).
- 오늘날 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식. 예, 유닉스 운영체제의 타임 슬라이스 10~200밀리.
- 변동 우선순위 알고리즘(의 전형적인 예).
