[OS] Scheduling

1. Scheduling이란?

한 개 이상의 프로세스들을 CPU에 할당하는 방식

쉽게 말하면, 하나의 CPU를 여러 프로세스들이 어떤 규칙으로 돌려 쓸 것인지 정하는 방식이다.

자원 관리 방식에는 시간 분할과 공간 분할이 있는데 스케쥴링이 시간 분할에 해당된다.

 

 

2. 시스템 성능 지표

• 응답 시간(요청~응답)
• 작업 처리량 : 단위 시간동안 완료된 작업의 수
• 자원 활용도 : 주어진 시간동안 자원이 활용된 시간
• 공평성

스케쥴링 기법은 위의 [시스템 성능 지표]를 고려하여 선택한다.

 

 

3. Scheduling 용어

• 대기 시간(Waiting Time) : 프로세스가 대기열에서 대기한 시간
• 실행 시간(Burst Time) : 프로세스를 처리하는데 드는 시간
• 응답 시간(Response Time) : 대기열 도착 ~ 첫 번째 출력
• 반환 시간(Turn-around Time) : 대기열 도착 ~ 실행 종료
• 정규화 반환 시간(Normalized Turn-around Time) : 실행 시간 대비 반환 시간 (반환 시간/실행 시간)
• 오버헤드(Overhead) : 부가적인 처리시간
• 선점(Preemptive) : 자원을 빼앗을 수 있는 것(할당 시간 종료, 우선순위가 높은 프로세스 등장에 의해). Context switch overhead는 많고, 시분할 시스템과 실시간 시스템에 적합
• 비선점(Non-preemptive) : 자원을 빼앗을 수 없는 것. Context switch overhead는 적고, 우선 순위 역전은 잦고, 평균 응답시간은 증가

 

4. Scheduling 기준

• I/O-bounded vs compute-bounded : 입출력이 성능을 결정 vs 연산이 성능을 결정
• Batch system vs interactive system
• 긴급성 : Real time 요구 강도
• 우선 순위 : 정적 우선 순위, 동적 우선 순위가 있음
• 총 실행 시간

 

 

5. Scheduling 단계

• Long-term : Job scheduling. Kernel에 등록할 작업 결정
• Mid-term : Swapping. 메모리 할당 결정
• Short-term : Process scheduling, dispatch

 

 

6. Scheduling 알고리즘

1) FCFS(First Come First Service)

선착순 알고리즘

- 비선점

- Interactive system보다는 Batch system에 적합

- 장점 : 구조가 단순하기 때문에 자원을 효율적으로 사용 가능

- 단점 : 긴 평균 응답 시간, Convoy effect(대기시간>실행시간) 발생 가능성

 

2) RR(Round Robin)

먼저 온 순으로 원을 그리듯 돌려쓰는 알고리즘

- 선점

- 대화형, 시분할 시스템에 적합

- 장점 : 차례마다 자원 사용 제한 시간(Time quantum)이 있기 때문에 독점(monopoly) 방지 역할을 함

- 단점 : Context switch overhead가 큼

 

※ Time quantum이 무한에 수렴 -> FCFS

※ Time quantum이 0에 수렴 -> Processor sharing

 

3) SPN(Shortest Process Next)

실행 시간이 가장 짧은 프로세스를 먼저 처리하는 알고리즘

- 비선점

- SJF(Shortest Job First)

- 장점 : 평균 대기 시간과 시스템 내 프로세스 수가 최소화되어 스케쥴링, 메모리, 시스템의 효율이 향상됨

- 단점 : 실행 시간이 긴 프로세스는 자원을 할당 받지 못할 가능성이 있음(Starvation=기아 현상, 무한대기 현상), 실행 시간 예측 기법 필요

 

4) SRTN(Shortest Remaining Time Next)

잔여 시간이 더 적은 프로세스가 선점하는 알고리즘

- SPN의 변형 기법(비선점->선점)

- 선점

- 장점 : SPN의 장점 극대화

- 단점 : 잔여 시간을 계속 추적(overhead)해야 하고 Context switching overhead가 크기 때문에 구현 및 사용이 비현실적, 실행 시간 예측 기법 필요

 

5) HRRN(High Response Ratio Next)

응답률이 높은 프로세스를 우선으로 하는 알고리즘

- SPN의 변형 기법(Aging 개념 도입)

- 비선점

- Response ratio(응답률) = (대기 시간+실행 시간)/실행 시간

- 많이 기다린 프로세스에게 기회를 제공

- 장점 : SPN의 장점 + Starvation 현상 방지

- 단점 : 실행 시간 예측 기법 필요

 

* 고려 방식

• 공평성 : FCFS, RR
• 효율성, 성능 : SPN, SRTN, HRRN

 

6) MLO(Multi Level Queue)

별도의 Ready Queue를 가지는 알고리즘

- 여러개의 Queue를 두는 기법

- 최초 배정 된 Queue는 벗어나지 못함

- Queue 사이에는 우선 순위 기반의 스케쥴링 사용

- 장점 : 빠른 응답 시간

- 단점 : 여러개의 Queue 관리로 인한 스케쥴링 overhead, 우선순위가 낮은 queue에 대한 starvation 현상 가능성 존재

 

7) MFO(Multi-level Feedback Queue)

Queue간 이동이 허용된 MLG

- Feedback(현재까지의 패턴 활용)을 통한 우선 순위 동적 조정

- 선점

- 장점 : 시스템의 변화에 대한 적응력 향상, 실행 시간 예측 기법 필요 없이 SPN, SRTN, HRRN의 효과를 볼 수 있음

- 단점 : 설계 및 구현이 복잡, 여러개의 Queue 관리로 인한 스케쥴링 overhead, 우선순위가 낮은 queue에 대한 starvation 현상 가능성 존재

- 성능 향상을 위한 기법1 : 각 준비 큐마다 시간 할당량을 다르게 배정하여, 프로세스의 특성에 맞는 형태로 시스템을 유연하게 운영 가능

- 성능 향상을 위한 기법2 : CPU를 짧게 쓰는 I/O Bounded 프로세스는 상위 단계의 Queue로 이동, CPU를 길게 쓰는 Computed-Bounded 프로세스는 하위 단계의 Queue로 이동 -> 평균 응답 시간 단축

- 성능 향상을 위한 기법3 : Aging 기법을 도입하여 대기 시간이 지정된 시간을 초과한 프로세스들은 상위 큐로 이동

 

 

 

이미지 출처 : 한빛 미디어 운영체제

참고 자료 : 김덕수 교수님 - www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN