Propotional Share

Propotional Share

반환시간, 응답시간 최적화 대신 각 작업에게 CPU의 일정비율을 보장하는 것이 목적

ex) 추첨 스케줄링 (lottery scheduling)
말그대로 추첨을 통해 실행될 프로세스 결정
더 자주 실행되어야 하는 프로세스는 당첨기회 더 많이 줌
-> 장시간 실행시 원하는 비율을 보장하게 됨

추첨 기법

무작위 방식을 이용

1. ticket currenncy (추첨권 화폐)
   추첨권을 자유롭게 할당함

2. ticket transfer (추첨권 양도)
   프로세스는 일시적으로 다른 프로세스에게 추첨권을 넘길 수 있음
   ex) 서버-클라이언트 환경에서 유용

3. ticket inflation (추첨권 팽창)
   프로세스는 자신이 가진 추첨권의 수를 늘리거나 줄일 수 있음
   (프로세스 서로 신뢰한다는 가정하)

---

초반에는 확률적인 원리에 따라 비율을 보장하기가 힘들다...

stride scheduling (보폭 스케줄링)

결정적 방식으로..

각 작업은 stride(보폭)을 가짐 (추첨권의 수에 반비례하는 값)
프로세스가 실행될 떄마다 pass라는 값을 보폭만큼 증가시켜 얼마나 CPU를 사용했는가 추적

리눅스 CFS (Completely Fair Scheduler)

동적 타임 슬라이스를 가진 가중치 라운드 로빈 기법

virtual runtime(vruntime) 이용
실행되는 동안 vruntime 누적시킴
가장 낮는 vruntime 우선 실행

시간간격은 어떻게 조절하는가?

• 기본 연산

1. sched-latency 변수
   -> 하나의 프로세스가 cpu를 사용한 후 다시 사용할 수 있을 때까지의 최대 시간간격

   보통은 48ms, 이를 프로세스 개수로 나누어 time slice 결정
   

2. min_granularity 변수
   최소 타임 슬라이스
   보통은 6ms

• Niceness
  사용자나 관리자가 우선순위 조정가능
  nice 레벨 부여를 통해
  0이 기본값, -20부터 19까지 가능
  19가 가중치가 낮은것임..(친절하면 양보한다는 느낌)

  CFS는 nice에 weight 값을 대응시켜놓음

  time_slice(k) = weight(k)/전체 weight 합 *schedule_latency
  이 가중치로 time slice 길이를 구할 때 사용됨

  runtime(k) = runtime(k) + weight0/weight(k) * runtime(k)
  이를 이용하여 weight와 반비례하게 vruntime을 구할 수 있음