🖌 시작하기 전에
반환시간이란?
작업 반환시간은 작업이 완료된 시각에서 작업이 도착한 시각을 뺀 시간이다. 이는 성능측면에서의 스케쥴링 평가 기준이다.
공정성이란?(fairness)
성능과는 다른 평가기준으로 스케쥴러는 전체 시스템의 성능을 극대화하기 위해 몇몇 작업에 대해 실행기회를 주지 않을 수 있는데 이런 경우 공정성이 악화된다고 한다.
응답시간(response time)
응답시간은 작업이 도착하는 시점으로부터 처음으로 스케줄 될 때까지의 시간으로 정의된다. 사용자와 상호작용을 원할히 하기위한 요구성능이다.
이와 같은 평가기준으로 앞으로 나열할 알고리즘의 스케쥴링을 평가해보고자 한다.
⏱ 선입선출 스케쥴링(FIFO)
가장 기본적인 알고리즘인 선입선출(First In First Out, FIFO) 혹은 선도착선처리(First Come First Served, FCFS) 스케쥴링이다.
- 장점
1 . 단순하다
2 . 구현하기 쉽다. - 단점
1 . Convoy effect
2 . 긴 평균 응답시간(response time)
예시를 보며 알아보자.
세 A, B, C 라는 작업이 0의 시간에 순서대로 거의 동시에 도착했다고 가정하자. 이때 A는 10, B는 20, C는 30에 종료했다. 그렇다면 세 작업의 평균 반환시간은
이렇게 구할 수 있다.
이때 A의 작업시간이 증가한다면 어떻게 될까?
A의 작업시간이 100초로 늘어나게 되었을 때 평균 반환시간을 구해보자.
이러한 현상을 convoy effect 라고 부른다.
convoy는 짐을 옮기는 대형트럭인데 이처럼 큰 차가 도로 앞에서 교통체증을 만드는 것처럼 작업시간이 긴 작업이 전체 작업시간을 늘리는 현상을 convoy effect라고 한다.
⏱ 최단 작업 우선 스케줄링
앞서 말한 convoy effect 문제를 해결할 수 있는 스케줄링이다. 최단 작업 우선(Shortest Job First, SJF)스케줄링은 가장 짧은 실행시간을 가진 작업을 먼저 실행시키는 스케줄링이다.
이때의 평균반환시간은
이렇게 됨으로서 110초에서 50초로 2배 이상 향상시킨 것을 알 수 있다. 하지만 이 알고리즘은 모든 작업이 동시에 도착했을 때를 가정했을 때에만 이런 효율을 보인다. 만약 B와 C가 늦게 도착했다면 어떻게 될까?
또다시 convoy effect가 발생했다. 그렇다면 평균 반환시간은?
⏱ 최소 잔여시간 우선 스케줄링
앞서다룬 SJF는 비선점형(Non-preemption) 스케줄러이기 때문에, 실행중인 작업을 중지하고 다른 작업을 실행하지 못한다. SJF에 선점 기능을 추가한 스케줄러를 최소 잔여시간 우선(Shortest Time-to-Completion First, STCF) 또는 선점형 최단 작업 우선(PSJF)라 한다. 새로운 작업이 도착하면 현재 실행중인 작업과 새로운 작업의 잔여 실행시간을 비교하여 잔여 실행시간이 가장 작은 작업을 스케줄한다.
평균반환시간
그렇다면 평균 응답시간은 어떨까?
위의 예시에서 A는 시간 0, B와 C는 시간 10에 도착한 경우 각 작업의 응답시간은 A는 0, B는 0, C는 10으로 평균 3.33이 된다. 응답시간이 짧다고 할 수 없다. 예를 들어, 3개의 작업이 동시에 도착한 경우, 세번째 작업은 스케줄되기 위해 먼저 실행된 두 작업이 완전히 끝날 때까지 기다려야한다. 반환시간 기준으로는 훌륭한 알고리즘이지만 응답시간과 상호작용 측면에서는 좋지 않은 방법이다.
⏱ 라운드 로빈 스케줄링
응답 시간 문제를 해결하기 위해 라운드 로빈(Round-Robin, RR) 스케줄링을 도입한다.
RR은 작업이 끝날 때까지 기다리지 않고 일정 시간 이후 다음 작업으로 전환한다. 작업이 실행되는 일정 시간을 타임 슬라이스(time slice) 혹은 스케줄링 퀀텀(scheduling quantum)이라고 부른다. 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다.
타임 슬라이스의 길이는 RR에게 매우 중요한 조건이다. 타임 슬라이스가 짧을수록 응답시간이 빨라져 RR의 성능이 더 좋아진다고 생각할 수 있다. 하지만 타임 슬라이스가 너무 짧을 시에는 문맥 교환 비용(Context switching)이 전체 성능에 큰 영향을 미칠 수 있다. 또한 너무 타임 슬라이스의 길이가 길어지면 곤란하다. context switching 비용을 상쇄할 수 있을 만큼 길어야한다.
context switching 비용
문맥 교환 비용에는 레지스터를 저장 / 복원하는 작업만 있는 것이 아니라, CPU 캐시, TLB, 분기 예측 등을 비롯하여 다른 하드웨어에도 프로그램과 관련된 다양한 작업 정보들이 저장되어 있다. 작업이 전환되면 이 정보들은 모두 갱신되어야 한다. 갱신 작업이 매우 큰 성능 비용을 유발한다.
RR의 반환 시간(You can't have your cake and eat it too.)
케익을 먹으면서 동시에 케익을 보존할 수 없다. RR은 각 작업을 잠깐 실행하고 다음 작업으로 넘어가기 때문에 완료시간은 늦어질 수 밖에 없다. 그렇다면 완료시간을 고려하는 반환시간은 거의 최악이라고 볼 수 있다. 따라서 응답 시간은 줄었지만 동시에 반환 시간까지 좋게 할수는 없다.
❌ 또 하나의 잘못된 가정이 있었다.
우리는 작업의 길이를 미리 알 수 없다.
정확한 스케줄링을 위해서는 프로세스의 미래 동작을 예측해야한다. 프로세서의 미래동작을 예측함에 있어 과거의 프로세스 동작 이력을 반영하는 방식으로 이 문제를 해결해보고자 한다. 이 스케줄러를 멀티 레벨 피드백 큐(Multi-level feedback queue)라 한다.
생각보다 글이 길어져서 다음 글에서 계속 해보려고 한다.
도움받은 자료
책 - 운영체제, 아주 쉬운 세 가지 이야기. 제 2판.
영상 - o Operating System (운영체제), CPA310, KOREATECH
o Instructor: Duksu Kim (김덕수)
