Здравствуйте, Ops, Вы писали:

Ops>Это если рандом.

Слава богу для современных многоядерных процов всегда рандом, это принципиально.
Т.е. их ядра хоть и работают на одинаковой частоте, но характер задержек при обращении к когерентному кешу, при спотыканиях конвейера и т.д. — он имеет случайную природу. А самое главное — одновременно проходящие и не проходящие CAS-операции на одной и той же точке кода перещёлкивают признаки у предсказателя переходов.


Ops>Но подозреваю, что реальные системы не совсем случайно работают, и может возникнуть ситуация, когда несколько потоков висят заметно долго.

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


V>>Т.е. вероятность того, что поток не продвинется на следующем такте очень быстро стремится к 0-лю с каждым заходом на новый круг.
Ops>Формулировка — . Случайное событие не зависит от предыдущих случайных событий.

Да ладно.
Формулировка ж из классики жанра — как лакмусовая бумажка для выявления понимающих второй закон термодинамики. ))

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

Т.е., чтобы получить, допустим, на 10-м обороте алгоритма вероятность 1/2, мы сначала должны были оказаться на 9-м обороте с вероятностью (1/2)⁹.
Обратив на этом обороте время, получается такой забавный трюк, что вероятность застревания в ближайшем будущем в 256 раз больше вероятности застревания в прошлом. ))
Ну и всё, собсно. ))
Иначе бы энтропия не росла.

Еще важный момент: в хороших lock-free алгоритмах (плохими не пользуюсь), чем больше нагрузка, тем меньше вероятность столкновения, бо данные забираются потребителем "пачками". Т.е. потребитель потенциально конфликтует (с некоторой небольшой вероятностью) лишь на каждый N-й передаваемый ему элемент, где N при увеличении нагрузки растёт. Т.е. мало того, что вероятность столкновений при увеличении нагрузки резко падает, так еще резко падает как общее кол-во interlocked-операций, так и общая нагрузка на механизм поддержания когерентности кеша. В моих тестах под нагрузкой межпоточные очереди по схеме "один источник — один приёмник" показывали до 20-ти раз увеличение быстродействия от средней нагрузки, сверху этого показывали отсуствие даже единичных конфликтов долгими часами. По схеме "много источников — один приёмник" показывали более частые конфликты, но всё-равно — один лишний оборот на тысячи элементов. Т.е. в пересчёте на элемент ни о чём.


Ops>Но с тем, что ты хотел сказать, пусть и получилось криво, в принципе согласен, с предыдущей оговоркой.

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

Здравствуйте, Ops, Вы писали:

Ops>Это если рандом.

Слава богу для современных многоядерных процов всегда рандом, это принципиально.
Т.е. их ядра хоть и работают на одинаковой частоте, но характер задержек при обращении к когерентному кешу, при спотыканиях конвейера и т.д. — он имеет случайную природу. А самое главное — одновременно проходящие и не проходящие CAS-операции на одной и той же точке кода перещёлкивают признаки у предсказателя переходов.


Ops>Но подозреваю, что реальные системы не совсем случайно работают, и может возникнуть ситуация, когда несколько потоков висят заметно долго.

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


V>>Т.е. вероятность того, что поток не продвинется на следующем такте очень быстро стремится к 0-лю с каждым заходом на новый круг.
Ops>Формулировка — . Случайное событие не зависит от предыдущих случайных событий.

Да ладно.
Формулировка ж из классики жанра — как лакмусовая бумажка для выявления понимающих второй закон термодинамики. ))

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

Т.е., чтобы получить, допустим, на 10-м обороте алгоритма вероятность 1/2, мы сначала должны были оказаться на 9-м обороте с вероятностью (1/2)⁹.
Обратив на этом обороте время, получается такой забавный трюк, что вероятность застревания в ближайшем будущем в 256 раз больше вероятности застревания в прошлом. ))
Ну и всё, собсно.
Иначе бы энтропия не росла.

Еще важный момент: в хороших lock-free алгоритмах (плохими не пользуюсь), чем больше нагрузка, тем меньше вероятность столкновения, бо данные забираются потребителем "пачками". Т.е. потребитель потенциально конфликтует (с некоторой небольшой вероятностью) лишь на каждый N-й передаваемый ему элемент, где N при увеличении нагрузки растёт. Т.е. мало того, что вероятность столкновений при увеличении нагрузки резко падает, так еще резко падает как общее кол-во interlocked-операций, так и общая нагрузка на механизм поддержания когерентности кеша. В моих тестах под нагрузкой межпоточные очереди по схеме "один источник — один приёмник" показывали до 20-ти раз увеличение быстродействия от средней нагрузки, сверху этого показывали отсуствие даже единичных конфликтов долгими часами. По схеме "много источников — один приёмник" показывали более частые конфликты, но всё-равно — один лишний оборот на тысячи элементов. Т.е. в пересчёте на элемент ни о чём.


Ops>Но с тем, что ты хотел сказать, пусть и получилось криво, в принципе согласен, с предыдущей оговоркой.

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