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

ГЛАВА 12

Управление памятью

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

12.1. Проблемы управления памятью

в работе компьютерных систем нередко возникают ситуации, когда ограниченными ресурсами основной памяти приходится управлять, т.е. разделять мевду несколькими совместно использующими ее "конкурентами". Программист, который никогда не занимался реализацией системных программ (компиляторов, операционных систем и т.п.), может даже не подозревать о существовании подобных проблем, поскольку действия, связанные с решением этих проблем, зачастую выполняются "за кулисами". Например, программисты, создающие программы на языке Pascal, знают, что процедура new(p) создает указатель р на новый объект (динамическую переменную) соответствующего типа. Но откуда берется пространство для хранения этого объекта? Процедура new имеет доступ к большой области памяти, называемой кучей (heap - динамически распределяемая область памяти), которая не используется переменными программы. Из этой области выбирается свободный блок последовательных байтов памяти, достаточный для хранения объекта того типа, на который указывает р, йър помешается адрес первого байта этого блока. По откуда процедуре new известно, какие байты памяти "свободны"? Ответ на этот вопрос читатель найдет в разделе 12.4.

Еше более удивительным является то, что происходит, когда значение указателя р изменяется то ли после операций присвоения или удаления, то ли после очередного обрашения к процедуре new(p). Блок памяти, на который указывал р, может оказаться недоступным в том смысле, что до него невозможно добраться посредством структур данных вашей программы и, следовательно, нельзя повторно использовать предоставляемое им пространство. С другой стороны, прежде чем изменять р, его значение можно было бы скопировать в какую-то другую переменную. В таком случае этот блок памяти по-прежнему оставался бы частью структур данных нашей программы. По как узнать, что тот или иной блок в области памяти, используемой процедурой new, больше не требуется вашей программе?

Подход к управлению памятью, используемый в языке Pascal, - лишь один из нескольких возможных. В некоторых случаях (например, в Pascal) одно и то же пространство памяти совместно используют объекты разных размеров. В других случаях все объекты, совместно использующие определенное пространство памяти, имеют

В русскоязьмной технической литературе (особенно переводной), посвященной управлению компьютерной памятью, нет единой вполне устоявшейся терминологии, поэтому в данной главе мы будем приводить как термины на русском языке (наиболее точные с нашей точки зрения), так и их англоязьмные эквиваленты. - Прим. ред.



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

1. В языке программирования Lisp пространство памяти делится на ячейки (cells), которые, по существу, представляют собой записи, состоящие из двух полей, при этом каждое поде может содержать либо атом (объект элементарного типа, например целое число), либо указатель на ячейку. Атомы и указатели имеют одинаковый размер, поэтому ддя всех ячеек требуется одинаковое количество байт. На основе этих ячеек можно создать любые известные структуры данных. Например, связные списки атомов могут использовать первые поля ячеек ддя хранения атомов, а вторые поля - ддя хранения указателей на следующие ячейки в списке. Двоичные деревья также можно представлять с помощью таких ячеек: содержимое первого поля каждой ячейки должно указывать на левого сына, а второго поля - на правого сына. При выполнении Lisp-программы пространство памяти, используемое ддя хранения ячеек, может оказываться - в разные моменты времени - частью нескольких различных структур; иногда это связано с тем, что ячейка передается из одной структуры в другую, а иногда с тем, что ячейка сразу же освобождается всеми структурами и может, таким образом, использоваться повторно.

2. Файловая система, вообще говоря, делит устройства вторичной памяти (например, диски) на блоки фиксированной длины. Например, UNIX, как правило, использует блоки по 512 байт. Файды хранятся в совокупности (не обязательно непрерывной) блоков. По мере создания и уничтожения файлов ддя повторного использования предоставляются блоки вторичной памяти.

3. Типичная мультипрограммная операционная система позволяет нескольким программам одновременно использовать основную память. Каждая программа располагает необходимым ей объемом памяти (известным операционной системе); потребность в памяти является составной частью запроса на обслуживание, выдаваемого в момент запуска программы на выполнение. В то время как в примерах 1 и 2 объекты, совместно использующие память (ячейки и блоки соответственно), имели одинаковые размеры, разным программам требуются разные объемы памяти. Таким образом, когда завершает свою работу программа, использующая, например, 100 Кбайт, вместо нее можно запустить на выполнение две программы, использующие по 50 Кбайт каждая, иди одну, которая использует 20 Кбайт, и другую, которая использует 70 Кбайт (в этом случае 10 Кбайт памяти останутся неиспользованными). С другой стороны, 100 Кбайт, освободившиеся в результате завершения работы программы, можно объединить с соседними неиспользуемыми 50 Кбайт, после чего можно запустить на выполнение программу, которой требуется 150 Кбайт памяти. Еще один вариант: ни одна из новых программ не умещается в освободившееся пространство, и 100 Кбайт временно остаются незанятыми.

4. Сушествует немало языков программирования, например Snobol, АРЕ иди SETL, которые выделяют пространство объектам произвольного размера. Этим объектам, которые представляют собой значения, присваиваемые переменным, выделяется бдок пространства из более крупного бдока памяти, часто называемого динамической памятью (heap). Когда значение переменной изменяется, новому значению выделяется пространство в динамической памяти; соответствующим образом корректируется и указатель ддя этой переменной - теперь он указывает на ее новое значение. Возможно, старое значение переменной уже не требуется, и занимаемое ею пространство может использоваться повторно. Однако в таких языках, как Snobol иди SETL, присвоения вида А = В реализуются путем изменения указателя: указатель ддя А теперь указывает на тот же объект, на который указывает указатель ддя В. Если йляА иди В выполнено новое присвоение, предыдущий объект не освобождается, а его пространство не подлежит повторному использованию.



Пример 12.1. Па рис. 12.1, а показана динамическая память, которая может использоваться Snobol-программой с тремя переменными: А, В и С. Значение любой переменной в Snobol является строкой символов, и в данном случае значением А и В является ОН HAPPY DAY, а значением С - PASS THE SALT4

Мы хотим хранить символьные строки с помощью указателей на блоки в динамической памяти. Первые 2 байта каясдого из этих блоков (число 2 является типичным значением, которое можно изменить) выделены для целого числа, указывающего длину строки. Например, длина строки ОН HAPPY DAY равна 12 байтам (с учетом пробелов между словами), поэтому значение А (и В) занимает 14 байт.

Если значение В заменить на ОН HAPPY DAZE, то необходимо подыскать в динамической памяти пустой блок длиной 15 байтов, включая 2 байта для указания длины. Далее выполняется корректировка указателя для переменной В так, чтобы он указывал на новое значение (рис. 12.1, б). Блок, содержащий целое число 12 и строку ОН HAPPY DAY, еще понадобится, поскольку на него указывает А. Если же изменить и значение А, этот блок будет уже бесполезен и подлежит повторному использованию. Мы еще вернемся в этой главе к вопросу о том, на основании каких признаков можно с уверенностью говорить об отсутствии указателей на такой блок. □

ОН HAPPY DAY

PASS THE SALT

OH HAPPY DAY

OH HAPPY DAZE 13

PASS THE SALT

Puc. 12.1. Строковые переменные в динамической памяти

В четырех приведенных выше примерах различия заметны, по крайней мере, по двум взаимно перпендикулярным "измерениям". Первый вопрос: имеют ли одинаковую длину объекты, совместно использующие память. В первых двух примерах (Lisp-программы и хранение файлов) объекты, которыми в одном случае являются Lisp-ячейки, а в другом - блоки, содержащие части файлов, имеют одинаковые размеры. Этот факт позволяет идти на определенные упрощения при решении задачи управления памятью. Например, в реализации Lisp область памяти делится на участки, каждый из которых может содержать ровно одну ячейку. Задача управления заключается в том, чтобы найти пустые участки, в которых могли бы разместиться вновь созданные ячейки. Аналогично, во втором примере диск делится на блоки одинакового размера; каждый блок предназначен для хранения определенной части одного файла: никогда не используется один блок для хранения частей нескольких файлов - даже если файл заканчивается посредине блока.

В третьем и четвертом примерах, где описывается выделение памяти в мультипрограммной системе и управление динамической памятью в языках, имеющих дело с переменными, значения которых представляют собой "большие" объекты, напро-

Значения переменных переводятся как "О, счастливый день" и "Передайте соль". - Прим. перев.

В данном случае значение переменной В обозначает "О, счастливое изумление". - Прим. перев.





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.0041