[OS] Scheduling: Introduction (Scheduling Policy들 정리)

Scheduling

운영체제 같은 시스템 소프트웨어는 mechanism과 policy라는 말을 사용합니다.

 

지금까지 Context Switching과 같은 mechanism, 즉 low-level의 기계에서 수행되는 방법에 대해 공부했는데, 어떤 근거, 판단 기준을 가지고 OS가 Context Switching을 하는지, 그 정책(policy)에 대한 것은 아직 다루지 않았습니다.

 

오늘 주제는 OS의 Scheduler가 수행하는 의사결정, 즉 알고리즘이라고 할 수 있는 정책에 대해서 알아봅시다 !

 

근데 여러분 그거 아셨나요 ?

 

사실 스케줄링이라고 하는 것은 컴퓨터에서 처음 나온 개념은 아닙니다. 컴퓨터가 나오기 훨씬 이전부터 운영 관리 분야에서부터 존재해왔던 개념입니다. 사실 이 모든것은 일을 더 효율적으로 하기 위한 것들이기 때문에 사람들이 일을 처리하는 순서에도 노하우와 정책들이 존재해왔고, 그 개념들이 컴퓨터에서 운영체제가 일을 더 효율적으로 하기 위한 정책으로 사용되어도 사실 전혀 놀랄게 없는 것이죠 !

 

그렇다면 질문과 함께 시작해봅시다.

 

 

스케줄링 정책을 어떻게 개발해야 하는가 ?
스케줄링 정책을 생각하는 기본적인 프레임워크는 어떻게 개발해야 할까?
주요 가정은 무엇인가?
어떤 메트릭이 중요한가?
초기 컴퓨터 시스템에서 사용된 기본적인 접근 방법은 무엇인가?

 

7.1 Workload Assumptions

가능한 정책 범위에 대해 들어가기 전에, 시스템에서 실행 중인 프로세스에 대해 몇 가지 단순화된 가정을 먼저 해 보겠습니다. 이러한 가정은 때로는 workload라고 불리며 시스템 정책을 구축하는 중요한 부분입니다. Workload에 대해 알고 있는 정보가 많을수록 정책을 미세 조정할 수 있습니다.

 

여기서 우리가 하는 워크로드 가정은 대부분 현실적이지 않지만, 지금은 괜찮습니다 !

이 가정들을 수정하면서 최종적으로 완전한 운영 스케줄링 체계로 발전시켜봅시다.

 

다음은 시스템에서 실행 중인 프로세스 또는 작업이라고 불리는 것들에 대한 가정입니다:

1. 각 작업은 동일한 시간 동안 실행됩니다.
2. 모든 작업이 동시에 도착합니다.
3. 시작하면 각 작업은 완료될 때까지 실행됩니다.
4. 모든 작업은 CPU만 사용하며 (즉, I/O를 수행하지 않습니다).
5. 각 작업의 실행 시간이 알려져 있습니다. 

 

이러한 가정 중 많은 것이 현실적이지 않다고 했지만, 특히 5번 가정이 다른 것보다 현실적이지 않다고 할 수 있습니다.

(실행시간 자체는 실행해보지 않으면 절대 알 수 없기 때문에, 실행시간이 알려져 있다는건 마치 미래에서 실행시간을 미리 알고 과거로 온 느낌..??)

 

7.2 Scheduling Metrics

앞으로 소개되는 많은 scheduling policies들 중에서 서로 비교하고 좋은 정책을 골라내기 위해서는 평가 지표가 필요합니다.

이 평가지표가 Scheduling Metrics입니다.

 

지금은 우선 한가지 지표로 시작해봅시다. Turnaround time입니다.

Turnaround time은 작업이 끝나는 시간에서 작업이 도착한 시간을 빼는 것으로 정의됩니다. (작업 도착 ~ 끝나는 시간)

 

Turnaround time

지금 당장은! 위의 가정중 2번 가정(모든 작업이 동시에 도착합니다.)때문에 turnaround time == completion time이라고 봐도 무방합니다.

 

Turnaround time이 초점으로 두고 있는 것은 바로 performance, 성능입니다!

이외에도 공정성을 평가하고자 하는 Fairness에 대한 지표 또한 존재합니다.

 

성능과 공평성은 서로 trade off관계에 있어서 성능을 최적화하고자 하면 공정성이 떨어지고, 공정성을 높이고자하면 성능이 안좋아지는 언제나 완벽한 것은 존재하지 않는 것 같습니다.

 

7.3 First In, First Out(FIFO) 선입선출

FIFO하면 Queue가 제일 먼저 떠오르는데, 그냥 말그대로 큐와 같이 스케줄링하는 것 입니다.

제일 쉽게 구현할 수 있는 스케줄링 정책으로 간단하고 구현하기 쉽다라는 것이 곧 최고의 장점입니다.

 

그리고 우리의 가정들 안에서 예시를 들어보면 생각보다 꽤 잘돌아가는 것을 알 수 있을 겁니다.

예시

실행시간이 모두 10초로 동일한 작업 A, B, C가 A -> B -> C 순서대로 0초즈음에 거의 엇비슷하게 도착했다고 봅시다.

 

FIFO방식에 의해서 그나마 제일 먼저온 A, 그 다음 B, 그 다음 C순으로 작업을 수행하고 있는 것을 볼 수 있습니다. 이 때 average turnaround time은 어떻게 될까요 ?

 

Turnaround time = completion time(작업이 끝난 시간) - arrive time(작업이 도착한 시간)

 

이 공식을 다시 리마인드하고 계산해보겠습니다.

A turnaround time = 10 - 0 = 10

B turnaround time = 20 - 0 = 20

C turnaround time = 30 - 0 = 30

 

avg turnaround time = (10 + 20 + 30) / 3 = 20

 

이렇게 됩니다.

 

그렇게 어렵지 않죠 ?

1. 각 작업은 동일한 시간 동안 실행됩니다.
2. 모든 작업이 동시에 도착합니다.
3. 시작하면 각 작업은 완료될 때까지 실행됩니다.
4. 모든 작업은 CPU만 사용하며 (즉, I/O를 수행하지 않습니다).
5. 각 작업의 실행 시간이 알려져 있습니다. 

 

이제 그러면 가정중에서 1번 가정(각 작업은 동일한 시간 동안 실행됩니다)와 2번 가정(모든 작업이 동시에 도착합니다)를 없애봅시다.

 

그러면 이제 FIFO 정책에서 어떤 최악의 경우가 발생할까요 ? 🤔

 

현금이 필요한 일이 있어 돈을 뽑으러 집근처에 있는 은행ATM기기가 있는 곳으로 갑니다. (이 때 은행ATM기기가 집 주변에 정말 딱! 한곳만 존재하고, 다른 곳은 가는데만 1시간 이상 걸려서 이곳밖에 없다고 칩시다)

 

은행ATM기기가 있는 곳으로 왔더니 앞에 어떤 한 분이 통장을 한 100개 정도 쌓아놓고 일을 처리하고 있습니다...그리고 그 분은 본인 일을 끝내기 전에는 뒤도 안돌아보고 본인 일만 신경쓰는 겁니다...

 

그럼 전 언제쯤 돈을 뽑을 수 있을까요?? 그 분이 100개의 통장에 대한 일을 모두 마친 후에나 할 수 있겠죠...

 

대충 느낌이 오시죠 ?

 

이제 한번 다시 위와 같이 그림으로 예시를 보겠습니다.

FIFO는 좋지 않아!

 

아까와 완전히 동일한 상황인데 이번에는 A의 작업시간이 100초, B, C는 동일하게 10초입니다.

 

이제 다시 average turnaround time을 구해봅시다.

A turnaround time = 100 - 0 = 100

B turnaround time = 110 - 0 = 110

C turnaround time = 120 - 0 = 120

 

avg turnaround time = (100 + 110 + 120) / 3 = 110

 

 

이 문제는 Convoy Effect로 언급되며, 리소스의 상대적으로 짧은 사용자들이 무거운 리소스 소비자 뒤에 대기열에 들어가는 상황을 나타냅니다.

 

Convey Effect, Convoy Effect

 

그러면 어떻게 해야 더 나은 알고리즘을 만들 수 있을까요 ? 🤔

 

7.4 Shortest Job First (SJF): 짧은 작업 먼저 처리하자

간단한 접근방법으로도 이 문제를 해결할 수 있습니다. 사실 제목이 모든 것을 설명하고 있습니다. 짧은 작업을 먼저 처리하는 것 입니다.

 

(FIFO방식의 또 다른 실생활 예시 중에서 슈퍼마켓에서 물건을 잔뜩 담은 사람이 앞에 있으면 오래 기다린 후에나 결제를 할 수 있잖아요 ?

SJF은 슈퍼마켓 결제하는 곳에서 보면 10개 미만, 적은 양의 물건들을 사는 사람들을 위한 결제하는 곳이 따로 있는 곳에 해당된다고 보시면 됩니다 !)

 

바로 FIFO 정책 예제를 그대로 가져와볼게요. 

Shortest Job First (SJF)

A의 작업시간: 100초, B,C의 작업시간: 10초

B turnaround time = 10 - 0 = 10

C turnaround time = 20 - 0 = 20

A turnaround time = 120 - 0 = 120

 

avg turnaround time = (10 + 20 + 120) / 3 = 50

 

훨씬 나은 성능을 보이는 것을 알 수 있겠네요.

 

1. 각 작업은 동일한 시간 동안 실행됩니다.
2. 모든 작업이 동시에 도착합니다.
3. 시작하면 각 작업은 완료될 때까지 실행됩니다.
4. 모든 작업은 CPU만 사용하며 (즉, I/O를 수행하지 않습니다).
5. 각 작업의 실행 시간이 알려져 있습니다. 

 

사실 모든 작업이 동시에 도착한다라는 2번 가정의 전제하에는 SJF가 최적의 스케줄링 알고리즘임을 증명할 수 있다고 합니다.

하지만 현실세계에서 모든 작업이 동시에 도착할 일은 거의 없겠죠..? 따라서 이번에는 최악의 상황을 생각하기 위해 2번 가정, 모든 작업이 동시에 도착한다라는 가정을 지워보겠습니다.

 

바로 예시를 한번 보겠습니다.

 

이번에는 A가 t = 0에 도착하여 100초 동안 실행되어야 하며, B와 C는 t = 10에 도착하여 각각 10초 동안 실행되어야 한다고 가정해 봅시다. 

 

A turnaround time = 100 - 0 = 100

B turnaround time = 110 - 10(10초에 도착) = 100

C turnaround time = 120 - 10(10초에 도착) = 110

 

avg turnaround time = (100 + 100 + 110) / 3 = 103.333초

(도착 시간이 이번에는 0이 아님을 유의. T turnaround 공식 다시 보고 와도 좋음)

 

이렇게 되면 처음 FIFO의 상황과 별로 나아진게 없어보입니다....

 

살짝 맥락과는 별개로, 이런 문제가 발생하게 되는 이유로는 3번 가정(시작하면 각 작업은 완료될 때까지 실행됩니다) 때문입니다.
이렇게 한번 실행하면 작업이 완료 될 때까지 멈추지 않는 것을 non-preemptive(비선점적) 스케줄러 방식입니다. 과거에는 이 방식으로 스케줄러가 구현이 되었지만 사실 현대에 있는 모든 스케줄러는 preemptive(선점적) 스케줄러 방식으로 되어있습니다.
그 말은 즉, 언제든지 다른 프로세스를 일시 중지시키고 다른 프로세스를 시작(선점)하게끔 할 수 있다는 뜻이고 이것이 곧 지금까지 우리가 살펴본 Context Switching입니다.

 

어쨋건 더 나은 방법은 없을까요 ?? 🤔

 

7.5 Shortest Time-to-Completion First (STCF): 완료까지 남은 시간이 가장 짧은 것을 먼저하자

STCF는 Preemtive Shorted Job First, PSJF라 불리우기도 합니다.

1. 각 작업은 동일한 시간 동안 실행됩니다.
2. 모든 작업이 동시에 도착합니다.
3. 시작하면 각 작업은 완료될 때까지 실행됩니다.
4. 모든 작업은 CPU만 사용하며 (즉, I/O를 수행하지 않습니다).
5. 각 작업의 실행 시간이 알려져 있습니다. 

 

위 문제를 해결하기 위해 우리는 3번 가정(작업이 반드시 완료되어야 한다는 가정)을 지워야합니다.

이 가정을 지운다는 뜻은 non-preemptive(비선점) 스케줄러를 preemptive(선점) 스케줄러로 바꾸는 것과 같은 의미를 가집니다.

 

그럼 이제 새로운 작업이 시스템에 들어올 때마다 STCF 스케줄러는 남은 작업 중 (새로운 작업 포함) 어떤 작업이 가장 적은 남은 시간을 가지고 있는지 결정하고 그 작업을 스케줄링(Context Switching 발생)합니다

 

예제와 한번 봅시다.

따라서 예시를 보면 B가 온 순간에 A가 쓰고 있던 CPU를 선점하고 B와 C를 모두 완료한 후에 A의 남은 작업이 스케줄링됩니다.

 

A turnaround time = 120 - 0 = 120

B turnaround time = 20 - 10(10초에 도착) = 10

C turnaround time = 30 - 10(10초에 도착) = 20

 

avg turnaround time = (120 + 10 + 20) / 3 = 50초

 

모든 작업이 동시에 도착할 때 SJF가 최적이라면,

모든 작업이 동시에 도착하지 않는 상황이라면 STCF가 가장 최적입니다.

7.6 A New Metric: Response Time (반응 시간)

1. 각 작업은 동일한 시간 동안 실행됩니다.
2. 모든 작업이 동시에 도착합니다.
3. 시작하면 각 작업은 완료될 때까지 실행됩니다.
4. 모든 작업은 CPU만 사용하며 (즉, I/O를 수행하지 않습니다).
5. 각 작업의 실행 시간이 알려져 있습니다. 

 

우리는 방금 작업들의 도착 시간이 동일하지 않아도, 수행 시간이 동일하지 않아도 최적의 결과를 낼 수 있는 STCF 정책을 살펴봤습니다. 

 

그리고 그 결과는 Performance에 초점을 둔 평가 지표인, Turnaround time을 기준으로 나온 결과입니다.

 

Performance와 또 하나 지표로 언급되었던 것이 바로 공정성(Fairness)을 위한 지표, Response time(응답 시간) 입니다.

Response time

 

Response time은 작업이 도착 후 처음으로 스케줄 되기까지의 시간을 말합니다.

위의 예시를 다시 가져와서 평균 응답시간을 구해보면

A Response time = 0

B Response time = 0

C Response time = 20 - 10 = 10

 

avg response time = 10 / 3 = 3.33초 (길다)

 

 

사실 STCF와 관련된 방법론은 응답 시간에는 특히 좋지 않습니다. 예를 들어, 세 개의 작업이 동시에 도착하면, 세 번째 작업은 전체적으로 실행되기를 기다려야 하며 그 전 두 작업이 한 번씩 예약되어야 합니다. 반환 시간에는 효과적일지 모르지만, 이 접근 방식은 응답 시간과 상호작용성에는 상당히 나쁩니다.

실제로 터미널에서 타이핑하고, 다른 작업이 내 작업 앞에서 예약되어서 시스템의 응답을 보기 위해 10초를 기다려야 한다면 굉장히~ 불편하겠죠..?

 

따라서 아직 해결해야할 문제가 남았습니다. 

 

따라서 또 다른 문제가 남았습니다:

어떻게 응답 시간을 고려하는 스케줄러를 구축할 수 있을까 ? 🤔

 

7.7 Round Robin

이 문제를 해결하기 위해 나온 것이 Round-Robin, RR 스케줄링입니다. 기본 아이디어는 간단합니다.

RR은 작업을 완료시키는 대신, 작업을 Time slice(scheduling quantum라고도 함) 동안 실행한 다음, 실행 대기열(run queue)의 다음 작업으로 context switch합니다. 작업이 완료될 때까지 반복하여 수행됩니다.

 

이러한 이유로 RR은 Time Slicing이라고도 불립니다. 시간 조각의 길이는 타이머 인터럽트 주기의 배수여야 하므로, 예를 들어 타이머가 10 ms마다 인터럽트되면 시간 조각은 10ms, 20ms 또는 10ms의 배수가 될 수 있습니다.

 

예시를 통해 확인해봅시다.

SJF vs RR

 

A, B, C가 모두 동일한 시간에 도착했고, 모두 실행시간이 5초라고 가정해봅시다.

 

SJF의 경우

A Response time = 0

B Response time = 5

C Response time = 10

 

avg response time = 5

 

RR의 경우

A Response time = 0

B Response time = 1

C Response time = 2

 

avg response time = 1

 

보다시피 엄청난 차이가 존재하는 것을 알 수 있습니다.

 

Time slice의 길이는 RR에 대해 중요한 역할을 합니다. Time slice의 길이가 짧을 수록 Response time metrics안에서 RR의 성능이 더욱 좋아집니다. 하지만 작업을 그만큼 더 많이 전환한다는 것을 뜻하고, 이는 곧 Context Switching의 비용이 더욱 커진다는 뜻입니다.

 

Context Switching의 비용은 레지스터를 save and restore하는 운영체제의 작업에서만 발생하는 것이 아닙니다.

CPU cache, TLB, Branch predictors, on-chip 하드웨어에서 상당한 state를 누적합니다.

다른 작업으로 전환하면 이 state가 모두 비워지고 현재 실행 중인 작업에 관련된 새로운 state를 가져오기에 눈에 띄는 성능 비용이 발생할 수 있습니다.

 

하지만 그렇다고 또 time slice를 너무 길게 만들어버리면 응답 시간이 길어지기 때문에... 적절한 time slice의 값을 정하는게 중요합니다.

(하지만 적절한 값을 구하는게 사실 제일 어렵죠 늘)

 

 

그리고 또, Response time mertics에서는 Round Robin이 최고의 성능을 나타내지만, Performance, 즉 Turnaround time을 기준으로 보면 어떨까요 ? (Figure 7.7)

 

RR의 경우

A Turnaround time = 13

B Turnaround time = 14

C Turnaround time = 15

 

avg turnaround time = (13 + 14 + 15) / 3 = 14초

 

상당히 나쁜 것을 알 수 있습니다.

사실 RR이 하는 알고리즘을 보면 하나의 작업을 time slice단위로 잘게 잘게 쪼개서 응답시간을 높인 것이기 때문에 작업이 완료되는 시간이 더 늦어지는 것은 어찌 보면 당연한 결과인 것 입니다.

 

이는 Performance와 Fairness의 trade off관계의 연장선으로 바라봐야합니다.

 

SJF나 STCF가 성능 면에서 매우 좋지만, 공정성 측면에서는 좋지 않지만

RR은 성능 측면에서는 좋지 않지만, 공정성 측면에서 좋은 것처럼 말입니다.

 

쉽게 말해서 모든 것을 원하고자 하는 것은 불가능합니다  😂

 

지금까지 잠깐 정리해보자면,

첫 번째 유형(SJF, STCF)은 반환 시간(Turnaround time)을 최적화하지만 응답 시간(Response time)에는 부적합합니다.

두 번째 유형(RR)은 응답 시간(Response time)을 최적화하지만 반환 시간(Turnaround time)에는 부적합합니다.

 

그리고 아직 고쳐야할 할 두 가지 가정이 있습니다

• 4번 가정(작업이 I/O를 수행하지 않는다)
• 5번 가정(각 작업의 실행 시간이 알려져 있다). 

이제 그러한 가정들을 다루어 보겠습니다.

7.8 Incorporating I/O

1. 각 작업은 동일한 시간 동안 실행됩니다.
2. 모든 작업이 동시에 도착합니다.
3. 시작하면 각 작업은 완료될 때까지 실행됩니다.
4. 모든 작업은 CPU만 사용하며 (즉, I/O를 수행하지 않습니다).
5. 각 작업의 실행 시간이 알려져 있습니다. 

 

이제 4번 가정도 지워봅시다. 사실 Input과 Output이 아예 존재하지 않는 프로그램이 존재할까요 ? 아니기 때문에 과감히 지웁니다.

 

I/O 요청을 보내게 되면 프로세스는 Blocked상태가 되고, Blocked된 상태에서 굳이 CPU를 들고 있을 필요가 없죠. 따라서 스케줄러는 그 시점에서 다른 작업을 스케줄링해야합니다.

 

또한 I/O가 완료될 때 스케줄러는 결정을 내려야 합니다. 그럴 때 인터럽트가 발생하고, 운영체제가 I/O를 발생시킨 프로세스를 Blocked 상태에서 Ready 상태로 이동시킵니다. 물론 그 시점에서 작업을 실행하기로 결정할 수도 있습니다.

 

운영체제는 각 작업을 어떻게 처리해야 할까요?

 

바로 예시를 함께 봅시다.

A는 10ms동안 CPU를 사용하여 작업하고, 곧바로 10ms동안 I/O 요청을 발생시킵니다.

B는 기존의 작업들처럼 50ms시간만큼의 CPU작업만 존재합니다.

 

두 작업 모두 CPU 사용시간이 총 50ms라는 점은 동일합니다.

 

근데 사진만 보면 정말 딱봐도 비효율적이라는 것이 느껴집니다. I/O를 고려하지 않고 하나의 작업을 실행한 다음 다른 작업을 실행하는 것은 별로 의미가 없어보입니다.

 

흔한 접근 방식은 A의 각 10ms 하위 작업 각각을 독립적인 작업으로 처리하는 것입니다. 

 

따라서 시스템이 시작될 때, 선택지는 10ms A 또는 50ms B를 예약할 것인지입니다.

STCF에서는 이 경우 A를 선택합니다. 그런 다음 A의 첫 번째 하위 작업이 완료되면 B만 남아 있고 실행을 시작합니다.

그런 다음 A의 새로운 10ms 하위 작업이 제출되고 B를 선점하여 10ms 동안 실행됩니다. 이렇게 하면 CPU가 다른 프로세스의 I/O 완료를 기다리는 동안, 다른 프로세스에 의해 사용되어 중첩이 가능하며, 시스템은 더 효율적으로 활용됩니다. (Figure 7.9)

7.9 No More Oracle: 더 이상의 신탁은 없다...

사실 지금까지는 저희는 인간이 범접할 수 없는 신의 힘을 빌린 가정을 두고 이야기하고 있었습니다.

 

1. 각 작업은 동일한 시간 동안 실행됩니다.
2. 모든 작업이 동시에 도착합니다.
3. 시작하면 각 작업은 완료될 때까지 실행됩니다.
4. 모든 작업은 CPU만 사용하며 (즉, I/O를 수행하지 않습니다).
5. 각 작업의 실행 시간이 알려져 있습니다. 

그것은 바로 실행시간, 바로 5번 가정에 대한 이야기입니다.

앞에서도 살짝 얘기했지만, 프로그램을 실제로 다 돌려보지 않고서는 실행 시간이 얼마나 걸리는지는 미래에서 오지 않고서야 알 수가 없습니다. 

 

그렇다면..지금껏 5번 가정을 기반으로 이야기를 했는데 이제 방법은 없는 것 일까요...???

 

실행 시간을 몰라도 SJF/STCF처럼 효율적이고, Round Robin처럼 공정한 스케줄링 정책은 없는 것인가요 ?? 🤔

---

추가)

아니요 ! 아직 끝은 아닙니다. 이번 글에서는 자세히 언급하지는 않지만 아래와 같이 아직 많은 방법들이 더욱 더 존재합니다.

Multi-Level Feedback Queue

SJF/STCF 반환시간만을 놓고 봤을 때 optimal함. 이것보다 더 좋아질 수 없음

하지만 현실적으로 불가능하기 위해 큐를 여러개 만들어서 비슷하게 만듦.

1개, 100개 있을 때 1개 끝나고 100개 할려했는데 2개짜리가 또 들어옴. 이런식으로 short job이 계속 들어오면 long job은 계속 기다리게 됨. 이것도 또 공정하지 못함.

long job한테 기회가 돌아가지 않음. 따라서 이런 문제를 해결하기 위한 방법들이 또 존재함 (Priority boost)

Proprotional Share(Fair Share)

Short job한테 확률을 많이 주기

Lottery - 비결정적

Short job한테 티켓을 10장 주고 Long job은 티켓 1장만 주기. 그리고 추첨하면 아무래도 Short job이 당첨확률이 더 높다(스케줄링 확률 증가) 하지만 long job도 어쩌다가 당첨될 수 있다. 기회 분배 가능

근데 이걸 하다보니까 결정적이지 않음.

디버깅이 가능한 이유는 두번째 실수한 곳에서 똑같이 에러가 나기 때문. 다시 실행하면서 결과를 추적할 수 있기 때문에. 하지만 이 방법은 비결정적이기 때문에 디버깅이 불가능. 예측이 불가능해짐. 이걸 결정적으로 만들어보자

Stride - 결정적

CFS - Linux

실제 Linux에서는 어떻게 구현되어있는지 → CFS

Lottery → Stride로 전환되서 Stride에서 여러가지 추가된게 CFS

작업이 많아서 트리 구조를 사용한다.

 

---

마무리

이렇게 context switching의 매커니즘 이후에 Policy에 대해서 알아봤습니다. 객체지향 설계를 할 때에도 책임을 분리하면 할 수록 생기는 복잡성, 엄청난 코드 점핑 등을 두고 이런 trade off관계를 생각하게 보았는데 운영체제라고 다를게 없네요.

성능과 공정성 차이의 trade off, 책에서 "쉽게 말해서 모든 것을 원하고자 하는 것은 불가능합니다"라는 말은 인생이나 세상 모든 것에 비추어봐도 관통하는 말인 것 같네요.

 

이렇게 Scheduling Policy에 대해서 알아보았고, 다음글은 Multi-Level Feedback Queue에 대한 집중탐구시간입니다.