[ OS 기초 ] 05. 스케줄링 알고리즘

대표적인 스케줄링 알고리즘
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)

 

01 FCFS

- 선착순 알고리즘 : 가장 먼저 도착한 프로세스부터 프로세서를 할당해주는 알고리즘
- FCFS가 적절한 시스템 : 배치 시스템 (일괄처리 시스템) - 빠른 응답보다 빨리 처리해주는게 더 중요
- FCFS가 부적합한 시스템 : 대화형 시스템 (interactive system) - 빠른 응답이 더 중요한 시스템
- 비선점(프로세서를 뺏기지 않음)이라 코어를 할당받으면 프로세스가 끝날때까지 프로세서를 사용
- 스케줄링의 기준 : 도착시간 (Ready Queue에 도착한 순서)
- Normalized Turn-around Time = Turn-around Time / Burst Time
- Normalized TT는 실행에만 필요한 시간 대비 전체 작업 수행시간(대기했던 시간을 포함)한 개념으로 단순히 대기 시간의 절대적인 값으로 비교하는게 아니라, 일종의 체감 대비 시간을 의미한다
- ex) 수행 시간이 2초인 프로세스와 1분인 프로세스에게 10초라는 대기시간은 체감상 다름. 대기시간은 같지만 똑같다고 평가하기 어려움

장점
- 자원 활용도가 높아 효율적으로 사용할 수 있다
- 스케줄링의 오버헤드가 낮다

단점
- 평균 응답시간이 길다 (짧은 예상 처리 시간에도 불구하고 늦게 도착하면 오랜 시간 대기해야 한다)
- Convoy effect : 긴 수행시간을 가진 프로세스로 인해 짧은 수행시간을 가진 프로세스들이 줄줄이 대기하는 현상

 

02 RR (Round-Robin)

- 원형 탁상에 위치한 프로세스들이 돌아가며 cpu를 할당받는 스케줄링 방식
- 자원 사용에 제약(제한시간, Time Quantum)이 있어, 시간을 다 사용하면 큐의 맨 뒤로 가서 다시 대기하는 방식
- RR이 적합한 시스템 : 대화형 시스템, 시분할 시스템
- 선점 스케줄링 : 특정 시간만큼 사용하면 다음 프로세스에 프로세서가 다시 할당됨 = 프로세서를 빼앗김
- 스케줄링의 기준 : 도착시간 + Time Quantum
- Time Quantum : 제한 시간, System parameter인 타임 퀀텀을 설정하면, 그 시간이 지난 후 Timer-runout으로 자원을 반납해야 한다
- Time Quantum을 어떻게 설정하느냐에 따라 성능에 변화가 생길 수 있다 (꼭 크다고 성능이 좋아지는 것 만은 아님)
- 만약 Time Quantum이 무한대라면? = FCFS
- 만약 Time Quantum이 아주 작다면? = 프로세서 쉐어링과 유사해지고 문맥교환으로 인한 오버헤드가 커진다

장점
- 특정 프로세서의 자원 독점(monopoly)를 방지할 수 있음

단점
- 프로세스가 바뀔 때마다 context switch가 발생해 오버헤드가 발생한다

 

03 SPN (Shortest Process Next)

- 실행시간(Burst Time)이 짧은 순서대로 프로세스를 처리하는 스케줄링, SJF로도 불림(Shortest Job First Scheduling)
- FCFS의 오랜 대기시간 문제를 해결 할 수 있음
- 비선점 스케줄링
- 스케줄링 기준 : 실행시간(Burst Time)
- Starvation : 무한대기현상. 만약 수행 시간이 짧은 프로세스들이 연속적으로 도착할 경우, 먼저 도착했던 프로세스 중 수행 시간이 매우 긴 프로세스들은 무한 대기를 해야 하는 문제가 발생

장점
- 평균 대기 시간 최소화
- 프로세서가 처리해야 하는 프로세스의 수도 최소화할 수 있어 부하가 적어지고 메모리도 절약할 수 있어 시스템 효율이 향상됨

단점
- Starvation 현상 (=> HRRN 스케줄링에서는 이를 Aging을 활용해 개선함)
- 스케줄링 기준이 실행 시간이기 때문에 미리 이를 예측해야하는데, 이 예측 기법도 필요하고 예측의 정확도 또한 보장하긴 어려움

 

04 SRTN (Shortest Remaining Time Next)

- 남은 시간(Remaining Time)이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
- 선점 스케줄링으로 남은 시간이 가장 짧은 프로세스가 프로세서를 차지함
- 스케줄링 기준 : 실행 시간(Burst Time)
- 현실적으로 구현이 어렵다는 문제가 있음

장점
- SPN과 마찬가지로 빨리 처리할 수 있는 프로세스를 먼저 처리할 수 있어 효율성이 향상됨

단점
- 역시나 시간 예측이 어렵고 추가적으로 잔여시간을 추적해야하는데 따른 오버헤드가 발생함
- 선점 스케줄링이기때문에 문맥교환이 자주 발생함

 

05 HRRN (High Response Ratio Next)

- 기존의 SPN 스케줄링에서 발생하는 Starvation 문제를 해결하기 위해 Aging 개념을 반영한 스케줄링
- 프로세스의 수행 시간을 고려하되, 오래 기다린 프로세스라면 가중치를 부여해 순서를 조정하는 스케줄링
- 비선점 스케줄링
- 스케줄링 기준 : 응답률(Response Ratio) = (실행시간 + 대기시간)/실행시간
- 프로세스 실행에 필요한 시간 대비 대기한 시간을 고려한다는 점 (그냥 대기 시간만 고려하는 게 아님)
- 응답률 식에 따르면, 실행시간 대비 대기 시간을 고려해 대기 시간이 길어질수록 응답률이 높아져서 실행 시간이 좀 더 길더라도 오래 대기한 프로세스들을 먼저 처리할 수 있게끔 처리

장점
- SPN의 장점을 가져오되, Starvation도 어느정도 방지할 수 있음

단점
- 시간 예측의 어려움

 

06 MLQ (Multi Level Queue)

- 앞선 스케줄링 기법들이 모두 큐를 하나로 가정했다면 멀티레벨큐는 레디 큐를 여러개 사용함
- 각각의 큐는 지정한 작업들을 위한 큐이며, 이 큐들에 우선순위를 배정해주는 스케줄링 기법
- 지정된 큐를 벗어나지 못하고, 각각의 큐는 독립적으로 스케줄링 기법을 사용할 수 있음
- 큐 간에는 우선순위 기반의 스케줄링을 사용함(Fixed Prioritym Preemptive scheduling)

장점
- 우선순위가 높은 큐는 빠르게 작업을 처리할 수 있음(중요한 프로세스는 빨리 처리가 됨)

단점
- 우선순위가 낮은 큐에는 마찬가지로 Starvation 현상이 발생할 수 있음
- 여러 큐를 사용하는데 따른 오버헤드가 발생함
- 처음에 지정된 우선순위가 바뀌지 않아 환경 변화에 유연하게 적응하지 못함

 

07 MFQ (Multi-level Feedback Queue)

- MLQ에서 처음 지정된 큐를 벗어나 우선순위를 바꿀 수 있도록 허용한 스케줄링 방식
- 환경 변화에 따라 우선순위 조정이 필요할 때 유용함
- 선점 스케줄링으로 우선순위가 바뀌거나 큐를 이동하면 프로세서를 뺏을 수(또는 뺏길 수) 있음
- 큐 간에 이동이 가능하며 피드백을 통해 큐의 우선순위가 조정된다(동적 우선순위)
- 피드백(Feedback) : 현재까지 프로세서의 사용 정보나 사용 패턴들

장점
- 앞의 SPN, SRTN, HRRN 처럼 실행시간을 예측할 필요가 없지만, 이들 스케줄링 기법의 장점을 취할 수 있다

단점
- 복잡하고 낮은 우선순위의 큐는 여전히 Starvation 을 겪을 수 있음

변형
- 다양한 정책과 전략을 사용해 변형을 주어 성능을 개선하거나 단점을 보완할 수 있음
ex. 시스템의 특성을 고려해 I/O bounded 프로세스의 우선순위를 높여주는 방법 : 응답시간을 줄일 수 있음 / 또는 Compute bounded 프로세스의 우선순위를 낮춰주기
ex. Aging 이 높은 프로세스의 우선순위를 높여주기
ex. 타임 퀀텀을 다르게 부여하기

 

**  KOREATECH 무료 OS강의(클릭) 학습 후 나름대로 이해한 뒤 정리한 내용입니다. **

[Course] Operating System (CPA310) - 운영체제 강의