[Chapter 5] CPU scheduling

CPU & I/O bursts in program execution

: CPU를 한 번에 오래 쓰느냐, 짧게씩 쓰느냐

 

CPU burst = CPU를 할당받는 것

 

<I/O bound job>

: CPU 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 Job

: 양이 많지만 짧은 CPU burst

ex. 한글

 

<CPU bound job> = CPU 에 묶여 있는 자원 

: 계산 위주 job

: 양이 적지만 긴 CPU burst

ex. 신경망 학습

 

 

 

=> I/O bound job(=process)와 CPU bound job이 섞여있음

-> CPU 스케줄링 필요(CPU와 I/O장치 등 시스템 자원을 골고루 효율적으로 사용할 수 있도록)

* I/O bound job에게 먼저 할당하는 것이 나음

1. 짧게 실행되므로

2. 사용자와 관련이 있으므로

 

CPU scheduler & Dispatcher

 

<CPU scheduler>

: Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스 선택

 

<Dispatcher>

: scheduler에 이해 결정된 프로세스에게 실제로 CPU 제어권 넘김

("context switch" 수행)

 

 

<CPU 스케줄링이 필요한 경우>-(중요)

1. Running -> Blocked

하드디스크, I/O 등에 자료를 요청할 때 CPU는 사용되지 않기 때문에

2. Running -> Ready

할당시간 만료되었을 때 time interrupt 걸어 그만 쓰라고 함

3. Blocked -> Ready

I/O 작업 완료 후 완료되었다는 interrupt

4. Terminate

 

*(중요)*

1~4는 nonpreemptive(강제로 뺴앗지 않고 자진 반납) => timer 사용 필요 x

다른 모든 scheduling은 preemptive(강제로 빼앗음) => 이때 timer 사용

 

 

 

Scheduling Criteria(평가 원칙)

 

= Performance Index=Performance Measure(성능 척도)

 

CPU utilization(활용도)

: CPU 얼마나 잘 활용하는가

ex. A 알고리즘 CPU util < B 알고리즘 CPU util

=> B가 좋은 것

 

Throughput(산출물)

 

: 단위시간 동안 실행을 완료하는 프로세스 개수

 

Turnaround time

ex. A 알고리즘은 a->b->c->d->a->b->... 처럼 정해진 순서로 할당하지만, B 알고리즘은 랜덤으로 프로세스를 고른다고 해보자.

그래도 B 알고리즘이 더 빨리 끝난다면 B 알고리즘을 더 높게 평가

 

Waiting time

 

: ready queue에서 기다리는 시간 -> 최대한 짧게 머무는 것이 좋음

ex. A 알고리즘 - ready queue에서 기다리는 시간 10초

B 알고리즘 - ready queue에서 기다리는 시간 5초

=> B 알고리즘이 good

 

* blocked time은 평가 척도로 쓰지 않음(waiting time은 쓸 수 있는데 못 쓰는 것이고 blocked time은 쓸 수 없는 상태이기 때문)

 

Response time

 

: request 를 보냈을 때, 가장 첫 번째 response가 도착하는 시간(프로세스가 CPU를 처음 할당받게 되는 시간)

* output 이 아니라 response 처음 받는 시간 !

(time-sharing 환경에서)

 

Scheduling Algorithms

 

FCFS(First-Come-First-Service)

 

: 먼저 도착한 프로세스부터 선착순으로 CPU 할당

프로세스 도착 순서 p1->p2->p3일 때 -> CPU 할당 순서 p1 -> p2 -> p3

 

"waiting time"

p1=0, p2=24, p3=27

-> "average waiting time(AWT)" = 17

 

<단점>

"convoy effect" 때문에 도착 순서에 따른 성능 편차가 큼

ex. 도착 순서가 p2->p1->p3으로 달라졌을 때

* convoy effect: 긴 프로세스 뒤에 짧은 프로세스

 

"waiting time"

p1=6, p2=0, p3=3

-> AWT = 3

 

=> p1->p2->p3일 때와 p2->p1->p3일 때 성능 차이가 너무 많이 남(17초/3초)

 

 

SJF(Shortest-Jov-First)

 

: CPU burst time(CPU 할당시간)이 가장 짧은 프로세스부터 스케줄링

 

하지만 하나의 프로세스 실행 도중 더 짧은 프로세스가 도착했을 때 어떻게 하느냐에 따라

nonpreemptive와 preemptive로 나뉜다.

 

1. Nonpreemptive

: 일단 CPU를 잡으면, 더 짧은 프로세스가 도착해도, 이번 CPU burst가 완료될 때까지 CPU를 선점당하지(뺏기지) 않음

: 쉽게 말해, "나 길게 안 쓸건데 먼저 써도 될까?"가 불가능.

 

2. Preemptive("선점당하다")

: =Shortest-Remaining-Time-First(SRTF)

: 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김.

: 쉽게 말해, "나 길게 안 쓸건데 먼저 써도 될까?"가 가능.

 

=> keyboard, mouse, harddisk 등 디바이스를 만들 때 중요한 기능으로 작용

 

<다음번 CPU burst time을 어떻게 알 수 있는가?>

 

: 과거의 예측값과 과거의 실제 CPU 사용 시간을 통해 예상 사용 시간 추정(지수 사용한 평균값 계산)

 

"a=0"

: τn+1 = τn

: 예측값 = 실제 사용 시간

=> 예측값을 사용

 

"a=1"

: τn+1 = tn

: 실제 사용 시간만 사용

 

 

a와 1-a가 둘 다 1 이하이므로 후속 term은 선행 term보다 적은 가중치 값을 가진다.

 

 

<Priority Scheduling>

: 각 프로세스마다 우선순위 숫자가 주어짐 -> 높은 우선순위 가진 프로세스일수록 CPU 먼저 할당

=> SJF는 일종의 priority scheduling(다음 CPU burst time 예측해서 우선순위 지정하기 때문)

 

(문제점)

: (중요)Starvation - 낮은 우선순위의 프로세스는 영원히 CPU 할당 못 받을 수도 있음

(해결책)

: Aging - 시간이 갈수록 우선순위 높여줌 -> 굶어죽지 않도록

 

Round Robin(RR)

 

각 프로세스는 동일한 크기의 할당 시간(퀀텀 quantum) 가짐 -> 할당 시간 끝나면 선점당하고 ready queue의 맨 뒤에 줄 다시 섬

=> 기본적으로 preempted 방식 !!

- q 크면 => FIFO선착순

- q 작으면 => context switch 오버헤드 커짐

=> 적절한 q값 설정해야 CPU 효율적으로 사용 가능

 

(+) response time 짧음: 일정 시간 내에 response가 무조건 온다는 확신 있음

* n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU tlrksdml 1/n을 얻음 -> 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음.

ex. 100개의 프로세스가 있으면 최대 99q만 기다리면 되기 때문에 보장된 방식

 

(-) SJF에 비해 average turnaround time 긺

 

!!Turnaround Time Varies WIth ~ 페이지 보지 말 것!!

 

 

<Multilevel queue>-사용 사례

: ready queue 여러 개로 분할(foreground/background)

"foreground" : RR 사용

* response time이 빨라야 하기 때문에 

"background" : FCFS 사용(온 순서대로)

* 시간 제한 별로 없기 때문(빨리 안 끝내도 되기 때문)

 

- Fixed priority scheduling

: foreground 먼저 처리 -> background 처리

(-) background 작업에 대한 starvation 발생 가능

 

- Time slice

: time slot 나눠서 각 queue에 CPU time 적절한 비율로 할당

ex. foreground에 80%, background에 20% 할당

 

<Multilevel Feedback Queue>

 

- 프로세스가 다른 큐로 이동 가능

- 에이징과 같은 방식으로 구현 가능

 

- Multilevel-feedback-queue scheduler를 정의하는 파라미터들

1. Queue의 수

2. 각 큐의 scheduling algorithm

* 각 큐가 각각 RR, FCFS ..등 어떤 알고리즘을 쓸 것인지 프로그램(한글 등)의 특성에 맞게 결정

3. Process를 상위 큐로 보내는 기준

* priority가 높은 경우 거꾸로 올려보냄

4. Process를 하위 큐로 내쫓는 기준

* 8ms 내에 완료하지 못하면 어떻게 하겠다.

5. 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

* 프로그램 특성상 중요하지 않은 것은 애초에 밑으로 빼놓음

 

큐의 특성에 따라 CPU를 각 프로세스에 할당하고, 다 수행되지 못했다면 아래 큐로 쫓겨나는 방식이다.

 

<그 외 특징>- 용어 의미만 알아두자

- homogeneous processor: CPU core가 여러 개

- Load sharing: 몰리지 않도록 부하 적절히 공유

- Symmetric Multiprocessing(SMP): 각 프로세서가 알아서 스케줄링

- Asymmetric Multiprocessing: 하나의 프로세서가 지휘자 역할 -> 나머지 프로세스 스케줄링 책임짐

 

참고할 것들-여기도 그냥 알아두기만 하자

 

<Real-time scheduling>

- hard real-time systems

: 정해진 시간 안에 반드시 끝내도록

- soft real-time computing

: soft real-time task는 일반 프로세스에 비해 높은 priority

 

<Thread scheduling>

- Local Scheduling: 거의 없음

- Global Scheduling: kernel level thread의 경우 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

 

<Algorithm Evaluation>

- Queueing model

: 손으로 계산

* 코드 두지 않고 그냥 페이퍼 상에서 입력값을 통해 performance index 값 계산

- Implementation & Measurement

: 코드 작성하는 방법

- Simulation

: 모의 프로그램 만들어 보는 방법