운영체제 5 : Process Scheduling (2)

이전 글에 이어서 스케줄링을 더 알아볼 것이다.

• 기본 스케줄링 알고리즘
• FCFS
• RR
• SPN
• SRTN
• HRRN
• MLQ
• MFQ

---

기본 스케줄링 알고리즘 (Basic Scheduling algorithms)

 

1. FCFS (First Come First Service)

: 먼저 도착한 프로세스를 먼저 처리한다.

 

- Non-preemptive scheduling

- 스케줄링의 기준은 도착 시간이 된다. 어떤 프로세스가 ready queue에 먼저 도착했는지를 본다.

 

장점

- scheduling이 매우 간단하기 때문에, overhead가 작고 자원을 효율적으로 사용 가능하다. 

- 일괄처리 시스템 (Batch system)에 적합하다.

 

단점

- 긴 평균 응답시간 (reponse time)과 convoy effect가 크다.

- 입력에 빠른 반응을 원하는 대화형 시스템 (interactive system)에는 부적합하다.

 

convoy effect

: 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들도 긴 대기시간을 갖게 되는 현상이다.

 

- Burst time (BT) : 프로세스가 종료될 때까지 필요한 실행 시간

- Waiting time (WT) : 프로세스가 들어와서 종료될 때까지 기다린 시간

- Turnaround time (TT) : 프로세스가 들어와서 종료될 때까지의 총 시간. 여기서는 response time으로 볼 수 있다.

- Normalized TT (NTT = TT/BT) : 정규화 시간으로 체감 시간이라고 볼 수 있다.

 

2. RR (Round-Robin)

: 먼저 도착한 프로세스를 먼저 처리하지만, 자원 사용 시간에 제한을 두는 방식이다.

 

- Preemptive scheduling

- 스케줄링의 기준은 ready queue에 도착한 시간으로 FCFS와 동일하다.

- 하지만 자원 사용에 제한 시간 (time quantum δ)을 둔다는 차이점이 있다.

- 제한 시간 δ은 system parameter로 가지고 있고, 이 시간이 지나면 프로세스는 자원을 반납해야한다.

 

장점

- 특정 프로세스가 자원을 독점 (monopoly)를 방지할 수 있다.

- 응답이 빨라야 하는 interactive system에 적합하다. 

 

단점

- context switch overhead가 크다.

 

time quantum δ 을 어떻게 설정하는 지에 따라 성능이 많이 차이난다.

- δ 를 아주 크다면 FCFS와 비슷할 것이다.

- δ 가 아주 작다면 모든 프로세스가 동시에 실행되는 것처럼 느껴지지만, overhead가 매우 클 것이다.

δ = 2

δ = 3

δ 가 바뀌면서 NTT와 평균 응답 시간 (Average response time)이 바뀐 것을 볼 수 있다.

 

---

3. SPN (Shortest-Process-Next)

: 실행시간을 스케줄링의 기준으로 하여, Burst time이 가장 작은 프로세스를 먼저 처리한다.

 

- Non-preemption sheduling

 

장점

- 평균 대기시간 (WT) 가 최소화된다.

- 시스템 내 프로세스 수가 최소화되어, 스케줄링 부하가 감고하고 메모리가 절약되어 시스템 효율이 향상된다.

- 많은 프로세스들에게 빠른 응답 시간을 제공한다. 

 

단점

- Starvation (무한대기) 현상이 발생하여, Burst time이 긴 프로세스는 자원을 할당받지 못할 수도 있다.

- 정확한 Burst time을 알 수 없기 때문에, Burst time을 예측하는 기법이 필요하다.

 

 

4. SRTN (Shortest Remaining Time Next)

: SPN의 변형으로, 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점하는 방식이다.

 

- Preemptive scheduling

 

장점

- SPN의 장점을 극대화한다.

 

단점

- 프로세스 생성 시, 총 Burst Time 예측이 필요하다.

- 잔여 실행을 계속 추적해야 하므로 overhead가 크다.

- 구현과 사용이 비현실적이다.

 

5. HRRN (High-Response-Ratio-Next)

: SPN의 변형으로 Aging concepts를 적용한다.

 

Aging concepts

: 프로세스의 대기 시간 (WT)을 고려하여 기회를 제공한다.

 

- Non-preemptive scheduling

- Response ratio = ( WT + BT ) / BT 가 높은 프로세스를 우선으로 한다.

- 즉, 필요한 Burst time 대비 얼마나 기다렸는지를 고려해준다.

- SPN의 장점을 가지고 Starvation를 방지할 수 있다.

- 하지만 여전히 BT를 예측해야하는 기법이 필요하다.

---

6. MLQ (Multi-level Queue)

- 작업 또는 우선순위 별 별도의 ready queue를 가진다.

- 최초에 배정된 queue를 벗어나지 못하고, 각각의 queue는 자신만의 스케줄링 기법을 사용한다.

- queue 사이에는 우선순위 기반의 스케줄리을 사용한다.

 

장점

- 우선 순위가 높은 queue는 응답 시간이 빠르다.

 

단점

- 여러 개의 queue를 관리하면서 스케줄링 overhead가 발생한다.

- 우선 순위가 낮은 queue는 starvation 현상이 발생할 수도 있다.

- 시스템 변화에 적응하기 어렵다.

 

 

7. MFQ (Multi-level Feedback Queue)

: 프로세스의 Queue간 이동이 허용된 MLQ 이다.

 

- Feedback을 통해 우선 순위를 조정한다.

 

특성

- Dynamic priority : 우선 순위가 동적이다.

- Preemptive scheduling

- Favor short burst-time processes

- Favor I/O bounded processes

- Improve adaptability

 

프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있다.

 

단점

- 설계 및 구현이 복잡하여 스케줄링 overhead가 크다.

- 여전히 starvation 문제가 있다.

 

변형

- 각 ready queue 마다 시간 할당량을 다르게 배정할 수 있다.

- I/O-bounded 프로세스를 상위로 올려서 우선 순위를 높일 수 있다. 이유는 I/O-bounded는 CPU를 많이 쓰지 않기 때문에 더 많은 프로세스에게 자원을 줄 수 있기 때문이다.

- 즉, 프로세스가 block될 때 상위의 ready queue 로 올려서, 시스템 전체의 평균 응답 시간을 줄일 수 있다.

- Aging 기법을 사용하여 대기 시간이 지정된 시간을 초과한 프로세스들은 상위 queue로 이동시킨다.

 

---

본 글은 HPC Lab. KOREAHECH YOUTUBE 채널의 김덕수 교수님 강의를 보고 작성되었습니다.

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