Ответ 1
В теории, да... это возможно. Но есть проблема с 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, так и на runtime. Чтобы выполнить быстрое литье типов, информация о типе должна быть размещена вблизи ссылки, или рядом с выделенной памятью. Мы могли бы думать, чтобы хранить информацию о типе в каталоге выделенных блоков памяти, но тогда... type-casts понадобится для доступа к каталогу, как и новый оператор и 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 }
До сих пор так приятно... но теперь мне нужна разделяемая память.
Первое, что мы замечаем, это то, что мы не можем хранить информацию о макете рядом с выделенной памяти больше.
Представьте массив с разделяемой памятью:
Пример:
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
Помните, что этот aproach заставляет нас повторять всю информацию о макете везде... но смысл здесь в том, чтобы использовать меньше памяти, не так ли??? Но чтобы разделить память, нам нужно больше памяти для хранения макетов-данных/указателей. Нет пончиков для нас. = (
Есть только одна надежда: позволяет деградировать возможности выполнения!
ЭТО МОЙ ОТВЕТ - Как я думаю, это может быть возможно = >
Как использовать каталог распределения памяти для хранения информации о типе?
Это можно сделать, но тогда динамическое кастинг будет страдать, а также GC будет страдать. Помните, что я сказал, что GC необходимо получить доступ к каталогу памяти, просто для удаления объектов... ну, теперь ему нужно будет получить доступ к каталогу каждый раз, когда он найдет ссылку, не просто удалить. О, МОЙ БОГ!! Мы собираемся убить производительность GC с этим, а также производительность исполнения. Слишком высокая стоимость, я думаю!
< = ЭТО МОЙ ОТВЕТ
Но... и если среда выполнения не поддерживает динамическое кастинг? если компилятор знает все о типе во время компиляции... тогда 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
Трехкрасовое инкрементальное обновление GC: нужно ли дважды сканировать каждый стек?