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

[captain cobalt]

для реализации сборки мусора не нужна многозадачная ось или потоки. никто не мешаеть позвать его автоматически в тот момент когда кончилась память (из системной функции new).

Абсолютно верно.

другой вариант, пользовательская программа может сама время от времени звать сборщика (тогда когда она считает нужным: в момент ожидания пользовательского ввода, после окончания ресурсоемкого куска)

Абсолютно верно.

сборка мусора никак не связана с виртуальными машинами/байткодом. есть библиотеки для C++ реализующие сборку для некоторых частных случаев

Абсолютно верно.

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

Сборщику мусора необходимо сообщить обо всех существующих указателях.

все еще предлагаю решить простейшую задачу:
1. программа попросила 200 байт памяти, вызвав системную функцию new/malloc
2. указатель на блок памяти нам вернули (в HL или записали куда-то еще в память)
3. мы этот блок использовали и он нам больше не нужен

как сборщик памяти сможет это понять и вернуть память в систему?

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

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

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

Будут полноценные malloc и free - тогда можно и о большем думать...

А можно поднатужиться, и сразу родить сборщик мусора. Тогда и free не понабодится.

[Advertiser]

[Vitamin]

А
Сборщик мусора знает обо всех указателях. Для того, чтобы "сообщить", что память больше не нужна, нужно в указатель в памяти записать другое значение (например, нулевой указатель - ни на что не указывающий). Когда сборщик мусора при следующем запуске не найдёт живых указателей на блок памяти, он объявит его мусором.

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

[elf/2]

как сборщик памяти сможет это понять и вернуть память в систему?

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

приехали
два основных типа ошибок связанных с работой с памятью это:
1. забыли освободить память
2. обратились к уже освобожденной памяти

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

про работу с динамическими связными структурами.
довольно часто используют такой подход: программа имеет свой менеджер памяти который берет память у системы большими кусками, а после окончания работы со структурой отдает ее сразу всю.
поскольку в таких структурах элементы одного типа - менеджер получается простой и очень эффективный. а C++ предоставляет все необходимое для его реализации (перегрузка оператора new)

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

для простоты: элемент списка содержит один байт данных, глобальный массив всех выделенных указателей изначально пуст и находится по адресу #8000, куча тоже пустая и лежит начиная с #c000
пытался нарисовать сам не смог...

[Знахарь]

Народ!!!! АУ!!!! Не далеко ль Вы полезли ? шо то я от ваших указателей одурел А как z80 одуреет ?

Может кто расписать на пальцах как это всё чудище будет работать ?

Вот надо мне не 200 байт, а скажем 70 килобайт для игры. И чтоб на прерываниях мизер системы. И чтоб оба экрана юзать... Да хрен с ним, хоть один, основной. И понятно, что не где попало память нужна... короче КАК это всё будет выглядеть реально ?

[SfS]

Вставлю свои пять копеек.

Я организовывал в программах, которые много работали с выделением-освобождением памяти следующее:

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

При выделении памяти - число элементов списка увеличивается. При освобождении - уменьшается, причем соседние свободные элементы объединяются в один.

Для списка хранится указатель на его голову и текущий элемент (последний выделенный участок памяти).

Таким образом при использовании free(void* ptr) экономится время, поскольку просматривается не весь список, а только элементы, соседние с удаляемым.

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

ИмХО, такой подход более расточителен по памяти, зато много головных болей устраняет.

[Vitamin]

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

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

Структура неявного однонаправленного списка:

2 байта - размер выделенной области.
14 Бит - флаг занятости цепочки
15 бит - флаг окончания списка.
(Наибольший размер выделяемой свободной памяти при этом 16384б.)

Выделение памяти:
LD HL,SIZE - размер
CALL ALLOC

Освобождение памяти:
LD HL,ADDR - адрес цепочки
CALL FREE

Можно применить для любой 16Кб области как в основной памяти, так и в страничной.

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

list_descriptor
head dw blk1
tail dw blk3 ;?
lock db 0

...
blk1 dw 0 ;previous==NULL - first one
dw blk2
...
blk2 dw blk1
dw blk3
....
blk3 dw blk2
dw 0 ;next==NULL - last one

вот и все. и хранить флаги начала/конца списка абсолютно не нужно.

пример списка применительно к менеджеру памяти. пустая куча:
head dw heap
tail dw heap
...
heap dw 0
dw 0
dw heap_len

выделили 200 байт. структура будет следующая:

head dw blk1
tail dw blk1
...
heap

;heap+200
blk1 dw 0
dw 0
dw heap_len-200

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

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

если использовать стандартные библиотеки для работы со связными списками, то в описывающей список структуре можно предусмотреть защелку для синхронизации (см. lock в пред. исходе)