Обсуждение 2020-04-17 про сборку мусора

Операционная система, написанная на языке Оберон и проект её перевода на русский язык. Только технические вопросы.
Ответить
БудДен
Сообщения: 940
Зарегистрирован: 07.10.18 14:01

Обсуждение 2020-04-17 про сборку мусора

Сообщение БудДен » 17.04.20 15:33

Из телеграма:

Вот с ячейками, в отличии от объектов, код компилируется.
Я думаю, что реализацию lock-free ядра а2 от Флориана, можно считать современной реализацией soft real-time a2
Можно диссер Флориана почитать

Вовсе не обязательно есть stop world в сборщиках мусора
Вроде бы в GC Azul есть сборщик мусора без "остановки мира"

Алгоритмы неблокирущего сборщика мусора существуют 100%.
В книге по компиляторам ( книга драконов? Не вспомню сходу) есть перечень на полстраницы.

Нашёл такую вот работу:
https://www.usenix.org/legacy/events/ve ... -click.pdf

Я хотел предложить пример про часы, которые просто считают время, и потом смотрим, насколько они отстали. Но поскольку может быть более одного рилтайм-треда, то они могут отстать по другой причине.

Я тёмен в драйверах, но я так понимаю, что иногда там важна реакция точно во время. Такие операции должны происходить в эксклюзивном режиме, тоже такой вот stop the world. Т.е., чтобы построить рилтайм приложение в ОС, нужно знать характеристики всех драйверов.

И вот ещё есть тема на лоре:
https://www.linux.org.ru/forum/development/13779416
2017-й год, все только присматривались

Дальше я ещё пытался прогуглить стоимость барьеров чтения/записи, т.к. есть смутное воспоминание, что они чертовски дороги.

И как раз по ссылке с pauseless сборкой мусора написано:

Денис Будяк, [17.04.20 15:04]
Read barriers, on the other hand, are rarely used in production
systems despite a wealth of academic research because of the
high mutator cost they usually incur.

Денис Будяк, [17.04.20 15:04]
Т.е. azul имеет свою цену, даже если он и решает проблему

Даже CAS не такой уж дешёвый - на интелах он блокирует системную шину.

https://habr.com/ru/post/195948/

Денис Будяк, [17.04.20 15:08]
А как обстоит дело с производительностью атомарных примитивов?
Современные процессоры настолько сложны и непредсказуемы, что изготовители не дают каких-то однозначных гарантий длительности тех или иных инструкций, тем более атомарных, в работе которых задействованы внутренняя синхронизация, сигнализация по шинам процессора и пр. Существует довольно большое число работ, в которых авторы пытаются замерить длительность инструкций процессоров. Я приведу измерения из [McKen05]. В этой работе авторы, помимо прочего, сравнивают длительность атомарного инкремента и примитива CAS с длительностью операции nop (no-operation). Итак, для Intel Xeon 3.06 ГГц (образца 2005 года) атомарный инкремент имеет длительность 400 nop, CAS – 850 – 1000 nop.

Денис Будяк, [17.04.20 15:08]
Справедливости ради стоит заметить, что, по моим ощущениям, с каждым новым поколением архитектуры Intel Core примитив CAS становится всё быстрее, видимо, инженеры Intel немало сил вкладывают в совершенствование микроархитектуры.

Денис Будяк, [17.04.20 15:09]
https://books.google.ru/books?id=ueXJCg ... us&f=false

Денис Будяк, [17.04.20 15:09]
см. чуть выше Listing 8.1


Это отдельные темы в общем-то, просто неблокирующие алгоритмы, наряду с другими драйверами, затрудняют достижение рилтайма. В любом случае, если в системе есть паузы, их нужно учитывать для создания гипотетического, скажем так, телефона на базе этой платформы. Просто паузы от сборщика мусора обычно менее предсказуемы. Спасибо, я изучу конечно, что там такого в сборщике мусора сделано, но пока что я не верю, что там предсказуемые паузы.

Аватара пользователя
Лис [Вежливый]
Сообщения: 283
Зарегистрирован: 08.10.18 13:32

Re: Обсуждение 2020-04-17 про сборку мусора

Сообщение Лис [Вежливый] » 17.04.20 15:45

> 2017-й год, все только присматривались

Ты ошибаешься. IBM опубликовал Metronome-TS в 2008-м году, и я о нём уже в 2009-м году знал.

БудДен
Сообщения: 940
Зарегистрирован: 07.10.18 14:01

Re: Обсуждение 2020-04-17 про сборку мусора

Сообщение БудДен » 17.04.20 16:47

Диссертация, описывающая современное ядро A2, называется

On the Design and Implementation of an
Efficient Lock-Free Scheduler
Florian Negele 1 , Felix Friedrich 1 , Suwon Oh 2 , and Bernhard Egger

Павиа
Сообщения: 76
Зарегистрирован: 23.05.19 21:28

Re: Обсуждение 2020-04-17 про сборку мусора

Сообщение Павиа » 17.04.20 20:22

Intel Xeon 3.06 ГГц (образца 2005 года) атомарный инкремент имеет длительность 400 nop, CAS – 850 – 1000 nop.
Глупо мерить nop так как интел их исполняет пачками по 16 штук без обращения к кэшу данных. И тут видно что исследователи накосячили не смогли 16 нопов в конвейр загрузить или не додумались, а только 8.
Справедливости ради стоит заметить, что, по моим ощущениям, с каждым новым поколением архитектуры Intel Core примитив CAS становится всё быстрее, видимо, инженеры Intel немало сил вкладывают в совершенствование микроархитектуры.
Это только кажется открываем Optimizetion Manual и смотрим ничего нового. CAS сваливается к скорости обращения к L3 на однопроцесорных и на многопроцессорных системах к RAM. Т.е. Со времен 486 процессора ничего не поменялос как блокировалась вся шина сигналом Lock так и блокируется.

Павиа
Сообщения: 76
Зарегистрирован: 23.05.19 21:28

Re: Обсуждение 2020-04-17 про сборку мусора

Сообщение Павиа » 17.04.20 21:06

Хотите настоящий Free-Lock используйте транзакции с откатами. А что-бы снизить вероятность отката до 0. Нужно просто разделить зоны ответственности, а на границе зоны должны отстоять далее чем число ядер. Т.е. размер зоны должен быть не менее числа ядер и не менее размера кэш линейки. Причем последнее избавляет от необходимости применять CAS. За счёт алгоритма двойной проверки.

А сборщик мусора реализуется через двунаправленный список. Там конечно в языке нужно ввести пометки слабые и сильные указатели.

Драйверам не нужно точное время. Есть два способа работы путём постоянного опроса и через прерывания. Если железа требует постоянного опроса, то такого разработчика железа надо на галеры отправлять за проф непригодность.

ОС должна состоять из 2-х частей жёсткого реального масштаба времени и отложенного исполнения(мягкого реального времени).

При жестком реальном времени задаче отводится квант времени если задача не успевает, то она убивается в конце кванта.
Для задачи ядро может подготовить ячейки либо задача сама опрашивает нужные регистры. В последнем случае задача должны быть готова к тому, что регистры могут оказаться в неопределенном состоянии.

Проблема с прерываниями такая же прерывания происходит внезапно и состояние ОС в этот момент не когерентно. Это значит что если вы по пробуете прочитать ячейки памяти или регистры то они могут оказаться в одном состоянии. Если вы попытаетесь записать в эти регистры ячейки то ваши действия может отменить любая часть ОС которую остановило прерывание.
Так как все программы должны писать в память, то после приходя прерывания его надо синхронизировать с ОС. Для чего взводиться флаг. И далее возвращается управление в ОС и при первой возможности при вызове системной процедуры(ядерной функции) происходит переключение задач. У ядерных процессов наивысший приоритет поэтому они получают управление и приступают к обработке прерывания. Оно проверяет чьё прерывание и передаёт управление драйверу.
Т.е., чтобы построить рилтайм приложение в ОС, нужно знать характеристики всех драйверов.
Только тех кто работают с жестким реальным временем. Нужно знать какой квант нужен программе 1 мс или 100 мкс. И знать какие ресурсы этой программе нужны. Ресурсы это зоны памяти и зоны регистров и железо которое отдаётся в монопольный доступ. Монополии это плохо поэтому нужно делать виртуализацию. Жёсткие системы это плохо людям нужна свобода поэтому ограничивать их не нужно нужно толкьо описать как делать правильно а как неправильно.
Переключение процессов занимает 1-10 мкс. Поэтому делать квант менее 10мс неправильно. А делать более 1 мс тоже неправильно так как процессор будет крутиться вместо того что-бы спать в энерго сберегающем режиме.

Квант в 1 мс состоит из 10 квантов по 100 мкс. Так что если есть задачи с меньшим квантом, то можно отдать управление им. Но начинаться они должны точно в свой временной интервал.

БудДен
Сообщения: 940
Зарегистрирован: 07.10.18 14:01

Re: Обсуждение 2020-04-17 про сборку мусора

Сообщение БудДен » 18.04.20 10:15

Всем спасибо за комментарии. Я просто хотел зафиксировать эту беседу. Я считал изначально, что ключевое слово REALTIME, к-рое в 2015 году сломали, является серебряной пулей для совмещения задач реального времени и сборки мусора. Активности со словом REALTIME могут работать во время сборки мусора (и они ограничены в работе с динамической памятью, на уровне компилятора). А оказывается, что ситуация сложнее и одного этого недостаточно. На IBM-овский метроном я когда-нибудь посмотрю, но сейчас я пытался понять, правильно ли я выбрал дату для ответвления. Мне не нравятся Lock-free алгоритмы, а слово REALTIME теперь надо чинить. Но всё же моя задача сейчас - в переводе A2, а не в каких-то изобретениях, поэтому и эта версия пойдёт. А починку REALTIME и дальнейшее улучшение подсистемы реального времени можно оставить в качестве упражнения.

Ответить