Структуры данных и алгоритмы (1021739), страница 91
Текст из файла (страница 91)
Например, UNIX, как правило, использует блоки по 512 байт. Файлы хранятся в совокупности (не обязательно непрерывной) блоков. По мере создания и уничтожения файлов для повторного использования предоставляются блоки вторичной памяти.Типичная мультипрограммная операционная система позволяет нескольким программам одновременно использовать основную память. Каждая программа располагает необходимым ей объемом памяти (известным операционной системе);потребность в памяти является составной частью запроса на обслуживание, выдаваемого в момент запуска программы на выполнение. В то время как в примерах 1 и 2 объекты, совместно использующие память (ячейки и блоки соответственно), имели одинаковые размеры, разным программам требуются разные объемы памяти. Таким образом, когда завершает свою работу программа,использующая, например, 100 Кбайт, вместо нее можно запустить на выполнение две программы, использующие по 50 Кбайт каждая, или одну, которая использует 20 Кбайт, и другую, которая использует 70 Кбайт (в этом случае 10Кбайт памяти останутся неиспользованными).
С другой стороны, 100 Кбайт, освободившиеся в результате завершения работы программы, можно объединить ссоседними неиспользуемыми 50 Кбайт, после чего можно запустить на выполнение программу, которой требуется 150 Кбайт памяти. Еще один вариант: ни однаиз новых программ не умещается в освободившееся пространство, и 100 Кбайтвременно остаются незанятыми.Существует немало языков программирования, например Snobol, APL или SETL,которые выделяют пространство объектам произвольного размера.
Этим объектам,которые представляют собой значения, присваиваемые переменным, выделяетсяблок пространства из более крупного блока памяти, часто называемого динамической памятью (heap). Когда значение переменной изменяется, новому значениювыделяется пространство в динамической памяти; соответствующим образом корректируется и указатель для этой переменной — теперь он указывает на ее новоезначение. Возможно, старое значение переменной уже не требуется, и занимаемоеею пространство может использоваться повторно. Однако в таких языках, как Snobol или SETL, присвоения вида А = В реализуются путем изменения указателя:указатель для А теперь указывает на тот же объект, на который указывает указатель для В.
Если для А или В выполнено новое присвоение, предыдущий объект неосвобождается, а его пространство не подлежит повторному использованию.ГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮПример 12.1. На рис. 12.1, а показана динамическая память, которая может использоваться Snobol-программой с тремя переменными: А, В та С. Значение любойпеременной в Snobol является строкой символов, и в данном случае значением А и Вявляется 'ОН HAPPY DAY', а значением С — 'PASS THE SALT'1.Мы хотим хранить символьные строки с помощью указателей на блоки в динамической памяти.
Первые 2 байта каждого из этих блоков (число 2 является типичнымзначением, которое можно изменить) выделены для целого числа, указывающегодлину строки. Например, длина строки 'ОН HAPPY DAY' равна 12 байтам (с учетомпробелов между словами), поэтому значение А (и В) занимает 14 байт.Если значение В заменить на 'ОН HAPPY DAZE'2, то необходимо подыскать в динамической памяти пустой блок длиной 15 байтов, включая 2 байта для указания длины.
Далее выполняется корректировка указателя для переменной В так, чтобы он указывал на новое значение (рис. 12.1, б). Блок, содержащий целое число 12 и строку 'ОНHAPPY DAY', еще понадобится, поскольку на него указывает А. Если же изменить изначение А, этот блок будет уже бесполезен и подлежит повторному использованию.Мы еще вернемся в этой главе к вопросу о том, на основании каких признаков можно суверенностью говорить об отсутствии указателей на такой блок.
П1213ОН HAPPY DAY12 OH HAPPY DAYJ13 OH HAPPY DAZE | 13PASS THE SALTPASS THE SALTбPuc. 12.1. Строковые переменные в динамической памятиВ четырех приведенных выше примерах различия заметны, по крайней мере, подвум взаимно перпендикулярным "измерениям". Первый вопрос: имеют ли одинаковую длину объекты, совместно использующие память.
В первых двух примерах(Lisp-программы и хранение файлов) объекты, которыми в одном случае являютсяLisp-ячейки, а в другом — блоки, содержащие части файлов, имеют одинаковыеразмеры. Этот факт позволяет идти на определенные упрощения при решении задачиуправления памятью. Например, в реализации Lisp область памяти делится на участки, каждый из которых может содержать ровно одну ячейку. Задача управлениязаключается в том, чтобы найти пустые участки, в которых могли бы разместитьсявновь созданные ячейки. Аналогично, во втором примере диск делится на блокиодинакового размера; каждый блок предназначен для хранения определенной частиодного файла: никогда не используется один блок для хранения частей несколькихфайлов — даже если файл заканчивается посредине блока.В третьем и четвертом примерах, где описывается выделение памяти в мультипрограммной системе и управление динамической памятью в языках, имеющих делос переменными, значения которых представляют собой "большие" объекты, напро1Значения переменных переводятся как "О, счастливый день" и "Передайте соль".
—Прим. перев.2В данном случае значение переменной В обозначает "О, счастливое изумление". —Прим. перев.12.1. ПРОБЛЕМЫ УПРАВЛЕНИЯ ПАМЯТЬЮ341тив, говорится о выделении пространства блоками разных размеров. Это требованиесоздает определенные проблемы, которые отсутствуют при выделении блоков фиксированной длины. Например, мы стремимся избежать фрагментации — ситуации,когда неиспользуемое пространство достаточно велико, но настолько раздроблено, чтонайти свободный участок для размещения крупного объекта не представляется возможным. Подробнее об управлении динамической памятью мы поговорим в разделах 12.4 и 12.5.Второй важный вопрос заключается в том, каким именно способом, явным илинеявным, выполняется сборка мусора (garbage collection — чистка памяти) —"симпатичный" термин, обозначающий возврат в систему неиспользуемого пространства. Иными словами, речь идет о том, должна ли программа выдавать для этогоспециальную команду, или "сборка мусора" выполняется в ответ на запрос выделения пространства, который в противном случае оказалось бы невозможным выполнить.
Рассмотрим управление файлами. Когда выполняется удаление файла, файловой системе известны блоки, в которых хранился этот файл. Например, в файловойсистеме можно было бы хранить адреса одного или нескольких "главных блоков"каждого файла, созданного в этой системе. В этих блоках хранится список адресоввсех блоков, используемых для хранения соответствующего файла. Таким образом,когда выполняется удаление файла, файловая система может в явном виде вернутьдля повторного использования все блоки, в которых хранился этот файл.В отличие от описанного выше подхода, когда из структуры данных Lispпрограммы освобождаются ячейки, они продолжают занимать свое место в основнойпамяти. Из-за вероятности наличия нескольких указателей на одну ячейку нельзя суверенностью говорить, в каком именно случае ячейка освобождена полностью; таким образом, нет возможности в явном виде собирать ячейки примерно так, как собираются блоки удаленного файла.
Со временем все участки памяти будут выделенынужным и ненужным ячейкам, и следующий запрос на выделение памяти для очередной ячейки инициирует (в неявном виде) чистку памяти. В этот момент интерпретатор Lisp помечает все нужные ячейки (с помощью алгоритма, который мы рассмотрим в разделе 12.3), а затем связывает все блоки, содержащие ненужные ячейки, создавая на их основе список свободного пространства.В табл. 12.1 сведены четыре описанных вида управления памятью и приведеныпримеры каждого из них.
Мы уже обсуждали использование блоков фиксированногоразмера. Управление основной памятью в мультипрограммной системе являетсяпримером явной "утилизации" блоков переменной длины: когда программа завершает работу, операционная система, зная, какая область памяти была выделена этойпрограмме, и зная, что никакая другая программа не могла использовать это пространство, тотчас же делает это пространство доступным другой программе.Таблица 12.1. Примеры четырех стратегий управления памятьюУтилизация неиспользуемого пространстваРазмерблокафиксированныйпеременныйявная"сборка мусора"ФайловаясистемаLispМультипрограммнаясистемаSnobolУправление динамической памятью в языке Snobol и многих других языках про- *граммирования является примером использования блоков переменной длины при чистке памяти.
Как и в случае языка Lisp, типичный интерпретатор Snobol не пытается "отдавать" блоки памяти до тех пор, пока не столкнется с нехваткой памяти. Вэтот момент интерпретатор Snobol (как и интерпретатор Lisp) приступает к "сборкемусора". Правда, у интерпретатора Snobol появляется дополнительная возможность:342ГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮстроки "тасуются" в области динамической памяти с целью уменьшения фрагментации; кроме того, свободные смежные блоки объединяются, образуя более крупныеблоки. Обратите внимание, что две последние возможности в Lisp не используются.12.2. Управление блоками одинакового размераПредставим, что у нас есть программа, манипулирующая ячейками, каждая изкоторых состоит из пары полей; каждое поле может быть указателем на какую-либоячейку или содержать "атом".
Эта ситуация, конечно, характерна для любой программы, написанной на Lisp, однако такую программу можно написать практическина любом языке программирования, в том числе и на языке Pascal, если мы определим ячейки как записи (тип record). Пустые ячейки, которые можно включить в какую-либо структуру данных, указаны в списке свободного пространства, а каждаяпеременная программы представляется указателем на соответствующую ячейку.Указываемая ячейка может быть одной из ячеек более крупной структуры данных.Пример 12.2. На рис.
12.2 приведен один из возможных вариантов структуры сети ячеек. Здесь А, В и С — переменные, строчными буквами обозначены атомы. Обратим внимание на некоторые интересные явления. На ячейку, содержащую атом а,указывает переменная А и еще одна ячейка. На ячейку, содержащую атом с, указывают две разные ячейки. Ячейки, содержащие атомы g и А, необычны в том отношении, что хотя они и указывают друг на друга, до них невозможно "добраться" из переменных А, В и С; более того, они отсутствуют в списке свободного пространства.
ПАSаТтБ,ч£/6I"tс•*deQ1л> h Т9Свободныеэ—PП9•-Рис. 12.2. Сеть ячеекДопустим, что при выполнении программы из списка свободного пространствамогут периодически изыматься новые ячейки. Например, может понадобиться заменить нуль-указатель в ячейке с атомом с (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
