CPU 가상화(2) - 스케줄러(1)

1. 스케줄링 정책

지금까지는 CPU 가상화를 구현하는 저수준의 기법인 “제한적 직접 실행”에 대해 알아 보았다. 제한적 직접실행을 통해 프로세스간 전환이 되는 과정(문맥 교환)을 이해하고 어떻게 운영체제의 주도하에 시스템(물리 장치들)을 관리 할 수 있는지 알 수 있었다. 그렇다면 운영체제는 어떤 원칙을 통해 프로세스를 전환할까?

• A 프로세스 실행중 타이머 인터럽트가 발생 했다. 수많은 프로세스중 어떤 프로세스로 전환할까?

운영체제는 특정한 원칙을 가지고 있고 이를 “스케쥴링 정책” 이라고 한다. 아래의 질문을 통해 어떻게 정책들이 발전해 왔는지 알아보고자 한다.

• 핵심 가정은 무엇일까?
• 어떤 평가 기준으로 정책을 평가할 수 있을까?

1.1. 핵심 가정

아래의 가정들은 비현실적이긴 하지만 차차 가정을 줄여 나가면서 최종적으로 제대로 동작하는 스케쥴링 정책을 만들 수 있다.

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

1.2. 평가 항목

• 성능 측면
  • 반환 시간 (turnaround time)
    • 작업이 완료된 시간 - 작업이 도착한 시간
    • 작업은 동시에 도착한다고 가정하였으므로 반환 시간은 작업이 완료된 시간임.
  • 응답시간
    • 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간
    • 시분할 컴퓨터의 등장으로 사용자가 터미널을 통해 시스템과 상호작용을 하기 시작하면서 요구됨
    • 상호작용이 중요한 프로그램일 경우 짧을 수록 좋다
• 공정성 측면
  • 기아 현상이 발생되지 않는지?
  • 프로세스들이 공정하게 CPU를 차지할 수 있는지?

→ 성능과 공정성은 trade-off 관계에 있음

1.3. 여러 스케쥴링 정책들

1.3.1. 선입 선출 (FIFO)

• 특징
  • 도착한 순서대로 처리함
  • 도착시간이 같다고 가정하기 때문에 반환 시간은 프로세스들의 완료 시간을 모두 더해 평균 낼 수 있음
• 장점
  • 구현이 매우 단순하다.
  • 실행 시간이 모두 같다는 가정을 완화 하면 convoy effect가 발생할 수 있음
  • 반환시간이 길어질 수 있음
    • 안좋은 케이스 반환 시간 : 110초단점

💡 convoy effect 짧은 시간동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상

 

1.3.2. 최단 작업 우선 (Shortest Job First, SJF)

• 특징
  • 가장 짧은 실행 시간을 가진 작업을 먼저 실행 시킴
• 장점
  • FIFO 대비 반환 시간에서 더 나은 성능을 보임
    • 반환 시간 : 50초 → 2배이상의 성능 향상

• 단점
  • 모든 작업은 동시에 도착한다는 가정을 완화하면 긴 실행시간을 가진 작업이 먼저 도착 했을 때 성능 감소
    • 반환 시간 : 103.33 초

1.3.3. 최소 잔여 시간 우선(Shortest Time-to-Completion First, STCF)

• 특징
  • 작업은 끝날 때까지 계속 실행되어야 한다는 가정을 완화 (선점형 스케줄러)
    • 선점형 : 문맥 교환을 수행 할 수 있음
    • 비선점형 : 작업이 끝날 때까지 계속 실행해야함
  • 언제든 새로운 작업이 들어오면 현재 실행 중인 작업과 비교해서 적은 잔여 실행 시간을 가진 작업을 스케줄함
• 장점
  • SJF대비 평균 반환 시간이 줄어듬
    • 반환 시간 : 50초
• 단점
  • 기아현상 발생 : 잔여 실행 시간이 긴 작업에 계속 밀릴 수 있음
  • 각 작업의 실행 시간이 사전에 알려져 있다는 가정이 비현실적임.
  • 응답시간이 느림

1.3.4. 라운드 로빈(Round-Robin, RR)

• 특징
  • 작업이 끝날 때까지 기다리지 않고 일정 시간동안 실행한 후 실행 큐의 다음 작업을 실행함
    • 타임 슬라이스, 스케줄링 퀀텀 : 작업이 실행되는 일정 시간

• 장점
  • 응답시간이 빠르다
  • 공정성 측면에서 우수함
• 단점
  • 타임 슬라이스가 너무 짧으면 문맥교환에 들어가는 비용으로 인해 전체 성능에 큰 영향을 줄 수 있음
  • 문맥 교환시 갱신해야 하는 정보들
    • 레지스터, CPU 캐시, TLB, 기타 하드웨어에 저장된 프로그램과 관련된 정보

1.3.5. 입출력 연산을 고려한 스케줄러

• 스케줄러가 고려해야 할 사항
  • 특정 작업이 입출력 요청을 한경우 다음에 어떤 작업을 스케줄 할 것인가?
  • 입출력이 완료되었을 때 어떤 행동을 할 것인가?
    • 입출력을 요청한 프로세스를 대기 상태에서 준비 상태로 이동시키기
    • 입출력을 요청한 프로레스를 바로 실행 시키기

• 중첩을 통한 CPU 사용 효율성 증대

아직 스케줄러가 각 작업의 실행 시간을 알고 있다는 비현실적인 가정을 완화하지 못했다. 이는 멀티 레벨 피드백 큐 라는 과거의 정보를 이용해서 미래를 예측하는 스케줄러를 통해 완화 해보자!