Мышление
, как описано выше. Распределители могут, конечно, также есть
проблема внутренней фрагментации; если распределитель раздает куски
памяти больше, чем, что просила, ни на незаданные Для (и, следовательно, неиспользуемого)
пространства на такой кусок является внутренней фрагментации (т. к.
отходов происходит внутри выделенного блока) и другой пример космического
мусора. Однако, ради простоты, и потому что он является более
интересным из двух типов фрагментации, мы ориентируемся в основном на внешней
фрагментации.
Мы будем также предполагать, что раз память раздают клиент, он не может
быть перемещена в другое местоположение в памяти. Например, если программа
вызывает malloc() и получает указатель на некоторое пространство в куче,
что область памяти-это по сути “принадлежит” программе (и не может
быть перемещен в библиотеке), пока программа не вернет ее через
соответствующий вызов Free(). Таким образом, отсутствие уплотнения свободного пространства, которое
Это почти 80 страниц; таким образом, вы действительно должны быть заинтересованы!
o
PERATING
С
YSTEMS
[В.
ERSION
1.00]
ВСЕМИРНАЯ ПАУТИНА
.
ОСТЕП
.
Орг
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
было бы полезно бороться с фрагментацией
. Уплотнения могут, однако,
использоваться в ОС для борьбы с фрагментацией при осуществлении
сегментации
(как обсуждалось в этой главе о сегментации).
Наконец, мы предположим, что распределитель управляет смежной области
байтов. В некоторых случаях выделения могут попросить этого региона растут;
например, на уровне пользователя памяти-выделение библиотека может позвонить в
ядре растут кучи (через системный вызов, такие как сбрк), когда он работает вне
пространства. Однако, для простоты, мы будем предполагать, что область -
один фиксированный размер на протяжении всей своей жизни.
17.2 механизмы низкого уровня
Прежде чем углубляться в детали политики, мы сначала рассмотрим некоторые
общие механизмы, используемые в большинстве распределителей. Во-первых, мы обсудим основы
разделения и объединения, единые методики в большинстве любого распределителя.
Во-вторых, мы покажем, как можно отслеживать размер выделенных регионов быстро
и с относительной легкостью. Наконец, мы обсудим, как построить простой список
внутри свободного пространства, чтобы отслеживать, что бесплатно, а что нет.
Расщепление и Коалесцирование
Бесплатный список содержит набор элементов, которые описывают свободные места еще
оставшихся в куче. Таким образом, предположим, что следующая 30-байтовая куча
Бесплатно
используемый
Бесплатно
Свободный список для этой кучи будет иметь два элемента. Одна запись
описывает первые 10 байт свободного сегмента (в байтах 0-9), и одна запись описывает
другие бесплатные сегмента (в байтах 20-29
глава
addr: 0
лен: 10
addr: 20
лен: 10
НЕДЕЙСТВИТЕЛЬНЫЙ
Как описано выше, запрос на все, что больше 10 байт будет
выполнена (возврат null); там просто не один непрерывный кусок
памяти такого размера в наличии. Запрос на точно такого размера (10 байт) может
быть легко удовлетворены любой из свободных блоков. Но что произойдет, если
запрос на что-то меньшее, чем 10 байт?
Предположим, что у нас есть запрос только для одного байта памяти. В этом
случае распределитель будет выполнять это действие называется разделение: он найдет
Как только ты передашь указатель на кусок памяти, в программу на C, это вообще сложно
определить все ссылки (указатели) для этого региона, который может быть сохранен в другие переменные
или даже в регистрах на момент исполнения. Это не может быть дело в более
stronglytyped, собранной "мусор" языков, что тем самым позволит уплотнение как способ
борьбы с фрагментацией.
c 2008-18, A
RPACI
-Д
USSEAU
T
ХРИ
Ми
ASY
p
IECES
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
свободный кусок памяти, который может удовлетворить запрос и разделить его на два.
Первый кусок он вернется к абоненту; вторая часть останется
в списке. Таким образом, в нашем примере выше, если запрос на 1 байт были сделаны,
и распределитель решил использовать второй из двух элементов в списке
, чтобы удовлетворить запрос, вызов malloc() возвращает 20 (адрес
1 байт выделенной области) и список будет в конечном итоге глядя, как этот
глава
addr: 0
лен: 10
addr: 21
лен: 9
НЕДЕЙСТВИТЕЛЬНЫЙ
На картинке вы можете видеть список в принципе остается неизменным; единственное изменение
заключается в том, что в регионе сейчас начинается в 21, а не 20, и длина
свободного края составляет сейчас всего 9
. Таким образом, разделение обычно используется в распределителях
когда запросы меньше, чем размер какого-либо конкретного свободного куска.
Следствие механизм встречается во многих распределителей известен как coalesc
Луг
свободного пространства. Возьмите наш пример сверху еще раз (бесплатно 10 байт
используется 10 байт, и еще 10 байт бесплатно).
Учитывая это (крошечный) кучи, что происходит, когда приложение вызывает бесплатный(10),
тем самым возвращая пространство в середине кучи? Если мы просто добавим это
свободное пространство обратно в наш список, не долго думая, мы могли бы в конечном итоге
с список, который выглядит так
глава
addr: 10
лен: 10
addr: 0
лен: 10
addr: 20
лен: 10
НЕДЕЙСТВИТЕЛЬНЫЙ
Внимание, проблема: пока всю кучу теперь бесплатно, это, казалось бы,
делятся на три куски по 10 байт каждый. Таким образом, если пользователь запрашивает 20
байт, простой список обхода не найдете такой бесплатный кусок, и возврата
отказа.
Что распределители сделать для того, чтобы избежать этой проблемы-объединить свободное пространство
, когда участок памяти освобождается. Идея проста: при возврате
бесплатный кусок в памяти, внимательно смотрите на адреса блока вы
возвращаете, а также близлежащие куски свободного места; если
newlyfreed место находится прямо рядом с одной (или двух, как в данном примере) существующего свободного
куски, объединить их в один большой бесплатный кусок. Таким образом, с
коалесцирующими, наш окончательный список должен выглядеть так
глава
addr: 0
лен: 30
НЕДЕЙСТВИТЕЛЬНЫЙ
Действительно, это то, что кучи списка посмотрел бы сначала, прежде чем какие-либо
перерасчеты были сделаны. С коалесцирующими, распределитель может лучше обеспечить
большие свободные экстенты доступны для применения.
Это обсуждение предполагает, что нет заголовков, нереалистичный, но упрощающий assump
tion мы делаем на данный момент.
o
PERATING
С
YSTEMS
[В.
ERSION
1.00]
ВСЕМИРНАЯ ПАУТИНА
.
ОСТЕП
.
Орг
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
запись ptr
Заголовок, используемый библиотекой malloc
20 байт, возвращенных вызывающему объекту
Рис. 17.1: Выделенный Регион Плюс Заголовок
размер
магия: 1234567
hptr
запись ptr
20 байт, возвращенных вызывающему объекту
Рис. 17.2: Конкретное Содержание Заголовка