LINUX.ORG.RU
Новости — Документация  

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


0

0

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

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

★★★★★

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

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

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

troorl ★★
()
Ответ на: Re: Алгоритм управления памятью TLSF от ip1981

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

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

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

anonymous
()

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

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

anonymous
()

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

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

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

KUser ★
()

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

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

Sorcerer ★★★★★
()
Ответ на: Re: Алгоритм управления памятью TLSF от Sorcerer

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

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

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

KUser ★
()
Ответ на: Re: Алгоритм управления памятью TLSF от mv

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

>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 ★★★
()

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

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

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 ★★★
()
Ответ на: Re: Алгоритм управления памятью TLSF от Sorcerer

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

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

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

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

KUser ★
()

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

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

dilmah ★★★★★
()
Ответ на: Re: Алгоритм управления памятью TLSF от KUser

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

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

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

Crazy_Doctor ★
()
Ответ на: Re: Алгоритм управления памятью TLSF от dilmah

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

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

+1, читаем:

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

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

generatorglukoff ★★
()
Ответ на: Re: Алгоритм управления памятью TLSF от dilmah

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

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

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

anonymous
()

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

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

generatorglukoff ★★
()
Ответ на: Re: Алгоритм управления памятью TLSF от generatorglukoff

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

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

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

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

Sorcerer ★★★★★
()

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

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

Adjkru ★★★★★
()
Ответ на: Re: Алгоритм управления памятью TLSF от Crazy_Doctor

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

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

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

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

KUser ★
()
Ответ на: Re: Алгоритм управления памятью TLSF от generatorglukoff

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

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

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

Crazy_Doctor ★
()
Ответ на: Re: Алгоритм управления памятью TLSF от rtc

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

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

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

rtc ★★
()
Ответ на: Re: Алгоритм управления памятью TLSF от rtc

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

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

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

Crazy_Doctor ★
()
Ответ на: Re: Алгоритм управления памятью TLSF от rtc

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

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

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

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

Crazy_Doctor ★
()
Ответ на: Re: Алгоритм управления памятью TLSF от anonymous

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

Тут есть сравнение: http://rtportal.upv.es/rtmalloc/papers/tlsf_slides.pdf

Согласно этому сравнению, TLSF не хуже чем DLmalloc.

Processor instructions:
 Alloc memory:
   DLmalloc:  279
   TLSF:      147
  
 Free memory:
   DLmalloc:  70
   TLSF:      140

Fragmentation:
  DLmalloc:  10,11
  TLSF:      10,49

anonymous
()
Ответ на: Re: Алгоритм управления памятью TLSF от generatorglukoff

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

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

> +1, читаем:

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

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

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

fmj
()
Ответ на: Re: Алгоритм управления памятью TLSF от rtc

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

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

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

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

fmj
()
Ответ на: Re: Алгоритм управления памятью TLSF от fmj

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

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

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

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

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

rtc ★★
()
Ответ на: Re: Алгоритм управления памятью TLSF от rtc

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

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

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

fmj
()
Ответ на: Re: Алгоритм управления памятью TLSF от Sorcerer

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

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

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

frame ★★★
()

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

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

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