Proportional Share Scheduling

비례 배분 또는 공정 배분 스케줄러

• 각 프로세스의 지분에 따라 CPU 시간 배분
• 지분 근거? - 우선 순위, 지불 금액 등
• 실제 사레 : 가상 머신, 클라우드, RT 시스템, 멀티프로세서 등 지분 결정이 쉬운 환경

개념

• 각 프로세스가 가진 “지분”에 따라 CPU 시간을 공정하게 나누는 방식
• 공정성 : 내가 받아야 할 몫을 제대로 받는가?
• 지분 기준 : 우선순위, 지불 금액, 사용자 요청 등

Lottery Scheduling (복권 스케줄링)

• 전체 추첨권 대비 자기 추첨권의 비율(%)로 표시

  • A 가 25장, B 가 75장
  • CPU 사용권 75% 25%

• 랜덤하게 뽑음 (무작위)

  • 정확히 %로 떨어지지 않음

• 추첨권 화폐

  • 각 사용자는 자신의 화폐 기준으로 각 작업에 추첨권 할당
    • 시스템이 전역 화폐 가지초 변환

  

• 추첨권 양도

  • 일시적으로 다른 작업에게 추첨권 양도(서버에서 주로 사용)
  • priority inversion(우선순위 역전)을 해결할 수 있음
    • 일시적으로 lock을 가지고 있는 우선순위가 낮은 프로세스에게 추첨권을 양도해, lock을 빨리 풀도록 함

• 추첨권 팽창

  • 추첨권 수의 일시적인 증가 또는 감소

• 불공정함

  • U = C1 / C2
  • C1 : 일찍 끝난 작업의 완료 시간
  • C2 : 늦게 끝난 작업의 완료 시간
  • ex) 실행시간 10인 두 개의 작업에 대해
    • C1 = 10, C2 = 20 → U = 0.5 (나쁨)
    • C1 = 20, C2 = 20 → U = 1(좋음)
    • 1에 가까워질수록 좋음

Stride Scheduling (보폭 스케줄링)