Главная Промышленная автоматика.

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

Второй важный вопрос заключается в том, каким именно способом, явным или неявным, выполняется сборка мусора (garbage collection - чистка памяти) - "симпатичный" термин, обозначающий возврат в систему неиспользуемого пространства. Иными словами, речь идет о том, должна ли программа выдавать для этого специальную команду, или "сборка мусора" выполняется в ответ на запрос выделения пространства, который в противном случае оказалось бы невозможным выполнить. Рассмотрим управление файлами. Когда выполняется удаление файла, файловой системе известны блоки, в которых хранился этот файл. Например, в файловой системе можно было бы хранить адреса одного или нескольких "главных блоков" каждого файла, созданного в этой системе. В этих блоках хранится список адресов всех блоков, используемых для хранения соответствующего файла. Таким образом, когда выполняется удаление файла, файловая система может в явном виде вернуть для повторного использования все блоки, в которых хранился этот файл.

В отличие от описанного выще подхода, когда из структуры данных Lisp-программы освобождаются ячейки, они продолжают занимать свое место в основной памяти. Из-за вероятности наличия нескольких указателей на одну ячейку нельзя с уверенностью говорить, в каком именно случае ячейка освобождена полностью; таким образом, нет возможности в явном виде собирать ячейки примерно так, как собираются блоки удаленного файла. Со временем все участки памяти будут выделены нужным и ненужным ячейкам, и следующий запрос на выделение памяти для очередной ячейки инициирует (в неявном виде) чистку памяти. В этот момент интерпретатор Lisp помечает все нужные ячейки (с помощью алгоритма, который мы рассмотрим в разделе 12.3), а затем связывает все блоки, содержащие ненужные ячейки, создавая на их основе список свободного пространства.

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

Таблица 12.1. Примеры четырех стратегий управления памятью

Утилизация неиспользуемого пространства

явная

"сборка мусора"

Размер

фиксированный

Файловая система

Lisp

блока

переменный

Мультипрограммная система

Snobol

Управление динамической памятью в языке Snobol и многих других языках про- * граммирования является примером использования блоков переменной длины при чистке памяти. Как и в случае языка Lisp, типичный интерпретатор Snobol не пытается "отдавать" блоки памяти до тех пор, пока не столкнется с нехваткой памяти. В этот момент интерпретатор Snobol (как и интерпретатор Lisp) приступает к "сборке мусора". Правда, у интерпретатора Snobol появляется дополнительная возможность:



строки "тасуются" в области динамической памяти с целью уменьшения фрагментации; кроме того, свободные смежные блоки объединяются, образуя более крупные блоки. Обратите внимание, что две последние возможности в Lisp не используются.

12.2. Управление блоками одинакового размера

Представим, что у нас есть программа, манипулируюшая ячейками, каждая из которых состоит из пары полей; кавдое поле может быть указателем на какую-либо ячейку или содержать "атом". Эта ситуация, конечно, характерна для любой программы, написанной на Lisp, однако такую программу можно написать практически на любом языке программирования, в том числе и на языке Pascal, если мы определим ячейки как записи (тип record). Пустые ячейки, которые можно включить в какую-либо структуру данных, указаны в списке свободного пространства, а каждая переменная программы представляется указателем на соответствуюшую ячейку. Указываемая ячейка может быть одной из ячеек более крупной структуры данных.

Пример 12.2. Па рис. 12.2 приведен один из возможных вариантов структуры сети ячеек. Здесь А, В и С - переменные, строчными буквами обозначены атомы. Обратим внимание на некоторые интересные явления. Па ячейку, содержащую атом а, указывает переменная А и еше одна ячейка. Па ячейку, содержащую атом с, указывают две разные ячейки. Ячейки, содержащие атомы g я А, необьины в том отношении, что хотя они и указывают друг на друга, до них невозможно "добраться" из переменных у1, 5 и С; более того, они отсутствуют в списке свободного пространства. □


Свободные

Рис. 12.2. Сеть ячеек

Допустим, что при выполнении программы из списка свободного пространства могут периодически изыматься новые ячейки. Например, может понадобиться заменить нуль-указатель в ячейке с атомом с (см. рис. 12.2) указателем на новую ячейку, которая содержит атом i и нуль-указатель. Эта ячейка будет изъята из вершины списка свободного пространства. Возможно таюке, что время от времени указатели будут изменяться таким образом, что переменные программы станут освобовдать занятые ими ячейки, как это случилось, например, с ячейками, содержащими g и А, на рис. 12.3. Например, ячейка, содержащая с, может в какой-то момент указывать на ячейку, содержащую g. Или еше один пример: значение переменной В может в какой-то момент измениться, что приведет (если не изменится что-либо еше) к освобо-вдению ячейки, на которую сейчас на рис. 12.2 указывает В, а таюке ячейки, со-

12.2. УПРАВЛЕНИЕ БЛОКАМИ ОДИНАКОВОЕО РАЗМЕРА



держащей due (но не ячейки, содержащей с, поскодьку она по-прежнему будет доступна из А). Ячейки, на которые невозможно перейти ни из одной переменной и которые отсутствуют в списке свободного пространства, называются недоступными.

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

Контрольные счетчики

Весьма привлекательным подходом к выявлению недоступных ячеек является включение в каждую ячейку так называемого контрольного счетчика, или счетчика ссылок (reference count), т.е. целочисленного поля, значение которого равняется количеству указателей на соответствующую ячейку. Работу такого счетчика обеспечить несложно. С момента создания указателя на какую-либо ячейку значение контрольного счетчика ддя этой ячейки увеличивается на единицу. Когда переназначается ненулевой указатель, значение контрольного счетчика ддя указываемой ячейки уменьшается на единицу. Есди значение контрольного счетчика становится равным нулю, соответствуюшая ячейка оказывается невостребованной и ее можно вернуть в список свободного пространства.

К сожалению, контрольные счетчики иногда не срабатывают. Ячейки с g и h на рис. 12.2 являются недоступными ячейками, образующими цикл. Значения их контрольных счетчиков равны 1, поэтому нельзя вернуть эти ячейки в список свободного пространства. Разумеется, есть способы обнаруясения циклов недоступных ячеек, но эффективность таких способов невелика. Контрольные счетчики удобно использовать в структурах, в которых невозмолшо появление циклов указателей. Примером подобной структуры является совокупность переменных, указывающих на блоки, содержащие данные (см. рис. 12.1). В этом случае можно выполнять явную чистку памяти. Ддя этого достаточно просто "подобрать" бдок, когда значение его контрольного счетчика становится равным нулю. Однако когда структуры данных допускают появление циклов указателей, метод контрольных счетчиков оказывается неэффективным - как с точки зрения пространства, требующегося ддя его реализации, так и с точки зрения времени, затрачиваемого на решение проблемы недоступных ячеек. Более эффективным в этом случае оказывается другой метод, который мы обсудим в следующем разделе.

12.3. Алгоритмы чистки памяти для блоков одинакового размера

Рассмотрим алгоритм, позволяющий определить, к каким ячейкам, показанным на рис. 12.2, возможен доступ из переменных программы. Точную постановку задачи можно выполнить, определив тип ячейки, который в языке Pascal будет представлен определенным типом записи. Четыре варианта, которые мы обозначим РР, РА, АР и АА, определяются тем, какие из двух полей данных являются указатедями, а какие - атомами (Р обозначает поде указателя (от pointer - указатель), А - поде атома). Например, РА означает, что левое поде является указателем, а правое поде - атомом. Дополнительное булево поде в ячейках, называемое mark (метка), показывает, является ди данная ячейка свободной, т.е. установив при "сборке мусора" ддя поля mark значение true, мы помечаем соответствующую ячейку как доступную ддя последующего использования. Определения типов данных показаны листинге 12.1.





0 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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 [110] 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0026