OSDev

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


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

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

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

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

Всё равно не понятно, каких именно инструкций не хватает в этих процессорах.

Большие страницы нужны там, где требуется случайный доступ к большим массивам данных. Например, данные размером 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. >>>

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

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



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