OSDev

для всех
Текущее время: 11 дек 2017, 22:09

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




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

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 938
Откуда: Дагоба
D-S писал(а):
испанский TLSF. Он конечно быстрый, но требует определенных возможностей от процессора (для IA и ARM подходит)

А какие именно возможности должен предоставлять процессор для эффективной реализации TLSF?

D-S писал(а):
Исследований в этом направлении полно, но единственный результат - на больших страницах размещают ядро. До пользовательских программ это не доходит.

Большие страницы активно используются в высокопроизводительных вычислениях при работе с большими массивами данных. Стандартные страницы в таких условиях могут снизить производительность до двух раз.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


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

Зарегистрирован: 14 май 2012, 22:17
Сообщения: 98
В большинстве аллокаторов есть таблица с индексом по по размеру свободных участков. В TLSF такая таблица - двухуровневая и обеспечивает куда более мелкую разбивку. На первом уровне разбивка крупная (например степень двойки) а во втором уровне - разбивка более мелкая для соответствующей категории. Соответственно по этим двум таблицам идёт поиск или точного значения (в идеале) или чуть большего по размеру (first-fit). Вот для поиска ближайшего подходящего по размеру и используется такие инструкции. Надо без перебора найти ближайшее значение. Для этого с каждой таблицей (для первого и второго уровня) ассоциировано слово, в котором единицами отмечаны позиции, которые имеют свободные участки соответствующего размера а нолями - пустые. Для быстрой "пробежки" по корзинам используются инструкции, которые возвращают число лидирующих нулей (т.е. куда "заглядывать не надо"). Это команды BSF/BSR в x86 или CLZ (Counting Lead Zeros) для ARM. Это идея. Основываясь на этом разработчики считают, что в их алгоритме фиксированное число шагов и ничего лучше для ОС реального времени не надо. Для того чтобы это было так - требуемое значение всё равно надо округлять до большего в первой таблице т.к. в предидущей категории точное соответствие может не быть а большее значение не найдётся из-за наличия в битовом массиве меньших установленных битов.

А где, в каких системах используются большие страницы для пользовательских процессов?


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

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 938
Откуда: Дагоба
Всё равно не понятно, каких именно инструкций не хватает в этих процессорах.

Большие страницы нужны там, где требуется случайный доступ к большим массивам данных. Например, данные размером 4ГБ будут содержать миллион страниц размером 4кБ. При последовательном доступе всё (более-менее) в порядке, – при первом промахе загрузил адрес физической страницы в TLB и обрабатывай всю страницу. Однако, при случайном доступе миллион страниц не поместятся в TLB. Может оказаться даже так, что на каждое обращение к данным сначала происходит загрузка адреса страницы в TLB, затем обращение непосредственно к данным.
Выделение больших страниц сейчас поддерживается как минимум в Windows и Linux.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


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

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
D-S, просто запутался. Для такого аллокатора в принципе ничего сверх естесвенного не требуется. Просто для того что бы он работал быстро неплохо иметь определенные команды, для работы с битами. Доказательство фиксированного числа шагов строится на основе этих команд. Но в качестве базеса можно положить их функциональную замену на любом другом наборе команд.


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

Зарегистрирован: 14 май 2012, 22:17
Сообщения: 98
Yoda писал(а):
Всё равно не понятно, каких именно инструкций не хватает в этих процессорах.


Речь как раз о том, что нужные инструкции в них ЕСТЬ!

Yoda писал(а):
Выделение больших страниц сейчас поддерживается как минимум в Windows и Linux.


Что-то я пропустил - пойду подтяну матчасть. :)


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

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


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

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


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

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