Беззамочные алгоритмы: модель «сделай, запиши,(попытайся снова)»

[egorinsk]

> Беззамочные алгоритмы

Epic fail, даже читать неохота дальше

[tyomitch]

«Неблокирующие» не отражает сути дела: важно не то, что синхронизация не блокирует поток, а то, что, что ни у одного ресурса нет единственного владельца, запрещающего доступ к ресурсу всем остальным.

Например, синхронизация при помощи TryEnterCriticalSection — неблокирующая, но не беззамочная.

[gridem]

Вообще-то, термин «беззамочная» в литературе нигде не используется. В вашем случае CalculateSomethingAboutSystemColors использует lock-free алгоритм. Поэтому не стоит вводить людей в заблуждение. Речь идет не о «замках», а о локах, точнее об их отсутствии.

[tyomitch]

Так как вы предлагаете это называть? «Безлочная»?

[mark_ablov]

использовать английские термины вместо попыток их перевода на русский? :)

[tyomitch]

Панталоны, фрак, жилет — всех этих слов на русском нет?
Дело вкуса, конечно. Кому-то и «приложеньице» вместо «апплет» резало слух. Но само «приложение» вместо «аппликация» ведь прижилось.

[gridem]

Предлагаю так, как описано в википедии:

Без ожиданий (wait-free)

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

Без блокировок (lock-free)

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

[Ivanhoe]

Просто не переводить?

[tenshi]

блокируется не поток, а ресурс. а ресурсы бывают разные — процессор, память, винт…

по теме, зачем вообще использовать общие переменные в многопоточном приложении? это широкое поле для всякого рода косяков. тут сообщения надо использовать. для каждого такого синглтона заводится отдельный поток с очередью сообщений, потом другие потоки просят первый «дай ка мне объектик», тот создаёт объект, если его нет, и пуляет во всех подписавшихся.

[tyomitch]

блокируется не поток, а ресурс. а ресурсы бывают разные — процессор, память, винт…

Не понимаю, что вы пытаетесь сказать. Показать вам стопицот гуглхитов по запросу «поток блокируется»?

по теме, зачем вообще использовать общие переменные в многопоточном приложении? тут сообщения надо использовать.

Вы сомневаетесь, что реализована передача сообщений именно через общие переменные?

[tenshi]

в гугле много глупостей. блокируется ресурс, а поток уже может ждать его разблокировки (так называемая «блокировка потока») а может не ждать и воспользоваться другим (в случае, например, «пула ресурсов»).

я сомневаюсь в необходимости велосипедирования. очередь сообщений пишется и отлаживается 1 раз и далее используется всеми.

[tyomitch]

в гугле много глупостей. блокируется ресурс, а поток уже может ждать… а может не ждать

Хорошо, принимаю вашу терминологию. Что дальше? Какой тезис вы аргументируете?

я сомневаюсь в необходимости велосипедирования.

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

[tenshi]

неблокирующий — вполне подходящий термин

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

[tyomitch]

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

Также вспомню знаменитое «патентное бюро можно закрывать: всё, что можно было изобрести, уже изобретено» (1899)

[tenshi]

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

какой смысл изобретать уже изобретённое?

[tyomitch]

— А к чему бы это служило на первый случай?
— На первый случай сгодилось бы и к тому, что ежели б случилось ехать, так знаешь, куда едешь.
— Ах, мой батюшка! Да извозчики-то на что ж? Это их дело. Это-таки и наука-то не дворянская. Дворянин только скажи: повези меня туда, свезут, куда изволишь.

[mark_ablov]

Классика же, довольно часто такое используется.
Да и алгоритм ясен, стоит только посидеть, подумать и представить что в любой момент поток2 получает управление.

[gridem]

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

[maxcom]

промпт 1.0, оригинал, впрочем, не сильно лучше

[koct9i]

Перевод терминов доставляет, примеры нужно было писать на Алгол-68.