Курсовая: Динамическое распределение памяти - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

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

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 1671 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

Список - конечная последовательность , состоящая из нуля или б олее атомов или Списков. Рассмотрим Список 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 в неатомарных узлах , отправляясь от множества "непосредственно доступных " узлов. A 1 [Нач альная установка .] Отметить все "непосредственно доступные " узлы , т.е . узлы , указатели на которые находятся в фиксированных ячейках в главной программе и которые служат отправными пунктами для доступа ко всей памяти . Установить К 1. А 2. [Следует ли за NODE (К ) другой узел ?] Установить К К +1.Если NODE ( K ) - атом или немаркированный узел , то перейти к шагу А 3. В противном случае , если узел NODE ( ALINK ( K )) не отмечен , то отметить его и , если он не атом, установить К 1 min ( K 1, ALINK ( K )). Точно также , если узел NODE ( BLINK ( K )) не отмечен , то отметить его и , если он не атом , установить K 1 min ( K 1, BLINK ( K )). A 3. [Конец ?] Установить K K 1. Если K M , то вернуться к шагу А 2, в противном случае алгоритм завершен. Возможен несколько лучший вариант , предусматривающий использование стека фиксированного размера. Алгоритм B . (Маркировка .) В это м алгоритме используется таблица , содержащая Н я чеек STACK [0], STACK [1I, ... ..., STACK [ H -1] , и получается тот же результат , что и в алго ри тме А . В этом алгоритм е действие "занести Х в стек " озн а чает следующее : "Установить T ( T + l ) m od H и STACK [ T ] X . Если Т = В , то установить В (В + 1) mod Н и К 1 min ( Kl , STACK [В ]) ". (Заметим , что Т указывает на текущую " вершину " стека , а В указывает на одну позицию ниже текущего " низа " ; STACK работает , по существу , как дек , с ограниченным входом .) B 1. [Начальная уста н овка .] Установить Т Н -1, В Н -1, K l М + 1. Отметить все непосредственно доступные узлы и последовательно занести их адреса в стек (с помощью только что описанного действия ). B2. [Стек пуст ?] Если Т = В , перейти к B 5. BЗ . [Взять из стека верхний элемент .] Установить К STACK [Т ], T ( T - l ) m od H . B4 .[Ис сле до в ат ь связ и .] Если узе л NODE ( K ) - ато м , то вериуться К B2. В противном случае , если NODЕ (А L1 NK (К )) не отмечен , то отметить его и занести ALINK (К ) в стек . Аналогично , если NODE ( BLINK (К )) не отмечен , то отметить его и занести REF (К ) в стек . Вернуться к B2. B5. [Прочесать .] Если K 1>М, то алгоритм завершен . (Переменная К 1 представляет наименьший адрес , откуда имеется возможность вновь выйти на узел , который следует отметить .) В противном случае , если NODE ( KI ) н 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 восстанавливаются их прежние значения. D 1. [Начальная установка .] Установить Т , Р Р0 . (Далее в этом алгоритме переменная Т будет использоваться в двух смыслах : если Т , то она указывает на вершину того , что, по существу , является стеком , а узел , на который указывает Т , некогда содержал связь , равную Р , вместо "искусственной " стековой связи , находящейся теперь в NODE (Т ).) D2. [Отметить .] Установить MARK (Р ) 1. DЗ, [Атом ?] Если ATOM (Р ) = 1, то перейти к Е 6. D4. [Вниз по ALINK .] Установить Q ALINK (Р ). Если Q и MARK ( Q ) = 0, то установить ATOM (Р ) 1, ALINK ( Р ) Т , Т Р, P Q и перейти к D2. (Теперь поля ATOM и ALINK на время изменены и , следовательно , довольно радикально изменилась списочная структура в некоторых отмеченных узлах . Но в шаге D6 все будет восстановлено .) D5. [Вниз по BLINK .) Установить Q BLINK (Р ). Если Q и MARK ( Q )=0, то установить BLINK (Р ) Т , Т Р , Р Q и перейти к D2. D6. [Вверх .] (В этом шаге устраняются изменения связей , сделанные в шагах D4 или D5; значение АТОМ (Т ) говорит о том , какую из связей ALINK (Т ) или BLINK (Т ) следует восстановить .) Если Т = , алгоритм завершен . В противном случае установить Q Т . Если АТОМ (Q)=1, то установить ATOM (Q) 0, Т ALINK ( Q ), ALINK ( Q ) P , P Q и вернуться к D5. Если ATOM ( Q ) = 0, то установить Т BLINK (Q), BLIN К (Q) Р , Р Q и вернуться к D6. Блок-схема алгоритма D показана на рисунке , После После ALINK BLINK D 1.Н ач . D 2 . D 3. D 4. Вниз по D 5. Вниз по D 6. Вверх установка Отметить Атом ? ALINK Уже BLINK Уже Да отмечен отмечен Обратим внимание на то , что в шагах D4 и D5 искусственно изменяется списочная структура . Когда происходит возврат к предыдущему состоянию , поле ATOM говорит о том , какие из связей ALINK и BLINK со дер жат искусственные адреса . "Вложения ", показанные в нижней части рисунка служат иллюстрацией того , что в алгоритме каждый неатомарный узел посещается три раза Доказательство правильности алгоритма D можно построить , основываясь на индукции по количеству узл ов , которые подлежат маркировке . Одновременно доказывается , что в конце алгоритма Р = Р0 . Алгоритм D будет работать быстрее , если исключить шаг DЗ , а вместо него выполнить проверки " ATOM ( Q ) = 1" и соответствующие действия в шагах D4 и D5, а также проверку " ATOM (Р 0) = 1" в шаге D1. Идею , на которой построен алгоритм D, можно применить не только для сбора мусора , но и в других задачах. Время выполнения наилучших из известных программ сбора мусора выражается , по существу , формулой c 1 N +c2M , где c1 и c2 — конс танты, N - количество маркируемых узлов , а М - общее количество узлов в памяти . Таким образом , М - N - количество найденных свободных узлов , и время , которое расходуется на возврат одного такого узла в свободную память , составляет ( c 1 N + c2М )/(М -N). Пусть N = М ; тогда формула преобразуется к виду ( c 1 + c 2)/( l — ). Следовательно , если = 3/4 , т . е. память заполнена на три четверти , то п отребуется 3c1 + 4c2 единиц времени , чтобы вернуть в свободную память один узел ; если =1/4 , то соответствующая величина составляет лишь 1/3 c 1 + 1/4 c 2. Если сбор мусора не использ уется , то расход времени на один возвращаемый узел равен константе c 3 и , вне всяких сомнений , отношение c3/c1 будет очень велико . Отсюда мы можем видеть , до какой степени неэффективен сбор мусора , когда память становится полной , и соответственно , насколько он эффективен , когда требования к памяти невелики. Можно объединить сбор мусора с некоторыми другими методами возврата ячеек в свободную память ; эти принципы не исключают друг друга , и в некоторых системах используются как счетчик ссылок , так и схемы сбо ра мусора , а кроме того , программист может явно освобождать узлы .
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
У девушки обязательно должен быть любимый человек. И ещё тот, с кем можно будет иногда мстить этому козлу.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru