앞장에서 MLFQ 스케줄링 방식을 살펴봤었습니다. MLFQ는 turnaround time과 response time 두가지 토끼를 모두 잡는 것을 목표로 한 스케줄링 방식이었습니다. 이번장에서 다룰 Proportional share(fair-share) 스케줄링 방식은 이름에서부터 알 수 있듯이 Fairness, 공정함에 초점을 맞춘 스케줄링입니다.
즉, 각 작업이 CPU를 사용하는 시간의 특정 비율을 보장받을 수 있도록 해주는 스케줄링 방식입니다.
이 Proportional share의 초기 예시로 Lottery Scheduling이 널리 알려져있습니다. 이 Lottery Scheduling의 기본 개념은 매우 간단합니다.
일정 간격으로 복권을 추첨해서, 당첨된 프로세스가 다음에 실행되게 된다(스케줄링 된다)
이제부터 이 Lottery Scheduling의 주요 메커니즘과 그 효과들에 대해서 알아보겠습니다.
Basic Concept: Tickets Represent Your Share
티켓을 통해 CPU지분을 표현하자!
Lottery Scheduling의 기본 개념은 Tickets입니다.사진처럼 말그대로 티켓, 복권입니다.
바로 예를 통해서 이해해보겠습니다.
두 개의 프로세스 A와 B가 있다고 가정해보겠습니다. 여기서 총 100장의 티켓이 있는데, A가 75장(0~74)을 가지고 있고 B는 25장(75 ~99)을 가지고 있습니다. 그리고 일정 간격(time slice)마다 복권 추첨을 통해 당첨 번호(0부터 99까지)를 뽑습니다. 이 때 당첨번호를 가지고 있는 프로세스가 스케줄러에 의해 다음번에 스케줄링 되어 CPU를 사용하게 됩니다.
이제 예시를 보면 당연하게도 75장의 티켓을 가진 A가 훨씬 많은 비율로 CPU를 사용하는 모습을 볼 수 있습니다.
하지만 이것이 각각이 티켓을 분배받은 비율만큼 무조건 실행된다는 것이 보장되지는 않습니다. 실제로 B는 100장 중 25장, 즉 25% 비율로 할당받기를 기대하지만 20번 4번, 20%의 비율로 실행되었습니다. 하지만 시간이 지나면서, 여러 번의 복권 추첨을 거치다보면 할당된 티켓 비율에 맞게 더 정확히 실행될 가능성이 높아집니다.
각 작업의 CPU에 대한 지분을 표현하는 개념이 바로 티켓 !
다양한 Ticket Mechanisms
1. Ticket Currency(티켓 통화)
예제를 통해 이해하는 게 더 직관적인 것 같아서 바로 예를 들어보겠습니다.
사용자 A와 B가 있고, A는 A1과 A2라는 2개의 작업을 돌리고 싶어하고, B는 B1 하나의 작업만을 돌리고 싶어합니다.
이 때 주어진 티켓 총 수가 사용자에게 각각 100장 씩 총 200장이라고 가정하겠습니다.
A는 100장의 티켓을 받았지만, 내부에서 A나라 내에서 통용되는 티켓을 각 작업당 500장 씩 1000장을 찍어냈습니다. 그리고 500장씩 각 작업에게 준 것 입니다.
만약 이게 A 나라에 국한된 이야기가 아니라 세계 공용 화폐라면 말이 안되겠죠? A가 1000장, B가 10장이면 CPU는 거의 사용자A가 독점하는 수준이 될 것 입니다. 따라서 시스템은 이를 올바른 전역 값으로 자동으로 변환시켜 줍니다.
사용자가 A가 1000장을 내부에서 발행했지만, 사실 A는 처음 나눠준 100장만큼의 비율로 티켓을 가져야하기 때문에, 1000장의 1장당 효용 가치를 1/10 하락시킵니다. 따라서 A의 각 작업당 500장 나누어졌지만, 공용 화폐 기준으로 바라보면 500장이 아닌 10분의 1 하락한 가치인 50장만큼의 가치를 지니게 되는 것 입니다.
사용자 B는 10장밖에 발행을 하지 않았지만, 100장만큼의 효력을 지니게끔 만들기 위해서 한 장의 가치를 10배 올립니다. 따라서 10장은 100장의 효용을 가지게 됩니다.
이렇게 global currency로의 변환을 마친 다음, 복권 추첨은 global currency(200장)을 기준으로 어떤 작업을 실행할지 결정합니다.
2. Ticket Transfer
또 다른 유용한 메커니즘은 '티켓 전송(ticket transfer)'입니다. 티켓 전송을 통해 프로세스는 일시적으로 다른 프로세스에게 자신의 티켓을 양도할 수 있습니다. 이 기능은 특히 클라이언트/서버 환경에서 유용합니다. 클라이언트 프로세스가 서버에게 메시지를 보내어 클라이언트를 대신하여 어떤 작업을 수행하도록 요청할 때 이 기능이 특히 유용합니다. 작업속도를 높이기 위해 클라이언트는 서버에게 티켓을 양도할 수 있으며, 이렇게 함으로써 서버가 가진 티켓의 수가 많아지게 되어 CPU를 할당받는 비율이 높아지게 되어 서버의 성능을 최대화하여 클라이언트에서 요청한 작업을 빠르게 처리할 수 있습니다. 작업이 완료되면 서버는 티켓을 클라이언트에게 다시 돌려주어 이전 상태로 돌아갑니다.
3. Ticket Inflation
티켓 인플레이션이란 프로세스가 일시적으로 소유하는 티켓 수를 늘리거나 줄일 수 있음을 뜻합니다.
위에서 사용한 예시를 다시 가져와보겠습니다.
사용자 A는 자신의 작업 A1을 어떻게든 빨리 끝내야겠다고 판단합니다. 따라서 A1의 티켓을 멋대로 추가 발행해버립니다. 심지어 A내부, 로컬이 아닌 Global로 말이죠.
위에처럼 10장을 멋대로 추가 발행해서 총 티켓 추가 210장이 되고 작업A1이 가진 티켓은 60장으로 비율이 늘어나게 되었습니다.
그럼 이전보다 CPU를 사용할 확률이 증가하게 되어 일을 우선적으로 처리할 수 있게 될 것입니다.
여기에는 필수적으로 전제가 되어야하는 것이 있는데, 바로 다른 프로세스와의 신뢰관계입니다.
B입장에서 "아 A1이 진짜 급한 작업인가보구나...뭐 일 끝내면 다시 원래대로 돌려놓겠지..일단 믿어보자" 하는 마음가짐을 필요로 합니다.
만약 A가 이를 돌려놓지 않는다면 욕심 많은 프로세스가 CPU를 독점하게 되는 문제가 발생할 수도 있습니다. 따라서 B가 이런 경우를 생각해 A를 신뢰하지 않을 수도 있겠죠.
만약 B입장에서 A를 신뢰할 수 없다면 아래처럼 생각할 것 입니다.
"아니? 뭐야 나도 급해죽겠는데 자기 먼저 하겠다고 멋대로 10장을 추가해??😡 그럼 난 20장 추가한다!"
그렇다면 이제부터는 불보듯 뻔합니다. A가 10장, 그에 따라 B가 20장, 다시 A는 30장.. 경쟁의 시작입니다.
따라서 티켓 인플레이션은 서로 믿을 수 있는 프로세스 그룹이 있는 환경에서 적용될 수 있습니다. 이러한 경우에, 하나의 프로세스가 우선순위가 높다고 판단되어 CPU 시간을 더 필요로 할 경우, 다른 프로세스와 통신하지 않고도 시스템에 그 필요성을 반영하기 위해 global 티켓을 더 발해 우선 순위를 높일 수 있습니다.
Lottery Scheduling을 어떻게 구현할까?
Lottery Scheduling은 Linked List를 통해서 쉽게 구현할 수 있습니다.
linked list에 ticket과 함께 작업들이 나열되어있고, while문을 통해서 작업들을 순회하면서 티켓의 수를 counter변수에 누적합니다.
이 때, Counter값이 당첨 번호를 초과하게 되면 해당 작업이 스케줄링 됩니다.
새로운 작업이 추가된다고 할 때에도 Linked List뒤에 새로운 작업 노드를 추가하고, 전체 티켓 수인 totalTickets의 개수를 추가된 Ticket양만큼을 늘리고 삭제된다고 할 때에는 반대로만 진행해주면 작업의 추가/삭제 또한 자유롭습니다.
이 때 작업들을 티켓 수가 높은 순대로 내림차순으로 정렬하면 보다 효율적으로 알고리즘을 탐색할 수 있습니다. 큰 수의 당첨번호라면 뒤에까지 탐색하지 않고도 앞단에서 당첨된 작업을 찾을 수 있기 때문입니다.
An Example
이제 Lottery Scheduling의 평가 기준을 제시하고 평가해봅시다. 그를 위해서 예시를 살펴봅시다.
2개의 작업이 동일한 티켓을 가지고 있고, 동일한 실행 시간 R을 가지고 있다고 가정해보겠습니다.
Lottery Scheduling은 말그래도 복권 추첨을 통해서 당첨된 작업을 스케줄링하는 것이기 때문에 비결정적입니다.
따라서 우리가 앞서서 시행을 여러번 계속해서 반복하다보면 비율에 근사하게 1:1의 비율로 CPU를 나눠서 쓰게 될 것이다라고 얘기했었는데, 아무리 그렇다하더라도 비결정적인 알고리즘이기 때문에 두 작업이 종료되는 시간에는 차이가 생길 수 밖에 없습니다.
이 차이를 양적으로 측정하기 위해서 fairness metric를 정의합니다. 이 지표는
첫번째 작업이 완료된 시간 / 두번째 작업이 완료된 시간
으로 표현됩니다. 예를 들어, R이 10인 경우, 첫번째 작업이 10에 완료되고 두번째 작업이 20에 완료된다면 F = 10/20 = 0.5가 됩니다.
두 작업이 거의 동시에 끝나면 끝날 수록 이 F지표는 1에 가까워질 것입니다. 따라서 이 fairness metric이 1에 가까울수록 공정한 스케줄러이며 0에 가까울수록 불공정한 스케줄러가 되는 것 입니다.
위 그래프를 확인해보면 작업의 실행시간 R이 길면 길수록 fairness, F가 1에 가까워지는 것을 볼 수 있습니다.
작업시간 R이 길다라는 것은 그만큼 CPU를 여러번 나눠써야한다는 얘기고, 이는 곧 여러번의 복권 추첨 시행을 거치게 된다는 말이기 때문에 시행수가 많아질 수록 fairness metric이 1에 가까워진다는 얘기가 되는 것 입니다.
작업에 티켓은 어떻게 할당할까?🤔
Lottery Scheduling에서 근본적으로 해결되기 쉽지 않은 어려운 문제가 존재합니다. 바로 작업에 티켓수를 얼마나 줘야할지 정하는 것이 매우 어렵다는 것 입니다. 짧은 작업에 티켓수를 더 많이 주면 되는거 아니야? 라고 생각할 수 있지만, 저희는 프로그램을 직접 다 돌려보기 전에는 해당 프로그램의 실행시간을 미리 알 수 없기 때문에 또 다시 어려움에 닥치게 됩니다. 이런 상수를 Voo-doo constant라고도 한다고 합니다.
결정적인 스케줄링 방식은 없나?👨🏻⚖️
Stride Scheduling 등장🦜🦩
Lottery Scheduling은 비결정적인 스케줄링 방식입니다. 구현하기에는 Lottery Scheduling이 정말 쉽지만 비결정적이라는 것은 생각보다 그렇게 메리트로 다가오지 않는게 사실입니다. 위에서도 살펴봤듯이 정확한 비율로 CPU를 제공하지 못할 가능성이 생긴다는 것도 그닥 마음에 들지는 않을 수 있습니다. 특히 작업 실행 시간 R이 짧으면 짧을 수록 이 비율은 더욱 정확하지 못하기 때문에 이러한 이유들로 결정적인 스케줄링 방법인 Stride Schdeuling이 등장하게 됩니다.
우리가 평상시에 개발하면서 늘 에러를 맞닦들이게 됐을 때, 에러 상황이 비결정적이라면 어떨까요 ??
정말 상상하기 싫네요..에러의 원인을 파악하기 위해서는 에러를 재현해야할 필요가 있는데, 에러가 뜨는 것도 비결정적이라면 디버깅하는 입장에서는 정말 미칠 노릇일 겁니다.
Stride scheduling도 사실 간단합니다. 시스템 내의 각 작업은 티켓 수에 반비례하는 역수인 stride를 가지고 있습니다.
즉, 티켓 수가 많을수록 stride는 작습니다.
위에서 본 예시에서 작업 A, B, C는 각각 100, 50, 250의 티켓을 갖고 있는데, 각 프로세스의 stride를 계산할 수 있습니다.
예를 들어, 큰 숫자를 해당 티켓 값으로 나누면(10,000을 각 티켓 값으로 나눈다고 가정하면), A, B, C의 각각의 stride 값은 100, 200, 40이 됩니다. 이 값을 각 프로세스의 stride라고 하며, 각 프로세스가 실행될 때마다 해당 프로세스의 global progress(진행 상황)을 추적하기 위해 해당 프로세스의 counter(pass value라고 함)를 해당 프로세스의 stride만큼 증가시킵니다.
스케줄러는 가장 낮은 pass값을 가진 프로세스를 스케줄링합니다. 그리고 해당 프로세스를 실행시키면 pass값을 해당 프로세스의 stride값만큼 증가시킵니다. 대충 코드로 보면 아래와 같습니다.
var curr = removeMin(queue) // 가장 낮은 Pass값의 프로세스 빼기
schedule(curr) // scheduling
curr.pass += curr.stride // pass값에 해당 프로세스의 stride값 더하기
insert(queue, curr); // 해당 프로세스를 다시 큐에 넣기
위 코드가 반복되는 것 입니다. 이제 표로도 한번 살펴봅시다.
A,B,C는 stride가 각 각 100,200,40으로 시작합니다. 처음에는 0부터 시작하기 때문에 임의로 선택되는데 여기서 ABC순으로 선택된다고 가정하겠습니다.
1. A가 처음 스케줄링 되어 실행되고, A의 pass값은 stride값만큼 증가하여 100이 되었습니다.
2. 그 후 B가 스케줄링 되어 실행되고, B의 pass값은 200이 되었습니다.
3. 이제 가장 낮은 pass값을 가지고 있는 C가 스케줄링 되어 C의 pass값은 400이 됩니다.
4. 다시 C의 pass값이 가장 낮기 때문에 계속해서 C가 스케줄링 되면서 pass값은 C의 stride값인 40만큼 증가됩니다.
5. 200, 200, 200 모두 동일해지는 시점까지 C가 계속 스케줄링 되다가 이 후 부터는 다시 처음의 과정이 반복되게 됩니다.
스케줄링된 횟수를 보면 총 8번의 시행 중 A는 2번, B는 1번, C는 5번으로 2: 1: 5로 티켓 수의 비율을 동일하게 반영하고 있는 것을 알 수 있습니다. Lottery Scheduling은 이 비율이 비결정적이였기에 실행할 때마다 달라질 수 있었지만, Stride Scheduling은 이 비율이 정확하게, 결정적으로 유지되며 반영됩니다.
그러면 아래와 같은 의문이 생길 수도 있을 것 같습니다.
뭐야? 그러면 Stride Scheduling은 Lottery Scheduling의 완벽한 상위호환아니야? Lottery Scheduling을 쓸 이유가 있나? 🤔
Lottery Schdeuling은 Stride Scheduling과 달리 작업 별 progress를 추적할 필요가 없습니다. 각 작업 당 가지고 있는 티켓 수를 제외하면 어떠한 state도 추적할 필요가 없습니다. 새로운 작업이 추가된다던가, 삭제된다했을 때도 단순히 Total ticket의 수만 들어온 작업이 가지고 있는 티켓 수만큼 늘려주거나 빼주면 됩니다.
반면 Stride Scheduling은 위의 예시를 기반으로 A,B,C가 어느정도 실행되어 어느정도 pass값이 쌓인 상태에서 새로운 작업 D가 들어오게 된다면, 우리의 로직대로라면 D가 A,B,C의 pass값 중 가장 낮은 pass값에 근사하게 될 때까지 CPU를 새로운 작업인 D가 독점하게 될 것입니다. 이건 우리가 원하는게 아닙니다😦. 따라서 D가 들어올 때 D의 pass값을 0으로 시작하는게 아닌 그 당시 가장 낮은 pass값과 동일하게 맞추고 시작한다던가 추가적인 고민이 필요하게 됩니다. Lottery Scheduling의 경우에는 이런 고민이 일절 필요가 없죠. 그냥 total ticket 수를 늘려주거나 줄이거나 해주면 끝입니다.
따라서 이런 부분에 있어서 Lottery Scheduling은 stride scheduling에 비해 이점을 가지게 됩니다.
Linux에서 사용하는 Completely Fair Scheduler (CFS)
위에서 살펴본 Lottery Scheduler와 Stride Scheduler가 있지만 현재 리눅스는 Completely Fair Scheduler(CFS)를 사용하고 있다고 합니다. CFS는 스케줄링 결정에 매우 적은 시간을 소비된다고 하고, Red-Black Tree와 같은 자료구조를 적절히 활용해서 이와 같은 혀과를 얻습니다.
스케줄링이 구글 데이터 센터 CPU 시간의 약 5%를 사용한다는 사례를 바탕으로 현대에서는 스케줄링을 결정하는데 드는 시간을 줄이도록, 이러한 오버헤드를 줄이드는 것이 현대 스케줄러 아키텍처의 주요 목표입니다.
CFS의 기본적인 동작
대부분의 스케줄러는 고정된 Time slice을 기반으로 동작했는데, CFS는 조금 다릅니다.
CFS의 목표는 'CPU를 모든 프로세스들 사이에 공장하게 분배하는 것'입니다.
이를 Stride Scheduling에서 사용된 Pass와 동일한 개념이지만 vruntime을 사용해서 수행합니다.
각 프로세스가 실행될 때마다, 해당 프로세스는 vruntime을 누적합니다. 가장 기본적인 경우에는 각 프로세스의 vruntime이 실제 시간과 비례하여 동일한 비율로 증가합니다. 스케줄링 결정이 발생할 때, CFS는 다음에 실행할 프로세스를 가장 낮은 vruntime을 가진 프로세스로 선택합니다.
한가지 의문점이 듭니다.
스케줄러는 어떻게 현재 실행 중인 프로세스를 중지하고 다음 프로세스를 중지할 때를 알까 ?? 🤔
여기서 유의해야할점은 CFS가 프로세스를 너무 자주 switch하면 공정성은 높아지겠지만, 성능이 저하됩니다. (context switching비용)
그리고 반대로 너무 조금씩 switch를 하게 된다면 성능은 향상하겠지만, 공정성은 저하됩니다.
CFS는 이 균형을 다양한 control 매개변수들을 통해 관리합니다.
첫 번째로는 'sched latency(스케줄 지연)'입니다. CFS는 이 값을 사용하여 한 프로세스가 switch를 고려하기 전에 실행되어야 하는 시간을 결정합니다(동적인 방식으로 해당 프로세스의 time slice을 결정합니다). 일반적인 'sched latency' 값은 48(밀리초)입니다.
CFS는 이 값을 CPU에서 실행 중인 프로세스 수(n)로 나누어 프로세스의 시간 조각을 결정하므로, 이 기간 동안 CFS가 완전히 공정하게 작동할 수 있도록 보장합니다.
아래 예를 통해서 더 살펴보겠습니다.
맨 처음 ABCD 이렇게 4개의 작업이 존재한다고 가정했을 때, CFS는 sched latency값을 지금 실행중인 프로세스의 수 n으로 나누어 각 프로세스의 time slice를 48 / 4 = 12, 12ms로 결정합니다. 그리고 가장 낮은 vruntime값을 가진 프로세스를 스케줄링하여 실행하기 전에 timer를 맞춰놓고 프로세스가 시작과 동시에 Timer를 시작시키면 12ms가 지나게 되면 context switching이 일어나는 방식입니다.
그런데 이대로면 염려되는 상황이 보이네요. 만약 실행중인 프로세스가 너무 많다면 어떻게 할까요..?
진짜 예를 들어 48개의 프로세스가 실행중이라고 한다면 48 / 48 = 1, 1ms마다 Context switching이 일어나게 된다면 성능이 현저히 떨어질 것 같지 않나요??
그래서 CFS는 이 문제를 해결하기 위해서 min granularity(최소 시간 단위)라는 매개변수를 추가합니다. 보통 6ms로 설정된다고 합니다. CFS는 프로세스의 time slice를 이 값보다 작게 설정하지 않도록하여 스케줄링 오버헤드가 너무 많이 발생하지 않도록 보장할 수 있습니다.
위에서 제가 든 예시라면, 1ms로 나누어져야하는 상황이지만 CFS는 1ms 대신 min granularity인 6ms로 time slice를 설정하여 목표인 sched latency인 48ms에 완벽하게 근접하지는 않지만 여전히 높은 효율을 달성하면서 근접하게 되는 것입니다.
Weighting (Niceness)
지금까지의 방법은 좋지만, 이대로만 한다면 모든 작업이 완전히 동일한 중요도, 우선순위를 가지고 작업을 하게 될 것 입니다. 하지만 우선순위가 높은 작업이 있고 낮은 작업이 있기 마련이죠. 이를 위해 CFS는 가중치(weight)를 작업에 부여하기로 결정합니다.
이 때 매개변수 이름이 nice입니다. 각 프로세스에 대해 nice매개변수를 -20부터 +19까지 설정할 수 있으며, 기본값은 0입니다.
양수의 nice값은 우선순위가 낮음을 의미하고 음수 값은 우선순위가 높음을 의미합니다. (음수가 이진수로 하면 훨씬 큰 수라서 이렇게 되는 듯)
우선순위가 높은 친구들은 time slice를 많이 받아야합니다. 따라서 자신의 우선순위 가중치값(weight k)가 높다면 더 많은 time slice를 가지게 됩니다. 반대로 우선순위가 낮다면 Weight k가 작아진다면 그만큼 적은 비율로 sched_latency(48ms) 곱하게 되기 때문에 적은 time slice를 가지게 됩니다.
vruntime은 Stride scheduling의 pass와 동일하다고 설명했었습니다. 따라서 vruntime이 작을수록 더 많이 스케줄러의 선택을 받을 확률이 높아지겠죠 ? 우선순위가 높은 작업들은 이 vruntime을 최소한으로 증가시키는 방향으로 갈 것이고 우선순위가 낮은 작업들은 vruntime을 막 높히게 될 것 입니다.
높은 우선순위를 가진 작업이라면 weight i(자신의 우선순위 값)를 높게 설정하여 비율을 작게 만들어 적은 값이 누적될 수 있도록 해야합니다. 반대로 낮은 우선순위라면 weight i를 낮게 설정하여 비율을 높게 만들어 높은 값이 누적되게 합니다.
Red-Black Trees를 통해 CFS를 개선시키자.
CFS의 주요 초점 중 하나는 위에서 말한 대로 효율성입니다. 스케줄러의 효율성에는 여러 측면이 있지만, 그 중 하나는 다음 실행할 작업을 찾는 데 소요되는 시간입니다. 리스트와 같은 간단한 데이터 구조는 확장성이 부족합니다. 현대 시스템은 때로 수천 개의 프로세스로 구성되어 있으므로, 단순히 리스트를 전체 탐색하는 것은 너무 비효율적입니다.
CFS는 프로세스를 red-black tree(레드-블랙 트리)을 사용함으로써 이 문제를 해결합니다. 레드-블랙 트리는 여러 종류의 균형 트리 중 하나입니다. 단순한 이진 트리와 달리(최악의 경우 삽입 패턴에 따라 리스트와 유사한 성능을 보일 수 있는), 균형 트리는 낮은 depth를 유지하기 위해 약간의 추가 작업을 수행하여 연산이 log시간(선형이 아니라)으로 유지될 수 있도록 합니다.
CFS는 모든 프로세스를 레드-블랙 트리에 저장하지 않습니다. 대신 실행 중이거나 실행 가능한 프로세스만 레드-블랙 트리에 저장됩니다. 프로세스가 blocked 상태로 들어가면(예: I/O 완료를 기다리거나 네트워크 패킷 수신을 기다리는 경우), 트리에서 제거되고 다른 곳에서 추적됩니다.
이를 더 명확히 이해하기 위해 예시를 살펴보겠습니다.
프로세스가 열 개 있다고 가정하고, 이들의 vruntime 값이 다음과 같다고 가정해봅시다: 1, 5, 9, 10, 14, 18, 17, 21, 22, 24. 만약 이 작업들을 순서대로 정렬된 목록에 유지한다면, 다음으로 실행할 작업을 찾는 것은 간단합니다. 첫 번째 요소를 제거하기만 하면 됩니다. 그러나 해당 작업을 다시 리스트에 (순서대로) 삽입할 때는 O(n) 작업으로 리스트를 스캔하여 올바른 위치를 찾아야 합니다. 어떤 검색도 평균적으로 선형 시간이 걸리는 매우 비효율적인 방법입니다.
같은 값을 레드-블랙 트리에 유지하면 위에 그림에 나와 있는 것처럼 표현됩니다. 프로세스는 vruntime에 따라 트리에서 정렬되며, 대부분의 작업(삽입 및 삭제와 같은)이 로그 시간인 즉, O(log n)에 이루어집니다. n이 수천 개인 경우 로그 시간이 선형 시간보다 훨씬 효율적입니다.
I/O 요청과 Sleeping Processes
다음에 실행할 가장 낮은 vruntime을 선택하는 데 문제가 발생하는 상황 중 하나는 오랜 시간 동안 blocked 상태에 있었던 작업들과 관련이 있습니다. A와 B 두 개의 프로세스가 있다고 가정해보겠습니다. 하나는(예: A) 계속해서 실행되고 있는 상태이고, 다른 하나(예: B)는 10초 동안 blocked 상태에 있었습니다. B가 Ready를 거쳐 다시 깨어날 때 B의 vruntime은 A의 것보다 10초 뒤에 있을 것이며, 이에 대해 어떤 추가작업을 해주지 않는다면 B는 이제 CPU를 다음 10초 동안 독점하여 A를 starvation에 처하게 만들 수 있습니다.
CFS는 이러한 경우에 대비하여 작업이 깨어날 때 해당 작업의 vruntime을 트리에서 찾은 최소값으로 설정함으로써 이를 처리합니다.
이 때 트리에는 현재 실행중인 작업들만 있다는 것을 유의하셔야합니다!! 이렇게 함으로써 CFS는 starvation현상을 피할 수 있지만, 그에는 비용이 따릅니다. 짧은 기간 동안 자주 blocked 상태에 있는 작업(IO요청이 많은 작업)은 CPU의 공정한 할당을 받지 못할 수 있습니다.
(계속해서 트리에서 나갔다 들어올 때 그 때 가장 낮은 vruntime으로 초기화되기 때문에)
마무리
이렇게 Proportional share scheduling 방식의 Lottery Scheduling(비결정적), Stride Scheduling(결정적), CFS 에 대해서 공부해보았습니다. 스케줄링 방식은 정말 이곳 운영체제 뿐만이 아니라 네트워크 등 여러 곳에서 사용되기 때문에 잘알아두면 좋을 것 같다는 생각으로 공부해보았습니다. 이제 아직 완전 초반이지만 쭉쭉 OSTEP 정복해보겠습니다. 화이팅
'CS > 운영 체제🖥️' 카테고리의 다른 글
| [OS] Multi Level Feedback Queue (MLFQ) (0) | 2023.12.11 |
|---|---|
| [OS] Scheduling: Introduction (Scheduling Policy들 정리) (0) | 2023.11.06 |
| [OS] CPU 가상화 메커니즘 (Limited Direct Execution) - 2부 (1) | 2023.10.31 |
| [OS] CPU 가상화 메커니즘 (Limited Direct Execution) - 1부 (1) | 2023.10.31 |
| [OS] OS Overview (CPU가상화, 메모리 가상화, Concurrency, Persistence) (0) | 2023.10.23 |
댓글