[OSTEP] Virtualization) 9. Lottery Scheduling

sunjoo9912·2022년 3월 26일
0

OSTEP 운영체제

목록 보기
6/17
post-thumbnail

[OSTEP] 9. Lottery Scheduling

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
    -> 새 프로세스를 추가할 때, 새로운 프로세스가 가진 추첨권의 개수, 전체 추첨권의 개수만 갱신하고 스케쥴한다.

profile
✧°₊·♡∗ˈ‧₊

0개의 댓글