Последние пару лет я занимался сборкой различных планировщиков, и мне пришло в голову поделиться своим непростым опытом с коллегами.
Речь идет о двух категориях коллег.
Первые — это те, кто хочет научиться разработать собственный планировщик за 21 день.
Вторые — те, кому нужен новый планировщик вообще без СМС и регистрации, просто чтобы он работал.
Особенно хотелось бы помочь второй категории людей.
Сначала, как обычно, стоит сказать несколько общих слов.
Что такое планировщик (или, для простоты, «планировщик»)? Это компонент системы, который распределяет ресурс или ресурсы системы среди потребителей.
Совместное использование ресурсов может происходить в двух измерениях: пространстве и времени.
Планировщики чаще всего фокусируются на втором измерении.
Обычно ресурс означает процессор, диск, память и сеть.
Но, если честно, можно вылить любую виртуальную чушь.
Конец обобщениям.
Наряду со словом «планировщик» часто появляются и другие слова, вызывающие гораздо больший общественный интерес: изоляция, честность, гарантии, задержки, сроки.
Еще есть фразы: качество обслуживания (QoS), реальное время, временная защита.
Люди, как показывает практика, часто ждут от планировщиков волшебных сочетаний свойств, которых невозможно достичь одновременно — с планировщиком или без него.
Если желаемые свойства достигаются, то обычно планировщики всё равно остаются вещью непредсказуемой сами по себе и в процессе их работы список вопросов только увеличивается.
Я постараюсь приоткрыть завесу тайны об их поведении.
Но обо всем по порядку.
Миф №1. Что в этом сложного?
Для объяснения и прогнозирования поведения систем с планировщиком люди написали массу книг, а также разработали целую теорию — и даже не одну.Как минимум стоит упомянуть теорию планирования и теорию массового обслуживания (неожиданно: в русской версии это теория массового обслуживания).
Все подобные теории достаточно сложны и, честно говоря, просто обширны.
Существует целый ряд формулировок задач планирования.
зоопарк со специальным классификация .
Дело не облегчает тот факт, что большинство задач, как известно, являются NP-полными или NP-трудными.
Даже в успешных случаях, когда существует полиномиальный алгоритм поиска оптимального решения или хорошего приближения к нему, часто оказывается, что для онлайн-версии задачи (когда заранее неизвестно, какие запросы нужно обрабатывать или когда они появятся), оптимального алгоритма вообще не существует и нужно быть оракулом, чтобы отчистить всё «как надо».
Однако дела обстоят не так плохо, как может показаться.
Человечество уже многое знает о планировщиках, и некоторые из них даже работают.
Миф №2. Планировщики решают все проблемы
Прекрасной иллюстрацией непредсказуемого поведения системы с планировщиком является современный Интернет. Это система со множеством планировщиков и абсолютным отсутствием гарантий по пропускной способности и задержке, отсутствием изоляции и подобия справедливости в формате протокола TCP - который, кстати, даже сейчас, десятилетия спустя, изучается и совершенствуется, и такие улучшения могут дать значительные результаты.
Давайте вспомним TCP ББР из Google. Авторы неожиданно заявляют, что создание TCP BBR было бы невозможно без новейших достижений теории управления, основой которой является нестандартная макс-плюс-алгебра.
Оказывается, именно здесь прошло более 30 лет. Но тут дело не в планировщике, скажете вы, а в управлении потоками.
И вы будете абсолютно правы.
Дело в том, что они очень тесно связаны.
В обычных системах планировщики сталкиваются с определенным узким местом — ограниченностью ресурса.
Это логично: ресурс дефицитен и, похоже, его надо поделить справедливо.
Допустим, у вас есть такой ресурс — дорожная сеть города — и вы хотите сделать для него планировщик (условно на выезде из гаража), чтобы сократить среднее время в пути.
Итак, оказывается, что среднее время в пути можно легко рассчитать, используя Теорема Литтла : он равен отношению количества машин в системе к скорости их входа в систему.
Если уменьшить делимое, то при той же пропускной способности время в пути уменьшится.
Оказывается, чтобы избежать пробок, вам просто нужно следить за тем, чтобы на дорогах было меньше машин (ваш капитан).
Планировщик не поможет с такой задачей, если нет управления потоком.
В Интернете описанная проблема называется раздувание буфера .
Если бы я писал набор правил «построения планировщика», первое правило было бы таким: контролировать очереди, возникающие за планировщиком.
Самый распространенный способ управления размером очереди, который я вижу, — это MaxInFlight (его расширенная версия называется MaxInFlightBytes).
С этим есть проблема: дело в том, что невозможно выбрать правильный номер.
Выбор любого фиксированного числа будет гарантировать вам либо недоиспользование пропускной способности (1), либо чрезмерную буферизацию (2) и, как следствие, увеличение средней задержки, либо, если вам очень повезет, таймауты и потерю пропускной способности.
Хороший контроль потока должен поддерживать систему в точка Кляйнрока между режимами (1) и (2), максимизируя соотношение пропускной способности и задержки (см.
TCP BBR).
Миф №3. Для изоляции нужна справедливость
Существует два классических применения справедливого планирования: сетевое и процессорное.GPS Это не система позиционирования, а идеальный планировщик, который одновременно обслуживает всех своих пользователей бесконечно малыми порциями.
Этот планировщик обеспечивает максимальную и минимальную справедливость.
Реальные планировщики (WFQ, DRR, SFQ, SCFQ, WF2Q) обслуживают потребителей порциями конечного размера — пакетами, если мы говорим о сети, или временными интервалами, если мы говорим о процессоре.
Эти планировщики спроектированы так, чтобы их поведение было максимально приближено к идеальному и минимизировали лаги — разницу в объеме обслуживания, получаемого разными пользователями.
Чтобы управлять выделенной полосой пропускания, разработчик затем вводит веса пользователей и начинает говорить так, как будто они находятся в изолированных системах с меньшей пропускной способностью.
Вот в этом и кроется обман.
На самом деле никакой изоляции нет. Допустим, у нас есть процессор, который мы потенциально хотим разделить между сотней пользователей.
Допустим, Витя хороший пользователь.
Он отправляет задачи, выполнение которых занимает 10 мс, и готов подождать 1 секунду, потому что понимает, что есть еще 99 пользователей.
Однако другие могут отправлять задачи, выполнение которых иногда занимает до 1 секунды.
Предположим, что упреждение невозможно.
Тогда Вите в худшем случае придется ждать 99 секунд. Витя, скорее всего, захочет уйти из такой системы.
Так неинтересно, скажете вы.
Что это за система - без упреждения? Система должна уметь обидеть, и она будет счастлива.
Ну, допустим, если время выполнения запроса больше 10 мс, мы включим вытеснение, передадим управление следующему запросу и вообще воспользуемся лучшим известным науке честным планировщиком.
Увидит ли Витя ответ за 1 секунду, как если бы он был в изоляции? 10 мс (текущий запрос услуги) + 99*10 мс (запросы других пользователей) + 10 мс (запрос посещения) = 1010 мс.
Это максимальное время ожидания — иными словами, в такой системе дела обстоят лучше.
Витя говорит - отличная система! - и отправляет запрос на 1 мс.
И снова выполняется за 1 с (в худшем случае).
В идеально изолированной системе такой запрос выполнился бы за 100 мс, а здесь получилось в 10 раз хуже.
Мало того, что от этой секунды никуда не деться, так еще и в реальной системе обязательно возникнут другие проблемы:
- Непредсказуемо переменное количество пользователей — если их не 100, а 1000, то придется подождать 10 секунд.
- Высокая стоимость переключения контекста.
Например, если вы планируете запросы к HDD, то переключение между пользователями может подразумевать время поиска 8 мс и, как следствие, привести к максимальному ожиданию в 800 мс, уменьшению пропускной способности диска и увеличению очередей для всех пользователей.
.
- Часто такие Вити хотят сделать не одну просьбу, а посылают их много.
Запросы накапливаются в очереди перед планировщиком и ждут друг друга.
- Другой приоритетный трафик.
- Не самый лучший известный науке планировщик может вносить дополнительную задержку (поиск конкретных чисел и формул по ключевым словам сервер с задержкой ).
Миф №4. Чтобы разделить полоску по весу, нужна справедливость
Получается, что справедливость не обеспечивает реальной изоляции, но хорошо разделяет полосы.Но не тут-то было.
Правосудие в таких классических планировщиках происходит мгновенно.
Это означает, что если вы не отправите запрос в свою очередь, вы не получите ресурс, и он будет разделен между другими заинтересованными сторонами.
По прошествии длительного периода времени (например, 24 часов) может оказаться, что ресурс съеден не в той пропорции, в которой веса были присвоены потребителям.
В худшем случае потребители могут прийти в любых размерах только в те моменты, когда других потребителей нет. В результате веса и потребляемый ресурс могут вообще не быть связаны.
Это шутка, скажете вы, такого никогда не бывает. Но предположим, что у нас есть распределенная система со своим планировщиком на каждой машине.
Запросы от двух пользователей поступают на две разные машины и никогда не конкурируют за ресурс, потому что на самом деле ресурсов два.
Если вы хотите видеть на графиках прямые линии совокупного потока, вам следует использовать историческую (долгосрочную) справедливость или квоты.
Но сначала спросите себя, зачем вам это нужно.
Миф №5. Дайте мне узкий канал для приоритетного трафика
Допустим, у вас есть справедливый планировщик с весами, и вы хотите выделить 0,1% пропускной способности для некоторого служебного трафика, а оставшиеся 99,9% — для остального.В результате вы получите максимальную задержку х1000. Это явление называется связью пропускной способности и задержки.
Это прямое следствие предыдущего обсуждения.
Максимальное время задержки обратно пропорционально выделенной полосе пропускания.
Это означает, что приоритетный трафик требует других механизмов.
Миф №6. Загрузил систему на полную и начал мерить задержку
Теорема.В любой системе, загруженной более 100%, задержка ответа не ограничена выше никаким числом.
Доказательство, я надеюсь, очевидно.
Очереди будут продолжать строиться, пока что-нибудь не лопнет. Как неправильно измерить и сравнить временные характеристики систем (в том числе с планировщиком), рассказывает Гил Тене (можно смотреть или читать ).
Оставлю здесь лишь иллюстрацию: 
Миф №7. Планировщик в реальном времени может гарантировать соблюдение моих сроков
Если вам больше не нужен справедливый планировщик, вам может понадобиться планировщик, который используется в системах реального времени.Там наверное все хорошо и быстро.
Помимо прочего, корректная работа системы реального времени зависит от выполнения задач в заданные сроки.
Однако это не значит, что все происходит быстро.
Например, сроки и задачи типа «сделать и внедрить новый планировщик до начала весеннего обзора».
Более того, среднее время отклика в таких системах может быть очень близким к худшему случаю.
Отличительная особенность систем RT: они заранее проверяют график на предмет осуществимости.
«Реализуемость» здесь означает возможность уложиться в сроки всех задач, а «заранее» — это, скажем, при сборке, при настройке системы или при запуске в ней новой задачи.
Далее есть простой способ соблюсти все сроки в системе, где это принципиально возможно.
Мы говорим о планировщике реального времени.
Например, проверенный что алгоритмы EDF ( Самый ранний срок в первую очередь ) оптимальны для одного процессора.
Оптимальность означает, что если для данного набора задач существует хоть какое-то осуществимое расписание, то EDF выполнит задачи раньше установленных сроков.
Но есть условия, при которых гармоничная картина мира рушится и система перестает укладываться в сроки.
- Переполнение.
Системы Hard-RT предполагают, что мы знаем, сколько времени займет выполнение задачи в худшем случае.
Однако в неидеальном мире это не так и выполнение задачи может занять больше времени.
Если мы позволяем задаче занять больше времени, чем ожидалось, мы ставим под угрозу выполнимость других задач.
В случае с EDF возникнет эффект домино.
- Перегрузка.
Вполне возможно, что вновь пришедшая задача не укладывается в желаемые сроки.
Если мы примем его к реализации, то снова получим эффект домино.
Обычно в таких случаях система перегружена и принимаются меры по ее устранению.
Например, они отказываются выполнять новые или какие-то текущие задачи.
Другой вариант — схема с пересмотром гарантий и переносом сроков выполнения некоторых задач.
Скажем иначе: минимизируя максимальную задержку, EDF срывает сроки выполнения максимально возможного количества задач.
EDF не следует применять непосредственно в условиях перегрузки, которую, как оказывается, часто трудно предсказать и/или предотвратить.
Однако методы борьбы по-прежнему существовать .
Миф №8. Система не может быть загружена более чем на 100%
Для определения коэффициента нагрузки в системах RT используется простая периодическая модель следующего типа.Есть задачи, которые приходят раз в T я ms и требуют эксклюзивного владения ресурсом для C. я мс в худшем случае.
Тогда коэффициент загрузки определяется как запрошенное время ресурса в секунду реального времени, то есть U = C. 1 /Т 1 +… + С н /Т н .
В такой простой модели всё понятно, но как посчитать коэффициент загрузки, если у нас нет никаких периодов, а есть только текущие задачи и их сроки? Тогда коэффициент нагрузки определяется по-другому.
Текущие задачи отсортированы по срокам.
Далее, начиная с одного запроса с наименьшим сроком исполнения в наборе M, мы перебираем все запросы и добавляем их в этот набор.
M на каждом шаге содержит запросы, которые должны быть полностью выполнены к определенному моменту времени t. Делим их общую остаточную стоимость (если вдруг некоторые из них мы уже частично достроили) на оставшееся время t – сейчас.
Полученное значение и есть коэффициент загрузки U множества М.
Для получения текущего коэффициента загрузки остается лишь найти максимум из всех полученных U. Найденное значение, как нетрудно догадаться, сильно меняется во времени и легко может оказываются больше 1. Расписание невозможно использовать с использованием EDF тогда и только тогда, когда коэффициент загрузки > 1. 
Если для вас важно соблюдение сроков, то метрикой, которую следует отслеживать, должен быть коэффициент загрузки, описанный выше, а не традиционное использование (процент времени, в течение которого система находилась в состоянии занятости).
Миф №9. Честный планировщик реального времени
В системах реального времени существует термин временная защита.Он используется для описания ситуации, когда никакое поведение пользователя не может поставить под угрозу выполнимость сроков транзакций других пользователей.
По сути, за этими словами скрывается простой факт: когда выполнение задачи занимает больше времени, чем мы ожидали, нам необходимо остановить ее выполнение.
Для реализации этой идеи существует набор механизмов, обходящих все костыли, игнорируемые планировщиками не реального времени.
В итоге задача сводится к резервированию полосы пропускания парой чисел (Q, P), где Q — бюджет потребителя (мс), а P — период пополнения бюджета (мс).
Вывод простой: потребитель получит Q/P ресурса.
Далее теория гарантирует, что задачи размером не более Q мс, поступающие не чаще одного раза в P мс, выполняются в течение срока P мс — при условии отсутствия перегрузки (переподписки).
То есть, К 1 /П 1 +… +Q н /П н < 1. Great theory. There are even different ways to reclaim an unused resource. Но Витю не остановить.
Он даже приходит на такую систему и с таким же желанием получить свои 10 мс по запросу.
Помимо Вити, в системе еще 99 пользователей.
Это значит, что мы должны зарезервировать за Вити 1% полосы, то есть Q/P = 1/100. Требуя, чтобы значение Q было не менее 10 мс, мы обеспечим выполнение запроса за один период. Предположим, Q = 10 мс.
Тогда P = Q/(1/100) = 100Q = 1 с.
Это гарантия нашего планировщика.
Конечно, 1000 мс — результат лучше, чем 1010 мс, но ненамного.
Но если Витя придет с желанием получить 1 мс, мы гарантированно сможем дать ему ответ за 100 мс.
У такого планировщика нет минимального кванта, и он будет переключать контекст минимально необходимое количество раз — что, кстати, очень важно для дисков.
Когда никто не требует ответов в очень короткие промежутки времени, диск начинает автоматически пакетировать самые большие фрагменты данных, и пропускная способность увеличивается.
Есть еще одно важное отличие между схемой резервирования и обычной схемой справедливого планировщика.
Он заключается в том, что мы можем более точно предсказать, когда закончится выполнение поступившего в систему запроса, и использовать эти знания в других частях системы.
Таким образом, справедливый планировщик реального времени имеет несколько полезных свойств по сравнению с обычным справедливым планировщиком (таких как предсказуемость, минимальные накладные расходы, большая гибкость), но они не включают в себя резкое улучшение времени отклика в худшем случае.
Теги: #Анализ и проектирование систем #реального времени #планировщик #справедливость #планирование #задержка планирования #планировщик #планировщик задач
-
Уничтожение Файлов И Очистка Диска
19 Oct, 24 -
Оптическая Изомеризма
19 Oct, 24 -
Как Развлекаются Авиаторы?
19 Oct, 24 -
Визуализация Связей Между Веб-Ресурсами
19 Oct, 24
