[OSTEP] Virtualization) 9. Lottery Scheduling

[OSTEP] 9. Lottery Scheduling

이 포스팅은 $<$Operating Systems: Three Easy Pieces$>$, Remzi H. Arpaci-Dusseau & Andrea C. Arpaci-Dusseau을 읽고 개인 학습용으로 정리한 글입니다.

CH 9. 비례 배분

• 비례 배분(Proportional Share) 혹은 공정 배분(fair share):
  반환 시간이나 응답시간을 최적화하는 대신 스케쥴러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적

1. 기본 개념

추첨권이 당신의 몫을 나타낸다

• 프로세스가 소유한 티켓의 개수와 전체 티킥에 대한 비율이 자신의 몫을 나타낸다
  (ex. A 75%, B 25%)

• 추첨 스케쥴링은 이러한 목적을 (타임 슬라이스가 끝날 때마다) 확률적으로 (하지만 결정적이지는 않게) 달성한다.

추첨 방식

• 스케쥴러는 전체 몇 장의 추첨권이 있는지 알아야만 한다
  (ex. 추첨권 100장)
• 스케쥴러는 추첨권을 선택한다
  (ex. 추첨권은 0~99의 숫자)
• 뽑힌 추첨권의 값에 따라 실행할 프로세스가 결정된다
  (ex. A 0~74, B 75~99)
• 스케쥴러는 당첨된 프로세스를 실행한다

• 원하는 비율 정확히 보장 X -> 두 작업이 장시간 실행될수록 원하는 비율 달성 가능성 높아짐

2. 추첨 기법

추첨권 화폐 (ticket currency)

• 사용자가 자신의 화폐 가치로 추천권을 자유롭게 할당할 수 있도록 허용
  -> 시스템은 자동적으로 화폐 가치를 변환

추첨권 양도(ticket transfer)

• 양도를 통하여 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다.

• 클라이언트 / 서버 환경에서 유용
  -> 클라이언트 프로세스 서버에게 메세지를 보내 자신을 대신해 특정 작업을 해달라고 요청
  -> 작업이 빨리 완료될 수 있도록 클라이언트는 서버에게 추첨권을 전달하고 자신의 요청을 수행하는 동안 서버의 성능을 극대화하려 함
  -> 요청을 완수하면 서버는 추첨권을 다시 클라이언트에게 돌려주고 먼저와 같은 상황이 된다
  

추첨권 팽창(ticket inflation)

• 프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘이거나 줄일 수 있음

• 프로세스들이 서로 신뢰하는 경우 (O)
  -> 어떤 프로세스가 더 많은 CPU 시간을 필요로 할 때 다른 프로세스들과 통신하지 않고 혼자 추첨권의 가치를 상향 조정하여 시스템에게 알릴 수 있음

• 서로 신뢰하지 않는 프로세스들이 상호 경쟁하는 경우 (X)
  -> 하나의 욕심 많은 프로세스가 매우 많은 양의 추첨권을 자신에게 할당하여 컴퓨터 장악할 수 있음

3. 구현

• 프로세스 리스트를 순회하며 counter 값이 winner 값을 초과할 때까지 각 추첨권의 개수를 counter에 더한다
  -> 값이 초과하게 되면 리스트의 현재 원소가 당첨자가 된다

예.

• 당첨 번호가 300인 경우 (counter = 0, winner = 300)
  -> A: counter = 100 < 300
  -> B: counter = 150 < 300
  -> C: counter = 350 > 300 당첨 프로세스

• 리스트 정렬 순서는 알고리즘의 정확성에 영향을 주지는 않는다
  -> 그러나 리스트를 내림차순으로 정렬하면 검색 횟수 최소화하여 효율적이다

4. 예제

• CPU를 공유하는 동일한 실행 시간을 갖는 두 개의 프로세스가 같은 개수의 추첨권을 가지는 경우
  -> 두 작업 거의 동시에 종료되어야 한다

• 불공정 지표(unfairness metric) U = 첫번째 작업이 종료된 시간 / 두번째 작업이 종료된 시간
  (완벽한 공정 스케쥴러에서 U = 1)
  

• 작업 길이가 같지 않은 경우, 평균 불공정도는 심각하다

• 작업이 충분한 기간동안 실행되어야 추천 스케쥴러는 원하는 결과에 가까워진다.

5. 추첨권 배분 방식

• 작업들에게 추첨권을 몇 개씩 배분해야 하는가?
  -> 미해결

• 사용자가 가장 잘 알고있다고 가정한다
  -> 각 사용자가 추첨권을 나누어 준 후 사용자가 알아서 실행시키고자 하는 작업들에게 배분
  

6. 왜 결정론적 방법을 사용하지 않는가

보폭 스케쥴링(stride scheduling)

• 결정론적 공정 배분 스케쥴러
• 시스템의 각 작업은 보폭을 가짐 -> 보폭은 추첨권의 수에 반비례
• 프로세스가 실행될 때마다 pass라는 값을 보폭만큼 증가시켜 얼마나 CPU를 사용하였는지 추적
• 스케쥴러는 가장 작은 pass를 가진 프로세스를 선택한다

• 추첨 스케쥴링: 정해진 비율에 따라 확률적으로 CPU 배분
  보폭 스케쥴링: 각 스케쥴링 주기마다 정확한 비율료 CPU 배분

• 왜 추첨 스케쥴링을 사용하는가:
  -> 추첨 스케쥴링에서는 프로세스의 상태 (CPU 사용 현황, pass 값)을 유지할 필요 X
  -> 새 프로세스를 추가할 때, 새로운 프로세스가 가진 추첨권의 개수, 전체 추첨권의 개수만 갱신하고 스케쥴한다.