CH9-1 Uniprocessor Scheduling

9장에서는 시스템 안에 CPU가 하나인 시스템에서의 CPU 관리에 대한 내용을 다룬다.

 

Aim of Scheduling: 스케줄링의 목적

- Response time: 사용자가 시스템에 작업을 요청한 순간부터 응답을 받을 때까지 걸리는 시간

- Throughput: 단위 시간당 시스템이 완료하는 작업의 양

- Processor efficiency: 전체 시간 중 CPU가 실제로 작업을 처리하며 바쁘게 실행된 시간의 비율

- Fairness: 모든 프로세스가 CPU 자원을 공평하게 할당받도록 보장하는 것을 목표로 한다.

 

Types of Scheduling

1. Long-term Scheduling

- 새로운 프로세스가 생성될 때 어떤 프로세스를 레디 큐에 넣을지를 결정

- batch job을 위한 스케줄링이다.

2. Medium-term Scheduling

- swapping과 관련이 있다.

- 메모리에 있는 프로세스 중 일부를 하드 디스크로 내보나거나 하드 디스크에 있던 프로세스를 다시 메모리로 불러오는 역할을 한다.

 

3. Short-term Scheduling

- ready 큐에 있는 프로세스 중에서 어떤 프로세스를 다음 순서로 CPU에 할당하여 실행할지 결정

- 가장 빈번하게 발생한다.

 

 

Short-Term Scheduling Criteria

User-oriented(사용자 지향 기준)

- Response Time: 사용자가 요청을 보낸 시점부터 출력될 때까지 걸리는 시간

- Turnaround Time: 프로세스가 실행된 시점부터 모든 실행을 완료할 때까지 걸리는 시간

- 사용자 입장에서 둘 다 짧은 게 좋다.

 

System-oriented(시스템 지향 기준)

- 효율적인 CPU 활용(Processor efficiency) 

- CPU 효율성을 높이려면 스위칭을 하면 안 된다.

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

- Throughput이 높을수록 시스템이 일정 시간 동안 더 많은 작업을 처리했다는 뜻이다.

 

Predictablity(예측 가능성), Fairness(공정성)은 숫자로 표현하기 어려운 특성이다.

예측 가능성과 공정성이 낮으면 특정 프로세스가 계속해서 우선순위에 밀려 실행하지 못해서 starvation 발생 가능성이 있다.

 

Priorities

각 프로세스에 우선순위를 부여하고 이를 바탕으로 다음에 실행할 프로세스를 결정하는 방식

 

- 항상 레디 큐에 있는 프로세스 중 가장 높은 우선순위를 가진 프로세스를 먼저 선택해서 CPU에 할당한다.

- 레디 큐는 우선순위에 따라 여러 개가 있다. 우선순위가 높은 프로세스끼리 모아놓은 레디 큐, 우선순위가 낮은 프로세스끼리 모아놓은 레디 큐 이런 식이다.

- starvation 발생 가능성이 있어서 이를 해결하기 위한 방법 역시 고려해야 한다.(starvation이 발생해서는 안 된다.)

 

Scheduling Algorithms

 

스케줄링을 한다 = 프로세스를 실행시키는 순서를 다르게 한다

service time = burst time

response time = service time + waiting time

 

1. First-Come-First-Served(FCFS)

- 먼저 온 순서대로 처리

- 우선순위: 큐에 도착한 시간

- non-preemption: 일단 실행을 시작한 프로세스가 스스로 종료하거나 I/O 대기 상태에 들어갈 때까지 다른 프로세스가 끼어들 수 없는 방식

→ 타임 아웃을 사용해 강제로 실행을 멈추게 할 수 없다.

- 실행 시간이 매우 긴 프로세스가 먼저 CPU를 차지하면 실행 시간이 짧은 프로세스들이 하염없이 기다려야 하는 상황이 발생한다.

큐에 도착한 시간이 빠를수록 우선순위가 높다.

	waiting time	service time
A	0 (0시 도착)	3
B	1 (2시 도착: 3-2=1)	6
C	5 (4시 도착: 9-4=5)	4
D	7 (6시 도착: 13-6=7)	5
E	10 (8시 도착: 18-8=10)	2

 

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

 

2. Round-Robin(= Time Sharing = Time Slicing)

- preemption: clock을 이용해서 프로세스를 강제로 중단시키는 선점 방식을 사용

- quantum이라고 불리는 제한된 시간 동안만 CPU를 사용할 수 있다.

- 주기적으로 clock interrupt를 발생시킨다.

- 할당된 퀀텀을 모두 사용한 프로세스는 실행을 마치지 못했더라도 강제로 중단된다. 이후 이 프로세스는 레디 큐의 맨 뒤로 보내진다.

- 우선순위: 큐에 도착한 시간

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

이 예제에서는 FCFS보다 response time이 길다. 

하지만 타임 퀀텀을 어떻게 설정하느냐에 따라 response time이 달라진다. 

즉, RR이 무조건 FCFS보다 성능이 좋다 또는 좋지 않다라고 단정 지을 수 없다.

 

3. Shortest Process Next

- 우선순위: 프로세스의 실행 시간

- service time이 짧은 프로세스부터 먼저 실행시킨다.

- non-preemption

- 짧은 프로세스들이 계속해서 도착할 경우, 실행 시간이 긴 프로세스는 계속해서 실행이 밀리게 되어 언제 실행할 지 예측하기 어려워진다.

- SPN은 프로세스의 예상 실행 시간에 크게 의존한다. 

- 실행 시간이 긴 프로세스는 새로운 짧은 프로세스들이 계속해서 들어오면 순위가 계속 밀려 영원히 실행되지 못하는 starvation 가능성이 있다.

 

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

 

FCFS, RR - 예측 가능성이 높고 starvation 발생 가능성은 없다.

SPN - 예측 가능성이 낮고 최악의 경우에는 starvation이 발생할 수 있다.

 

CALCULATING PROGRAM 'BURST': 실행 시간을 예측하는 방법

(1) Simple Average(산술평균)

(2) Exponential Averaging

최신 데이터에 더 큰 가중치를 두고, 과거 데이터일수록 가중치를 기하급수적으로 줄여서 예측에 반영하는 방식이다.

'가장 최근이 일어난 일이 미래에 더 큰 영향을 미칠 것이다'라는 가정에 기빈한다.

 

Use of Exponential Averaging

증가하는 함수, 감소하는 함수 둘 다 Exponential Averaging을 사용해서 예측하면 어느 정도 실제 값과 일치하다는 것을 알 수 있다.

 

4. Shortest Remaining Time

-  SPN을 preemptive하게 적용시킨 방식

- Remaining Time(전체 실행 시간이 아니라 어떤 시점에 남아 있는 실행 시간)을 비교해서 우선순위를 정한다.

- SRT도 실행 시간이 긴 프로세스의 예측 가능성이 낮고 starvation 발생 가능성이 있다.

 

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

 

5. Highest Response Ratio Next(HRRN)

- non-preemption

ratio = (waiting time + service time) / service time = w/s + 1

ratio가 클수록 우선순위가 높다. (waiting time이 길수록, service time이 짧을수록 ratio가 커진다.)

- 실행시간이 짧은 프로세스를 먼저 실행하지만 대기 시간이 긴 프로세스에도 우선순위를 주기 때문에 starvation 발생 가능성이 사라지고 예측 가능성이 높아진다.

 

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

 

[5가지 스케줄링 방식 정리]

우선순위	큐 도착시간	실행시간	대기시간 + 실행시간
non-preemption	FCFS	SPN	HRRN
preemption	RR	SRT

 

FCFS, RR은 예측 가능성과 공정성을 중요시하는 방식이다.

SPN, SRT는 response time을 최소화하는 것을 중시하고 예측 가능성과 공정성을 고려하지 않은 방식이다.

HRRN은 앞선 두 그룹의 중간 정도의 성능과 공정성과 예측 가능성도 고려하고 있는 방식이다.