Компьютерные книги
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 111

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 105 106 107 108 109 110 < 111 > 112 113 114 115 116 117 .. 161 >> Следующая

size_t newLen = * (size_t*)&releaseBlock[MARKERJSIZE] +
*(size_t*)&secondAddr[MARKER_SIZE];
*(size_t*)&releaseBlock[MARKERJSIZE] = newLen;
*(size_t*)SreleaseBlock[newLen - MARKER_SIZE - SIZE_SIZE] = newLen; char * predBlock = *(char**)&secondAddr[MARKER_SIZE + SIZE_SIZE]; char * nextBlock =
*(char**)&secondAddr[MARKER_SIZE + SIZE_SIZE + PTR_SIZE];
*(char**)&predBlock[MARKER_SIZE + SIZE_SIZE + PTR_SIZE] =
releaseBlock;
*(char**)&nextBlock[MARKER_SIZE + SIZE_SIZE] = releaseBlock;
*(char**)&releaseBlock[MARKER_SIZE + SIZE_SIZE] = predBlock;
*(char**)&releaseBlock[MARKER_SIZE + SIZE_SIZE + PTR_SIZE] =
nextBlock;
} else {
// Случай (3) - в системе появляется новый свободный блок.
*releaseBlock = FREE_MARKER;
size_t len = *(size_t*)&releaseBlock[MARKER_SIZE]; releaseBlock[len - MARKER_SIZE] = FREE_MARKER;
*(size_t*)&releaseBlock[len - MARKERJSIZE - SIZE_SIZE] = len; if (freePtr == NULL) {
*(char**)&releaseBlock[MARKER_SIZE + SIZE_SIZE] = releaseBlock;
*(char**)&releaseBlock[MARKER_SIZE + SIZE_SIZE + PTR_SIZE] =
releaseBlock;
freePtr = releaseBlock;
} else {
char * predBlock = *(char**)&freePtr[MARKER_SIZE + SIZE_SIZE];
*(char**)&releaseBlock[MARKER_SIZE + SIZE_SIZE] = predBlock;
*(char**)&releaseBlock[MARKER_SlZE + SIZE_SIZE + PTR_SIZE] =
freePtr;
*(char**)&freePtr[MARKER_SIZE + SIZE_SIZE] = releaseBlock;
*(char**)&predBlock[MARKER_SIZE + SIZE_SIZE + PTR_SIZE] =
releaseBlock;
}
}
}
Работу метода граничных маркеров тоже можно проверить на примере, подобном операциям преобразования выражений. На приложенном компакт-
Алгоритмы распределения памяти
319
диске метод граничных маркеров реализован программами папки "Chapters \5.3\BoardMarkers". Реализованная система распределения памяти применяется для хранения выражений так же, как это было сделано для предыдущего случая.
Метод граничных маркеров удобно применять на практике. Он быстро работает, обладает хорошими показателями фрагментации памяти. Пожалуй, единственный его серьезный недостаток (впрочем, как и у остальных описываемых здесь методов) — это невысокая надежность. Управляющая информация о связях свободных блоков, граничные маркеры и т. п. хранятся по соседству с выделяемыми участками памяти, а значит, любая ошибка в адресации может привести к сбою в работе системы, который полностью нарушит нормальную работу. Для повышения надежности следовало бы отделять управляющую информацию от распределяемой памяти. Однако если в методе двусвязных списков это сделать сравнительно несложно, то в методе граничных маркеров это просто невозможно, поскольку хранение маркеров непосредственно в блоках памяти составляет самую суть метода.
В заключение главы приведем пример еще одного алгоритма управления памятью, который носит название метода двоичных близнецов. При этом методе размеры всех выделяемых системой блоков памяти являются степенями двойки, что, конечно, может привести к большим потерям памяти из-за сильной внутренней фрагментации. Действительно, даже если реально требуется блок памяти размером, скажем, в 75 байтов, то все равно система выделит 128 байтов, т. к. это ближайшая к 75 сверху степень двойки. Зато во всех остальных отношениях система довольно привлекательна. Она работает быстро, и так же быстро происходит слияние соседних свободных блоков, так что борьба с внешней фрагментацией не занимает много времени.
Идея метода состоит в том, чтобы вместо единого списка свободных блоков иметь несколько списков свободных блоков одного и того же размера: список номер к будет содержать лишь свободные блоки размером 2к. На рис. 5.5 показана структура буфера и вспомогательных переменных при распределении памяти этим методом. Массив freeLists на этом рисунке содержит указатели начал списков свободных блоков, к-й элемент этого массива указывает на список свободных блоков размером 2к, расположенных в буфере buffer размером 2П.
Наша система распределения памяти оказывается достаточно гибкой, поскольку любой свободный блок памяти размером 2к+х байтов можно разделить на два блока, каждый из которых будет иметь размер 2к байтов. Это позволит легко варьировать размеры блоков, перемещая их при необходимости из одного списка свободных блоков в другой.
Поиск свободного блока всегда начинается с того, что проверяется список свободных блоков нужного размера, и если список не пуст, то первый же
320
Гпава 5
блок из этого списка выдается в качестве свободного. Если блок подходящего размера сразу же не находится, то система пробует найти блок вдвое большего размера и разделить его на два равных по размеру блока. Одна из этих половинок сохраняется в списке свободных блоков соответствующего размера, а другая отдается в качестве результата запроса. Если и такого вдвое большего блока нет, то система пробует находить все большие и большие блоки до тех пор, пока либо не найдется какой-либо свободный блок, который можно раздробить на более мелкие, либо не будет достигнут верхний предел размеров блоков, и система откажет в запросе.
Возврат ранее выделенного участка памяти в систему происходит по той же схеме. Когда участок возвращается, система определяет, свободен или нет тот двойник (или близнец) возвращаемого блока, с которым вместе они могли бы составить блок вдвое большего размера. Если блок-близнец оказывается свободен, то происходит объединение блоков, и в систему возвращается уже вдвое больший блок памяти.
Предыдущая << 1 .. 105 106 107 108 109 110 < 111 > 112 113 114 115 116 117 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Завалишин Д. "Интернетско-русский разговорник" (Web-программирование)

Заенцев И.В. "Нейронные сети: основные модели" (Web-программирование)

Владимиров А.А. "Wi-фу: «боевые» приемы взлома и защиты беспроводных сетей" (Web-программирование)

Вьейра Р. "SQL Server 2000. Программирование в 2 ч." (Web-программирование)

Веллинг Л.Т. "Разработка web приложений с помощью php и mysql" (Web-программирование)
Авторские права © 2013 ComputersBooks. Все права защищены.

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed