Теорема
Порядковая и мультипликативная размерность частично-упорядоченного множества совпадают.
P.S. Размерность частично-упорядоченного множества можно интерпретировать
- как степень параллельности процессов в системе
- как размерность времени системы
(детальнее смотри в книге на стр. 58).
воскресенье, 12 сентября 2010 г.
Подписаться на:
Комментарии к сообщению (Atom)
"Concurrent" in "concurrent programming" stands for "одновременный" rather than "конкурирующий". By translating it as "конкуретное программирование" you basically invert the meaning of the term - threads are not competing with each other, they are working simultaneously.
ОтветитьУдалитьСогласен, "степень распаралелленности системы" возможно более корректно.
ОтветитьУдалитьКстати, думаю над твоим тезисом - http://software.intel.com/ru-ru/blogs/2009/02/07/fifo/.
Я его переформулировал так:
Если имеется N+1 асинхронных процесс (в терминах книги Lynch - без глобального времени) и все сообщения исходящие от процесса №(N+1) находятся в отношении happens-before, то "мера распаралелленности системы" меньше чем N. Т.е. если история системы позволяет установить глобальный порядок сообщений от одного из процессов, то остальные процессы должны за это платить (эдакая количественная фиксация наличия "виртуального наблюдателя").
Скорее всего также необходимо отделить "виртуального наблюдателя" от остального функционала системы, скажем - "минимальное подмножество сообщений в системе позволяющее установить глобальный порядок". Иначе, если распределенный процесс не только вытаскивает сообщения из очереди, но и занят чем-то еще, то размерность системы будет равна Максимуму этих двух размерностей.
Возможно
Я правильно понимаю, что ты имеешь в виду, что если мы построим направленный ациклический граф (DAG) системы, где вершинами выступают сообщения (обработка сообщения процессом), а связями happens-before отношения, потом ранжируем граф (вычислим ранги вершин), то количество вершин на каждом ранге - есть степень параллельности системы (количество процессоров, которое она может утилизировать)?
ОтветитьУдалитьПолучается что каждое happens-before отношение уменьшает параллельность на 1.
Путаница с терминологией - что ты понимаешь под рангом вершины?
ОтветитьУдалить- количество исходящих ребер?
- расстояние от корня графа?
Извиняюсь, я имел в виду ярус графа:
ОтветитьУдалитьhttp://ru.wikipedia.org/wiki/%D0%AF%D1%80%D1%83%D1%81%D0%BD%D0%BE-%D0%BF%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%B0
Кол-во вершин на ярусе - параллельность.
тут рисунок - http://picasaweb.google.com/104861960997088986052/qeSppG?authkey=Gv1sRgCMLW17G7mNb-NA#5517533366035573570
ОтветитьУдалить{R0,R1,R2,R3} - читатели из очереди Queue.
Вопрос: чем существенным отличаются системы, в которых все сообщения от одного из процессов (queue) возможно упорядочить анализируя историю сообщений, от произвольных систем?
Т.е. сообщения a1,b1,c1,d1 возможно упорядочить анализирую историю.
Т.е. a1->b1->c1->d1
("->" - causal order)
Т.е. в системе читателей необходимо присутствуют некоторые сообщения (зеленые), которые с получениями данных из очереди (красные) образуют непрерывную цепочку, обходящую всех читателей.
Я пока вижу два очевидных вывода:
1) читатели не могут состоять из "автономных групп", т.е. любые два читателя имеют события увязанные по "->".
2) наличие цепочки ограничивает частоту сообщений, читаемых их очереди, не только скоростью очереди, но и скоростью обмена сообщениями между читателями.
3) процесс не может в произвольный момент времени ("по своему желанию") послать запрос очереди и в ответ получить данные от очереди. Предварительно процесс должен получить сообщение от друго читателя, устанавливающее отношение "->" между последовательными сообщениями из очереди.
---
Интересно было бы
1) понять все последствия наличия "виртуального наблюдателя"
2) иметь метрику, позволяющие обнаружить "виртуального наблюдателя"
---
P.S. Эта цепочка сообщений и образует "виртуального наблюдателя".
Этот комментарий был удален автором.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьхотя пункт 3) вывода не совсем верен
ОтветитьУдалитьвозможна такая ситуация (http://picasaweb.google.com/104861960997088986052/qeSppG?authkey=Gv1sRgCMLW17G7mNb-NA#5517543290148651730):
процесс R2 послал заброс msg2 в очередь на чтение данных. он был заблокирован очередью. Но в момент когда пришло сообщение msg3 от читателя R3 (тоже запрос на чтение данных или просто "передача маркера") очередь смогла отдать данные чатателю R2 в сообщениии msg4. Некоторый вариант блокирующего чтения, когда сама очередь следит за установлением отношения "->".
> тут рисунок - http://picasaweb.google.com/104861960997088986052/qeSppG?authkey=Gv1sRgCMLW17G7mNb-NA#5517533366035573570
ОтветитьУдалитьНа рисунке система с нулевым параллелизмом, она работает как централизованная система - полностью детерминированная. Не понятно, ты это и хотел изобразить или так получилось? Если это и хотел, но не понятно что в такой системе анализировать. Есть так получилось, то не понятно, что ты хотел изобразить.
... или тут имеется в виду, что в системе так же есть произвольное число произвольных сообщений между R0-R3 (не изображены), которые не приводят к отправке сообщений Queue. А изображены только сообщений, которые следуют за, и приводят к отправке сообщений Queue?
ОтветитьУдалитьДля меня первый приходящий в голову вывод: нет гонок при обработке сообщений от Queue... хотя это свойство быстро "растворяется", т.к. при обработке производных сообщений (сообщений, отправленных во время обработки сообщений от Queue) гонки уже возможны.