В теории да ... это возможно. Но есть проблема с GC:
чтобы собрать мусор, нужно знать расположение данных
хранится в памяти, и он также должен хранить данные, чтобы указать, если
блок памяти используется или нет ... но информация о макете является общей
со временем выполнения, потому что время выполнения должно знать типы объектов
(т. е. расположение памяти) для выполнения приведения типов.
Как работает GC?
GC начинает читать корневые объекты, которые он знает. Получает все ссылки
и пометить их как в использовании . Для каждого из указанных объектов, он получает
макет и читает больше ссылок из этих, и отмечает их
как используется ... и этот процесс продолжается, пока не останется больше ссылок.
Примечания. Я использовал информацию о типе и макете в одном значении.
Пример:
Imagine we have some object layouts:
====================================
A: { int, object, double, object }
B: { object, object }
C: { int }
Memory Data:
============
Now we need to describe what is in memory.
The following list is composed of memory positions,
and the data contained in each position.
There are 2 kinds of notation I will use:
- Address: ROOT[ list-of-root-references ]
- Address: type-identifier { object-data }
Note that each object can span multiple memory
positions from the first one.
e.g. 90: B { 0, 0 } -- this reads as
"stored at address 90: type-identifier of B followed by raw data { 0, 0 }"
- A reference is represented by a number,
that point to the memory address of the pointed object.
1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 } There is a self-reference here!
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 } Note that 0 is a null reference!
The GC need to know the layout of each object.
Otherwise it wouldn't be abled to tell
what knid of information is stored in each memory position.
Running the GC:
===============
Garbage collecting steps, to clean the memory described above:
Step 1: Get ROOT references: 2, 3, 9 and mark as 'in-use'
Step 2: Get references from 2, 3 and 9: 3, 6, 7. Note that 0 is a null reference!
Step 3: Get references from 3, 6 and 7: 6, 7, 8, and mark them.
Step 4: Get references from 6, 7, 8, and mark them: only 8!
Step 5: Get references from 8... it has none! We are finished with marking objects.
Step 6: Delete unmarked objects.
This shows what happened in each step with each object stored in the memory.
Step -> 1 2 3 4 5
Memory
20 x
30 x x
40 DELETE
50 DELETE
60 x x
70 x x
80 x x
90 x
То, что я описал, - это очень простой алгоритм GC.
Взгляните на трехцветную маркировку ... это действительно круто!
Вот как сделаны настоящие современные GC.
Сборка мусора (информатика) - описывает некоторые современные методологии GC.
Но ... где хранится информация о макете?
Этот вопрос важен, поскольку он влияет как на сборщик мусора, так и на время выполнения.
Чтобы сделать быстрое приведение типа, информация о типе должна быть размещена рядом со ссылкой,
или рядом с выделенной памятью. Мы могли бы думать, чтобы хранить информацию о типе
в каталоге выделенных блоков памяти, но тогда ... Тип-приведения потребуется
чтобы получить доступ к каталогу, так же, как новый оператор и GC, когда это необходимо
удалить объект.
Если мы храним информацию о расположении рядом со ссылкой, то каждая ссылка на
один и тот же объект будет повторять ту же информацию вместе с указателем
сам по себе.
Пример:
To represent the memory data I will introduce the following notation:
- Address: { object-data } -- this time object type is not at the begining!
- A reference is represented by a type-identifier and an address-number,
that point to the memory address of the pointed object,
in the following format: type/number...
e.g. A/20 -- this reads as: "at address 20, there is an object of type A"
Note that: 0/0 is a null reference,
but it still requires space to store the type.
The memory would look like this:
1: ROOT[ B/90, A/20, B/30 ]
20: { 1236, B/30, 0.5, C/60 }
30: { C/60, A/70 }
40: { 1237 }
50: { 1238, A/20, 0.8, A/50 }
60: { 1234 }
70: { 1234, 0/0, 0.7, C/80 }
80: { 1235 }
90: { 0/0, 0/0 }
Если мы храним информацию о расположении рядом с выделенным блоком памяти, то это хорошо!
Это быстро и позволяет избежать повторения информации о макете.
Пример:
The memory looks like the first sample:
*This is the same notation used at the begining of this answer.
1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 }
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 }
Пока все хорошо ... но теперь я хочу общую память.
Первое, что мы заметили, это то, что мы не можем хранить информацию о макете рядом с
выделенная память больше.
Представьте массив с разделяемой памятью:
* тысяча сорок-девять * Пример: * ** 1052 тысяча пятьдесят-один *
I'll introduce a new notation for arrays:
type-identifier < array-length >
1: ROOT[ 20, 31 ] -- pointer 31 is invalid, destination has no type-identifier.
20: INT<5> -- info about layout of the next memory data (spans by 10 memory units)
30: 2
31: 3 -- should have type-identifier, because someone
32: 5 is pointing here!! Invalid memory!!
33: 7
34: 11
Мы все еще можем попытаться разместить информацию о макете рядом с указателем,
вместо. Массив общей памяти теперь возможен:
Пример:
1: ROOT[ INT<5>/30, INT<2>/31 ]
30: 2
31: 3
32: 5
33: 7
34: 11
Помните, что этот подход заставляет нас повторять информацию о макете везде ...
но смысл в том, чтобы использовать меньше памяти, не так ли? Но чтобы поделиться памятью, нам нужно
больше памяти для хранения данных макета / указателей. Для нас пока нет пончиков. = (* +1062 *
Есть только одна надежда: давайте ухудшим функции времени выполнения!
ЭТО МОЙ ОТВЕТ - Как мне кажется, это возможно =>
Как насчет использования каталога выделения памяти для хранения информации о типах?
Это можно сделать, но тогда пострадает динамическое приведение, а также пострадает GC.
Помните, я сказал, что GC необходимо получить доступ к каталогу памяти, просто чтобы удалить объекты ...
ну, теперь ему нужно было бы обращаться к каталогу каждый раз, когда он находит ссылку,
не просто удалить. О, МОЙ БОГ!! Мы собираемся убить производительность GC этим, а также производительность во время выполнения. Я думаю, слишком высокая стоимость!
<= ЭТО МОЙ ОТВЕТ </em>
Но ... а если среда выполнения не поддерживает динамическое приведение? если компилятор знает
все о типе во время компиляции ... тогда GC даже не будет существовать ... ему НУЖНО
информация о типе, потому что эта информация говорит ему, что такое макет
память, используемая этим типом.
Не простое, умное решение, в поле зрения.
Может быть, я просто неправ. Но я не могу представить себе путь к этому лучше, чем он есть.Современные GC еще сложнее, чем это ... Я рассмотрел только основы,
Я думаю, что современные GC оптимизируют другими способами, то есть другими, более надежными способами.
Другие ссылки:
http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
http://www.memorymanagement.org/glossary/t.html
http://www.cs.purdue.edu/homes/sbarakat/cs456/gc-2.pdf
Трехцветное инкрементное обновление ГХ: нужно ли сканировать каждый стек дважды?