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

[Vitamin]

Это не годится для динамических связных структур данных.

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

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

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

сразу не может. но после последовательности освобождение-выделение вполне может случиться и такая ситуация.

Ничего не боюсь!
Одна куча на всю систему.
Со сборщиком мусора.
Кому не надо, не использует его.

одна куча на всю систему может быть только в нижней памяти. да и то она принадлежит системе. а у каждого процесса своя куча, которая рулится ЛЮБЫМ менеджером. по умолчанию- системным (без сборщика)

На какую тему?
Сборщик мусора встаёт поперёк дороги каким-то приёмам оптимизации?

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

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

LD HL,block1
CALL allocate
LD DE,dest
LD BC,len
LDIR

Весьма симпатично.

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

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

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

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

[Advertiser]

[captain cobalt]

Однако, ничто не мешает сделать сборщик мусора свойством оси.

[captain cobalt]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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 в пред. исходе)

[captain cobalt]

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

С третьей стороны, сборщик мусора особо не мешает при "обычном" программировании.

сразу не может. но после последовательности освобождение-выделение вполне может случиться и такая ситуация.

Если вся память исчерпана, то некоторая задача не сможет получить ещё памяти, даже если в кучах других задач есть мусор.

одна куча на всю систему может быть только в нижней памяти. да и то она принадлежит системе. а у каждого процесса своя куча, которая рулится ЛЮБЫМ менеджером. по умолчанию- системным (без сборщика)

Что-то я сомневаюсь, что обоснованно давать каждой задаче по куче. По той же причине перерасхода памяти с невозможностью перераспределения.

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

Да здравствует объединённый распределитель памяти!

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

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

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

Несомненно.
Но динамическое выделение (распределение) памяти в любом случае понадобится.

[Vitamin]

Что-то я сомневаюсь, что обоснованно давать каждой задаче по куче. По той же причине перерасхода памяти с невозможностью перераспределения.

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

Но динамическое выделение (распределение) памяти в любом случае понадобится.

с этим никто не спорит. вопрос в освободительской политике %)