[OS] 스케줄링: 비례 배분 (Proportional Share)

장선규·2023년 6월 29일
OSOSTEPProportional Sharescheduling가상화비례 배분스케줄링운영체제
0

[OS] OSTEP Study

목록 보기
6/28

비례 배분 (Proportional Share)

이번 장에서는 시간을 최적화 하는 것보다는, 작업의 비율 배분에 초점을 맞춘 스케줄러를 알아볼 것이다.

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

  • 추첨 스케줄링 (lottery scheduling)
    • 다음 실행될 프로세스를 추첨을 통해 결정
    • 더 자주 수행되어야 하는 프로세스는 더 높은 당첨 기회
    • 비례배분 스케줄러의 대표적인 예

핵심 질문: 어떻게 CPU를 정해진 비율로 배분할 수 있는가?

1. 기본 개념: Tickets Represent Your Share (추첨권 == 할당량)

추첨권(티켓): 프로세스가 할당받아야 할 자원의 몫

  • 예)
    • A는 75장의 추첨권, B는 25장의 추첨권을 가지고 있다.
    • 그러면 CPU 비율을 A: 75%, B: 25%로 가져가는 것이 목표

추첨 스케줄링은 이러한 목적을 확률적으로 달성함

  • 추첨 스케줄링은 각 작업의 CPU 비율에 대해서 목표 설정 (위의 예에서는 75%, 25%)
  • 각 타임 슬라이스별로 무작위로 추첨
    • 예를 들어 이런식으로 추첨 결과가 나옴
    • 추첨 번호 0~74는 A, 75~99는 B 임
    • 결과
    • A: 80%, B: 20%
  • 결과가 정확히 75:25가 되지는 않지만, 두 작업이 장시간 실행될 수록 원하는 비율을 달성할 가능성이 높아짐
  • 결정론적인 방식에 비해 좋은 점
    • 특이 상황에 잘 대응
    • 관리해야할 상태의 정보가 거의 없어 가벼움
    • 난수 발생만 빠르게 되면 결정도 빠름

참고로 추첨 스케줄링은 할당량을 "확률적"으로 달성한다.

  • 추첨권을 확률만큼 주고, 여러번 실행 시키면, 해당 확률에 수렴하게 됨
  • 정확히 75%, 25%가 나오지 않으나, 수렴함

결정론적(Deterministic)으로 할당시키는 방법은

  • 예를 들어, 3번 A 실행시키고 한번은 B 실행 <- 이를 반복

2. 추첨 기법

1) 추첨권 화폐(ticket currency)

사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당할 수 있도록 허용하는 기법.

  • 시스템은 자동적으로 화폐 가치를 반환함
  • 예)
    • 사용자 A, B 둘다 각각 100장의 추첨권 받음
    • 사용자 A는 작업 A1,A2 실행중, 자신이 정한 화폐로 각각 500장의 추첨권 할당함
      • A의 화폐 가치로는 500인데, 전역 기준으로는 50장으로 변환됨
    • 사용자 B는 B1 하나의 작업을 실행중이고, 자신이 정한 화폐 기준으로 10장 중 10장을 할당함
      • B의 화폐 가치로는 10인데, 전역 기준으로는 100장으로 변환됨

2) 추첨권 양도(ticket transfer)

프로세스가 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있는 기법

  • 클라이언트/서버 환경에서 유용
  • 클라이언트 프로세스는 서버에게 메시지를 보내 자신을 대신해 특정 작업을 해달라고 요청
    • 작업이 빨리 완료될 수 있도록 서버에게 추첨권도 같이 전달
  • 서버가 요청을 완수하면 추첨권을 다시 클라이언트한테 반환

3) 추첨권 팽창(ticket inlation)

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

  • 프로세스들이 서로 신뢰하는 환경에서 유용
    (서로 상호 경쟁하는 환경에서는 의미가 없음, 서로 팽창하려 할 것)
  • 특정 프로세스가 더 많은 CPU 시간을 필요로 하면, 시스템에 이를 알리고, 혼자 추첨권의 가치를 상향조정

3. 구현

구현이 간단하다.

// counter: 당첨자를 발견했는지 추적하는 데 사용됨
int counter = 0;

// winner: 0부터 총 추첨권의 수 사이의 임의의 값을 얻기 위해 난수 발생기를 호출함
int winner = getrandom(0, totaltickets);

// current: 작업 목록을 탐색하는 데 사용
node_t *current = head;

// 티켓 값 > winner를 만족할 때까지 반복
while (current)
{
    counter = counter + current->tickets;
    if (counter > winner)
        break; // 당첨자 발견
    current = current->next;
}
// "current" 는 당첨자를 가리킴: 당첨자가 실행될 수 있도록 준비
  • 당첨 번호 winner를 랜덤으로 추출
  • 작업의 목록을 순회
    • counter에 현재 가리키고 있는 작업이 가지고 있는 추첨권의 개수를 누적합
    • 만약 누적합 counter가 winner보다 커지면 당첨!
    • 루프를 빠져나와 순회 종료
  • 만약 위의 경우에서 winner가 300이라면
    • 처음엔 A 가리키고 counter = 100
    • B 가리키고 counter = 150
    • C 가리키고 counter = 400 -> 당첨자 발견

일반적으로 리스트가 내림차순으로 정렬했을 때 가장 효율적이게 됨
(추첨권 많은 순으로 앞에 위치, 그녀석들이 당첨될 확률이 높은 것은 당연)

4. 예제 (추첨권 배분 방식의 공정성 분석)

예를 들어 두개의 작업(A,B)이 같은 개수의 추첨권을 가지고 있고, 실행 시간(R)도 같다고 하자.

목표: 두 작업을 거의 동시에 종료시키는 것
불공정 지표(U) = (첫 작업 종료시간) / (두번째 작업 종료 시간)

작업의 길이가 1일 때

  • A(완) B(완) -> U = 1/2 = 0.5

작업의 길이가 2일 때

  • A A(완) B B(완) -> U = 2/4 = 0.5
  • A B A(완) B(완) -> U = 3/4 = 0.75
  • B A B(완) A(완) -> U = 3/4 = 0.75
  • B B(완) A A(완) -> U = 2/4 = 0.5
    => 평균 U = (0.5+0.75)/2 = 0.675

이런식으로 작업의 길이를 늘려가면 동시에 끝날 확률이 점점 늘어난다. 즉, 불공정 정도가 1에 가까워지며 균등하게 작업이 배분이 된다.

따라서 작업시간이 충분히 길어야 추첨 스케줄러가 원하는 결과에 가까워진다는 것을 알 수 있다.

5. 추첨권 배분 방식

그렇다면 추첨권은 작업에게 어떻게 분배해야 하는가?

  • 사용자가 알아서? 이것은 해결책이 아님..

-> "추첨권 할당 문제"는 미해결 문제

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

무작위성을 이용한 스케줄러는 단순하고, 나름 정확하다.
하지만 정확한 비율은 보장할 수 없고, 짧은 기간만 실행되는 경우 더 그렇다.
따라서 결정론적 공정 배분 스케줄러인 "보폭 스케줄링"이 고안되었다.

보폭 스케줄링(stride scheduling)

  • 결정론적 공정 배분 스케줄러
  • 각 작업은 보폭을 가지고 있고, 보폭은 자신이 갖고있는 추첨권 수에 반비례함
    • A(100) B(50) C(250)의 추첨권을 가지고 있음
    • 그러면 보폭은 임의의 큰 값을 각자의 추첨권 개수로 나누어 계산 가능 (큰 값은 10000이라고 하자)
      A(추첨권:100, 보폭:100)
      B(추첨권:50, 보폭:200)
      C(추첨권:250, 보폭:40)
  • 보폭(stride)은 프로세스가 실행될 때마다 pass라는 값을 보폭만큼 증가시켜 얼마나 CPU를 사용했는지를 추적
  • 스케줄러는 보폭과 pass 값을 가지고 어느 프로세스를 실행시킬지 결정
    • 가장 작은 pass값을 가진 프로세스 선택
    • 프로세스를 실행시킬 때마다 pass값을 보폭만큼 증가시킴
    • 의사코드
      current = remove_min(queue);      // pass 값이 최소인 작업 선택
schedule(current);                // 자원을 타임 슬라이스만큼 선택된 프로세스에게 전달
current->pass += current->stride; // 다음pass값을 보폭 값을 이용하여 갱신
insert(queue, current);           // 다시 큐에 저장
  • 보폭 스케줄링 추척 (아까 전 ABC)
    • pass 같은 경우 아무거나 실행 가능
    • 모든 pass가 다시 같아지는 시점에서,
      A 2번, B 1번, C 5번 실행됨
    • 이는 추첨권의 개수 100, 50, 250과 정확히 비례함

보폭 스케줄링은 각 스케줄링 주기마다 정확한 비율로 CPU를 배분한다.

그럼 왜 추첨 스케줄링을 쓰는지?

  • 추첨 스케줄링은 상태 정보를 유지할 필요가 없음
  • 보폭 스케줄링에서는 새 프로세스가 오면 pass값이 얼마가 되어야 하는지 정해야됨 (0이면 당분간 독점할 것)

7. 요약

비례 배분 스케줄링: 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것

  • 추첨 스케줄링
    • 무작위성을 이용하여, 추첨권이 많은 작업이 실행될 확률이 높은 스케줄링 방식
    • 추첨권(티켓): 프로세스가 할당받아야 할 자원의 몫
  • 보폭 스케줄링
    • 결정적 방법으로, 각 작업에게 CPU의 일정 비율을 보장하는 스케줄링 방식
  • 두 방식 모두 입출력과 맞물렸을 때, 제대로 동작하지 않아 많이 사용되지 않음
  • 추첨권을 어떠한 기준으로 얼마나 할당하는 것에 대한 문제가 미해결
profile
장선규
코딩연습
이전 포스트

[OS] 스케줄링: Multi-level Feedback Queue

다음 포스트

[OS] 멀티프로세서 스케줄링

0개의 댓글