[운영체제]스케줄링:비례 배분

비례 배분이란 반환 시간이나 응답 시간을 최적화하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적이다.

비례 배분의 좋은 예는 추첨 스케줄링이다. 기본적인 아이디어는 다음 실행될 프로세스를 추첨을 통해 결정하는 방식이다. 더 자주 실행되어야 하는 프로세스는 당첨 기회를 더 많이 준다. 

핵심적인 문제는 어떻게 CPU를 정해진 비율로 배분할 것인가이다.

 

추첨 스케줄링에 있어서 추첨권은 중요한 근간이 된다. 추첨권으로 프로세스는 받아야할 자원의 몫을 나타낸다. 프로세스가 소유한 추첨권의 양과 전체 추첨권의 비율로 몫을 나타낼 수 있다.

예를 들어 A는75장, B는 25장 소유하고 있다. A에게는 75%의 CPU를, B에게는 25%의 CPU를 할당한다.

A가 0~74까지의 추첨권을 가지고 있고, B는 75~99까지의 소유권을 가지고 있다. 스케줄러는 무작위적으로 하나의 소유권을 뽑아 다음 스케줄을 결정한다. 스케줄러가 20개의 추첨권을 뽑았을 때, B의 비율이 20%가 나왔다. B에게는 25%가 할당되어야 맞다. 하지만 시간이 지나 더 많은 추첨권을 뽑으면 B의 확률은 더 올라갈 가능성이 높아진다.

 

무작위성

무작위적 방식에는 3가지의 장점이 있다.

1.전통적인 방식이 해결하지 못하는 특이 상황을 잘 대응한다.

LRU는 좋은 교체 알고리즘이지만 반복되는 순차적인 접근 패턴을 보이는 오버헤드에 대해서는 최악의 성능을 보인다. 반면 무작위 방식에서는 그러한 최악의 경우가 발생하지 않는다.

 

2.무작위 추첨 방식은 가볍다.

관리해야 할 상태 정보가 거의 없기 때문에 프로세스의 상태 정보(프로세스가 가진 추첨권의 개수)만 알면 된다.

 

3.무작위 추첨 방식은 빠르다.

난수 발생 시간이 빠르기만 하면 빠르게 결정 된다.

 

추첨 기법

추첨권을 다루는 다양한 기법이 있다. 추첨권 화폐에 대해 알아보자. 추첨권 화폐는 사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당할 수 있도록 허용한다.  

예를 들어 A와B에게 각각 100장의 추첨권이 있다고 가정하자. A는 A1,A2 작업에 각각 자신의 화폐 단위로 각각 500장 씩 할당 하였다.(시스템 내에서 자동적으로 변환해준다.)B는 자신의 화폐 단위로 10장 중 10장을 할당하였다. 

시스템은 A1과 A2의 몫을 A의 기준 화폐 500장에서 전역 기준 화폐 각각 50장으로 변환한다(처음에 받은 100장으로 변환됨). B의 추첨권 10장은 시스템에 의해 100장으로 변환된다(처음에 받은 100장으로 변환됨). 

 

추첨권 양도

양도를 통해 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다. 클라이언트/서버 환경에서 유용하다.

클라이언트 프로세스는 서버에게 메세지를 보내 자신을 대신해 특정 작업을 해달라고 요청한다. 작업이 빨리 완료될 수 있도록 클라이언트는 서버에게 추첨권을 전달하고 서버가 자신의 요청을 수행하는 동안 서버의 성능을 극대화하려 한다. 요청이 완료되면 서버는 추첨권을 다시 클라이언트에게 되돌려준다.

 

추첨권 팽창

프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘리거나 줄일 수 있다. 물론 프로세스들이 경쟁하는 상황에서는 의미가 없다. 프로세스들이 서로 신뢰하는 상황에서는 유용하다. 어떤 프로세스가 더 많은 CPU 시간이 필요하다면 시스템에 이를 알리고 추첨권의 가치를 상향 조정한다.

 

추첨 스케줄링 구현

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

typedef struct _ele{
    int data;
    struct _ele * next;
}Ele;

typedef struct _node{
    Ele * head;
    Ele * tail;
    Ele * cur;
}Node;

void LInit(Node *pn){
    pn->head = NULL;
    pn->tail = NULL;
}

int Random(){
    int winner;    //당첨된 랜덤 값
    winner = rand() % 100;

    return winner;
}

void LInsert(Node *pn,int data){
    Ele * newNode = (Ele*)malloc(sizeof(Node));
    
    newNode->data = data;

    if(pn->head == NULL){
       pn->head = newNode;
       printf("%d is inserted\n",newNode->data);
    }
    else{
        pn->tail->next = newNode;
        printf("%d is inserted\n",newNode->data);
    }
    pn->tail = newNode;
}

void LDelete(Node *pn){
    Ele * rpos = pn->cur;
    if(pn->head == NULL)
        printf("출력 완료\n");
    else{
        pn->cur = pn->head;
        printf("%d ",pn->cur->data);
        
        while(pn->cur->next != NULL){
            pn->cur = pn->cur->next;
            printf("%d ",pn->cur->data);
        }
    }
    free(rpos);
}

int main(){
    Node n1;
    srand(time(NULL));
  
    LInit(&n1);

    LInsert(&n1,Random());
    LInsert(&n1,Random());
    LInsert(&n1,Random());
    LInsert(&n1,Random());

    LDelete(&n1);
    
}