LINUX.ORG.RU

Алгоритм управления памятью TLSF


0

0

Появился перевод описания алгоритма управления памятью TLSF. Данный алгоритм характерен тем, что эффективность его O(1) и использует он стратегию выделения памяти "хорошо подходящими" (good-fit) блоками.

>>> Подробности

★★★★★

Проверено: Shaman007 ()

Куда он внедрён или будет внедрён?

troorl ★★
()
Ответ на: комментарий от ip1981

>На каком языке программы в тексте статьи?

ну чего ты как маленький, псевдокод это

anonymous
()

данный алгоритм может за время O(1) фрагментировать память. )

anonymous
()
Ответ на: комментарий от acefsm

>как там дела с оверхедом?

с ним все хорошо :)

anonymous
()

Хорошая статья!

З.Ы. Тут недавно обсуждение планировщиков процессов в ядре было, интересно, есть подобное описание их алгоритмов?

KUser
()

Интересный алгоритм. Вместо битовых масок можно использовать связанный список диапазонов свободных блоков, упорядоченный по возрастанию размера. Так можно избежать фрагментации (поиск по fl). Диапазоны без свободных элементов содержат ссылку на первый больший диапазон со свободными. Так можно быстро вставить новый свободный элемент.

Sorcerer ★★★★★
()
Ответ на: комментарий от Sorcerer

Мнда, я поторопился: битовых масок не избежать.

Sorcerer ★★★★★
()
Ответ на: комментарий от Sorcerer

multimap из С++ хорошо подходит: он позволяет хранить несколько элементов с одним ключом

В качестве ключа используем размер свободного блока, итератор upper_bound() нам вернёт указатель на элемент с равным или большим ключом - как раз то, что нам надо.

KUser
()
Ответ на: комментарий от mv

>http://rtportal.upv.es/rtmalloc/allocators/tlsf/index.shtml

квест прошёл до

geek@geek-laptop:~/Projects/TLSF-2.2.1/src$ make
gcc -O2 -Wall -fomit-frame-pointer -I/usr/src/linux-headers-2.6.22-6-generic/include/ -c -o tlsf.o tlsf.c
/tmp/ccnjTgPM.s: Assembler messages:
/tmp/ccnjTgPM.s:103: Error: no such instruction: `clz %eax,%ebx'
/tmp/ccnjTgPM.s:149: Error: no such instruction: `clz %eax,%edx'
/tmp/ccnjTgPM.s:159: Error: no such instruction: `clz %edx,%esi'
/tmp/ccnjTgPM.s:181: Error: no such instruction: `clz %eax,%edx'
/tmp/ccnjTgPM.s:206: Error: no such instruction: `clz %eax,%eax'
/tmp/ccnjTgPM.s:216: Error: no such instruction: `clz %eax,%eax'
/tmp/ccnjTgPM.s:300: Error: no such instruction: `clz %eax,%ebx'
/tmp/ccnjTgPM.s:515: Error: no such instruction: `clz %eax,%ebx'
/tmp/ccnjTgPM.s:528: Error: no such instruction: `clz %eax,%ebx'
/tmp/ccnjTgPM.s:540: Error: no such instruction: `clz %eax,%ebx'
make: *** [tlsf.o] Ошибка 1


кто дальше

geek ★★★
()
Ответ на: комментарий от geek

Исправь в tlsf.c

#define _ARMV5_ 1
//#define _IA32_ 1

на

//#define _ARMV5_ 1
#define _IA32_ 1

anonymous
()

Йо-хо-хо :)) квест пройден %))

src> make
gcc -O2 -Wall -fomit-frame-pointer   -c -o tlsf.o tlsf.c
src> cd ../example/
example> make
cc -O2 -I../src   -c -o test.o test.c
cc -O2 -I../src -o test test.o ../src/tlsf.o
example> ./test 
Total free memory= 1045392
Test OK

Cy6erBr4in ★★★
()
Ответ на: комментарий от Sorcerer

Это верно, но скорость поиска в упорядоченном массиве такая же:

> Вместо битовых масок можно использовать связанный список диапазонов свободных блоков, упорядоченный по возрастанию размера.

Если я правильно понял, мы имеем массив размеров блоков, упорядоченный по возрастанию, но скорость поиска в нём тоже O(log n). Или есть способ как-то ускорить поиск в данном случае?

KUser
()
Ответ на: комментарий от KUser

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

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

Crazy_Doctor
()
Ответ на: комментарий от dilmah

>народ, а никому не показалось что нас тихонько обманывают про O(1)?

+1, читаем:

>Следующая функция – search_suitable_block – ищет первый непустой список свободных блоков, содержащий блоки идентичного или большего размера, соответствующего заданным fl и sl. Эта функция просматривает структуру данных справа налево по индексу второго уровня, переходя при необходимости на более высокие значения индекса первого уровня, пока не найдёт первый непустой список свободных блоков.

Натюрлих O(n)

generatorglukoff ★★
()
Ответ на: комментарий от dilmah

> народ, а никому не показалось что нас тихонько обманывают про O(1)?

Да, есть там пара очень подозрительных операций. типа удаления, возврашение, слияния блоков.

anonymous
()

кстати, а чем изначально забивается таблица? функции инициализации не вижу

generatorglukoff ★★
()
Ответ на: комментарий от generatorglukoff

>> Следующая функция – search_suitable_block – ищет первый непустой список свободных блоков, содержащий блоки идентичного или большего размера, соответствующего заданным fl и sl. Эта функция просматривает структуру данных справа налево по индексу второго уровня, переходя при необходимости на более высокие значения индекса первого уровня, пока не найдёт первый непустой список свободных блоков.

> Натюрлих O(n)

Какое тут O(n)? Смотрите алгоритм. Сначала поиск по битмапу в оптимальной строке (при фиксированном f1), если в строке нет ничего подходящего, то поиск по битмапу в столбце -> находим более высокую строку, а затем поиск по битмэпу в ней. Максимум 3 элементарных поисковых операции.

Sorcerer ★★★★★
()

огнелис с ним уже тестили?

Adjkru ★★★★★
()
Ответ на: комментарий от Crazy_Doctor

Но если блок не нашли мы можем получить тормоза в этом месте:

Цитата:
---------------
Следующая функция – search_suitable_block – ищет первый непустой список свободных блоков, содержащий блоки идентичного или большего размера, соответствующего заданным fl и sl. Эта функция просматривает структуру данных справа налево по индексу второго уровня, переходя при необходимости на более высокие значения индекса первого уровня, пока не найдёт первый непустой список свободных блоков. Опять же, использование инструкций для работы с битами позволяет реализовать такой поиск очень компактно
---------------

Кстати, я подозреваю, что при скорости O(log n) всё равно получаем фиксированное количество операций: ведь количество свободных блоков ограничено - оно никогда не превысит 2^A, где A - разрядность адреса.
Значит и количество операций всё равно не превысит некоторого максимального числа

KUser
()
Ответ на: комментарий от generatorglukoff

Параметры fl и sl находятся за постоянное количество операций (формула одна и та же). Чтобы найти первый свободный блок размером больше чем надо, операций надо не больше чем 32*2^{\alpha} (общее количество индексов в карте). Где зависимость от размера требуемой памяти? Пока не вижу.

Может чего не понимаю?

Crazy_Doctor
()
Ответ на: комментарий от Crazy_Doctor

Кстати, верно заметил комрад: Sorcerer ** (*) (26.07.2007 18:32:54)

всё гораздо проще.

Crazy_Doctor
()
Ответ на: комментарий от rtc

Хмм, оно на паскале и ограничено 32 битами...

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

rtc ★★
()
Ответ на: комментарий от rtc

Про возвращение не видел (хотя, думаю, не проблема: по идее те же операции нахождения fl и sl), а вот про склейку есть (в самом конце):

Функция free всегда пытается объединять соседние блоки. Merge_left проверяет, свободен ли предыдущий физический блок и, если это так, удаляет его из списка свободных блоков и объединяет с освобождаемым блоком. Merge_right делает тоже самое, но со следующим физическим блоком. Соседние физические блоки могут быть быстро найдены при помощи размера текущего блока (для следующего блока) и указателя на предыдущий блок, хранимого в заголовке свободного блока. Все операции выполняются за время O(1).

Crazy_Doctor
()
Ответ на: комментарий от rtc

Алгоритм не ограничен, что естественно. Просто реализация именно для 32-битного процессора приведена для примера.

Насчёт Паскаля - выше народ пости реализацию на Си и кто-то даже пробовал скомпилять.

Так что вроде нормально. Правда, насколько мне сказали, похожие алгоритмы есть и другие.

Crazy_Doctor
()
Ответ на: комментарий от dilmah

>народ, а никому не показалось что нас тихонько обманывают про O(1)?

Мне показалось, что по ссылке медленный боян. :D

anonymous
()
Ответ на: комментарий от generatorglukoff

>>народ, а никому не показалось что нас тихонько обманывают про O(1)?

> +1, читаем:

>>Следующая функция ? search_suitable_block ? ищет первый непустой список свободных блоков, содержащий блоки идентичного или большего размера, соответствующего заданным fl и sl. Эта функция просматривает структуру данных справа налево по индексу второго уровня, переходя при необходимости на более высокие значения индекса первого уровня, пока не найдёт первый непустой список свободных блоков.

> Натюрлих O(n)

Умнег, ты там хотя-бы один цикл видишь, в приведенных листингах (хоть прямой, хоть через рекурсию)? Все "проходы по спискам" делают аппаратные, отрабатывающие за 3 такта инструкции, завернутые в ffs и fls

fmj
()
Ответ на: комментарий от rtc

> Хмм, оно на паскале и ограничено 32 битами...

Дану? А я думал на бейсике!

Малолетки, это не паскаль, это АДА! (и писать только так, все большие буквы, т.к. этот язык, в отличии от большинства других, достоин высочайших почестей).

fmj
()
Ответ на: комментарий от fmj

>Умнег, ты там хотя-бы один цикл видишь, в приведенных листингах (хоть прямой, хоть через рекурсию)? Все "проходы по спискам" делают аппаратные, отрабатывающие за 3 такта инструкции, завернутые в ffs и fls

Обидели автора :)

И что же делает этот аллокатор, когда памяти больше нет, но есть дополнительный кэш? Например glibc malloc пожет замапить дополнительно несколько страниц, что сбросит в своп какие-то данные.

Этот же алокатор статически отображает всю память аллокатора (все 32 бита) на некую таблицу, при этом оверхед при выборе бОльшего блока становится чудовищным, если все малые блоки уже израсходованы. Ближайшая степень двойки в верхних разрядах.

rtc ★★
()
Ответ на: комментарий от rtc

> Этот же алокатор статически отображает всю память аллокатора (все 32 бита) на некую таблицу, при этом оверхед при выборе бОльшего блока становится чудовищным, если все малые блоки уже израсходованы. Ближайшая степень двойки в верхних разрядах.

Это не general purpose аллокатор, так что не надо к нему с требованиями общими лезть.

fmj
()
Ответ на: комментарий от Sorcerer

>Интересный алгоритм. Вместо битовых масок можно использовать связанный список диапазонов свободных блоков, упорядоченный по возрастанию размера. Так можно избежать фрагментации (поиск по fl). Диапазоны без свободных элементов содержат ссылку на первый больший диапазон со свободными. Так можно быстро вставить новый свободный элемент.

Прошло всего-то чуть больше 10-и лет и они осилили сделать что-то подобное борландовскому аллокатору? Я х.ею с таких инноваций, дорогая редакция ...

frame ★★★
()

"Алгоритм расщипления" - списки размеров свободных блоков по убыванию, объеденение меньших в большие, добовление остатков в списки меньших и другие фичи. Все уже придумано в 70е годы прошлого века - _запатентовано_(!). А так же доказало свою несостоятельность на интенсивных нагрузках (читай многозадачных системах). Так что радоватся рано. И главное - в чем новизна творчества (плагиат)?

neDBA
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.