Board.KolibriOS.org

Official KolibriOS board
It is currently Sat Oct 31, 2020 1:04 pm

All times are UTC+03:00




Post new topic  Reply to topic  [ 182 posts ]  Go to page Previous 19 10 11 12 13 Next
Author Message
PostPosted: Tue Oct 20, 2009 2:09 pm 
Offline
Kernel Developer
User avatar

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


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


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

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

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

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

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

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

_________________
Евангелие от Иоанна: стих 1
Code:
; В начале было Слово:
B32:        mov     ax, os_stack       ; Selector for os


Top
   
PostPosted: Fri Jul 22, 2011 1:51 am 
Offline
User avatar

Joined: Tue Aug 25, 2009 4:45 pm
Posts: 797
Для всех разработчиков (всех - это yogev_ezra и art_zh) - что думаете о статье о Колибри и Ко в самом крупном журнале индустрии? http://industrial-embedded.com/


Top
   
PostPosted: Fri Jul 22, 2011 9:00 am 
Offline
Kernel Developer

Joined: Wed Mar 08, 2006 6:25 pm
Posts: 3952
А ссылка на статью есть ?


Top
   
PostPosted: Fri Jul 22, 2011 9:21 am 
Offline

Joined: Mon Sep 24, 2007 11:11 am
Posts: 2814
А сама статья вообще в природе есть?


Top
   
PostPosted: Fri Jul 22, 2011 11:18 am 
Offline
Public Relations
User avatar

Joined: Mon Jun 07, 2010 12:01 pm
Posts: 1879
Если я понял правильно, то он имел в виду, чтобы мы им предложили написать статью о Колибри. Ну предложить-то можно, только захотят ли они.


Top
   
PostPosted: Fri Jul 22, 2011 12:49 pm 
Offline
Kernel Developer
User avatar

Joined: Fri Aug 14, 2009 1:46 am
Posts: 1421
XVilka
Я очень сомневаюсь, что этот гламурненький таблоид вообще когда-нибудь рискнет упомянуть о существовании Колибри.
И дело здесь не в ЖРВ-стандартах, а в том что они курируют огромный лохотрон мощный коммерческий сектор, которому открытый код строжайше противопоказан.

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


Top
   
PostPosted: Fri Jul 22, 2011 12:56 pm 
Offline
Public Relations
User avatar

Joined: Mon Jun 07, 2010 12:01 pm
Posts: 1879
А как насчёт http://www.rtcmagazine.com/ например?


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 182 posts ]  Go to page Previous 19 10 11 12 13 Next

All times are UTC+03:00


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited