рилтайм и сборка мусора

>запускаются одновременно... Один процесс ведущий, другой - ведомый

Нестыковку не замечаешь?

В realtime вполне допустимы паузы. Более того, они неизбежны. Вопрос только в том, ограничена ли сверху величина этих пауз.

> Нестыковку не замечаешь?
Если про процесс известно (не ему, а «менеджеру мусоросборного рилтайма»), что процесс ведомый, то на первом же вызове IO он зависнет и будет висеть, пока ведущий процесс не завершит этот вызов.

> Вопрос только в том, ограничена ли сверху величина этих пауз.
Например, в музыкальном софте плохо, если задержки по тракту существенно больше 10мс. Или что-то такого порядка, точно не помню. Необходимость уложить сборку мусора в 10мс накладывает принципиальные ограничения на количество объектов в куче.

>на количество объектов в куче

на алгоритмы и количество извилин у разработчиков.

> и количество извилин у разработчиков
При неограниченном количестве извилин ЯП вообще не нужны - можно сразу выражать идеи в машинном коде.

> Например, в музыкальном софте плохо, если задержки по тракту существенно больше 10мс.

Значит, ОСРВ с такими задержками непригодна для музыкального софта (если считать музыку задачей жесткого РВ).

> Значит, ОСРВ с такими задержками непригодна для музыкального софта (если считать музыку задачей жесткого РВ).
А мы можем перейти от тавтологии к обсуждению темы или я всё же ошибся форумом?

>> Значит, ОСРВ с такими задержками непригодна для музыкального софта (если считать музыку задачей жесткого РВ).

А мы можем перейти от тавтологии

Если для тебя простейшие определения из области РВ - тавтология, то тебе рано обсуждать РВ.

к обсуждению темы или я всё же ошибся форумом?

Совмещение РВ и сборки мусора делается совершенно по-другому. Можешь начать с алгоритма Бейкера, продолжить алгоритмами, реализованными в JVM 1.5 и Метрономом (и учти, что полностью годного для РВ алгоритма просто нет, или он мне неизвестен).

А твоя идея с журналом - просто какой-то мутный бред, если неизвестны характеристики используемых алгоритмов сборки мусора; если же они известны, то с двумя процессами тупо неет смысла заморачиваться.

Это всё не говоря о том, что реальная работа в РВ сильно завязана на время, а ты предлагаешь просто врать о времени (брать его показания из журнала), что просто пугает.

Какой у вас опыт в разработке систем, работающих в реальном времени? Где можно на ваш код посмотреть?

> Какой у вас опыт в разработке систем, работающих в реальном времени?

~15 лет

Где можно на ваш код посмотреть?

Смотря кто ты такой.

Покажите его всем. Моя личность значения не имеет. Есть подозрение что вы путаете «слышал о чем-то» и «умею что-то».

> Покажите его всем.

Ты в своем уме? %)

Моя личность значения не имеет

Смотря для чего. У кучи людей есть доступ к тому, что я писал - может, ты один из этих людей.

Есть подозрение что вы путаете «слышал о чем-то» и «умею что-то».

А реальное основание у подозрения есть?

В кои-то веки согласен с tailgunner.

Ты написал бредятину.

Для реалтайма существуют алгоритмы инкрементальных сборщиков мусора.
Вот тут можно ознакомиться некоторыми:
ftp://ftp.cs.utexas.edu/pub/garbage/bigsurv.ps

> Это всё не говоря о том, что реальная работа в РВ сильно завязана на время, а ты предлагаешь просто врать о времени (брать его показания из журнала), что просто пугает.
Ты просто не понял идею, а не понял ты её потому, что не захотел понять. Если захочешь понять, задай уточняющие вопросы.

просто какой-то мутный бред, если неизвестны характеристики используемых алгоритмов сборки мусора

Ты к моему описанию добавил свои слова и потом назвал это мутным бредом. Может это и бред, но это тогда твой бред, а не мой.

Метрономом

Вот, толк от тебя всё же есть. Теперь я, наконец, начинаю понимать, что есть инкрементная сборка мусора, которая выторговывает уменьшение пауз за счёт производительности. Хотя я пока не понял смысл её работы, сколько это стоит и каковы гарантируемые результаты.

>> Это всё не говоря о том, что реальная работа в РВ сильно завязана на время, а ты предлагаешь просто врать о времени (брать его показания из журнала), что просто пугает.

Ты просто не понял идею

Вызовы, связанные со временем, журнализуются, и потом это журнал используется для ответов второму процессу. Так или нет?

а не понял ты её потому, что не захотел понять.

Ты хочешь песочницу, в которой программы с GC волшебным образом становятся РВ-программами. Если это не так, тоо объясни нормально, какую именно задачу ты решаешь, потому что ты предлагаешь решение чего-то, но чего именно - непонятно.

Метрономом

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

Анонимус дал гораздо лучшую ссылку - там и про инкрементальность написано. Но многабукаф, да.

>Вызовы, связанные со временем, журнализуются, и потом это журнал >используется для ответов второму процессу. Так или нет?
Да.

Ты хочешь песочницу, в которой программы с GC волшебным образом становятся РВ-программами.

Я понимаю, что за это надо платить. Вопрос, чтобы цена была конечной.

про инкрементальность написано

Посмотрю.

Чтобы это реально работало, необходим более чем двухкратный запас производительности: либо пускать задачи на двух ядрах параллельно, либо переключать их на одном, но тогда не понятно, как вообще изменится время отклика системы.
Оно вообще надо?

>>Вызовы, связанные со временем, журнализуются, и потом это журнал используется для ответов второму процессу. Так или нет?

Да.

Ну тогда объясни мне, как будет работать этот простой фрагмент кода и что из него получится:

/* записываем управляющий пакет на устройство */
write(dev_fd, &ctl_pkt, sizeof(ctl_pkt));
/* отмечаем этот факт в логе */
gettimeofday(&ts, NULL);
print_log(ts, «выдали управление на устройство»);

Ты хочешь песочницу, в которой программы с GC волшебным образом становятся РВ-программами.

Я понимаю, что за это надо платить.

То есть задачу я понял правильно.

write(dev_fd, &ctl_pkt, sizeof(ctl_pkt)); // ждёт, пока мастер сделает этот вызов, сам ничего не пишет, возвращает тот же результат, что и вызов в мастере
gettimeofday(&ts, NULL); // аналогично
print_log(ts, «выдали управление на устройство»); // аналогично

Короче, бред. Выполнение будет состоять из сплошных проверок, блокировок и ожиданий.

>Чтобы это реально работало, необходим более чем двухкратный запас >производительности: либо пускать задачи на двух ядрах параллельно, >либо переключать их на одном, но тогда не понятно, как вообще >изменится время отклика системы.

Оно вообще надо?

Нужно сравнивать с другими вариантами, только тогда станет ясно. Во всяком случае, меня радует то, что моим способом (вроде) можно всё же добиться результата хотя бы ценой двукратной переплаты по памяти и производительности. В остальных случаях мне это пока неясно. Вот, например, статья по метроному, http://www.research.ibm.com/people/d/dfb/papers/Bacon03Controlling.pdf
они добились (не знаю на каком железе) того, что паузы в программе не превосходят 6мс. Учитывая, что рантайм становится намного сложнее (например, происходит сегментация массивов, обращение к любому объекту происходит через два указателя и ещё есть барьер чтения), они тоже заплатили немало и по памяти, и по скорости. Может быть, у них получается переплата более, чем вдвое. А паузы - только в 6мс, на грани допустимого для музыкальных программ. При моём подходе, если я ничего не путаю, можно сделать паузы сколь угодно малыми, ведь можно сделать не два чередующихся процесса, а N процессов. Зная максимальную долю сборки мусора в общих затратах вычислительного времени, по всем интервалам времени от 0 до +inf, просто делим единицу на эту долю и получаем N. Примерно так. А может и не так, я для того и пришёл сюда, чтобы разобраться и сравнить с альтернативами. Точнее говоря, свою идею я кинул только для затравки и думал, что меня сразу ткнут носом в правильное решение. В другое решение меня ткнули, но лучше ли оно, чем моё - я пока что не знаю.

Как определяется, что вызов «тот самый»? И как это сочетается с активностью устройства (с него идут прерывания - что делается с ними)?

>двукратной переплаты по памяти и производительности

Это в сферическом вакууме, когда программы подавляющую часть времени занимаются рассчётами, не взаимодействуя с внешним миром. На практике все бывает наоборот. И сколько вычислительных ресурсов уйдёт на поддержание журнала системных вызовов (нужно же еще сохранять все результаты вызовов, пока слейв их не «подобрал») и на постоянные синхронизации...

Ну насколько я понимаю,

Как определяется, что вызов «тот самый»?

Предполагается, что алгоритмы полностью детерминированы внешней средой и выдают одинаковые последовательности вызовов. Можно даже банально считать вызовы: 1-й, 2-й...

с него идут прерывания - что делается с ними

Их в реальном времени видит мастер. Слейв их видит не раньше, чем выполнит то количество вызовов, после которого прерывание было увидено мастером.

>>с него идут прерывания - что делается с ними

Их в реальном времени видит мастер.

Мастер и слейв периодически меняются ролями.

Слейв их видит не раньше, чем выполнит то количество вызовов, после которого прерывание было увидено мастером.

Это предполает, что оба процесса пойдут по жестко детерминированным путям в коде. Лично мне это кажется в лучшем случае хрупким основанием для построения работающей системы.

>прерывания

И тут слабое место этого подхода. Реакиця на прерывание не должна зависеть на от внутреннего состояния алгоритма. Если прерывания, пришедшие, когда программа была в состояниях s1 и s2, обрабатываются по-разному, значит переход из одного состояния в другое тоже должен логгироваться. Мда..

>Лично мне это кажется в лучшем случае хрупким основанием для построения работающей системы.

Мне тоже. Но раз ТС предложил рассмотреть такие сферические алгоритмы...

Мастер и слейв периодически меняются ролями.

Угу. И, кстати, необходимым условием для переключения должен быть пустой журнал — т.е. слейв должен догнать мастера, и только в этот момент можно переключиться. А учитывая, что слейв вставал на сборку мусора... RT, как мне видится, становится всё призрачней.

> А учитывая, что слейв вставал на сборку мусора...

ВотЪ. Без точных характеристик сборщика мусора даже обсуждать «а как работать с внешними устройствами» рановато. А если есть детерминированный сборщик мусора... то и два процесса не нужно :)

процесс 1       шедулер            процесс 2
стал ведущим                    стал ведомым
1                                  write (suspend)
2              пора запустить GC(2)?  <-----    
                нет. suspend
3 write (suspend) 
4 write завершён 
               пишем результаты write в журнал
                 resume(2)    --> получил возврат write
5                          gettimeofday (suspend)
6              журнал пуст. Пора запустить GC(2)?  <-----    
                да. 
7 gettimeofday(suspend)
8 gettimeofday завершён
9                пишем в журнал
10                gc(2) завершён
11                 возвращаем из журнала в процесс 2
12                 поскольку в gc(2) мусор собран, 
                   хотим сделать его ведущим. 
                   11-8<макс_допустимое_отставание?  Да. 
                   процесс 2 становится ведущим. 
                   процесс 1 становится ведомым
                   gc(1)
13                                        print_log (suspend)
14                                        print_log вернулся          
15 print_log - берём из журнала. 

Примерно вот так.

> Это предполает, что оба процесса пойдут по жестко детерминированным путям в коде.
А что может им помешать, если весь ввод-вывод и рандом мы вынесли вовне? По-моему, процессор - это всё же штука детерминированная. Во всяком случае, если каждый процесс - однонитевый.

Реакиця на прерывание не должна зависеть на от внутреннего состояния алгоритма.

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

Один процесс ведущий, другой - ведомый. Имеется журнал IO, в который заносятся все вызовы, относящиеся к внешнему миру (обращение к таймеру, sleep, случайные числа, ввод-вывод), и результаты, которые получены из внешнего мира. Соответственно, ведущий процесс делает эти вызовы и журнализирует их. Ведомый процесс не делает вызовов, он вместо этого обращается к журналу, откуда берёт результат вызова. Через короткое время в ведомом процессе принудительно запускается сборка мусора. После сборки мусора ведомый процесс «догоняет» ведущий, идя по журналу функций внешнего мира, после чего они меняются местами. Теперь в новом ведомом процессе запускается сборка мусора, потом он «догоняет» ведущий, потом они меняются местами и т.п.

Это ты примерно описал Erlang :) Только там несколько планировщиков по количеству ядер (ведущие - обычные ОС-нити, привязанные по affinity к ядрам), а все остальные процессы (уровня VM, ведомые) - распределены между ними. Когда код ведомого процесса компилируется - после каждых n редукций (фактически - аппликаций функции) ставится что-то вроде jupm на ассоциированный планировщик, тот переключает на другой процесс, и т.д. + есть приоритеты (вытесняющая многозадачность). Так происходит параллельное выполнение процессов - это возможно потому что все редукции чистые (не имеют побочных эффектов). Особые операции - обмен сообщениями и IO. Лёгкий процесс (на каждый - структура общим счётом ~500 байт) имеет очереди (r/w queue) входящих и исходящих сообщений, при этом они ассинхроные, поэтому обмен сообщениями происходит довольно просто (написали - забыли, читать можно по мере надобности). С IO тоже самое, только асинхронные сообщения посылаются (и принимаются) к (от) специальному треду, выполняющему IO (так инкапсулируются побочные эффекты - в отдельном треде).

Насчёт GC там два важных момента - во-первых GC работает отдельно с каждым процессом (он может работать с ними отдельно, используя SMP, если это возможно), во-вторых сборщик упрощённый инкрементальный - упрощённый он потому что нет мутабельных структур данных, т.е. механизм сборки несколько облегчается.

Вообще, Erlang может гарантировать soft real time поведение.

Вот ещё ссылка на тему: http://prog21.dadgum.com/16.html

И цитата:

ESC:

* Creating and destroying processes is very fast.

* Sending and recieving messages between processes is very fast. Message passing is asynchronous.

* Processess behave the same way on all operating systems.

* We can have very large numbers of processes, >> 10 000.

* Processes share no memory and are completely independent. The only way for processes to interact is through message passing.

* Processes can monitor each other.

* It is possible to selectively receive messages.

* Remote processes appear largely the same as local processes.

Erlang processes are currently scheduled on a reduction count basis. One reduction is roughly equivalent to a function call. A process is allowed to run until it pauses to wait for input (a message from some other process) or until it has executed 1000 reductions.

There are functions to slightly optimize the scheduling of a process (yield(), bump_reductions(N)), but they are only meant for very restricted use, and may be removed if the scheduler changes.

A process waiting for a message will be re-scheduled as soon as there is something new in the message queue, or as soon as the receive timer (receive ... after Time -> ... end) expires. It will then be put last in the appropriate queue.

Erlang has 4 scheduler queues (priorities): 'max', 'high', 'normal', and 'low'.

'max' and 'high' are strict. This means that the scheduler will first look at the 'max' queue and run processes there until the queue is empty; then it will do the same for the 'high' queue.

'normal' and 'low' are fair priorities. Assuming no processes at levels 'max' and 'high', the scheduler will run 'normal' processes until the queue is empty, or until it has executed a total of 8000 reductions (8*Max_Process_Reds); then it will execute one 'low' priority process, if there is one ready to run.

The relationship between 'normal' and 'low' introduces a risk of priority inversion. If you have hundreds of (active) 'normal' processes, and only a few 'low', the 'low' processes will actually get higher priority than the 'normal' processes.

There was an experimental version of a multi-pro Erlang runtime system. It supported Erlang processes as OS threads, and then used the scheduling and prority levels of the underlying OS.

One important thing to note about the scheduling is that from the programmer's perspective, the following three things are invariant:

- scheduling is preemptive. - a process is suspended if it enters a receive statement, and there is no matching message in the message queue. - if a receive timer expires, the process is rescheduled.

The Erlang Processor, for example, will most likely schedule based on CPU cycles (essentially a time-based scheduler). It may also have multiple thread pools, allowing it to context switch within one clock cycle to another process if the active process has to e.g. wait for memory.

In a runtime environment that supports it, it should be possible to also have erlang processes at interrupt priority (meaning that they will be allowed to run as soon as there is something for them to do — not having to wait until a 'normal' priority process finishes its timeslice.)

>А если есть детерминированный сборщик мусора... то и два процесса не >нужно :)
Так в том-то и вопрос, есть ли такой сборщик мусора или нет его. Вот статью про метроном я ещё не дочитал. Но я ожидал там увидеть что-то вроде графика того, каковы накладные расходы в зависимости от параметров процесса (размер памяти, относительная скорость выделения и что там третье). Есть предположение, что при плохом сочетании параметров там всё становится нелинейно плохо.

Вообще, в целом, я правильно понимаю, что сборка мусора с остановкой процесса занимает линейное время от количества живых объектов, если для каждого указателя есть forwarding pointer? А для инкрементной как это выглядит? Неужели тоже линейно? Что-то из интуитивных соображений кажется, что там должно быть что-то более плохое.

> Это ты примерно описал Erlang :)

Даже и близко не похоже.

>По-моему, это можно обустроить, если аппаратные прерывания будет воспринимать шедулер, а рабочие процессы будут заниматься только вычислениями и единственное прерывание, которое они могут воспринимать, происходит от шедулера. Хотя это может быть и слабым местом в моих рассуждениях.

Я в программе делаю a = 1;, а в обработчике исключения стоит if (a) {...}. И всё, 2 копии программы рассинхронизированы. Вывод: все подобные «a = 1» должны осуществляться через системные вызовы.

> Это ты примерно описал Erlang :)
По-моему, нет. У меня два процесса делают одно и то же.

> а в обработчике исключения стоит
Откуда взялось это исключение, вот в чём вопрос? Прерывания от шедулера должны быть невидимы для логики процесса, остальные события во внешнем мире должны быть узнаваемы через вызовы изнутри рабочего процесса.

Я ничего не сказал про память. Памяти ессно, должно хватать всегда. Потому что нехватка памяти - это, по-любому, конец света. Значит, если мы когда-то на программном уровне отказываем в памяти, то это должно происходить в обоих процессах одинаково. Конечно, тут можно придраться, ведь процессы по-разному вызывают GC и, значит, память может кончиться у одного процесса и не кончиться в том же месте у другого. Предлагаю пока это отложить на потом :-) Видимо, при достаточном резерве памяти этот вопрос можно сделать неактуальным.

По-моему, нет. У меня два процесса делают одно и то же.

Ну если именно два и именно так - то да, совсем не похоже. А, кстати, почему именно так? Что получится при обобщении на n процессов? Очевидно ведь, что будет фиксированное количество планировщиков и переменное количество воркеров которые переключаются (посредством сигналов или редукций) и асинхронно обмениваются сообщениями между собой (MP) и внешним миром (IO).

Тем не менее soft real time in Erlang + GC in Erlang — вполне сабж.

>Откуда взялось это исключение, вот в чём вопрос? Прерывания от шедулера должны быть невидимы для логики процесса, остальные события во внешнем мире должны быть узнаваемы через вызовы изнутри рабочего процесса.

Т.е. тупой пулинг, вместо реакций на асинхронные события? Сурово. Сибирским мужикам, паяющием спектрумы в гаражах, идея будет по душе.

Кстати, вот: http://prog21.dadgum.com/15.html

>Т.е. тупой пулинг, вместо реакций на асинхронные события? Сурово. >Сибирским мужикам, паяющием спектрумы в гаражах, идея будет по душе.
Не могу понять иронии. Я просто хочу разобраться. Пулинг вместо прерываний - вещь небезплатная, но и другие варианты тоже дорогостоящи. Где мера?

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

И цитата:

The incremental collectors I'm familiar with work that way: they involve a full, non-incremental marking phase, and then copying and compaction are spread out over time. This means that the expense of such a collector is proportional to the amount of data that must be scanned during the marking phase and as such has a lurking pathological case.

> Примерно вот так.

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

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

P.S. это не говоря о милых мелочах вроде ioctl(dev_fd, SOME_CODE, &var). Как ты собираешься отслеживать такие вещи?

> Т.е. тупой пулинг,

Когда я слышу «пулинг» вместо «поллинг», мне хочется медленно и жестоко убивать.

>А ещё можно всё писать без сборки мусора вообще. Дёшево и сердито, правда, требуется больше извилин.

И мне эта идея нравится больше всего.

Потому что ваш гипотетический RT получается слишком не бесплатным: 1. С более чем двукратной избыточностью ресурсов. 2. Со сложным, череватым ошибками, рантаймом. Которые замучишься отлаживать. 3. Однопоточный. (Либо в виде отдельных процессов, взаимодействующих через системные вызовы. Каждый в двойном экземпляре.) 4. Без возможности асинхронного реагирования на сигналы/прерывания.

>поллинг

Посыпаю голову пеплом.

> Когда я слышу «пулинг» вместо «поллинг»
Мне это тоже показалось странным, но ввиду общей безграмотности я решил, что это я чего-то недопонял.

Я не понял, как именно ты определишь, следует ли выдать запись на устройство.

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

> И мне эта идея нравится больше всего.
Мне она тоже, в общем-то нравится, но я всё же ищу поводы применить более простые для разрабочика языки в RT. Например, лисп.

Потому что ваш гипотетический RT получается слишком не бесплатным:

Сборка мусора и безплатность - это совершенно разные вещи :-) Даже без RT. Во всяком случае, результат кажется мне заведомо достижимым таким путём, без особых ограничений. Цена известна, прейскурант содержит все возможные предложения. Кому дорого, тот идёт в другой магазин. В случае инкрементной сборки мусора, похоже, это всё же не так. Хотя, может быть, tailgunner или ещё кто-то опровергнут последнюю приведённую мной цитату.

>> Я не понял, как именно ты определишь, следует ли выдать запись на устройство.

Ведущий процесс всегда выполняет вызов в реальности. Ведомый процесс никогда этого не делает.

...пока они не поменялись ролями. И когда они меняются, то новый мастер остается с невыполненными операциями В/В и журналом, из которого результаты этих операций подделываются. Результаты каких именно операций подделываются - всех, насколько хватит журнала?

Хо-хо! Какая милая идея. От себя добавлю что тут нужен язык в котором существует явное отделение чистых функций от функций с побочными эффектами (то есть это не CL ни разу). С другой стороны представь себе ситуацию, что где-то в программе вызывается вполне чистая функция Аккермана. То есть как бы не вышло что твои процессы довольно сильно разбежались по «реальному времени». Тогда они просто съедят всю доступную память. Или все чистые функции мы тоже кешируем?

Например, в музыкальном софте плохо, если задержки по тракту существенно больше 10мс. Или что-то такого порядка, точно не помню. Необходимость уложить сборку мусора в 10мс накладывает принципиальные ограничения на количество объектов в куче.

У мну ночальнег в 80-х работал в Дженсим, они проблему со сборкой мусора в рилтаймных управляющих системах решили просто: мусор не плодили.