스케줄링 알고리즘 구현 - seukejulling algolijeum guhyeon

[Operating System ⑤-2] 스케줄링 알고리즘들

HPC Lab 김덕수 교수님의 운영체제 강의를 정리한 내용입니다.

강의링크

목차

1. FCFS, First-Come-First-Service

2. RR, Round-Robin

3. SPN, Shortest-Process-Next

4. SRTN, Shortest Remaining Time Next

5. HRRN, High-Response-Ratio-Next

6. MLQ, Multi-level Queue

7. MFQ, Multi-level Feedback Queue

기본 스케줄링 알고리즘들

다중 프로그래밍 환경에서 System이 여러개의 Process를 관리하기 위해 스케줄링이 필요하다.

기본이 되는 프로세스 스케줄링 알고리즘들은 다음과 같다.

1. FCFS (First-Come-First-Service) : 선착순 방식
2. RR (Round-Robin): 제한시간을 두는 방식

1. SPN (Shortest-Process-Next): 짧은 BT를 우선으로 처리하는 방식
2. SRTN (Shortest Remaining Time Next): 남은 시간이 짧은 것을 우선으로 처리하는 방식
3. HRRN (High-Response-Ratio-Next): RR이 적은 것을 우선으로 처리하는 방식

1. MLQ (Multi-level Queue): 여러개의 레디큐를 두는 방식
2. MFQ (Multi-level Feedback Queue): MLQ와 동일한 방식에서 queue를 다이나믹하게 운용하는 방식

1-A. FCFS

가장 간단한 형태의 알고리즘으로, 빨리 도착한 프로세스에게 CPU를 할당하는 방식이다.

FCFS 구조

FCFS의 특징은 다음과 같다.

• 비선점형 : Process가 CPU 코어를 할당 받으면 작업을 마칠 때까지 쭉 사용하게 된다
• 스케줄링 기준: 레디큐에 도착한 시간을 기준으로 할당한다
• 자원 효율적으로 사용 가능: Process가 CPU를 할당받게 되면 작업을 마칠 때까지 쭉 사용하기 때문에, Context switching Overhead가 적다.
• 일괄처리 시스템에 적합, 대화형 시스템에 부적합 : Process가 도착한 순서대로 처리하는 것(퍼포먼스 높이는 것)이 중요하기 때문에, 각 Process의 응답시간이 느려질 수 있다.

단점

1. Convoy effect : 긴 실행시간을 가진 Process로 인해 다른 프로세스의 대기시간이 길어지는 현상 P2의 burst time이 2초인데도 불구하고, burst time이 10초인 P1이 끝날 때까지 기다려야 하는 문제가 있을 수 있다.
   즉, 하나의 실행시간이 긴 프로세스로 인해서 다른 프로세스의 대기시간이 길어진다.
   
2. 긴 평균 응답시간(response time)

FCFS 스케줄링 케이스

• Arrival time: 도착시간
• Burst time(BT): 실행시간
• Waiting time(WT): 대기시간
• Turnaround time(TT): 응답시간
• Normalized TT(NTT): 상대적 응답시간
  • 상대적인 응답시간을 고려하기 위해서 TT/BT로 계산한다
  • (예) BT가 5초인 프로세스와 BT가 1초인 프로세스 모두 WT가 1초라면, BT 1초인 프로세스가 상대적으로 불합리

실제 예시를 통해 계산해보면 위와 같은 결과를 도출할 수 있다.
각 프로세스의 NTT값을 보면, 매우 큰 차이가 있는 것을 알 수 있다.
실행시간이 큰 p2때문에 나머지 프로세스들이 긴 시간을 기다려야 하는 문제점도 있다 (convoy effect).

1-B. RR

RR(Round-Robin) 라운드 로빈 방식

RR 방식은 선착순 방식의 문제점을 개선한 제한 시간 설정방식이다.
Time quantum이라는 제한시간을 두어 해당 시간동안만 CPU를 사용하고 다음 프로세스에게 넘겨주게 된다.

RR 구조

Round Robin의 특징은 다음과 같다.

• 선점형 스케줄링: 프로세스들이 돌아가며 제한시간 동안만 사용한다.
• 스케줄링 기준: 레디 큐에 도착하는 순서대로 할당한다.
• 자원사용 제한시간(time quantum) 존재: 제한시간을 두어 자원의 독점을 방지한다.
  • context switch(비싼 연산) 때문에 overhead가 크다 (fcfs와 상반됨)
• 대화형/시분할 시스템에 적합

RR 스케줄링 케이스

time quantum 2일 때

각 프로세스가 FCFS방식 보다 균일한 NTT값을 가진다.

1-C. SPN

SPN (Shortest-Process-Next)

FCFS 방식의 문제점은 실행시간이 긴 프로세스로 인하여 짧은 시간의 프로세스들이 오랜 시간을 기다려야 하는 것이었다.

SPN은 BT가 적은 Process를 가장 먼저 처리하여 이러한 문제를 개선한 방식이다.
비선점형 스케줄링 방식이며, SJF(Short Job First) 스케줄링이라고도 불린다.

장점

• 평균 대기시간(WT) 최소화 : 짧은 프로세스부터 빠르게 처리하기 때문에 Process 수가 최소화 된다.
  • System 입장에서 부하도 적고 메모리도 절약되기 때문에, 효율이 향상된다

단점

• 무한대기 : 대기시간이 긴 프로세스는 무한대기를 해야하는 상황이 발생한다.
  • 기아현상: bt가 1시간인 P1이 가장 먼저 도착했다고 하더라도, bt가 그보다 적은 P2,3,4…가 온다면 계속 양보해야 한다.
• 정확한 BT를 알 수 없다: BT를 기준으로 스케줄링이 되지만, 정확하게 계산할 수 없고, 예측기법이 필요하다.

SPN 스케줄링 케이스

기아현상 발생: P2는 BT가 길다는 이유로 12초를 기다렸으며, TT는 19

1-D. SRTN

SRTN (Shotest Remaining Time Next)

SRTN 기법은 남은시간이 가장 적은 프로세스를 먼저 스케줄링하는 방식이다.

SRTN의 특징은 다음과 같다.

• SPN을 변형한 기법
• 선점형 스케줄링: 잔여시간이 더 적은 프로세스가 등장하는 순간 CPU를 선점한다

장점

• 평균 대기시간(WT)를 최소화하여 시스템의 부하를 줄여주는 등 SPN방식의 장점을 극대화한다.

단점

• 프로세스 생성 시 실행시간(BT)을 예측해야하며, 잔여시간을 계속 추적해야 하므로 시스템에 있어서 부하가 커진다.
• 또한 context switching 일어난다.
• 이러한 문제 때문에 현실적으로는 구현이 어렵다.

1-E. HRRN

HRRN (High-Response-Ratio-Next

HRRN은 Response Ratio를 계산하여 해당 값이 가장 높은 프로세스를 우선적으로 스케줄링하는 기법이다.

HRRN의 특징은 다음과 같다.

• SPN을 변형한 기법 : SRTN보다 현실적이다.
• 비선점형 스케줄링
• Aging concepts: SPN의 기아현상을 해결하기 위한 개념이다.
  • 나이가 많은(대기 시간이 긴) 프로세스를 배려한다는 의미
  • 즉, 프로세스의 대기시간을 고려하여 스케줄링한다.

• Response ratio (응답률): (WT+BT)/BT

  • 분자의 WT(대기시간)이 높으면 우선순위가 높아진다.
  • 즉, BT(필요시간) 대비 얼마나 기다렸는지를 고려한다.

SPN의 장점을 취하면서 기아문제를 방지했지만, 여전히 BT(실행시간)을 예측해야한다(Overhead)는 문제점이 있다.

HRRN 스케줄링 케이스

1-F. MLQ

MLQ (Multi-level Queue)

SRTN과 HRRN은 기아문제를 해결하는 대신 각 프로세스의 BT를 측정해야 하기 때문에 시스템 부하가 발생한다는 문제점이 있었다.
MLQ는 레디큐를 여러개 두어, BT 측정 없이도 기아문제를 해결할 수 있는 스케줄링 방법이다.

MLQ의 특징은 다음과 같다.

• 각 queue마다 별도의 우선순위를 매긴다
  • 각각 자신만의 기법을 사용하며 최초 배정된 큐 벗어나지 못한다. (시스템 변화 적응 못함)

단점

• 스케줄링 오버헤드 발생: 여러 개의 레디큐를 관리하기 때문
• 우선순위가 낮으면 기아문제 발생: 큐를 여러 개 두더라도 우선순위 낮으면 여전히 CPU 할당받지 못함

1-G. MFQ

MFQ (Multi-level Feedback Queue)

큐 간의 이동이 불가능하여 시스템 환경 적응이 어렵다는 MLQ의 단점을 극복하기 위하여, 큐 간의 이동을 허용한 방법이다.

MFQ의 특성은 다음과 같다.

• 우선순위가 동적: Queue간에 프로세스가 이동할 수 있도록 허용
  • Feedback(응답)을 통해서 우선순위를 조정한다.
• 선점형 스케줄링
• 시스템 환경 변화에 적응 가능
• BT(실행시간)을 예상할 필요없이 SPN,SRTN,HRRN기법의 효과를 볼 수 있음

단점

• 설계 및 구현 복잡: 여러개의 큐, 큐간의 이동
• 스케줄링 오버헤드 큼: 변화하는 우선순위
• 기아현상: 여전히 우선순위 낮은 프로세스는 CPU 할당 받지 못함

변형

• 시간 할당 다르게 주는 변형 가능
• 어떤 프로세스를 올려주느냐에 대한 다양한 정책 설정 가능
  • (예) i/o 바운디드 프로세스 상위로 올려주는 정책 설정
  • 이유
    • i/o는 cpu잠깐만 쓰고 나온다.
    • 시스템 입장에서는 많은 수를 빠르게 처리해주는 것이 부하 적음. 좀 더 많은 프로세스에 서비스 가능.
    • 즉, 프로세스가 block 될 때 ready로 진입하게 하여, 전체 평균 응답시간 줄임
• 오래기다린 프로세스 위로 올릴 수도 있음

요약

프로세스 스케줄링을 위한 기본 알고리즘들

1. FCFS (First-Come-First-Service) : 선착순 방식
2. RR (Round-Robin): 제한시간을 두는 방식

1. SPN (Shortest-Process-Next): 짧은 BT를 우선으로 처리하는 방식
2. SRTN (Shortest Remaining Time Next): 남은 시간이 짧은 것을 우선으로 처리하는 방식
3. HRRN (High-Response-Ratio-Next): RR이 적은 것을 우선으로 처리하는 방식

1. MLQ (Multi-level Queue): 여러개의 레디큐를 두는 방식
2. MFQ (Multi-level Feedback Queue): MLQ와 동일한 방식에서 queue를 다이나믹하게 운용하는 방식