CPU 스케쥴링2

EDF: Earliest Deadline First 스케줄링

• 마감시간이 빠를수록 높은 우선순위를 부여
• 마감시간이 늦을수록 낮은 우선순위를 부여

Proportional Share 스케줄링

• 전체 시간 T중에서 각 그룹별로 할당하는 시간을 다르게 하여 스케줄링 하는 것
• 과정
  • 전체 T만큼의 지분이 시스템의 모든 프로세스에게 할당된다
  • N 지분을 요청한 프로세스만이 승인된다(N<T)
  • 각 프로세스는 전체 처리기 시간의 N/T 만큼 할당 받는다.

POSIX 실시간 스케줄링

• SCHED_FIFO: FIFO 큐와 FCFS 정책을 사용하는 스케줄링
• SCHED_RR: 라운드로빈 방식을 사용하는 스케줄링

운영체제 사례들

• Linux 스케줄링: 선점형, 우선순위 기반, 항상 상수 시간이 걸리는 O(1) 스케줄링 사용, 높은 우선순위가 큰 시간 할당량 q를 받음
  • 완전 공정 스케줄러(Completely Fair Scheduler, CFS)
  • 실시간 프로세스의 우선순위는 변화 하지 않지만 (0~99)고정
  • 일반 프로세스의 우선순위 값은 변화한다. NICE (+100~+140)동적 (희생: 본인의 우선순위를 일부로 낮춤으로써 다른 프로세스가 먼저 실행 될 수 있도록 함)
  • 우선순위가 높은 프로세스는 가상시계를 통해(virtual run time) 적은 주기를 할당한다. 
  • 리눅스는 숫자가 작을 수록 우선순위가 높다.

• windows 스케줄링: 선점형, 우선순위 기반, 디스패처가 스케줄러이다, 가변클래스(1~15), 실시간 클래스(16~31) 총 32단계 우선순위 배열로 구성 
  • 숫자가 클수록 우선순위가 높다.
  • real-time (31~16)
  • high (15~1)
  • above normal (15~1)
  • normal(15~1)
  • below normal (15~1)
  • idle priority (15~1)

• Solaris 스케줄링: 우선순위 기반 스케줄링, 6개의 스케줄링 클래스
  • 숫자가 클수록 우선순위가 높다. 
  • Real time (RT): 우선순위 1
  • System (SYS): 우선순위 2
  • Time sharing (TS): 우선순위 3, 다단계 피드백 큐를 사용
  • Interactive (IA): 우선순위 3
  • Fair Share (FSS): 우선순위 3
  • Fixed priority (FP): 우선순위 3

알고리즘 평가

• 결정론적 모델링
  • 분석적 평가의 한 부류
  • 특정 부하를 미리 정해 놓고 그 부하에 대한 각 알고리즘의 성능을 측정한다
  • 결정론적 평가
    • 각 알고리즘에 대해 평균 대기 시간의 최소 값을 구한다.
    • 간단하고 빠르지만 정확한 입력 수치를 필요로 하고 단지 그 입력에 대해서만 해당된다는 점이다

큐잉 모델

• 프로세스의 도착과 CPU와 I/O 버스트를 확률적으로 설명한다.
  • 보통 지수 분포를 가정하여 평균으로 기술한다.
  • 평균 처리량, 이용률, 대기 시간 들을 계산한다.
• 컴퓨터 시스템은 서버의 네트워크로 볼 수 있으며 각 서버는 대기 프로세스를 넣을 큐를 가진다.

시뮬레이션

• 제한적인 큐잉 모델을 대신하기 위해 고려됨
• 컴퓨터 시스템의 프로그램 모델
• 과정
  • 확률에 기초한 랜덤 넘버 발생
  • 수학적 혹은 경험적으로 정의된 분포
  • 실제 시스템의 이벤트를 차례대로 기록한 추적 테이프