The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

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

26.07.2007 12:39

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

  1. Главная ссылка к новости (http://dixx.ru/reference/tlsf...)
  2. TLSF: a constant time allocator for real-time systems
Автор новости: Alchemist
Тип: яз. русский / Справочная информация
Короткая ссылка: https://opennet.ru/11528-memory
Ключевые слова: memory, kernel
При перепечатке указание ссылки на opennet.ru обязательно
Обсуждение (15) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.1, fresco (??), 13:56, 26/07/2007 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Качество перевода просто супер. Новикову респект!
     
  • 1.2, pavlinux (??), 14:17, 26/07/2007 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    При беглом просмотре видно, что эфективность не О(1).
    Будет время, посмотрю...

     
     
  • 2.3, fresco (??), 14:24, 26/07/2007 [^] [^^] [^^^] [ответить]  
  • +/
    Кстати, да. Время работы алгоритма не детерминировано вроде... Если блоков нужного размера в массиве не окажется?

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

     
     
  • 3.4, sauron (??), 14:34, 26/07/2007 [^] [^^] [^^^] [ответить]  
  • +/
    Детерминировано. Память то это конечная. Не найдет блоки успокоится.
     
     
  • 4.5, fresco (??), 15:00, 26/07/2007 [^] [^^] [^^^] [ответить]  
  • +/
    Нифига. Нет куска нужного размера -- он будет искать больший, если и его нет -- еще больший. не вернет же он ENOMEM, если нет блока памяти в 1kb, но полно в 2kb.
     
     
  • 5.7, Alchemist (?), 00:00, 27/07/2007 [^] [^^] [^^^] [ответить]  
  • +/
    операция поиска в индексах выполняется за детерминированное время. там нет никаких циклов :) это легко видно из сорцов по ссылке на оригинал. другое дело - расширение объёма памяти, выделенной процессу, там могут быть косяки.
     
  • 2.6, Alchemist (?), 23:53, 26/07/2007 [^] [^^] [^^^] [ответить]  
  • +/
    Там зависит от реализации [s]brk(). Если оно даёт О(1), то работать будет всё за О(1), в противном случае иногда будет что-то иное. С другой стороны, изначально алгоритм ориентирован на системы реального времени, а на тех задачах часто можно сразу выделить большую кучу и не париться этим вопросом.
     
     
  • 3.8, Аноним (-), 08:42, 27/07/2007 [^] [^^] [^^^] [ответить]  
  • +/
    Скажите, а разве бывают не O(1) реализации sbrk? Я всегда думал, что он просто двигает границу... Или у меня устаревшие данные?
     
     
  • 4.9, Alchemist (?), 16:21, 27/07/2007 [^] [^^] [^^^] [ответить]  
  • +/
    Вообще говоря, для того, чтобы двигать границу, надо ещё найти свободные страницы памяти, которые будут соответствовать месту между старой и новой границей. Потому что если просто подвинуть размер сегмента данных и не сделать соответствующих изменений в таблице страниц, при обращении к оному месту мы поимеем исключение. Так что sbrk() - тот же аллокатор, но на уровне ядра. И реализован он может быть по-разному. Вот в детали реализации в разных ОС я не вникал, поэтому говорить что-то о его эффективности не могу.
     

  • 1.10, а344 (?), 11:19, 12/11/2008 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Подниму старую тему ...

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

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

     
     
  • 2.11, Антонина (?), 13:33, 22/12/2008 [^] [^^] [^^^] [ответить]  
  • +/
    Добрый день,
    кто-нибудь откликнулся ?
    очень нужен этот материал
    завтра доклад :-((
     
     
  • 3.12, а344 (?), 15:02, 22/12/2008 [^] [^^] [^^^] [ответить]  
  • +/
    >Добрый день,
    >кто-нибудь откликнулся ?
    >очень нужен этот материал
    >завтра доклад :-((

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

     
     
  • 4.13, Антонина (?), 12:58, 25/12/2008 [^] [^^] [^^^] [ответить]  
  • +/
    Привет, может поделитесь информацией
    у меня что-то плохо получается
     
  • 4.14, Антонина (?), 12:59, 25/12/2008 [^] [^^] [^^^] [ответить]  
  • +/
    Привет, может поделитесь информацией
    у меня что-то плохо получается
     
     
  • 5.15, vsg (?), 11:23, 27/02/2011 [^] [^^] [^^^] [ответить]  
  • +/
    http://replay.waybackmachine.org/20070728155440/http://dixx.ru/reference/tlsf
     
     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Спонсоры:
    Inferno Solutions
    Hosting by Hoster.ru
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2021 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру