Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2020-04-01 | 124 |
5.00
из
|
Заказать работу |
|
|
Все пустые блоки размера si связаны в список; кроме того, существует массив заголовков списков свободных блоков, по одному для каждого допустимого размера si. Если для нового элемента данных требуется блок размером d, то выбирается свободный блок такого размера si, чтобы si>d, однако si-1 < d, то есть наименьший допустимый размер в котором умещается новый элемент данных. Под наименьшим размером конечно понимается такой размер который не намного больше блока данных. Таких величин как «не намного» конечно не бывает, поэтому нужно для конкретного алгоритма точно определять величину погрешности на которую размер блока памяти может отличаться от размера блока данных.
Что делать когда нужного блока нет
Трудности возникают в том случае, когда не оказывается пустых блоков требуемого размера si. В этом случае находится блок размером si+1 и расщепляется на два блока размером si и si+1-si.
Блок si это блок нужного размера. После создания нужного блока у нас появляется новый блок, размер которого должен быть членом ряда, то есть величина si+1-si должна равняться некоторому числу sj из используемой последовательности, j<i.
Из сказанного уже может быть ясно, почему в методе близнецов ряд чисел экспоненциальный. В таком ряду числа растут очень быстро, поэтому в общую сумму ряда наибольший вклад вносят небольшое количество членов ряда, или иначе говоря небольших чисел существенно больше чем больших. Это соответствует ситуации с блоками данных, большинство которых также имеет небольшой размер. Кроме того, такой ряд будет как бы сам подстраиваться под реальную ситуацию с блоками данных.
Рассмотрим пример. Пусть мы имеем изначально следующий ряд: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, то есть ряд построенный на числах Фиббоначи. И есть следующие блоки данных: 1, 2, 1, 4, 4, 1. Посмотрим как будут распределяться наши блоки и что будет происходить с памятью. Занятые блоки будем помечать красным, а новые блоки синим.
|
Шаг 1: Блок данных объёмом 1: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Шаг 2: Блок данных объёмом 2: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Шаг 3: Блок данных объёмом 1: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Шаг 4: Блок данных объёмом 4: 1, 1, 2, 3, 1, 4, 8, 13, 21, 34, 55
Шаг 5: Блок данных объёмом 4: 1, 1, 2, 3, 1, 4, 3, 5, 13, 21, 34, 55
На этом шаге мы имеем небольшие потери. А именно пришлось использовать блок длины 5 для хранения блока данных длины 4
Шаг 6: Блок данных объёмом 1: 1, 1, 2, 3, 1, 4, 3, 5, 13, 21, 34, 55
Не сложно заметить, что количество блоков небольшого размера увеличилось. А теперь попробуем оценить потери. Рассмотрим ещё один пример и на нём рассчитаем отношение занятой памяти реальными данными к памяти которую пришлось вычеркнуть и списка свободной памяти. Пусть необходимо разместить следующие блоки: 4,1, 6,7. Общая память 1, 1, 2, 3, 5, 8, 13,
Блок 4: 1, 1, 2, 3, 5, 8, 13
Блок 1: 1, 1, 2, 3, 5, 8, 13
Блок 6: 1, 1, 2, 3, 5, 8, 13
Блок 7: 1, 1, 2, 3, 5, 8, 5, 8
Итак получаем
Требовалось | Использовано |
4 | 5 |
1 | 1 |
6 | 8 |
7 | 8 |
Итого 18 | Итого 22 |
Отношение = 18/22=0,82 Это своего рода КПД (коэффициент полезного действия)
Конечно смотря с чем сравнивать. Если сравнить с двигателями внутреннего сгорания, то это очень высокий КПД.
Почему размер блока остатка должен быть членом ряда
Представим себе процесс поиска блока нужного размера. Пусть в ряду размеров нет никаких закономерностей. Тогда все, что нам остается это честно просмотреть весь ряд, а блок нужного размера вполне может оказаться в самом конце это ряда. Или даже ещё хуже ситуация: блок примерно подходящего размера нашёлся уже в самом начале, однако пока мы не просмотрим весь ряд нельзя абсолютно уверенно сказать, что нет лучшего варианта. Поэтому единственной возможностью закончить процесс поиска досрочно - это обнаружение идеального варианта, то есть такого блока памяти размер которого абсолютно точно равен размеру блока данных, а это событие маловероятно.
|
Если же ряд размеров свободных блоков подчиняется хорошо считаемой закономерности, то мы имеем сразу два удобства.
Во-первых, мы можем вычислить с некоторой точностью номер блока нужного размера. Причём некоторое время это вычисление можно выполнять абсолютно точно, и лишь когда начнётся процесс разбиения больших блоков на маленькие точные вычисления будет выполнять несколько сложнее.
Во-вторых, первый же найденный блок и будет оптимальным решением (потому как следующий будет уже больше и может быть даже существенно больше).
Заключение
Все рассуждения, приведённые выше нужны только для того, чтобы сформулировать проблемы и очертить пути их решения. А вот ниже мы займёмся конкретным методом, называемым методом близнецов. Этот метод даёт ответ на следующие вопросы:
1. Как разбить память на блоки разного размера, так чтобы для любого блока данных нашелся нужный объём памяти.
2. Как упорядочить блоки свободной памяти, так чтобы поиск нужного блока велся максимально быстро.
3. Как организовать быстрое перераспределение памяти так, чтобы не было потребности перерабатывать всю память и составлять новый список свободных блоков.
Литература
1. Вострикова З.П. и др. "Программирование на языке "БЕЙСИК" для персональных ЭВМ". Машиностроение, 1993г.
2. Гохман А.В. и др. "Сборник задач по математической логике и алгебры множеств", издательство Саратовского Университета, 1969г.
3. Гусев В.В. Основы импульсной техники. М. Советское радио, 1975
4. Касаткин В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г.
5. Машовцев В.А. Вступительные экзамены по информатике//Информатика. 1997, №13
6. Орлов В.А. О вступительных экзаменах по информатике//Информатика, 1997, №15
7. Яснева Г.Г. Логические основы ЭВМ//Информатика и образование, 1998, №2
8. Лыскова В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование 1999
9. Шауцкова Л.З. “Решение логических задач средствами алгебры логики”, газета Информатика 1999, №5.
|
|
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!