[운영체제] Ch.5-2 스케쥴링 알고리즘

본 글은 김덕수 교수님의 2019년도 봄학기 운영체제(CPA310)

강의 내용을 바탕으로 요약 정리한 내용입니다.

 

https://sites.google.com/view/hpclab/courses/operating-system

HPC Lab., KOREATECH - Operating System

 

---

FCFS (First-Come-First-service)

일명 선착순 알고리즘이다. 비선점 스케쥴링 방식이며

스케쥴링 기준은 먼저 ready queue에 도착한 프로세스를 먼저 처리하는 것이다.

Context Switching이 적어지므로 '비교적' 효율적으로 자원을 사용하는 알고리즘이다.

Batch System에 적합한 방식이다.

단점으로는 Convoy effect로 인해 발생하는 긴 평균 응답시간이 있다.

다른 프로세스들이 긴 대기시간을 갖게 되는 현상을 Convoy effect라고 한다.

이는 비선점 방식이므로 수행시간이 긴 프로세스가 작업에 들어가도 자원을 빼앗기지 않아서 발생한다.

해당 효과 때문에 긴 평균 응답시간(response time)을 가진다는 단점이 있다.

 

 

Round-Robin (First-Come-First-service)

라운드 로빈은 선점 스케쥴링이다.

ready queue에 도착한 순서대로 프로세스를 처리한다.

단, 자원 사용 제한 시간(time quantum)이 존재한다.

타임 퀀텀이 지나면 프로세스는 자원을 반납해야 한다.(TImer-runout)

이는 특정 프로세스의 자원 독점을 방지한다는 의의가 있으나, Context Switch Overhead가 커진다는 단점이 생긴다.

따라서 대화형 시스템이나 시분할 시스템에 적합한 방식이다.

 

타임 퀀텀이 시스템의 성능을 결정하는 핵심 요소가 된다.

타임 퀀텀이 너무 커지면 사실상 FCFS와 다름이 없으며

타임 퀀텀이 너무 작아지면 context switch overhead가 과해질 것이다.

 

Round-Robin 방식

시간이 지나서 프로세스가 자원을 반납할 때

ready queue의 마지막 대기열로 들어간다는 것을 명심하자.

 

 

---

 

SPN(Shortest-Process-Next)

비선점 스케쥴링 방식인 SPN은 실행시간(burst-time)이 가장 작은 프로세스를 먼저 처리한다.

장점으로는 평균 대기시간이 최소화된다는 장점이 있다.

또한 시스템 내 프로세수 수가 최소화된다는 장점도 존재한다.

이는 스케쥴링의 부하 감소로 이어지며, 메모리가 절약되고 시스템 효율이 향상되는 결과를 불러온다.

많은 프로세스들에게 빠른 응답 시간을 제공할 수도 있다.

 

단점으로는 Starvation(무한 대기 현상)이 발생한다는 것이다.

Burst Time이 긴 프로세스는, Burst Time이 작은 프로세스들이 마구마구 들어올 때

자원을 할당받지 못할 수도 있다.

또한, 프로세스들의 정확한 실행시간을 알 수 없기 때문에, 실행시간 예측 기법이 필요하다.

 

 

SRTN(Shortest Remaining Time Next)

SPN의 변형인 SRTN은 선점 스케쥴링 방식이다.

잔여 실행 시간이 더 적은 프로세스가 ready 상태로 들어오면, 자원이 선점된다.

장점으로는 SPN의 장점을 극대화시켰다는 점이나,

단점으로는 Context Switching Overhead가 부담되고, 프로세스 생성시 총 실행 시간 예측이 필요하다는 점

그리고 잔여 실행을 계속 추적해야 한다는 점에서 비현실적이다.

 

 

HRRN(High Response Ratio Next)

HRRN도 SPN의 변형이다. ( SPN + Aging Concepts ) HRRN은 비선점 스케쥴링 방식이다.

Aging이라는 개념이 들어간다. 에이징은 프로세스의 대기 시간(WT)을 고려하여 기회를 제공한다는 것인데

응답률이 높은 프로세스에게 먼저 자원을 할당시킨다는 것이다.

응답률은 (WT+BT) / BT로 계산한다.

분자인 대기 시간이 커질수록 응답률이 커질 가능성이 높아진다.

이는 Starvation(무한 대기 현상)을 방지하고자 하는 시도로 볼 수 있다.

여전히 실행 시간의 예측 기법이 필요하므로, overhead가 발생한다.

 

 

---

 

 

 

FCFS와 RR이 공평성에 초점을 두고

SPN, SRTN, HRRN와 같은 알고리즘들이 성능에 초점을 둬서 장단점을 가져갔다면

MLQ, MFQ와 같은 알고리즘들은 위의 단점을 극복하면서 장점을 극대화시키려는 알고리즘이다.

 

MLQ(멀티 레벨 큐)

멀티 레벨 큐는 작업( 혹은 우선순위 )별 별도의 ready queue를 만드는 방식이다.작업들이 최초로 배정 된 레디 큐를 벗어나지 못하며,각 레디 큐는 각각 자신만의 스케쥴링 기법을 사용한다.큐 사이에는 우선순위 기반의 스케쥴링을 사용한다.

 

MLQ

 

장점으로는 응답시간이 빠르다는 것이나,단점으로는 여러 개의 Queue를 관리할 때 발생하는 overload그리고 우선순위가 낮은 Queue에서 Starvation이 발생할 수 있다는 점이다.

 

 

MFQ(멀티 레벨 피드백 큐)

멀티 레벨 피드백 큐는 큐 사이의 이동을 허용하는 MLQ라고 이해하면 된다.

즉, 우선순위를 새롭게 배정할 수 있는 것이다.

또한, aging 기법을 적용하여 프로세스들도 상위 큐로 이동시킬 수 있다.

 

작업들이 최초로 배정 된 레디 큐를 벗어나지 못하며,

각 레디 큐는 각각 자신만의 스케쥴링 기법을 사용한다.

큐 사이에는 우선순위 기반의 스케쥴링을 사용한다.