OSDev

для всех
Текущее время: 12 дек 2017, 05:45

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 15 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Менеджер глобальной кучи
СообщениеДобавлено: 07 июн 2015, 08:58 

Зарегистрирован: 09 янв 2015, 04:04
Сообщения: 35
Всем доброго времени суток. В результате метода проб и ошибок обнаружил свой серьезный недочёт - отсутствие глобальной кучи и собственно менеджера. Сейчас встал вопрос. Есть ли готовые решения которые можно без особых плясок с бубном использовать в своем проекте? Или придется писать свой аллокатор с нуля?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Менеджер глобальной кучи
СообщениеДобавлено: 07 июн 2015, 13:16 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
Думаю что нет. Всё таки это индивидуальный продукт. И решения заложенные в нем определяют облик ОС.
Как управлять памятью. Какие структуры использовать. Как строить механизм выделения, освобождения. Как строить защиту и устойчивость. Как обрабатывать параллельности и как решать проблему исключений. Решает разработчик.

Но что-то подсказать можно. К примеру методы и структуры.

Динамический* массив структур в котором хранятся рамки и их свойства. Рамки задают диапазон в памяти к которым прилагаются эти свойства.
*) Максимальный размер массива фиксирован.

Куча представляет собой список свободных участков. Для экономии памяти сам список располагается в свободных участках. Алгоритм кучи можно посмотреть в GNU C++ или у Кнута, да ещё много где.

Стековое выделение памяти для динамических структур.

Я со всем разбирался сам. Делал всё с нуля. Старался придумать. Такова была моя цель.
Всё как-то не соберусь с духом что-бы описать управление памятью. Вернее даже не знаю с какой стороны подойти начать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Менеджер глобальной кучи
СообщениеДобавлено: 08 июн 2015, 04:00 

Зарегистрирован: 10 апр 2012, 23:19
Сообщения: 274
kailot2 тебе нужен OSDEV за пять минут.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Менеджер глобальной кучи
СообщениеДобавлено: 08 июн 2015, 07:49 

Зарегистрирован: 09 янв 2015, 04:04
Сообщения: 35
Кто сказал что мне нужен OSDEV за пять минут?
Мне нужно выделять участки памяти под различные объекты разного размера , я не думаю что эта
задача из тех , для которых годиться велосипедный метод. Я читал про различные аллокаторы , некоторые из них постоянно совершенствуются, так зачем изобретать свой велосипед с квадратными колесами если есть куда более продвинутые решения


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Менеджер глобальной кучи
СообщениеДобавлено: 08 июн 2015, 16:59 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
Все аллокаторы, примерно одинаковы по скорости. А вот в зависимости от синтетического теста некоторые быстрее. Но честно это настолько несущественно что я даже не заворачивался. Сделал самым простым способом он самый быстрый на мой взгляд.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Менеджер глобальной кучи
СообщениеДобавлено: 08 июн 2015, 19:34 

Зарегистрирован: 09 янв 2015, 04:04
Сообщения: 35
pavia писал(а):
Сделал самым простым способом он самый быстрый на мой взгляд.

Я никогда не работал со связными списками и прочим , вот подумываю реализовать на битмапе , ибо хотя бы представляю как это сделать. Не посоветуешь литературу в тему. Просто , по моему,
эта задача решалась уже много раз многими программистами , и я думаю это совсем не та задача
на которую необходимо тратить драгоценное время.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Менеджер глобальной кучи
СообщениеДобавлено: 08 июн 2015, 19:51 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1315
Откуда: Зеленоград
Без умения работать со списками в осдеве делать нечего. Да и не только в осдеве, по большому счёту, а всюду, где приходится делать работу самому, а не полагаться на 100500 готовых библиотек. Так что либо осваивайте, либо меняйте область деятельности.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Менеджер глобальной кучи
СообщениеДобавлено: 08 июн 2015, 22:23 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
kailot2
1) Когда я делал свой аллокатор я обрёл знания. Эти знания я не встречал нигде.
2) Списки является прямым следствие после битовой карты. Более того битовая карта не применима для аллокатора. Так что не тратьте на неё время.
3) Я советую вам взять кукую либо открытую ОС или Компилятор и скопировать от туда алгоритм кучи.
Почему я не публикую свой? Да по простой причине руки не доходят нормально оттестировать.
А алгоритм достаточно сложный.
4) Но могу дать словесное описание.

Куча представляет из семя массив блоков свободных и занятых
Каждый блок имеет вначале и конце свой размер.
В переменных с размером также имеется битовый флаг,
который сигнализирует свободный или занятый блок
Свободные блоки организованы в список, при помощи указателей
на предыдущей и следующий свободные блоки.
Список не кольцевой и начинается и заканчивается с nil. В некоторых алгоритмах предлагается использовать кольцевой список.


Код:
   PBlockFree = ^TBlockFree;  // Элемент для списка свободных блоков
   TBlockFree = packed record
    LeftSize: DWord;
    Prev: PBlockFree;
    Next: PBlockFree;
   FreeBytes:array [0..X] of Byte; //пустое место имеет переменное число байт
    RightSize: DWord;       // из-за этого структуру нельзя описать формально
    end;

Поэтому формально каждый блок описывается двумя структурами.

Код:
PBlockFree_Start = ^TBlockFree_Start;  // Начало блока 
   TBlockFree_Start = packed record 
     LeftSize: DWord;
     Prev: PBlockFree_Start;
     Next: PBlockFree_Start;
     end;
   PBlockFree_Stop = ^TBlockFree_Stop;  // Конец блока
   TBlockFree_Stop = packed record
     RightSize: DWord;       
     end;


В элементах структур LeftSize и RightSize помимо размера хранится ещё и битовый флаг отвечающий свободный блок или занятый. Если флаг равен 0, то блок свободен 1 используется.
Для совмещения в одной DWord флага и размера. Любой блок выравнивается на границе в 4 байта. Поэтому у размера нижние 2 бита всегда 0. И можно при помощи маски совместить или отличить. Флаг от размера.

Код:
{Формула для выравнивания на границе}
function  Allign(Addr:DWord; Chank:DWord):DWord;
begin
Allign:=(Addr+(Chank-1)) and not (Chank-1);
end;



Если блок свободный, то чтобы изменить его тип на занятый надо сделать
Код:
Block_Start^.LeftSize:=Size or 1; // Изменяем флаг на занято
Block_Stop:=PDWord(Addr(Block_Start^)+Size-SizeOf(Block_Stop^)); // вычисляем адрес конец блока
Block_Stop^.RighteSize:=Block_Start^.LeftSize; // Изменяем флаг на занято


Суть алгоритма выделения и освобождения памяти.
Если размер выделяемой памяти меньше чем описатель свободного блока, то надо его увеличить. Это решает проблему с тем что при освобождении надо выделять память. Теперь не нужно.

Надо перебрать все свободные блоки. Если нашли подходящий по размеру то помечаем блок как занятый. Или блок разрезается на два. Первый помечается как занятый, а второй(остаток) помечается как свободный.

Если размер остатка меньше чем описатель свободного блока, то надо его увеличить. Это решает проблему с тем что при освобождении надо выделять память. Теперь не нужно.

Если не нашли нужный блок в списке свободных. То просим у ОС увеличить размер кучи. Т.е. сами увеличиваем.

Если и это не помогает генерируем ошибку системы.


Для освобождение блока нам надо проверить левый и правый блоки. Если они свободные то нам надо слить(объединить) наш блок с левым или правым или одновременно слить 3 блока(левый и наш и правый).


Ускоряем код. Для ускорения выделения надо начинать проверять с того блока который только что освободили. Для этого достаточно поместить освобожденный блок на верхушку списка.
В кольцевом варианте алгоритма просто запоминают позицию и начинают с неё.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Менеджер глобальной кучи
СообщениеДобавлено: 09 июн 2015, 17:44 
Аватара пользователя

Зарегистрирован: 14 май 2012, 22:17
Сообщения: 98
А куча чего? Если это распределитель физических страниц - это одно, если данные ядра - другое. Хотя в принципе и то и другое - данные переменной длины. Кстати - любой аллокатор должен быть хорошо адаптирован к многопоточности а не иметь одну глобальную блокировку, но это большая отдельная тема.

pavia писал(а):
Куча представляет из семя массив блоков свободных и занятых
Каждый блок имеет вначале и конце свой размер.
В переменных с размером также имеется битовый флаг,
который сигнализирует свободный или занятый блок
Свободные блоки организованы в список, при помощи указателей
на предыдущей и следующий свободные блоки.


Это похоже на аллокатор Дуга Ли (Doug Lea). Он старый, но проверенный временем и главное, никто принципиально лучше не предложил - почти все это его подварианты в той или иной степени - различаются в основном индексацией свободных блоков. Подходит и для физических страниц (единица - страница) и для выделения небольших отрезков переменной длины в памяти под объекты ядра (придуман как раз для небольших фрагментов). Есть ещё аллокатор типа BiBoP (его варианты: slab, slub). Он подходит для размещения большого количества небольших одинаковых объектов в ядре. Работает быстрее и с меньшей фрагментацией, но не универсален. Для систем реального времения нужны аллокаторы с фиксированным количеством шагов для выделения памяти - это например испанский TLSF. Он конечно быстрый, но требует определенных возможностей от процессора (для IA и ARM подходит) и на мой взгляд имеет значительный оверхед по служебной информации если размещаемых данных мало (за всё надо платить).

pavia писал(а):
Ускоряем код. Для ускорения выделения надо начинать проверять с того блока который только что освободили. Для этого достаточно поместить освобожденный блок на верхушку списка.
В кольцевом варианте алгоритма просто запоминают позицию и начинают с неё.


Решение правильное для небольших фрагментов - больше шансов, что именно эта память ещё "горячая" (находится в кэше процессора). Есть данные, что это может значительно ускорить работу нагруженных систем. Для данных типа "страница" преимущества совсем не очевидны, да и к тому-же их надо обнулять если они выделяются разным процессам.

Относительно аллокатора для страниц - есть ещё вопрос как использовать то, что большинство современных процессоров поддерживает страницы разного размера. Исследований в этом направлении полно, но единственный результат - на больших страницах размещают ядро. До пользовательских программ это не доходит. Здесь кстати во многом КМК виновато наследство старых систем, где этого не было (большинство современных VMM в операционках в той или иной степени происходят от исследовательского проекта Mach) и нужды в этом не было особой (памяти было мало).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Менеджер глобальной кучи
СообщениеДобавлено: 09 июн 2015, 19:45 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
Цитата:
А куча чего? Если это распределитель физических страниц - это одно, если данные ядра - другое. Хотя в принципе и то и другое - данные переменной длины. Кстати - любой аллокатор должен быть хорошо адаптирован к многопоточности а не иметь одну глобальную блокировку, но это большая отдельная тема.

Увы но не один аллокатор не может быть оптимизирован под параллельность. Иначе будут проблемы с фрагментацией. Решается только системно, т.е несколько методов аллокации, каскадность и сложные законы на разрешение запрещения и паузы. В прочим вы правы что это отдельная большая тема.

Цитата:
Это похоже на аллокатор Дуга Ли (Doug Lea). Он старый, но проверенный

Ничуть. Дуг Ли группирует данные одного размера.
То что предложил Я это ещё более старый аллокатор, классический Heap.
Я их сравнивал у меня разница была 1-5% в приделах погрешности измерения.
Реально нужен только при научных расчетах с длинной арифметикой в остальных случаях я преимуществ не вижу.


Цитата:
Работает быстрее и с меньшей фрагментацией, но не универсален. Для систем реального времения нужны аллокаторы с фиксированным количеством шагов для выделения памяти - это например испанский TLSF. Он конечно быстрый, но требует определенных возможностей от процессора (для IA и ARM подходит) и на мой взгляд имеет значительный оверхед по служебной информации если размещаемых данных мало (за всё надо платить).
Я с этим ещё не определился. Есть варианты:
1. Для систем реального времени аллокатор не нужен.
2. Сгодится классический так как в среднем он имеет 1 шаг на 100 запросов.
3. Нужен специальный. Так как то что выше не столь надежно как хотелось бы.

Цитата:
Относительно аллокатора для страниц - есть ещё вопрос как использовать то, что большинство современных процессоров поддерживает страницы разного размера. Исследований в этом направлении полно, но единственный результат - на больших страницах размещают ядро. До пользовательских программ это не доходит.

Уже не помню. Но там какая-то проблема именно в процессоре х86-64 из-за чего идея не работает должным образом.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB