ostep / 가상화 / CPU / 스케줄링 정책 (한글판 10장, 영문판 7장)

들어가며

ostep에서는 스케줄링 정책에 대해서 설명할 때 비현실적인 가정 하에 만든 단순화한 모델에서 시작해 가정을 하나씩 없애가면서 점점 복잡한 모델을 만들면서 최종적으로 현실에서 사용하는 모델에 다다릅니다.
이 장에서는 작업의 실행 시간을 사전에 알 수 있는 경우까지만 다룹니다.
책에서와 섹션 구성에 아주 살짝의 차이를 두었습니다.
- 책에서는 알고리즘별로 섹션을 구성하여, 알고리즘을 설명하고, 가정을 완화한 다음에 생기는 문제를 같이 제시했습니다.
- 저는 사용한 가정에 따라 섹션을 구성하여, 각 섹션별로 이전 섹션에서 가정을 완화한 모델을 제시하고, 이전 섹션에서 최적의 알고리즘을 적용했을 때 발생하는 문제를 제시하고 이를 새로운 모델로 해결하는 방향으로 풀어갔습니다.

워크로드에 대한 가정

모든 작업은 같은 시간동안 실행됩니다.
모든 작업은 동시에 도착합니다.
각 작업은 시작되면 완료될 때까지 실행됩니다.
모든 작업은 CPU만 사용합니다.
각 작업의 실행 시간은 사전에 알려져 있습니다.

스케줄링 알고리즘 한 눈에 살펴보기

비선점형 스케줄링

가장 단순한 모델

모든 가정을 고려한 가장 단순한 모델에서 출발해보겠습니다.

모델
- 모든 작업이 같은 시간동안 실행되고,
- 동시에 도착하고,
- 시작하면 완료될 때까지 실행되고,
- CPU만 사용하고,
- 실행 시간은 사전에 알려져 있습니다.
평가 기준: 반환 시간
- 이 때 스케줄링 알고리즘은 무엇을 최적화해야 할까요?
  - 각 작업을 완료하는데 소요된 시간을 최적화할 수 있겠습니다. 이를 반환 시간으로 정의합니다.
    - 계산할 때에는 주어진 정보를 활용하여 $(완료\ 시간) - (도착\ 시간)$ 으로 계산할 수 있겠습니다.
알고리즘: FIFO
- 모든 작업들이 시간적인 측면에서는 동일하기 때문에 어떤 순서로 실행해도 평균 반환 시간은 동일합니다.
- 가장 심플하게 구현하자면 작업들이 나열된 순서대로 실행하는 알고리즘을 생각할 수 있겠습니다. 이 알고리즘을 FIFO (선입선출)라고 부릅니다.

가정 완화: 작업들의 실행 시간이 항상 같지는 않다면?

이전 모델에서 "모든 작업이 같은 시간동안 실행된다"라는 가정을 제거해보겠습니다.

모델
- 모든 작업이 동시에 도착하고,
- 시작하면 완료될 때까지 실행되고,
- CPU만 사용하고,
- 실행 시간은 사전에 알려져 있습니다.
평가 기준: 반환 시간
FIFO의 문제: Convoy Effect
- 선입선출 알고리즘에서 길이가 각각 10, 10, 100인 작업이 다른 순서로 들어온 경우를 비교해보겠습니다.
  - 순서대로 시간이 10, 10, 100인 작업이 들어온 경우 반환시간이 각각 10, 20, 120이며, 평균 반환시간은 $\frac{10+20+120}{3} = 50$ 입니다.
  - 순서대로 시간이 100, 10, 10인 작업이 들어온 경우 반환시간이 각각 100, 110, 120이며, 평균 반환시간은 $\frac{100+110+120}{3} = 110$ 입니다.
- 각각의 작업의 소요 시간은 같은데 평균 반환시간이 이렇게 차이가 나는 이유는 앞에 시간이 오래 걸리는 작업이 있어서 뒤의 짧게 끝나는 작업들이 모두 긴 시간을 기다리기 때문입니다.
- 이 효과를 Convoy Effect라고 합니다.
해결 방법: SJF
- Convoy Effect를 최소화하려면 작업 시간이 최소인 작업부터 순서대로 실행해야 합니다.
- 이렇게 대기 중인 작업 중 소요 시간이 최소인 작업부터 실행하는 알고리즘을 최단 작업 우선(Shortest Job First, SJF)라고 합니다.
- SJF 알고리즘은 현재 가정 하에서 평균 반환 시간을 최소화함이 수학적으로 증명되어 있습니다.
  - 여담: 수학적인 증명 스케치
    - 가정에 의해 모든 작업이 동시에 도착하기 때문에 모든 작업 목록이 도착 시점에 정해짐을 알 수 있습니다.
    - 작업 목록의 개수가 정해져 있을 때 평균 반환 시간을 최적화하는 것과 총 반환 시간을 최적화하는 것은 같습니다. $(평균\ 반환\ 시간) = \frac{(총\ 반환\ 시간)} {(작업\ 개수)}$ 이기 때문입니다.
    - 총 반환 시간
      - 총 반환시간은 각 작업의 반환시간, 즉 각 작업이 완료되기까지 기다려야 하는 시간을 모두 합하여 구할 수 있습니다. 다른 방법으로는 각 작업이 실행되는 동안 작업들이 실행 및 대기중인 시간을 모두 합할 수도 있습니다. 그림으로 나타내면 다음과 같습니다.
      - 먼저 실행하면 실행할수록 많은 작업들이 대기 중이므로, 많은 작업들이 짧은 시간동안만 대기하도록 짧은 작업의 순서대로 실행시키는 알고리즘이 총 반환시간을 최소화합니다.
        엄밀하게는 재배열 부등식을 통해 증명할 수 있습니다.

가정 완화: 작업들이 모두 같은 시간에 도착하지는 않는다면?

책에서는 별도로 다루지 않았으므로 짧게 넘어가겠습니다. 이 경우에도 각 작업이 끝날 때마다 대기 중인 작업 중 가장 짧은 작업을 실행시키는 SJF 알고리즘이 최적의 알고리즘입니다.

아까전의 예시에서 시간이 각각 10, 10, 100인 작업들이 간발의 차로 100, 10, 10의 순서대로 도착한다고 가정해보겠습니다. 그렇다면 SJF 알고리즘을 적용하여도 최적의 평균 대기 시간은 $\frac{100 + 110 + 120}{3} = 110$ 이 되겠습니다.

선점형 스케줄링

들어가며

지금까지는 "작업이 시작하면 완료될 때까지 계속 실행된다"는 가정 하의 스케줄링 알고리즘에 대해서 살펴보았습니다. 이는 예전에 많이 사용했던 일괄 처리 시스템에서 유효하게 사용되었던 가정입니다. 이런 가정 하의 스케줄러를 비선점(non-preemptive) 스케줄러라고 합니다.

반면 현대 운영체제에서는 OS가 한 프로세스의 실행을 중단시키고 다른 프로세스에게 실행권을 넘길 수 있습니다. 구체적으로 말하면 스케줄러는 앞 장에서 다루었던 문맥 교환을 수행할 수 있습니다. 이렇게 한 작업을 중단시키고 다른 작업을 처리하는 스케줄러를 선점 스케줄러라고 하며, 현대 OS에서 사용하는 거의 모든 스케줄러는 선점 스케줄러입니다.

가정 완화: 작업이 완료되기까지 기다리지 않아도 된다면?

모델
- 모든 작업은 CPU만 사용하고,
- 실행 시간은 사전에 알려져 있습니다.
평가 기준: 반환 시간
SJF의 문제: Convoy Effect
- 아까전에 보았던 간발의 차로 100, 10, 10의 순서대로 작업이 도착하는 상황을 생각해보겠습니다.
- 앞의 상황에서는 작업이 끝날 때까지 기다려야 한다는 가정이 있었습니다.
- 따라서 SJF 알고리즘을 적용하여도, 나중에 도착한 짧은 작업이 이미 시작한 긴 작업을 중단할 수 없었기 때문에 기다려야 했습니다. 다시 말해, 앞에 살펴보았던 Convoy Effect가 다시 발생했음을 확인할 수 있습니다.
해결: STCF
- 작업이 도착하는 족족 현재 실행 중인 작업을 포함해서 SJF 알고리즘을 적용한다고 생각하면, 현재 시점에서 가장 잔여 시간이 적은 작업을 먼저 실행해야 한다는 사실을 알 수 있습니다. 이를 STCF (Shortest Time-to-Completion First)라고 부릅니다.
새로운 평가 기준: 응답 시간
일괄 처리 시스템에서는 작업의 반환 시간을 최적화하는 것과 작업이 처음 실행되는 시간을 최적화하는 것이 좋은 평가 기준이었습니다.
하지만 시분할 컴퓨터가 등장하면서 사용자가 상호작용을 하면서 응답 시간이라는 새로운 평가 기준이 중요해지기 시작했습니다.
- ostep에서는 응답 시간을 작업이 도착하기부터 처음 스케줄될 때까지의 시간으로 정의합니다.
  - 수식으로는 다음과 같이 정의합니다: $(응답\ 시간) = (첫\ 실행\ 시간) - (도착\ 시간)$

응답 시간을 최적화하는 알고리즘

모델
- 모든 작업은 CPU만 사용하고,
- 실행 시간은 사전에 알려져 있습니다.
평가 기준: 응답 시간
문제
- 반환 시간을 최적화하는 알고리즘의 경우 응답 시간이 길어지는 경우가 있습니다. 예를 들어 10초짜리 작업이 10개가 대기하고 있다면 대기 중인 11초짜리 작업은 응답시간이 최소 100초가 되겠습니다.
알고리즘: Round Robin
- Round Robin 알고리즘은 정해진 타임 슬라이스(time slice) 혹은 스케줄링 퀀텀(scheduling quantum)동안 현재 작업을 실행 한 후 대기 중인 다음 작업으로 넘어갑니다.
- 타임 슬라이스의 길이
  - 응답 시간 측면에서는 짧은 것이 좋습니다.
  - 문맥 교환 비용의 상쇄(amortization) 측면에서는 긴 것이 좋습니다.
  - 이 둘을 고려해서 적절한 길이로 설정해야 합니다.
트레이드오프: 공정한 정책의 경우 반환 시간이 안 좋습니다.
- 동일한 작업을 가지고 공정한 정책과 불공정한 정책을 비교해 보겠습니다.
  - 두 정책 모두 총 CPU 사용 시간은 동일합니다. (문맥 교환 비용은 상쇄되었다고 가정하겠습니다.)
  - 공정한 정책의 경우 CPU의 시간을 골고루 나누어주기 위해서 실행 중인 작업을 중단시키고 대기시키는 과정이 있습니다. 이로 인해 CPU 사용 중에 더 많은 작업들이 대기 중이게 됩니다.
  - 총 실행 시간이 같을 때, 대기 중인 작업이 더 많을 때 총 반환 시간이 커짐을 알 수 있습니다.
    - 표로 만들어서 각 시간대별로 비교해보시면 비교가 쉽습니다. (아래 표에서는 세로줄끼리 비교)시간이 10, 10, 100인 작업이 도착했을 때 첫 번째 표는 STCF, 두 번째 표는 time slice를 5로 놓은 RR입니다.
입출력 연산의 고려
모델
- 모든 작업은 CPU와 입출력을 모두 사용하고,
- 실행 시간은 사전에 알려져 있습니다.
알고리즘
- 한 개의 작업이 CPU를 사용하다가 입출력 작업으로 넘어갈 경우, 입출력을 대기하고 있는 CPU 자원을 다른 작업에게 할당한다면 시스템을 더 잘 활용할 수 있습니다.
- 이를 구현하기 위해서 각 입출력 작업 사이의 CPU 작업들(CPU 버스트)을 별개의 작업으로 간주하면 기존의 정책을 그대로 적용하면서 입출력 대기중일 때 다른 작업을 수행할 수 있게 됩니다.

나가며

이렇게 실행 시간이 사전에 알려져 있는 경우에 여러 가지 알고리즘을 학습하고 비교하였습니다. 하지만 현실에서는 작업의 실행 시간이 얼마인지 사전에 알고 있다는 가정은 비현실적입니다. 따라서 다음 장에서는 사전 지식 없이 반환 시간과 응답 시간을 모두 고려하는 알고리즘에 대해서 다루게 됩니다.