[OS기초] CPU Scheduling

# Resource Scheduling 

<2가지 측면의 resource>

- preemptable resource : 양보가 가능한 리소스. 한 프로세스가 점유한 상태에서 다른 프로세스에게 양보가 가능한 자원.  CPU, memory...

- non-preemptable resource : 한 프로세스가 점유하면 사용을 마칠 때까지 다른 프로세스에게 양보할 수 없는 자원. printer...

<CPU 스케쥴링>

1. CPU를 어느 프로세스에게 줄 것인지의 문제

2. 얼마만큼 오래 CPU를 할당해 줄것인지의 문제

- CPU Bursts : 프로그램의 수행 중에 연속적으로 CPU를 사용하는 단절된 구간. 스케줄링의 단위. 

- I/O Bursts : 프로그램의 수행중에 I/O의 완료를 기다리며 블록되는 구간

*Batch Monitor에서의  Job :  한번 수행을 시작하면 수행을 완료할 때 까지 쭉 하는 것

Process : 끝나지 않은 여러개의 Job이 동시다발적으로 수행될 수 있음

- CPU Bursts Size

Burst Size가 큰 작업 : 과학기술 연산 등 CPU intensive한 작업

Burst Size가 작은 작업 : 터치패드 동작 등 I/O interactive 한 작업

- CPU Scheduling

1. 어떤 프로세스를?

2. 얼마나 오랫동안?

- CPU State Transition

: new, terminate, ready, running , waiting 

: ready -> running : dispatching(not scheduling)

: running -> ready : 하드웨어 인터럽트. OS의 스케줄러가 개입(preemptive scheduling)

: running -> waiting : 자기 스스로 CPU Yield하여 (non-preemptive scheduling)

: running -> terminating : non-preemptive scheduling

: waiting -> ready : preemptive scheduling

# Scheduling Policies

- Aging : 태스크가 CPU를 기다리는 시간에 비례하여 우선순위를 점진적으로 높여주는 기법

- Scheduling Objective

Maximize resource utilization, 의미있는 수행을 극대화시키기, CPU, I/O Device, ...

Minimize overhead

Minimize context switches

Distribute CPU cycles equitably, fairness =>FIFO, Priority, Aging ...

- Maximize Throughput, CPU intensive(background codex algorithms)

- Minimize Response time, foreground app

- Minimize Turnaround time 

- Minimize Waiting time 

* Response time관련의 예

: 아이폰과 안드로이드 젤리빈의 스크린 터치 스와핑

아이폰 : in-house OS로 스크린 터치 스와핑을 최적화

안드로이드 : 리눅스 OS기반으로 다양한 환경(Server, Cloud, Moblie,...)에서 사용하다보니 CPU intensive의 문제도 배제할 수 없어 최적화 시키지 못함

=> 여러가지 fake기술을 통해 극복 (백터 알고리즘을 미리 예측하는 기술 등)

# Scheduling Policies

- FIFO (First In First Out)

: CPU Burst 단위로 FIFO를 수행, preemtive scheduling, blocked의 단위로 종료

: Blocked이 일어나야 종료되므로, 한 CPU Burst안에 무한 루프가 있으면 CPU가 monopolized될 수 있음. => timeout 설정(RR)

: short time 작업에 대한 수행을 먼저 처리하지 못함

* CPU Burst : CPU 실행, I/O Burst : 입출력 대기

- SJF (Shourtest Job First) : Optimal Algorithm, 개념적 알고리즘임 

: SJF에서는 OS가 태스크의 남은 CPU Burst Size를 예측할 수가 없음. (burst size와 지난 예측 값 등으로 알파값을 구하여 CPU Burst Size를 예측을 하기도 함)

- preemtive SJF : re-scheduling, STCF(Shortest Time to Completion First) => 남은 시간을 계산

- non-preemtive SJF : no re-scheduling 

- RR (Round Robin)

: 기본적으로 FIFO수행, timeout 값까지만 수행하고 다시 ready-queue로 반환되고 다시 수행됨. => CPU Burst가 작은것 먼저 수행되게 됨

* Time Slice(Time Quantum) : time out 값, 태스크에게 CPU가 할당된 후 다음 스케줄링을 위한 timer interrupt가 발생할 때 까지의 시간

*work load의 패턴에 따라 FIFO가 RR보다 성능이 좋을 때가 있음

* Slide Switch 모델의 도입

: FIFO(or RR(TS=∞)) <----[switch]------> RR(TS=0)

=> dynamic한 algorithm이 필요하게 됨

=> "Adaptive Scheduling" : workload와 workload안에 있는 프로세스의 특성에 따라 Time Slice의 크기를 동적으로 바꿔주는 스케줄링 기법

CPU Bound Process의 요구사항 CPU utilization과 Throughput

I/O Bound Process의 요구사항 짧은 ResponseTime

- MLFQ (Multi Level Feedback Queue)

* Real-time System : 작업 수행이 주어진 시간안에 성공적으로 마쳐야하는 시스템. 비행기 항법제어 등등

=> priority 중요!

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

반대로, gerneral performance program에서 priority-based scheduling이 알맞지 않은 이유

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

* 리눅스 2.4 ~ 2.6

- Fair Share Scheduling : Bandwidth Scheduling, Proportial Share Scheduling 이라고도 함

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

* Performance Isolation : 어떤 CPU를 많이 차지할 것 같은 애플리케이션이 들어오면 그 애플리케이션의 영향을 격리시키는 것 (자동차 OS의 제어)

* 멀티미디어

=> Bandwidth Scheduling이 필요. (실제로, 리눅스에는 CFS(Completely Fair Scheduler)가 들어있음)

* rotating Staircase deadline  scheduler : CPU를 빼앗기면 큐의 맨 뒤로 가는게 아니라 자신의 데드라인에 따라서 큐의 중간, 맨앞, 맨뒤로도 갈 수 있음

제일 처음으로 Fair Share Scheduler로 채택

=> CFS, 리눅스의 기본 커널 스케줄러 - 리눅스 2.6.23 ~