Board.KolibriOS.org
http://board.kolibrios.org/

Колибри для встроенных систем?
http://board.kolibrios.org/viewtopic.php?f=25&t=1211
Page 12 of 13

Author:  art_zh [ Tue Oct 20, 2009 2:09 pm ]
Post subject:  Re: Колибри для встроенных систем?

diamond wrote:
Мда. Похоже, комментарий в конце поста хотя и услышали, но не восприняли. Ну ладно, попробую ещё раз.
Есть много разных алгоритмов сортировки, в том числе быстрая (quicksort) и пирамидальная (heapsort). В среднем быстрая сортировка быстрее, но в худшем случае она ведёт себя просто ужасно. В ядре обычной системы имеет смысл использовать быструю сортировку вместо пирамидальной, потому что практически во всех случаях она быстрее. Но ядру RTOS быстрая сортировка категорически противопоказана, потому что теоретически вполне возможна ситуация "фатального невезения", когда быстрая сортировка будет выполняться слишком долго, а вот пирамидальная вполне подходит, хотя она в среднем и медленнее.
Один момент применительно к Колибри. Есть такая функция, как alloc_page - выделение физической страницы. Которая вызывается из кучи разных мест всеми подряд и выполняется с запрещёнными прерываниями. Она не использует под необходимые структуры много памяти (всего по одному биту на каждую существующую физическую страницу, занята/свободна, плюс две вспомогательные переменные) и в типичной ситуации (практически во всех ситуациях) находит свободную физическую страницу очень быстро. Но легко представить ситуацию, при которой этой функции понадобится несколько миллионов тактов, что даже на гигагерцовых процессорах приводит к запрещению прерываний на несколько миллисекунд, а на процессорах послабее соответственно увеличивает время до вполне ощутимых макроскопических величин. Кроме того, порядок величины указан исходя из того, что сейчас Колибри не знает ничего ни о PAE, ни о x64 и адресовать память больше 4 Гб в принципе не может, а потенциально эту величину следует ещё увеличить пропорционально объёму памяти, что опять-таки становится вполне ощутимым временем, даже если несколько миллисекунд ничего не решают. Но попытки переделать эту конкретную функцию уже могут натолкнуться на сопротивление, если окажется, что в типичной ситуации оно замедляет процесс (функция, между прочим, критичная для производительности системы) или существенно раздувает объём необходимой памяти, пусть и снижает гарантированное время работы - то, что хорошо для RTOS, вовсе необязательно хорошо для обычной системы.
На всякий случай уточняю, если кто не понял: если первый пример можно было обойти, просто не обращаясь к жёстким дискам, то в этом примере независимо от крутости обработчика он может просто не получить вовремя управления из-за других процессов в системе.
Повторяю ещё раз - это всего лишь пример блокировки, уже второй. Всего блокировок несколько сотен.


diamond wrote:
... при организации связанным списком перебор делать всё равно придётся, чтобы при выделении непрерывного блока страниц найти блок нужной длины. А освобождение памяти превратится в кошмар из-за того, что нужно будет просмотреть все блоки с целью проверить, не нужно ли склеить только что освобождённый с каким-то из старых.


Для менеджера памяти идеально подходит сортировка вставками в бинарное дерево. Поиск, сортировка и вставка в более-менее упорядоченном дереве в худшем случае занимают порядка log2N шагов. Чтобы добавить/удалить одну страницу памяти из тысячи, нужно не больше 10 шагов! Места для дерева требуется столько же, сколько и для двусвязного списка.

Правда, в отсутствие "садовника" деревья имеют тенденцию "дичать", выбрасывая длинные "черенки" без ветвления, что в самом худшем случае вырождает всю структуру в односвязный список, поэтому время от времени система должна их приводить в божеский вид. Переподвешивание бинарного дерева - несложная операция, занимающая ровно 2 N log2N шагов - столько же, сколько в среднем нужно для быстрой сортировки. Безусловные плюсы налицо:

1) аллокация памяти ускоряется в N раз и перестает быть RT-проблемой;

2) упорядочение дерева требуется редко (скажем, после каждой сотни обычных вызовов менеджера памяти) и выполняется гарантированно быстро;

3) система может проводить упорядочивание дерева без блокировки прерываний;

4) можно объединить упорядочивание дерева с другой важной функцией - "сшивкой" смежных страниц памяти.

Author:  XVilka [ Fri Jul 22, 2011 1:51 am ]
Post subject:  Re: Колибри для встроенных систем?

Для всех разработчиков (всех - это yogev_ezra и art_zh) - что думаете о статье о Колибри и Ко в самом крупном журнале индустрии? http://industrial-embedded.com/

Author:  Serge [ Fri Jul 22, 2011 9:00 am ]
Post subject:  Re: Колибри для встроенных систем?

А ссылка на статью есть ?

Author:  SoUrcerer [ Fri Jul 22, 2011 9:21 am ]
Post subject:  Re: Колибри для встроенных систем?

А сама статья вообще в природе есть?

Author:  yogev_ezra [ Fri Jul 22, 2011 11:18 am ]
Post subject:  Re: Колибри для встроенных систем?

Если я понял правильно, то он имел в виду, чтобы мы им предложили написать статью о Колибри. Ну предложить-то можно, только захотят ли они.

Author:  art_zh [ Fri Jul 22, 2011 12:49 pm ]
Post subject:  Re: Колибри для встроенных систем?

XVilka
Я очень сомневаюсь, что этот гламурненький таблоид вообще когда-нибудь рискнет упомянуть о существовании Колибри.
И дело здесь не в ЖРВ-стандартах, а в том что они курируют огромный лохотрон мощный коммерческий сектор, которому открытый код строжайше противопоказан.

Это все равно как если бы VOGUE напечатал статью Проханова :twisted: .

Author:  yogev_ezra [ Fri Jul 22, 2011 12:56 pm ]
Post subject:  Re: Колибри для встроенных систем?

А как насчёт http://www.rtcmagazine.com/ например?

Page 12 of 13 All times are UTC+03:00
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/