рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Динамическое распределение памяти

Динамическое распределение памяти - раздел Программирование, Список - Конечная Последовательность, Состоящая Из Нуля Или Более Атомов Или...

Список - конечная последовательность, состоящая из нуля или более атомов или Списков. Рассмотрим Список L a N, b, c d N, e L, N f , g h L, j N а соответствующей диаграммой для него будет Существует много способов для представления Списочных структур в памяти машины.Обычно все они являются вариациями на одну и ту же основную тему, согласно которой для представления общих лесов деревьев используются бинарные деревья одно поле, скажем RLINK, используется для указания на следующий элемент Списка, а другое поле DLINK можно использовать для указания на первый элемент под-Списка.

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

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

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

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

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

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

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

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

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

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

Алгоритмы сбора мусора интересны по нескольким причинам. В первую очередь такие алгоритмы полезны в других ситуациях, когда мы хотим отметить все узлы, на которые прямо или косвенно ссылается данный узел. Можно, например, найти все подпрограммы, к которым прямо или косвенно обращается некоторая подпрограмма.Сбор мусора обычно распадается на две фазы. Мы предполагаем, что первоначально биты маркировки во всех узлах равны нулю или мы все их устанавливаем в нуль. Теперь во время первой фазы отмечаются все узлы, не являющиеся мусором, отправляясь от узлов, которые непосредственно доступны из главной программы. Во второй фазе осуществляется последовательный проход по всей области пула памяти и все неотмеченные узлы заносятся в список свободного пространства.

Наиболее интересная особенность сбора мусора состоит в том, что во время работы этого алгоритма в нашем распоряжении остается очень ограниченный объем свободной памяти, которую можно использовать для управления алгоритмом маркировки.

Следующий алгоритм маркировки относится, наверное, к наиболее очевидным. Алгоритм А. Маркировка. Пусть вся память, используемая для хранения Списков, состоит из узлов NODE 1, NODE 2 NODE М, и предположим, что эти слова являются либо атомами, либо содержат два поля связи ALINK и BLINK. Предположим, что первоначально все узлы немаркированные.Назначение этого алгоритма состоит в том, чтобы отметить все узлы, которые можно достичь по цепочке указателей ALINK и или BLINK в неатомарных узлах, отправляясь от множества непосредственно доступных узлов.

A1 Начальная установка. Отметить все непосредственно доступные узлы, т.е. узлы, указатели на которые находятся в фиксированных ячейках в главной программе и которые служат отправными пунктами для доступа ко всей памяти.Установить К1. А2. Следует ли за NODEК другой узел Установить КК1.Если NODEK - атом или немаркированный узел, то перейти к шагу А3. В противном случае, если узел NODEALINKK не отмечен, то отметить его и, если он не атом, установить К1minK1,ALINKK. Точно также, если узел NODEBLINKK не отмечен, то отметить его и, если он не атом, установить K1minK1,BLINKK. A3. Конец Установить KK1. Если KM, то вернуться к шагу А2, в противном случае алгоритм завершен.

Возможен несколько лучший вариант, предусматривающий использование стека фиксированного размера. Алгоритм B. Маркировка.В этом алгоритме используется таблица, содержащая Н ячеек STACK 0, STACK 1I, STACKH-1 , и получается тот же результат, что и в алгоритме А . В этом алгоритме действие занести Х в стек означает следующее Установить TTl mod H и STACKTX. Если Т В, то установить В В1 mod Н и К1min Kl, STACK В. Заметим, что Т указывает на текущую вершину стека, а В указывает на одну позицию ниже текущего низа STACK работает, по существу, как дек, с ограниченным входом.

B1. Начальная установка.Установить ТН-1, ВН-1, KlМ1. Отметить все непосредственно доступные узлы и последовательно занести их адреса в стек с помощью только что описанного действия.

B2. Стек пуст Если Т В, перейти к B5. BЗ. Взять из стека верхний элемент. Установить КSTACK Т, TT-l mod H. B4.Исследовать связи. Если узел NODEK - атом, то вериуться К B2. В противном случае, если NODЕАL1NKК не отмечен, то отметить его и занести ALINK К в стек. Аналогично, если NODE BLINK К не отмечен, то отметить его и занести REF К в стек. Вернуться к B2. B5. Прочесать. Если K1 М, то алгоритм завершен.Переменная К1 представляет наименьший адрес, откуда имеется возможность вновь выйти на узел, который следует отметить.

В противном случае, если NODEKI нe отмечен, увеличить К1 на 1 и повторить этот шаг. Если NODE К1 отмечен, то установить КК1, увеличить К1 на 1 и перейти к B4. Этот алгоритм можно улучшить, если не заносить в стек X, когда NODE X - атом. Алгоритм B фактически становится алгоритмом А, когда Н 1, и очевидно, эффективность его плавно возрастает с увеличением Н. К сожалению, алгоритм B не поддается точному анализу по тем же причинам, что и алгоритм А, и мы не в состоянии указать, при каком Н этот метод будет достаточно быстрым.

В качестве правдоподобного, но не очень надежного можно назвать значение Н 50, при котором алгоритм B применим для сбора мусора в большинстве случаев. В алгоритме В используется стек, расположенный в последовательных ячейках памяти, которые расположены в памяти непоследовательно.Этот факт наводит на мысль, что в алгоритме мы могли бы организовать стек, каким-то образом разбросав его по той же самой области памяти в которой собирается мусор.

Это нетрудно сделать, если предоставить программе сбора мусора немного больше места, чтобы она могла вздохнуть свободнее. Будем считать, например, что все Списки представлены, за тем лишь исключением, что поле RЕF в каждом головном узле используется для сбора мусора, а не для счетчика ссылок. Тогда мы можем переработать алгоритм организовав стек в полях REF головных узлов. Алгоритм D Маркировка.Пусть дано множество узлов, имеющих следующие поля MARK одноразрядное поле,первоначально нулевое в каждом узле, ATOM еще одно одноразрядное поле, ALINK указательное поле, BLINK указательное поле, Когда ATOM 0, поля ALINK и BLINK могут содержать или указатель на другой узел того же формата когда ATOM 1, содержимое полей ALINK и BLINK несущественно для данного алгоритма.

Если задан указатель Р0, то этот алгоритм устанавливает 1 в поле MARK в узле NODE Р0 и во всех других узлах, до которых можно добраться по цепочке указателей ALINK и BLINK и в которых ATOM MARK 0. В алгоритме используются три указательные переменные, Т, Q и Р, и связи при выполнении алгоритма могут быть временно изменены, но так, что после завершения алгоритма во всех полях ATOM, ALINK и BLINK восстанавливаются их прежние значения.

D1. Начальная установка.Установить Т, РР0. Далее в этом алгоритме переменная Т будет использоваться в двух смыслах если Т, то она указывает на вершину того, что, по существу, является стеком, а узел, на который указывает Т, некогда содержал связь, равную Р, вместо искусственной стековой связи, находящейся теперь в NODE Т. D2. Отметить.

Установить MARK Р 1. DЗ, Атом Если ATOM Р 1, то перейти к Е6. D4. Вниз по ALINK. Установить QALINK Р. Если Q и MARK Q 0, то установить ATOM Р 1, ALINK РТ, ТР, PQ и перейти к D2. Теперь поля ATOM и ALINK на время изменены и, следовательно, довольно радикально изменилась списочная структура в некоторых отмеченных узлах.Но в шаге D6 все будет восстановлено.

D5. Вниз по BLINK. Установить QBLINK Р. Если Q и MARKQ0, то установить BLINK РТ, ТР, РQ и перейти к D2. D6. Вверх. В этом шаге устраняются изменения связей, сделанные в шагах D4 или D5 значение АТОМ Т говорит о том, какую из связей ALINK Т или BLINK Т следует восстановить. Если Т, алгоритм завершен.В противном случае установить QТ. Если АТОМ Q1, то установить ATOM Q0, ТALINK Q, ALINKQP, PQ и вернуться к D5. Если ATOM Q 0, то установить ТBLINK Q, BLINКQР, РQ и вернуться к D6. Блок-схема алгоритма D показана на рисунке, После После ALINK BLINK D1.Нач. D2. D3. D4. Вниз по D5. Вниз по D6. Вверх установка Отметить Атом ALINK Уже BLINK Уже Да отмечен отмечен Обратим внимание на то, что в шагах D4 и D5 искусственно изменяется списочная структура.

Когда происходит возврат к предыдущему состоянию, поле ATOM говорит о том, какие из связей ALINK и BLINK содержат искусственные адреса.Вложения, показанные в нижней части рисунка служат иллюстрацией того, что в алгоритме каждый неатомарный узел посещается три раза Доказательство правильности алгоритма D можно построить, основываясь на индукции по количеству узлов, которые подлежат маркировке.

Одновременно доказывается, что в конце алгоритма РР0. Алгоритм D будет работать быстрее, если исключить шаг DЗ, а вместо него выполнить проверки ATOM Q 1 и соответствующие действия в шагах D4 и D5, а также проверку ATOM Р0 1 в шаге D1. Идею, на которой построен алгоритм D, можно применить не только для сбора мусора, но и в других задачах.

Время выполнения наилучших из известных программ сбора мусора выражается, по существу, формулой c1Nc2M, где c1 и c2 константы, N-количество маркируемых узлов, а М - общее количество узлов в памяти.Таким образом, М - N - количество найденных свободных узлов, и время, которое расходуется на возврат одного такого узла в свободную память, составляет c1N c2ММ-N. Пусть N М тогда формула преобразуется к виду c1 c2l . Следовательно, если 34, т. е. память заполнена на три четверти, то потребуется 3c1 4c2 единиц времени, чтобы вернуть в свободную память один узел если 14 , то соответствующая величина составляет лишь 13c1 14c2. Если сбор мусора не используется, то расход времени на один возвращаемый узел равен константе c3 и, вне всяких сомнений, отношение c3c1 будет очень велико.

Отсюда мы можем видеть, до какой степени неэффективен сбор мусора, когда память становится полной, и соответственно, насколько он эффективен, когда требования к памяти невелики.

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

– Конец работы –

Используемые теги: Динамическое, распределение, памяти0.059

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Динамическое распределение памяти

Что будем делать с полученным материалом:

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

Еще рефераты, курсовые, дипломные работы на эту тему:

Динамическое распределение памяти
Если числа в этих адресах стоящие до двоеточия увеличиваютя от первого к последнему на еденичку,то это означает что на каждый блоквыделен один… Задание 8Программа хранит матрицы ввиде двух структур Struct Matr1 int m, n… Задание 12Задание 14Задание 16Программа выполняет считываниематрицы произвольных размеров из файла разделителями…

Изучение законов нормального распределения и распределения Релея
Теоретическая часть В отличие от детерминированных процессов, течение которых определено однозначно, случайный процесс это изменение во времени… Здесь k номер реализации. Мгновенные значения случайного процесса в… Передняя панель стенда Стенд включает в себя - семь источников независимых случайных сигналов одного шумового с…

Функции распределения, плотность распределения
функции распределения плотность распределения... Мат ожидание дисперсия... Практика...

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

Память, виды памяти, методы тренировки памяти
При этом память всегда связывалась с процессом обучения т.е. накопления информации, а попытки объяснения памяти всегда совпадали с известными на… Позже - уже в 19 и начале 20 веков - в связи с созданием таких систем, как… Наконец, в связи с развитием исследований в области генетики и молекулярной биологии, раскрытием механизмов хранения…

Статистическое распределение выборки. Гистограмма. Эмпирическая функция распределения
Тема Основные понятия математической статистики... Генеральная совокупность Выборка Выборочные значения как случайные... Статистическое распределение выборки Гистограмма Эмпирическая функция распределения...

Стандартные процедуры размещения и освобождения динамической памяти
Динамическая память... Указатель... Стандартные процедуры размещения и освобождения динамической памяти...

Методы проверки гипотез о законах распределения и параметрах законов распределения
На сайте allrefs.net читайте: "Методы проверки гипотез о законах распределения и параметрах законов распределения"

Дискретная случайная величина: определение, закон распределения и функции распределения
Ситуация когда полную группу составляют равновозможные события называется классической Поэтому определение вероятности по формуле р А m n... Частотой р А появления события А или статистической вероятностью события А...

Мнестическая сфера: понятие и виды памяти. Развитие памяти в детском возрасте.
Виды памяти Генетическая память сохраняет информацию, которая определяет анатомическое и физиологическое строение организма в процессе развития и… Она существенно больше зависит от внешних условий. Различают несколько видов и… Эта связь может проявиться в следовании за любым движущимся объектом, впервые увиденным животным в первые часы жизни,…

0.036
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам