우선순위 알고리즘

우선순위 알고리즘

프로세스마다 우선순위를 부여해 우선순위가 높은 프로세스를 먼저 실행시키는 방식이다.

가령 A프로세스가 B프로세스 보다 높은 우선순위를 가진다고 한다면 일반적으로 생각해 봤을 때 A프로세스가 어느정도 실행이되고, B프로세스 또한 어느정도 실행된다고 생각할 수 있다. 하지만 보편적인 운영체제에서 B프로세스는 실행이 되지 않는다. 이 상태를 기아상태라고한다.

그렇다면 반대로 일반적으로 생각하는 것이 맞다면 A와 B프로세스가 단순히 임의의 메시지를 출력하낟고 한다면 I/O 작업을 하는 과정에서 낮은 우선순위르 프로세스가 실행될 수 있다.

이와 같은 상태에서 기아상태가 발생하는 것은 매우 드문일이다.

라운드로빈 알고리즘

그렇다면 우선순위가 같은 경우 어떤 프로세스를 먼저 실행시켜야 할까? 프로세스의 형평성을 위해서 라운드 로빈 알고리즘을 사용한다. 형평성을 위해서 정해진 시간만큼 실행하고 다른 프로세스에 넘겨준다. 이렇게 정해진 시간을 퀀텀 혹은 타임 슬라이스라고 부른다. 타임 슬라이스가 길면 마우스로 드래그 앤 드롭하는 것이 느려지고 짧게하면 컨텍스트 스위칭이 자주 일어나 성능 저하가 일어난다.

스케줄링이 되는 시점

스케줄링이 되는 시점은 3가지 정도다.

1. 매 타임 슬라이스 마다 스케쥴링이 동작.

2. 프로세스가 생성되고 소멸될 때 마다.

3. 프로세스가 블로킹 될 때.

Priority inversion

프로세스의 우선순위가 바뀌는 현상을 말하는데, 가령 A프로세스 > B프로세스 > C프로세스 상태가 있다고 하자. A와 C는 IPC 상태일 때 A는 일을 하다가 C에서 값이 넘어오지 않아 A가 블로킹 되었다고 한다면 기다리고 있던 B프로세스가 실행이 된다. 이러한 상태일 경우 A와 C 입장에서는 일을 처리하지 못하게 된다.

이를 방지하기 위해서 A가 C에게 우선순위를 위임하고 블로킹 상태로 넘어가야 B가 실행되지 않는다.

프로세스 우선순위

IDLE_PRIORITY_CLASS	우선순위 4
NORMAL_PRIORITY_CLASS	우선순위 9
HIGH_PRIORITY_CLASS	우선순위 13
REALTIME_PRIORITY_CLASS	우선순위 24
ABOVE_NOMAL_PRIORITY_CLASS	NOMAL_PRIORITY_CLASS 보다 높고 HIGH_PRIORITY_CLASS 보다 낮음. Windows NT and ME 이하에서는 지원되지 않음.
DELOW_NOMAL_PRIORITY_CLASS	IDLE_PRIORITY_CLASS 보다 높고 NORMAL_PRIORITY_CLASS 보다 낮음. Windows NT and ME 이하에서는 지원되지 않음.

ABOVE_PRIORITY_CLASS.cpp

#include <stdio.h>
#include <tchar.h>
#include <Windows.h>
 
int _tmain(int argc, TCHAR* argv[])
{
    STARTUPINFO siNORMAL = { 0, };
    PROCESS_INFORMATION piNORMAL = { 0, };
    TCHAR commandOne[] = _T("NORMAL_PRIORITY_CLASS.exe");
 
    STARTUPINFO siBELOW = { 0, };
    PROCESS_INFORMATION piBELOW = { 0, };
    TCHAR commandTwo[] = _T("BELOW_NORMAL_PRIORITY_CLASS.exe");
 
    siNORMAL.cb = sizeof(siNORMAL);
    siBELOW.cb = sizeof(siBELOW);
 
    SetPriorityClass(GetCurrentProcess(), ABOVE_NORMAL_PRIORITY_CLASS);
    CreateProcess(NULL, commandOne, NULL, NULL, TRUE, 0, NULL, NULL, &siNORMAL, &piNORMAL);
 
    CreateProcess(NULL, commandTwo, NULL, NULL, TRUE, 0, NULL, NULL, &siBELOW, &piBELOW);
 
    while (1)
    {
        for (int i = 0; i < 10000; i++)
        {
            for (int i = 0; i < 10000; i++)
            {
 
            }
        }
 
        Sleep(10);
        printf("ABOVE_NORMAL_PRIORITY_CLASS process \n");
    }
 
    return 0;
}

NORMAL_PRIORITY_CLASS.cpp

#include <stdio.h>
#include <tchar.h>
#include <Windows.h>
 
int _tmain(int argc, TCHAR* argv[])
{
    SetPriorityClass(GetCurrentProcess(), NORMAL_PRIORITY_CLASS);
 
    while (1)
    {
        for (int i = 0; i < 10000; i++)
        {
            for (int i = 0; i < 10000; i++)
            {
 
            }
        }
 
        Sleep(10);
        printf("NORMAL_PRIORITY_CLASS process \n");
 
    }
 
    return 0;
}

BELOW_PRIORITY_CLASS.cpp

#include <stdio.h>
#include <tchar.h>
#include <Windows.h>
 
int _tmain(int argc, TCHAR* argv[])
{
    SetPriorityClass(GetCurrentProcess(), BELOW_NORMAL_PRIORITY_CLASS);
 
    while (1)
    {
        for (int i = 0; i < 10000; i++)
        {
            for (int i = 0; i < 10000; i++)
            {
 
            }
        }
 
        printf("BELOW_PRIORITY_CLASS process \n");
 
    }
    return 0;
}

위 그림처럼 우선순위가 높은 프로세스만 실행되고 있는 것을 볼 수 있다. 위의 예제 중 for 문과 Sleep()을 제거하면 골고루 실행되는 것을 볼 수 있다.