Asmxygen
Gitea
Builds
FTP
Wiki
Telegram
Discord
Reddit
diamond wrote:Мда. Похоже, комментарий в конце поста хотя и услышали, но не восприняли. Ну ладно, попробую ещё раз.
Есть много разных алгоритмов сортировки, в том числе быстрая (quicksort) и пирамидальная (heapsort). В среднем быстрая сортировка быстрее, но в худшем случае она ведёт себя просто ужасно. В ядре обычной системы имеет смысл использовать быструю сортировку вместо пирамидальной, потому что практически во всех случаях она быстрее. Но ядру RTOS быстрая сортировка категорически противопоказана, потому что теоретически вполне возможна ситуация "фатального невезения", когда быстрая сортировка будет выполняться слишком долго, а вот пирамидальная вполне подходит, хотя она в среднем и медленнее.
Один момент применительно к Колибри. Есть такая функция, как alloc_page - выделение физической страницы. Которая вызывается из кучи разных мест всеми подряд и выполняется с запрещёнными прерываниями. Она не использует под необходимые структуры много памяти (всего по одному биту на каждую существующую физическую страницу, занята/свободна, плюс две вспомогательные переменные) и в типичной ситуации (практически во всех ситуациях) находит свободную физическую страницу очень быстро. Но легко представить ситуацию, при которой этой функции понадобится несколько миллионов тактов, что даже на гигагерцовых процессорах приводит к запрещению прерываний на несколько миллисекунд, а на процессорах послабее соответственно увеличивает время до вполне ощутимых макроскопических величин. Кроме того, порядок величины указан исходя из того, что сейчас Колибри не знает ничего ни о PAE, ни о x64 и адресовать память больше 4 Гб в принципе не может, а потенциально эту величину следует ещё увеличить пропорционально объёму памяти, что опять-таки становится вполне ощутимым временем, даже если несколько миллисекунд ничего не решают. Но попытки переделать эту конкретную функцию уже могут натолкнуться на сопротивление, если окажется, что в типичной ситуации оно замедляет процесс (функция, между прочим, критичная для производительности системы) или существенно раздувает объём необходимой памяти, пусть и снижает гарантированное время работы - то, что хорошо для RTOS, вовсе необязательно хорошо для обычной системы.
На всякий случай уточняю, если кто не понял: если первый пример можно было обойти, просто не обращаясь к жёстким дискам, то в этом примере независимо от крутости обработчика он может просто не получить вовремя управления из-за других процессов в системе.
Повторяю ещё раз - это всего лишь пример блокировки, уже второй. Всего блокировок несколько сотен.
Для менеджера памяти идеально подходит сортировка вставками в бинарное дерево. Поиск, сортировка и вставка в более-менее упорядоченном дереве в худшем случае занимают порядка log2N шагов. Чтобы добавить/удалить одну страницу памяти из тысячи, нужно не больше 10 шагов! Места для дерева требуется столько же, сколько и для двусвязного списка.diamond wrote:... при организации связанным списком перебор делать всё равно придётся, чтобы при выделении непрерывного блока страниц найти блок нужной длины. А освобождение памяти превратится в кошмар из-за того, что нужно будет просмотреть все блоки с целью проверить, не нужно ли склеить только что освобождённый с каким-то из старых.
Правда, в отсутствие "садовника" деревья имеют тенденцию "дичать", выбрасывая длинные "черенки" без ветвления, что в самом худшем случае вырождает всю структуру в односвязный список, поэтому время от времени система должна их приводить в божеский вид. Переподвешивание бинарного дерева - несложная операция, занимающая ровно 2 N log2N шагов - столько же, сколько в среднем нужно для быстрой сортировки. Безусловные плюсы налицо:
1) аллокация памяти ускоряется в N раз и перестает быть RT-проблемой;
2) упорядочение дерева требуется редко (скажем, после каждой сотни обычных вызовов менеджера памяти) и выполняется гарантированно быстро;
3) система может проводить упорядочивание дерева без блокировки прерываний;
4) можно объединить упорядочивание дерева с другой важной функцией - "сшивкой" смежных страниц памяти.
.