Chapter 4. CPU 스케줄링

스케줄링(Scheduling)

: CPU를 기다리고 있는 여러 프로세스 중에 누구를 선택해야 할지에 대해 필요한 방식이나 기준

(주어진 시점에서 어떤 프로세스가 이 자원을 사용할 수 있도록 해 줄 것인가를 결정하는 것)

* 대부분 스케줄링이라 함은 CPU 스케줄링을 의미

 

스케줄링(Scheduling)의 단계

** 스케줄링이 요구되는 시점을 기준으로 구분

 

■ 장기 스케줄링 (=작업 스케줄링)

* 대부분 제일 먼저 겪게 되고, 한번 겪으면 그 다음에는 겪을 일 X

: 어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가 결정

=> 요청된 일을 프로세스로 만들어 시스템에 알려진 일거리로 추가할지 말지 결정.

     & 다중 프로그래밍의 정도(Multiprogramming Degree)를 조절.

- 수행 횟수 적음, 대부분 FIFO 방식 (우선순위 방식을 사용하기도 함)

 

■ 중기 스케줄링

* 메모리 부여 받으면, 보류 준비-> 준비. 프로세스가 시스템에 있는 동안 여러번 겪을 확률 多

: 보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가 결정

=> Swap-Out 된 프로세스들 중 어떤 프로세스를 다시 Swap-In (또는 Resume) 할 것인가를 결정

- 장기와 단기 사이 중간 단계

 

■ 단기 스케줄링 (=디스패치)

* 우리가 흔히 말하는 스케줄링 의미

: 준비 상태에 있는 프로세스들 중에서 어느 프로세스에게 CPU를 할당할지를 결정

- 프로세스 스케줄러 또는 디스패처(Dispatcher)에 의해 수행

- 일반적으로 부르는 대부분의 프로세스 스케줄링 = 단기 스케줄링.

- 입출력 또는 시간 종료 인터럽트나 시스템 콜 등과 같은 다양한 이유에 의해 가동

- 횟수 잦음 -> 한번 실행에 드는 시간 최대한 줄여야 함.

 

<스케줄링과 프로세스 상태>

 

스케줄링의 목적과 기준

<목적>

CPU를 할당받을 프로세스를 잘 골라 실행시켜줌으로써 전체적으로 시스템의 성능을 높이는 것.

-> 그렇다면 무엇을 보고 시스템 성능이 좋다고 할 것인가? (성능을 평가하는 잣대가 무엇인가?)

 

1) 사용자의 관점 -> 대표적으로 "응답시간(Response Time)" *정확하게 예측 불가

: 대화형 시스템에서, 프로세스의 요청에 대해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간

= 보통, 프로세스가 들어와서 끝날 때까지 걸리는 시간

(사용자의 입장에서 가장 직접적으로 성능을 느낄 수 있는 지표)

그 외에도

- "반환 시간(Turn-around Time)" : 요청으로부터 결과를 돌려받는 데까지 걸린 시간 (in 일괄처리)

- "예측가능성(Predictability)" : 요청한 일이 얼마 후쯤에는 완료될 수 있을 것이다

 

2) 시스템의 관점 -> "처리량(Throughput)"과 "활용도(Utilization)" 등

- "처리량(Throughput)" : 단위 시간에 완료되어진 프로세스의 개수로 측정

- "활용도(Utilization)" : 주어진 시간 동안 특정 자원이 실제로 가동된 시간의 비율

 

예) 대화형 시스템 - "응답 시간", 일괄처리 시스템 - "처리량" 이 가장 중요

=> 시스템을 사용하는 환경과 목적에 맞는 지표에 치중해서 스케줄링을 해주어야 한다!

 

이외에도

- 공평성(Fairness): 가능한 한 CPU 사용 시간을 공평하게 나누어 주어야 한다.

- 특정 프로세스가 장기간 CPU를 받지 못하게 되는 경우는 최대한 피하고, 시스템에 있는 여러 자원들은 가급적 균형 있게 사용되도록 해야 한다는 것

등이 있다.

 

그렇다면, 성능 지표는 어떤 경우에 어떤 것들이 상충될까?

예) 프로세스 빠른 응답 시간 위해 CPU 스위칭 자주 -> 문맥 교환 필요 (CPU 시간 상당 부분 사용)

-> 사용자 프로세스 실행해 줄 시간이 줄어듦 -> 처리량 감소.

(반대로, 처리량을 높이기 위해 수행시간 짧은 프로세스를 주로 처리하면 수행 시간이 긴 프로세스의 처리가 늦어져 응답시간이 길어지는 문제 발생.)

 

<스케줄링 정책을 만들 때 고려해야 할 기준들>

◎ 스케줄링의 대상이 되는 프로세스의 성격

1) 연산 위주 (CPU-bound 또는Computation-bound) 프로세스 : 연산 > 입출력

2) 입출력 위주 (I/O-bound) 프로세스 : 연산 < 입출력

~ 대부분의 시스템에는 두 종류의 프로세스가 섞여 있음

-> 목적에 따라 어떤 종류의 프로세스를 더 우대할지 생각해야 함.

(시스템 환경에 따라 응답 시간을 우선으로 할지, 처리량을 우선으로 할지)

 

스케줄링 기법들

◈ 비선점(Nonpreemptive) 스케줄링 (실행 중인 프로세스에 의해 CPU 반납)

: 한 프로세스가 CPU를 할당받았을 때 CPU를 스스로 반납할 때까지 계속 사용하도록 허용하는 방식

예) (1) 프로세스가 실행 상태에서 대기 상태로 전환될 때, 대표적인 예가 입출력 요청.

      (4) 프로세스가 수행을 마치고 종료될 때

 

◈ 선점(Preemptive) 스케줄링 (실행 중인 프로세스의 의지와 상관 없이 CPU 뺏김)

: CPU를 할당받아 실행 중인 프로세스로부터 CPU를 선점해(빼앗아) 다른 프로세스에 할당할 수 있도록하는 방식

과정> 현재 실행 중인 프로세스보다 우선순위가 높은 프로세스가 도착 -> 현재 프로세스 실행 중단 -> 우선순위 높은 프로세스에게 CPU를 할당 ( 현재 실행 중이었던 프로세스의 의지와 상관없이 CPU를 빼앗김 )

예) (2) 프로세스가 실행 상태에서 준비 상태로 전환될 때, 시간 종료와 같은 인터럽트가 발생할 때.

      (3) 프로세스가 대기 상태에서 준비 상태로 전환될 때, 예로 입출력의 종료.

 

▶ FCFS (First Come First Service) 스케줄링 (=FIFO 스케줄링)

: 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU를 할당해주며,

  CPU를 할당받은 프로세스는 스스로 CPU를 반납할 때까지 CPU를 독점하여 사용하는 비선점 방식

- CPU를 독점하여 사용하기 때문에 아주 긴 프로세스가 실행 될 경우 뒤에 있는 프로세스들은 오래 기다려야 하므로 대화식 시스템에 적합 X

- 평균 응답 시간이 길어진다는 단점.

- 반면, 준비 상태 프로세스의 개수와 크기를 짐작할 수 있다면 각각의 프로세스의 실행을 예측할 수 있고,

도착 순서만이 실행순서를 결정짓는다는 점에서 공평.

- 가장 단순한 형태로서 실제 시스템에서 바로 사용되기는 어렵. but, 다른 스케줄링 기법의 보조 장치로서 활용 가능

예) 우선순위가 동일할 경우의 차선책

 

<알아두기🚨>

* CPU 요구량 (프로세스 완료를 위한 CPU 시간의 양) ≒ 프로세스의 크기(Size)

* 응답 시간=프로세스가 끝나는 시간=완료시간.

(사용자가 느끼는 평균 응답 시간은 사실, 평균 대기 시간과 가깝다!)

* 평균 응답 시간이 짧다고 해서 모든 프로세스의 응답 시간이 짧아지는 것은 아니지만,

보편적으로 그럴 확률을 높일 수 있기 때문에 평균 응답 시간을 줄이기 위한 노력은 필요하다.

* 도착 순서= CPU 배정받는 순서

* 진짜 응답 시간은 우리가 알아낼 수 없기에 종료 시간(완료 시간)을 응답 시간이라 한다.

(평균 응답 시간은 사실 평균 종료 시간의 의미)

=> 대안: 평균 대기 시간 (가장 평균 응답시간과 가깝)

 

▶ SPN(Shortest Process Next) 스케줄링 (=SJF(Shortest Job First) 스케줄링)

: 준비 큐에서 기다리고 있는 프로세스 중 가장 짧은(CPU 요구량이 가장 적은) 것을 먼저 실행시켜주는 비선점 방식

- 평균 응답 시간 최소화 할 수 있으나, 실행 시간이 긴 프로세스는 무한 대기 현상을 겪음.

(짧은 실행 시간을 가진 프로세스들은 계속해서 도착할 수 있기 때문)

- 실행할 프로세스가 충분하다면, 이 기법은 처리량에 관한 한 매우 훌륭한 성능

- FCFS와 비교했을 때 전체적으로 빠른 응답 시간을 기대할 수 있으나,

  긴 프로세스일수록 그 편차가 커져 예측가능성은 오히려 떨어짐.

* 에이징 (Aging): 기다린 시간만큼 우선순위를 높여(실행가능성을 높여) 긴 프로세스의 무한대기 가능성을 낮추는 방법

ㄴ 예) HRRN 스케줄링 기법

- 하지만, 각 프로세스의 크기를 실행 전에 정확히 알지 못하고(실행 후에야 알 수 있음) 스케줄을 해야 한다.

  ~ 해결책: 지수 평균 (Exponential Averaging) 방법

             -> 비슷한 환경에서 반복적으로 실행되어지는 프로세스에 대해 적용할만 함.

 

▶ SRT(Shortest Remaining Time) 스케줄링

: SPN을 선점 방식으로 운영하는 것. 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜주는 방식

(Remaining Time이 적게 남은 프로세스일수록 CPU 주겠다~)

- SPN의 단점 + 완료까지 남은 실행 시간의 계산

+ 실행 시간이 짧은 프로세스가 자주 도착할 경우의 잦은 선점으로 인한 문맥교환의 부담

~> 이를 보완하면 SRT 효율적 사용 가능

- 반환 시간 면에서는 SRT가 SPN보다 우수

(수치상으로 SRT의 평균 응답 시간도 SPN보다 더 좋은 것으로 나오나, SRT는 남은 시간의 계산과 함께 SPN보다 더 많은 문맥교환이 요구되어 실제로는 평균 응답 시간이 좀 더 길어질 것이다.)

* SPN 스케줄링 수정 방법?

=> Future-knowledge 스케줄링: CPU를 바로 할당하는 대신, 도착시간을 계산하여 그만큼 CPU를 쉬게하여(CPU idle 상태) 기다렸다가 SPN을 적용하는 것.

(가까운 미래를 알기 위해, 처음 1초 동안 CPU를 쉬게하여 오히려 더 우수한 결과를 가져올 수 있다!)

* SRT에서의 잦은 문맥교환 문제를 해결할 방법?

-> SRT 스케줄링을 위한 임계 값(Threshold Value)을 정해두고 두 프로세스의 남은 시간 차이가 임계값을 넘지 않을 경우에는 선점되지 않도록 한다!

 

▶ HRRN(Highest Response Ratio Next) 스케줄링

: SPN과 SRT 방식의 약점인 수행시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법

준비 큐에 있는 프로세스들 중에서 응답률(Response Ratio)이 가장 높은 프로세스에게 높은 우선순위를 주며,

비선점 방식이다.

* 응답률 = 프로세스의 크기(CPU 요구량)에 대한 대기 시간의 비율

              = (대기시간+CPU 요구량) / CPU 요구량

- 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아지므로(대기 시간을 Aging해서 우선순위에 반영)

  수행 시간이 긴 프로세스도 머지않아 CPU를 할당받을 수 있게 된다.

- 큰 프로세스일수록 우선순위가 낮으므로 평균 응답 시간의 단축도 가능

 

▶ 라운드 로빈(Round-Robin) 스케줄링

: FCFS 스케줄링을 기반으로 하여 CPU를 할당하되, 각 프로세스는 한 번에 쓸 수 있는 CPU의 시간 크기

즉, 시간 할당량(Time Quantum)이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기게 되는 선점 방식

- CPU를 반환한 프로세스는 다시 준비 큐의 끝에 들어가게 되고,

  준비 큐의 맨앞에 있는 프로세스가 CPU를 할당받게 된다.

- FCFS 기법에서처럼 한 프로세스가 CPU를 독점하는 단점을 방지할 수 있으나,

  CPU의 선점에 따른 문맥교환의 오버헤드를 감수해야 함.

-> 그럼에도, 대화식 시스템, 시분할 시스템 적합!

- 시간할당량에 따라,

> 시간 할당량이 아주 크면: FCFS 방식과 같아짐

> 시간할당량이 아주 작으면: 문맥 교환의 오버헤드가 커짐

1) 2)가 아니면 일반 라운드 로빈,

2) 입출력 완료 큐를 사용하면 가상 라운드 로빈!

: 입출력 완료 큐에서는 CPU에서(실행 중) 입출력으로 인한 대기 상태로 전환됨에 따라

  못 쓴 시간 할당량만큼만 다음 디스패치 시에 사용 가능하다.

 (입출력에 의해 못 쓰고 남긴만큼의 시간 할당량을 보장하기 위함)

 (+ 시간할당량을 다 써야 시간 종료 -> 준비 큐로 들어감)

<우선순위 스케줄링?>

속성상 대부분 선점 방식으로,

- 정적(Static) 우선순위: 프로세스가 생성될 때 부여된 우선순위가 완료 때까지 변하지 않는 값

- 동적(Dynamic) 우선순위: " 시스템에 있는 동안 조정될 수 있음.

* 구매(Purchaesd) 우선순위: 실행을 빨리할 목적으로 비용을 지불하고 우선순위를 높이도록 함

 

▶ 다단계 큐(Multi-level Queue) 스케줄링

: 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏기는 선점 방식

- 다단계 큐?: 정적 우선순위를 사용하는 스케줄링 구현 시 가장 적합한 자료구조

ㄴ 같은 우선순위 값을 가지는 프로세스들을 위해 큐가 필요함

  + 서로 다른 우선순위의 프로세스들을 구별하고 관리하기 위해 우선순위의 개수만큼 큐가 필요함

- 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어감.

 

▶ 다단계 피드백 큐(Multi-level Feedback Queue, MFQ) 스케줄링

: 동적 우선순위를 기반으로하는 선점 방식

: 프로세스들의 CPU 요구량을 몰라도 짧은 프로세스들에게 유리하면서 입출력 프로세스를 우대할 수 있는 스케줄링 기법의 해답!

- 완료까지 남은 시간을 몰라도 지금까지 실행된 시간을 잘 활용하면 SPN이나 SRT와 비슷한 효과,

즉, 짧은 프로세스에게 유리하도록 해줄 수 있다.

- 중간 단계의 맨 앞에 있는 프로세스는 상위 단계의 큐들이 모두 비어 있는 경우에만 CPU를 받을 수 있고,

  입출력이 발생하지 않는 한 할당된 시간을 다 사용할 수 있다.

- 프로세스의 성격에 맞도록 우선 순위를 조정해 줌으로써 적응성이 있는 스케줄링이 가능하다.

(= Process의 behavior에 Adeptive하다.)

- 입출력 프로세스를 우대함으로써 CPU를 포함한 전체 자원들의 활용도를 높여 시스템의 성능을 높일 수 있는 기법

➖ Priority ↑, Quantum size ↓ 〰〰 짧고 I/O bound일 확률 ↑

➖ Priority ↓, Quantum size ↑ 〰〰 꽤 크고 CPU bound일 확률 ↑

- MFQ 기법은 여러 변형된 모양이 존재한다.

예) 각 단계에서 시간 할당량을 다 쓴 경우 그 단계의 큐에서 몇 번의 순환 후 다음 단계로 떨어뜨리거나,

입출력의 완료 시 각 단계의 상승 폭을 더 크게 해주는 형태 

- 남아있는 무한 대기의 가능성 -> Aging 기법 활용 방법 (일정 시간을 넘긴 대기 -> 상위 큐로 이동)

▶ Fair-share 스케줄링

: 프로세스들의 특성이나 중요도에 따라 몇 개의 그룹으로 나누고, 각각의 그룹에 (서로 다르게) 할애된 일정량의 CPU 시간을 그 그룹에만 영향을 끼치도록한 기법

(지금까지의 기법들은, 스케줄링의 대상이 되는 모든 프로세스들을 하나의 그룹으로 취급했다.)

- (스케줄링 기법을 뭘 사용하든) 그룹별로 일정량의 CPU 시간을 할애했을 때, 특정 그룹에 속한 프로세스의 과도한 CPU 사용은 그 그룹내의 다른 프로세스들에게만 불이익을 줄 뿐, 다른 그룹으로까지 파급되지 않도록 함.

 

실시간(Realtime) 스케줄링

◎ 실시간(Real time) 시스템: 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템

- 경성 실시간(Hard Realtime) 시스템

: 작업이 마감시한(Deadline) 내에 완료되지 않으면 (시스템이 중지되는 등의) 치명적인 결과를 초래하는 시스템

- 연성 실시간(Soft Realtime) 시스템

: 작업이 마감시한 내에 종료되지 않으면 데이터의 손실 등의 피해가 발생하지만 시스템은 계속해서 운영 가능한 시스템

=> 경성은 마감시한을 넘긴 후 완료되는 작업은 의미가 없는 반면,

     연성은 마감시한을 넘긴 후부터는 완료의 가치가 점점 떨어지게 되는 것을 말함.

- 일반적으로, 실시간 = 경성

 

- 정적 방법: 프로세스들의 특징과 개수를 알 수 있는 경우 유용

- 동적 방법: 프로세스의 생성 시간이나 특성을 알 수 없는 경우 사용

* 실시간 운영 환경은 대부분 특수하므로, 실행되어야 할 일들의 성격 (크기, 발생주기 등) 이나 개수를 사전에 알 수 있는 경우가 많다.

 

■ RM(Rate Monotonic) 알고리즘 (정적 환경에서 최적의 기법)

: 낮은 우선순위의 프로세스가 더 높은 우선순위의 프로세스가 도착할 경우 CPU를 뺏기게 되는 선점 방식

- 대표적인 정적 스케줄링 방식. (크기와 개수가 알려진 프로세스들이 주기적으로 발생되는 환경에서 사용)

- 프로세스들은 서로 독립적이고 주기적으로 발생되는 환경에서 각 프로세스의 마감시한은 각자의 주기와 같다고 가정하고, 주기가 짧을수록 높은 우선순위를 받게 된다.

- CPU 사용률(U) 가 아래 식을 만족하면 RM 기법 가능!

(1보다 적을 경우: 무조건 가능! / 1일 경우: 될 때도, 안 될 때도 / 1보다 클 경우: 무조건 불가능!)

(* P=주기, D=마감시한(D<=P), C=크기(수행시간)(C<=D))

- 스케줄링 비용 적음

- 대신, 새로운 프로세스가 추가되는 환경에 바로 적응 못하고,

  이 프로세스를 추가하여 전체 스케줄링을 다시 해야 함. (단점)

 

■ EDF(Earliest Deadline First) 알고리즘 (RM으로 안 되는 애들의 스케줄링 가능성을 확장시켜줌)

: 프로세스의 마감시한이 가까울수록 우선순위를 높게 부여하는 선점 방식의 동적 스케줄링

* RM으로 할 수 있음하고, 될수도 안 될수도 있는 애들(=1)을 EDF로 하면, 1이하일 경우 성공!

(RM으로 할 수 O ---> EDF로 할 수 O /  EDF로 할 수 O ---> RM으로 할 수 X(세모))

- 동적=새로운 프로세스가 도착할 때 바로 대응 가능

- 우선순위에 의해 실행 중 CPU를 뺏길 수 있으며, 한 프로세스의 실행이 완료될 경우에는 마감시한이 가장 가까운(임박한) 것을 찾아 스케줄링

- 모든 프로세스가 주기적일 필요는 x. 주기적일 경우에는 마감시한을 주기로, 아닐 경우는 마감시한이 알려져야 함.

- 다음 조건이 성립한다면 EDF 기법으로 가능한 스케줄이 존재!

- 새로운 프로세스의 동적 수용이 허용되나, 그때마다 가능한 스케줄을 찾기 위한 계산을 해야하는 부담 O

 

* RM이나 EDF 모두 상호 독립적이라는 가정을 하고 있기에

 공유(Shared) 데이터를 통한 프로세스 간의 통신이 있는 경우에는 적용 불가.

-> 이 경우, PIP, PCP 등 사용 (교재에서는 설명 X)

 

윈도에서의 스케줄링

: 윈도는 스레드 단위로 CPU를 할당하는 우선순위에 의한 선점 스케줄링 방식이다.

- 두 개의 클래스로 구분: 16~31(for 실시간 클래스) + 0~15(for 일반 플래스)

- 실시간 클래스: 정적 우선순위로 운영되는 다단계 큐, fkdnsem fhqls qkdtlr

- 일반 클래스: 동적 우선순위로 운영되는 MFQ

(대표적인 우선순위의 변동) 시간 종료 인터럽트의 경우 하향으로, 입출력 완료의 경우 상향으로.

-> 입출력위주 프로세스 우대