Алгоритм работы библиотечных функций malloc/free языка С

/* malloc(3) выделяет блок памяти размером size байтов и возвращает его адрес. Выравнивание границы происходит автоматически, но выделенная память не инициализируется нулями.

free(3) освобождает блок памяти по указателю ptr и делает его доступным для последующих выделений. ptr должен указывать на блок, ранее полученный вызовом malloc(3), calloc(3) или realloc(3).

Эти функции управления памятью используют brk(2) и sbrk(2). Когда функциям malloc(3), calloc(3) или realloc(3) нужно изменить границу выделяемой памяти, они обычно делают это с запасом. Если будущим запросам хватает уже выделенного пространства, они не используют системный вызов. Так библиотечные функции минимизируют число использований нижележащих системных вызовов. У каждого блока памяти есть байты, где хранится длина блока и признак того, занят он или свободен. Функция free(3) никогда не возвращает память назад ядру. Вместо этого она устанавливает признак того, что блок свободен. Будущие запросы выделения памяти ищут среди всех свободных блоков блок подходящего размера, прежде чем вызывать системный вызов увеличения памяти. Смежные свободные блоки сливаются во время поиска для их более эффективного переиспользования. Аллокатор – динамический распределитель вынужден хранить список возможно несвязных областей свободной памяти, называемый пулом или кучей. Программа запрашивает блоки случайного размера в случайном порядке и освобождает их случайным образом.Все свободные блоки памяти объединяются в двунаправленный связанный список.(или односвязный,сохраняя указатель на предыдущий элемент).Поиск в списке может вестись тремя способами:· First fit - до нахождения первого подходящего· Best fit – до нахождения блока, размер которого ближе всего к размеру заданного блока· Worst fit - до нахождения самого большого блока */

Алгоритм работы malloc/free

· Блоки размером более 4 Kбайт выделяются стратегией first fit из двусвязного кольцевого списка с использованием циклического просмотра. · Блоки удаляются с помощью метода парных меток. · Все выделяемые таким образом блоки будут иметь размер, кратный 4Кбайтам.· На каждые 4 Кбайта пула выделяется спец. Запись – дескриптор. (Записи объединяются в динамический массив (_heapinfo).) · Размещение дескрипторов в _heapinfo в точности соответствует размещению страниц в пуле.· Структура _malloc_info для нефрагментированных блоков описывает область непрерывной памяти, которой принадлежит блок (начало, размер, статус)Для фрагментированных блоков дескриптор хранит размер фрагмента, счетчик занятых фрагментов и список свободных. Все свободные фрагменты объединены в список _fraghead.· В актуальном состоянии поддерживаются только дескрипторы первых блоков каждой непрерыывной области.· Головные дескрипторы всех областей связаны в два двунаправленных списка.· В одном списке содержатся все области в пуле(свободные, занятые, фрагментированные). (Список отсортирован по адресам. Он точно такой же как и в классическом алгоритме парных меток. Используется для поиска соседей блока при его освобождении). · Второй список – кольцевой, несортированный и он содержит только свободные блоки.(По нему осуществляется поиск по принципу первого подходящего)· Выделяемые блоки искючаются из списка. (Если при выделении потребовалось отрезать от блока хвост, то хвост возвращается в список в качестве самостоятельного блока).· Блоки меньшего размера объединяются в очереди с размерами, кратными степеням двойки, как в алгориме близнецов.(Элементы очередей называются фрагментами).· Парные фрагменты при освобождении не объединяются. Вместо этого 4 Кб блок разбивается на фрагменты одинакового размера.· Пока хотя бы один фрагмент блока занят, блок считается занятым.(Иначе блок возвращается в пул).

(с.230)

Алгоритм близнецов

За фиксированное (небольшое) время способен либо найти подходящий блок памяти, либо определить, что его нет.

· Объединяем блоки каждого размера в список. Если в списке блоков требуемого размера ничего нет, то ищем в списке блоков большего размера. Если там что-то есть разрезаем этот блок на части.

· Последовательные размеры блоков ограничиваются степенями двойки. (Адрес блока -близнеца получается инвертированием соответствующего бита в одресе блока).

· При освобождении блоки-близнецы объединяются.

(с. 247)

4. Системный режим процессора является полномочием (или применяется в качестве такового) Обладание им позволяет выполнять операции недопустимые в пользовательском режиме, и этот режим не может произвольно устанавливаться.

(с. 783)

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

Код ядра (собственно это и есть сама система) рассматривается как полностью доверительный.

(http://www.wasm.ru/print.php?article=drvw2k01)

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

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

(http://www.wasm.ru/print.php?article=drvw2k01)

5. Транзакция – группа операций модификации разделяемой структуры данных, кторая происходит атомарно (неделимо), не прерываясь никакими другими операциями с той же струкурой данных.

(с. 379)

Транзакция – группа операций, которые либо исполняются вместе, либо не исполняются вовсе.

(с. 401)

6. Семафоры Дийкстры – целочисленная переменная, с которой ассоциирована очередь ожидающих нитей. Стараясь пройти через семафор, нить пытается вычесть из значения переменной 1. Если значение переменной >= 1, нить проходит сквозь семафор успешно (семафор открыт). Если переменная равна 0 (семафор закрыт), нить останавливается и ставится в очередь.

(с. 394)

7. Мертвая блокировка – цикл взаимного ожидания. Образование замкнутого цикла в графе ожидающих друг друга задач.

(с. 368)

8. Контекст процесса (нити) – полный набор регистров, которые нужно сохранить, чтобы нить не заметила переключения. К таким регистрам, как минимум, относятся все регистры общего назначения, указатель стека, счетчик команд, слово состояния процессора. Если система использует виртуальную память, то в контекст входят также регистры диспетчера памяти, управляющие трансляцией виртуального адреса.

(с. 438)

9. Гармонически взаимодействующие последовательные процессы – концепция, состоящая в следующем:

1. Каждый поток (нить) представляет собой независимый программный модуль, для которого создаяется иллюзия чисто последовательного исполнения.

2. Нити не имеют разделяемых данных.

3. Все обмены данных и вообще взаимодействие происходят с использованием специальных примитивов, которые одновременно выполняют и предачу данных, и синхронизацию.

4. Синхронизация, не сопровождающаяся предачей данных просто лишена смысла – нити, не имеющие разделяемых структур данных, совершенно независимы и не имеют ни критических точек, ни нереентабельных модулей.

10. Селектор страницы (сегмента) в сегментных и страничных диспетчерах памяти – битовое поле виртуального адреса в системах с сегментной и страничной адресацией, задающее выбор страницы/сегмента: складывая его с указателем на таблицу трансляции, получаем адрес дескриптора данной страницы/сегмента.

(с. 282)

11. Дескриптор страницы (сегмента) в сегментных и страничных диспетчерах памяти – элемент таблицы трансляции, содержащий права доступа к странице, признак присутствия этой страницы в памяти и физический адрес страницы/сегмента. Для сегментов (в отличие от страниц, которые имеют фиксированную длины и образуют непрерывное пространство) там также хранится его длина.

(с. 283)

12. Абсолютная загрузка – способ загрузки, который состоит в том, что программа всегда загружается с одного и того же адреса. Это возможно в следующих случаях:

· Система может предоставить каждому процессу свое адресное пространство. (Это возможно только на процессорах, осуществляющих трансляцию виртуальногоадреса в физический).

· Система может исполнять в каждый момент только один процесс.

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

(с. 160)

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

(с. 163)

13. Элементы таблицы перемещений в относительном (перемещаемом) загрузочном модуле – ссылки на перемещаемые объекты внутри модуля. (Ассемблер при каждой ссылке на ассемблерный символ генерирует не только "заготовку" адреса в коде, но и запись в таблице перемещений. Эта запись хранит место ссылки на такой символ в коде или данных. При настройке программы на реальный адрес загрузки нам, таким образом, необходимо пройтись по всем объектам, перечисленным в таблице перемещений, и переместить каждую из ссылок — сформировать из заготовки адрес. В качестве "заготовки" адреса обычно используется смещение адресуемого объекта от начала программы и для перемещения оказывается достаточно добавить к "заготовке" адрес загрузки).

(с. 165, 178)

14. Позиционно-независимый код – код, использующий только относительную адресацию, когда адрес получается сложением адресного поля команды и адреса самой этой команды – значения счетчика команд. Этот код можно загружать с любого адреса без всякой перенастройки.

(с. 168)

15. Реентерабельная программа – программный модуль, который либо не содержащит критических секций, (для которых не обеспечено взаимоисключение), либо сам обеспечивает взаимное исключение для них.

(с. 379-380)

16. Критическая секция – интервал, в течение которого модификация нарушает целостноть разделяемой структуры данных, и наоборот, интервал, в течение которого алгоритм нити полагается на целостность этой структуры. ( Задача написания корректной многопоточной программы, таким образом, может решаться двумя способами: либо искоренением критических секций из всех используемых алгоритмов, либо обеспечением гарантии того, что никакие две нити никогда одновременно не войдут в критическую секцию, связанную с одним и тем же разделяемым объектом. )

(с. 378)

17. Список контроля доступа (ACL, Access Control List) – таблица, строки которой соответствуют учетным записям пользователей, а столбцы – отдельным операциям, которые можно осуществлять над объектом. Перед выполнением операции система ищет идентификатор пользователя в таблице и проверяет, указана ли выполняемая операция в списке его прав.

(с. 772-773)

Кольцо доступа -

18. Кооперативные многозадачные системы – принцип переключения нитей по инициативе активной нити.

(с. 435)

Вытесняющая многозадачность – методы преключения нитей по инициативе системы.

(с. 437)

Дата добавления: 2015-12-08