Introduction
다음 가정들을 하나씩 지워가면서 반영할 것이다. 이때 시스템에서 실행 중인 것을 job이라고 하겠다.
- assumptions
1. Each job runs for the same amount of time.
2. All jobs arrive at the same time.
3. Once started, each job runs to completion.
4. All jobs only use the CPU (i.e., they perform no I/O)
5. The run-time of each job is known.
이 가정들을 하나씩 지워가면서 반영할 것이다.
Scheduling Metrics
스케줄을 평가(측정) 하기 위한 scheduling metric을 정의해보자.
- Turnaround time (performance metric)
Turnaround time은 job이 도착했을 때부터 job이 끝날 때까지의 시간이다.
이는 성능(performance)에 관한 지표다.
- Response time
Response time은 job이 도착했을 때부터 그 job이 처음으로 시작될 때까지의 시간이다.
이는 공정성(fairness)에 관한 지표다.
앞서 모든 job이 동시에 도착한다고 가정했으므로 여기서는 이고 이다.
Scheduling methods
(A) FIFO(First In, First Out)
가장 일반적인 알고리즘은 FIFO(First In, First Out)다.
FCFS(First Come, First Served)라고도 불린다
10 동안 실행되는 A, B, C 세 job이 동시에 도착했다고 가정하자. ()
그러면 평균 turnaround time은 이다.
이처럼 FIFO는 구현이 간단하지만 단점도 존재한다. 먼저 스케줄 된 job A가 100 동안 실행된다고 가정해보자.
그러면 평균 turnaround time은 으로 아주 커지게 된다. 이렇게 앞의 job 때문에 뒤의 job들이 밀리는 것을 convoy effect라고 한다.
(B) SJF(Shortest Job First)
이런 convoy effect의 문제를 해결하려고 시도한 방법이 SJF(Shortest Job First)다.
위 상황에서 시간이 오래 걸리는 A 대신 B와 C를 먼저 스케줄 한다고 가정하자.
그러면 평균 turnaround time은 으로 줄어든다.
SJF는 job들이 동시에 도착한다면 최적의 알고리즘이다. 하지만 다음과 같은 상황을 고려해보자.
만약 긴 job인 A가 스케줄 되었을 때, 더 짧은 job들이 도착해도 A가 계속 실행된다. 즉 convoy problem이 다시 발생하게 되고 평균 turnaround time은 다시 증가한다.
(C) STCF(Shortest Time-to-Completion First)
어떤 job이 실행 중일 때, 이를 중지하고 다른 job을 실행하는 것을 선점(preemption)이라고 하자.
SFJ에 preemption을 더한 알고리즘이 STCF(Shortest Time-to-Completion First)이다. PSJF(Preemptive SJF)라고도 부른다.
위 그림과 같이 SFJ와 달리 A가 실행 중임에도 더 짧은 job인 B, C가 도착한다면 B와 C를 먼저 스케줄 한다.
이는 FIFO와 SJF보다 turnaround time 관점에서 이득이 있다. 그러나 response time이 좋지 않다.
(D) RR(Round Robin)
이러한 문제를 해결하기 위해 RR(Round-Robin) 알고리즘이 등장했다.
RR은 job이 끝날 때까지 실행하는 것이 아니라 time slice(= scheduling quantum)라는 단위만큼만 실행한 뒤 run queue의 다른 job을 실행한다. 이런 특징 때문에 time-slicing이라고도 불린다.
response time은 (SJF나 STCF에 비해) 최적화되어있다.
RR은 timer interrupt가 전제되어야 되며, 이때 time slice는 timer-interrupt 주기의 배수여야 한다. 특히 time slice의 길이가 중요한데, time slice가 짧으면 성능이 좋아지지만 context switch의 비용이 증가한다.
RR은 response time이 짧은 fair한 알고리즘이지만, turnaround time은 최악이다.
I/O Overlap
여기까지 살펴보았을 때, turnaround time(performance)과 response time(fairness)의 상충관계가 있음을 알 수 있다.
하지만 모든 job이 I/O가 없고 각 job들의 run time을 알고 있다는 가정이 남아있다. 이들을 해결해보자.
다음 그림은 job A에 의해 CPU가 I/O 처리를 기다릴 때를 가정한 그림이다. (이하 STCF라고 가정)
job A가 Disk와 I/O 처리를 할 때 Block과 Running 상태가 반복되는데, 이때 CPU를 사용하지 않는 것은 비효율적이다.
따라서 다음과 같이 처리할 수 있다.
이렇게 I/O를 처리하면서 기다리는 동안 다른 job B를 overlap하는 것이 더 효율적이다.
(E) MLFQ(Multi-Level Feedback Queue)
이제 job들의 run time을 알고 있다는 가정 하나만이 남아있다.
현실에서는 어떤 job이 언제 끝날지 알 수 있는 방법이 없다. 이런 문제를 해결하면서 turnaround time과 response time을 최적화하려고 한다.
MLFQ (v.1 How To Change Priority)
여러 queue를 이용하며, 큐가 높으면 우선순위가 높다.
job은 우선 short job이라고 가정하고 높은 우선순위를 준다.
만약 long job이면 알아서 낮은 큐로 이동한다. (→ 이것으로 예측을 대신한다.)
규칙은 다음과 같다.
1. 우선순위가 높은 job부터 실행
2. 우선순위가 같으면 RR 실행
3. new job은 최고 우선순위
4. time slice를 다 쓰면 강등. 그전에 양보하면 유지
하지만 이런 규칙의 MLFQ에는 크게 두 가지 문제가 존재한다.
MLFQ Problem
1. Starvation: 위에서 interactive jobs를 계속하면(또는 job이 들어오면), 낮은 큐는 한 번도 실행 못한다(starved).
2. Gaming scheduler: time slice가 끝나기 직전에 I/O를 반복하는 방식을 사용할 수도 있다.
3. CPU-bound job이 interactive가 많은 job으로 갑자기 변하면 문제가 된다.
그래서 규칙을 일부 수정했다.
MLFQ (v.2 The Priority Boost)
모든 job들에게 boost를 주는 새로운 규칙을 추가하다는 것이다.
Rule 5: After some time period S, move all the jobs in the system to the topmost queue.
즉 일정 시간 S가 지나면, 모든 job을 최고 큐로 올리는 것이다. 모두 위로 올라가 RR을 적용하면 starve가 해결된다.
대신 시간 S가 너무 크면 long job이 굶고, 너무 짧으면 interactive가 많은 job들이 잘 안 끝나게 되므로, 적절한 S를 정하는 것이 중요하다.
이제 1번 문제(starving)와 3번 문제를 해결했다. 이번에는 2번 문제(gaming scheduler)를 해결해보자.
MLFQ (v.3 Better Accounting: allotment)
이를 위해 Rule 4를 수정해야 한다.
Rule 4: jobs이 다시 반환을 하든 말든 allotment를 다 쓰면 강등시키기.
그러면 오른쪽 그림처럼 gaming 하더라도 강등시킨다.
Tuning MLFQ And Other Issues
이제 MLFQ의 여러 변수들을 매개변수화(parameterize)해야 하는 문제가 생긴다.
예를 들어 얼마나 많은 queue가 있어야 하는지, time slice가 각 queue마다 얼마나 큰지, starving을 피하기 위해 얼마나 자주 boost 해야 할지 등등의 문제 말이다.
하지만 이는 정책마다 다르고 정해진 답은 없다. 다음은 여러 정책들 중 하나의 예시다.
- Lower Priority, Longer Quanta
아래 그림처럼 낮은 우선순위 큐에 조금 더 많은 시간(time slice)을 주기도 한다.
MLFQ Summary
- LMFQ Rule
1. 우선순위가 높은 job부터 실행
2. 우선순위가 같으면 RR 실행
3. new job은 최고 우선순위
4. time slice를 다 쓰면 강등. 그전에 양보하면 고정
4. jobs이 다시 반환을 하든 말든 allotment를 다 쓰면 강등
5. 시간 S가 지나면 모든 job을 top queue로 올림
Proportional Share
이번에는 fair-share라고도 불리는 proportional-share scheduler를 살펴보자. 이 방식은 turnaround time이나 response time을 최적화하는 대신, 일정 비율의 CPU time을 보장하는 것이 목적이다. 이는 lottery scheduling이라고도 불린다.
(F) Lottery scheduling
프로세스에게 ticket을 나눠주고, 스케줄러는 0과 total ticket 사이의 난수를 생성한다. 이후 해당 난수의 ticket을 가지고 있는 job을 스케줄 하기 때문에 ticket을 많이 가지고 있을수록 스케줄 될 확률이 높아진다.
예)
A가 0~10 사이 짝수, B가 0~10사이 홀수 티켓일 때,
난수가 [0 1 2 3 4]이면 [A B A B A] 순서로 스케줄함- Unfairness metric U
불공정성을 나타내는 지표 U를 정의하자.
U = 1인 경우, 즉 perfectly fair로 만드는 것이 목표다. (job length가 길수록 fair 함)
Ticket Mechanisms
ticket currency
티켓 통화는 티켓을 화폐처럼 쓰는 성질을 의미한다.
A와 B에게 티켓을 100개씩 주었을 때, A가 내부에서 A1, A2에게 local 화폐를 잘 배분하면, 나중에 그것이 global currency로 치환된다.
ticket transfer
티켓을 양도한다는 성질이다.
특히 client/server 관계에서 유용하다. 클라이언트가 서버에게 요청하면서 티켓을 같이 전달하면 server가 빠르게 응답할 확률이 올라간다.
ticket inflation
프로세스들이 경쟁적으로 티켓을 생산하면 inflation 현상이 발생한다. 따라서 프로세스들이 서로 신뢰하는 환경이 필요하다.
Implementation
ticket을 이용한 스케줄링 구현을 살펴보자.
// counter: used to track if we've found the winner yet
int counter = 0;
// winner: use some call to a random number generator to
// get a value, between 0 and the total # of tickets
int winner = getrandom(0, totaltickets);
// current: use this to walk through the list of jobs
node_t *current = head;
// loop until the sum of ticket values is > the winner
while (current) {
counter = counter + current->tickets;
if (counter > winner)
break; // found the winner
current = current->next;
}
// ’current’ is the winner: schedule it...(G) Stride scheduling
random은 간단하지만 비결정론적(non-deterministic)이라는 단점이 있다.
- Stride Scheduling (a deterministic fair-share scheduler)
stride: 티켓 비율에 반비례
pass: stride 만큼 추가하는 count
예)
ticket: A(100), B(50), C(250)
stride: A(100), B(200), C(40)
ticket value를 10,000으로 나눠서 생각하면
각각 100걸음, 200걸음, 40걸음씩 걸어야 10,000을 채움pass가 가장 낮은 process부터 실행해 주면 deterministic 하다.
current = remove_min(queue); // pick client with minimum pass
schedule(current); // use resource for quantum
current->pass += current->stride; // compute next pass using stride
insert(queue, current); // put back into the queue하지만 새로운 job이 들어왔을 때 문제가 되기 때문에, stride schedule 대신 로또 방식을 사용한다. (로또는 global state가 total ticket 하나뿐이라 new job에 유연하게 대처 가능)
Summary
Proportional-share scheduling을 구현하는 두 가지 방법 Lottery Scheduling과 Stride Scheduling을 살펴보았다.
Lottery는 proportional share라는 목적을 달성하는 데 중점을 두었고, Stride는 deterministic 하다는 특징이 있다.
하지만 I/O overlap 문제와 티켓 할당 문제로 잘 쓰이지 않고, 앞서 다룬 MLFQ가 더 범용적으로 쓰인다.
Other methods
- CFS(Completly Fair Share)
https://opensource.com/article/19/2/fair-scheduling-linux
리눅스 커널에서 사용하는 스케줄 방식이다.
구간을 나누고 n 개 정하고 timer를 거는데, 사실 정확히 1/n은 아니고 차등을 준다.
schedule latency: 구간을 정하고 1/n로 나눠서 사용한다.
자신의 time slice = [자신의 우선순위 / 전체 우선순위] * latency
vruntime = pass.
자기 우선순위()가 높을수록 pass가 작아지고, 기회를 자주 얻을 수 있다.
- Red-Black tree: insert/delete를 O(n)이 아니라 O(log(N))에 끝낼 수 있다.
delete: job의 끝이나 I/O도 delete에 해당함.
new job은 tree에서 찾은 최솟값으로 맞춰줌
Uploaded by Notion2Tistory v1.1.0