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

[SfS]

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

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

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

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

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

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

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

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

[Advertiser]

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