OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 19 Март, 2019 20:14

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
СообщениеДобавлено: Воскресенье, 10 Октябрь, 2010 17:22 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 769
Откуда: Казань
Многие языки семейства Оберон включают в себя сборщик мусора. В основном используется алгоритм Mark-and-Sweep. Сам по себе этот алгоритм не сложный, он основывается на том, что у нас имеется множество начальных указателей, с которых мы начинаем помечать объекты, как используемые, и так далее, если у объекта есть свои указатели, то и эти объекты помечаем как используемые. Далее можно добавить в список свободной памяти все объекты, которые оказались не помеченными.
Нахождение начального множества указателей не такое простое дело, как кажется. Это множество включает в себя глобальные переменные-указатели, локальные переменные-указатели, возможно, регистры, если в них временно хранится какой-нибудь указатель, который нигде больше не хранится. Множество глобальных переменных-указателей обычно сохраняется определенным образом в объектный файл и загручик получает эту информацию из объектного файла и соотвественно сборщик мусора знает, какие из глобальных переменных являются указателями.
А вот как определить какие из локальных переменных являются указателями?
Во многих книгах Никлауса Вирта, этот вопрос как-то обходится стороной. Например, в книге Project Oberon по поводу начальных указателей написано: "We shall postpone the question of how these roots are to be found, and first present a quick tutorial about tree traversal."
Возможно, в книге где-то упоминается реализация поиска начальных указателей в локальных переменных, просто я не нашел. Если кто укажет мне на раздел в книге и страницу, буду очень благодарен.
Возможно, у него есть отдельная статья, где он подробно описывает устройство сборщика мусора.

Проверил, как сборщик мусора устроен в системе BlackBox. В модуле Kernel есть следующая функция:
Код:
PROCEDURE MarkLocals;
        VAR sp, p, min, max: INTEGER; c: Cluster;
    BEGIN
        S.GETREG(FP, sp); nofcand := 0; c := root;
        WHILE c.next # NIL DO c := c.next END;
        min := S.VAL(INTEGER, root); max := S.VAL(INTEGER, c) + c.size;
        WHILE sp < baseStack DO
            S.GET(sp, p);
            IF (p > min) & (p < max) & (~strictStackSweep OR (p MOD 16 = 0)) THEN
                candidates[nofcand] := p; INC(nofcand);
                IF nofcand = LEN(candidates) - 1 THEN CheckCandidates; nofcand := 0 END
            END;
            INC(sp, 4)
        END;
        candidates[nofcand] := max; INC(nofcand);    (* ensure complete scan for interface mark*)
        IF nofcand > 0 THEN CheckCandidates END
    END MarkLocals;

Из которой следует, что проверяются не только указатели а все значения в стеке с шагом 4 байта. Если значение хранящееся в 4-х байтах лежит в интервала от min до max, то возможно это указатель и с него надо начинать проверку.
Как мне кажется это не совсем правильный алгоритм, так как если в какой-то переменной случайно окажется значение равное указателю на память, которое больше не используется, то память не будет освобождена, пока эта переменная не изменит свое значение.
Например, можно проделать следующий эксперимент:
Процедура внутри себя выделяет 600 мегабайт и вызывает себя рекурсивно, пока удается выделить память, или пока количество вызовов не достигнет 10. В данном примере, у меня выделяется 2 раза по 600 мегабайт, больше не может выделиться.
Код:
MODULE TestCollector;

    IMPORT Kernel, SYSTEM, Log;

    PROCEDURE Alloc(n: INTEGER);
    VAR p: POINTER TO ARRAY 150000000 OF INTEGER;
        a: INTEGER;
    BEGIN
        IF n < 10 THEN
            NEW(p);
            IF p # NIL THEN
                Log.String("OK"); Log.Ln;
                Alloc(n+1);
            ELSE
                Log.String("FAIL"); Log.Ln;
            END;
        END;
    END Alloc;
   
    PROCEDURE Do*;
    BEGIN
        Alloc(0);
    END Do;

END TestCollector.

Немного изменю программу. Теперь указателю присваивается NIL, и теоретически процедура может очень много раз себя вызвать, так как стоит ограничение 10 раз, то она выполнится 10 раз и остановится.
Код:
MODULE TestCollector;

    IMPORT Kernel, SYSTEM, Log;

    PROCEDURE Alloc(n: INTEGER);
    VAR p: POINTER TO ARRAY 150000000 OF INTEGER;
        a: INTEGER;
    BEGIN
        IF n < 10 THEN
            NEW(p);
            IF p # NIL THEN
                p := NIL;
                Log.String("OK"); Log.Ln;
                Alloc(n+1);
            ELSE
                Log.String("FAIL"); Log.Ln;
            END;
        END;
    END Alloc;
   
    PROCEDURE Do*;
    BEGIN
        Alloc(0);
    END Do;

END TestCollector.

А теперь рассматривается случай, когда в переменной типа INTEGER случайно оказалось значение равное указателю. Этот пример отработает только 2 раза, хотя по логике должен был бы отработать 10 раз, как и предыдущий пример.
Код:
MODULE TestCollector;

    IMPORT Kernel, SYSTEM, Log;

    PROCEDURE Alloc(n: INTEGER);
    VAR p: POINTER TO ARRAY 150000000 OF INTEGER;
        a: INTEGER;
    BEGIN
        IF n < 10 THEN
            NEW(p);
            IF p # NIL THEN
                a := SYSTEM.VAL(INTEGER, p);
                p := NIL;
                Log.String("OK"); Log.Ln;
                Alloc(n+1);
            ELSE
                Log.String("FAIL"); Log.Ln;
            END;
        END;
    END Alloc;
   
    PROCEDURE Do*;
    BEGIN
        Alloc(0);
    END Do;

END TestCollector.


В общем основной вопрос этого большого топика в том, как правильно реализовать поиск указателей в локальных переменных?


Последний раз редактировалось Rifat Воскресенье, 10 Октябрь, 2010 18:59, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 10 Октябрь, 2010 18:52 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2292
Откуда: Россия, Санкт-Петербург
http://tsya.ru/
Ни единой ошибки! : )


Последний раз редактировалось Александр Ильин Воскресенье, 10 Октябрь, 2010 20:17, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 10 Октябрь, 2010 19:06 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 769
Откуда: Казань
Сборщик мусора реализованный в BlackBox подходит под определение "conservative root scanning". "Conservative root scanning treats all bit patterns that happen to represent legal object addresses on the heap as if they were actual pointers to heap objects. This usually works well since it is unlikely that a random integer or float value on the stack is a legal object address, but it makes the memory management completely unpredictable."

А то что я ищу называется "exact root scanning". Реализовано в какой-либо из оберон систем "exact root scanning"? Если да, то где можно почитать об этом.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 10 Октябрь, 2010 21:21 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Посмотрите в A2, может быть там есть.

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

Стековая консервативность это ещё цветочки, вот в Mono до выхода версии 2.8 (она вышла на прошлой неделе) сборщик вёл себя консервативно в некоторых случаях и в куче. Начиная с Mono 2.8 консервативность сохранилась только по стеку.

На работе пишем программы под Mono. Летом 2009 года стала "течь память". Под Microsoft.Net - не стала, а под Mono стала. У Микрософта сборщик точный, а у Mono консервативный, вот и всё объяснение. Пришлось в срочном порядке переделывать программу так чтобы кэшировать объекты для повторного использования, заодно и производительность увеличили.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB