Итак, мы имеем ОС (или просто среду, не важно), которая обеспечивает прикладным программам персистентную оперативную память, и вообще персистентную «жизнь». Программы живут в общем адресном пространстве с управляемыми (managed) пойнтерами, объектной байткод-машиной, не замечают рестарта ОС и, в целом, счастливы.
Очевидно, что такой среде нужна сборка мусора. Но — какая?
Есть несколько проблем, навязанных спецификой.
Во-первых, теоретически, объём виртуальной памяти в такой среде огромен — терабайты, всё содержимое диска. Ведь мы отображаем в память всё и всегда.
Во-вторых, нас категорически не устраивают stop the world алгоритмы. Если для обычного процесса остановка в полсекундны может быть приемлема, то для виртуальной памяти, которая, большей частью, на диске, это будут уже полчаса, а то как бы не полсуток!
Наконец, если считать, что полная сборка мусора составляет полсуток, нас, наверное, это не устроит — было бы здорово иметь какой-то быстрый процесс сбора мусора, хотя бы и не полностью честный, пусть он часть мусора теряет, но если удаётся быстро вернуть 90% — уже хорошо.
Тут нужна оговорка. Вообще говоря, в системе, которая располагает парой терабайт виртуальной памяти, это не так уж критично — даже если не делать освобождение памяти полсуток, возможно, не так много и набежит — ну, например, истратится 2-3, ну 5 гигабайт, ну даже и 50 гигабайт — не жалко, диск большой.
Но, скорее всего, это приведёт к большой фрагментации памяти — множество локальных переменных окажутся раскиданы по многим далеко расположенным страницам, при этом высока вероятность того, что небольшие вкрапления актуальной информации будут перемежены с тоннами неактуального мусора, что сильно повысит нагрузку на оперативную память.
Ок, итого у нас две задачи.
- Быстрый, недорогой, возможно — неполный (собирает не весь мусор), нон-стоп алгоритм для постоянного применения. Предполагается, что память, которой он будет «касаться» — реально в памяти, а не высвоплена на диск.
- Полный, возможно — долгий и дорогой, но тоже нон-стоп (!) алгоритм для всего адресного пространства. Предполагается, что доступ к «памяти» будет приводить его на диск с вероятностью в 99%.
Второе требование кажется нереальным, и таким, собственно, и является. Полная сборка памяти — это обход практически всех объектов (кое-что в некоторых алгоритмах можно оптимизировать), и если они на диске и диск терабайтный, то оценочное время — часы, хорошо если не сутки. Какой тут нон-стоп?
На помощь приходит интересная мысль, которая, как часто бывает, очевидна, как только её у кого-нибудь прочтёшь: объект, который был мусором вчера, будет мусором и завтра.
Это, на практике, означает, что если у нас есть вчерашняя фотография всей памяти системы, то сборку мусора можно сделать именно что по фотографии! При этом найденный в ней мусор можно освободить и в актуальной версии памяти тоже!
А ведь ОС с персистентной оперативной памятью именно что и занимается созданием полных «фотографий» состояния памяти.
(Надо сказать, что я очень люблю, когда возникают такие концептуальные совпадения — для меня они являются признаком того, что модель системы достаточно целостна и ортогональна.)
Таким образом, возникает удивительная ситуация — у нас есть «фотография» памяти системы, и по ней можно делать сборку мусора даже самыми банальными mark&sweep алгоритмами.
Напомню, как он устроен, вкратце: обходим по ссылкам все достижимые объекты и ставим им маркер: «не мусор». Потом обходим всё и то, что без маркера, то — мусор.
Однако, тут возникает целый сонм оптимизационных задач.
Начнём с очевидной: записывать на диск дорого и опасно, если случится сбой — мы потеряем снапшот системы, а это недопустимо.
Значит, нужна оптимизация. Напрашиваются два варианта.
Первый — в процессе сбора мусора делать отдельную копию снапшота. Жутко дорого — потребуется почти удвоить объем дисковой памяти. И перезаписать почти все страницы.
Второй — не трогать оргинал (что всегда хорошо), а маркеры складывать в отдельный параллельный (сортированный по адресам объектов?) буфер, вероятно, в виде хешмапа или сортированного дерева.
Навскидку выбор очевиден. Но, может быть, есть третий вариант?
Ещё один момент, который напрашивается — это маркировка поколений. Интуитивно кажется, что 90% данных не станут мусором условно никогда — код классов, объекты с музыкой и видео — всё это хранится веками и явно не требует ежедневной проверки.
Наверное, большую сборку можно делать иногда тоже частичной — например, раз в сутки обрабатывать только последнее поколение, раз в двое суток — два последних, а на выходные уж перетряхнуть всё. Генеральная уборка.
Однако, можно бы попросить у основного аллокатора и быстрого сборщика мусора хинтов. Например, если в процессе работы были модифицированы объекты из самого нижнего, условно «константного» поколения (где лежат классы и огромные константные объекты), то это могло бы быть триггером для полной сборки.
Собственно, на сегодня в ОС Фантом реализован только быстрый алгоритм — на базе счётчика ссылок. Полный сборщик ждёт своего героя.
С быстрым, кстати, всё тоже непросто. Там есть нерешаемая (не волнуйтесь, мы её почти решили:) проблема с races — синхронизация инкремента числа использований объекта.
Суть её проста. Мы с вами читаем из поля объекта А ссылку на объект Б. Поскольку мы теперь ей (ссылкой) владеем и хотим пользоваться, мы, конечно, увеличиваем на 1 счётчик ссылок внутри объекта Б.
object *b_ptr = a[xx];
b_ptr->ref_count++;
Но — вот беда — между этой парой строк случилось переключение контекста и другой тред в этот самый момент взял и стёр из объекта А эту самую ссылку на Б. И была она последняя. И счётчик ссылок ушёл в ноль, и стал объект удалённым. И тут-то мы начали ему счётчик ссылок увеличивать. А он уже убит, очищен, выделен кому-то ещё и содержит совсем другие данные.
Весело? И mutex на каждое считывание поля объекта не поставишь — тогда машина из такого мьютекса вылезать не будет, только и будет что запирать его и отпирать. Даже спинлок приведёт к кратному, в разы замедлению кода.
Неприемлемо.
Решение выглядит так: фактически уничтожать объект только после того, как все нити всех виртуальных машин прошли границу инструкции виртуальной машины. Это гарантирует, что все декременты и инкременты закончились. Механизм для этого есть, он уже используется при снапшотах.
На этом на сегодня закончу, отметив, что я совершенно не коснулся задачи компактификации (она же дефрагментация) объектов. Тоже, вообще говоря, непочатый край. Отдельно есть задача написания аллокатора объектов с большой степенью локализации аллокации, причём с разбиением арен быстрых объектов по нитям. Здесь же — разнесение мьютексов аллокатора по аренам с тем, чтобы не возникало затора на входе в аллокатор.
Собственно, всё это — очень хороший пример задач, которые встают в проекте ОС Фантом — нет ничего нереального, но постоянно требуются хорошие инженерные решения для того, чтобы обойти на вид необходимые проблемы.
Комментарии (18)
Amomum
08.04.2016 16:52И mutex на каждое считывание поля объекта не поставишь — тогда машина из такого мьютекса вылезать не будет, только и будет что запирать его и отпирать. Даже спинлок приведёт к кратному, в разы замедлению кода.
Почему бы не сделать счетчик атомарным?ZyXI
08.04.2016 20:57+2А смысл? Проблема не в инкременте, проблема в том, что объект будет уничтожен до инкремента, но после возникновения новой ссылки. Атомарность счётчика на такую возможность никак не влияет.
Ruslan_r
08.04.2016 16:59+2Мне понравилась идея персистентной ОС, но я очень много не понимаю, а очень хочется. Может вам нужно сделать что-то вроде карты модулей и объектов в виде UML схемы. Это повысит порог вхождения в вашу ОС и привлечение новых людей. Ведь не обязательно понимать полностью как устроена и работает вся ОС, может кого-то заинтересует отдельная подсистема и человек будет работать над ней.
NLO
08.04.2016 17:17НЛО прилетело и опубликовало эту надпись здесь
dzavalishin
08.04.2016 23:41+1Было бы здорово, но сделать это небанально.
Если есть знаток того, как работают mem mapped files при fork, приглашаю в соучастники такой разработки. Это, видимо, единственный путь.
jcmvbkbc
09.04.2016 16:07как работают mem mapped files при fork
Мэппинг просто шарится между процессами.
uvelichitel
09.04.2016 14:20+1Очевидно, что такой среде нужна сборка мусора.
Не всем очевидно. Машина Тьюринга работает на бесконечной ленте и ни мусора ни его уборки не предполагает. Персистентная модель также крайне привлекает возможностью бескрайнего undo во всех его смыслах, что тоже не рифмуется с идеей мусора.
Wowa69
09.04.2016 14:43-1object *b_ptr = a[xx];
b_ptr->ref_count++; — В этом случае то что передался указатель на объект, у которого счётчик ссылок уже нул уже является ошибкой.ZyXI
09.04.2016 17:02Где вы в статьё нашли «передачу указатель на объект с нулевым счётчиком ссылок»? Там прямо написано: сначала передали нормальный объект, а не мусор с нулевым счётчиком. Потом в другом потоке счётчик был обнулён.
К примеру, у вас есть асинхронный словарь с кэшем. В одном из использующих кэш потоков из словаря уже взяли объект, но ещё не увеличили счётчик. А в другом произошло событие, из?за которого кэш нужно очистить. Система решила переключится на другой до
ref_count++и выполняла его вплоть доref_count--. Получился объект, на который ссылаются, но с нулевым счётчиком. При этом, когда его получали, всё было нормально.
0serg
10.04.2016 12:53У Вас со счетчиком ссылок проблема потому что Вы нарушаете идиому владения. Создавать копии ссылок на объект может только тот кто этим объектом владеет. В многопоточной системе каждый тред должен получать владение независимо, если треду А нужен объект которым владеет тред Б, то его обязательно необходимо запрашивать у треда Б через один из механизмов синхронизации.
Если сам счетчик ссылок на объект по какой-то причине не умирает вместе с объектом а остается нулем, то можно еще атомарный CAS использовать.NLO
10.04.2016 14:53НЛО прилетело и опубликовало эту надпись здесь
0serg
11.04.2016 17:23+1В варианте когда указатель может протухнуть в любой момент такой код работать не будет. Он базируется на том что объект просто не умирает в течении некоего времени когда с ним возможна работа. Тот кто объект в конце подчищает уже после смерти потоков — тот и «владелец» объекта. Синхронизация обычно в таком коде сводится к тому что этот владелец ждет пока помрут потоки которые могут с объектом работать.
А вообще mutex можно рассматривать как частный вариант идиомы владения. Взятие мьютекса соответствует взятию на себя «владения» ресурсом.
sebres
12.04.2016 17:28+1Реф-каунтинг вообще штука капризная.
Взять для примера те же цикличные или кольцевые ссылки (буде таковые разрешены) — как только граф где-то замкнулся в кольцо, мы имеем для всех объектов в том кольце (и соответственно других "деток" всех этих объектов рекурсивно) значениеref_countотличное от0, и что особенно весело — навсегда (если не принимать меры). Самая красота начинается если где-то пересекаются два и более таких графа.
Т.е. иногда просто невозможно установить — это leak как он есть или просто "долгоиграющая" кольцевая последовательность.
Ну и если тупо повыкидывать сами ссылки довольно несложно ("рекурсивно" с защитой от бесконечного цикла или принудительным декрементом после разрыва кольца), то сделать это "правильно" в случае наличия какой-нибудь привязанной логики типа "деструкторов" и т.п. уже совсем не просто — ибо нередко играют роль уже совершенно другие факторы, например последовательность "освобождения" (тот же вызов "деструктора" и т.д.).
И это только один пример, что называется навскидку, а тех граблей в теме реф-каунтинга и без атомарности хоть отбавляй...
NLO
00.00.0000 00:00НЛО прилетело и опубликовало эту надпись здесь
sebres
12.04.2016 22:14Вот враз видно человека не совсем в теме:
- дано тупо два "объекта": наш
Aи какой-тоBданный нам снаружи, надо добавитьBв "дочки" нашемуA, соответственно проинкементив егоB->ref_count; - как не зная
B(или всех "дочерних" связейB) исключить ситуацию (которая якобы "на нашей совести"), что уBуже есть какой-то "дочерний"X, для которого уже существует reference кA?
Т.е. не зная полностьюB(что часто именно так) случайно не замкнуть кольцо?
Я уж не говорю про то, что даже полностью зная
Bсо всеми "детками" его, это часто в принципе не реально, ибо:
- на этом этапе запрещена "итерация" по
B; - на этом этапе запрещена "итерация" по какому-либо "потомку" от
B, т.к. может привести к неожиданному результату, находится в состоянии одномоментного изменения (например ротация дерева хэш-таблицы) или находится в состоянии деструкции и т.д. и т.п.; - итерация по детям предполагает смену или блокировку нитей (тупо запирание контекста, т.е. возможен deadlock, нежелательное распараллеливание потоков, и т.п. радости);
- сводит на нет всю прелесть реф-каунтинга, ибо такая проверка — тупо очень долгая операция (т.е. по длительности и сложности не сопоставима с предполагаемой "атомарность" реф-каунтинга);
Исключение конечно составляют частные случаи, когда
A->ref_count == 0(т.е. объектAреально нигде еще не референсирован, соответственно кольцо исключено), но такое на практике на самом деле очень и очень редко (т.е. грубо говоря "конструктор" и иже с ним)… Ну илиB"примитивен" сам по себе, т.е. в принципе не может "владеть" другими объектами (не имеет "детей"), что хотя и не редкость, но лишь чуть-чуть улучшает ситуацию описанную выше.
Если бы все просто было бы с реф-каунтингом в чистом его виде, люди не напридумывали бы нестрогие или невладеющие (weak) references, умный указатели (типа smart, shared или intrusive pointers), тот же GC и так далее и тому подобное.
- дано тупо два "объекта": наш
NLO
НЛО прилетело и опубликовало эту надпись здесь