🚪 들어가며

비례 배분(Proportional Share) 스케줄러

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

추첨 스케줄링(lottery scheduling)

비례 배분 스케줄링 중 하나로, 다음 실행될 프로세스를 추첨을 통해 결정한다. 더 자주 수행되어야 하는 프로세스에게 당첨 기회를 더 많이 주는 방식이다.

1️⃣ 기본 개념: 추첨권 = 나의 몫

추첨권(티켓): 추첨 스케줄링의 근간을 이룸.

추첨권은 프로세스가 받야야 할 자원의 몫을 나타내는 데 사용

예시) 프로세스 A가 75장의 추첨권, B가 25장의 추첨권을 가지고 있는 상황
➡️ A에게 75%, B에게 25%의 CPU를 각각 할당하는 것이 목적

추첨 스케줄링은 이러한 목적은 타임 슬라이스가 끝날 때마다 확률적으로(결정적X) 달성

🎯 무작위성의 이용: 추첨 스케줄링의 장점
[장점 1] 전통적인 방식이 잘 해결하지 못하는 특이 상황에 잘 대응
[장점 2] 매우 가벼움(관리해야 할 상태 정보가 거의 없기 때문)
[장점 3] 매우 빠름(난수 발생 시간이 빠르기만 하다면)

스케줄러는 전체 몇 장의 추첨권이 있는지 알아야 한다.
다음 예시를 통해 이를 알아보자.

추첨권은 0 - 99의 숫자이며 프로세스 A가 0 - 74의 추첨권을, B가 75 - 99의 추첨권을 가지고 있다고 가정하자.

63 85 70 39 76 17 29 41 36 39 10 99 68 83 63 62 43 0 49 49

이에 따른 스케줄링 결과는 다음과 같다.

A B A A B A A A A A A A B A B A A A A A

여기서 우리는 무작위성은 원하는 비율을 정확히 보장하지는 않는다는 것을 알 수 있다.(예시에서 A는 80%, B는 20%의 타임 슬라이스를 획득) 하지만, 두 작업이 장시간 실행될수록, 원하는 비율을 달성할 가능성이 높아진다.

2️⃣ 추첨 기법

추첨권 화폐(ticket currency)

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

시스템은 자동적으로 화폐 가치를 변환한다.

다음의 예시와 함께 이를 알아보자.

사용자 A, B가 시스템으로부터 100장의 추첨권을 받았다고 가정하자.
사용자 A는 실행 중인 두 개의 작업 A1, A2에 자신이 정한 화폐 총 1000장 중 각각 500장 씩을 할당하고, B는 실행 중인 하나의 작업 B1에 자신의 정한 화폐 총 10장 중 10장 모두를 할당한 상황이다.

User A → 500 (A's currency) to A1 → 50 (global currency)
       → 500 (A's currency) to A2 → 50 (global currency)
User B → 10 (B's currency) to B1 → 100 (global currency)

즉, 각자가 정한 화폐를 시스템이 전역 화폐로 변환하고 전역 추첨권 화폐량(예시에서는 총 200장)을 기준으로 추첨을 진행한다.

추첨권 양도(ticket transfer)

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

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

추첨권 팽장(ticket inflation)

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

이 기법은 프로세스들이 서로 신뢰할 때 유용
➡️ 상호 경쟁하는 경우 특정 프로세스가 매우 많은 양의 추첨권을 자신에게 할당하여 컴퓨터를 장악할 수 있기 때문

어떤 프로세스가 많은 CPU 시간이 필요한 경우
➡️ 다른 프로세스들과 통신하지 않고 시스템에게 이를 알려 혼자 추첨권의 가치를 상향 조정

3️⃣ 구현

추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 점

필요한 것: 난수 발생기, 프로세스들의 집합을 표현하는 자료 구조(리스트 등), 추첨권의 전체 개수

다음의 예시와 함께 살펴보도록 하자.

HEAD → [A | Tix: 100] → [B | Tix: 50] → [C | Tix: 250] → NULL

A, B, C 세 개의 작업이 있고 Tix는 각각의 작업이 가진 추첨권의 개수를 의미한다.

다음은 추첨 스케줄링 결정 코드이다.

// 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"는 당첨자를 가리킴: 당첨자가 실행될 수 있도록 준비

스케줄을 결정하기 위해 먼저 총 추첨권의 개수 중 한 숫자를 선택해야 하는데, 300이 선택되었다고 가정하자. 다음과 같은 과정을 거쳐 당첨자 프로세스를 선택하게 된다.

1. winner에 무작위로 총 추첨권 개수 범위 내에서 추첨권 개수를 저장한다.

2. 프로세스 리스트를 순회하며 프로세스가 가진 추첨권 개수를 counter에 더해나간다.

3. counter 값이 winner 값을 초과하면 해당 프로세스를 선택하고 순회를 마친다.

일반적으로 리스트를 내림차순으로 정렬하면 이 과정이 가장 효율적이 된다.
➡️ 검색 횟수가 최소화되는 것을 보장
➡️ 특히, 적은 수의 프로세스가 대부분의 추첨권을 소유하고 있는 경우에 효과적

4️⃣ 예제

두 개의 프로세스가 각각 100개의 추첨권을 갖고 동일한 실행 시간(R)을 갖는 상황을 가정하자.

목표: 두 작업을 거의 동시에 종료
➡️ 추첨 스케줄링의 무작위성 때문에 한 작업이 다른 작업보다 먼저 종료될 수 있음.

불공정 지표(unfairness metric)

위의 차이를 정량화하기 위한 불공정 지표 U를 정의한다.

U = 첫 번째 작업이 종료된 시간 / 두 번째 작업이 종료된 시간

R = 10, 첫 번째 작업은 시간 10, 두 번째 작업은 시간 20에 종료한 경우, U = 10/20 = 0.5이다.

두 작업이 거의 동시에 종료하면 U는 1에 근접해진다. ➡️ 목표

         1.0 ┐---------------------------------
             │                      * ********
             │              * ****** *
         0.8 ┤        ****** *
             │      **
             │   ***
         0.6 ┤ **
Fairness     │*
             │
         0.4 ┤
             │
             │
         0.2 ┤
             │
             │
         0.0 ┼──────────┬──────────┬──────────┬
             1          10         100        1000
                          Job Length

위의 그래프는 평균적인 불공정 정도를 보이고 있다.
※ OSTEP 서적 상에서 두 작업의 수행 시간을 1에서 1000까지 변경시키며 30번씩 실행시킨 결과를 토대로 생성한 그래프를 비슷하게 옮겨놓은 것이다.

그래프를 통해 다음과 같은 사실을 알 수 있다.
작업의 길이가 길지 않은 경우 ➡️ 평균 불공정정도 심각함.
작업이 충분한 기간동안 실행 ➡️ 추첨 스케줄러는 원하는 결과에 가까워짐.

5️⃣ 추첨권 배분 방식

작업들에게 추첨권을 몇 개씩 분배해야 하는가?
➡️ 시스템 동작이 추첨권 할당 방식에 따라 크게 달라지기 때문에 어려운 문제

[접근 방식 1] 사용자가 가장 잘 알고 있다고 가정

이는 각 사용자에게 추첨권을 나누어 준 후 사용자가 알아서 실행시키고자 하는 작업들에게 추첨권을 배분하는 것

But, 어떤 일을 해야 하는지 제시하지 않음. ➡️ [접근 방식 1]은 해결책이 아님.

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

무작위성의 이용 ➡️ 스케줄러를 단순하며 어느 정도 정확하게 만들 수 있지만 정확한 비율 보장X

보폭 스케줄링(stride scheduling)

Waldspurger가 고안한 결정론적 공정 배분 스케줄러

시스템의 각 작업은 보폭을 가지고 있음.
➡️ 보폭: 자신이 가지고 있는 추첨권 수에 반비례하는 값

임의의 큰 값을 각자의 추첨권 개수로 보폭을 계산할 수 있음.

다음의 예시와 함께 이를 알아보자.

3️⃣의 예시처럼 작업 A, B, C가 각각 100, 50, 250의 추첨권을 가지고 있는 경우, 임의의 큰 값인 10,000을 각자의 추첨권 개수로 나누어 100, 200, 40의 보폭을 얻을 수 있다.

프로세스가 실행될 때마다 pass라는 값을 보폭만큼 증카시켜서 얼마나 CPU를 사용했는지 추척한다.

다음은 Waldspurger가 작성한 의사코드이다.

current = remove_min(queue); // pass 값이 최소인 클라이언트로 선택
schedule(current); // 자원을 타임 퀀텀만큼 선택된 프로세스에게 할당
current−>pass += current−>stride; // 다음 pass 값을 보폭 값을 이용하여 갱신
insert(queue, current); // 다시 큐에 저장한다

처음 세 작업의 pass 값은 모두 0에서 시작한다.
➡️ pass 값이 모두 같으므로 아무 프로세스나 실행될 수 있음.

다음을 통해 이 규칙에 따라 각 프로세스가 타임 슬라이스만큼 실행되고 종료될 때 각 작업의 pass 값들이 갱신되는 모습을 확인할 수 있다.

A[stride=100] │  100   100   100   100   100   200   200   200
B[stride=200] │  0     200   200   200   200   200   200   200
C[stride=50]  │  0     0     40    80    120   120   160   200
              └──┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────
                 A     B     C     C     C     A     C     C ...
              시간의 흐름 →

위에서 알 수 있듯, C는 5번, A는 2번, B는 1번 만 실행되었다.
➡️ 실행 횟수가 각자의 추첨권 개수 250, 100, 50과 정확히 비례

추첨 스케줄링 ➡️ 정해진 비율에 따라 확률적으로 CPU 배분

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

보폭 스케줄링의 정확도를 고려할 때 왜 추첨 스케줄링을 사용하는가?

추첨 스케줄링은 보폭 스케줄링과 다르게 상태 정보가 필요 없다.

위 보폭 스케줄링의 예에서 중간에 새로운 작업이 시스템에 도착한 경우
➡️ 새로운 작업의 pass 값을 0으로 지정하는 경우 CPU 독점

추첨 스케줄링의 경우 새 프로세스를 추가할 때 새로운 프로세스가 가진 추첨권의 개수, 전체 추첨권의 개수만 갱신하고 스케줄한다.
➡️ 새 프로세스를 쉽게 추가할 수 있음.

🧺 비례 배분 스케줄링 내용 정리

추첨 스케줄링 ➡️ 무작위성(randomness) 사용

보폭 스케줄링 ➡️ 결정적 방법 사용

둘 다 CPU 스케줄러로서 널리 사용되고 있지 않음.
[이유 1] 위의 접근 방식이 특히 입출력과 맞물렸을 때 제대로 동작하지 않음.
[이유 2] 추첨권 할당 문제

추첨권 할당량을 비교적 정확하게 결정할 수 있는 환경에서 유용하게 사용
예시) 가상화 데이터 센터에서 Windows 가상 머신에 CPU 사이클의 1/4을 할당하고 나머지는 Linux 시스템에 할당하고 싶은 경우

📚 참고 문헌

Operating Systems: Three Easy Pieces ― 9: Scheduling: Proportional Share

운영체제 아주 쉬운 세 가지 이야기 ― 12: 스케줄링: 비례 배분