CPU 스케쥴링

CPU 스케쥴링 개요

•

일을 쉬지않고 계속 시키는 것이 OS의 숙제! 
⇒ Maximize CPU utilization

•

CPU – I/O 버스트(Burst) Cycle
→ 프로세스 실행은 CPU 실행 및 입출력(I/O) 대기로 구성

OS는 프로세스로부터 CPU를 회수 → 다른 프로세스에게 CPU를 의뢰 → 할당

•

CPU 버스트 분포
→ 많은 수의 짧은 CPU 버스트와 적은 수의 긴 CPU 버스트 존재

◦

burst time은 스케쥴링의 중요한 기준 중 하나

•

프로세스의 수행 = CPU 사용(cpu burst) + I/O 대기(I/O burst)

◦

I/O-bound 프로그램 (입출력 지향) → 많은 수의 짧은 CPU 버스트

◦

CPU-bound 프로그램 (CPU 지향)→ 적은 수의 긴 CPU 버스트

cpu burst time 도표

짧은 burst duration ~ 높은 빈도

긴 burst duration ~ 낮은 빈도

프로세스를 스케쥴링하기 위한 큐 (Queue)

프로세스는 실행되는 동안 다양한 스케쥴링 큐 사이를 이동

운영체제는 이러한 스케쥴링 큐에서 프로세스들을 선택하기 위한 스케쥴러 사용

•

Job queue : 현재 시스템 내의 모든 프로세스들의 집합

•

ready queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스들의 집합

•

Device queue : I/O device의 처리를 기다리는 프로세스의 집합

CPU 스케쥴러?

스케줄링은 시스템의 목표를 달성하기 위해 프로세서를 할당하는 일련의 과정.

메모리에 있는 프로세스들 중 실행할 준비가 되어있는 ready 상태의 프로세스를 선택하고, 그 프로세스에 CPU를 할당 → 단기 스케쥴러가 수행

비선점(Non Preemptive)

•

할당받은 자원을 자진해서 반납하고 문맥 교환(뺏을 수 없다)

◦

system call, I/O 등

•

context switch overhead가 적음

•

잦은 우선 순위의 역전, 평균 응답 시간 증가

선점(preemptive)

•

타의에 의해 자원을 빼앗기고 문맥교환  (뺏을 수 있다)

•

context switch overhead가 큼 ⇒ 프로세스가 자주 바뀜

•

Time sharing system, real time system 등에 적합 → 응답성이 높다

•

경쟁이 불가피, 정합성 이슈

•

CPU 스케쥴링 결정은 다음의 네 가지 상황에서 발생

한 프로세스가 실행 상태(running)에서 대기 상태(blocked)로 전환 될 때 → 비선점

프로세스가 종료(terminated)될 때 → 비선점

프로세스가 실행 상태(running)에서 준비 완료 상태(ready)로 전환될 때 → 선점

프로세스가 대기 (blocked 상태)에서 준비 완료 상태(ready)로 전환될 때 → 선점

디스패쳐(Dispatcher)

디스 패쳐 작업

•

CPU의 제어권을 CPU 스케쥴러에 의해 선택된 프로세스에게 넘김

•

프로세스의 레지스터에 적재(문맥 교환)

◦

모든 context switch에서 호출

•

운영체제의 커널 모드(kernel mode) → 사용자 모드(user mode) 전환

•

프로그램을 다시 시작하기 위해 사용자 프로그램이 올바른 위치를 찾을 수 있도록 적절한 위치로 이동

디스패치 지연(dispatch latency)

•

하나의 프로세스를 중지하고 다른 프로세스를 실행시킬 때 소요되는 시간

•

적으면 적을 수록 좋다

스케쥴링 기준

CPU 이용률(utilization) → Max

•

CPU를 가능한 최대한 바쁘게 유지

처리량(Throughput) → Max

•

단위 시간 당 완료된 프로세스의 개수

총 처리 시간(Turnaround time) → Min

•

프로세스의 제출 시간과 완료 시간과의 간격

대기 시간(Waiting time) → Min

•

준비 완료 큐에서 대기하면서 보낸 시간의 합

응답 시간(Response Time) → Min

•

작업요청으로부터 하나의 요구를 제출한 후 첫번째 응답이 발생할 때까지의 시간 (응답 출력하는데 걸리는 시간 X) 

도착 → 준비 큐 도착(프로세스 도착)

시스템 스케쥴링 기준

모든 시스템은 아래의 기준을 충족해야 함

•

No starvation

◦

최대한 기아 상태 없이

•

공평함(fairness)

◦

모든 프로세스가 CPU를 공평하게 

•

균형, 효율성 :

◦

모든 시스템의 부분들이 바쁘게

Batch Process system

•

maximize Throughput

•

minimize Turn around time

•

maximize cpu utilization

Interactive system

•

minimize variance in response time

real time system

•

deadline

•

predictabilty

Starvation(기아)

•

특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태를 말한다.

•

나쁜 스케쥴링 정책이 기아문제 초래

◦

높은 우선순위 프로세스가 낮은 우선순위 프로세스를 실행으로부터 지속적으로 멀어지게 한다

•

동기화 문제 또한 기아 문제 초래

◦

지속적인 reader 요청 ← writer 접근 불가

Aging(에이징)

•

기아 문제를 해결할 해결책

•

쓰레드의 스케쥴링 우선순위를 준비 큐에 기다린 시간의 비율에 따라 올려준다

•

혹은 lock 시도 횟수에 따라 쓰레드 스케쥴링 우선순위 증가

•

최종적으로 높은 우선순위에 도달해서 기아문제 해결 

스케쥴링 알고리즘

비선점(Non-Preemptive) 스케줄링

•

running → waiting, terminated

•

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법

•

프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용

•

모든 프로세스에 대한 요구를 공정하게 처리 가능

•

일괄 처리 방식에 적합, 중요한 작업이 기다리는 경우가 발생할 수 있음

•

응답시간 예측이 용이

•

종류 : FCFS(FIFO), SJF, 비선점 우선순위, HRN, 기한부 등 알고리즘

선점(Preemptive) 스케줄링

•

waiting → ready, running → ready

•

하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

•

우선순위가 높은 프로세스를 빠르게 처리할 수 있음

•

주로 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용

•

선점으로 인한 많은 오버헤드를 초래함

•

선점을 위해 시간 배당을 위한 인터럽트용 타이머 클럭(Clock)이 필요

•

종류 : 선점 우선순위, RR(Round Robin), 다단계 큐(MLQ), 다단계 피드백 큐(MFQ) 등 알고리즘

선입 선처리 스케쥴링
(First-come, First-Served, FCFS)

•

CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받음

•

FIFO 큐로 관리

•

Batch system에 적합

•

장점

◦

가장 간단한 형태

◦

코드 작성이 쉽고 이해하기 쉬움

◦

자원을 효율적으로 사용 가능(높은 자원 활용성) → 스케쥴 오버헤드가 적음

•

단점

◦

순서에 따라 대기 시간의 차이가 큼

◦

모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다려야 함(호위효과, Convoy effect)

▪

Convoy effect

•

하나의 수행시간들이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상 (대기 시간 >> 실행 시간)

◦

비선점형(긴 평균 응답 시간)이기 때문에, 시분할 시스템에 부적합

최단 작업 우선 스케쥴링
(Shortest-Job-First, SJF)

•

CPU burst가 짧을 수록 CPU를 먼저 할당 받음

•

장점

◦

평균 대기 시간 최소화

◦

시스템 내 프로세스 수 최소화

◦

많은 프로세스들에게 빠른 응답 시간 제공

•

단점

◦

다음 CPU 요청의 길이 파악이 어려움 (예측이 어려움)

◦

Starvation 현상 발생

▪

Burst time이 긴 프로세스는 자원을 할당받지 못 할 수 있음

•

Aging으로 해결

•

선점형 최단 작업 우선 스케쥴링(Preemptive SJF)

선점형 : 새로운 프로세스가 도착한 후 수행중인 프로세스의 잔여 Burst time 비교하여 그 중에서 최단 burst time process를 가지고 CPU를 빼앗아 작업을 수행

•

비선점형 최단 작업 우선 스케쥴링(Non Preemptive SJF)

→ 비선점형은 도착한 프로세스들과의 비교를 현재 수행하고 있는 프로세스를 완료시킨 후 수행한다.

우선 순위 스케쥴링
(Priority)

•

우선순위가 프로세스들에 연관되어 있으며, 높은 우선순위를 가진 프로세스에게 CPU 할당

•

MLQ(Multi Level Queue)

•

MFQ(Multi level Feedback Queue)

•

장점

◦

내부적 정의(시간제한, 메모리 요구, open files수 등) 활용 가능

◦

외부적 정의(프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양 등) 활용 가능

•

단점

◦

무한 봉쇄, 기아 상태 → Aging 고려

▪

우선 순위가 밀려서 프로세스를 잃어버림

▪

오랫동안 방치된 우선 순위를 올려주는 방식

•

MLQ(Multi Level Queue)

◦

작업 타입(우선 순위) 별로 별도의 ready queue를 가짐

▪

최초 배정된 queue를 벗어나지 못함

▪

각각의 queue는 자신만의 스케줄링 기법 사용

▪

Queue의 구성은 정책에 따라 결정

◦

Queue 사이에는 우선 순위 기반의 스케쥴링 사용

◦

Queue 별로 별도의 스케쥴링 알고리즘을 가짐

▪

포어 그라운드 - 라운드 로빈

▪

백그라운드 - FCFS

◦

각 큐는 일정 비율로 CPU를 나누어 사용

▪

포어그라운드 큐 - cpu 시간의 80%

▪

백그라운드 큐 - cpu 시간의 20%

◦

장점

▪

우선순위가 높은 프로세스에 한해서 빠른 응답 시간 

◦

단점

▪

여러 개의 Queue 관리 등 스케줄링 overhead

▪

우선 순위가 낮은 queue는 starvation 현상 발생 가능

•

MFQ(Multi level Feedback Queue)

◦

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

◦

프로세스를 CPU burst 성격에 따라 구분

◦

Feedback을 통해 우선 순위 조정 (Aging)

▪

현재까지의 프로세서 사용 정보 및 패턴 활용

▪

기아 상태를 예방

◦

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

◦

MFQ는 다음의 파라미터에 의해 정의

▪

큐의 개수

▪

각 큐를 위한 스케쥴링 알고리즘

▪

우선 순위 조정 기준

•

한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법

•

한 프로세스를 낮은 우선순위큐로 강등시키는 시기를 결정하는 방법

▪

최초 큐 배정 방법

•

프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법

◦

단점

▪

설계 및 구현이 복잡, 스케쥴링 오버헤드가 크다.

◦

변형

▪

각 준비 큐마다 시간 할당랼(quantum)을 다르게 배정

•

프로세스의 특성이 맞는 형태로 운영 가능

▪

입출력 위주 프로세스(I/O bounded)들을 상위 단계의 큐로 이동, 우선 순위 높임

•

프로세스가 block될 때 상위의 준비 큐로 진입하게 함

•

시스템 평균 응답 시간 줄임, 입출력 작업을 분산 시킴

▪

대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동 ⇒ Aging

◦

예시

▪

Q0 : 시간 할당량 8ms. RR / Q1 : 시간할당량 16ms. RR / Q2 : FCFS

•

스케쥴링 시나리오

◦

새로운 job이 Q0으로 진입. 시간할당량 8ms 내에 종료되지 않을 경우 Q1으로 이동

◦

Q1으로 진입한 프로세스가 시간할당량 16ms 내에 종료되지 않을 경우 Q2로 이동

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

•

선점형 

•

스케쥴링 기준은 도착 시간, 먼저 도착한 프로세스를 먼저 처리 ⇒ FCFS를 베이스로 함

•

시간 할당량(Time Quantum)이라고 일컫는 작은 단위의 시간을 정의

◦

한 번에 한 프로세스에게 한 번의 시간 할당량 동안 CPU를 할당

◦

FCFS + Time Quantum

•

장점 

◦

대화형(interactive), 시분할(real time) 시스템 최적화

•

단점

◦

시간 할당량(Time Quantum)에 따른 성능에 영향이 존재(성능 변화가 생김)

◦

너무 클 경우 – FCFS와 동일한 알고리즘이 됨

◦

너무 작을 경우 – Context Switch에 시간을 더 뺏김(Context Switch overhead 증가)

▪

너무 작을 경우에는 모든 프로세스가 각각 프로세서 위에서 동시에 실행되는 느낌

•

Time quantum 별 평균 총처리 시간 예시

•

예시 (Time Quantum = 2)

•

예시 (Time Quantum = 3)

OS 스케쥴링

UNIX System

•

Interactive system

◦

Priority-based scheduling, preemptive scheduling

•

Priority

◦

Kernel priority

▪

커널 모드에 있는 프로세스

▪

interruptible/uninterruptible priority

◦

User priority

▪

사용자 모드에 있는 프로세스

•

Clock handler

◦

주기적으로 인터럽트 발생

◦

모든 프로세스들의 우선순위 조정

•

스케줄링 기법

◦

높은 우선 순위 우선

▪

프로세서 사용량에 따라 우선순위가 주기적으로 변함

◦

MFQ 스케줄링 기법

•

우선순위 조정

◦

프로세서 사용 반영 (decay computation)

◦

우선순위 조정

Window System

•

Thread scheduling

•

Priority-based, Preemptive scheduling

•

32-level priority scheme

◦

Variable class: 1-15

◦

Real-time class: 16-32

•

MLQ scheduling

◦

각각의 우선순위 마다 큐(queue)를 가짐

◦

스케줄러(scheduler)는 높은 우선순위 큐부터 순차적으로 방문하며, 실행할 준비가 된 스레드를 찾음

•

스케줄링 기법

◦

스레드가 자신의 time quantum을 다 소비하고 나올때
→ 우선순위 하향 조정 (variable class의 경우)

◦

Wake-up 시 → 우선순위 상향 조정 (variable class의 경우)

▪

상향 정도는 스레드가 대기 중이었단 작업에 종속적

•

예) 
키보드/마우스 I/O → 크게 상향
디스크 I/O → 약간 상향