[운영체제] ep8) Uniprocessor Scheduling

ㅇCPU 스케줄링: Process에 CPU 시간을 할당하는 방법

스케줄링의 목적은 유저 입장과 시스템 입장으로 나눌 수 있다

<유저 입장>

response time(응답시간): 프로세스가 처음 도착한 후, 처음 CPU를 할당받아 실행되기까지 걸리는 시간

turnaround time(반환시간): 프로세스가 시스템에 도착한 후, 모든 작업을 마치고 종료될 때까지의 총 시간

<시스템 입장>

throughput(처리율/처리량): 단위시간당 Process를 종료시키는 수

processor efficiency(CPU 효율성): 얼마나 OS 개입이 적고, CPU를 이용하였는지

Fairness(공정성): 같은 기준을 갖은 Process들은 모두 공정하게 같은 기회를 가져야 한다

Predictability(예측 가능성): 언제쯤 끝날지에 대한 예측 가능성 

 

스케줄링의 타입은 3가지가 있다

1. Long-term Scheduling

[New -> Ready]

[New -> Ready / Suspend]

 

2. Medium-term Scheduling: 스와핑(swapping)

[Ready / Suspend -> Ready]

[Blocked / Suspend -> Blocked]

 

3. Short-term Scheduling: 레디-큐의 프로세스들을 실행시키는 순서의 방법

[Ready -> Running] (dispatcher 기능)

성능에 가장 중요한 타입이며, 우리는 9장에서 이걸 집중적으로 다룰 예정이다

 

Scheduling and Process State Transitions

 

Queuing Diagram for Scheduling

 

 

Short-term Scheduling을 설계할 때는 양적인 측면과 질적인 측면이 대립한다

만약에 양적인 측면을 취하게 된다면 생산성이 올라가고 양적으로 정확한 표현이 가능하겠지만 공정성과 예측가능성이 떨어진다

반대로 질적인 측면을 취하게 된다면 공정성과 예측가능성은 올라가겠지만 생산성이 떨어지고 양적으로 정확한 표현이 어려워진다

이 두 가지 측면을 잘 고려해서 설계하여야 하는데 보통 현대 시스템에서는 양적인 측면을 메인으로 취하고, 질적인 측면을 보조로 지키자는 추세이다

 

스케줄링 알고리즘에는 메인으로 5가지가 있고 추가로 2가지가 더 있다

알고리즘들을 알아보기 전에 선점형(Preemtive)과 비선점형(Non-preemptive)에 대해 공부하고 앞으로의 상황에 대해 가정해 보자

 

 

상황)

 

 

1. FCFS(First-Come-First-Served): 먼저 온 순서대로 처리

[비선점형]

 

각 기법의 response time을 구하는 방법은 [waiting time + service time = response time]의 평균을 구하면 된다

FCFS: ((0 + 3) + (1 + 6) + (5 + 4) + (7 + 5) + (10 + 2)) / 5 = 43 / 5

 

 

 

2. RR(Round-Robin): 각 프로세스에 일정한 시간(time quantum)을 할당

a.k.a. time slicing

[선점형]

 

 

여기서 time quantum값은 1이다

q = 1 (1 간격의 time-out)

time quantum값에 따라 waiting time이 길어지게 되므로 잘 설정해줘야 한다

 

 

참고 그림

 

 

FCFS: ((0 + 3) + (1 + 6) + (5 + 4) + (7 + 5) + (10 + 2)) / 5 = 43 / 5

RR: ((1 + 3) + (10 + 6) + (9 + 4) + (9 + 5) + (5 + 2)) / 5 = 54 / 5

 

 

 

3. SPN(Shortest Process Next) = SJF(Shortest Job First): 레디-큐에 있는 Process 중 실행시간이 가장 짧은 Process를 실행

[비선점형]

 

but 비선점형인데도 불구하고 있는 SPN의 문제점: predictability ↓, starvation ↑

 

FCFS: ((0 + 3) + (1 + 6) + (5 + 4) + (7 + 5) + (10 + 2)) / 5 = 43 / 5

RR: ((1 + 3) + (10 + 6) + (9 + 4) + (9 + 5) + (5 + 2)) / 5 = 54 / 5

SPN: ((0 + 3) + (1 + 6) + (7 + 4) + (9 + 5) + (1 + 2)) / 5 = 38 / 5

 

 

여기서 다음 프로세스를 결정하는데 Burst Time을 본다

ㅇBurst Time: Process가 CPU에서 실행되는 데 필요한 총시간

2가지 계산방법이 있다

1. 산술 평균을 이용한 실행시간 예측

Ti: CPU를 사용하는 시간, Si: i번째 예측값

 

2. 가중치 평균(Exponential Averaging)을 이용한 실행시간 예측

Tn: 실제 Burst Time (a값은 0~1 사이)

 

 

 

 

4. SRT(Shortest Remaining Time) = SRTF(SRT First): 현재 실행 중인 Process가 완료되기 전에 실행시간이 더 짧은 Process가 나타나면 선점

[선점형]

 

SPN의 선점형 버전이며 이름에서 알 수 있듯이 남은 시간을 비교한다

 

FCFS: ((0 + 3) + (1 + 6) + (5 + 4) + (7 + 5) + (10 + 2)) / 5 = 43 / 5

RR: ((1 + 3) + (10 + 6) + (9 + 4) + (9 + 5) + (5 + 2)) / 5 = 54 / 5

SPN: ((0 + 3) + (1 + 6) + (7 + 4) + (9 + 5) + (1 + 2)) / 5 = 38 / 5

SRT: ((0 + 3) + (7 + 6) + (0 + 4) + (9 + 5) + (0 + 2)) / 5 = 36 / 5

구현 가능한 것들 중 성능 best

 

 

 

5. HRRN(Highest Response Ratio Next): 대기시간과 실행시간의 Ratio를 계산해 우선순위가 높은 Process를 실행

[비선점형]

 

Ratio가 가장 큰 것부터 실행한다

Ratio 공식

 

FCFS: ((0 + 3) + (1 + 6) + (5 + 4) + (7 + 5) + (10 + 2)) / 5 = 43 / 5

RR: ((1 + 3) + (10 + 6) + (9 + 4) + (9 + 5) + (5 + 2)) / 5 = 54 / 5

SPN: ((0 + 3) + (1 + 6) + (7 + 4) + (9 + 5) + (1 + 2)) / 5 = 38 / 5

SRT: ((0 + 3) + (7 + 6) + (0 + 4) + (9 + 5) + (0 + 2)) / 5 = 36 / 5

SRT: ((0 + 3) + (1 + 6) + (5 + 4) + (9 + 5) + (5 + 2)) / 5 = 40 / 5

 

 

 

추가 1. Feedback 스케줄링: 실행시간이 긴 Process에게 우선순위 페널티를 준다

대부분의 시스템이 사용한다

[선점형]

 

주의) 이해를 위해 프로세서를 여러 개 그린 거고 실제로는 프로세서가 하나인 시스템이다

 

n번 큐의 Process가 스케줄 되려면 0 ~ n-1번 큐가 모두 비어야 한다

 

 

 

 

 

 

추가 2. Fair-Share 스케줄링: application 단위로 스케줄링을 한다 (같은 application 에서 나온 Process를 한 번에 처리)

RR의 그룹 Fair-Share 버전

Example of Fair Share Scheduler Three Processes, Two Groups

 

A-B-A-C

-A-B-A-C

-A-B-A-C

-...

 

 

 

 

 

추가) 전통적인 UNIX 스케줄링: 각각의 우선순위 큐를 가지는 Feedback 시스템

각각의 RR을 사용하는 우선순위 큐를 가지는 멀티레벨 피드백 시스템이다

우선순위는 프로세스 타입, 실행 히스토리에 근거해 부여되며, 1초마다 갱신(재계산)된다

각각의 우선순위 큐를 가지는 멀티레벨 Feedback 시스템 (RR을 사용)

 

양적인 측면보다는 질적인 측면에 초점을 두었다

공정성 good, starvation X / 성능 bad

 

<스케줄링 공식>

j: Process #

i: 몇 번째 갱신(재계산)인지 - 1초 간격

CPUj(i): CPU 이용률

Pj(i): Process j의 우선순위 (값이 작을수록 우선순위가 높다)

Basej: 기본 베이스 우선순위

nicej: 우선순위를 user가 조정

 

최근에 CPU를 많이 썼으면 그 Process의 우선순위를 낮춘다

반대로 CPU를 오래 못썼으면 그 Process의 우선순위를 높인다

 

 

 

 

 

 

 

 

 

 

 

참고 및 출처: Operating Systems: Internals and Design Principles(William Stalling), Operating System Concepts(Silberschatz, Abraham)