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


1 Требования к динамической памяти в компонентных системах

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

Можно выделить два основных требования к динамической памяти в таких системах:
1. Защита от возможного взаимного повреждения, при сохранении единого адресного пространства.
Это означает, что никакие операции с памятью, выполняемые одним компонентом, не должны приводить к повреждению областей памяти, используемых другим компонентом.
2. Корректное и своевременное удаление динамических объектов, разделяемых компонентами.
Это означает, что а) никакой объект не должен удаляться, пока он используется хотя бы одним компонентом; б) если объект не используется никаким компонентом, он должен быть удалён за некоторое конечное время.

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

Инвариант 1 (И1)

для любого присутствующего в состоянии системы значения P, имеющего указательный тип
[ (P указывает на недоступную область памяти)
OR
(P указывает на существующий объект) &
(тип указуемого объекта соответсвует типу P) &
(на всём протяжении своего существования P указывает на один и тот же объект) ]

Инвариант 2 (И2)

[ для любого присутствующего в состоянии системы значения P, имеющего указательный тип
( (P = NIL)
OR
(P указывает на существующий объект) ) ]
&
[ существует конечное T > 0 такое, что
для любого существующего в системе динамического объекта D
некоторое время назад, меньшее T,
в состоянии системы существовало значение P указательного типа, указывающее на D ]


Средства обеспечения И1

Первоначально наложим ограничение:

1) в системе отсутствует возможность удаления динамических объектов.

Тогда в не-объектно-ориентированном языке И1 может быть обеспечен языковыми средствами на этапе компиляции. Для этого необходимо соответствие языка следующим требованиям:

2) неотъемлемой частью указательного типа является тип указуемого значения;
3) значения указательных типов порождаются либо одновременно с созданием объектов соответствующих типов, либо копированием уже существующих значений того же типа - и никаким другим образом (отсутствует операция взятия адреса произвольных объектов);
4) указательные типы являются герметичными: т.е. к ним применимы операции =, #, разыменование - и никакие другие;
5) операция разыменовывания имеет тип результата, строго соответствующий типу указателя.
6) не инициализированные явно указатели указывают на недоступную область памяти (имеют спец. значение NIL).

Объектно-ориентированный язык (допускающий расширение типов) добавляет полиморфизм, т.е. происходит "раздвоение" типа переменных на статический и динамический (являющийся произвольным расширением статического). Для указательных типов вводится операция проверки динамического типа и приведения базового типа к расширенному.
Чтобы обеспечить соблюдение И1, требуется способ во время выполнения определять фактический тип указуемого значения и проверять допустимость операции преобразования. Таким образом, обязательной частью каждого динамического объекта должен быть уникальный идентификатор типа. К перечисленным выше требованиям добавляется ещё одно:

7) подсистема времени выполнения должна поддерживать теги типов и их проверку при операциях преобразования типов.

Соблюдение совокупности требований 1-7 гарантирует истинность И1 на протяжении всей работы программной системы, независимо от ошибок, допущенных в исходном коде разработчиками её компонентов.


Операция удаления динамических объектов

Очевидно, что система, позволяющая создавать, но не позволяющая удалять динамические объекты, имеет весьма ограниченные возможности применения. Включение операции удаления динамических объектов несёт с собой две хорошо известных проблемы: а) "повисшие указатели" - при удалении объекта, на который ещё существуют указатели; б) "утечки памяти" - наличие объектов, на которые уже не осталось указателей и которые уже никогда не будут удалены. Фактически, эти две проблемы являются нарушениями соответствующих частей И2.

Утечки памяти сами по себе являются достаточно серьёзными, но при этом не вызывают нарушения И1. Образование висячих ссылок с высокой вероятностью может вести к нарушению И1. В наилучшем из возможных случаев память по адресу бывшего динамического объекта станет недоступной для чтения, и для "повисших указателей" будет соблюдена первая альтернатива И1 ("x указывает на недоступную область памяти"), т.е. при попытке обращения по таким указателям другие динамические объекты повреждены не будут, а произойдёт ошибка времени выполнения, аналогичная обращению по нулевому указателю. Однако диспетчер памяти при удалении динамического объекта может не освобождать страницу памяти, в которой он был размещён. Тогда ошибка времени выполнения генерироваться не будет. И наконец, в худшем случае (возможно, спустя продолжительное время), по этому же адресу будет размещён новый объект, что приведёт к нарушению И1 - т.е. повреждению компонентом, имеющим висячие ссылки, нового объекта.

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

Таким образом, единственным
cредством обеспечения И2
является отказ от ручного освобождения памяти и использование тех или иных механизмов автоматического освобождения.

Это даже в однопоточной компонентной системе.
А в параллельной системе начинается вообще веселье... Потому что совокупный эффект компонентности и параллельности...

И простой сборщик тут проблему не решает.
Активный Оберон, естественно, тоже поддерживает сборку мусора.

Однако имеется такая проблема:
выполняется некий активный объект. Он больше никому не нужен, на него нет ссылок снаружи. Но ведь на него есть ссылка из его собственного стека! Есть якорь! Сборщик не подбирает этот объект... И такое поведение явно специфицировано в стандарте языка.

ЧТо это значит? А то, что останавливать активные объекты приходится явно... Иначе они будут жить вечно, будучи "сами себе якорями"... Т.е. опять ручное управление, что противоречит идее компонентного программирования - если объект нужен многим, то откуда мы знаем, можно ли остановить его активность?

В Активном Блэкбоксе эту проблему я решил. В два этапа.
1) На уровне ядра введён механизм стоп-сигналов для потоков. Т.е. для каждого потока есть стоп-флаг, который этот поток циклически может проверять и по флагу завершиться - сам, корректным возвратом управления...
2) На уровне ядра введен механизм назначения потоку объекта-владельца. Сборщик мусора, трассируя якоря, не маркирует объект-владелец по ссылкам из стека собственного потока. Т.е. после этапа маркировки объекты, на которые нет якорей извне, а только из сосбтвенных потоков, остаются непомеченными. Далее, перед этапом сборки мусора, идёт этап остановки потоков. Проверяются объекты-владельцы для всех потоков. Как только обнаруживается что владелец никому не нужен, потоку выбрасывается стоп-флаг (естественно, никакой принудительной остановки...). Затем объект-владельцы принудительно маркируются, как доступные, чтобы их не прибить до остановки их потоков. Сборщик убирает мусор и заканчивает свой цикл. Активные объекты ещё могут работать - но через n-e время их потоки по проверке стоп-флага остановятся, и эти объекты перестанут быть активными - на следующем цикле сборщик их подберёт как самые обыкновенные "пассивные".

Публикации по активному Блэкбоксу есть здесь:
http://oberoncore.ru/index.php?option=com_content&task=blogcategory&id=14&Itemid=10
Плюс можно скачать в Дистрибутивам и сам АББ. Эта бета, которая никогда не станет релизом, просто пробный шар...
http://forum.oberoncore.ru/viewforum.php?f=31 - здесь её обсуждение.

В целом, в идее активных объектов я разочаровался.
Для системных задач (уровня ядра систем) удобнее и достаточнее простые мониторы в сочетании с потоками. С запретом рекурсивных входов.
А для основного программирования нужна асинхроника - ваши агенты сделаны в более правильном направлении, чем активные объекты. Но нужно идти ещё дальше. Кстати, Вы приходите к идее формализации протоколов - посмотрите описания Зоннона и Композиты (http://forum.oberoncore.ru/viewforum.php?f=33).
И есть конкретные идеи, которые будут воплощаться - на этот год нашей командой выигран госгрант на эти цели.

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

Необходимость сборщика давно обоснована специалистами по компонентно-ориентированному программированию, в частности - в книге К. Шиперски, в книге К. Пфистера (есть на OberonCore в секции "Блэкбокс", в русском переводе). Именно поэтому во всех версиях Оберона, поддерживающих динамическую модульность, есть и сборщик. Разработчики Компонентного Паскаля пошли ещё дальше - они прямо в стандарте языка указали, что реализация, не поддерживающая автоуправление памятью и метаинформацию, не соответствует стандарту.

2 Илья Ермаков:

Сегодня схематично в своем блоге набросал обоснование того, что нормальное многопоточное программирование врядли будет возможно, если язык не будет поддерживать сборку мусора:
http://stanonwork.blogspot.com/2007/08/blog-post.html
Конечно, по хорошему, необходимо некоторое формальное доказательство, что невозможно синхронизировать все активности так, чтобы их можно удалять явно (у меня там написано)...

Вы вроде бы занимаетесь подобными вопросами в BlackBox'е?! Кажется Вы говорили как-то об автоматической остановки активностей... Есть ли у Вас какие-нибудь публикации по этому поводу да и просто интересно мнение человека, который занимается этими вещами... :-)

Ответ на »сообщение 5061« (info21)
___________________________

... на форумах OberonCore.ru.

Разумеется, и там. Точнее, в теме "Оберон-07" http://forum.oberoncore.ru/viewtopic.php?f=30&t=615

Но трактовки (точки зрения) и краткое изложение сути изменений лучше все же дополнить непосредственным знакомством с приведенными мной работами Вирта.

Ответ на »сообщение 5058« (Руслан Богатырев)
___________________________

Некое предварительное представление о сути изменений, внесенных Виртом в классический Оберон, можно получить ...

... на форумах OberonCore.ru.

Ответ на »сообщение 5059« (Стэн)
___________________________

Ответ на »сообщение 5055« (Илья Ермаков)
___________________________
Я думал по этому поводу и пришел к тому, мы немного не с той позиции смотрим на компонентное ПО.
Слишком маленькие абстракции, слишком рано компилируется, учитывается только интерфейс связей, но не учитывается протокол взаимодействий...
Я считаю, что текущий способ решения задачи - "сборка программ из уже подготовленных абстракций" еще далек от совершенства. Надо думать... :-)

"Надо думать" - золотые слова :-) Равно как и про учёт протоколов взаимодействий...
Значит, буим думать... :-)

Ответ на »сообщение 5055« (Илья Ермаков)
___________________________

Ответ на »сообщение 5054« (Стэн)
___________________________
Да, приходится признать, что активные объекты с компонентным ПО плохо совместимы. После долгих размышлений прихожу к тем же выводам, о каких говорили Вы.
См. http://forum.oberoncore.ru/viewtopic.php?p=7598#p7598 - от этого сообщения и ниже.

Я думал по этому поводу и пришел к тому, мы немного не с той позиции смотрим на компонентное ПО.
Слишком маленькие абстракции, слишком рано компилируется, учитывается только интерфейс связей, но не учитывается протокол взаимодействий...
Я считаю, что текущий способ решения задачи - "сборка программ из уже подготовленных абстракций" еще далек от совершенства. Надо думать... :-)

Ответ на »сообщение 5056« (info21)
___________________________

Вирт закончил переработку сообщения об Обероне.
Оберон-07 будет вот-вот объявлен.

Некое предварительное представление о сути изменений, внесенных Виртом в классический Оберон, можно получить по этим его работам нынешнего года:

1. The Programming Language Oberon. revised for Strong-ARM 1.1.2007 / 1.6.2007.
http://www.inf.ethz.ch/personal/wirth/Articles/OberonSAReport.pdf

2. An Oberon Compiler for the ARM Processor. May 2007.
http://www.inf.ethz.ch/personal/wirth/Articles/OberonSACompiler.pdf

Ответ на »сообщение 5056« (info21)
___________________________

Интересно.