Планировщик траха мозга

Планировщик траха мозга
Разработчик(и)	С Коливасом
Финальный выпуск	0,512 / 3 октября 2016 г .; 7 лет назад
Написано в	С
Операционная система	Линукс
Лицензия	GNU GPL
Веб-сайт	ядро .коливас .org

Планировщик Brain Fuck Scheduler ( BFS ) — это планировщик процессов, разработанный для ядра Linux в августе 2009 года на основе самого раннего подходящего планирования виртуального крайнего срока (EEVDF), ^{[ 2 ]} в качестве альтернативы планировщику Completely Fair (CFS) и планировщику O(1) . ^{[ 3 ]} BFS был создан Коном Коливасом . ^{[ 4 ]}

Цель BFS, по сравнению с другими планировщиками, — предоставить планировщику более простой алгоритм , который не требует корректировки эвристики или параметров настройки для адаптации производительности к конкретному типу вычислительной нагрузки. Коливас утверждал, что эти настраиваемые параметры трудно понять обычному пользователю, особенно с точки зрения взаимодействия нескольких параметров друг с другом, и утверждал, что использование таких настраиваемых параметров часто может привести к повышению производительности в конкретном целевом типе вычислений. ценой ухудшения производительности в общем случае. ^{[ 4 ]} Сообщается, что BFS улучшает быстродействие настольных компьютеров Linux с числом ядер менее 16 . ^{[ 5 ]}

Вскоре после своего появления новый планировщик попал в заголовки новостей в сообществе Linux, появившись на Slashdot и получив обзоры в Linux Magazine и Linux Pro Magazine . ^{[ 3 ]}^{[ 6 ]}^{[ 7 ]} Хотя были различные отзывы об улучшении производительности и отзывчивости, Кон Коливас не намеревался интегрировать BFS в основное ядро. ^{[ 4 ]}

Теоретический дизайн и эффективность

В 2009 году был представлен BFS, который первоначально использовал структуру данных двусвязного списка . ^{[ 8 ]}^{[ 9 ]} но структура данных рассматривается как очередь . Вставка задачи ⁠ $O(1)$ ⁠ . ^{[ 9 ]}^{: пер. 119–120} Поиск следующей задачи для выполнения: ⁠ $O(n)$ ⁠ худший случай. ^{[ 9 ]}^{: пер. 209} Он использует единую глобальную очередь выполнения , которую используют все процессоры. Задачи с более высоким приоритетом планирования выполняются первыми. ^{[ 9 ]}^{: пер. 4146–4161} Задачи упорядочиваются (или распределяются) и выбираются на основе формулы виртуального срока во всех политиках, за исключением классов приоритета реального времени и изохронного режима.

Поведение выполнения по-прежнему является взвешенным вариантом планировщика циклического перебора, особенно когда задачи имеют тот же приоритет, что и политика изохронности. ^{[ 9 ]}^{: пер. 1193–1195, 334–335.} Настраиваемый пользователем интервал циклического перебора ( квант времени ) по умолчанию составляет 6 миллисекунд, что было выбрано как минимальный джиттер , чуть ниже уровня обнаружения человеком. ^{[ 9 ]}^{: пер. 306} Коливас утверждал, что все, что меньше 6 мс, бессмысленно, а все, что больше 300 мс для циклического интервала времени, бесполезно с точки зрения пропускной способности. ^{[ 9 ]}^{: пер. 314–320} Этот важный параметр позволяет настроить планировщик циклического перебора как компромисс между пропускной способностью и задержкой. ^{[ 9 ]}^{: пер. 229–320} Все задачи получают одинаковый интервал времени, за исключением FIFO реального времени, который, как предполагается, имеет бесконечный интервал времени. ^{[ 9 ]}^{: 1646, 1212–1218, 4062, 3910 гг.}

Коливас объяснил причину, по которой он решил использовать моноочередь с двусвязным списком, а не многоранговую очередь (циклический перебор). ^{[ 10 ]}^{: о 3}) массив приоритетов ^{[ 11 ]}^{[ 10 ]} на каждый процессор, который использовался в его планировщике RDSL, должен был облегчить справедливость в сценарии с несколькими процессорами и устранить сложность, из-за которой каждая очередь выполнения в сценарии с несколькими очередями должна была поддерживать свои собственные задержки и справедливость [задачи]. ^{[ 9 ]}^{: пер. 81–92.} Он утверждал, что детерминированные задержки были гарантированы с помощью BFS в его более поздней версии MuQSS. ^{[ 12 ]}^{: пер. 471–472.} Он также признал возможную проблему конфликта блокировок (связанную с изменением, удалением и созданием данных узла задачи). ^{[ 12 ]}^{: пер. 126–144.} с увеличением процессоров и накладными расходами ⁠ $O(\log n)$ ⁠ следующая задача для поиска выполнения. ^{[ 12 ]}^{: пер. 472–478.} MuQSS попыталась решить эти проблемы.

Позже Коливас изменил дизайн на список пропуска в версии BFS v0.480 в 2016 году. ^{[ 13 ]} На этот раз это изменило эффективность планировщика. Он отметил ⁠ $O(\log n)$ ⁠ вставка задачи, ⁠ $O(1)$ ⁠ поиск задач; ⁠ $O(k)$ ⁠ , с ⁠ $k\leq 16$ ⁠ , для удаления задачи. ^{[ 13 ]}^{: пер. 4}

Виртуальный дедлайн

Формула виртуального крайнего срока представляет собой будущий крайний срок, который представляет собой масштабированный временной интервал циклического алгоритма, основанный на смещении хорошего уровня на текущее время (в минимальных единицах или наносекундных джиффи , внутреннем счетчике времени ядра). ^{[ 9 ]}^{: пер. 4023, 4063} Виртуальный срок только предполагает порядок, но не гарантирует, что задача будет выполнена точно в запланированный на будущее момент. ^{[ 9 ]}^{: пер. 161–163.}

Сначала создается таблица поиска коэффициентов prio. ^{[ 9 ]}^{: пер. 8042–8044} Он основан на рекурсивной последовательности. Он увеличивается на 10% за каждый хороший уровень. ^{[ 9 ]}^{: пер. 161} На графике это следует параболическому шаблону, а упорядоченные задачи распределяются как скользящая квадратичная функция от 0 до 39 (соответствует от самого высокого до самого низкого приоритета приятности) в качестве домена и от 128 до 5089 в качестве диапазона. ^{[ 9 ]}^{: пер. 177–179, 120, 184–185.} Движущаяся часть происходит от t в формуле виртуального срока, на которую намекнул Коливас.

g(0) = 128
g(i) = INT( g(i-1)*11/10 )

Индекс	Числитель
0	128
1	140
2	154
3	169
4	185
5	203
6	223
7	245
8	269
9	295
10	324
11	356
12	391
13	430
14	473
15	520
16	572
17	629
18	691
19	760
20	836
21	919
22	1010
23	1111
24	1222
25	1344
26	1478
27	1625
28	1787
29	1965
30	2161
31	2377
32	2614
33	2875
34	3162
35	3478
36	3825
37	4207
38	4627
39	5089

-to-index" задачи "nice Функция сопоставления f(n) преобразуется из значения nice -20...19 в индекс 0...39, который будет использоваться в качестве входных данных для таблицы поиска соотношения prio. Эта функция отображения является TASK_USER_PRIO() макрос в sched.h в заголовке ядра. Внутренняя реализация ядра немного отличается от статического приоритета в диапазоне от 100 до 140, но пользователи увидят его как -20...19.

Хороший	Индекс
−20	0
−19	1
−18	2
−17	3
−16	4
−15	5
−14	6
−13	7
−12	8
−11	9
−10	10
−9	11
−8	12
−7	13
−6	14
−5	15
−4	16
−3	17
−2	18
−1	19
0	20
1	21
2	22
3	23
4	24
5	25
6	26
7	27
8	28
9	29
10	30
11	31
12	32
13	33
14	34
15	35
16	36
17	37
18	38
19	39

Виртуальный срок основан на этой точной формуле: ^{[ 9 ]}^{: пер. 4063, 4036, 4033, 1180}

T = 6
N = 1<<20
d(n,t) = t + g(f(n)) * T * (N/128)

Альтернативно,

{\mathtt {d(n,t)={\frac {g(f(n))}{128}}*T*N+t}}

^{[ 14 ]}

где d(n,t) — виртуальный крайний срок в целочисленных наносекундах u64 как функция nice н и t — текущее время в niffies, g(i) — поиск таблицы соотношений prio как функция индекса, f(n) — функция сопоставления приятного индекса задачи, T — временной интервал циклического алгоритма в миллисекундах, N — константа, равная 1 миллисекунде в наносекундах, как аппроксимация коэффициента преобразования, уменьшающая задержку. $\mathrm {\frac {10^{9}ns}{10^{3}ms}}$ но Коливас использует константу по основанию 2 N примерно с таким масштабом. ^{[ 9 ]}^{: пер. 1173–1174 гг.} Меньшие значения d означает, что виртуальный крайний срок ранее соответствует отрицательным значениям nice. Большие значения d указывает, что виртуальный крайний срок переносится на более позднее время, что соответствует положительным значениям nice. Он использует эту формулу всякий раз, когда истекает интервал времени. ^{[ 9 ]}^{: пер. 5087}

128 по основанию 2 соответствует 100 по основанию 10 и, возможно, «псевдо100». ^{[ 9 ]}^{: пер. 3415} 115 по основанию 2 соответствует 90 по основанию 10. Коливас использует 128 для «быстрых смен », ^{[ 9 ]}^{: пер. 3846, 1648, 3525.} как и в делении, сдвигается вправо по основанию 2.

Хороший	Виртуальный срок в интервалах времени относительно т	Виртуальный срок в точных секундах относительно т
−20	1.0	0.006
−19	1.09	0.006562
−18	1.2	0.007219
−17	1.3	0.007922
−16	1.4	0.008672
−15	1.5	0.009516
−14	1.7	0.010453
−13	1.9	0.011484
−12	2.1	0.012609
−11	2.3	0.013828
−10	2.5	0.015187
−9	2.7	0.016688
−8	3.0	0.018328
−7	3.3	0.020156
−6	3.6	0.022172
−5	4.0	0.024375
−4	4.4	0.026812
−3	4.9	0.029484
−2	5.3	0.032391
−1	5.9	0.035625
0	6.5	0.039188
1	7.1	0.043078
2	7.8	0.047344
3	8.6	0.052078
4	9.5	0.057281
5	10.5	0.063000
6	11.5	0.069281
7	12.6	0.076172
8	13.9	0.083766
9	15.3	0.092109
10	16.8	0.101297
11	18.5	0.111422
12	20.4	0.122531
13	22.4	0.134766
14	24.7	0.148219
15	27.1	0.163031
16	29.8	0.179297
17	32.8	0.197203
18	36.1	0.216891
19	39.7	0.238547

Политики планирования

BFS использует политики планирования, чтобы определить, сколько задач ЦП может использовать. BFS использует 4 уровня планирования (называемых политиками планирования или классами планирования), упорядоченными от лучшего к худшему, что определяет способ выбора задач. ^{[ 9 ]}^{: пер. 4146–4161} причем те, что сверху, выполняются первыми.

Каждая задача имеет особое значение, называемое prio. В версии v0.462 (используемой в наборе исправлений ядра -ck 4.0) всего имеется 103 «очереди приоритетов» (также известные как prio) или разрешенные значения, которые она может принимать. В качестве приоритетной очереди не использовалась никакая специальная структура данных, а только сама очередь выполнения двусвязного списка. Более низкое значение prio означает, что оно более важно и выполняется первым.

Политика реального времени

Политика реального времени была разработана для задач реального времени . Эта политика подразумевает, что выполняемые задачи не могут быть прерваны (т. е. вытеснены) задачей с более низким приоритетом или уровнями политики с более низким приоритетом. Классы приоритета, рассматриваемые планировщиком в соответствии с политикой реального времени, — это те, которые отмечены SCHED_RR и SCHED_FIFO. ^{[ 9 ]}^{: пер. 351, 1150 г.} Планировщик по-разному обрабатывает циклический перебор в реальном времени (SCHED_RR) и FIFO в реальном времени (SCHED_FIFO). ^{[ 9 ]}^{: пер. 3881–3934.}

В проекте заложены первые 100 очередей со статическими приоритетами. ^{[ 9 ]}^{: пер. 189}

Задача, которая будет выбрана для выполнения, зависит от наличия задачи с наименьшим значением prio из 100 очередей и планирования FIFO. ^{[ 9 ]}^{: пер. 4146–4161}

В форках приоритет процесса будет понижен до обычной политики. ^{[ 9 ]}^{: пер. 2708}

При непривилегированном использовании (т. е. пользователем без полномочий root) sched_setscheduler, вызываемого с запросом класса политики реального времени, планировщик понизит задачу до изохронной политики. ^{[ 9 ]}^{: пер. 350–359, 5023–5025.}

Изохронная политика

Политика Isochronous была разработана для обеспечения производительности, близкой к реальному времени, для без полномочий root . пользователей ^{[ 9 ]}^{: пер. 325}

В проекте предусмотрена одна очередь приоритетов, которая по умолчанию выполняется как задачи псевдореального времени, но может быть настроена как задача реального времени. ^{[ 9 ]}^{: Ин 1201, 346–348.}

Поведение политики может позволить задачу можно понизить до обычной политики. ^{[ 9 ]}^{: пер. 336} когда он превышает настраиваемый процент обработки ресурсов (по умолчанию 70%). ^{[ 9 ]}^{: пер. 343, 432}) на 5 секунд, масштабируемый по количеству подключенных процессоров и разрешению таймера плюс 1 такт. ^{[ 9 ]}^{: Ин 343, 3844–3859, 1167, 338.}^{[ 12 ]}^{: 1678 г., 4770–4783, 734 гг.} Формула была изменена в MuQSS из-за конструкции нескольких очередей. Точные формулы:

{\mathtt {T_{BFS}=((5*F*n)+1)*R}}

{\mathtt {T_{MuQSS}=(5*F)*R}}

где T — общее количество изохронных тиков, F – частота таймера, n — количество подключенных процессоров, R — это настраиваемый процент обработки ресурсов, не выраженный в десятичном виде, а в виде целого числа. По умолчанию частота таймера установлена на 250 и может быть изменена в ядре, но обычно настраивается на 100 Гц для серверов и 1000 Гц для интерактивных рабочих столов. 250 — сбалансированное значение. Параметр От R до 100 задачи выполнялись как в реальном времени, а при значении 0 — не в псевдо-реальном времени, а все, что посередине, было в псевдо-реальном времени. ^{[ 9 ]}^{: пер. 346–348.}

Для выполнения была выбрана задача, у которой был самый ранний виртуальный крайний срок, но когда существует несколько изохронных задач, они планируются как циклический, что позволяет задачам запускать настраиваемое значение циклического перебора (с 6 мс по умолчанию) одну за другой в справедливом режиме. равные шансы без учета хорошего уровня. ^{[ 9 ]}^{: пер. 334}

Такое поведение изохронной политики уникально только для BFS и MuQSS и не может быть реализовано в других планировщиках ЦП. ^{[ 9 ]}^{: пер. 324, 8484–8485.}^{[ 12 ]}^{: 1287–1288 гг.}

Нормальная политика

Обычная политика была разработана для регулярного использования и является политикой по умолчанию. Вновь созданные задачи обычно помечаются как обычные. ^{[ 9 ]}^{: пер. 502}

В проекте предусмотрена одна приоритетная очередь, и задачи выбираются для выполнения в первую очередь на основе самого раннего виртуального срока.

Политика приоритета простоя

Приоритет простоя был разработан для фоновых процессов, таких как распределенные программы и транскодеры, чтобы процессы переднего плана или процессы, находящиеся выше этой политики планирования, могли работать бесперебойно. ^{[ 9 ]}^{: пер. 363–368}

В конструкции предусмотрена 1 приоритетная очередь, и задачи могут быть автоматически повышены до обычной политики, чтобы предотвратить бессрочное удержание ресурсов . ^{[ 9 ]}^{: пер. 368}

Следующая выполненная задача с приоритетом простоя, а также другие задачи, находящиеся в той же политике приоритетов, выбирается по самому раннему виртуальному крайнему сроку. ^{[ 9 ]}^{: пер. 4160–4161}

Упреждение

Вытеснение может произойти, когда новая готовая задача с политикой более высокого приоритета (т. е. с более высоким приоритетом) имеет более ранний виртуальный крайний срок, чем выполняющаяся в данный момент задача, которая будет исключена из расписания и помещена в конец очереди. ^{[ 9 ]}^{: пер. 169–175.} Отменено означает, что его виртуальный срок обновлен. ^{[ 9 ]}^{: пер. 165–166.} Время задачи восполняется до максимального такта циклического перебора, когда оно израсходовало все свое время. ^{[ 9 ]}^{: пер. 4057–4062, 5856} Если планировщик обнаружил задачу с более высоким приоритетом и самым ранним виртуальным крайним сроком, она будет выполняться вместо менее важной, выполняющейся в данный момент задачи, только если все логические процессоры (включая ядра с гиперпоточностью / потоки SMT) заняты. Планировщик будет откладывать вытеснение как можно дольше, если есть неиспользуемые логические процессоры.

Если задача отмечена политикой приоритета простоя, она вообще не может вытеснять даже другие задачи, отмеченные политикой простоя, а вместо этого использует совместную многозадачность . ^{[ 9 ]}^{: 2341–2344 гг.}

Размещение задач, несколько ядер

Когда планировщик обнаруживает задачу пробуждения в системе, отличной от Unicore, ему необходимо определить, на каком логическом процессоре выполнить задачу. Планировщик отдает предпочтение большинству простаивающих ядер с гиперпоточностью (или простаивающих потоков SMT ) сначала на том же процессоре, на котором выполнялась задача. ^{[ 9 ]}^{: пер. 261} затем другое простаивающее ядро многоядерного процессора, ^{[ 9 ]}^{: пер. 262} затем другие процессоры на том же узле NUMA, ^{[ 9 ]}^{: пер. 267, 263–266, 255–258.} затем все занятые гиперпоточные ядра/потоки SMT/логические процессоры должны быть выгружены на одном узле NUMA , ^{[ 9 ]}^{: пер. 265–267} затем другой (удаленный) узел NUMA ^{[ 9 ]}^{: пер. 268–270} и ранжируется в списке предпочтений. ^{[ 9 ]}^{: пер. 255–274} Это специальное сканирование предназначено для минимизации задержек, возникающих в результате миграции задачи. ^{[ 9 ]}^{: пер. 245, 268–272.}

Порядок преимущественного права аналогичен предыдущему пункту. Порядок вытеснения: сначала гиперпоточное ядро/модули SMT на одном и том же многоядерном процессоре, затем другое ядро в многоядерном процессоре, а затем другой ЦП на том же узле NUMA. ^{[ 9 ]}^{: пер. 265–267} Когда он сканирует задачу для вытеснения на другом удаленном узле NUMA, вытеснением являются только любые занятые потоки с виртуальным крайним сроком от меньшего до равного или более позднего, предполагая, что все логические процессоры (включая потоки Hyper-Threaded Core / SMT) на машине все занятый. ^{[ 9 ]}^{: пер. 270} Планировщику придется искать подходящую задачу с более низким или, возможно, равным приоритетом политики (при необходимости с более поздним виртуальным крайним сроком), чтобы вытеснить и избежать логических ЦП с задачей с политикой с более высоким приоритетом, которую он не может вытеснить. Локальное вытеснение имеет более высокий ранг, чем сканирование удаленного простаивающего модуля NUMA. ^{[ 9 ]}^{: пер. 265–269.}

Когда задача принудительно вытесняется в момент замедления ЦП в результате масштабирования частоты ЦП, опосредованного ядром (так называемого регулятора частоты ЦП), задача специально помечается как «прикрепленная», за исключением тех, которые помечены как политика реального времени. ^{[ 9 ]}^{: 2085 год} Помеченный значок «липкий» означает, что задача все еще имеет неиспользованное время и ее выполнение ограничено тем же процессором. ^{[ 9 ]}^{: пер. 233–243} Задача будет помечена как закрепленная всякий раз, когда регулятор масштабирования ЦП масштабирует ЦП на более низкой скорости. ^{[ 9 ]}^{: 2082–2107, 8840–8848.} Прикрепленная задача в режиме ожидания либо случайно вернется к выполнению на полной частоте ГГц, либо будет перепланирована для выполнения на лучшем простаивающем процессоре, который не является тем же процессором, на котором выполнялась задача. ^{[ 9 ]}^{: 2082–2086, 239–242, 2068–2079.} Нежелательно переносить задачу в другие места, а вместо этого переводить ее в режим ожидания из-за увеличения задержки, вызванной накладными расходами при переносе задачи на другой узел ЦП или NUMA. ^{[ 9 ]}^{: пер. 228, 245} Эта липкая функция была удалена в последней версии BFS (v0.512), соответствующей набору обновлений Kolivas 4.8-ck1, и не существовала в MuQSS.

планировщик

Привилегированный пользователь может изменить политику приоритетов процесса с помощью программы schedtool. ^{[ 9 ]}^{: пер. 326, 373} или это делается самой программой. ^{[ 9 ]}^{: пер. 336} Классом приоритета можно управлять на уровне кода с помощью системного вызова, такого как sched_setscheduler, доступного только пользователю root. ^{[ 15 ]} какой schedtool использует. ^{[ 16 ]}

Тесты

В современном исследовании ^{[ 5 ]} автор сравнил BFS с CFS, используя ядро Linux v3.6.2 и несколько конечных точек, основанных на производительности. Целью данного исследования было оценить Completely Fair Scheduler (CFS) в стандартном ядре Linux и BFS в соответствующем ядре, исправленном с помощью набора исправлений ck1. Было использовано семь разных машин, чтобы увидеть, существуют ли различия и в какой степени они масштабируются с использованием показателей, основанных на производительности. Количество логических процессоров варьировалось от 1 до 16. Эти конечные точки никогда не входили в число основных целей проектирования BFS. Результаты были обнадеживающими.

Ядра, исправленные с помощью набора патчей ck1, включая BFS, превзошли по производительности стандартное ядро с использованием CFS почти во всех протестированных тестах производительности. ^{[ 5 ]} Можно было бы провести дальнейшее исследование с более крупным тестовым набором, но на основе небольшого тестового набора из 7 оцененных компьютеров такое увеличение очереди процессов, эффективности/скорости в целом не зависит от типа ЦП (моно, двойной, четырехпоточный, гиперпоточный). и т. д.), архитектуру ЦП (32- и 64-разрядные версии) и кратность ЦП (моно- или двухсокетный).

Более того, на нескольких «современных» процессорах, таких как Intel Core 2 Duo и Core i7 , которые представляют собой обычные рабочие станции и ноутбуки, BFS стабильно превосходил CFS в ванильном ядре во всех тестах. Прирост эффективности и скорости был от небольшого до умеренного.

Принятие

BFS является планировщиком по умолчанию для следующих дистрибутивов Linux для настольных компьютеров:

Кроме того, BFS был добавлен в экспериментальную ветку репозитория разработки Google для Android . ^{[ 21 ]} Он не был включен в выпуск Froyo после того, как слепое тестирование не показало улучшения пользовательского опыта. ^{[ 22 ]}

МуQSS

BFS был упразднен в пользу MuQSS , формально известного как планировщик списков пропуска нескольких очередей , переписанной реализации той же концепции. ^{[ 23 ]}^{[ 24 ]} Основной автор отказался ^{[ 25 ]} работа над MuQSS к концу августа 2021 года.

Теоретический дизайн и эффективность

MuQSS использует двунаправленный статический массив из 8 уровней пропуска , а задачи упорядочиваются по статическому приоритету [очередям] (ссылаясь на политику планирования) и виртуальному сроку выполнения. ^{[ 12 ]}^{: пер. 519, 525, 537, 588, 608} 8 был выбран для соответствия массиву в строке кэша. ^{[ 12 ]}^{: пер. 523} Для ускорения удаления задач была выбрана двусвязная структура данных. Удаление задачи занимает всего O(1) со списком двойного пропуска по сравнению с оригинальным дизайном Уильяма Пью, который требует ⁠ $O(n)$ ⁠ худший случай. ^{[ 12 ]}^{: пер. 458}

Вставка задачи ⁠ $O(\log n)$ ⁠ . ^{[ 12 ]}^{: пер. 458} Следующая задача для поиска выполнения — ⁠ $O(k)$ ⁠ , где $k$ — количество процессоров. ^{[ 12 ]}^{: пер. 589–590, 603, 5125.} Следующее задание для выполнения — ⁠ $O(1)$ ⁠ через очередь выполнения, ^{[ 12 ]}^{: пер. 5124} но планировщик проверяет все остальные очереди выполнения, чтобы обеспечить справедливость задач между ЦП, задержку или балансировку (чтобы максимизировать загрузку ЦП и согласованность кэша на одном и том же узле NUMA по сравнению с теми, которые обращаются к другим узлам NUMA), поэтому в конечном итоге ⁠ $O(k)$ ⁠ . ^{[ 12 ]}^{: пер. 591–593, 497–501, 633–656.} Максимальное количество задач, которые он может обрабатывать, составляет 64 тыс. задач на очередь выполнения на процессор. ^{[ 12 ]}^{: пер. 521} В некоторых конфигурациях он использует несколько очередей выполнения задач, по одной на каждый ЦП, тогда как его предшественник BFS использовал только одну очередь выполнения задач для всех ЦП.

Задачи в списке пропуска упорядочены по градиенту таким образом, что приоритет политики реального времени стоит на первом месте, а приоритет политики простоя — на последнем. ^{[ 12 ]}^{: 2356–2358 гг.} Нормальные и неактивные политики приоритетов по-прежнему сортируются по виртуальному крайнему сроку, который использует приятные значения. ^{[ 12 ]}^{: пер. 2353} Задачи политики реального времени и изохронной политики выполняются в порядке FIFO , игнорируя хорошие значения. ^{[ 12 ]}^{: 2350–2351 гг.} Новые задачи с тем же ключом размещаются в порядке FIFO, что означает, что новые задачи помещаются в конец списка (т. е. самый верхний узел по вертикали), а задачи на 0-м уровне или в начале-внизу начинают выполняться первыми, прежде чем те, которые находятся ближе всего к верхние вертикально и те, которые находятся дальше всего от головного узла. ^{[ 12 ]}^{: пер. 2351–2352, 590 г.} Ключом, используемым для вставленной сортировки, является либо статический приоритет ^{[ 12 ]}^{: пер. 2345, 2365,} или виртуальный срок. ^{[ 12 ]}^{: пер. 2363}

Пользователь может разделить очереди выполнения между многоядерными процессорами или создать очередь выполнения для каждого логического процессора. ^{[ 12 ]}^{: пер. 947–1006.} Предполагалось, что совместное использование очередей выполнения позволит уменьшить задержку за счет снижения пропускной способности. ^{[ 12 ]}^{: пер. 947–1006.}

Новое поведение, представленное MuQSS, заключалось в использовании таймера высокого разрешения с точностью ниже миллисекунды, когда временные интервалы были израсходованы, что приводило к перепланированию задач. ^{[ 12 ]}^{: пер. 618–630, 3829–3851, 3854–3865, 5316.}

См. также

Справедливое планирование

Ссылки

^ "-ck взлом: BFS версии 0.512, linux-4.8-ck1, MuQSS для linux-4.8" . ck-hack.blogspot.com . 03.10.2016 . Проверено 10 ноября 2016 г.
^ «Планировщик ЦП MuQSS [LWN.net]» . LWN.net .
^ Перейти обратно: ^а ^б «Con Kolivas представляет новый планировщик BFS » Журнал Linux» . Linuxpromagazine.com. 2 сентября 2009 г. Проверено 30 октября 2013 г.
^ Перейти обратно: ^а ^б ^с «Часто задаваемые вопросы о BFS v0.330» . Ck.kolivas.org . Проверено 30 октября 2013 г.
^ Перейти обратно: ^а ^б ^с «Сравнение планировщиков ЦП» (PDF) . Repo-ck.com . Проверено 30 октября 2013 г.
^ «Con Kolivas возвращается с планировщиком Linux, ориентированным на настольные компьютеры» . Слэшдот. 6 сентября 2009 года . Проверено 30 октября 2013 г.
^ «Инго Молнар тестирует новый планировщик BF» . Журнал Линукс. 08.09.2009 . Проверено 30 октября 2013 г.
^ "sched-bfs-001.patch" . Кон Коливас. 13 августа 2009 г. Проверено 9 октября 2020 г.
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с ^т ^в ^v ^В ^х ^и ^С ^аа ^аб ^и ^{объявление} ^но ^из ^в ^ах ^есть ^также ^и ^аль ^{являюсь} ^а ^к ^ап ^ак ^с ^как ^в ^В ^из ^хорошо ^топор ^{является} ^тот ^нет ^бб ^{до нашей эры} ^др. ^быть ^парень ^бг ^чб «4.0-sched-bfs-462.patch» . Кон Коливас. 16 апреля 2015 г. Проверено 29 января 2019 г.
^ Перейти обратно: ^а ^б «Планировщик сроков для вращающейся лестницы» . корбет. 6 марта 2007 г. Проверено 30 января 2019 г.
^ "sched-rsdl-0.26.patch" . Кон Коливас. Архивировано из оригинала 26 июля 2011 г. Проверено 30 января 2019 г.
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с ^т ^в ^v «0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch» . Кон Коливас. 27 августа 2018 г. Проверено 29 января 2019 г.
^ Перейти обратно: ^а ^б "4.7-sched-bfs-480.patch" . Кон Коливас. 2016-09-02 . Проверено 9 октября 2020 г.
^ Альтернативная формула представлена для простоты понимания. Вся математика выполняется в целочисленной математике, поэтому потеря точности будет большой. Возможно, именно поэтому Коливас отложил деление на 128 до одного из самых больших чисел, кратного 128, в результате которого не было остатка.
^ «Планировщик Linux» . Моше Бар. 01 апреля 2000 г. Проверено 29 января 2019 г.
^ "schedtool.c" . фрик. 17 июля 2017 г. Проверено 30 января 2019 г.
^ «Sabayon 7 приносит Linux-рай» . Остатик.com . Проверено 30 октября 2013 г.
^ «Издание 2010 года теперь доступно для загрузки» . PCLinuxOS. 22 октября 2013 г. Проверено 30 октября 2013 г.
^ «Zenwalk 6.4 готов! - Релизы - Новости» . Zenwalk.org. Архивировано из оригинала 23 октября 2013 г. Проверено 30 октября 2013 г.
^ «О GalliumOS — GalliumOS Wiki» . wiki.galliumos.org . Проверено 8 июня 2018 г.
^ [1] Архивировано 22 сентября 2009 г., в Wayback Machine.
^ «CyanogenMod 5 для G1/ADP1» . Lwn.net . Проверено 30 октября 2013 г.
^ «ck-hacking: linux-4.8-ck2, MuQSS версия 0.114» . ck-hack.blogspot.com . 21 октября 2016 г. Проверено 10 ноября 2016 г.
^ «Con Kolivas объявляет о выпуске первого основного выпуска MuQSS, преемника BFS — Phoronix» .
^ «5.14 и будущее MuQSS и еще раз -ck» . ck-hack.blogspot.com . 31 августа 2021 г. Проверено 20 сентября 2022 г.

Внешние ссылки

Часто задаваемые вопросы по планировщику Brain Fuck

[1] "-ck взлом: BFS версии 0.512, linux-4.8-ck1, MuQSS для linux-4.8" . ck-hack.blogspot.com . 03.10.2016 . Проверено 10 ноября 2016 г.

[2] «Планировщик ЦП MuQSS [LWN.net]» . LWN.net .

[Linux_Pro_Magazine_on_BFS-3] Перейти обратно: ^а ^б «Con Kolivas представляет новый планировщик BFS » Журнал Linux» . Linuxpromagazine.com. 2 сентября 2009 г. Проверено 30 октября 2013 г.

[bfsfaq-4] Перейти обратно: ^а ^б ^с «Часто задаваемые вопросы о BFS v0.330» . Ck.kolivas.org . Проверено 30 октября 2013 г.

[shedulers_compared-5] Перейти обратно: ^а ^б ^с «Сравнение планировщиков ЦП» (PDF) . Repo-ck.com . Проверено 30 октября 2013 г.

[6] «Con Kolivas возвращается с планировщиком Linux, ориентированным на настольные компьютеры» . Слэшдот. 6 сентября 2009 года . Проверено 30 октября 2013 г.

[7] «Инго Молнар тестирует новый планировщик BF» . Журнал Линукс. 08.09.2009 . Проверено 30 октября 2013 г.

[sched-bfs-001.patch-8] "sched-bfs-001.patch" . Кон Коливас. 13 августа 2009 г. Проверено 9 октября 2020 г.

[4.0-sched-bfs-462.patch-9] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с ^т ^в ^v ^В ^х ^и ^С ^аа ^аб ^и ^{объявление} ^но ^из ^в ^ах ^есть ^также ^и ^аль ^{являюсь} ^а ^к ^ап ^ак ^с ^как ^в ^В ^из ^хорошо ^топор ^{является} ^тот ^нет ^бб ^{до нашей эры} ^др. ^быть ^парень ^бг ^чб «4.0-sched-bfs-462.patch» . Кон Коливас. 16 апреля 2015 г. Проверено 29 января 2019 г.

[lwn-224865-10] Перейти обратно: ^а ^б «Планировщик сроков для вращающейся лестницы» . корбет. 6 марта 2007 г. Проверено 30 января 2019 г.

[11] "sched-rsdl-0.26.patch" . Кон Коливас. Архивировано из оригинала 26 июля 2011 г. Проверено 30 января 2019 г.

[0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch-12] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с ^т ^в ^v «0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch» . Кон Коливас. 27 августа 2018 г. Проверено 29 января 2019 г.

[4.7-sched-bfs-480.patch-13] Перейти обратно: ^а ^б "4.7-sched-bfs-480.patch" . Кон Коливас. 2016-09-02 . Проверено 9 октября 2020 г.

[14] Альтернативная формула представлена для простоты понимания. Вся математика выполняется в целочисленной математике, поэтому потеря точности будет большой. Возможно, именно поэтому Коливас отложил деление на 128 до одного из самых больших чисел, кратного 128, в результате которого не было остатка.

[15] «Планировщик Linux» . Моше Бар. 01 апреля 2000 г. Проверено 29 января 2019 г.

[16] "schedtool.c" . фрик. 17 июля 2017 г. Проверено 30 января 2019 г.

[17] «Sabayon 7 приносит Linux-рай» . Остатик.com . Проверено 30 октября 2013 г.

[18] «Издание 2010 года теперь доступно для загрузки» . PCLinuxOS. 22 октября 2013 г. Проверено 30 октября 2013 г.

[19] «Zenwalk 6.4 готов! - Релизы - Новости» . Zenwalk.org. Архивировано из оригинала 23 октября 2013 г. Проверено 30 октября 2013 г.

[20] «О GalliumOS — GalliumOS Wiki» . wiki.galliumos.org . Проверено 8 июня 2018 г.

[21] [1] Архивировано 22 сентября 2009 г., в Wayback Machine.

[22] «CyanogenMod 5 для G1/ADP1» . Lwn.net . Проверено 30 октября 2013 г.

[bfsretired-23] «ck-hacking: linux-4.8-ck2, MuQSS версия 0.114» . ck-hack.blogspot.com . 21 октября 2016 г. Проверено 10 ноября 2016 г.

[phoronix-MuQSS-24] «Con Kolivas объявляет о выпуске первого основного выпуска MuQSS, преемника BFS — Phoronix» .

[muqsseol-25] «5.14 и будущее MuQSS и еще раз -ck» . ck-hack.blogspot.com . 31 августа 2021 г. Проверено 20 сентября 2022 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]