9장 단일처리기 스케줄링

(1)

9 장 단일처리기 스케줄링 9 장 단일처리기 스케줄링

9 장의 강의 목표

• 처리기 스케줄링의 유형을 이해한다 .

• 단일처리기 시스템에서 여러 단기 - 스케줄링 방식들의 동작 원리를 이해한다.

• 단일처리기 시스템에서 여러 단기 - 스케줄링 방식들의 장단

점을 이해한다 .

(2)

목 목 차 차

9.1 처리기 스케줄링의 유형 9.2 스케줄링 알고리즘들

9.3 전통적인 유닉스 시스템에서의 스케줄링

제9 장 단일처리기 스케줄링 3

9.1 처리기 스케줄링의 유형

• 처리기 스케줄링의 정의

– 응답 시간이나 처리량, 효율성을 증대시키기 위해 처리기가 다음 에 실행할 프로세스를 선택하는 것!

• 선후 관계에 따른 스케줄링의 유형 3 가지

장기 스케줄링 d f lti i 을 결정 – 장기 스케줄링: degree of multiprogramming을 결정 – 중기 스케줄링: swapper의 역할

단기 스케줄링 CPU스케줄링에 해당 – 단기 스케줄링: CPU 스케줄링에 해당

(3)

9.1 처리기 스케줄링의 유형 - 개요 ( 계속 )

• 프로세스 상태와 스케줄링 유형과의 관계

• 스케줄링 단계와 프로세스 상태와의 관계

9.1 처리기 스케줄링의 유형 - 개요 ( 계속 )

• 프로세스가 일생 동안 거치는 스케줄링 큐 다이어그램

• 스케줄러의 성능 Î 프로세스들이 일생 동안 각종 큐에서

대기하는 시간을 얼마나 줄일 수 있을 것이냐 하는 문제

(4)

장기 스케줄링

9.1 처리기 스케줄링의 유형

• 새 프로세스의 시스템 진입 허용 여부를 결정

– 다중프로그래밍의 정도를 결정함 – 새로운 프로세스의 진입 허용 시점은?

시스템 내의 부하 절과 관련

• 시스템 내의 부하 조절과 관련

• 시스템 포화 상태 여부

어떤 규정으로 작업들을 골라 프로세스로 만들어줄 것인가?

– 어떤 규정으로 작업들을 골라 프로세스로 만들어줄 것인가?

• FCFS (First-Come-First-Served)

• Priority-basedPriority based

• CPU-burst 길이

• 입출력-중심(I/O-bound) 프로세스 우대

• 여유 입출력 자원 사용 예정 프로세스 우대

중기 스케줄링

• 스와핑 (swapping) 기능의 일부

– 스왑 공간으로 쫓겨나간(swap-out) 프로세스 전체 또는 일부 중 어느 것을 다시 주 메모리로 스왑인(swap-in)할 것인가?

(5)

단기 스케줄링

• 디스패쳐 (dispatcher) 라고도 함

– 장기/중기 스케줄러보다 매우 자주 실행

– 세밀한 기준으로 다음 번에 실행시킬 프로세스를 선정

• 단기 스케줄러 실행 시점

– 클럭(타이머) 인터럽트(시간할당량 만료 시) – 입출력 인터럽트

– 운영체제 시스템 호출(커널 내 preemption point 또는 사용자 모드 로 복귀하기 직전)

로 복귀하기 직전)

– 신호(signal)(예를 들면, 세마포어)

9.2 스케줄링 알고리즘: 단기 스케줄링 평가 기준

• 기준 1 : 사용자 중심 관점 vs. 시스템 중심 관점

사용자 중심 관점 – 사용자 중심 관점

• 개별 사용자 또는 개별 프로세스의 입장에서 자신들에게 긍정적인 영향을 미치는 스케줄러와 그렇지 못한 스케줄러를 평가

• 예: 응답 시간(Response Time)

– 프로세스가 요구한 작업 요청에 대해 시스템이 최초로 출력을 내주기 시 작할 때까지 걸린 시간

– 시스템 중심 관점

• 스케줄러가 처리기를 얼마나 효율적으로 활용했느냐?

• 예: 처리량(Throughput)

– 단위 시간 안에 실행을 완료시킬 수 있는 프로세스의 수

– 어느 한 관점만을 중시하면 다른 관점이 안 좋아짐!어느 한 관점만을 중시하면 다른 관점이 안 좋아짐!

– 모든 시스템에서 중시해야 할 관점 Î 사용자 중심 – 시스템 유형 별로 중시해야 할 관점이 다를 수 있음

• 예) 단일처리기 시스템Î시스템 중심 관점이 상대적으로 덜 중요!

(6)

단기 스케줄링 평가 기준들 ( 계속 )

9.2 스케줄링 알고리즘

• 기준 2 : 성능 중심 관점 vs. 성능 외적 관점

– 성능 중심 관점

• 대부분 정량적인 척도Î측정이 용이함. 성능 외적(기타)관점

– 성능 외적(기타) 관점

• 대부분 정성적인 척도Î측정이 어려움

• 예: 예측 가능성(Predictability)

스케줄링 평가 척도

9.2 스케줄링 알고리즘 단기 스케줄링 평가 기준들

(7)

스케줄링 평가 척도 ( 계속 )

9.2 스케줄링 알고리즘 단기 스케줄링 평가 기준들

우선순위 기반 스케줄링

• 우선순위가 높은 프로세스를 먼저 실행 !

– 우선순위별 대기 큐를 별도로 두고,

– 높은 우선순위의 대기 큐에 있는 프로세스를 먼저 실행

우선순위[RQi] > 우선순위[RQj] for i < jj

• 같은 우선순위 큐 내에서는 어떤 정책을 쓸 것인가?

– 순수 우선순위 기반 스케줄링의 문제점 : Starvation!Starvation!

(8)

다양한 스케줄링 정책들

• 비교 기준 1 : Selection Function

– 다음 번 실행을 위해 준비 큐에서 대기 중인 프로세스 중 하나를 고를 때 사용하는 알고리즘

Function Factors – Function Factors

• w= 대기한 시간과 실행한 시간을 모두 합쳐 시스템에 들어온 후 지

금까지 경과한 시간

• e= 지금까지 실행하는 데에만 걸린 시간

• s= 프로세스가 시작해서 종료하기까지 걸릴 총 서비스 시간

– 선택 함수의 예

• max[w] : 시스템에 진입한지 가장 오랜 시간을 보낸 프로세스를 선택 하라는 것ÎFCFS를 의미!

하라는 것ÎFCFS를 의미!

비교 기준 2 : Decision Mode

9.2 스케줄링 알고리즘 다양한 스케줄링 정책들

• 선택 함수가 호출되는 시점이 언제인가 ?

• 비선점 (nonpreemptive)

– 프로세스가 일단 실행 상태(Running state)에 진입하면 종료되거 나 자발적으로CPU를 놓을 때까지는 CPU를 빼앗기지 않는다 나 자발적으로CPU를 놓을 때까지는 CPU를 빼앗기지 않는다.

• 선점 (preemptive)

– 현재 실행 중인 프로세스라 할지라도 운영체제에 의해 인터럽트 가 걸려 비자발적으로 준비 큐로 이동될 수 있다.

nonpreemptive모드보다 문맥 교환 횟수가 많아지긴 하지만

– nonpreemptive 모드보다 문맥 교환 횟수가 많아지긴 하지만,…

– 한 프로세스가 처리기 시간을 독점하는 것을 방지할 수 있어 효율 적인 스케줄링이 가능함!

적인 케줄링이 가능함

(9)

스케줄링 기법들의 동작 방식 비교

• 스케줄링 기법 비교를 위한 프로세스들

First Come First Served

• First-Come-First-Served

– FIFO(First-In-First-Out) 라고도 함

프로세스는 준비 상태가 되면 준비 큐에 들어간다 – 프로세스는 준비 상태가 되면 준비 큐에 들어간다.

– 현재 실행 중인 프로세스가 실행을 종료Î 준비 큐에서 대기 중 이던 프로세스 중 가장 오랫동안 기다렸던 프로세스가 다음 번 실 행 프로세스로 선정됨

FCFS (계속)

( )

• First-Come-First-Served( 계속 )

– FCFS는 짧은 프로세스보다는 긴 프로세스에게 유리 Î

N ti 모드로 동작하기 때문!

Nonpreemptive 모드로 동작하기 때문!

– 입출력 중심의 프로세스보다처리기 중심 프로세스를 우대하는 경향이 나타남

경향이 나타남

– FCFS는 결국 비효율적 스케줄링 기법이지만…

• 우선순위 기법과 결합하면 성능이 많이 나아짐!

(10)

라운드-로빈(Round-Robin)

( )

• FCFS에서 짧은 프로세스가 피해보는 현상 완화 방법

– 시간을 측정하고 있다가 어떤 긴 프로세스가 일정 시간 이상을 넘어 가는 순간 실행을 강제로 중단시키는(preemption)것

•

프로세스 실행 시간 측정 방법

•

프로세스 실행 시간 측정 방법

– 클럭(clock) 인터럽트(또는 타이머 인터럽트) 클럭 인터럽트는 일정 간격으로 주기적으로 발생 – 클럭 인터럽트는 일정 간격으로 주기적으로 발생

•

라운드-로빈 스케줄링 기법 동작 방식

클럭 인터럽트가 발생하면 클럭 인터럽트 서비스 루틴이 실행되고 – 클럭 인터럽트가 발생하면 클럭 인터럽트 서비스 루틴이 실행되고, – 클럭 인터럽트 서비스 루틴은 현재 실행 중이던 프로세스를 준비 큐

로 이동시키고,

– 준비 큐에서FCFS 방식으로 다음 번 프로세스를 골라 실행시킴

•

시간 할당량

(time slicing,

또는

time quantum)

기법이라고도 함

라운드-로빈(Round-Robin) (계속)

( ) ( )

• 시간할당량의 크기(q)가 라운드-로빈 성능에 미치는 영향

– 시간할당량이 너무 작다면?시간할당량이 너무 작다면? ÎÎ 문맥교환 오버헤드가 증가문맥교환 오버헤드가 증가 – 시간할당량이 너무 크다면? Î FCFS와 비슷해짐

• 시간할당량의 권장 길이 시간할당량의 권장 길이

– 프로세스가 사용자와 최소한 한 번 이상 대화하기에 충분하거나 – 프로세스 내의 어떤 한 함수 정도는 실행을 마칠 수 있는 충분한

길이

(11)

라운드 - 로빈 (Round-Robin) ( 계속 )

• 시간 할당량의 크기가 스케줄링에 미치는 영향

( ) ( )

라운드-로빈(Round-Robin) (계속)

• 단점 : 입출력 중심 프로세스보다 처리기 중심 프로세스를 우대할 수 밖에 없는 현상이 여전히 발생함!

( ) ( )

우대할 수 밖에 없는 현상이 여전히 발생함!

• 해소 방법 : 가상 라운드 로빈 _(VRR) 스케줄링 방식

• 입출력 중심 프로세스와 처리 기 중심 프로세스를 분리하여 준비 큐를 둠.

• 계산하던 중 시간할당량을 다 썼다면 그냥 준비 큐로 들어 감감.

• 입출력 요청으로 CPU를 반납 했다면 입출력 대기 큐로 들 어감어감.

• 스케줄러는 입출력 대기 큐에 있는 프로세스를 먼저 스케줄 링 함!

(12)

Shortest Process Next(SPN)

• FCFS의 긴 프로세스 우대 편향성 완화 방법 2:

가장 짧은 프로 세스를 먼저 실행시키는 정책

( )

세스를 먼저 실행시키는 정책

– 종료 시까지 남아 있는 실행시간이 가장 짧은 프로세스를 다음 번 프 로세스로 선택세 택

•

비중단(Nonpreemptive) 모드로 동작

•

실행 시간이 짧은 프로세스가 실행 시간이 짧은 프로세스가

(비록 늦게 도착했더라도)(비록 늦게 도착했더라도) 긴 프로

긴 프로 세스들보다 먼저 스케줄링될 수 있음!

•

단점

: 짧은 프로세스들이 지속적으로 시스템에 진입한다면 이

들보다 상대적으로 긴 프로세스가 기아 상태 에 빠질 수 있다 들보다 상대적으로 긴 프로세스가 기아 상태 에 빠질 수 있다

Shortest Process Next(SPN) ( 계속 )

• SPN 구현 상의 문제점

( ) ( )

– 각프로세스가 요구하는 총 실행 시간을 미리 알아야 한다는 점 – 미리 알기 어렵기 때문에 시스템은 이를 유추할 수 있어야 함

• 프로세스의 예상 실행 시간을 유추하는 방법

– 단순 평균 : Î^Sⁿ⁺¹⁼ _n¹

∑

ⁿ ^Tⁱ ^Sⁿ⁺¹⁼_n¹^Tⁿ⁺ⁿ_n⁻¹^Sⁿ

– 지수적 평균(exponential averaging)

∑

i=

n 1 n n

) 1

( S

T S

과거에 측정된 실행 시간일수록 다음 실 )

1 ( ...

) 1 ( ...

) 1 (

1 1 1

1

− + +

− +

=

− +

=

− − +

+

i n i n n n

n

n n n

S T

T T

S

S T

S

α α

α

α 시간일수록 다음 실

행 시간 예측에 미치 는 영향이 작아짐

• α: 가중치 요소(weighting factor)

...

0064 . 0 032

. 0 16 . 0 8 . 0 8 . 0

2 3

1= + 1+ + +

=

− −

+ n n− n n

n T T T T

S

가정해보면 경우를

α 일

α : 가중치 요소(weighting factor)

(13)

Shortest-Process-Next(SPN) ( 계속 )

•

특정

α 값이 주어졌을 때T_n-i

앞에 붙는 계수 값들의 변화

( ) ( )

– 단점: 최근에 갑자기 비정상적으로 처리기를 많이 사용한 경우 향후 에도 그럴 것으로 예측해버리므로 잠시 후 정상 구간으로 진입했을 때 잘못된 예측을 할 가능성이 있다

때 잘못된 예측을 할 가능성이 있다.

Shortest-Process-Next(SPN) ( 계속 )

• 지수적 평균 기법과 단순 평균 기법의 예상 실행 시간 값 비교

( ) ( )

비교

• 지수적 평균 기법이 좀 더 현실과 부합하는 예상을 하고 있음

(14)

SRT (Shortest Remaining Time)

• SPN 의 중단 (preemptive) 모드 버전에 해당

( g )

• 예상되는 남아있는 실행 시간이 가장 짧은 프로세스가 다 음 번 프로세스로 선택됨

if (“새로 도착한 프로세스의 예상되는 남아있는 실행 시간” “현

– if (“새로 도착한 프로세스의 예상되는 남아있는 실행 시간”< “현 재 실행 중인 프로세스의 예상 실행 시간”) Î 늦게 도착했더라도 현재 실행 중인 프로세스를 중단하고 곧장 선택됨.

• 단점 단점

– 매 스케줄링 때마다 프로세스들의 남아있는 실행 시간을 평가해 야 하는 부담

– 긴 프로세스가 기아 상태에 빠질 가능성

Highest Response Ratio Next (HRRN)

• 준비 큐에 있는 프로세스 중 R 값 ( 응답 비율 ) 이 가장 큰 프 로세스를 다음 번 프로세스로 선택

g p ( )

로세스를 다음 번 프로세스로 선택

– 프로세스가 시스템 내에 머문 시간(즉, 프로세스의 나이)을 고려 – 서비스 시간이 짧은 프로세스의 R값이 상대적으로 크기 때문에

짧은 프로세스를 우대하는 면도 있고,

대기 시간 때문에 시스템에 오래 머문 긴 프로세스도 오래 머물면 – 대기 시간 때문에 시스템에 오래 머문 긴 프로세스도 오래 머물면

머물수록R 값이 커지기 때문에 홀대 받지는 않는다.

• 응답 비율의 정의 ^{응답 비율의 정의} w + s

– R= 응답 비율

– w= 처리기를 기다리며 대기한 시간

s s R = w +

w 처리기를 기다리며 대기한 시간

– s = 예상되는 서비스 시간

(15)

피드백 (Feedback) 스케줄링

다양한 스케줄링 정책들 9.2 스케줄링 알고리즘

• 프로세스들의 예상되는 서 비스 시간을 미리 알아낼

( )

비스 시간을 미리 알아낼 필요가 없다

• 중단점을 만날 때마다 프 중단점을 만날 때마다 로세스는 한 단계 낮은 우 선순위의 준비 큐로 강등 되어 진입

되어 진입

• 새로 도착한 프로세스일수 록 그리고 짧은 프로세스 록 , 그리고 짧은 프로세스 일수록 오래된 프로세스나 긴 프로세스보다 우대 받

는 정책

^{• 큐} ^RQ⁰^{~ RQ}^n-1 ^{: FCFS 방식}

는 정책

• Multilevel Feedback Queue 의 구조를 갖게 됨

큐 Q₀ Q_n₁ 방식

• 큐 RQ_n : 라운드-로빈 방식

Queue 의 구조를 갖게 됨

피드백 (Feedback) 스케줄링 ( 계속 )

다양한 스케줄링 정책들 9.2 스케줄링 알고리즘

– 피드백의 변형1 : 모든 큐에서 고정된 시간 할당량이 있는 라운드 로빈 방식으로 스케줄링

( ) ( )

로빈 방식으로 스케줄링

• 짧은 프로세스가 계속 진입하는 경우 긴 프로세스가 불이익을 받음 – 피드백의 변형피드백의 변형2 :2 : 시간 할당량의 크기를 큐 별로 다르게 함시간 할당량의 크기를 큐 별로 다르게 함

(16)

스케줄링 정책들의 특징

스케줄링 정책들의 특징 ( 계속 )

( )

(17)

스케줄링 정책들의 비교분석 결과

스케줄링 정책들의 비교분석 결과 ( 계속 )

( )

(18)

스케줄링 정책들의 성능 비교

• 2 가지 비교 분석 방법을 사용

– 큐잉 분석(Queuing Analysis)

– 시뮬레이션 모델링(Simulation Modeling)

• 큐잉 분석

– 관찰에 의하면 프로세스의 서비스 시간에 관계없이 다음 프로세 스를 선택하는 스케줄러는 다음과 같은 관계를 따른다.

• Normalized Turnaround Time = = 1

1

r

T T

• T_r= 턴어라운드 시간 또는 시스템에 머문 시간; 시스템 내에 총 머문

시간(대기 시간+ 실행 시간)

ρ

− 1 Ts

( )

• T_s= 평균 서비스 시간; 실행 상태에 머물렀던 평균 시간

• ρ= 처리기 이용율

큐잉 분석 ( 계속 )

9.2 스케줄링 알고리즘 스케줄링 정책들의 성능 비교

(19)

큐잉 분석 ( 계속 )

• 전체적인 정규화된 턴어라운드 시간 비교

짧은 작업을 우대Î 처 리기 이용율이 높아짐에 따 리기 이용율이 높아짐에 따 라 평균 정규화된 턴어라운 드 시간 개선

preemptive 스케줄링

preemptive 스케줄링 기법을 사용한 경우에 평균 정규화된 턴어라운드 시간 이 최대로 개선됨을 확인

하지만 전체적으로 성능 향성의 정도가 그리 확연하 지는 않다는 것도 알 수 있 다

다.

큐잉 분석 ( 계속 )

스케줄링 정책들의 성능 비교

• 짧은 프로세스들이 모여 있는 높은 우선순위 등급에 대한 결과

결과

시스템이 비중단 모드의 우선순위 기반 스케줄링 기 우선순위 기반 케줄링 기 법을 사용했을 때 큰 성능 향 상을 보인다는 것을 알 수 있 다.

(20)

큐잉 분석 ( 계속 )

• 긴 프로세스들이 모여 있는 낮은 우선순위 등급에 대한 결 과

과

우선순위를 사용한 경 우 더 안 좋은 성능을 보 우 더 안 좋은 성능을 보 인다는 것을 알 수 있다.

시뮬레이션 모델링

• 가정

– 50,000개의 프로세스를 대상

– 각 프로세스의 도착률은 λ = 0.8, 평균 서비스 시간은 T_s = 1, 따라 서 처리기 이용율은 λT 0 8이라고 가정

서 처리기 이용율은 ρ= λT_s= 0.8이라고 가정

– 처리기 이용율은 변하지 않고 0.8로 고정되어 있는 어떤 한 시점 에 대한 실험이라고 봐도 무방함!

에 대한 실험이라고 봐도 무방함!

• 프로세스 분류

서비스 시간 백분율 별로 100개의 그룹으로 나누어짐 – 서비스 시간 백분율 별로 100개의 그룹으로 나누어짐

– 500개의 프로세스는 서비스 시간으로 1을 요구하는 그룹으로, 또

다른 500개의 프로세스는 서비스 시간으로 2를 요구하는 그룹으

로 나누어지는 식

– 마지막 500개의 프로세스는 가장 긴 서비스 시간인 100을 요구하

는 그룹으로 분류될 것임 는 그룹으로 분류될 것임

(21)

시뮬레이션 모델링 ( 계속 )

• 정규화된 턴어라운드 시간에 대한 시뮬레이션 결과

시뮬레이션 모델링 ( 계속 )

• 대기 시간에 대한 시뮬레이션 결과

(22)

Fair-Share 스케줄링

• Background

– 하나의 사용자 응용 프로그램이 여러 개의 프로세스(또는 스레드) 들로 구성된 경우도 많음

사용자의 관점에서는 개별 프로세스 보다는 자신의 프로세스 집 – 사용자의 관점에서는 개별 프로세스 보다는 자신의 프로세스 집

합(즉, 응용 전체)이 어떻게 동작하는지에 관심을 더 갖게 됨.

– 스케줄링의 단위를 개별 프로세스가 아닌 프로세스 집합 단위로스케줄링의 단위를 개별 프로세스가 아닌 프로세스 집합 단위로 하는 것이 더 공정하지 않을까?

• Fair-Share 스케줄링

– 프로세스 집합 단위의 스케줄링 방식

– “공정함을 나누어 갖는다”라는 “공정-공유”의 의미가 함축

Fair-Share 스케줄링 ( 계속 )

• Fair-Share 스케줄링의 동작 방식 개요

– 각 사용자에게는 일종의 가중치가 부여됨

• 가중치는 시스템 전체 자원 중에 이 사용자가 사용할 수 있는 지분을 의미

의미

– 사용자 A가 사용자 B에 비해2배 큰 가중치를 가지고 있다고 가정

• 목표목표: “: 한참 수행한 후에 평가해봤더니 사용자한참 수행한 후에 평가해봤더니 사용자AA가 사용자가 사용자BB에 비해에 비해 2배에 달하는 작업량을 소화해 냈더라.”라는 결론이 도출되도록 – 자원 사용율을 지분에 맞게 통제하는 것

• 복합 우선순위 활용을 통한 Fair-Share 통제 방법

– 복합 우선순위

• 순수한 의미의 프로세스 별 우선순위+

• 최근 처리기 사용 시간+

• 프로세스가 소속된 그룹이 최근 소비한 처리기 시간

(23)

Fair-Share 스케줄러의 동작 예

• 세 개의 프로세스가 두 개의 그룹을 구성

그룹을 구성

– 그룹 1: A, 그룹 2: B, C

• 각 그룹의 가중치는 0.5

• 스케줄링 순서

– A, B, A, C, A, B, …

– 그룹 별 가중치 0.5를 유지하 게 됨.

9.3 전통적인 유닉스 시스템에서의 스케줄링 통적 유닉 시 에서의 케 링

• 동작 방식

“다 레벨 피 백 ” 방식 – “다중-레벨 피드백 큐” 방식

• 우선순위 등급 별로 하나씩 큐가 존재

• 각 큐 내에서는 라운드 로빈 방식으로 스케줄링각 큐 내에서는 라운드 로빈 방식으로 스케줄링 – 스케줄링은1초마다 한번씩 실시

• 실행 중인 프로세스가1초 이내에 자발적으로CPU를 놓거나 종료되지 않으 면 스케줄러가 강제로CPU를 뺏어 다른 프로세스에게 할당

면 스케줄러가 강제로CPU를 뺏어 다른 프로세스에게 할당

– 각 프로세스의 우선순위는 기본적으로 1초마다 한 번씩 재계산 된다

• 기본 우선순위 큐의 순위(내림차순)기본 우선순위 큐의 순위(내림차순) – 스와퍼(swapper)

– 블록 입출력 장치 제어 – 파일 처리

– 문자 입출력 장치 제어 – 사용자 프로세스

(24)

9장 단일처리기 스케줄링