Привет всем. Продолжу о Фантоме. Для понимания полезно прочесть статью про персистентную оперативку, а так же общую статью про Фантом на Открытых Системах. Но можно и так.
Итак, мы имеем ОС (или просто среду, не важно), которая обеспечивает прикладным программам персистентную оперативную память, и вообще персистентную «жизнь». Программы живут в общем адресном пространстве с управляемыми (managed) пойнтерами, объектной байткод-машиной, не замечают рестарта ОС и, в целом, счастливы.
Очевидно, что такой среде нужна сборка мусора. Но — какая?
Есть несколько проблем, навязанных спецификой.
Во-первых, теоретически, объём виртуальной памяти в такой среде огромен — терабайты, всё содержимое диска. Ведь мы отображаем в память всё и всегда.
Во-вторых, нас категорически не устраивают stop the world алгоритмы. Если для обычного процесса остановка в полсекундны может быть приемлема, то для виртуальной памяти, которая, большей частью, на диске, это будут уже полчаса, а то как бы не полсуток!
Наконец, если считать, что полная сборка мусора составляет полсуток, нас, наверное, это не устроит — было бы здорово иметь какой-то быстрый процесс сбора мусора, хотя бы и не полностью честный, пусть он часть мусора теряет, но если удаётся быстро вернуть 90% — уже хорошо.
Тут нужна оговорка. Вообще говоря, в системе, которая располагает парой терабайт виртуальной памяти, это не так уж критично — даже если не делать освобождение памяти полсуток, возможно, не так много и набежит — ну, например, истратится 2-3, ну 5 гигабайт, ну даже и 50 гигабайт — не жалко, диск большой.
Но, скорее всего, это приведёт к большой фрагментации памяти — множество локальных переменных окажутся раскиданы по многим далеко расположенным страницам, при этом высока вероятность того, что небольшие вкрапления актуальной информации будут перемежены с тоннами неактуального мусора, что сильно повысит нагрузку на оперативную память.
Ок, итого у нас две задачи.
Второе требование кажется нереальным, и таким, собственно, и является. Полная сборка памяти — это обход практически всех объектов (кое-что в некоторых алгоритмах можно оптимизировать), и если они на диске и диск терабайтный, то оценочное время — часы, хорошо если не сутки. Какой тут нон-стоп?
На помощь приходит интересная мысль, которая, как часто бывает, очевидна, как только её у кого-нибудь прочтёшь: объект, который был мусором вчера, будет мусором и завтра.
Это, на практике, означает, что если у нас есть вчерашняя фотография всей памяти системы, то сборку мусора можно сделать именно что по фотографии! При этом найденный в ней мусор можно освободить и в актуальной версии памяти тоже!
А ведь ОС с персистентной оперативной памятью именно что и занимается созданием полных «фотографий» состояния памяти.
(Надо сказать, что я очень люблю, когда возникают такие концептуальные совпадения — для меня они являются признаком того, что модель системы достаточно целостна и ортогональна.)
Таким образом, возникает удивительная ситуация — у нас есть «фотография» памяти системы, и по ней можно делать сборку мусора даже самыми банальными mark&sweep алгоритмами.
Напомню, как он устроен, вкратце: обходим по ссылкам все достижимые объекты и ставим им маркер: «не мусор». Потом обходим всё и то, что без маркера, то — мусор.
Однако, тут возникает целый сонм оптимизационных задач.
Начнём с очевидной: записывать на диск дорого и опасно, если случится сбой — мы потеряем снапшот системы, а это недопустимо.
Значит, нужна оптимизация. Напрашиваются два варианта.
Первый — в процессе сбора мусора делать отдельную копию снапшота. Жутко дорого — потребуется почти удвоить объем дисковой памяти. И перезаписать почти все страницы.
Второй — не трогать оргинал (что всегда хорошо), а маркеры складывать в отдельный параллельный (сортированный по адресам объектов?) буфер, вероятно, в виде хешмапа или сортированного дерева.
Навскидку выбор очевиден. Но, может быть, есть третий вариант?
Ещё один момент, который напрашивается — это маркировка поколений. Интуитивно кажется, что 90% данных не станут мусором условно никогда — код классов, объекты с музыкой и видео — всё это хранится веками и явно не требует ежедневной проверки.
Наверное, большую сборку можно делать иногда тоже частичной — например, раз в сутки обрабатывать только последнее поколение, раз в двое суток — два последних, а на выходные уж перетряхнуть всё. Генеральная уборка.
Однако, можно бы попросить у основного аллокатора и быстрого сборщика мусора хинтов. Например, если в процессе работы были модифицированы объекты из самого нижнего, условно «константного» поколения (где лежат классы и огромные константные объекты), то это могло бы быть триггером для полной сборки.
Собственно, на сегодня в ОС Фантом реализован только быстрый алгоритм — на базе счётчика ссылок. Полный сборщик ждёт своего героя.
С быстрым, кстати, всё тоже непросто. Там есть нерешаемая (не волнуйтесь, мы её почти решили:) проблема с races — синхронизация инкремента числа использований объекта.
Суть её проста. Мы с вами читаем из поля объекта А ссылку на объект Б. Поскольку мы теперь ей (ссылкой) владеем и хотим пользоваться, мы, конечно, увеличиваем на 1 счётчик ссылок внутри объекта Б.
Но — вот беда — между этой парой строк случилось переключение контекста и другой тред в этот самый момент взял и стёр из объекта А эту самую ссылку на Б. И была она последняя. И счётчик ссылок ушёл в ноль, и стал объект удалённым. И тут-то мы начали ему счётчик ссылок увеличивать. А он уже убит, очищен, выделен кому-то ещё и содержит совсем другие данные.
Весело? И mutex на каждое считывание поля объекта не поставишь — тогда машина из такого мьютекса вылезать не будет, только и будет что запирать его и отпирать. Даже спинлок приведёт к кратному, в разы замедлению кода.
Неприемлемо.
Решение выглядит так: фактически уничтожать объект только после того, как все нити всех виртуальных машин прошли границу инструкции виртуальной машины. Это гарантирует, что все декременты и инкременты закончились. Механизм для этого есть, он уже используется при снапшотах.
На этом на сегодня закончу, отметив, что я совершенно не коснулся задачи компактификации (она же дефрагментация) объектов. Тоже, вообще говоря, непочатый край. Отдельно есть задача написания аллокатора объектов с большой степенью локализации аллокации, причём с разбиением арен быстрых объектов по нитям. Здесь же — разнесение мьютексов аллокатора по аренам с тем, чтобы не возникало затора на входе в аллокатор.
Собственно, всё это — очень хороший пример задач, которые встают в проекте ОС Фантом — нет ничего нереального, но постоянно требуются хорошие инженерные решения для того, чтобы обойти на вид необходимые проблемы.
Итак, мы имеем ОС (или просто среду, не важно), которая обеспечивает прикладным программам персистентную оперативную память, и вообще персистентную «жизнь». Программы живут в общем адресном пространстве с управляемыми (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 на каждое считывание поля объекта не поставишь — тогда машина из такого мьютекса вылезать не будет, только и будет что запирать его и отпирать. Даже спинлок приведёт к кратному, в разы замедлению кода.
Неприемлемо.
Решение выглядит так: фактически уничтожать объект только после того, как все нити всех виртуальных машин прошли границу инструкции виртуальной машины. Это гарантирует, что все декременты и инкременты закончились. Механизм для этого есть, он уже используется при снапшотах.
На этом на сегодня закончу, отметив, что я совершенно не коснулся задачи компактификации (она же дефрагментация) объектов. Тоже, вообще говоря, непочатый край. Отдельно есть задача написания аллокатора объектов с большой степенью локализации аллокации, причём с разбиением арен быстрых объектов по нитям. Здесь же — разнесение мьютексов аллокатора по аренам с тем, чтобы не возникало затора на входе в аллокатор.
Собственно, всё это — очень хороший пример задач, которые встают в проекте ОС Фантом — нет ничего нереального, но постоянно требуются хорошие инженерные решения для того, чтобы обойти на вид необходимые проблемы.
