В этой главе мы рассмотрим другой тип планировщика, известный как планировщик proportional-share, также иногда называемый планировщиком справедливой доли. Proportional-share основан на простой концепции: вместо оптимизации времени выполнения или отклика планировщик может попытаться гарантировать, что каждое задание получит определенный процент процессорного времени.
Отличный ранний пример планирования в стиле proportional-share можно найти в исследованиях Waldspurger and Weihl и известен как lottery scheduling; однако эта идея, безусловно, старше. Основная идея довольно проста: время от времени проводите лотерею, чтобы определить, какой процесс должен запускаться следующим; процессы, которые должны запускаться чаще, должны иметь больше шансов выиграть в лотерею. Легко, не правда ли? А теперь перейдем к деталям! Но не раньше чем сформулируем суть проблемы:
СУТЬ ПРОБЛЕМЫ: КАК ПРОПОРЦИОНАЛЬНО РАЗДЕЛИТЬ ПРОЦЕССОР
Как мы можем спроектировать планировщик для пропорционального распределения ЦП? Каковы ключевые механизмы для этого? Насколько они эффективны?
Базовая концепция: распределение доли на основе билетов
В основе планирования лотереи лежит одна очень простая концепция: билеты, которые используются для представления доли ресурса, которую должен получить процесс (или пользователь, или что-то еще). Процент билетов, которые имеет процесс, представляет его долю в рассматриваемом системном ресурсе.
Давайте рассмотрим пример. Представьте себе два процесса, A и B. A имеет 75 билетов, а B - только 25. Таким образом, мы хотели бы, чтобы А получил 75% процессора, а В - оставшиеся 25%.
Планирование лотереи достигает этого вероятностно (но не детерминистически), проводя лотерею с определённой частотой. Проведение лотереи просто: планировщик должен знать, сколько всего билетов (в нашем примере их 100). Затем планировщик выбирает выигрышный билет, который представляет собой число от 0 до 99. Предполагая, что А держит билеты от 0 до 74 и В ОТ 75 до 99, выигрышный билет просто определяет, будет ли А или В работать. Затем планировщик загружает состояние этого выигрышного процесса и запускает его.
СОВЕТ: ИСПОЛЬЗУЙТЕ СЛУЧАЙНОСТЬ
Одним из самых красивых аспектов планирования лотереи является использование случайности. Когда вам нужно принять решение, использование такого рандомизированного подхода часто является надежным и простым способом сделать это.
Случайные подходы имеют по крайней мере три преимущества перед более традиционными решениями. Во-первых, random часто избегает странного поведения углового случая, с которым более традиционный алгоритм может иметь проблемы. Например, рассмотрим политику замены LRU (более подробно рассмотренную в следующей главе, посвященной виртуальной памяти); хотя LRU часто является хорошим алгоритмом замены, он достигает наихудшей производительности для некоторых циклически-последовательных рабочих нагрузок. У random, с другой стороны, нет такого худшего случая.
Во-вторых, random легкий, использует мало ресурсов для отслеживания альтернативные варианты. В традиционном алгоритме планирования справедливой доли отслеживание того, сколько ЦП получил каждый процесс, требует учета каждого процесса, который должен обновляться после запуска каждого процесса. При этом при использовании случайного подхода требуется только самое минимальное состояние каждого процесса (например, количество билетов).
Наконец, случайный подход может быть довольно быстрым. До тех пор, пока генерация случайного числа происходит быстро, принятие решения также является быстрым, и поэтому случайность может быть использована в ряде мест, где требуется скорость. Конечно, чем быстрее потребность, тем больше случайность стремится к псевдослучайности.
Вот пример вывода выигрышных билетов такого лотерейного планировщика:
Вот получившееся расписание:
Как видно из примера, использование случайности в планировании лотереи приводит к вероятностной корректности в достижении желаемой пропорции, но не дает никаких гарантий. В нашем примере выше B получает только 4 из 20 временных срезов (20%) вместо желаемого 25% распределения. Однако чем дольше эти две работы конкурируют, тем больше вероятность того, что они достигнут желаемого процента.
СОВЕТ: ИСПОЛЬЗУЙТЕ БИЛЕТЫ ДЛЯ ПРЕДСТАВЛЕНИЯ ДОЛИ
Одним из самых мощных (и основных) механизмов в разработке лотерейного планирования является билет. Билет используется для представления доли процесса в процессоре в этих примерах, но может быть применен гораздо шире. Например, в более поздней работе по управлению виртуальной памятью для гипервизоров Waldspurger показывает, как билеты могут использоваться для представления доли памяти гостевой операционной системы. Таким образом, если вам когда-либо понадобится механизм для представления доли собственности, этим механизмом как раз может быть ... билет.
Механизмы билетов
Планирование лотереи также предоставляет ряд механизмов для манипулирования билетами различными и иногда полезными способами. Один из способов - с понятием ticket currency. Currency позволяет пользователю с набором билетов распределять билеты между своими собственными заданиями в любой валюте, которую он хотел бы; затем система автоматически преобразует указанную валюту в правильное глобальное значение.
Например, предположим, что пользователи A и B получили по 100 билетов. Пользователь A выполняет два задания, А1 и А2, и дает им по 500 билетов (из 1000 всего) в валюте A. Пользователь B выполняет только 1 задание и дает ему 10 билетов (из 10 всего). Система преобразует распределение A1 и A2 от 500 в валюте A до 50 в глобальной валюте; аналогично, 10 билетов B1 преобразуются в 100 билетов. Затем лотерея проводится в глобальной валюте билета (всего 200), чтобы определить, какое задание выполняется.
Еще один полезный механизм - передача билетов (ticket transfer). При трансферах процесс может временно передать свои билеты другому процессу. Эта способность особенно полезна в настройке клиент / сервер, когда клиентский процесс отправляет сообщение серверу с просьбой выполнить некоторую работу от имени клиента. Чтобы ускорить работу, клиент может передать билеты на сервер и таким образом попытаться максимизировать производительность сервера, пока сервер обрабатывает запрос клиента. После завершения сервер передает билеты обратно клиенту, и все остается по-прежнему.
Наконец, инфляция билетов (ticket inflation) иногда может быть полезной техникой. С инфляцией процесс может временно увеличить или уменьшить количество билетов, которыми он владеет. Конечно, в конкурентном сценарии с процессами, которые не доверяют друг другу, это имеет мало смысла; один жадный процесс может дать себе огромное количество билетов и завладеть машиной. Скорее, инфляция может быть применена в среде, где группа процессов доверяет друг другу; в таком случае, если какой-либо процесс знает, что ему нужно больше процессорного времени, он может увеличить свою стоимость билета как способ отразить эту потребность в системе, и все это без связи с другими процессами.
Реализация
Наверное, самое удивительное в планировании лотереи-это простота ее реализации. Все, что вам нужно, - это хороший генератор случайных чисел для выбора выигрышного билета, структура данных для отслеживания процессов системы (например, список) и общее количество билетов.
Предположим, что мы сохраняем процессы в списке. Вот пример, состоящий из трех процессов, A, B и C, каждый из которых имеет некоторое количество билетов.
Чтобы принять решение о расписании, мы сначала должны выбрать случайное число (победителя) из общего количества билетов (400) допустим, мы выбираем число 300. Затем мы просто проходим по списку с помощью простого счетчика, который помогает нам найти победителя (рис.9.1).
Код ходит по списку процессов, добавляя каждое значение билета в счетчик до тех пор, пока значение не превысит победителя. Как только это произойдет, текущий элемент списка станет победителем. В нашем примере с выигрышным билетом 300 происходит следующее. Во-первых, счетчик увеличивается до 100, чтобы учесть билеты задачи А; поскольку 100 меньше 300, цикл продолжается. Затем счетчик будет обновлен до 150 (билеты В), 150 всё ещё меньше 300, и таким образом мы снова продолжим. Наконец, счетчик обновляется до 400 (явно больше 300), и таким образом мы выходим из цикла с победителем записанным в current (C).
Чтобы сделать этот процесс наиболее эффективным, обычно лучше всего организовать список в отсортированном порядке, от самого большого количества билетов до самого низкого. Упорядочение не влияет на корректность алгоритма, однако в целом гарантирует, что будет выполнено наименьшее количество итераций списка, особенно если есть несколько процессов, которые обладают большей частью билетов.
Пример
Чтобы сделать динамику планирования лотереи более понятной, мы теперь проведем краткое исследование времени выполнения двух заданий, конкурирующих друг с другом, каждое с одинаковым количеством билетов (100) и одинаковым временем выполнения (R, которое мы будем варьировать).
В этом сценарии мы хотели бы, чтобы каждая работа заканчивалась примерно в одно и то же время, но из-за случайности планирования лотереи иногда одна работа заканчивается раньше другой. Чтобы количественно оценить эту разницу, мы определяем простую метрику справедливости (fairness metric), F, которая является просто временем завершения первого задания, деленным на время завершения второго задания. Например, если R = 10, а первое задание заканчивается в момент времени 10 (а второе задание - в 20), то F = 10 / 20 = 0,5. Когда оба задания закончатся почти одновременно, F будет довольно близко к 1. В этом сценарии это и есть наша цель: совершенно справедливый планировщик достигнет F = 1.
На рис. 9.2 показана средняя справедливость при изменении длины двух заданий (R) от 1 до 1000 в течение тридцати испытаний (результаты генерируются с помощью симулятора, представленного в конце главы). Как видно из графика, когда длина задания не очень велика, средняя справедливость может быть довольно низкой. Только когда задания выполняются в течение значительного числа временных срезов, планировщик лотереи приближается к желаемому справедливому результату.
Как назначить билеты?
Одна проблема, которую мы не решали с планированием лотереи, заключается в следующем: как распределить билеты по заданиям? Эта проблема является сложной, потому что, конечно, поведение системы сильно зависит от того, как распределяются билеты. Один из подходов заключается в предположении, что пользователи знают лучше; в таком случае каждому пользователю вручается некоторое количество билетов, и пользователь может распределить билеты на любые задания, которые они выполняют по своему желанию. Однако это решение не является решением: оно действительно не говорит вам, что делать. Таким образом, при заданном наборе заданий “проблема назначения билетов” остается открытой.
Планирование шага (stride scheduling)
Вы также можете задаться вопросом: зачем вообще использовать случайность? Как мы видели выше, в то время как случайность дает нам простой (и приблизительно правильный) планировщик, он иногда не дает точных правильных пропорций, особенно в коротких временных масштабах. По этой причине Waldspurger изобрел Stride scheduling, детерминированный планировщик справедливой доли.
Планирование шага также просто. Каждое задание в системе имеет шаг, который обратно пропорционален количеству билетов, которые у него есть. В приведенном выше примере с заданиями A, B и C, с 100, 50 и 250 билетами соответственно, мы можем вычислить шаг каждого из них, разделив некоторое большое число на количество билетов, назначенных каждому процессу. Например, если мы разделим 10 000 на каждое из этих значений билета, мы получим следующие значения шага для A, B и C: 100, 200 и 40. Мы называем это значение шагом (stride) каждого процесса; каждый раз, когда процесс запускается, мы будем увеличивать счетчик для него (называемый pass value) на его шаг, чтобы отслеживать его глобальный прогресс.
Затем планировщик использует шаг и проход, чтобы определить, какой процесс должен выполняться следующим. Основная идея проста: в любой момент времени выберите процесс для запуска, который имеет наименьшее значение pass value; когда вы запускаете процесс, увеличьте его pass counter на его stride. Псевдокод реализованный Waldspurger:
В нашем примере мы начинаем с трех процессов (A, B и C), со значениями шага 100, 200 и 40, и все с pass value равными 0. Таким образом, сначала может выполняться любой из процессов, так как их pass value одинаковы. Предположим, что мы выбираем A (произвольно; можно выбрать любой из процессов с равными значениями низких частот). А выполняется; когда закончилось время выполнения, мы обновляем его pass value до 100. Потом запускаем В, pass value которого устанавливается равным 200. Наконец, мы запускаем C, pass value которого увеличивается до 40. В этот момент алгоритм выберет наименьшее pass value (задача C), и запустит его, обновив свой проход до 80 (шаг C равен 40, как вы помните). Затем C будет работать снова (все еще самое низкое значение прохода), повышая свой проход до 120. Теперь A будет работать, обновляя свой пропуск до 200 (теперь он равен B). Затем C будет работать еще дважды, обновляя свой pass value до 160, а затем до 200. В этот момент все pass value снова равны, и процесс будет повторяться до бесконечности. Рисунок 9.3 прослеживает поведение планировщика с течением времени.
Как мы видим из рисунка, C запускался пять раз, А дважды, а В только один раз, точно пропорционально их значениям билетов 250, 100 и 50. Планирование лотереи достигает пропорций вероятностно с течением времени; stride-scheduling получает их точно в конце каждого цикла планирования.
Поэтому вы можете задаться вопросом: учитывая точность stride-scheduling, зачем вообще использовать планирование лотереи? Ну, у планирования лотереи есть одно приятное свойство, которого нет у планирования шага: нет глобального состояния. Представьте себе, что новое задание входит в середину нашего примера планирования шага описанного ранее; каким должно быть его pass value? Должен ли он быть установлен на 0? Если это так, то он монополизирует центральный процессор. При планировании лотереи нет глобального состояния для каждого процесса; мы просто добавляем новый процесс с любыми билетами, которые у него есть, обновляем единственную глобальную переменную, чтобы отслеживать, сколько всего билетов у нас есть, и исходим из этого. Таким образом, лотерея значительно облегчает внедрение новых процессов разумным образом.
The Linux Completely Fair Scheduler (CFS)
Несмотря на эти более ранние работы в области fair-share scheduling, нынешний подход Linux достигает аналогичных целей альтернативным способом. Планировщик, названный Completely Fair Scheduler (или CFS), реализует справедливое планирование, но делает это очень эффективным и масштабируемым способом.
Чтобы достичь своих целей в области эффективности, CFS стремится тратить очень мало времени на принятие решений о планировании, как благодаря присущему ей дизайну, так и умному использованию структур данных, хорошо подходящих для этой задачи. Недавние исследования показали, что эффективность планировщика удивительно важна; в частности, в исследовании центров обработки данных Google Канев и др. показал, что даже после агрессивной оптимизации планирование использует около 5% общего процессорного времени центра обработки данных. Таким образом, сокращение этих накладных расходов является ключевой целью современной архитектуры планировщика.
Basic Operation
В то время как большинство планировщиков основаны на концепции фиксированного временного отрезка, CFS работает немного по-другому. Его цель проста: справедливо разделить процессор поровну между всеми конкурирующими процессами. Он делает это с помощью простой техники подсчета, известной как виртуальная среда выполнения (vruntime).
По мере выполнения каждого процесса он накапливает vruntime. В самом простом случае время работы каждого процесса увеличивается с одинаковой скоростью, пропорционально физическому (Реальному) времени. При принятии решения о планировании CFS выберет процесс с наименьшим временем vruntime для следующего запуска.
Возникает вопрос: как планировщик узнает, когда остановить текущий процесс и запустить следующий? Вопрос понятен: если CFS выключается слишком часто, fairness увеличивается, как CFS будет гарантировать, что каждый процесс получает свою долю процессорного времени например уменьшая временное окно доступа, даже во вред производительности (слишком много переключений контекста); если CFS переключается реже, производительность увеличивается (уменьшается число переключений контекста), но за счет справедливости.
CFS управляет этим с помощью различных параметров. Первый - это sched latency. CFS использует это значение, чтобы определить, как долго должен работать один процесс, прежде чем рассматривать переключение (эффективно определяя время выполнения процесса динамическим способом). Типичное значение sched latency составляет 48 (миллисекунд); CFS делит это значение на число (n) процессов, запущенных на процессоре, чтобы определить временной срез для процесса, и таким образом гарантирует, что в течение этого периода времени CFS будет полностью справедливым.
Например, если запущено n = 4 процесса, CFS делит значение sched latency на n, чтобы получить временной срез для каждого процесса в 12 мс. Затем CFS планирует первое задание и запускает его до тех пор, пока не будет использовано 12 мс (виртуального) времени выполнения, а затем проверяет, есть ли задание с более низким временем выполнения vruntime для запуска вместо него. В этом случае есть, и CFS переключится на одну из трех других работ, и так далее. На рис. 9.4 показан пример, в котором четыре задания (A, B, C, D) выполняются таким образом для двух временных срезов; два из них (C, D) затем завершаются, оставляя только два оставшихся, которые затем каждый запускаются в течение 24 мс в циклическом (round-robin) режиме.
Но что делать, если запущено "слишком много" процессов? Не приведет ли это к слишком малому временному срезу и, следовательно, к слишком большому количеству переключений контекста? Хороший вопрос! И ответ - приведёт.
Чтобы решить эту проблему, CFS добавляет еще один параметр, min granularity, который обычно имеет значение 6 мс. CFS никогда не установит временной срез процесса меньше этого значения, гарантируя, что не будет потрачено слишком много времени на планирование накладных расходов.
Например, если запущено десять процессов, наш первоначальный расчет разделит sched latency на десять, чтобы определить временной срез (результат: 4,8 МС). Однако из-за минимальной детализации CFS установит временной срез каждого процесса равным 6 мс. Хотя CFS не будет совершенно справедлива по отношению к целевой задержке планирования (sched latency) в 48 МС, она будет близка к этому, все еще достигая высокой эффективности процессора.
Обратите внимание, что CFS использует периодическое прерывание таймера, что означает, что он может принимать решения только через фиксированные промежутки времени. Это прерывание срабатывает часто (например, каждые 1 мс), давая CFS возможность проснуться и определить, достигло ли текущее задание конца своего выполнения. Если задание имеет временной срез, который не является идеальным кратным интервалу прерывания таймера, это нормально; CFS точно отслеживает vruntime, что означает, что в долгосрочной перспективе он в конечном итоге приблизится к идеальному совместному использованию ЦП.
Weighting (Niceness)
CFS также позволяет контролировать приоритет процессов, позволяя пользователям или администраторам предоставлять некоторым процессам более высокую долю ЦП. Он делает это не с помощью билетов, а с помощью классического механизма UNIX, известного как nice level процесса. Параметр nice может быть установлен в значение от -20 до +19 для процесса, с значением по умолчанию 0. Положительные значения параметра nice подразумевают более низкий приоритет, а отрицательные - более высокий; когда вы слишком хороши, вы просто не получаете столько внимания (планирования), увы.
CFS сопоставляет nice value каждого процесса с весом, как показано здесь:
Эти веса позволяют нам вычислить эффективный временной срез каждого процесса (как мы делали это раньше), но теперь с учетом их различий в приоритетах. Формула, используемая для этого, выглядит следующим образом, предполагая, что N это количество процессов:
Давайте сделаем пример, чтобы увидеть, как это работает. Предположим, что есть две работы, A и B. A, потому что это наша самая ценная работа, получает более высокий приоритет, присваивая ей nice level -5; B, потому что мы её нелюбим, просто имеет приоритет по умолчанию (nice level равно 0). Это означает weight A (из таблицы) равен 3121, в то время как weight B равен 1024. Если вычислить time slice каждого задания, вы увидите, что time slice задания А примерно равен 3/4 от sched_latency (следовательно 36 мс) а В 1/4 (следовательно 12 мс).
В дополнение к обобщению расчета временного среза, способ которым CFS вычисляет vruntime также должен быть адаптирован. Вот новая формула, которая берет фактическое время выполнения, накопленное процессом i (время выполнения i), и масштабирует его обратно пропорционально весу процесса, деля вес по умолчанию 1024 (вес 0) на его вес, вес i. В нашем запущенном примере vruntime A будет накапливаться в одну треть от скорости B.
Одним из умных аспектов построения приведенной выше таблицы Весов является то, что таблица сохраняет коэффициенты пропорциональности процессора, когда разница в хороших значениях постоянна. Например, если процесс А вместо этого имеет хорошее значение 5 (не -5), а процесс В имеет хорошее значение 10 (не 0), CFS будет планировать их точно так же, как и раньше. Проведите математику сами, чтобы понять, почему.
Использование красно-чёрных деревьев
Как указывалось выше, одним из основных направлений деятельности CFS является эффективность. Для планировщика существует много аспектов эффективности, но один из них прост: когда планировщик должен найти следующее задание для запуска, он должен сделать это как можно быстрее. Простые структуры данных, такие как списки, не масштабируются: современные системы иногда состоят из 1000 процессов, и поэтому периодический поиск по длинному списку с интервалом в несколько миллисекунд является расточительным.
CFS решает эту проблему, сохраняя процессы в красно-черном дереве. Красно-черное дерево - это один из многих типов сбалансированных деревьев; в отличие от простого бинарного дерева (которое может вырождаться в листовую производительность при наихудших шаблонах вставки), сбалансированные деревья выполняют небольшую дополнительную работу по поддержанию низкой глубины и, таким образом, гарантируют, что операции логарифмичны (а не линейны) во времени.
CFS не сохраняет все процессы в этой структуре; скорее, в ней хранятся только запущенные (или управляемые) процессы. Если процесс переходит в спящий режим (например, ожидая завершения ввода-вывода или прибытия сетевого пакета), он удаляется из дерева и отслеживается в другом месте.
Давайте рассмотрим пример. Предположим, что существует десять заданий и что они имеют следующие значения времени выполнения: 1, 5, 9, 10, 14, 18, 17, 21, 22, и 24. Если бы мы сохранили эти задания в упорядоченном списке, найти следующее задание было бы просто: просто удалите первый элемент. Однако, помещая эту работу обратно в список (по порядку), мы должны были бы сканировать список, ища правильное место, чтобы вставить его, сложность такой операции O(n). Любой поиск довольно неэффективен и занимает в среднем линейное время.
Сохранение значений в красно-черное дерево делает большинство операций более эффективным, как показано на рис. 9.5. Процессы сортируются в дереве по vruntime, и большинство операций (таких как вставка и удаление) логарифмические во времени, т. е., О(log n). Когда число n исчисляется тысячами, логарифмический метод заметно эффективнее линейного.
Работы с вводом/выводом и спящими процессами
Одна из проблем с выбором наименьшего vruntime для следующего запуска возникает с заданиями, которые перешли в спящий режим в течение длительного периода времени. Представьте себе два процесса, A и B, один из которых (A) работает непрерывно, а другой (B) заснул на длительный период времени (скажем, 10 секунд). Когда B проснется, его vruntime будет на 10 секунд отставать от A, и таким образом (если мы не будем осторожны), B теперь монополизирует процессор в течение следующих 10 секунд, пока он догоняет, A фактически голодает .
CFS обрабатывает этот случай, изменяя vruntime задания, когда оно просыпается. В частности, CFS устанавливает vruntime этого задания на минимальное значение, найденное в дереве (помните, что дерево содержит только запущенные задания). Таким образом, CFS избегает голодания, но не без затрат: задания, которые спят в течение коротких периодов времени, часто никогда не получают свою справедливую долю процессора.
Другие особенности CFS
У CFS есть много других особенностей, слишком много, чтобы обсуждать их на этом этапе книги. Он включает в себя множество эвристик для повышения производительности кэша, имеет стратегии эффективной работы с несколькими процессорами (как обсуждается далее в книге), может планировать работу с большими группами процессов (вместо того, чтобы рассматривать каждый процесс как независимую сущность) и многие другие интересные функции. Читайте последние исследования, начиная с Bouron*, чтобы узнать больше.
* “The Battle of the Schedulers: FreeBSD ULE vs. Linux CFS” by J. Bouron, S. Chevalley, B. Lepers, W. Zwaenepoel, R. Gouicem, J. Lawall, G. Muller, J. Sopena. USENIX ATC ’18, July 2018, Boston, Massachusetts
СОВЕТ: ПРИ НЕОБХОДИМОСТИ ИСПОЛЬЗУЙТЕ ЭФФЕКТИВНЫЕ СТРУКТУРЫ ДАННЫХ
Во многих случаях сойдет и список. Во многих случаях этого не произойдет. Знание того, когда какую структуру данных использовать, является отличительной чертой хорошей инженерии. В случае, обсуждаемом здесь, простые списки, найденные в более ранних планировщиках, просто не работают хорошо в современных системах, особенно в сильно загруженных серверах, найденных в центрах обработки данных. Такие системы содержат тысячи активных процессов; поиск в длинном списке, чтобы найти следующее задание для запуска на каждом ядре каждые несколько миллисекунд, будет тратить драгоценные циклы процессора. Требовалась более совершенная структура, и CFS обеспечила ее, добавив отличную реализацию красно-черного дерева. В более общем плане, выбирая структуру данных для системы, которую вы строите, внимательно рассмотрите ее шаблоны доступа и частоту использования; понимая их, вы сможете реализовать правильную структуру для поставленной задачи.
Вывод
Мы ввели концепцию планирования proportional-share и кратко обсудили три подхода: lottery scheduling, stride scheduling и полностью справедливый планировщик (CFS) Linux. lottery scheduling использует случайность умным способом для достижения пропорциональной доли; stride scheduling делает это детерминистически. CFS, единственный реальный планировщик, обсуждаемый в этой главе, немного похож на взвешенный циклический алгоритм с динамическими временными срезами, но построенный для масштабирования и хорошей работы под нагрузкой; насколько нам известно, это наиболее широко используемый планировщик справедливой доли из существующих сегодня.
Ни один планировщик не является панацеей, и у планировщиков справедливого распределения есть своя справедливая доля проблем. Одна из проблем заключается в том, что такие подходы не особенно хорошо сочетаются с вводом-выводом; как упоминалось выше, задания, которые иногда выполняют ввод-вывод, могут не получить свою справедливую долю ЦП. Другая проблема заключается в том, что они оставляют открытой трудную проблему назначения билетов или приоритета, то есть откуда вы знаете, сколько билетов должно быть выделено вашему браузеру или на какое nice value установить ваш текстовый редактор? Другие планировщики общего назначения (такие как MLFQ, который мы обсуждали ранее, и другие подобные планировщики Linux) обрабатывают эти проблемы автоматически и, таким образом, могут быть более легко развернуты.
Хорошая новость заключается в том, что есть много областей, в которых эти проблемы не являются доминирующей проблемой, и пропорционально-распределенные планировщики используются с большим эффектом. Например, в виртуализированном центре обработки данных (или облаке), где вы можете назначить одну четверть циклов процессора виртуальной машине Windows, а остальные-базовой установке Linux, пропорциональное совместное использование может быть простым и эффективным. Эта идея также может быть распространена на другие ресурсы; см. Waldspurger* для получения более подробной информации о том, как пропорционально распределять память на сервере ESX VMWare
* “Memory Resource Management in VMware ESX Server” by Carl A. Waldspurger. OSDI ’02, Boston, Massachusetts.
