[OS] 운영체제 Process Scheduling 기법

스케쥴링이란 한정된 자원을 할당할 프로세스를 선택하는 것을 말한다.
자원을 할당할 프로세스를 선택하는 기법(알고리즘)에는 여러가지가 존재하는데 하나씩 알아보자!!

FCFS(First-Come-First-Service)

먼저 온 녀석부터 자원을 할당하는 기법(알고리즘)이다.
먼저 ready queue에 온 프로세스부터 자원을 할당하고, 할당한 자원은 프로세스가 수행이 끝날때까지, 할당 받는다.
즉, 비선점 스케쥴링 정책을 이용한다.

• 비선점 스케쥴링 정책 이용
• 자원에 대해서 효율적으로 사용 가능하다.(왜냐면 비선점 스케쥴링 정책을 이용하기 때문에 스케쥴링 overhead가 낮기 때문이다.)
• FCFS는 Batch System에 적합하고, 응답성이 중요한 대화형 시스템인 interactive System에 부적합하다.
• Convoy effect(먼저온 프로세스가 수행시간이 매우 길면 그뒤에 온 프로세스는 수행시간보다 대기시간이 훨씬 길어지게 되는 현상이다. 고속도로에서 맨앞에 엄청 느리게 가는 차때문에 뒤에 차들이 막히는 현상과 같당..)
• 평균 응답시간이 매우 길다.(대기시간이 길어지기에...)

(FCFS 기법 스케쥴링시 프로세스가 프로세서를 할당받는 방식이다.)

RR(Round-Robin)

뭔가 이름처럼 빙빙 돌거같다.
FCFS와 다르게 자원사용 제한시간이 존재하여 먼저 ready queue에 온 프로세스가 자원을 할당받아 수행이 끝나는걸 기다리지않는다. 자원 사용 제한시간이 존재하여 프로세스 수행이 끝나지않아도 프로세서를 할당받은 프로세스를 timer runout시키고 그다음 ready queue의 프로세스가 자원을 할당받는다.

• 선점 스케쥴링 정책이용
• 스케쥴링의 기준으로는 ready queue에 먼저온 프로세스에 자원을 먼저 할당하는데, 자원 사용 제한시간이 있다!!!!
• 자원사용제한시간을 time quantum이라하고 time quantum이 끝나면 프로세스는 할당받은 자원을 다시 반납한다.
• 즉, 프로세스의 독점을 방지한다.(convoy effect 부작용을 방지한다.)
• 그러나 그만큼 스케쥴링 오버헤드가 크겠다.(context switch overhead, 그만큼 프로세서를 할당받고 받납하는 프로세스가 자주 바뀌닌까..!!)
• FCFS는 Batch System에 적합한반면 RR기법은 사용자와의 응답성이 중요한 interactive system에 적합하다. 또, time sharing system에도 적합하다.

Time quantum

RR을 보면 알겠지만 자원사용 제한시간을 결정하는게 중요하다고 느꼈을 것이다!!
time quantum이 너무크면 FCFS랑 차이가없다...
time quantum이 너무 작으면 그만큼 context switch overhead가 커서 성능이 안좋다...

즉, 적절하게 timequantum을 설정하는것이 RR의 핵쉼!!

(FCFS와는 다르게 Timer-runout으로 자원을 반납해 ready queue의 맨 뒤로 프로세스가 다시 대기하는것을 볼수가 있다!!)

SPN(Shortest Process Next)

실행시간(Burst time)이 작은 프로세스부터 자원을 할당하는 스케쥴링 기법이다.
SJF(Shortest Job First)라고도 부른다.
자원을 할당받으면 프로세스 수행이 끝날때까지 할당받기때문에 비선점 스케쥴링 기법이다.
(뭔가 되게 효율적인 스케쥴링 알고리즘같다는 느낌이 든다!!)

SPN의 장점

평균 대기시간(WT)가 적다.(BT가 작은 프로세스부터 자원을 할당하닌까!)
시스템 내의 프로세스의 수가 최소화된다.(BT가 작은 프로세스부터 자원을할당받고 수행이 끝나기 때문에 ready queue에있는 프로세스 수가 적다.)
많은 프로세스들에게 빠른 응답시간이 제공된다.

SPN의 단점

BT가 긴 프로세스는 계속 자원을 할당받지못하고 계속 뒤로 밀리게된다.. 이를 starvation 즉, 기아현상이라 한다.
프로세스의 정확한 Burst time(실행시간)을 알수가없다. 물론 이전에 수행이 끝난 프로세스는 terminated(zombie)상태에서 pcb에 기록하고 목숨을 다하기에 어느정도 Burst time을 예측할순 있지만 정확한 시간은 예측못한다.

SRTN(Shortest Remaining Time Next)

SPN의 변형으로 잔여 Burst time이 더 적은 프로세스가 ready queue에 들어오면 선점되는 스케쥴링 기법이다.
말그대로 선점 스케쥴링 기법이다.
뭔가 SPN보다 더 효율적일거같다. 이미 자원을 할당받아서 수행중인 프로세스도 더 짧은 Burst time의 프로세스가 ready queue에 오면 선점해버리닌까.!

SRTN장점

예상한것처럼 SPN의 장점이 극대화된다.

SRTN단점

계속해서 잔여 Burst time을 추적해야하므로 그만큼 overhead(부하)가 생길것이다.
선점 스케쥴링기법이므로 그만큼 context switch비용이 들것이다.
SPN과 마찬가지로 Busrt time의 정확한 시간을 예측하기 어렵다.
(sw 세상에서는 뭐든지 trade off가 존재한다..)
SPN처럼 BT가 작은 프로세스는 계속해서 뒤로밀리는 기아현상이 일어난다.

HRRN(High Response Ratio Next)

SPN + Aging concepts의 스케쥴링기법으로 SPN의 기아현상을 해결하는 스케쥴링 기법이다.
Aging concepts란 의미그대로 나이 개념이고 프로세스의 대기시간을 나이로 생각해서 대기를 많이한 프로세스에게 자원을 할당해서 기아 현상이 일어나지 않도록 방지하는 스케쥴링 기법이다.(노약좌석에서 어르신이오면 비켜드리는 !)

HRRN의 스케쥴링 기준

Response Ratio가 높은 프로세스가 우선적으로 자원을 할당받는다.
Response Ratio = (WT + BT) / BT 로 정처기에서는 (HRRN 대서서)로 외운기억이 있다.

HRRN의 장정

SPN의 장점도 그대로 살리면서 starvation(기아현상)도 막기에 되게 좋은 스케쥴링 기법이다!!

HRRN의 단점

그러나.. SPN, SRTN이 가지고 있던 BurstTime(프로세스 실행시간)을 정확하게 예측하지 못한다.

SPN, SRTN, HRRN은 FCFS, RR과 다르게 BT를 기준으로 프로세스에게 자원을 할당하여 시스템의 성능 향상을 중요하게 생각한다. 그런데 여전히 BT를 정확하게 예측하기 어렵다는 단점이 존재한다... 이 문제는 MLQ, MFQ 스케쥴링 기법으로 해결할수 있다.

아래 그림은 지금까지 알아본 스케쥴링 기법을 분류한 기준(공평성, 효율성)과 스케쥴링 기법을 한눈에 볼수있는 그림이다.

MLQ(Multi-level Queue)

SPN, SRTN, HRRN은 효율성을 중요하게생각하는 스케쥴링 기법인데,, BT(실행 시간)을 예측하기 어려운 단점이있다. 이 문제점을 해결하면서 SPN, SRTN, HRRN의 장점을 살릴수있는 스케쥴링 기법이 바로 MLQ이다.
MLQ스케쥴링 기법은 우선순위 별 별도의 ready queue를 여러개 가지고 있다.
최초 배정된 queue를 프로세스는 벗어나지 못하고, 각각의 queue는 자신만의 스케쥴링 기법을 사용한다.

MLQ의 장점

우선수위가 높은 큐의 프로세스들은 응답시간 이 빠르다.

MLQ의 단점

우선순위가 낮은 큐의 프로세스들은 기아 현상이 발생할수있다.(자원을 계속 할당받지 못할수도 있음)
여러개의 queue가 존재하니 그만큼의 overhead(부하)가 생길것이다.

MFQ(Multi-level Feedback Queue)

MLQ와는 다르게 프로세스가 Queue간의 이동이 허용된 스케쥴링 기법이다.
Feedback이라는 것을 통해서 우선순위를 조정할수있다.

MFQ의 단점

당연하게도 설계가 복잡하고 그만큼 부하도 크다.
프로세스가 큐간의 이동이 가능해도 기아현상이 발생할수 있다.

MFQ의 변형

MFQ는 변형을 하여 다양하게 스케쥴링을 할수 있다.

• 각 ready queue마다 time quantum을 다르게 설정
• I/O bounded process들은 우선순위 높은 큐로 이동시켜 시스템 전체 평균응답시간을 줄이게 할수있다.
• computed bounded process들은 우선순위 낮은 큐로 이동시켜 시스템 전체 평균응답시간을 줄일 수 있다.
• 대기시간이 긴 프로세들은 aging기법을 통해 상위큐로 이동시킬 수 있다.

이렇게 MFQ 스케쥴링 기법은 시스템 특성에 맞게 변형하여 효율적으로 스케쥴링을 할수 있다.

김덕수 교수님의 운영체제 강의

https://www.youtube.com/watch?v=actKUqea6Xc&t=301