운영체제의 기초 - 9. CPU Scheduling 2

Scheduling Policies (2)

이 전 수업 내용 정리

Preemptive scheduling:

Non-Preemptive scheduling: 

Preemptible Resource: 한 프로세스가 점유한 상태에서 다른 프로세스에게 양보할 수 있는 자원

  - 대표적인 예. CPU, main memory

  - 어떤 프로세스가 CPU를 점유해서 돌고 있었는데 양보해야할 시점이 왔을 때 그 점유한 프로세스에 state를 안전하게 대피시키는 것(Context Switching)

Non-Preemptible Resource: 한 프로세스가 점유하면 사용을 마칠 때까지 프로세스에게 양보할 수 없는 자원

  - 대표적인 예. printer

  - 문서가 반쯤 프린터 됐는데 그걸 다른 job이 가져갔다 말도 안되죵

CPU Burst: Scheduling의 단위가 되는 entity, (job이나 프로세스 전체가 아니라 I/O와 I/O 사이의 있는 연속적인 수행 구간)

  - 프로그램의 수행 중에 연속적으로 CPU를 사용하는 단절된 구간, 

SJF: optimal한 Policie. Shortest Job을 먼저 수행시키는 스케쥴링

그러나 Shortest Job을 찾으려면 CPU burst size를 예측해야 하는데 그것은 사실상 불가능

FIFO: 먼저 온 프로세스를 먼저 처리하는 스케쥴링

단순해서 좋으나 Short job이 왔을 때 잘 처리하지 못함

어떤 순서로 job이 오느냐에 따라 response time에 큰 영향을 미침

FIFO 스케쥴링의 단점을 좀더 해소하기 위해 preemptive하게 만든 스케쥴링 알고리즘이

Round Robin(RR): time slice라고 하는 일정한 interval을 주어 그 안에서만 CPU를 점유하게 하는 것. 

CPU Burst size가 time slice보다 크면 수행을 강제종료당하고 ready queue 맨뒤로 보내는 방법임.

time slice: 태스크에게 CPU가 할당된 후  다음 스케쥴링을 위한 Timer interrupt가 발생할 때까지의 시간

RR 알고리즘은 FIFO보다 성능이 좋으나 (response time이 적다는 것)

어떤 경우에는 반대일 때가 있음

CPU Burst size의 차이가 균일하다면 FIFO 성능 > RR의 성능

CPU Burst size의 차이가 크다면 FIFO 성능 < RR의 성능

Adaptive scheduling: Workload의 특성에 따라 Time Slice의 크기를 동적으로 바꿔주는 스케쥴링 기법

프로세스 특성 2가지

1. CPU Bound Process: 대부분의 시간을 CPU 연산을 하면서 보내는 것 (긴 CPU Burst를 갖음)

   CPU-bound 프로세스의 요구사항: 높은 CPU Utilization과 Throughput

2. I/O Bound Process: 대부분의 시간을 I/O를 보낸 후 waiting하면서 보내고 실제 CPU연산은 굉장히 짧게 하는 것 (작은 CPU Burst를 갖음)

    I/O-bound 프로세스의 요구사항: 짧은 Response Time

위 두가지 프로세스는 서로 스케쥴링 하는 방법이 다름

CPU Bound Process가 불필요하게 timer interrupt를 많이 만드는 문제를 어떻게 극복할까?

Adaptive scheduling을 하면 된다!

CPU Bound Process (Proc2)는 TS를 길게 주고, I/O Bound Process (Proc1)는 TS를 짧게 주면서 높은 우선순위를 준다

왜냐 shortest Job first가 optimal한 알고리즘이니까

OS이 Adaptive(조정할 수 있는)하게 workload에 따라서 그리고 workload 안에있는 프로세스의 특성에 따라서 time Quantum 사이즈를 Adaptive하게 바꾸려면 OS이 제일 먼저 무엇을 할 수 있어야 하는가?

OS관점에서 Adaptive scheduling을 하려면 제일 먼저 어떤 프로세스가 I/O bound인지 CPU bound인지 Characterize해야 함

그럼 어떻게 Characterize할 수 있을까?

Time Quantum을 주고 자기 Time Quantum 전에 I/O를 해서 CPU를 release하는 것은 short CPU burst이고 I/O bound하다고 생각할 수 있다

Time Quantum을 다 했는대도 계속 돌고 싶어하면 CPU bound일 확률이 굉장히 높다

MLFQ (Multi-Level Feedback Queue): Run Queue가 여러개 레벨로 있다 (제일 위의 큐가 우선순위 높음)

- 새로운 프로세스가 생성이 되면 가장 우선순위 높은 큐에 들어감

- 그리고 거기서 RR함

- RR 하다가 자기의 Time quantum보다 더 빨리 끝났으면 계속 그 queue에 머물러 있고

- 그렇지 않으면 그 아래 큐로 강등이 됨 

- 우선순위가 낮아지는 큐일수록 TS의 사이즈가 커짐

- I/O bound한 프로세스는 짧은 퀀텀과 높은 우선순위, CPU bound한 프로세스는 긴 퀀텀과 낮은 순위를 갖게 됨

- Exponential Queue라고도 함

- Exponential Queue 사용했을 때 Proc1, Proc2 수용되는 패턴을 보임

- Proc1 1ms 동안 돌다가 I/O request를 함 (Time quantum 전에 끝났으니 우선순위를 유지, 짧은 quantum 유지)

- Proc2 1ms 동안 도니 우선순위가 1개 낮아지고 time slice는 2로 증가 

MLFQ가 추구하는 것

- SJF 스케쥴링이 optimal이다.

- FIFO와 RR을 이용해서 기본적인 스케쥴러를 만들어 왔다

- 그럼에도 불구하고 workload Characterize을 고려해야 한다는 요구사항에 만족시키는 기법이다

Scheduling Policies (3)

지금까지의 스케쥴링 시스템은 general 했음

Real-Time System: 작업 수행이 요청되었을 때, 이를 주어진 시간 안에 성공적으로 마쳐야 하는 시스템

Priority-based Scheduling: 프로세스들에게 선호도를 매기고, 선호도가 높은 프로세스를 먼저 수행하는 스케줄링 기법

- general-purpose scheduling은 기본적으로 1/n 의 개념임

- 어떻게 fair하게 우선순위를 주는가? 일단 우선순위가 부여되면 Starvation 문제가 발생

Starvation: 수행할 준비를 마치고 CPU를 할당받기를 기다리는 프로세스가 무기한 연기되는 현상

- Mission Critical System에서는 중요하지 않은 프로세스가 starvation 되는 것은 문제가 되지 않음

이렇게 애플리케이션에 따라 Scheduling Policie도 굉장히 달라짐

general-purpose scheduling  -->  Priority Scheduling (Mission Critical System을 위한 것)  -->  Fair Share Scheduling

Fair Share Scheduling = Bandwidth Scheduling = Proportional Share Scheduling

대기 중인 프로세스들에게 정해진 비율에 따라 CPU의 Bandwidth를 분배하는 스케줄링 기법

Performance Isolation: CPU를 많이 차지할 것 같은 애플리케이션이 들어왔을 때 걔의 영향을 격리 시키는 것

예를들어 자동차 내부 임베디드 시스템이 리눅스 OS에 요구하는 것은 Head Unit이 자동차 관련기능에 CPU 비율을 높게 주고, 네비게이션 같은 브라우징 기능에는 CPU를 사용할 수 있는 량을 30% 이하로 제한 시켜 달라

- 리눅스 OS 안에는 CFS (Complete Fair Scheduling) 이라는 Bandwidth Scheduling이 있음 

Scheduling Policies 총 정리

- 제일 먼저 스케줄링이론을 갖고 출발 했을 때 사람들이 다 알고 있던 것은

- SJF 이것을 Preemptive하게 말하면 Shortest Remaining Time First 스케줄링이 Optimal 한 것이다

- 그런데 이 Remaining time을 예측하는 것이 불가능하다

- 어쩔 수 없이 FIFO를 사용해야 하는데 Non-preemptive하기 때문에 짧은 job이 와도 context switching을 못함

- 이런 문제를 극복하기 위해 Round Robin 스케줄링을 도입

- RR은 FIFO 스케줄링 알고리즘인데 굉장히 짧은 interval을 가지고 CPU burst size가 작은 것이 도착했는지 확인하는 기법

- RR 스케줄링을 기반으로 해서 OS를 구성했으나 Optimal하지 않은 workload들이 생겼음

- 이것을 Adaptive하게 조정하기 위해서 MLFQ 스케줄링 알고리즘을 도입함

- MLFQ 스케줄링 알고리즘이 해결할 수 없는 Mission Critical한 이슈들을 해결하기 위해 우선순위알고리즘(Priority-based Scheduling)이 사용됨

- 이것이 리눅스 2.4 - 2.6 커널의 이야기

- 최근들어 Performance Isolation이나 멀티미디어를 위한 Bandwidth Scheduling의 필요성이 증가 됐고

- 여러사람들이 이것을 만족시킬 수 있는 Fair share 알고리즘을 제시하기 시작함

- 제일 먼저 리눅스에서 Fair share 알고리즘으로 제시된 것이 Rotating Staircase Deadline Scheduler 임

- RSD: RR, MLFQ + 알파(Deadline) 자기의 데드라인값에 따라 큐의 중간, 앞, 뒤 다 들어갈 수 있다

예를들어, 내가 받아야 할 Bandwidth가 30%다. 그런데 이번 턴에 15% 밖에 못 받았다

그럼 이것은 데드라인이 짧기 때문에 앞으로 들어가서 곧 바로 CPU 받을 수 있게 됨

또 다른 예, 내가 받아야 할 Bandwidth가 30%인데 35%로나 받았다. 얘는 데드라인을 뒤로 해서 나중에 받게 됨 

이런식으로  MLFQ에 fair share scheduling을 가미한 것이 Rotating Staircase Deadline Scheduler됨

- 현재 리눅스는 CFS (Completely Fair Scheduler) 사용중

---

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=649

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=650