УМЕНЬШЕНИЕ ЗАВИСИМОСТИ ОТ СИНХРОНИЗАЦИИ В ПОМЕТКЕ СБОРА МУСОРА

1. Система, которая устраняет зависимость от CAS-инструкций процессора для пометки сбора мусора, причем устраненные CAS-инструкции включают в себя одну или более инструкций сравнения и замены или инструкций сравнения и установки, при этом система содержит:
память, имеющую адресуемые блоки, причем каждый адресуемый блок является индивидуально адресуемым с помощью соответствующего адресного значения;
один или более указателей, находящихся в памяти, причем каждый указатель находится в по меньшей мере двух адресуемых блоках и каждый указатель имеет адресную часть, которая хранит адресное значение, и часть, относящуюся к сбору мусора, которая не включает в себя адресную часть;
при этом процессор находится в функциональном взаимодействии с памятью, процессор имеет набор инструкций, причем набор инструкций процессора включает в себя по меньшей мере одну инструкцию записи, которая при ее исполнении атомарно записывает значение в по меньшей мере в один адресуемый блок, при этом инструкция записи исключает какую-либо CAS-инструкцию;
модифицирующий поток, который при его исполнении изменяет, по меньшей мере, одно или более адресных значений одного или более соответствующих указателей;
сборщик мусора, который работает одновременно с модифицирующим потоком во время фазы пометки сбора мусора и использует инструкцию записи, чтобы атомарно устанавливать бит метки ссылки в части указателя, относящейся к сбору мусора, в качестве указания того, что адресной частью указателя идентифицирована область памяти, которая не была доступной для высвобождения при прошлой проверке;
посредством чего система выполняет фазу пометки сбора мусора, в то же время сохраняя целостность адресных значений, записанных модифицирующим потоком, без зависимости от CAS-инструкций, даже если модифицирующий поток и сборщик мусора работают одновременно друг с другом.
2. Система по п.1, в которой инструкция записи, используемая для атомарной установки бита метки ссылки, имеет средний счетчик циклов процессора, который обозначается здесь как среднее записи, при этом устраненные CAS-инструкции из набора инструкций процессора включают в себя самую быструю устраненную CAS-инструкцию, которая имеет средний счетчик циклов процессора, который обозначается здесь как CAS-среднее, и при этом CAS-среднее по меньшей мере вдвое больше среднего записи.
3. Система по п.1, в которой сборщик мусора содержит код фазы пометки, который находится в барьере считывания модифицирующего потока.
4. Система по п.1, в которой сборщик мусора содержит код фазы пометки, который находится в потоке сборщика мусора.
5. Система по п.1, при этом:
указатель включает в себя по меньшей мере 64 бита и часть указателя, относящаяся к сбору мусора, включает в себя по меньшей мере 8 бит; и
система включает в себя по меньшей мере два модифицирующих потока, каждый из которых работает одновременно со сборщиком мусора во время фазы пометки сбора мусора и каждый из которых при исполнении изменяет одно или более адресных значений одного или более соответствующих указателей.
6. Система по п.1, в которой модифицирующий поток работает в адресном пространстве ядра.
7. Система по п.1, при этом система дополнительно содержит модуль регистрации измененного указателя, который при его исполнении регистрирует соответствующие идентификаторы одного или более указателей, соответствующий адрес каждого из которых был изменен модифицирующим потоком во время фазы пометки сбора мусора, в результате чего модуль регистрации измененного указателя помогает в идентификации недостижимых непомеченных областей памяти.
8. Система по п.1, при этом адресной частью указателя идентифицирована область памяти, которая хранила или хранит объект, определенный программой, реализованной на объектно-ориентированном языке программирования.
9. Процесс сбора мусора, который устраняет зависимость от CAS-инструкций процессора во время фазы пометки, причем устраненные CAS-инструкции включают в себя одну или более инструкций сравнения и замены или инструкций сравнения и установки, при этом процесс выполняется посредством кода, исполняющегося в вычислительной системе, причем процесс содержит этапы, на которых:
сборщик мусора принимает местоположения одного или более указателей, которые находятся в цифровой памяти вычислительной системы, причем каждый указатель имеет адресную часть, которая хранит адресное значение, и часть, относящуюся к сбору мусора, которая не включает в себя адресную часть;
модифицирующий поток исполняется одновременно со сборщиком мусора и имеет доступ к, по меньшей мере, адресной части по меньшей мере одного из указателей;
сборщик мусора использует неCAS-инструкцию записи, чтобы атомарно устанавливать бит метки ссылки в части указателя, относящейся к сбору мусора, без перезаписи адресной части указателя, при этом установленный бит метки ссылки указывает, что адресной частью указателя идентифицируется или идентифицирована область памяти для последующей обработки сбора мусора;
посредством чего процесс выполняет фазу пометки сбора мусора, в то же время сохраняя целостность адресных значений, без зависимости от CAS-инструкций, даже если модифицирующий поток и сборщик мусора исполняются одновременно друг с другом.
10. Процесс по п.9, в котором сборщик мусора, использующий неCAS-инструкцию записи, чтобы атомарно устанавливать бит метки ссылки в части указателя, относящейся к сбору мусора, содержит:
атомарное считывание байтового значения из части указателя, относящейся к сбору мусора, в переменную, каковая переменная обозначается здесь как GCportion;
установку бита метки ссылки в GCportion; и затем
использование неCAS-инструкции записи, чтобы атомарно записывать значение из GCportion обратно в часть указателя, относящуюся к сбору мусора,.
11. Процесс по п.10, в котором модифицирующий поток изменяет, по меньшей мере, адресную часть указателя после упомянутого атомарного считывания байтового значения и перед упомянутым использованием неCAS-инструкции записи для атомарной записи значения, при этом процесс дополнительно содержит регистрацию идентификатора указателя, чтобы поддерживать последующее определение того, является ли измененный указатель ложноположительным значением высвобождаемой памяти.
12. Процесс по п.9, дополнительно содержащий по меньшей мере одно из следующих действий, выполняемых посредством кода, исполняющегося в вычислительной системе:
обработка части указателя, относящейся к сбору мусора, как если бы она содержала все нули;
обнуление части указателя, относящейся к сбору мусора;
обработка части указателя, относящейся к сбору мусора, как если бы она была снабжена знаком согласно старшему биту адресной части указателя;
снабжение знаком старшего бита адресной части указателя посредством части указателя, относящейся к сбору мусора; и
игнорирование части указателя, относящейся к сбору мусора, при использовании адресной части указателя.
13. Процесс по п.9, дополнительно содержащий код, исполняющийся в вычислительной системе, который регистрирует соответствующие идентификаторы одного или более указателей, соответствующий адрес каждого из которых был изменен модифицирующим потоком во время фазы пометки сбора мусора, в результате чего регистрация помогает в автоматической идентификации недостижимых непомеченных областей памяти.
14. Процесс по п.9, в котором модифицирующий поток исполняется в пользовательском адресном пространстве.
15. Процесс по п.9, в котором сборщик мусора использует неCAS-инструкцию записи, чтобы атомарно устанавливать старший бит указателя в качестве бита метки ссылки.