Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

if ptr <> null then

If ptr^.tag не отмечен then

установить ptr^.tag

mark (ptr^.llink)

mark (ptr^.rlink)

End if

End if

Выполнение данной процедуры для конкретного графа проиллюстрировано на следующем рисунке.

Штрихованными линиями показан порядок маркировки узлов.

Недостаток этого алгоритма – использова­ние значительного объема памяти для стека, поддерживающего рекурсию. Шорром и Уэйтом был разработан процесс маркировки, не требующий до­полнительной стековой памяти. Их метод основывается на перестановке указателей в об­ратном порядке при прохождении связных структур. В таком случае при достижении конца списка процесс может проследовать обратно за указателями к выходу.

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

Алгоритм маркировки для сборки мусора и процесс подсчета ссылок могут реализовываться значительно эффективнее при использовании циклического сдвига указателей и операций скольжения, описанных Сузуки.

Управление динамической памятью с ячейками переменно­го размера сопряжено с теми же трудностями, и кроме этого возникают дополнительные проблемы. Именно ячейки переменного размера требуются в большинстве языков программиро­вания. Дополнительные проблемы зависят от метода управления динамической памятью. При использовании сборки мусора их можно сформулировать следующим образом.

· Поскольку ячейки имеют переменный размер, их просмотр становится непростым. Одно из решений – поддержка для каждой ячейки поля размера. Просмотр занимает больше памяти и времени, чем его эквивалент для ячеек постоянных размеров.

· Процесс маркировки ячеек нетривиален. Как пройти цепочку, начавшуюся с указателя, если заранее не определено место расположения указателя в целевой ячейке? Другой проблемой являются ячейки, не содержащие указателей. Можно ввести системные указатели для каждой ячейки, но они должны под­держиваться параллельно с пользовательскими указателями. Этот подход снижает эффективность с точки зрения памяти и времени для выполне­ния программы.

· Нетривиально поддерживается список доступной памяти. Вначале этот список может состоять из одной ячейки, содержащей всю доступную память. Запросы на сегменты уменьшают размер этого блока. Освобожденные ячейки добавляются в список. Проблема заключается в том, что список пре­вращается в перечень блоков переменной длины. Это замедляет процесс размещения переменных в памяти, поскольку в ответ на запрос выполняется поиск блока достаточного размера. По прошествии некоторого вре­мени список может состоять из большого числа очень маленьких блоков, недоста­точных для удовлетворения большинства запросов. В этот момент может потре­боваться объединение смежных блоков в блоки больших размеров. В качестве аль­тернативы возможно использование первого достаточно большого блока в списке, что сократит поиск, но потребует упорядочения списка по размерам блока. В любом случае нужны дополнительные расходы на поддержание списка.

Если в качестве метода управления динамической памятью используются счетчики ссылок, то из трех перечисленных проблем остается только последняя.

4.11. Резюме

Стиль и использование языка программирования во многом определяется его типами данных, которые вместе с управляющими структурами формируют ядро языка. В число элементарных типов многих языков входят числовые, символьные и булевские типы. Числовые типы данных достаточно часто поддерживаются непосредст­венно аппаратным обеспечением.

Определяемые пользователем перечислимые и ограниченные типы удобны, а их ис­пользование повышает читабельность и надежность программ.

Другой компонентой большинства языков программирования являются массивы. Связь ме­жду ссылкой на элемент массива и адресом этого элемента в памяти описывается функцией доступа, которая представляет собой реализацию отображения. Массивы мо­гут быть статическими (как в языке FORTRAN 77); фиксированными автоматическими (как в процедурах Pascal); автоматическими (как в блоках языка Ada) или динами­ческими (в массивах ALLOCATABLE языка FORTRAN 90). В большинстве языков существует лишь ограниченное число операций с массивами как единым целым.

В синтаксис современных языков вошли записи. Поля записей задаются разнообразными способами. Например, в языках COBOL и PL/I ссылаться на них можно без указания всех префиксов, но реализация этой возможности беспорядоч­на, и читабельность программ при этом ухудшается. В таких объектно-ориентированных языках программирования как Java и C# записи поддерживаются объектно-ориентированной конструкцией.

Объединения – это ячейки памяти, которые могут содержать различные типы значе­ний в различные периоды выполнения. Размеченные объединения содержат метку для записи типа текущего значения. Свободным называется объе­динение без метки. Большинство объединений современных языков имеют небезопас­ную структуру, исключением является язык Ada.

Часто бывает удобно и относительно просто реализовать множества данных. Однако, задачи, для выполнения которых обычно используются множества, могут нетрудно решаться и с помощью других типов.

Целью использования указателей является достижение гибкой адресации и управление динамической памятью. Однако при использовании указателей возникает проблема вися­чих указателей, которую трудно обойти, и проблема мусора, который трудно собрать.

Управление динамической памятью без опасностей, характерных для указателей, обеспечивают ссылки подобные ссылкам в языках Java и C#.

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

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