스케줄링
현재 실행 중인 여러 프로세스들 중 과연 어떤 프로세스에게 CPU를 할당하여 작업권을 줄 것인지, 작업권을 주는 그 순서는 어떻게 배정할 것인지, 이것을 결정하는 과정이 바로 스케줄링이다.
그리고 이러한 스케줄링 정책의 성능(효율성과 안정성)을 평가하는 지표로서 반환 시간(turnaround time)과 응답 시간(response time) 이라는 것을 이용하곤 한다.
반환시간이란 작업(프로세스)이 등록되고 완료되어 종료될 때까지 걸리는 그 시간을 뜻하는데, 프로세스들의 평균 반환시간이 짧은 스케줄러가 긴 것보다 당연하게도 효율적이라고 평가된다.
응답시간은 작업(프로세스)이 등록되고 난 뒤 처음으로 스케줄 되어 실행되기까지 걸린 시간을 뜻한다.
응답시간은 반환시간과는 다르게 프로세스 작업이 완료되었는 지 그 유무에 대해선 관심이 없고, 말 그대로 작업이 최초로 CPU에게 할당될 때까지 얼마만큼의 시간이 걸렸는지를 평가하는 지표이다.
사용자와의 빠른 상호작용을 중요시하는 현대의 컴퓨터 시스템에서는 반환시간보다 더욱 중요하게 평가되는 지표라고도 말할 수 있을 것 같다.
선점방식과 비선점방식
스케줄링 정책은 크게 선점방식과 비선점방식으로 나누어진다.
선점방식과 비선점방식은, 현재 진행하고 있는 프로세스의 작업을 잠시 멈추고 다른 프로세스의 작업을 스케줄 할수 있는지 없는지 그 가능 여부에 따라서 구분되어 진다.
작업 도중에 새로운 스케줄링 처리가 가능하다면 선점방식으로 분류되고, 그렇지 않다면 비선점방식 으로 분류된다.
(인터럽트를 통하여 Context Switch(문맥교환)을 수행할 수 있는 환경기반의 스케줄링 기법은 선점방식에 해당되고, 그렇지 않은 것들은 비선점방식이라고 보면 된다)
비선점방식의 스케줄러는 과거에서나 이용되던 방식으로 현대의 OS에서는 대개 선점방식의 스케줄러를 이용한다.
비선점(non-preemptive)방식의 스케줄링 알고리즘
비선점방식의 스케줄링 알고리즘으로는 대표적으로 FIFO(FCFS), SJF가 존재한다.
FCFS(First Come First Serve)라고도 불리는 FIFO(First In First Out) 알고리즘은 프로세스가 프로세스 리스트에 들어온 순서 그대로 작업을 스케줄 하는 정책이다.
비선점방식이기때문에 도중에 다른 프로세스로 작업을 전환하지도 않고, 그저 정직하게 프로세스가 등록된 바로 그 순서를 차곡차곡 따라가며 작업을 진행하는 방식이다.
SJF(Shortest Job First) 알고리즘은 FIFO(FCFS) 방식보다는 조금 더 스마트하게 움직인다.
SJF는 현재 작업 대기 중인 프로세스 리스트 중에 가장 작업시간이 짧은 프로세스를 우선해서 골라 스케줄 시키는 방식으로 동작한다.
따라서 SJF 방식에서는 FIFO(FCFS) 방식처럼 반환시간이 짧은 프로세스들이 반환시간이 굉장히 큰 프로세스에 가로막혀 작업을 하염없이 기다리는 경우가 존재하지 않는다.
(대기 중인 프로세스들이 모두 동시에 들어왔다고 가정할 때)
즉 SJF 방식이 FCFS 방식보다 평균 반환시간이 더 짧고 우수한 스케줄링 알고리즘에 해당된다.
선점(preemptive)방식의 스케줄링 알고리즘
선점방식의 스케줄링 알고리즘으로는 대표적으로 STCF(Shortest Time-to-Complition First)가 존재한다.
선점형 SJF 알고리즘이라고도 불리는 STCF은 SJF의 동작방식에다 선점기능을 추가한 버전이라고 보면 된다. (따라서 PSJF(Preemptive SJF) 알고리즘이라고도 불린다)
SJF처럼 현재 작업 대기 중인 프로세스 리스트 중 가장 작업시간이 짧은 프로세스를 최우선으로 골라 스케줄 하는데, 하나의 프로세스를 작업하는 도중에 새로운 작업이 등록된다면 현재 맡고있는 작업의 잔여시간과 새롭게 등록된 작업의 잔여시간을 비교하여 도중에 작업할 프로세스를 변경하기도 하는 방식이다.
RR(Round-Robin)
RR(Round-Robin)은 프로세스의 응답시간에 중점을 둔 선점방식의 스케줄링 알고리즘이다.
RR은 단지 정해진 시간만큼만(정해진 양만큼만) 프로세스를 실행시킨 뒤, 또 다른 다음 프로세스로 작업을 전환하는 방식으로 전체 작업을 진행한다.
(각 프로세스의 작업시간을 잘게 나누어(타임 슬라이스, 스케줄링 퀀텀) 공정하게 작업을 배분하는 방식이다. 따라서 RR은 타임 슬라이싱 스케줄링이라고도 부른다)
작업 프로세스를 빠르게 전환해가면서 모든 프로세스의 작업을 공평하게 실행시켜 전체 프로세스의 응답시간이 짧아지도록 설계하겠다는 것이 바로 RR의 기본 발상이다.
따라서 RR 스케줄러의 경우 프로세스의 응답속도는 빠르지만 프로세스의 평균 반환시간은 앞서 말한 다른 스케줄링 기법들보다 떨어지는 편이다.
(응답속도와 반환시간은 반비례적인 관계이다. 평균 반환시간을 낮추기 위해서는 작업을 완전히 종료시키는 것에 최대한 집중해야 한다. 하지만 RR의 경우 응답속도에 집중하여 동작하기 때문에 작업의 종료여부 자체에는 관심이 없다)
또한 RR은 프로세스의 작업시간들을 잘게 나누어 작업을 빈번히 전환하면서 실행하기때문에 Context Switch가 자주 일어나는 환경이 되어 버렸다는 단점이 존재한다.
따라서 RR 스케줄러는 평균 응답시간에 집중하여 프로세스들의 응답이 너무 늦어지지 않도록 타임슬라이스의 길이를 더욱 잘게 나눌 것인지, 아니면 늘어나는 오버헤드 비용을 상쇄시키는 것에 집중하여 타임슬라이스를 충분히 늘릴 것인지를 적절하게 선택하여 설계해야만 한다.
입출력을 고려한 스케줄링 기법
우수한 스케줄링 정책을 구현하기 위해서는 모든 시스템이 "중첩"적으로 동작되도록 스케줄러를 설계해야만 한다.
CPU가 일을 하고 있을 때 HDD와 같은 입출력장치들이 굳이 쉬고 있어야할 이유는 없으며, 역으로 입출력장치들이 동작 중일때 굳이 CPU가 동작하지 말아야 한다는 이유 또한 없다.
당연히 모든 장치가 동시에 동작하게끔 설계하는 것이 효율적인 방식이 될 것이다.
(중첩되지 않은 설계의 스케줄링 예시)
해당 그림은 STCF 스케줄링 기법 위에서 동작하는 프로세스 A와 B에 대한 작업 흐름을 나타낸 것이다.
그림을 보면 A가 스케줄러로 인해 우선권을 갖게되어 CPU에 의해 B보다 먼저 작업이 진행되는 것을 볼 수 있다. (A와 B의 잔여 작업 시간이 동일하여 랜덤하게 A가 먼저 선택된 상황)
그런데 프로세스 A는 작업 진행 도중 Disk에 접근하여 특정 자료를 꺼내와야하고, 꺼내온 자료를 바탕으로 다시 작업을 진행해야 한다는 조건이 따른다.
심지어 A의 작업 잔여시간에는 이러한 Disk 입출력과 관련된 시간이 계산되어있지 않으므로 단순한 STCF 바탕의 스케줄러는 계속해서 A에게만 우선권을 부여할 것이다.
따라서 Disk가 작업을 진행하는 시간동안 CPU는 아무일도 하지 않고 단순히 A를 기다리고만 있는 비효율적인 동작이 이루어지게 되는 것을 볼 수 있다.
이것이 중첩되지 않은 설계의 스케줄러에서 나타나는 비효율적인 현상이다.
(중첩적으로 설계된 스케줄링의 예시)
반면 이 그림에서는 (프로세스 A가 요청한) Disk가 작업하는 동안 CPU가 B 프로세스를 작업을 진행하고 있는 것을 볼 수 있다. (해당 그림 또한 STCF 스케줄러 위에서 동작하고 있음을 가정한다)
즉 CPU와 DISK가 중첩적으로 작동하고 있다.
똑같은 STCF 스케줄러 기반에서 어떻게 이러한 차이를 구현해 낼 수 있을까?
바로 특정한 입출력을 대기 중인 상태에 있는 프로세스가 존재한다면, 해당 프로세스는 작업 목록에서 가려지게끔 스케줄러를 설계하는 식으로 이러한 차이를 구현해 낼 수 있다.
또한 입출력 대기시간으로 인하여 나눠진 A의 작업 영역들을 모두 독립적인 작업으로 간주하게끔 설계를 진행한다면, 프로세스 B가 먼저 실행된다거나 B가 도중에 우선권을 아예 가져가버리는 일이 없어지게 된다.
즉 IO 작업을 보유하고 있는 잘게 잘려진 A들이 항상 앞부분에서 먼저 실행되어 지는 것이다.
(IO 작업을 가진 프로세스가 스케줄의 뒷부분으로 가게되면 시스템이 비중첩이 되어 비효율적이다)
