나는 완벽하게 공정한 스케줄러에 대해 꽤 많은 설명을 들었지만 모두 한 가지 중요한 세부 사항이 부족한 것 같습니다. 모든 것이 설명되는 방식은 본질적으로 실행 중인 "큐"(효율적인 순서를 유지하는 레드-블랙 트리)에 대한 요약과 각 프로세스가 vruntime 값을 업데이트하는 방법에 대한 세부 정보로 요약됩니다. 주요 세부 사항에 대한 요약은 건너뛰고 내 질문에 중요한 내용에만 집중하겠습니다.
프로세스가 예약될 때마다 vruntime이 업데이트되어 CPU에 도달한 시간을 반영합니다. 이러한 설명의 대부분은 값이 단조롭게 증가한다는 사실을 나타냅니다("엄격하게 증가하는" 것이 더 정확할지라도). 운영 체제는 새로운 프로세스를 예약하기로 결정할 때마다 vruntime이 가장 낮은 프로세스를 살펴보고 실행을 위해 보냅니다.
이러한 설명에는 중요한 세부정보가 누락되어 있습니다. 실행, 실행, 실행하는 브라우저 프로세스가 있다고 가정해 보겠습니다. 며칠 후에 해당 프로세스의 vruntime은 많은 시간의 CPU 시간을 반영하여 커질 것입니다. 동일한 머신(논의를 위해 단일 CPU 하드웨어)에는 새로운 CPU 바인딩 프로세스가 있습니다. 스케줄러는 두 프로세스를 모두 살펴보고 CPU Hog의 vruntime이 0임을 확인하고 이를 예약합니다.
내가 본 모든 CFS 설명에는 이 프로세스가 다른 프로세스의 vruntime이 줄어들 때까지 실행된다고 나와 있지만 이는 사실이 아닙니다. 이 경우 브라우저 프로세스는 몇 시간 또는 며칠 후에 CPU 사용량이 이를 따라잡을 때까지 중단됩니다.
퍼지 요소가 있어야 하거나 가상 런타임을 직접 비교하는 것보다 더 많은 것이 있어야 하지만 이 모든 설명에서는 이 중요한 세부 사항을 건너뛰었습니다. 내가 무엇을 놓치고 있나요?
(또한 대규모 다중 CPU 시스템이 프로세스 그룹의 vruntime을 오버플로할 수 있다는 사실을 아는 사람이 있습니까? CPU 시간은 약 544년을 얻어야 하지만 64 프로세서 시스템은 10년 동안 작동할 수 있습니다... ..신경 쓰지 마세요. =] )
답변1
따라서 일반적인 CFS 설명에는 두세 가지 사항이 누락되어 있습니다. 스케줄러는 vruntime이 가장 낮은 프로세스를 선택하고 실행합니다. 그러나 vruntime은 실제로 프로세스가 CPU에서 소비한 시간을 나타내지 않으며 현재 실행 대기열에서 소비한 시간도 나타내지 않습니다. 이는 기발한 수학을 통해 원하는 의미를 기발하게 구성하는 경험적으로 계산된 값입니다.
각 CPU에는 자체 프로세스 대기열(실제로는 RB 트리이지만 대기열처럼 동작함)이 있습니다. 각 프로세스 큐는 가상 런타임이 가장 작은 프로세스인 "가장 왼쪽" 프로세스를 추적합니다. 총 실행 시간을 추적할 때 대기열의 가상 실행 시간을 계산하지 마세요. 대신 프로세스의 가상 런타임과 대기열의 최소 런타임 간의 차이를 고려하세요. 이 차이는 중요한 의미를 갖습니다. 이는 해당 프로세스와 가장 왼쪽 프로세스 간의 실행 시간 차이입니다. 즉, 이 프로세스가 가장 왼쪽 프로세스보다 CPU 시간을 얼마나 더 많이 받는가입니다.
따라서 새로운 프로세스가 CPU 대기열에 들어가면 vruntime이 없습니다. 단지 가장 왼쪽 프로세스와 동일한 값을 상속받을 뿐입니다. vruntime은 이제 동일하므로 차이는 0입니다. 이는 새 프로세스가 더 이상예상되는가장 왼쪽 프로세스보다 CPU 시간이 더 많습니다. 다음 컨텍스트 전환 시 새 프로세스가 예약될 가능성이 있습니다.
프로세스는 여러 가지 이유로 실행 큐를 떠납니다. IO를 기다리거나 휴면 상태가 실행 큐를 떠나는 일반적인 트리거입니다. 프로세스가 일시적으로 CPU를 필요로 하지 않게 만드는 상황에서는 해당 프로세스가 대기열에서 제거됩니다. 이런 일이 발생하면 최대 절전 모드 프로세스의 vruntime에서 현재 최소 vruntime(가장 왼쪽 프로세스의 vruntime)을 뺍니다. 결과적으로 vruntime은 이제 다음 예약 프로세스보다 CPU 시간이 얼마나 더 많은지를 반영합니다. 실행 대기열에 다시 참여하려고 하면 대기열의 최소 vruntime이 프로세스의 vruntime에 추가되고 대기열 중간 어딘가에 입력됩니다. 이는 이전 대기열을 떠날 때 즐겼던 것과 거의 같은 위치입니다.
그게 설명이에요. vruntime은 프로세스가 현재 실행 대기열에 있는지 또는 예약 가능한 상태인지 여부에 관계없이 CPU 공정성 기록의 상대적 차이로 해석될 수 있도록 영리한 방식으로 작동합니다.