М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 27

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

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

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

Запрос и освобождение памяти

В процедурных языках программирования есть явные выражения или опера­торы запроса и освобождения памяти. Язык С использует malloc, функцию весьма опасную, поскольку в ней никак не проверяется соответствие выде­ленного объема памяти размеру указуемого объекта. Следует использовать функцию sizeof, даже когда это явно не требуется:

int*p = (int*)malloc(1); /* Ошибка */

int *p = (int *) malloc(sizeof(int)); /* Этот вариант лучше */

Обратите внимание, что malloc возвращает нетипизированный указатель, ко­торый должен быть явно преобразован к требуемому типу.

При освобождении памяти задавать размер блока не нужно:

free(p);

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

Языки C++ и Ada используют нотацию, из которой ясно видно, что созда­ется указуемый объект конкретного типа. При этом нет опасности несовме­стимости типа и размера объекта:

typedef Node *Node_Ptr;

Node_Ptr *p = new Node; // C++

type Node_Ptr is access Node;

P: Node_Ptr := new Node; --Ada

Оператор delete освобождает память в C++. Ada предпочитает, чтобы вы не освобождали память, выделенную в куче, потому что освобождение памяти опасно по существу (см. ниже). Конечно, на практике без освобождения не обойтись, поэтому применяемый метод назван освобождением без контроля (unchecked deallocation), и назван он так для напоминания, что его использова­ние опасно. Обратите внимание, что освобождаемая память — это область хранения указуемого объекта (на который ссылается указатель), а не самого указателя.

Повисшие ссылки

Серьезная опасность, связанная с указателями, — это возможность создания повисших ссылок (danglingpointers) при освобождении блока памяти:

int *ptr1 = new int; int *ptr2;

ptr2 = ptrl; // Оба указывают на один и тот же блок

result = delete ptrl; // ptr2 теперь указывает на освобожденный блок

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

Повисшие ссылки могут возникать также в С и C++ без какого-либо явно­го участия программиста в освобождении памяти:

char *proc(int i) /* Возвращает указатель на тип char */

{

char с; /* Локальная переменная */

return &c; /* Указатель на локальную переменную типа

char */

}

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

Ada пытается избежать повисших ссылок.

• Указатели на объекты (именованные переменные, константы и парамет­ры) запрещены в Ada 83; в Ada 95 они вводятся специальной конструк­цией alias, правила которой предотвращают возникновение повисших ссылок.

• Явного выделения памяти избежать нельзя, поэтому применяемый метод назван Unchecked Deallocation (освобождение без контроля) с целью предупредить программиста об опасности.

8.4. Алгоритмы распределения динамической памяти

Менеджер кучи — это компонент исполняющей системы, который выделяет и освобождает память. Это делается посредством поддержки списка свободных блоков. Когда сделан запрос на выделение памяти, она ищется в этом списке, а при освобождении блок снова подсоединяется к списку свободных блоков. Разработчик исполняющей системы должен рассмотреть много вариантов и принять проектные решения, в частности по порядку обработки блоков, их структуре, порядку поиска и т. д.

.

С распределением динамической области памяти связана проблема фраг­ментации. На рисунке 8.6 показана ситуация, когда сначала были выделены пять блоков памяти, а затем второй и четвертый освобождены. Теперь, хотя доступны 1000 байтов, невозможно выделить больше 600 байтов, потому что память раздроблена на небольшие блоки. Даже когда третий блок освободит­ся, памяти будет достаточно только при условии, что менеджер кучи «умеет» сливать смежные свободные блоки.

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

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

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

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

Виртуальная память

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

С помощью виртуальной памяти менеджер кучи может продолжать выде­ление динамической памяти почти бесконечно, не сталкиваясь с проблемой фрагментации. Единственный риск — это связанная с виртуальной памятью ситуация пробуксовки (thrashing), которая происходит, когда код и данные, требуемые для фазы вычисления, занимают так много страниц, что в памяти для них не хватает места. На подкачку страниц тратится так много времени, что вычисление почти не продвигается.

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

Последняя проблема, связанная с динамической памятью, — образование му­сора (garbage), например:

int *ptr1 = new int; // Выделить первый блок

int *ptr2 = new int; // Выделить второй блок

ptr2 = ptrl; // Второй блок теперь недоступен

После оператора присваивания второй блок памяти доступен через любой из указателей, но нет никакого способа обратиться к первому блоку (см. рис. 8.7). Это может и не быть ошибкой, потому что память, к которой нельзя об­ратиться, (называемая мусором) не может вам помешать. Однако, если про­должается утечка памяти, т. е. образуется мусор, в конечном счете программа выйдет из строя из-за недостатка памяти. Чрезвычайно трудно локализовать причину утечки памяти, потому что нет прямой связи между причиной и симптомом (недостатком памяти).

Очевидное решение состоит в том, чтобы не создавать мусор, прежде все­го тщательно заботясь об освобождении каждого блока до того, как он станет недоступен. Кроме того, исполняющая система языка программирования мо­жет содержать сборщик мусора (garbage collector). Задача сборщика мусора со­стоит в том, чтобы «повторно использовать» мусор, идентифицируя недоступ­ные блоки памяти и возвращая их менеджеру динамической памяти. Сущест­вует два основных алгоритма сборки мусора: один из них для каждого блока

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

Сборка мусора традиционно выполняется в таких языках, как Lisp и Icon, которые создают большое число временных структур данных, быст­ро становящихся мусором. Проведены обширные исследования по сборке мусора; особое внимание в них уделено параллельным и пошаговым мето­дам, которые не будут нарушать интерактивные вычисления или вычисле­ния в реальном масштабе времени. Eiffel — один из немногих процедур­ных языков, которые включают сборщики мусора в свои исполняющие системы.

8.5. Упражнения

1. Как представлен на вашем компьютере указатель? Как представлен на вашем компьютере указатель null?

2. Напишите на языке С алгоритм обработки массива с помощью индекса­ции, а затем измените его, чтобы использовать явные операции с указа­телями. Сравните получающиеся в результате машинные команды и время выполнения двух программ. Есть ли различие в оптимизации?

3. Покажите, как можно применить «часовых», чтобы сделать поиск в спи­ске более эффективным.

4. Почему не была использована операция адресации для фактического па­раметра, являющегося указателем на функцию:

float х = integrate(&fun, 1.0, 2.0);

5. Покажите, как можно использовать повисшие ссылки, чтобы разрушить систему типов.

6. Изучите в Ada 95 определение доступности (accessibility) и покажите, как правила предотвращают возникновение повисших ссылок.

7. Напишите программу обработки динамической структуры данных, на­пример связанного списка. Измените программу, чтобы использовать кэш узлов.

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

9. Если у вас есть доступ к компьютеру, который использует виртуальную память, посмотрите, как долго можно продолжать запрашивать память. При нарушении каких пределов выделение памяти прекращается?

Глава 9

Вещественные числа

9.1. Представление вещественных чисел

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

Характеристики

Список файлов книги