💿

04 : CPU Scheduling

course

last review

2023/04/10

mastery

intermediate

progress

not started

date

2023/03/14

4 more properties

Previous chapter

03 : Limited Direct Execution

Main Question : How to develop Scheduling

Workload Assumptions

Scheduling Metrics

turnaround time : 반환시간

First In First Out(FIFO)

Examples

Shortest Job First(SFJ)

Preemptive : 선점

Shortest Time-to-Completion First(STCF)

New Evaluation Model : Response Time

Round-Robin(RR)

Response time VS Turnaround Time

Incorporating I/O

Main Question : How to develop Scheduling

스케줄링 정책을 생각하기 위한 기본적인 프레임워크를 어떻게 만들어야 하는가? 어떤 것들을 가정해야하는가? 어떤 기준으로 정책을 평가해야하는가? 초기에는 어떤 기법들이 사용되었는가?

Workload Assumptions

프로세스가 동작하는 일련의 행위를 워크로드(workload)라 한다.

•

적절한 워크로드의 선정은 스케줄링 정책 개발에 매우 중요한 부분이다.

우리는 시스템에서 실행중인 프로세스나 작업(job)에 대해 다음과 같은 가정을 한다.

모든 작업은 같은 시간 동안 실행된다.

모든 작업은 동시에 도착한다.

작업은 일단 시작하면 최종적으로 종료될 때까지 실행된다.’

모든 작업은 CPU만 사용한다.(즉, 입출력은 없다.)

각 작업의 실행 시간은 사전에 알려져 있다.

Scheduling Metrics

워크로드에 대한 가정 이외에 스케줄링 정책의 평가를 위해 스케줄링 평가 항목(scheduling metric)을 결정해야한다.

turnaround time : 반환시간

작업이 진행된 시간을 반환시간(turnaround time)이라 한다. 작업이 완료된 시각에서 작업이 도착한 시각을 뺀 시간이다.

T_\text{turnaround}=T_\text{completion}-T_\text{arrival}

모든 작업은 동시에 도착한다고 가정했으므로,

T_\text{arrival}=0

이라고 생각할 수 있을 것이다.

First In First Out(FIFO)

가장 기본적인 알고리즘이다. FIFO는 장점이 많다.

•

단순하다.

•

구현하기 쉽다.

•

우리의 가정 하에서는 매우 잘 동작한다.

Examples

노란색이 A, 파란색이 B, 초록색이 C 작업이다.

•

작업A,B,C가 동시에 도착했다.

◦

즉, 모든 작업의 TarrivalT_\text{arrival}Tarrival​가 0이다.

•

이때 간발의 차로 ascending하게 도착했다고 판정이 떴을 경우 위와 같이 스케쥴링 될 것이다.

이 때 평균 반환시간(Average Turnaround Time)는 다음과 같이 구할 수 있을 것이다.

T_\text{ATT} = \cfrac{\sum^n T_\text{completion} - T_\text{arrival}}{n}

즉, (10+20+30)/3 = 20이다.

굉장히 합리적인 정책같지만, 이제 5개의 가정 중 하나의 가정을 해금할 것이다.

이제부터 각 작업의 작업시간인 모두 같은 시간 동안 실행되지 않는다.

이때 다음과 같은 문제점이 발생할 것이다.

이제 A의 작업시간이 100초로 늘었다. 이 상태에서 평균 반환시간은 110초로 늘어나게 된다.

이 현상을 convey effect(호송 효과)라고 부른다.

편의점에서 음료수 하나를 사는데 앞사람이 카트에 가득 물건을 싣고 계산대를 독차지하는 것.

Shortest Job First(SFJ)

사실 1번 가정이 박살이 났더라도 생각보다 간단하게 ATT를 줄일 수 있는 방법이 있다.

작업시간이 작은 B와 C를 우선적으로 스케쥴러에 배치하는 것이다.

작업시간이 가장 적은 스케쥴부터 먼저 배치하는 것을 최단 작업 우선(Shortest Job First)이라고 한다.

이제 실행시간이 가장 긴 A가 계산대를 가장 나중에 차지하기 때문에 B와 C가 오랫동안 기다려야 하는 적폐상황이 오지 않는다! 만세!

이때의 평균 반환시간을 구하면 다음과 같다.

\cfrac{10+20+120}{3}=50

이제 문제가 없어보인다. 그럼 다음 가정을 해금하자.

이제 모든 작업은 동시에 도착하지 않으며 임의의 시간에 도착할 수 있다.

반대로 이야기한다면, SJF는 모든 작업이 동시에 도착할 때 최적의 알고리즘이 될 수 있다는 것이다.

T=0인 시점에서 A만 도착했다고 가정하자. A 이외에 다른 프로세스가 없기 때문에 A를 배정한다.

그러나 T=10인 시점에서 B와 C가 들어오게 된다면 A가 모두 끝날때까지 B와 C는 하염없이 기다리게 된다. 즉, ATT를 다시 구하면 다음과 같다.

\cfrac{100+(110-10)+(120-10)}{3}=103.33...

이 문제를 해결하기 위해서는 아이러니하게도 가정 3을 완화해야 한다.

Preemptive : 선점

•

선점 스케줄러 : 다른 프로세스를 실행시키기 위해 필요하다면 현재 프로세스의 실행을 중단한다.

•

비선점 스케줄러(ex : SJF) : 각 작업이 종료될 때까지 계속 실행된다.

Shortest Time-to-Completion First(STCF)

이제 각 작업은 작업을 실행하는 도중에 중지될 수 있다.

즉, B나 C가 도착했을 때 스케줄러는 하던일을 중지하고 다른 작업으로 스위치가 가능하다.

SJF는 비선점형 스케줄러이기 때문에 실행중인 작업을 중지하고 다른 작업을 실행하지 못한다.

현재 실행중인 작업과 새로운 작업의 잔여 실행시간을 비교해 잔여시간이 가장 작은 작업을 스케줄하는 방식을 최단 잔여시간 우선(Shortest Time-to-Completion First)라 한다.

이제 T=10인 시점에서 B와 C가 들어왔을 때 스케쥴러는 잔여시간이 작은 순서대로 재배치를 하게 된다. 이때의 ATT는 다음과 같다.

\cfrac{120+(20-10)+(30-10)}{3}=50

New Evaluation Model : Response Time

STCF는 다음과 같은 조건에서 매우 훌륭한 정책이다.

•

작업의 길이를 미리 알고 있다.

•

작업이 오직 CPU만 사용한다.

•

평가 기준이 반환시간이다.

그러나 시분할 컴퓨터가 등장하면서 사용자가 터미널에서 시스템에게 상호작용을 원활히 하기 위한 성능을 요구하게 되었다.

따라서 응답시간(response time)이라는 새로운 평가 기준이 태어나게 된다.

작업이 도착하는 시점부터 처음으로 스케줄 될 때까지의 시간을 기준으로 측정한다.

T_\text{response} = T_\text{firstrun}-T_\text{arrival}

A = 0, B = 0, C = 10이 될 것이다.

STCF는 이런 관점에서 응답시간이 짧다고 할 수 없다. 따라서 응답시간을 최소화하는 스케줄러를 만들어야 한다.

Round-Robin(RR)

일정 시간 실행한 후 실행 큐의 다음 작업으로 전환하는 방식을 라운드 로빈(RR)이라 한다.

이때 단위 시간을 타임 슬라이스(time slice) 또는 스케쥴링 퀀텀(scheduling quantum)이라 부른다.

•

타임슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다. 타이머가 n길이마다 인터럽트를 발생시킨다면 타임슬라이스의 길이는 kn이 되어야 한다.

타임슬라이스의 길이는 RR에게 매우 중요하다.

타임슬라이스가 짧을 수록, 응답시간의 기준으로는 RR의 성능이 좋아진다.

그러나 타임슬라이스가 너무 짧으면 Context Switching의 비용이 더 커지게 됨을 유의하라.

Response time VS Turnaround Time

RR와 같은 공정한 정책

모든 프로세스에게 CPU 분배하는 정책

은 반환시간과 같은 평가 기준에서는 성능이 나쁘다.

반대로 공정성이 더 중요하다면 응답시간은 줄어들지만 반환시간은 나빠진다.

Incorporating I/O

이제 가정4를 해금할 때가 왔다.

모든 프로그램은 입출력 작업을 수행한다.

현재 실행중인 프로세스가 입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행할지 결정해야한다.

현재 실행중인 작업은 입출력이 완료될 때까지 CPU를 사용하지 않기 때문이다.

Next chapter

05 : Multi-Level Feedback Queue