лекция 8 (Языки программирования (лекции) (2008))

Языки программирования. Лекция 8.

Указатели и ссылки (продолжение)

Изначально указатели используются в двух видах:

1. Ссылки на объекты из динамической памяти (Ада, Модула2 и Паскаль используют указатели только в таком виде)

2. Используется понятие адреса, понятно, что с помощью адреса можно ссылаться на любые объекты

В Си и Си++ указатели участвуют и в работе с динамической памятью, а также используются как низкоуровневая абстракция понятия адреса.

Возникают различные проблемы, связанные с понятием указателя:

1. Смещение адресов

T *p;

p = &a; // если переменная а является локальной, т.е. объявленной где-то в стеке, а указатель является глобальным по отношению к стеку, то в этой точке значение указателя определено, но он указывает "в никуда". Попытка разыменования указателя приводит к доступу к содержимому стека, которое не является актуальным.

// если а статическая переменная, то free(p); - ошибка, которую тяжело определить, могут помочь только отладочные версии библиотеки управления памятью.

2. Проблема висячих ссылок

проблема висячих ссылок возникает даже в языках, в которых нет смешения адресов, в связи с тем, что явно присутствуют механизмы освобождения памяти. Например:

T *p1, *p2;

p1 = new T;

p2 = p1; // в результате p1 и p2 указывают на один объект.

delete p1; // в результате разрушается ссылка р1 на объект, сам объект уничтожается, а ссылка р2 остается висячей. После этого можно написать *p1;

а) до удаления

p2

б) после удаления

р1

р2

Один из типичных примеров:

while (p != NULL) {

free(p);

p = p->next; //пример работы с висячей ссылкой – р уже освобождена, а мы работаем с ней} (*)

Чем сложна проблема висячих ссылок? Если прогнать кусок (*) в разных средах, разных вычислительных системах и в разных конфигурациях – результат везде будет разный. В VC++ Debug – немедленно сообщение об ошибке, Release - возможно никакой ошибке зафиксировано не будет. Почему так происходит? Если представить одно поточное приложение, то у каждого такого приложения свой менеджер динамической памяти. Менеджеру памяти по оператору free сообщаем, что блок памяти на больше не нужен, но обычно менеджер ничего с этой памятью не делает. Только в том случае, если другой поток запросит операцию calloc (malloc и т.д.), и в процессе выполнения операции память утилизируется и в нее будет что-то записано, тогда только и произойдет порча памяти. А в примере с циклом – память освобождается, но ее содержимое не стирается. Если у нас многопоточное приложение, то (*) - не единственный поток команд. Менеджер памяти обычно тоже используется несколькими потоками и в этом случае никто не гарантирует, что после free управление вернется тому же потоку. Другой поток может запросить и испортить эту память. И в примере с циклом на следующей операции мы можем влезть и освободить уже чужую память. При этом если разные потоки одного процесса – никто не отловит не точность. Такие ошибки возникают исключительно из-за некорректного освобождении памяти.

3. Мусор

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

T *p1;

p1 = new T;

p1 = new T; // старое значение теряется. И на этот участок памяти больше ничего не ссылается. Сообщение об ошибке не выдаётся.

а)

б)

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

А)замедление работы приложения (при каждом прогоне приложения – виртуальная память загрязняется все больше)

Б)в некоторой момент оператор new откажет – при нехватке памяти

Мусор очень трудно обнаружить – в основном проявляется на стадии эксплуатации.

Пункты 2 и 3 относятся только к указателям, которые работают с элементами динамической памяти и обусловлены только наличием явного оператора освобождения динамической памяти (delete).

Рассмотрим способы борьбы с рассмотренными проблемами.

1. не надо смешивать адреса – так яп Ада, Модула2 и Паскаль отличаются тем, что указатели используются исключительно для работы с объектами динамической памяти. Никакого смешения не происходит ни в одном из рассмотренных случаев.

В Паскале есть процедуры NEW(P) – отведение объекта динамической памяти и DISPOSE(P) извлечения.

В Ада:

type PT is access T;

x:PT;

X := new T; //размещаем объект в динамической памяти

Нет понятия адресной операции, нарушая систему контроля типов можно совершить следующие вещи:

Y:T;

Y' ADDRESS //такие действия используются для низкоуровнего программирования и делают программу нестандартизованной

В Модуле2 операция ADR возвращает адрес переменной, но опять же использование таких конструкций не приветствуется и делает программу ненадежной.

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

а) приходится рассматривать указатели на нединамические объекты

б) новые конструкции должны быть надежные

type PT is access T; //старый указательный тип

X:PT;

a:T;

X:= a' access; // - ошибка

Есть специальный атрибут access операции access – это получение адреса от нединамической переменной а.

type PTT is access all T;// объекты PTT могут адресовать произвольные объекты типа T

Y: PTT;

X:=new T; //единственное что можно сделать с объектом типа PT

Y :=new T; // допустимо

Y:=X; //допустимо

Y:= a' access; // допустимо

Именно объекты типа PTT можно передавать в произвольные программы, в тоже время компилятор относится осторожно к таким объектам.

X:=Y; // Запрещено

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

2. рассмотрим методы борьбы с висячими ссылками.

А) Метод с использованием надгробий.

p1 = new T; // в данном методе считается, что указатель р1 указывает не на объект динамической памяти, а на надгробие. Надгробие - это специальная ячейка памяти, которая всегда указывает на объект. Надгробие появляется как только появляется сам объект динамической памяти. И все указатели ссылаются не на сам объект, а на надгробие.

p2 = p1; // переприсваиваются адреса надгробий

delete p1; // а надгробие заносится нулевой адрес, заметим что у указателя не может быть нулевого адреса, каждый указатель всегда должен ссылаться на какое-нибудь надгробие.

*p2 (разыменование р2 после delete p1) // ошибка, и она будет обнаружена именно в тот момент когда она возникла, т.е. при любой попытке разыменования р2

В современных языках такой алгоритм не используется, потому что

1) у нас тратиться место на добавления ячейки-надгробия

2) получается двойная операция разыменования – вначале разыменовываем указатель, получая доступ к надгробию, а потом вынуждены разыменовывать надгробие

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

Б) Метод ключей и замков.

Этот метод также основан на дополнительном выделении памяти, а именно с самим объектом связана некоторая ячейка с целочисленным значением, называемым замком, а указатель состоит из пары – ключ адрес. Дополнительная память идет на ключ и на замок. В момент появления объекта, генерируются ключ и замок, которые получают одно и тоже значение. И операция с этим указателем разрешается только если ключ равен замку.

р1 = р2; // копируется и адрес и соответствующий ключ

delete p1; // замку присваивается какое-то недопустимое значение

*p2 (попытка разыменования р2) // уже вызывает ошибку поскольку уже ключ и замок не совпадают

Заметим, что происходит единственное обращение к памяти и данная схема немного более эффективна, чем схема с надгробиями.

3. рассмотрим методы борьбы с висячими ссылками

Создатели языка Ада решали эту проблему с использованием того, что нет смешения типов. Только указатели могут ссылаться на объекты динамической памяти. И как только такие указатели (если являются локальными переменными) прекращают свое существование и объекты, на которые они ссылаются могут прекратить свое существование.

Проблема полностью не решена так как такие могут ссылаться на глобальные переменные. Проблему может решить только автоматический сборщик мусора. Сейчас он во многих современных яп (Java, Cи#, Оберон). Существуют два основных подхода к методам сборки мусора:

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

p2 = new T

p1 = p2;(**)

Когда отводиться объект в динамической памяти, выделяется дополнительная память к объекту, в которой содержится количество ссылок на объект. В начале после new(T) счетчик равен нулю. При каждом присваивании счётчик ссылок увеличивается на 1 (в (**) для объекта, на который указывал р2 счетчик увеличивается, а для объекта, на который указывал р1 уменьшается), если указатель является локальным и уходит из области видимости то счетчик уменьшается. Как только счётчик ссылок становится равным 0, объект никому не нужен, в принципе менеджер памяти имеет право его использовать в данный момент. Главный недостаток - с каждым объектом связывается счётчик ссылок и появляются дополнительные накладные расходы.

2. Пассивный метод (применяется в динамических языках типа ЛИСПа) - mark-and-scan, сборка мусора.

При каждом объекте памяти выделяется дополнительный бит, указывающий, используется объект или нет. В начале все объекты помечаются как неиспользованные. Как только объект отводится в память – то используется (бит = 0). При этом объект, на который указывал р1 не помечается как неиспользованный. В определенный момент не хватает памяти для операции new, когда все объекты используемые включается сборщик мусора. Он проходит по всем указателям и помечает реально используемые объекты памяти, а те которые им не помечаются- считаются неиспользуемыми.

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

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

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

Последнее замечание о простых типах данных.

Нужны ли простые типы данных вообще? Существует язык объектно-ориентированный язык SmallTalk, в котором конструкция 5+3 рассматривается так, объект 5 посылает сообщение "+" объекта 3 и в результате получается объект 8. В SmallTalk есть только тд, встроенные в язык, и все тд являются объектами. У объектов есть методы, и объекты общаются путем посылки сообщений. Сообщение - имя(параметры). Например, у методы «+» есть два параметра – сам объект и объект, которому посылается сообщение. Объект, которому посылается сообщение, просматривает таблицу методов, если у него есть методы, которые обрабатывают полученное сообщение, то происходит некоторые действия (в примере - операция «+»).

Такой стиль программирования очень удобен – когда все рассматривается единообразно, как объекты с методами и свойствами. Однако простые тд остаются в языках, так как все объекты в современных яп размещаются в динамической памяти, и работа с ними весьма накладна. В Си# и Java используется некий компромисс, а именно для каждого простого тд существует класс-обертка. Для каждого тд, встроенного в язык существует тд, который представляет из себя класс (так для int существует класс integer в Java, или int32 в Си#). Понятие обертка это из Java, а для Си# существует CLR, где объявлены и описаны все процедуры и функции с соответствующими классами. Таким образом, когда нам надо работать с объектами простых тд как с переменными и значениями, мы работаем как в Си, если нам нужны их объектные свойства, тогда происходит моментальная обертка, т.е. преобразование в соответствующий класс (в Си# такой процесс получил название Boxing, а обратный Unboxing). В частности в результате в этих языках решена проблема передачи параметров.