Автор:
Хищник
первая публикация 12.10.2008 на
данном форуме
Реализация простейшего алгоритма сборки мусора на Форте
Одной из важных проблем при разработке программ является управление памятью. Это понятие включает в себя различные операции, но наибольшие проблемы возникают, когда программе требуется динамическое выделение памяти, т.е. создание и уничтожение областей памяти в процессе работы. При этом может возникнуть явная проблема, когда программа пытается воспользоваться памятью, которую ошибочно считает своей, и более опасная из-за своей скрытности ситуация, когда программа с точки зрения ОС удерживает за собой область памяти, но потеряла ссылки на нее, так что вынуждена запрашивать все новые и новые области для той же цели (это называется утечкой памяти). Утечка обычно возникает, когда из-за логических ошибок программе не удается выполнить операцию уничтожения области памяти (на самом деле под этим понимается уведомление операционной системы, что память больше не требуется программе и может быть использована для других нужд).
Одним из кардинальных методов борьбы с утечками является использование автоматических процедур удаления неиспользуемых областей памяти. В этом случае программа только выделяет память, но не уничтожает ее, оставляя эту операцию т.н. сборщику мусора (garbage collector). Сборщик мусора хранит информацию об областях памяти, которые затребовала себе программа, и при необходимости помечает их как неиспользуемые. При этом после нескольких операций выделения и уничтожения в памяти могут возникать неиспользуемые участки (или, другими словами, память становится фрагментированной). Однако вместо попыток «вписать» новый блок памяти в подходящий свободный участок сборщик мусора может использовать другой интересный алгоритм. Дело в том, что программы, интенсивно создающие и уничтожающие объекты в памяти, существенно замедлят управление памятью из-за необходимости постоянно дефрагментировать память или искать подходящий свободный блок (что тоже способствует фрагментации). Вместо этого сборщик выделяет память с постоянным нарастанием адресов, только помечая удаленные блоки. Рано или поздно память, доступная сборщику, будет исчерпана, однако в ней окажется много блоков, помеченных как свободные. В этом случае выполняется сборка мусора – физическое перемещение блоков памяти, которые последовательно занимают место в общем блоке, выделенном для сборщика мусора. Операция сборки мусора обычно занимает заметное время, так что программа, использующая такой алгоритм управления памятью, работает достаточно быстро, но с периодическими «замираниями».
Поскольку при дефрагментации области памяти физически перемещаются, программа не может просто запомнить адрес, где находятся нужные данные (они могут оказаться перемещены в процессе сборки мусора). Поэтому к таким областям следует обращаться только через менеджер памяти, передавая ему идентификатор нужного блока.
Пример управления памятью со сборкой мусора приведен ниже. В программе создается большая область памяти (переменная LIMIT содержит максимальный размер, который можно запросить у системы, из него вычитается величина c#RESERVED, которая оставляется программе для обычного выделения по ALLOT). Полученная область рассматривается как куча (heap), и ей управляет таблица на c#HEAP-ENTRIES записей. Для каждой записи хранится начальный адрес и размер этого блока памяти. Отдельно хранится таблица занятости, где 0 соответствует свободной памяти. Обычно, если память используется для различных целей, это значение не просто не равно нулю, а равно количеству ссылок на эти данные из разных мест. Тогда программный модуль, которому больше не нужна эта память, не обнуляет поле занятости, а только уменьшает его на 1. Если при этом получается 0, память не требуется ни одной части программы, и может быть физически освобождена.
Сборка мусора выполняется словом :gc. Слово проходит по всем элементам массива ссылок на память, и переупорядочивает области памяти так, чтобы они размещались строго последовательно, занимая места блоков, отмеченных как свободные.
Выделение памяти выполняется словом DYNAMIC, которое ожидает на стеке требуемый размер памяти, возвращая идентификатор области, которая выделена программе. Выделенная память помечается как свободная словом DESTROY, ожидающим на стеке идентификатор. Зная идентификатор, можно также определить начальный адрес этой области памяти словом –HEAPLISTADR.
Код:
\ ========================== Start ==========================
\ Quark Forth
FORTH DEFINITIONS
DECIMAL
1024 CONSTANT c#HEAP-ENTRIES \ # of dynamically allocated objects
2048 1024 * CONSTANT c#RESERVED \ guaranteed in reserve
1 VALUE AUTO-COLLECT? \ allow garbage auto collection
QUAN HEAP-SIZE
: RECALCULATE-HEAP-SIZE
LIMIT @ c#RESERVED - HERE -
DUP 0 < IF " Can't allocate heap memory" PRINT ELSE
TO HEAP-SIZE THEN
;
CREATE HEAPLIST[] c#HEAP-ENTRIES 8 * ALLOT
CREATE HEAPUSAGE[] c#HEAP-ENTRIES 4 * ALLOT
\ HEAPLIST:
\ +0 - start address of memory area
\ +4 - size of memory area;
\ HEAP USAGE:
\ 0 means don't used
RECALCULATE-HEAP-SIZE
CREATE HEAP[] HEAP-SIZE ALLOT
: -HEAPUSAGE // INDEX --> ADR )
4 * HEAPUSAGE[] +
;
: -HEAPLISTADR // INDEX --> ADR )
8 * HEAPLIST[] +
;
: -HEAPLISTSIZE // INDEX --> ADR )
8 * HEAPLIST[] + 4 +
;
: CLEAR-HEAP
c#HEAP-ENTRIES 0 DO
0 I -HEAPUSAGE !
0 I -HEAPLISTADR !
0 I -HEAPLISTSIZE !
LOOP
;
CLEAR-HEAP
: ?free // N --> T | F )
DUP -HEAPUSAGE @ 0 = SWAP -HEAPLISTSIZE @ 0 = AND
;
: ?used // N --> T | F )
-HEAPUSAGE @ 0 = NOT
;
: ?garbaged // N --> T | F )
DUP -HEAPUSAGE @ 0 = SWAP -HEAPLISTSIZE @ 0 = NOT AND
;
: :?collect // N --> ) \ collect one entry if garbaged
DUP ?garbaged \ don't used & garbaged
IF
\ move memory content
DUP >R
R@ -HEAPLISTADR @ R@ -HEAPLISTSIZE @ + \ from where
R@ -HEAPLISTADR @ \ to
HEAP-SIZE R@ -HEAPLISTADR @ - R@ -HEAPLISTSIZE @ - \ all remains
CMOVE
\ correct addrs of objects if needed
R>
c#HEAP-ENTRIES 0 DO
I -HEAPLISTADR @ OVER -HEAPLISTADR @ > \ adr greater (need to be corrected)?
IF
I -HEAPLISTADR @ OVER -HEAPLISTSIZE @ - I -HEAPLISTADR @ !
THEN
LOOP
\ drop size of collected entry to 0
0 SWAP -HEAPLISTSIZE !
THEN
;
: :gc // --> ) \ force garbage collection
c#HEAP-ENTRIES 0 DO
I ?garbaged \ don't used & garbaged
IF
\ move memory content
I -HEAPLISTADR @ I -HEAPLISTSIZE @ + \ from where
I -HEAPLISTADR @ \ to
HEAP-SIZE I -HEAPLISTADR @ - I -HEAPLISTSIZE @ - \ all remains
CMOVE
\ correct addrs of objects if needed
c#HEAP-ENTRIES 0 DO
I -HEAPLISTADR @ J -HEAPLISTADR @ > \ adr greater (need to be corrected)?
I ?used AND
IF
I -HEAPLISTADR @ J -HEAPLISTSIZE @ - I -HEAPLISTADR !
THEN
LOOP
\ drop size of collected entry to 0
0 I -HEAPLISTSIZE !
0 I -HEAPLISTADR !
THEN
LOOP
;
: ?garbaged# // --> #_garbaged_entries )
0
c#HEAP-ENTRIES 0 DO
I ?garbaged \ don't used & garbaged
IF 1+ THEN
LOOP
;
: FIND-HEAPENTRY // --> INDEX | -1 )
0
BEGIN
1+ DUP 1- ?free OVER c#HEAP-ENTRIES = OR
UNTIL
DUP c#HEAP-ENTRIES = IF DROP -1 ELSE 1- THEN
;
: :freememoryadr // --> ADR )
HEAP[]
c#HEAP-ENTRIES 0 DO
I -HEAPLISTADR @ I -HEAPLISTSIZE @ + 2DUP >
IF DROP ELSE NIP THEN
LOOP
;
: DYNAMIC // SIZE --> INDEX )
FIND-HEAPENTRY
DUP -1 = AUTO-COLLECT? AND \ no free
IF
DROP :gc FIND-HEAPENTRY
THEN
DUP -1 = IF DROP CR " No more room for dynamic allocation " PRINT THEN
\ ===== otherwise set up new entry =====
OVER HEAP-SIZE :freememoryadr - >
DUP
IF
AUTO-COLLECT? IF DROP :gc OVER HEAP-SIZE :freememoryadr - > THEN
THEN
IF
DROP CR " Not enough memory " PRINT
AUTO-COLLECT? IF " (even after garbage collection) " PRINT THEN
// ABORT
THEN
DUP -HEAPUSAGE 1 SWAP !
DUP -HEAPLISTADR :freememoryadr SWAP !
SWAP OVER -HEAPLISTSIZE !
;
: DESTROY // INDEX --> )
DUP c#HEAP-ENTRIES > IF DROP CR " Invalid heap entry " PRINT THEN
-HEAPUSAGE 0 SWAP !
;
: ARRAY // SIZE --> )
CREATE DYNAMIC , DOES> @ -HEAPLISTADR @ ;
: G
20 0 DO
0 I 5 + GOTOXY I . 25 0 DO 0x20 EMIT LOOP
5 I 5 + GOTOXY I -HEAPLISTADR @ .
15 I 5 + GOTOXY I -HEAPLISTSIZE @ .
25 I 5 + GOTOXY I -HEAPUSAGE @ .
LOOP
;
78 20 * ARRAY VG[]
: VG // --> ) \ visualize heap memory usage
78 20 * 0 DO 32 VG[] I + C! LOOP
c#HEAP-ENTRIES 0 DO
I -HEAPUSAGE @ IF
I -HEAPLISTADR @ I -HEAPLISTSIZE @ + HEAP[] - \ end block
HEAP-SIZE 78 / 20 / /
I -HEAPLISTADR @ HEAP[] - \ first block
HEAP-SIZE 78 / 20 / /
2DUP = IF DROP VG[] + 176 SWAP C!
ELSE
DO
I VG[] + 178 SWAP C!
LOOP
THEN
THEN
LOOP
20 0 DO
0 I 4 + GOTOXY 186 EMIT 79 I 4 + GOTOXY 186 EMIT
78 0 DO
I 1+ J 4 + GOTOXY VG[] J 78 * + I + C@
EMIT
LOOP
LOOP
0 3 GOTOXY 201 EMIT 78 0 DO 205 EMIT LOOP 187 EMIT
0 24 GOTOXY 200 EMIT 78 0 DO 205 EMIT LOOP
;
Вход
Регистрация
Благодарности
Forth-FAQ
