운영체제 5. 스케줄링 : 개요

5. 스케줄링 : 개요

5.1 워크로드에 대한 가정

• 프로세스가 동작하는 일련의 행위를 워크로드(Work load)라 한다. 워크로드에 대한 이해도가 높을수록 그에 최적화된 스케줄링 정책을 정교하게 개발할 수 있다.
• 우리는 시스템에서 실행 중인 프로세스 혹은 작업(job)에 대해 다음과 같은 가정을 한다
  1. 모든 작업은 같은 시간동안 실행된다.
  2. 모든 작업은 동시에 도착한다.
  3. 작업은 일단 시작하면 최종적으로 종료될 때 까지 실행된다.
  4. 모든 작업은 CPU만 사용한다.(즉, 입출력을 수행하지 않는다.)
  5. 각 작업의 실행시간은 사전에 알려져 있다.

5.2 스케줄링 평가 항목

• 스케줄링 정책의 평가를 위해 스케줄링 평가항목(Scheduling metric)을 결정해야 한다.
• 반환시간은 (turnaround time) 작업이 완료된 시각에서 작업이 도착한 시각을 뺀 시간
• 반환은 성능 측면에서 평가 기준이다.
• 공정성(fairless)는 작업들에 공평하게 실행 기회를 주는가 이다.

5.3 선입선출(FCFS : First Come First Served)

• 기본적인 알고리즘은 선입선출(FIFO) 또는 선도착선처리(FCFS) 스케줄링이다. FIFO는 단순하며 구현하기 쉽다. 우리의 가정하에 잘 동작한다.
• CPU를 많이 필요로 하지 않는 프로세스들이, CPU를 오랫동안 사용하는 프로세스가 끝나기를 기다리는 현상을 Convoy effect 라고 한다.

5.4 최단 작업 우선(SJF : Shortest Job First)

• 가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다.
• 모든 작업이 동시에 도착한다면 SFJ가 최적(Optimal)의 스케줄링 알고리즘을 증명할 수 있다. 하지만 모든 작업이 동시에 도착하지 않고 임의의 시간에 도착한다고 가정한다면 다시 Convoy 문제가 발생할 수 있다.

5.5 최단 잔여 시간 우선(STCF : Shortest Time-to-Completion First)

• 이 문제를 해결하기 위해 가정 3을(작업은 끝날 때 까지 계속 실행된다.) 완화해야 한다. 즉, 작업은 실행 도중에 중단 될 수 있다. 타이머 인터럽트가 발생하고 문맥교환이 가능하다면, 스케줄링은 하던 일을 중지하고 다른 작업으로 스위치가 가능하다. 앞서 다른 SFJ는 비선점형 스케줄러이기 때문에, 실행중인 작업을 중지하고 다른 작업을 실행하지 못한다.
• SJF에 선점 기능을 추가한 스케줄러를 최단 잔여시간 우선 또는 선점형 최단 작업 우선(PSJF)라 한다. 새로운 작업이 도착하면, 이 스케줄러는 현재 실행중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행시간을 비교하여, 잔여 실행을 비교하여, 잔여 실행 시간이 가장 작은 작업을 스케줄한다.

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

• 작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가기준이 반환시간 하나라면 STCF는 매우 훌륭한 정책이다. 그러나 시분할 컴퓨터가 등장하며 사용자는 터미널에서 작업하게 되어 시스템에게 상호작용을 원할히 하기위한 성능을 요구하게 되었다. 응답시간(response time)이라는 새로운 평가 기준이 나왔다.
• 응답시간은 작업이 도착하는 시점부터 처음으로 스케줄 될 때 까지의 시간으로 정의된다.
• STCF를 비롯하여 비슷한 류의 정책들은 응답시간이 짧다고 할 수 없다. 예를 들어, 3개의 작업이 동시에 도착한 경우 세 번째 작업은 딱 한 번 스케줄 되기 위해 먼저 실행된 두 작업이 완전히 끝날때 까지 기다린다.
• 반환시간 기준으로는 매우 훌륭한 반면, 응답시간과 상호작용 측면에서는 매우 나쁜 방법이다.

5.7 라운드 로빈(RR : Round-Robin)

• 응답시간 문제를 해결하기 위하여 라운드 로빈(RR) 스케줄링이라 불리는 스케줄링 알고리즘을 도입한다. RR은 작업이 끝날 때까지 기다리지 않는다. 대신 일정시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 이때 작업이 실행되는 일정시간을 타임 슬라이스(time slice) 또는 타임퀀텀(time quntum)이라 부른다. 이러한 이유로 RR은 때때로 타임슬라이싱이라고 불린다. 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다.
• 타임슬라이스의 길이는 RR에게 매우 중요하다. 타임슬라이스가 짧을수록, 응답시간 기준으로 RR의 성능은 더 좋아진다. 그러나 타임 슬라이스를 너무 짧게 지정하면 문제가 생긴다. 짧게 지정하면 문맥교환 비용이 전체 성능에 큰 영향을 미친다. 시스템 설계자는 시스템이 최적의 상태로 동작할 수 있도록 타임 슬라이스의 길이를 결정해야 한다. 문맥교환의 비용을 상쇄할 수 있을 만큼 길어야 하지만 응답시간이 너무 길어지면 곤란하다.
• 문맥교환 비용에는 레지스터를 저장/복원하는 작업만 있는 것 아니다. CPU캐시, TLB, 분기 예측등을 비롯하여 다른 하드웨어에도 프로그램과 관련된 다양한 작업 정보들이 저장되어 있다. 작업이 전환되면 이 정보들은 모두 갱신되어야 한다. 갱신 작업이 매우 큰 성능 비용을 유발한다.
• 반환 시간이 유일한 평가기준인 경우 타임 슬라이스를 가진 RR은 매우 안좋은 최악의 정책이다. RR은 각 작업을 잠깐 실행하고 다음 작업으로 넘어가고 하면서 가능한 각 작업을 늘리는 것이 목표이다. 반환 시간은 작업 완료 시간만을 고려하기 때문에, RR은 거의 최악이며, 많은 경우 단순한 FIFO보다도 성능이 안좋게 된다.
• 일반적으로 RR과 같은 공정한 정책, 즉 작은 시간 단위로 모든 프로세스에게 CPU를 분배하는 정책은 반환 시간과 같은 평가 기준에서는 성능이 나쁘다. 불공정하게 한다면 하나의 작업을 끝까지 실행하고 종료할 수 있지만 나머지 작업들에 대한 응답 시간은 포기해야 한다. 반대로 공정성을 더 중히 여긴다면 응답 시간은 줄어들지만 반환 시간은 나빠지게 된다.

5.8 입출력 연산의 고려

• 가정 4를 완화하자. 모든 프로그램은 입출력 작업을 수행한다.
• 현재 실행중인 프로세스가 입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행할지를 결정해야 한다. 현재 실행중인 작업은 입출력이 완료될 때까지 CPU를 사용하지 않을것이기 때문이다. 입출력 요청을 발생시킨 작업은 입출력 완료를 기다리며 대기 상태가 된다. 입출력이 하드디스크 드라이브에 보내진 경우, 프로세스는 드라이브의 현재 입출력 워크로드에 따라 몇 초 또는 좀 더 긴 시간 블록된다. 스케줄러는 그 시간동안 실행 될 다른 작업을 스케줄 해야 한다.
• 하나의 프로세스가 입출력 완료를 대기하는 동안, 다른 프로세스가 CPU를 사용하여 연산의 중첩이 가능해진다.
• 입출력을 고려한 스케줄링 기법은 각 CPU버스트를 하나의 작업으로 간주함으로써 스케줄러는 대화형 프로세스가 더 자주 실행되는 것을 보장한다. 이러한 작업이 입출력을 실행하는 동안 다른 계산 위주의 작업들이 실행된다. 결과적으로 CPU의 이용률이 더 높아진다.