[OSTEP 가상화(virtualization)]Chapter 7 CPU 스케줄링

 

3~4장까지 저수준 기법에 대해서 이해하였다. 이것을 제대로 이해하지 않는다면 정책을 이해할 수 없다.

운영체제의 스케줄러의 고수준 정책에 관해서는 이해가 필요하다. 이제부터는 다양한 스케줄링 정책을 소개할 것이다.

이러한 정책은 원칙이라고도 불리며 오랫동안 개발된 정책이다. 

 

스케줄링 정책은 어떻게 개발하는가?

 

📝10.1 워크로드에 대한 가정

가장 먼저 프로세스에 대하여 몇 가지 가정 할 것이다. 일련의 프로세스들이 실행하는 상황을 워크로드라고 부르기로하자

워크로드를 결정하는 것은 정책 개발에서 매우 중요한 부분이다. 워크로드에 관해 더 잘 알수록 그에 맞게 정책을 정교하게 할 수 있다.

 

우리가 지금 설명에서 사용할 워크로드에 대한 가정은 비현실적이다. 하지만 논의하는데 문제는 없다.

논의가 진행됨에 따라 워크로드도 구체적으로 변할 것이고 최종적으로 제대로 동작하는 스케줄링 정책이 탄생할 것이다.

 

1. 모든 작업은 같은 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다.
3. 각 작업은 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 cpu만 사용하며 입출력과정은 없다.
5. 각 작업의 실행 시간은 사전에 알려져 있다. 

📝10.2 스케줄링 평가 항목

워크로드에 대한 가정 이외의 스케줄링 정책의 비교를 위해 스케줄링 평가 항목을 결정해야한다.

결론적으로 반환 시간이라는 하나의 평가 기준을 사용할 것이다. 반환 시간은 작업이 완료된 시각에서 작업이 시스템에 도착한 시각을 뺀 시간이다.

 

반호나 시간은 성능 측면에의 평가 기준이다. 다른 평가 기준으로는 공정성이다.

 

📝10.3 선입선출(FIFO)

가장 기초적인 알고리즘은 선입선출(First In First Out, FIFO) 또는 선도착선처리(First Come First Served, FCFS) 스케줄링이다.

위 그림의 평균 반환 시간은 20이다. 이렇게 보면 간단하지만 강력해보일 수 있으나 아주 큰 문제가 있다.

바로 실행 시간에 따라 성능이 천차만별이라는 것이다.

위 그림은 A가 너무 긴 시간을 사용하기에 평균 반환 시간이 매우 증가한다.

이러한 문제점을 convoy effect라고 칭하며, 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 현상이다.

 

📝10.4 최단 작업 우선(SJF)

말 그대로 가장 짧은 시간을 가진 작업을 먼저 실행시키는 것이다.

선입선출에서 문제가 되었던 평균 반환 시간이 SJF를 씀으로써 110초에서 50초로 2배 이상 성능 향상을 하였다.

모든 작업이 동시에 도착한다 가정하면 SJF는 최적의 스케줄링 알고리즘이다.

 

물론 이론적으로 좋다는 뜻이다. SJF는 가장 좋은 스케줄링 방법으로 개발되었지만 가정이 비현실적이다.

가정을 완화해서 생각해보면 

1. 모든 작업은 같은 시간 동안 실행된다.  
2. 모든 작업은 동시에 도착한다. (도착 시간이 항상 같지 않다)
3. 각 작업은 시작되면 완료될 때까지 실행된다. (여러 병행 작업의 영향으로 비효율적으로 작동할 수 있다.)
4. 모든 작업은 cpu만 사용하며 입출력과정은 없다.
5. 각 작업의 실행 시간은 사전에 알려져 있다.  (사전에 실행 시간 예측은 불가능하다)

 

1번 2번 5번에서 엄청난 페러다임 오류를 가지고있다.

그렇기에 SJF는 사실상 convoy effect 오류에서 자유로울 수 없다.

선점형 스케줄러

FIFO, SJF는 각 작업이 종료될 때까지 계속 실행하는 비선점형 스케줄러이다. 이론적으로 모든 형태 스케줄러는 선점형이고 다른 프로세스 실행을 위해 문맥 교환을 수행한다.

📝10.5 최소 잔여시간 우선(STCF)

convoy effect를 해결하기 위해 가정 3을 완화해야 한다. 이제부터 선점형 스케줄러로 문맥 교환이 일어날 스케줄러이다.

그렇다면 해결방법은 무엇일까? 남은 작업 시간에 따라 도착한 작업이 더 짧다면 그것으로 문맥 교환해 짧은 것부터 처리하는 것이다.

 

다행이도 이렇게 동작하는 스케줄러는 존재한다. 최소 잔여시간 우선(Shortest Time-to-Completion First, STCF) 또는 선점형 최단 작업 우선(Preemption Shortest Job First, PSJF)이다.

 

이는 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고

그 중 가장 적은 잔여 실행 시간을 먼저 스케줄한다.

위 그림을 보면, A가 실행중이다가 B, C가 도착하고 나서 A를 중단한 후 가장 잔여시간이 짧은 작업인 B부터 C까지 순차적으로 처리한 뒤 다시 A를 재개하는 방식을 사용하고 있다.

 

그 결과 반환 시간이 50초가 되고 convoy effect가 일어나지 않는 것이 확인되었다. 

그렇기에 SJF는 최적의 결과를 낸다면 STCF는 최적의 스케줄링이 된다. 

 

물론 실행 시간을 알기는 어렵기에 이것도 비현실적이다. 또한 문맥 교환으로인한 컨텍스트 스위칭 오버헤드 비용도 존재한다.

 

📝10.6 새로운 평가 기준 : 응답 시간

작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나라면 STCF는 매우 훌륭하다.

하지만 시분할 컴퓨터의 등장 이후, 사용자와 시스템의 상호작용을 원활하게 하기 위한 성능이 요구되었다.

 

그것은 응답 시간이다. 응답 시간은 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간으로 정의된다. 

 

이전까지 다루었던 스케줄링 방식들은 응답시간이 그리 썩 좋지 않다. 먼저 실행된 작업들이 완전히 끝날 때까지 기다려야 하기 때문이다.

 

예를 들어 다음과 같은 경우 B가 10초에 왔을 때 A는 0 B는 0 C는 10이 되어 3.33의 응답 시간을 가진다. 

우리한 응답 시간까지 좋은 스케줄러를 만들어야한다..

 

📝10.7 라운드 로빈 (Round-Robin, RR)

RR은 작업이 끝날때까지 기다리지 않고 일정 시간 실행한 후 문맥 교환을 발생시킨다.

 

이 때 작업을 실행하는 일정 시간을 타임 슬라이스(time slice) 또는 스케줄링 퀀텀(scheduling quantum) 이라고 한다.

이러한 이유로 RR은 때때로 타임 슬라이싱 이라고 불린다. 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다.

 

타임 슬라이스의 길이는 RR에게 매우 중요하다.

• 짧을수록 응답 시간 기준으로 RR의 성능이 좋아진다.
• 그러나 타임 슬라이스를 너무 짧게 지정하면 문제가 생긴다.
  • 문맥 교환 비용이 전체 성능에 큰 영향을 끼칠 수 있기 때문이다.
• 문맥 교환 비용을 상쇄할 수 있을 만큼 길어야 하지만 그렇다고 응답 시간이 너무 길어지면 안된다.

다시 정리하자면 RR은 일정 시간마다 문맥 교환을 발생시키는 정책이다. 문제점은 문맥 교환 비용을 감수할 만큼의 응답 시간에 대한 리턴이 와야한다. 그러면 매우 길어야한다는 것이다.

 

그러나 RR의 장점이 있다. 우리는 처음 이야기 할때 평가 기준에 성능, 공정성이 있다고 했다. RR은 매우 공정한 정책이다.

성능은 나쁘다. 매우 공정하다는 것이다.

 

📝10.8 입출력 연산의 고려

우선 가정 4를 완화해보자 모든 프로그램은 입출력 작업을 수행한다. 

입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행할지 결정해야한다. 현재 실행 중인 작업은 입출력이 완료될 때까지 CPU를 사용하지 않을 것이기 때문이다.

 

아래는 완료하는데 50msec이 소요되지만 10msec마다 입출력을 요청하는 작업 A와 입출력 없이 50msec이 걸리는 작업 B를 STCF 스케줄러로 수행한 그림이다.

위를 해결하기 위한 일반적인 접근 방식은 A의 각 10msec 하위 작업을 독립적인 작업으로 다루는 것이다.

이렇게 함으로써 CPU 이용률을 더 높일 수 있다.

 

📝10.9 만병통치약은 없다. 

스케줄러는 각 평가 기준에 최적화 되어있다. 

처음의 워크로드로 선정한 가정에 대해 매우 의존적이다. 

 

 

 

📝10.10

워크로드 가정: 스케줄링 개발하기 위한 가정으로 매우 비현실적이다.

스케줄링 평가 항목

• 평가항목
  • 성능
    • 반환 시간 : 작업 완료 시간 - 도착 시간
    • 응답 시간 : 작업 시작 시간 - 도착 시간
  • 공정성

스케줄링 정책

• 비선점 알고리즘
  • 선입선출(FIFO)
    • 가장 기초적인 알고리즘, 도착 순서대로 처리하며 종료까지 실행하여 Convoy effect 문제가 발생한다.
  • 최단 작업 우선(SJF)
    • 가장 짧은 실행 시간을 가진 작업을 먼저 실행
    • 이론적으로 최적의 스케줄링이지만 비현실적이다. 
    • Convoy effect 문제는 계속 발생
• 선점 알고리즘
  • 최소 잔여시간 우선(STCF)
    • SJF를 선점형으로 만든 알고리즘으로, 실행 중인 작업을 중단하고 짧은 작업부터 처리한다.
    • 이 방식은 convoy effect를 해결할 수 있다. 다만, 문맥 교환에 따른 오버헤드가 있다.
  • 라운드 로빈(RR)
    • 일정 시간만큼 작업을 실행한 후 문맥 교환을 발생시키는 방식이다. 타임 슬라이스 또는 스케줄링 퀀텀이라고 불린다.
    • 짧을수록 응답 시간이 좋지만, 너무 짧으면 문맥 교환 오버헤드가 성능에 영향을 미친다. RR은 공정성이 뛰어나지만 성능은 상대적으로 떨어진다

만병통치약은 없다:

• 모든 스케줄러는 특정 평가 기준에 최적화되어 있으며, 초기 워크로드 가정에 따라 달라진다. 특정 상황에 맞는 최적의 정책을 개발해야 한다.