Где несколько стеков и куч помещаются в виртуальную память?

Я пишу ядро ​​и мне нужно (и хочу) поместить несколько стеков и куч в виртуальную память, но я не могу понять, как разместить их эффективно. Как нормальные программы это делают?

Как (или где) стеки и кучи помещаются в ограниченную виртуальную память, предоставляемую 32-разрядной системой, чтобы у них было как можно больше места для роста?

Например, когда в память загружается простая программа, структура ее адресного пространства может выглядеть следующим образом:

[  Code  Data  BSS  Heap->  ...  <-Stack  ]

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

Многие программы имеют разделяемые библиотеки, которые размещаются где-то в виртуальном адресном пространстве. Затем есть многопоточные программы, у которых есть несколько стеков, по одному для каждого потока. А в программах .NET есть несколько куч, каждая из которых должна иметь возможность увеличивать одну так или иначе.

Я просто не понимаю, как это сделать достаточно эффективно без предопределенного ограничения на размер всех куч и стеков.


operating-system heap-memory virtual-memory stack-memory
person Daniel A.A. Pelsmaeker    schedule 22.04.2013    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Я предполагаю, что у вас есть основы в вашем ядре, обработчик прерывания для ошибок страницы, который может отображать страницу виртуальной памяти в RAM. На следующем уровне вам понадобится диспетчер адресного пространства виртуальной памяти, у которого код пользовательского режима может запрашивать адресное пространство. Выберите степень детализации сегмента, которая предотвращает чрезмерную фрагментацию, 64 КБ (16 страниц) - хорошее число. Разрешить коду пользовательского режима как зарезервировать пространство, так и зафиксировать его. Простое растровое изображение размером 4 ГБ / 64 КБ = 64 КБ x 2 бита для отслеживания состояния сегмента выполняет свою работу. Обработчик прерывания сбоя страницы также должен обращаться к этому битовому изображению, чтобы узнать, действителен ли запрос страницы.

Стек - это выделенная виртуальная машина фиксированного размера, обычно 1 мегабайт. Обычно потоку требуется всего несколько его страниц, в зависимости от уровня вложенности функций, поэтому зарезервируйте 1 МБ и зафиксируйте только несколько верхних страниц. Когда поток встраивается глубже, он вызывает сбой страницы, и ядро ​​может просто отобразить дополнительную страницу в ОЗУ, чтобы позволить потоку продолжить. Вы захотите пометить несколько нижних страниц как особые, когда на них возникает ошибка страницы потока, вы объявляете имя этого веб-сайта.

Самая важная задача диспетчера кучи - предотвращение фрагментации. Лучший способ сделать это - создать резервный список, который разбивает запросы кучи по размеру. Все, что меньше 8 байтов, поступает из первого списка сегментов. От 8 до 16 от второго, от 16 до 32 от третьего и так далее. Увеличивая размер ведра по мере продвижения вверх. Вам придется поиграть с размерами ведра, чтобы добиться наилучшего баланса. Очень большие выделения поступают непосредственно из диспетчера адресов виртуальных машин.

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

Эта схема позволяет создавать любое количество стопок и куч.

person Hans Passant    schedule 30.04.2013
comment
Вы хорошо описываете, как работает куча, но я не понимаю, как эта «схема» позволяет мне создавать любое количество куч. Если я зарезервирую 16 МБ для первой кучи сразу после кода и данных пользователя, то где мне разместить вторую кучу? Сразу после первого? Тогда первая куча не может вырасти больше своих первоначальных 16 МБ. Или фрагментировать эту кучу при расширении (разделить кучу), но это плохо для локализации кеша (например, высокочастотной кучи), максимального размера объекта (например, кучи большого объекта), сборки мусора или по какой-либо причине используется несколько куч. Например. В .NET много куч, как они это делают? - person Daniel A.A. Pelsmaeker; 30.04.2013
comment
Вам не хватает части, в которой выделения кучи являются сегментами, а не фиксированным размером. Когда куча будет расти, она будет иметь много сегментов, они могут быть разбросаны по адресному пространству. Локальность кэша обычно очень хороша, потому что массивы имеют элементы фиксированного размера, которые происходят из одной и той же цепочки дополнительных списков. - person Hans Passant; 30.04.2013

arrow_upward
0
arrow_downward

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

Управление памятью всегда состоит из нескольких уровней, на каждый из которых возложена четко определенная ответственность. С точки зрения программы виден диспетчер уровня приложения, который обычно занимается только своей собственной выделенной кучей. Уровень выше может иметь дело с созданием нескольких куч, если необходимо, из (его) одной глобальной кучи и назначением их подпрограммам (каждая со своим собственным менеджером памяти). Выше этого может быть стандартный _1 _ / _ 2_, который он использует, и выше тех, которые операционная система имеет дело со страницами и фактическим распределением памяти для каждого процесса (в основном это не касается не только нескольких куч, но даже кучи пользовательского уровня в целом).

Управление памятью дорого обходится и поэтому попадает в ловушку ядра. Комбинирование этих двух факторов может серьезно снизить производительность, поэтому то, что кажется фактическим управлением кучей с точки зрения приложения, фактически реализовано в пользовательском пространстве (библиотека времени выполнения C) ради производительности (и по другим причинам, выходящим на данный момент за рамки). ).

При загрузке разделяемой (DLL) библиотеки, если она загружается при запуске программы, она, конечно, скорее всего будет загружена в CODE / DATA / и т. Д., Поэтому фрагментация кучи не происходит. С другой стороны, если он загружается во время выполнения, почти нет другого шанса, кроме использования пространства кучи. Статические библиотеки, конечно же, просто подключаются к разделам CODE / DATA / BSS / etc.

В конце концов, вам нужно будет наложить ограничения на кучи и стеки, чтобы они не переполнялись, но вы можете выделить другие. Если нужно вырасти за этот предел, вы можете либо

  • Завершить приложение с ошибкой
  • Попросите диспетчера памяти выделить / изменить размер / переместить блок памяти для этого стека / кучи и, скорее всего, впоследствии дефрагментировать кучу (ее собственный уровень); вот почему free() обычно работает плохо.

Принимая во внимание довольно большой фрейм стека размером 1 КБ на каждые call в качестве среднего (может случиться, если разработчик приложения неопытен), 10 МБ стека будет достаточно для 10240 вложенных call -s. Кстати, кроме этого, практически нет необходимости в более чем одном стеке и куче для каждого потока.

person Powerslave    schedule 25.04.2013
comment
Но переключение между потоками не должно переключать все адресное пространство (и вызывать сброс TLB), поэтому для каждого потока, используемого процессом, его стек должен присутствовать в адресном пространстве процесса. . И ссылка в моем сообщении показывает изображение того, как процесс CLR имеет очень много куч. Итак, требуется более одного стека и кучи в одном адресном пространстве. - person Daniel A.A. Pelsmaeker; 25.04.2013
comment
Адресное пространство - это совсем другой уровень абстракции. Фактически, в этом случае у вас есть несколько стеков и куч в одном и том же адресном пространстве. Само адресное пространство управляется ОС, а куча - нет; им управляет код библиотеки пользовательского уровня. - person Powerslave; 25.04.2013