Планировщик задач HaikuOS. Часть 1. Оцениваем.
Содержание:
- Прелюдия.
- Завариваем кашу.
- АзБиБука.
- О честности и эффективности.
- Рецепт сыворотки правды.
- Принцип действия на пальцах.
- Кагдила в Королевстве Датском.
- Анализируем это.
- SOS Tester собственной персоной.
Прелюдия.
Полтора месяца регулярного использования одного и того же стабильного преальфа-билда показали что Haiku доросла до стадии когда в ней можно реально что-то делать.
Вот только оглядываясь на весь недолгий опыт использования понимаю что делать в основном пришлось много однотипного - строчить куда следует багрепорты и начитываться документацией дабы можно было когда-нибудь принять деятельное участие в их разгребании (знали бы вы сколько сотен-тысяч багов лежат и ждут своего сквошера, а сколько багов ещё не нашли...).
Когда сильно кидающихся в глаза ещё не идентифицированных ранее проблем заметно поубавилось, возникло желание копнуть глубже. А что может быть глубже и важнее планировщика задач?
Завариваем кашу.
Планировщик задач ОС - царь и бог, нет его главнее. Это Он решает какой задаче когда и сколько выполняться.
Хочется его потестировать. Т.е. сравнить лоб-в-лоб с неким проверенным эталоном. И всё что окажется хуже чем в эталоне - недоработка и требует исправления. Правильный эталон я считаю - самая последняя доступная коммерческая реализация BeOS.
Теперь вопрос - а как собственно сравнивать, чем? Тем более не заглядывая в исходники эталона? И за неимением на уме ничего лучшего я принялся разрабатывать свой собственный мега-тест-пакет под хитромудрым названием (для солидности :)) SOS Tester - [S]imple [O]S [S]cheduler Tester.
Конечно же никакой он не "мега", но как будет показано далее, своё название хотябы наполовину оправдывает и действительно полезен.
Суть работы программы - выяснение степени "честности" и эффективности планировщика. Кто такой "честный планировщик" и в чём измеряется его эффективность - разговор отдельный и прежде чем к нему приступить мне хотелось бы чтобы мы с читателем оказались в одном контексте. А посему предлагаю небольшой вводный экскурс во внутренний мир BeOS-подобных операционных систем.
АзБиБука.
Разработчики оригинала оставили нам в наследство (в Be Newsletter и Be Book) достаточно подробные спецификации. Кратко по пунктам.
1) Многозадачность и мультипроцессорность.
Программа в BeOS - это команда (team) или по-другому процесс, состоящий из 1 и более потоков или нитей (threads). Поток - некая последовательность программного кода имеющая свой идентификатор и ассоцииорованные с ним ресурсы (память и проч.). Каждый процесс тоже имеет свой идентификатор, внутренний список всех своих потоков и некие общие для всех своих потоков ресурсы.
BeOS - многозадачная ОС с поддержкой мультипроцессорности (SMP). Причём реализовано это так что программы заранее не могут знать какой их поток на каком процессоре будет выполняться.
По возможности потоки выполняются системой параллельно на всех доступных процессорах. Даже если процессор только один всё равно достигается определённый эффект параллельности. Происходит это за счёт того что потоки выполняются не непрерывно, а некоторыми фиксированными отрезками времени - "квантами" (в BeOS - 3 миллисекунды).
Кому дать очередную порцию времени того или иного процессора и у кого досрочно отобрать если срочно потребовалось решает планировщик задач.
2) Синхронизация и обмен данными.
Потоков много и порядок их выполнения заранее не определён. А потому чтобы синхронизировать работу потоков и обеспечить их взаимодействие на уровне системы реализованы следующие механизмы:
Синхронизация:
- единственный примитив синхронизации - семафор.
Обмен данными:
- разделяемые области (виртуальной) памяти
- непосредственная посылка сообщения одного потока другому
- порты сообщений, в которые многие могут писать и из которых многие могут читать
Кроме того потоки могут просить систему непосредственно приостановить, убить, усыпить себя или другого. А также заняться ожиданием пробуждения, возобновления или завершения работы того или иного потока и т.д.
Часть всего этого в итоге сводится к тем же семафорам, часть - к событиям по таймеру.
Внутри ядра применеюется ещё кое-что, но это вне рамок краткого рассмотрения.
3) Состояния потоков.
Потоки находятся в одном из следующих определяемых говорящими системными константами состояний:
B_THREAD_RUNNING - поток в данный момент выполняется на процессоре
B_THREAD_READY - поток ждёт своей очереди на выполнение
B_THREAD_SUSPENDED - поток приостановлен или только что был создан и ждёт своей команды на запуск
B_THREAD_WAITING - поток ждёт освобождения семафора
B_THREAD_RECEIVING - поток занят получением данных
B_THREAD_ASLEEP - поток спит (не тоже самое что приостановлен т.к. в случае спящего известно время грядущей побудки)
4) Приоритеты потоков.
Ещё одно важное свойство потока - его приоритет. Приоритет - число от 0 до 120. Причём различают 2 категории приоритетов:
- разделяемого времени (time-sharing) - от 0 до 99 включительно
- реального времени (real-time) - от 100 до 120 включительно
Приоритеты потоков играют первостепенную роль в выборе потока которому планировщик отдаст очередной квант процессорного времени когда такой момент (resheduling) наступит.
Общее правило номер раз:
Если есть хотябы один поток реального времени ожидающий кванта, ему или его собрату более высокого приоритета и уходит очередной квант. Только если на момент решедулинга нет ни одного нуждающегося потока реального времени планировщик снизходит до того чтобы удостоить этой чести одного из "простолюдинов" - потоков разделяемого времени.
Общее правило номер два:
Потоки внутри одной категории получают свой квант с вероятностью прямо пропорциональной их приоритету. Причём увеличивается эта вероятность по степени двойки.
Как мы увидим далее не все BeOS-подобные ОС придерживаются данного правила, но оно существовало изначально и задокументировано.
5) Исключительные ситуации.
Не всё "в королевстве" происходит мерно гладко. Не все потоки "едят свой хлеб" спокойно, иногда планировщик решает вмешаться раньше назначенного срока.
Причиной тому являются некоторые исключительные события, например аппаратные прерывания.
Кстати сама операция вызова очередного решедуленга по таймеру реализована именно через прерывание. А как ещё это сделать так чтобы с гарантией? :) Поток не должен и не может мешать планировщику выполнять свою работу.
Другим примером исключительной ситуации является тот факт что некий поток перестаёт держать семафор, освобождения которого кто-то ждал. В таком случае планировщик посмотрит кого семафор тормозил и если это поток, скажем, реального времени а тормозился он, скажем, потоком разделяемого времени, то резделяемый обойдётся - его не до конца израсходованный квант досрочно отберут. А может и не посмотреть правда, если его об этом попросят, операции с семафорами имеют опцию не вызывать решедулинг.
Ещё пример - кем-то инициированная (да пусть даже самим собой) смена приоритета потока. Из грязи в князи или наоборот.
Это вкратце. Сюда можно много ещё чего добавить, но сказанного уже вполне достаточно чтобы иметь некоторое понятие о той катавасии что постоянно происходит в ядре ОС, не реже чем каждые 3 миллисекунды.
О честности и эффективности.
Понятие честности планировщика относительное. Планировщик может быть оптимизирован как угодно в зависимости от того для чего та или иная ОС предназначена. В Be всегда особо упирали на то что BeOS - MediaOS, и как следствие имеем маленький квант и особый класс задач реального времени. Концепция MediaOS в этом плане ничем не мешает Desktop-направлению пути развития Haiku, тем более что в медиа-подсистеме есть переключатель, переводящий медиа-задачи в зону реального времени и обратно.
Для Desktop'ности самое важное - то, как поступает планировщик с задачами разделяемого времени. Т.к. система целиком писалась одной командой, у её архитекторов была возможность задать иерархию приоритетов потоков на уровне API и системных сервисов таким образом что пользователю почти гарантирован отзывчивый графический интерфейс и быстрая перерисовка экрана по требованию. Все задачи общего назначения имеют более низкие приоритеты и не мешают.
По большому счёту в такой ситуации от планировщика многое-то и не требуется. Функция распределения квантов должна просто _не мешать_ задумке архитекторов системы, соблюдать иерархию. Задачи более высокого приоритета всегда продвигаются по очереди быстрее менее приоритетных. Задачи одинакового приоритета должны получать ресурсов поровну. И обеспечивающего такое планировщика в данной ОС я считаю необходимо честным.
В нашем случае система не столько должна _быть_ быстрой, сколько _казаться_ таковой пользователю, всегда готовая среагировать на события с мыши/клавиатуры и перерисовать окошко на экране. Обеспечение такого со стороны планировщика - условие достаточной честности.
Соотношение скорости продвижения потоков разных приоритетов в очереди на исполнение и прочие количественные особенности - это уже не так важно до тех пор пока пользователю комфортно, разве что обозначив чёткие правила можно позволить разработчикам приложений на что-то надеяться и лучше их оптимизировать.
Сформулировать эффективность можно так - это функция от времени. Чем меньше время потраченное планировщиком на переключение между задачами и чем меньше время простоя потоков в ожидании процессора а также процессора в ожидании потоков, тем выше эффективность.
В данных формулировках в данной ОС честность превыше эффективности.
Рецепт сыворотки правды.
Но вернёмся к нашим баранам, т.е. простому процессу-тестеру (а каждая программа - это процесс), возомнившему себя вправе проследить за работой Великого и Ужасного, да так чтобы тот ничего не смог утаить :)
Если разработчики ОС не готовят жестокой подставы, то от её ядра можно ожидать вполне предсказуемого хотябы по основным пунктам поведения.
Например того что оно делает различия между потоками реального и разделяемого времени. Будем на это надеяться. Как-то худо-бедно ведь система работает, даже запускает многие старые BeOS-приложения.
Пытаться анализировать работу планировщика в условиях непредсказуемой параллельной работы множества потоков загруженной со всеми сервисами и прочими приложениями ОС проблематично. Проще искуственно создать некую хорошо известную ситуацию и посмотреть как планировщик справляется уже с ней. Ситуация - это когда запущены и работают некие задачи, по наперёд заданному сценарию. Это раз.
Ситуаций можно придумать великое множество, но условно их можно побить на 3 категории: задачи одинаковые по сути но разные по приоритетам, одинаковые по приоритетам но разные по сути и комбинация обоих этих вариантов. Остановимся пока на первом варианте, остальные слишком сложны для скороспелого simple-tester'а. Это два.
Важно обеспечить точность измерений, чтобы гарантированно все задачи стартовали одновременно и одновременно завершались. И вообще гарантированно завершались :) И чтобы всё прочее происходящее во время тестирования в ОС не оказывало на них существенного влияния. Это три.
После завершения тестирования нужно собрать статистику выполнения каждой задачи и выдать её на гора. Это четыре.
Принцип действия на пальцах.
Предлагаю следующую аналогию:
- Планировщик задач - завхоз.
- Процессоры - лопаты в ведении завхоза. Выдаются сроком не более чем на 3мс, после чего он их отбирает и решает куда отдать дальше. Сколько всего у завхоза лопат и какая в данный момент кому выдана - известно только ему.
- Потоки - нуждающиеся в лопатах. Для чего каждому нужна лопата - его личное дело.
- Приоритет потока - авторитет нуждающегося в глазах завхоза.
Некто главный строит в шеренгу перед забором н-ное количество рабочих различной мускулистости (мускулистость - эквивалент авторитета).
Каждому рабочему указывается своя индивидуальная штакетина (переменная-счётчик) откуда начинать и собственно задача - копать "от забора до обеда" (инкриментировать счётчик в бесконечном цикле).
Завхозу сообщают о том что всем этим рабочим потребуются лопаты, как он будет рабочих ими обеспечивать - его дело.
Главный удаляется на некоторое время, а по возвращению прекращает раскопки и начинает детективное расследование, суть которого - по соотношению длин прорытых траншей в сочетании с мускулистостью их рывших рабочих составить мнение о профпригодности завхоза. Достаточно ли эффективно тот распределяет лопаты и каких при этом придерживается установок.
Есть тут несколько нюансов которые я опустил и которые касаются сугубо реализации программы, но суть думаю вы уловили.
Упомяну лишь то что программа учитывает многопроцессорный случай и все погрешности измерений, а потокам приоритеты выделяются по следующей схеме:
Главный поток-детектив - поток реального времени.
Т.к. именно он даёт команду на старт и стоп, то должен быть всегда в состоянии это сделать. Выход нескольких высокоприоритетных потоков-рабочих из повиновения череват Reset'ом.
Потоки-рабочие, одинаковые по сути но разные по приоритетам - потоки разделяемого времени. Для простоты анализа логов приоритеты на пачку таких потоков выставляются так чтобы произошло равномерное размазывание в заданном диапазоне.
Диапазон приоритетов потоков я намеренно ограничил таким образом чтобы у рабочих они находились в зоне (30-99) исключив с некоторым запасом область низких приоритетов, ведь там сконцентрирована основная масса системных и прочих BeOS-приложений которые могут оказаться запущенными параллельно с работой тестера.
Так уж исторически сложилось что подавляющее большинство потоков в системе и различных приложениях имеют приоритеты не выше 20-22. В BeOS B_LOW_PRIORITY (фоновые задачи) - 5, B_NORMAL_PRIORITY (обычные потоки) - 10, B_DISPLAY_PRIORITY (большая часть графического интерфейса) - 15, B_URGENT_DISPLAY_PRIORITY - 20. Только медиа-задачи, пользовательский ввод и часть потоков ядра/драйверов имеют приоритеты близкие к зоне реального времени и в самой зоне (100-120).
Продолжая нашу аналогию это - "пришлые", которым тоже зачем-то нужны дефицитные лопаты и внимание завхоза к которым нам нежелательно и было бы неплохо свести его к минимуму. Чтобы ещё больше снизить влияние "пришлых" можно запускать тест на максимально урезанной системе, в которой работают только ядро с драйверами, app_server, input_server и окошко Terminal'а.
Кагдила в Королевстве Датском.
Итак после пары вечеров у компьютера есть чем тестировать. Приступаем.
Завхоз-контест: Zeta 1.51 vs Haiku R1/alpha1
На моей однопроцессорной одноядерной конфигурации выхлоп следующий:
1) Сценарий "20 потоков с приоритетами в диапазоне 30-99".
Zeta:
Settings: work time 20000000 microseconds, 20 working threads.
Real work time 20000016 microseconds, 20 working threads.
Inaccuracy if SMP and more than one CPU enabled: 0.000235%.
Number Priority Value Share (%)
--------------------------------------------------
0 30 0 0.000000
1 33 0 0.000000
2 37 0 0.000000
3 40 0 0.000000
4 44 0 0.000000
5 48 0 0.000000
6 51 0 0.000000
7 55 0 0.000000
8 59 0 0.000000
9 62 0 0.000000
10 66 0 0.000000
11 69 0 0.000000
12 73 773374 0.011481
13 77 5095995 0.075649
14 80 14265575 0.211770
15 84 49935995 0.741291
16 88 163575647 2.428252
17 91 248338198 3.686537
18 95 1422206811 21.112409
19 99 4832163367 71.732612
Haiku:
Settings: work time 20000000 microseconds, 20 working threads.
Real work time 20000004 microseconds, 20 working threads.
Inaccuracy if SMP and more than one CPU enabled: 0.000125%.
Number Priority Value Share (%)
--------------------------------------------------
0 30 0 0.000000
1 33 0 0.000000
2 37 0 0.000000
3 40 0 0.000000
4 44 0 0.000000
5 48 0 0.000000
6 51 0 0.000000
7 55 0 0.000000
8 59 0 0.000000
9 62 0 0.000000
10 66 0 0.000000
11 69 0 0.000000
12 73 0 0.000000
13 77 452212 0.006669
14 80 2981318 0.043966
15 84 9123815 0.134549
16 88 53505042 0.789041
17 91 231272037 3.410580
18 95 1102276559 16.255325
19 99 5381407496 79.359871
2) Сценарий "20 потоков с приоритетами в диапазоне 80-99".
Zeta:
Settings: work time 20000000 microseconds, 20 working threads.
Real work time 20000020 microseconds, 20 working threads.
Inaccuracy if SMP and more than one CPU enabled: 0.000245%.
Number Priority Value Share (%)
--------------------------------------------------
0 80 2622800 0.038939
1 81 3198878 0.047491
2 82 12490347 0.185434
3 83 10510837 0.156046
4 84 10868945 0.161363
5 85 13654016 0.202711
6 86 34698971 0.515149
7 87 28006075 0.415784
8 88 63514821 0.942955
9 89 56889869 0.844600
10 90 112048556 1.663498
11 91 115966553 1.721665
12 92 236266290 3.507662
13 93 223450040 3.317389
14 94 451431289 6.702050
15 95 467950532 6.947298
16 96 888472984 13.190469
17 97 850114296 12.620987
18 98 1560835310 23.172510
19 99 1592728201 23.645999
Haiku:
Settings: work time 20000000 microseconds, 20 working threads.
Real work time 20000004 microseconds, 20 working threads.
Inaccuracy if SMP and more than one CPU enabled: 0.000135%.
Number Priority Value Share (%)
--------------------------------------------------
0 80 0 0.000000
1 81 0 0.000000
2 82 0 0.000000
3 83 0 0.000000
4 84 0 0.000000
5 85 0 0.000000
6 86 0 0.000000
7 87 0 0.000000
8 88 0 0.000000
9 89 0 0.000000
10 90 0 0.000000
11 91 0 0.000000
12 92 0 0.000000
13 93 190048 0.002807
14 94 2282757 0.033718
15 95 9666466 0.142781
16 96 44490680 0.657161
17 97 211485429 3.123798
18 98 1085748569 16.037317
19 99 5416274731 80.002419
3) Сценарий "20 потоков с приоритетами в диапазоне 93-99".
Zeta:
Settings: work time 20000000 microseconds, 20 working threads.
Real work time 20000016 microseconds, 20 working threads.
Inaccuracy if SMP and more than one CPU enabled: 0.000245%.
Number Priority Value Share (%)
--------------------------------------------------
0 93 220871240 3.293793
1 93 213498277 3.183842
2 93 225312541 3.360025
3 93 215885276 3.219439
4 94 145615984 2.171532
5 94 145216414 2.165573
6 94 156054337 2.327196
7 95 147055073 2.192993
8 95 151236716 2.255352
9 95 139189425 2.075694
10 96 314224131 4.685940
11 96 296990166 4.428934
12 96 295259467 4.403125
13 97 295329753 4.404173
14 97 315383010 4.703222
15 97 298160239 4.446383
16 98 784213275 11.694761
17 98 774381799 11.548146
18 98 783243431 11.680298
19 99 788559924 11.759581
Haiku:
Settings: work time 20000000 microseconds, 20 working threads.
Real work time 20000012 microseconds, 20 working threads.
Inaccuracy if SMP and more than one CPU enabled: 0.000125%.
Number Priority Value Share (%)
--------------------------------------------------
0 93 0 0.000000
1 93 0 0.000000
2 93 0 0.000000
3 93 0 0.000000
4 94 0 0.000000
5 94 0 0.000000
6 94 0 0.000000
7 95 0 0.000000
8 95 0 0.000000
9 95 0 0.000000
10 96 0 0.000000
11 96 0 0.000000
12 96 973655 0.014609
13 97 18480510 0.277279
14 97 18540914 0.278186
15 97 18274859 0.274194
16 98 415220831 6.229921
17 98 437248269 6.560418
18 98 429312008 6.441343
19 99 5326894331 79.924051
Анализируем это.
Завхоз... тьфу, планировщик Zeta прекрасно различает ситуацию когда потоки приоритетами разнятся сильно и когда - не очень. Для планировщика Haiku же оба случая идентичны.
Характер распределения времени процессора в планировщике Zeta - с шагом в 2 приоритета шанс на выполнение умножается на 2. Не совсем то что описано в Be Book / Be Newsletter, но похоже. В Haiku же этот принцип не соблюдается ни в одном, ни в другом виде, между соседними по приоритету потоками целая пропасть.
Ещё больше заметно когда увеличиваешь количество потоков, скажем до 200, и растягиваешь время исполнения на подольше:
sos_tester_output_200_30-99_Haiku.txt
sos_tester_output_200_30-99_ZETA.txt
sos_tester_output_200_80-99_Haiku.txt
sos_tester_output_200_80-99_ZETA.txt
Также обращает на себя внимание то что в обоих ОС между потоками одинакового приоритета процессорное время распределяется примерно поровну.
В общем-то ничего криминального обнаружить не удалось. Да, характер у планировщиков разный, но требованиям необходимой честности удовлетворяют оба. А т.к. субъективно в обоих ОС работать мне как пользователю довольно комфортно, то очень вероятно что и с достаточной честностью дела обстоят неплохо.
Разве что насчёт Haiku меня гложут смутные сомнения, уж больно мало времени достаётся сидящему в самом низу шкалы приоритетов графическому пользовательскому интерфейсу когда есть много прожорливых более приоритетных задач.
Хотя и у Zeta формально тоже не всё в порядке, есть косячок-с. Поток с самым малым приоритетом кроме IDLE получает времени больше чем поток с приоритетом на единичку выше. Мы ещё вернёмся к этой проблеме.
Вот. А программистов что расставляя приоритеты в потоках своих программ надеялись на соблюдение правила возрастания важности приоритетов по степени двойки ждёт облом. Причём в Haiku - самый жестокий.
Ещё одна деталь реализации между делом всплывшая наружу - ограничение максимального количества потоков на процесс. В Zeta - 201. В Haiku - 1365, что есть треть максимального общего количества на систему (4096 в обоих случаях).
SOS Tester собственной персоной.
Программу можно скачать по следующему адресу:
http://otoko.narod.ru/files/haiku/sos_tester.zip
Для удобства сборки и запуска прилагаются кликабельные скрипты.
Начать работу можно с команды: sos_tester -h
Или для вышеприведённых сценариев:
#1: sos_tester -t 20000 -n 20 -p 30 99 >sos_tester_output_20_30-99.txt
#2: sos_tester -t 20000 -n 20 -p 80 99 >sos_tester_output_20_80-99.txt
#3: sos_tester -t 20000 -n 20 -p 93 99 >sos_tester_output_20_93-99.txt
Пожелания по улучшению инструмента принимаются и я уже прекрасно вижу что там улучшить, но думаю вы и сами сможете воплотить все ваши задумки быстрее меня.
Наигрались? Тогда двигаемся дальше.
(c) Михаил Панасюк aka BeAR, 2009. E-mail: otoko yandex ru