Scheduling Policy는 어떻게 짜야 할까요?

1. Concept
2. Practical Scheduling Policies

 

 

---

1. Concept

Workload Assumption
Scheduling Metrics
FIFO
SJF
STCF
New Scheduling Metrics
RR
Length of the Time Slicing
Incoporationg I/O

 

저번 시간에 한번 Scheduling Policies 에 대해 알아보았죠?

그럼 이제 Policy는 어떻게 구현해야 할지 이번 글에서 다뤄보도록 하겠습니다.

 

Workload Assumption

 

Workload란 무엇일까요?

쉽게 말하면 어떤 entity에서 주어진 시간 동안 실행되는 작업을 의미합니다.

우리는 CPU Scheduling을 편하게 평가하기 위해서 몇가지 가정을 해 줄 텐데요

 

1. 각 작업은 같은 실행동안 실행된다
2. 모든 작업은 동시에 들어온다
3. 모든 작업은 CPU만을 사용한다 ( I/O 사용 안함 )
4. 모든 작업의 길이는 전부 알 수 있습니다.

 

이건 굉장히 Unrealistic 하죠? 추후 진행하면서 점점 이 가정을 깨트리겠지만

지금은 굉장히 유용한 가정이므로 일단 넘어갈게요.

 

Scheduling Metrics

우리는 이제 스케쥴링 Metric 을 알아야 하는데요, 그 전에 Metric의 뜻을 한번 짚어 보자면

 

소프트웨어의 속성이나 규격을 측정할 수 있는 지표.
프로그램의 복잡성, 코드별 버그의 수, 수요자 요구 사항의 수 따위를 측정한다.

 

랍니다.

 

---

우리는 그럼 어떤 Metric을 쓰나요?

 

일단 여러 가지 종류의 Metric이 있을 수 있지만 제일 많이 쓰는 것 위주로 두 가지를 소개하겠습니다.

하나는 Performance Metric인 Turnaround Time, 둘째는 Fairness 입니다.

 

Turnaround Time
T(completion) -  T(arrive) 를 한 것입니다.

Fairness
Performance 와는 좀 상충되지만, 얼마나 공평하게 실행되느냐를 봅니다.

 

First In, First Out(FIFO)

 

아주 간단합니다, 맨처음에 온걸 먼저 실행하고 그 다음에 온걸 다음에 실행하는거죠

이럴 경우 각 10초가 걸릴 때, Average turnaround runtime은 어떻게 될까요?

가 되겠습니다.

 

---

FIFO의 문제점은 뭘까요?

 

workload assumption의 1 조건 (모든 작업이 같은 시간이 걸린다) 가 없다고 생각해봅시다.

A는 100초 B는 20초 C는 20초가 걸릴 경우, Average turnaround runtime은 어떻게 될까요?

 

 

 

가 됩니다. B,C는 빨리 끝낼수 있음에도 불구하고 5배가 넘는 대기시간에 걸려 평균 실행시간이 높아졌습니다.

이것을 바로 Convoy Effect 라고 한답니다.

 

Shortest Job First (SJF)

그렇다면 한번, 짧은 작업부터 해 볼까요? 아까와 같은 가정에서

가 된다면, Average turnaround time 는 확실히 많이 감소했죠?

 

 

---

SJF의 문제점은 뭘까요?

 

workload assumption의 2 조건 (모든 작업이 같은 시간에 출발한다) 가 없다고 생각해봅시다.

 

그리고 이런 경우를 한번 가정해 봅시다

그렇다면 Average turnaround time 은 다시 매우 증가할 것이고, Convoy Effect가 발생할 것입니다.

 

 

Shortest Time-to-Completion (STCF)

그럼 대체 어떻게 해야 할까요?

 

Scheduler 한테 남은 시간을 계산해서 보내달라고 해 봅시다.

들어올때 남은 시간이 짧은 순서대로 계산을 시키는 것이죠.

Average Turnaround time 도 SJF의 동시입력 조건만큼 짧아지게 된답니다.

---

STCF는 뭐가 문제일까요?

 

사실 기존의 Turnaround Time Metric 에선 전혀 문제가 없습니다. 다만, 새 Metric에서 문제가 있죠.

 

New Scheduling Metrics : Response Time

만약 저희가 작업을 돌려놓고 밥먹으러 다녀온다면 B작업이 A작업이 끝난 한참 뒤에 실행되어도 상관이 없겠죠.

그런데 실제로 저희 작업은 메신저 한번 켜고, 인터넷 쇼핑 한번 하고 그러는데 이를 위해선 즉각적인 반응이 필요합니다.

 

그래서 저희는 Response time이라는 것을 New Scheduling Metrics로 한번 삼아보도록 하겠습니다.

Response Time
T(firstrun) -  T(arrive)

이 Metric에 의하면 STCF에 A,B,C가 동시에 들어왔을때 A의 Response Time 이 매우 길어집니다.

 

Round Robin (RR)

RR은 Time Slicing Scheduling입니다. 그전에는 한 작업이 종료될즈음에 새 작업을 했었죠?

 

이 방식은 Time Slice 단위로 실행한 뒤, 대기열(Run Queue)에 남은 작업으로 Context Switch하여 또 Time Slice 단위로 실행해 줍니다. 이 Time Slice의 길이는 time - interrupt period의 배수여야 해요.

 

이걸로 ABC를 각각 3초씩 run 하게 된다면 어떨까요?

 

위의 Average Response Time은

지만, RR의 Average Response Time은

가 됩니다.

 

다만 Turnaround Time은 기대하기 어렵겠습니다.

---

 

그렇다면 이 Time Slice의 단위는 어떻게 정하는 게 좋을까요?

 

짧을 경우	길 경우
Response Time이 우수합니다 Context switching의 비용이 성능에서 차지하는 부분이 커집니다.	Response Time이 좋지 못합니다 다만, Context switching의 비용이 크다면 이를 좀 Armortize 할 수 있습니다.

이것을 둘이 trade - off 관계에 있다고 합니다.

이것을 종합적으로 잘 고려하여 프로그램을 짜는 것이 System designer의 역할입니다.

 

Incorporating I/O

이제 3번째 가정을 파괴하여 봅시다.

이럴 경우 프로세스가 I/O에서 input을 받는 동안에는 CPU에서 작업을 할 수 없습니다. (Blocked상태)

검은색 작업이 A 이고 노란색 작업이 B 일때 이러한 방식으로 쓰게 된다면 

CPU가 A가 돌아가는 동안 Resource효율이 매우 낮아집니다.

처럼 해야 CPU utilization이 maximized되겠죠.

이 컨셉트는 I/O 가 동작할때 Blocked된 Process를 OS가 그 Process를 ready(그 전 글의 Process State 참조해주세요) 상태로 돌려놓으면 해결이 됩니다.

 

우리는 추후 작업 A를 interactive job으로, B를 Batch job으로 표현합니다.

 

Summary

STCF	RR
response time ⬇ turnaround time ⬆ Need to know runtime (workload 가정 4) Good for Batch computing	response time ⬆ turnaround time ⬇

 

 

---

2. Practical Scheduling Policies

 

MLFQ
Lottery Scheduling
Stride Scheduling
Completely Fair Scheduler

 

Multi-Level Feedback Queue (MLFQ)

 

진짜 Operating System이 돌아가는 환경에서는, 위의 Workload 가정이 적용되지 않습니다.

그 어떠한 사전 지식도 없는 상태에서 돌아가게 되는거죠.

 

MLFQ의 두가지 목표는

1. Batch 작업의 Turnaround Time을 최적화하기
2. Interactive 작업의 Response Time을 최적화하기

입니다.

 

여기서의 두 가지 테크니컬한 과제는

1. Batch 작업과 Interactive 작업을 구분하는 방법
2. Run time을 어떻게 추적하는지 입니다.

 

MLFQ의 기본적인 규칙입니다.

 

서로 Priority level이 다른 Queue 여러개가 있습니다.

 

Rule 1 : Priority level이 다르면 higher Queue가 choose됩니다. (If Priority(A) > Priority(B), A runs (B doesn't))

Rule 2 : Priority level이 같으면 RR이 됩니다. (If Priority(A) = Priority(B), A & B run in RR)

 

Priority는 어떻게 정해질까요?

 

Rule 3 : 맨 처음에 job이 들어온다면, 제일 우선순위 높은 큐에 배정됩니다

Rule 4a : 들어온 job이 배정된 entire time slice를 사용한다면 우선순위를 내립니다. (Batch Job)

Rule 4b : 들어온 job이 배정된 entire time slice를 사용하다 give up을 한다면 우선순위를 유지합니다. (Interactive Job)

 

이 방법 하에서, MLFQ는 STCF와 동작이 비슷합니다.

---

MLFQ는 실제로 어떻게 동작할까요?

 

 

한번 어떻게 동작하는지 Queue를 3개 가지고, time slice = 10msec인 MLFQ를 기준으로 예시를 볼까요?

A라는 긴 작업이 돌아가는 와중에 B라는 짧은 작업이 들어오는 것이죠

 

동작이 STCF와 왜 비슷하게 동작하는지 알 수 있는 예시입니다.

Run Time을 알지 못해도, 짧은 작업이라면 높은 우선도에서 진행되어 끝날 것이고 긴 작업이라면 우선도가 낮아져 마지막에 실행될 테니까요.

 

 

만약 Interactive Job이 들어온다면 어떻게 될까요?

B가 Time Slice를 전부 사용하지 않으므로, B는 언제나 제일 높은 우선순위 Queue에 있게 됩니다.

 

---

MLFQ의 문제점은 뭘까요?

 

MLFQ에는 두가지 문제점이 있습니다.

 

P1 : Starvation

만약 너무 많은 수의 Interactive Job이 존재한다면 Long Running Batch Job은 절대로 실행될 수 없습니다.

 

P2 : Change Behavior

한번 낮은 Queue로 간 작업이 Interactive Job 혹은, 실행 시간이 얼마 남지 않더라도 다시 올라오지 않습니다.

 

---

 

해결법은 무엇일까요?

 

 

Rule을 하나 더 추가해볼까요?

Rule 5 : S 시간이 지나면, 모든 작업의 Priority를 Highest Queue로 초기화 시킵니다. ( The Priority Boost )

 

그렇다면, 저 위의 Problems 는 해결이 된답니다.

---

MLFQ에서 관리해주어야 하는 변수는 무엇일까요?

 

MLFQ에서 정해줘야 하는 변수는 매우 많습니다.

1. Queue의 개수
2. Slice per Queue
3. S의 기간
4. ...

여기에 정확한 정답이 없기 때문에, 여러가지를 고려해서 Parameter을 잘 조정해 주어야 합니다.

Time Slice
high-priority queues → short time slices
high-priority queue는 주로 Interactive Job으로 이루어져 있으므로, Response Time이 중요하니 Time slice를 줄여줘야 합니다.

The Low-priority queue → longer time slices
Long running Jobs가 많으므로, Turnaround Time 과 Context Switch 비용을 줄여주기 위해 Time Slice를 늘여줍니다.

 

 

 

Solaris 의 MLFQ 구현

Solaris는 1) 어떤 수준의 lifetime으로 process의 우선순위가 조정되는지, 2) Time Slice의 길이가 어느정도인지, and 3) S 가(boost time) 어느정도인지 에 대한 Set of table을 제공해 줍니다.

Rules of MLFQ (Review)

Rule 1 : Priority level이 다르면 higher Queue가 choose됩니다. (If Priority(A) > Priority(B), A runs (B doesn't))

Rule 2 : Priority level이 같으면 RR이 됩니다. (If Priority(A) = Priority(B), A & B run in RR)

Rule 3 : 맨 처음에 job이 들어온다면, 제일 우선순위 높은 큐에 배정됩니다

Rule 4a : 들어온 job이 배정된 entire time slice를 사용한다면 우선순위를 내립니다. (Batch Job)

Rule 4b : 들어온 job이 배정된 entire time slice를 사용하다 give up을 한다면 우선순위를 유지합니다. (Interactive Job)

Rule 5 : S 시간이 지나면, 모든 작업의 Priority를 Highest Queue로 초기화 시킵니다. ( The Priority Boost )

 

---

Lottery, Stride, Completely Fair Scheduling Policies는 Proportional Share Scheduler입니다.

각각의 작업에 일정 퍼센티지의 CPU Time을 제공하고, Turnaround나 Respone Time에 대해서는 생각하지 않습니다.

 

Lottery Scheduling

Ticket이라는 용어를 한번 정의하고 시작해볼까요?

Ticket은 process에게서 자원을 얼마나 공유받을 수 있는지를 나타냅니다. Percentage of Tickets이 중요하겠죠?

 

Lottery Scheduling에서는 이 Ticket을 Random하게 뽑습니다.

만약 Process A가 0~74 까지의 Ticket을 보유중이고 Process B가 75~99 까지의 Ticket을 보유중이라면 

각 실행 Time Slice마다 티켓을 뽑아서 그 작업을 실행합니다.

---

Lottery Scheduling 에서 제공하는 별도의 기능은 무엇일까요?

 

Curruency 는 유저들에게 유저 내의 ticket을 분배하도록 허가합니다.

System이 이를 추후 Global Currency로 바꾸게 해주니까요

 

또 일시적인 Ticket transfer 를 제공하여 priority를 임시조정 가능하게 해 주는 기능도 있답니다.

---

Lottery Scheduling 의 장점은 무엇일까요?

 

Lottery Scheduling의 장점은 이것의 엄청 간단한 implemetation에 있어요.

티켓을 뽑을 random number generator
프로세스를 추적할 data structure
티켓의 총 개수

만 결정하면 되니, 아주 쉽겠죠?

 

이를 한번 연결리스트로 구현해 봅시다.

// 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...

 

이럴 경우 어떻게 동작할까요?

 

---

Lottery Scheduling 의 문제점은 무엇일까요?

 

 

우린 이걸 Random에 의존하기 때문에 fariness가 잘 지켜지는지 확신할 수 없습니다.

이 fariness를 평가하기 위해서는 또 다른 Metric이 필요합니다.

 

 

를 한번 사용해 봅시다.

 

그렇다면 이 Policy의 U값은 어떻게 나올까요?

와 같이 나오게 된답니다. 티켓 수가 같을때 Job First 와 Job Second를 뽑을 확률은 각 1/2인데

시행 횟수가 매우 많게 되면, 거의 비슷한 시간에 끝나게 되기 때문이죠.

 

Lottery Scheduling은 Implementation이 좋지만 Random-based Scheduling의 한계로 Job Length가 낮으면 fairness가 잘 지켜지지 않습니다. 그렇기 때문에 Random 이 아닌 Scheduling을 찾아야 합니다.

 

Stride Scheduling

Stride Scheduling 은 deterministic fair-share scheduler 입니다.

 

각 프로세스는 Ticket대신 Stride를 가집니다

각 프로세스는 pass value를 가집니다. pass value는 프로세스가 실행될 때마다 stride만큼 증가합니다.

Scheduler은 제일 낮은 값의 pass value를 가진 것을 실행시킵니다.

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

 

여기서 Stride값은 어떻게 설정해 주어야 할까요?

와 같이 Ticket에 반비례하게 설정해 주어야 합니다.

 

---

Stride Scheduling과 Lottery Scheduling 중 무엇을 써야 할까요?

 

저 중간에 New Process가 삽입된다면 A, B, C는 Starve하게 되고 늘 새로 들어온 Process가 독점하게 됩니다.

그래서 적절한 Global State(Pass value)를 설정해 주어야 하는데, 이는 매우 어렵죠.

 

그래서 Lottery Scheduling이 Stride Scheduling보단 많이 쓰이는 방식이랍니다.

 

Completely Fair Scheduling

 

그렇다면 그냥 Lottery Scheduling을 쓰면 되는 걸까요? 아닙니다.

Scheduleing Overhead 때문에 Lottery Scheduling은 사용할 수 없는 방식입니다.

while (current) {
    counter = counter + current->tickets;
    if (counter > winner)
        break; // found the winner
    current = current->next;
}

최적화 후에도 전체 CPU Resource의 5%정도를 Operating System의 Scheduler가 사용하는데, 저 위의 코드블럭의 실행당 거의 O(n) time이 걸리는 Lottery Scheduling은 적절하지 않습니다.

---

어떤 방식을 사용하여야 할까요?

 

Linux에서는 Completely Fair Scheduler를 사용합니다.

Linux의 CFS는 매우 효율적이고(highly efficient) 그리고 확장 가능한(scalable) 방법으로 구현되어 있습니다.
CFS는 counting-based technique를 사용합니다. ( Vruntime )
---------------------------------------------------------------------------------------------------------------------

Linux는 fixed 된 Time slice의 개념을 사용하지 않습니다.
각 process가 실행 될 때마다, vruntime이 축적됩니다.
CFS scheduler는 vruntime이 제일 작은 값을 실행시킵니다.

---

이 Scheduler의 중요 Trade-Off는 뭘까요?

 

이 Scheduler의 Trade-Off는 Switch Frequency입니다.

---

CFS는 고정된 Time Slice를 사용하지 않는다고 했는데 Switch Frequency를 어떻게 조절할 수 있을까요?

 

이는 sched_latency, min_granularity 라는 변수를 통해 조절됩니다.

sched_latency 란 뭘까요?

sched_latency 는 time slice를 유동적으로 결정하는 변수입니다.

sched_latency = 48ms
n = 4 ( with same priority )
→ A time slice is 12ms

min_granularity 란 뭘까요?

min_granularity는 한 process당 최소 보장되는 time slice를 결정하는 변수입니다.

sched_latency = 48ms
n = 10 ( with same priority )
→ A time slice is 4.8 ms

But, if min_regularity is 6ms then
→ A time slice is 6 ms

min_granularity를 사용하는 이유는 CPU efficiency를 지켜주기 위해서입니다.

---

CFS에서 우선순위를 정하는 방법은 뭘까요?

 

CFS에서 우선도 높은 프로그램은 nice value라는 것이 있습니다.

CFS는 이 nice value를 weight 로 mapping 합니다.

이 weight은 어떻게 반영될까요?

vruntime이 증가할때 반영이 됩니다.

예를 들어 process가 -5 nice 값을 갖고 있고, weight 가 3121라고 합시다.

runtime이 10 sec 이면, vruntime 은 10 sec중 3.2 sec (0.328 ∙ 10 sec) 만큼만 반영됩니다.

 

nice가 0일 경우보다 더 많이 chosen 되겠죠?

---

그렇다면 이제 이 Vruntime이 작은 Process는 어떻게 찾을까요?

 

Red-Black Tree를 활용합니다. ( key로 vruntime을 사용 )

 

그렇다면 찾는 실행은 O(l) 밖에 걸리지 않고, Placing job은 O(log n) 밖에 걸리지 않으므로 결과적으로 O(log n) 이 걸린다는 뜻입니다. 앞서 언급한 Lottery Scheduling Policy에 비해 효율적입니다.

---

I/O와 Sleeping Process는 어떻게 다룰까요?

 

CFS에서는 IO job에게 뭔가 특별한 것을 부여하지는 않습니다.

다만 I/O 를 기다리거나 Sleep 을 하느라 돌아가지 않고 있다가 돌아갈 상황에 vruntime을 확인하면 전체적으로 다른 process의 vruntime은 상승했을것이므로 그 다음 작업으로는 I/O를 받은 job이 돌아가도록 하겠죠.

 

---

문제점은 없을까요?

 

가장 낮은 vruntime을 잡을 경우 Starvation이 발생합니다.

예를들어 process A가 계속 동작하다, process B가 들어올 경우 B만 엄청나게 동작하게 되겠죠?

 

해결법은, CFS가 vruntime을 update할 때 그 다음으로 찾을 수 있는 제일 작은 값으로 mapping하는 것입니다.

 

To read more

single.dvi (wisc.edu)