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

Курсовая

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

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

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

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 1671 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

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

Список - конечная последовательность , состоящая из нуля или б олее атомов или Списков. Рассмотрим Список 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 - 2016
Рейтинг@Mail.ru