[OS] Lottery Scheduling (추첨 스케줄링)

운영체제 스터디를 진행하던 중 갑작스레 기술 블로그를 시작하는 것이 좋겠다는 생각이 들어 이렇게 첫 글을 작성합니다. 부족한 점이 있다면 언제든지 피드백해주시면 정말 감사드리겠습니다.

먼저 제가 앞으로 작성해나갈 OS 시리즈는 Remzi 교수님의 Operating Systems: Three Easy Pieces 책에 기반하여 작성한다는 점을 사전에 말씀드리며 해당 책의 링크는 다음과 같습니다.
OSTEP 교재 링크

Proportional Share Scheduling의 기본 개념

본 노트에서는 운영체제의 핵심 구성 요소 중 하나인 프로세스 스케줄러, 특히 Proportional Share 스케줄러 (Fair Share 스케줄러)에 대해 다루고자 합니다. 이 스케줄러는 기존의 FCFS(First-Come, First-Served), SJF(Shortest Job First), RR(Round Robin) 등과는 다른 접근 방식을 취합니다.

Proportional Share 스케줄러의 주요 목표는 시스템 자원, 특히 CPU 시간을 각 프로세스에 일정한 비율로 공정하게 분배하는 것입니다. 이는 기존 스케줄링 알고리즘들이 주로 반환 시간($T_{\text{turnaround}}$)이나 응답 시간 ($T_{\text{response}}$)의 최적화에 중점을 둔 것과는 대조적입니다. 그 중에서도 먼저 이 포스트에선 Proportional Share 스케줄러의 좋은 예시인 추점 스케줄링에 대해서 알아보도록 하겠습니다.

Lottery Scheduling

기본 아이디어는 이름과 잘 어울리게 각 프로세스에 추첨권을 할당하고 다음 프로세스를 추첨하는 것입니다. 이 때 더 자주 수행되어야 하는 프로세스에는 가중치를 더 많이 줘서 다음 번에 실행될 확률을 높이는 방식을 택한다고 합니다.

예를 들어, A와 B라는 프로세스가 있다고 가정해보겠습니다. A 에게는 80장의 추첨권을, B에게는 20장의 추첨권이 할당되어 있습니다. 이 때, 스케줄러는 A에게 80%의 비율, B에게는 20%의 비율로 CPU를 점유할 수 있는 기회를 주고자 하는 것이 이 스케줄러의 목적이라고 볼 수 있습니다.

추첨 방식은 간단합니다. 스케줄러는 총 추첨권의 갯수를 알고 있는 상황에서 (위 예시에선 100장) 추첨권을 랜덤으로 선택하게 됩니다. 이 때 추첨권은 0~99 사이의 정수입니다. A는 0~79, B는 80~99의 추첨권을 가지고 있다고 한다면 (추첨이 uniform하게 된다는 가정하에...) 뽑힌 추첨 값에 따라 만약 랜덤으로 선택된 숫자가 0~79 사이라면 다음으로 실행할 프로세스를 A로, 나머지 80~99 사이의 숫자가 생성되었다면 다음으로 실행할 프로세스는 B로 결정됩니다. 이처럼 실행할 프로세스가 확률적으로 결정되는 것이 Lottery Scheduling의 추첨 방식입니다. 예시는 다음과 같습니다.

선택된 추첨권
63 85 70 39 76 17 29 41 36 39 10 99 68

추첨 결과 
A B A A A A A A A A A B A

위 결과를 보면 알 수 있듯이, 프로세스 A에게 약 85%, B에게 약 15%의 CPU 시간이 점유되었습니다. 이는 원래의 목표와 거리가 있긴 하지만 이 작업이 장시간으로 실행될수록, 초기에 설정한 비율에 도달할 가능성이 높아진다고 합니다.

Lottery Scheduling 구현

추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 점입니다. 난수 발생기와 각 프로세스와 할당된 추첨권의 갯수를 나타낼 수 있는 연결 리스트 (Linked List), 그리고 총 추첨권의 갯수입니다. C++로의 구현은 아래의 코드를 참고해주세요. \
간략하게 코드를 요약하자면 각 연결 리스트의 노드를 프로세스로 생각하고 추첨권을 할당해줍니다. 그리고 반복문을 돌면서 0과 총 추첨권 갯수 사이의 정수 타입의 난수를 발생시키고 해당 난수가 노드를 순회하며 할당된 추첨권의 범위 안에 들어가면 해당 프로세스를 선택하는 방식으로 구성되어 있습니다.

#include <iostream>
#include <stdlib.h>
#include <random>

int assigned_tickets = 0;

struct node_t {
    int tickets; 
    struct node_t *next;
};

struct node_t *head = NULL;

void insert(int tickets) { 
    node_t *tmp = (node_t*)malloc(sizeof(struct node_t));
    tmp -> tickets = tickets;
    tmp -> next = head;
    head = tmp; 
    assigned_tickets += tickets;
}

int main() {
    insert(50); 
    insert(100);
    insert(25);
    char process_names[] = {'A', 'B', 'C'};

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(0, assigned_tickets);

    for (int i = 0; i < 100; ++ i) {
        int index = 0;
        int winner = dis(gen);
        int counter = 0;
        
        struct node_t *current = head;
        while(current) {
            counter += current -> tickets;
            if (counter > winner) break;
            current = current -> next;
            index ++;
        }   
        std::cout << "winner: " << winner << " Process " << process_names[index] << std::endl;
    }   
}

추첨 스케줄링을 위와 같이 Linked List를 통해 간단하게 구현할 수 있지만 추첨권을 다루는 방법에는 다양한 것이 존재한다고 합니다. 다음 챕터에서는 이 다양한 기법에 대해서 다루겠습니다.

추첨 기법

이 챕터에서는 여러가지 추첨 기법에 대해 간략하게 설명하고 넘어가도록 하겠습니다.

Ticket Currency

Ticket Currency는 하나의 프로세스 안에 여러 개의 쓰레드가 있을 때 유용하게 사용할 수 있습니다. 이 개념은 추첨권을 프로세스 안에서 해당 프로세스에 할당된 범위 내에서 자유롭게 쓰레드에 할당할 수 있도록 허용하는 것을 의미합니다.

예를 들면, 프로세스 A, B가 각각 100장의 추첨권을 받았다고 가정해보겠습니다. A 프로세스 안에서 총 1000장의 추첨권이 내부적으로 있다고 추가로 가정을 하고 A1과 A2에 각각 500장의 추첨권을 할당하였습니다. 글로벌 시스템에서는 이 500장의 추첨권을 글로벌 화폐 가치로 변환하여 결과적으로 아래의 그림과 같이 A1과 A2에 각각 50장의 추첨권이 할당된다고 해석할 수 있습니다.

Ticket transfer

하나의 프로세스는 본인이 가지고 있는 추첨권을 다른 프로세스에게 양도를 통해 일시적으로 넘겨줄 수 있습니다. 이는 서버 클라이언트 환경에서 특히 유용하다고 합니다. 예를 들어, 클라이언트 프로세스는 서버에게 메시지를 보내 클라이언트를 대신하여 서버에게 특정 작업을 수행해달라고 요구할 수 있는데 이 때, 클라이언트는 작업이 빠르게 완료될 수 있도록 서버에게 추첨권을 양도할 수 있습니다.

Ticket Inflation

어떤 프로세스가 CPU 점유를 많이 해야하는 상황이라면 본인의 티켓의 가치를 상향 조정할 수 있는데 이를 Ticket Inflation 이라고 부릅니다. 아무래도 이 기법은 한 프로세스의 CPU 장악 가능성을 초래하기 때문에 프로세스들이 서로 경쟁하지 않고 신뢰하고 있는 상황에서 유용하게 쓰인다고 합니다.

요약

이 블로그 포스트에서는 운영체제의 프로세스 스케줄러 중 하나인 Proportional Share 스케줄러, 특히 Lottery Scheduling (추첨 스케줄링)에 대해 다루었습니다. 요약하자면 추첨 스케줄링 기법은 프로세스들의 할당을 공정하게 배분하기 위해 랜덤 추출에 의한 추첨에 기반하였으며 더 많은 CPU 시간이 필요한 프로세스에 더 많은 추첨권을 할당하여 확률을 높이는 방식으로 동작합니다. 이에 대한 구현 예시는 간단하다는 장점이 있었고, 세부 추첨 기법에는 Currency, Transfer, Inflation이 있었습니다. 다음 포스트에서는 Address Translation의 원리에 대해서 다루도록 하겠습니다. 끝까지 읽어주셔서 정말 감사드리며 댓글과 피드백은 언제든지 환영입니다 🙇‍♂️