Опубликован перевод (http://dixx.ru/reference/tlsf) описания алгоритма управления памятью TLSF (http://tlsf.baisoku.org/) с эффективностью O(1), использующий стратегию выделения памяти "хорошо подходящими" (good-fit) блоками и комбинацию связных списков и битовых карт для управления памятью.

URL: http://dixx.ru/reference/tlsf
Новость: http://www.opennet.me/opennews/art.shtml?num=11528

• Алгоритм управления памятью TLSF,fresco, 13:56 , 26-Июл-07
• Алгоритм управления памятью TLSF,pavlinux, 14:17 , 26-Июл-07
  • Алгоритм управления памятью TLSF,fresco, 14:24 , 26-Июл-07
    • Алгоритм управления памятью TLSF,sauron, 14:34 , 26-Июл-07
      • Алгоритм управления памятью TLSF,fresco, 15:00 , 26-Июл-07
        • Алгоритм управления памятью TLSF,Alchemist, 00:00 , 27-Июл-07
  • Алгоритм управления памятью TLSF,Alchemist, 23:53 , 26-Июл-07
    • Алгоритм управления памятью TLSF,Аноним, 08:42 , 27-Июл-07
      • Алгоритм управления памятью TLSF,Alchemist, 16:21 , 27-Июл-07
• OpenNews: Алгоритм управления памятью TLSF,а344, 11:19 , 12-Ноя-08
  • OpenNews: Алгоритм управления памятью TLSF,Антонина, 13:33 , 22-Дек-08
    • OpenNews: Алгоритм управления памятью TLSF,а344, 15:02 , 22-Дек-08
      • OpenNews: Алгоритм управления памятью TLSF,Антонина, 12:58 , 25-Дек-08
      • OpenNews: Алгоритм управления памятью TLSF,Антонина, 12:59 , 25-Дек-08
        • OpenNews: Алгоритм управления памятью TLSF,vsg, 11:23 , 27-Фев-11

Качество перевода просто супер. Новикову респект!

При беглом просмотре видно, что эфективность не О(1).
Будет время, посмотрю...

Кстати, да. Время работы алгоритма не детерминировано вроде... Если блоков нужного размера в массиве не окажется?

Тоже беглым взглядом, если ошибся -- сильно не бейте.

Детерминировано. Память то это конечная. Не найдет блоки успокоится.

Нифига. Нет куска нужного размера -- он будет искать больший, если и его нет -- еще больший. не вернет же он ENOMEM, если нет блока памяти в 1kb, но полно в 2kb.

операция поиска в индексах выполняется за детерминированное время. там нет никаких циклов :) это легко видно из сорцов по ссылке на оригинал. другое дело - расширение объёма памяти, выделенной процессу, там могут быть косяки.

Там зависит от реализации [s]brk(). Если оно даёт О(1), то работать будет всё за О(1), в противном случае иногда будет что-то иное. С другой стороны, изначально алгоритм ориентирован на системы реального времени, а на тех задачах часто можно сразу выделить большую кучу и не париться этим вопросом.

Скажите, а разве бывают не O(1) реализации sbrk? Я всегда думал, что он просто двигает границу... Или у меня устаревшие данные?

Вообще говоря, для того, чтобы двигать границу, надо ещё найти свободные страницы памяти, которые будут соответствовать месту между старой и новой границей. Потому что если просто подвинуть размер сегмента данных и не сделать соответствующих изменений в таблице страниц, при обращении к оному месту мы поимеем исключение. Так что sbrk() - тот же аллокатор, но на уровне ядра. И реализован он может быть по-разному. Вот в детали реализации в разных ОС я не вникал, поэтому говорить что-то о его эффективности не могу.

Подниму старую тему ...

>URL: http://dixx.ru/reference/tlsf

Этот сайт походу давно уже не отвечает, копия сохранилась у кого-нибудь?

Добрый день,
кто-нибудь откликнулся ?
очень нужен этот материал
завтра доклад :-((

>Добрый день,
>кто-нибудь откликнулся ?
>очень нужен этот материал
>завтра доклад :-((

Придётся на англицком читать :)
Я в общих чертах осилил.

Привет, может поделитесь информацией
у меня что-то плохо получается

Привет, может поделитесь информацией
у меня что-то плохо получается

http://replay.waybackmachine.org/20070728155440/http://dixx....