Pull to refresh

Comments 28

UFO landed and left these words here
фьютекс это и есть спинлок :)
UFO landed and left these words here
Не совсем :) spinlock в ядре Линукса существует уже давно, а вот futex — с ядра 2.6. Futex отличается от спин-лока наличием формализованного интерфейса, подобного mutex'ам, в то время, как спинлок делался и делается «как бог на душу положит» :) Кроме того, спинлоки используются в ядре, в то время, как futex — для user-space
Спинлоком называется любой busy-wait примитив. Нет разницы в ядре он или в user-space, атомарные операции обычно реализуются через непривилегированные инструкции.
Обычно в спинлоке ещё есть счётчик максимального количества busy-wait циклов, после этого он говорит ядру — я не дождался, поток можно суспендить.
В NT CRITICAL_SECTION тоже содержит в себе спинлок, который можно инициализировать через InitializeCriticalSectionAndSpinCount.
>>Спинлоком называется любой busy-wait примитив

Я примерно так и сказал — «как бог на душу положит» :)
Насчет user-space — Вы безусловно правы, но я имел в виду, что, несмотря на похожесть интерфейсов с mutex, sysenter (т.е. вход в ядро и манипуляции с планировщиком потоками) не вызывается, и ожидание идет за счет пустого (или почти пустого) цикла.

Насчет SpinCount в NT уже и забыл :)
мутно очень, многого не понял. А для тех, кто поймет, тут наверное очевидные вещи.
Так и есть) Как-то слишком размыто и абстрактно.
Попытайтесь, пожалуйста, сформулировать что вы не поняли, это важно. Я буду редактировать и дописывать статью. Это так, черновой вариант.
Мьютекс получается из семафора со значением 1

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

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

По ходу для обычных 32-бит используют обычный cmpxchg, который полегче будет, а cmpxchg8b достаточно тяжелая операция, которая актуальна только для 64-бит.

cmpxchg8b (double 32-bit cas) используют для реализации lock-free очередей, где обычной практикой является изменение за одну операцию двух 32-битных чисел — собственно того, что нужно изменить и тэга (версии) этого изменения, чтобы избежать, так называемой проблемы ABA, которая в свою очередь возможна и при использовании обычных мутексов ;)

Но, собственно, поскольку нормальный lock free возможен только при double CAS, при тенденции плавного перехода на 64-бит lock free становится относительно непопулярным методом, поскольку пока производители CPU не реализовали 128-бит CAS и не собираются этого делать в ближайших перспективах, в следствие того, что это считается тупиковой ветвью развития, которая все равно не решает ряда проблем. Некоторые все равно тупо держатся за само понятие lock free, которе бесспорно актуально в некоторых случаях, но явно не в тех, где это реализуется через sleep() — ведь основная цель lock free также и sleep/wait free — чтобы не было переключения контекстов потоков и т.п. :)

А еще применительно к смежной области хорошо бы изучить memory barriers и все, что связано cache line size применительно к SMP — и быстродействием, которое будет так заметненько прихрамывать на подобной реализации ;)

Если опыта в подобных делах не очень много, то для обычной работы, чтобы не ловить глюки, которые проявляются далеко не всегда, лучше использовать стандартные мутексы и кондишны :)

P.S. Извините за краткость — если об этом написать более подробно, получится материал на несколько глав большой и толстой книги. Курите доки — там все есть.
>Представьте себе, что, если вы пытаетесь лочить свой, основанный на атомарных операциях (да их, кстати, так наывают) примитив, спинлоком из того же потока, когда он уже этим же потоком залочен, то получите дедлок :)
И правильно получу. Иначе этот мьютекс будет называться рекурсивным и должен будет содержать ещё и счётчик. ;)
Спасибо за назидательный тон, но статья прежде всего о выражении одних примитивов синхронизации другими, в частности синхронными очередями. :)
>поскольку пока производители CPU не реализовали 128-бит CAS
Странно, а cmpxchg16b это что?

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

Описали бы что ли, что за ОС, какая задача стояла, почему решили на базе очереди все делать, почему она была единственным доступным примитивом, что за архитектура такая? А то смотрится как выдранный из контекста кусок кода без комментариев.
Я старался максимально абстрактно. Просто очереди или их расширение до потоков — альтернативный метод синхронизации, через который можно выразить также и классические примитивы.

>почему решили на базе очереди все делать, почему она была единственным доступным примитивом,
Потому что это действительно единственный примитив синхронизации доступный процессу :)

Если честно, изложение статьи мне не совсем понравилось, но такие темы нужно поощрять.
А вообще, для тех кому интересна эта многопоточная проблематика очень советую почитать что-нибуть про lock-free containers.
Мне однажды доводилось самому писать свой lock-free список используя только CAS2, очень интересное упражнение, всем рекомендую.
К сожалению сейчас становится всё меньше программистов, которые понимают как работает и для чего используется Memory Barrier…
Скажите что именно не понравилось, я постараюсь поправить. :) Lock-free становится популярной темой в связи с увеличением количества процессоров.
Что можно улучшить:
Вот вы говорите, что возникла задача написать свои примитивы на основе очереди, в реальности же и сама очередь всегда построена на примитивах более низкого уровня (CAS etc), про что вы потом вспоминаете и кстати довольно доступным для новичка образом объясняете. А вот утверждение что «всё — очереди» слегка неверно.
Я бы просто начал с конкретной задачки из жизни и рассказал на каких примитивах всё это строится и как работает. Знать базовые принципы всегда важнее, т.е. на мой взгляд в вашей статье ценно именно упоминание об этих примитивах, а не об очереди.
Далее, мне кажется что если уж вы взялись приводить примеры кода, то нужно это сделать более законченым, чтобы видно было что к чему. А то как-то всё фрагментами…
В общем, совершенно очевидно что вы устали и/или провели слишком много времени с компутером :)
Если бы я ещё про мембар написал, вообще бы никто ничего не понял :)))
Да всё нормально! Главное начать :)
Главное сначала самому разобраться, чтобы не нужно было не понимать, чего вы не поняли :)

Но направление в принципе верное — дерзайте. По крайней мере это лучше, чем у некоторых, которые для реализации очередей используют IOCP под виндой :)

И еще — использовать интринсики компайлера для доступа к подобным вещам местами оправдано, но бывает, что они не всегда делают то, что нужно.
Каждый день имею дело с примитивами синхронизации, но статья настолько абстрактна и не формализована, материал не разложен по полкам, что после прочтения — в голове каша.
Есть такая штука, как Hoare's CSP. На базе CSP в операционках Plan9 и Inferno реализована очень простая система синхронизации нитей. Благодаря ей, многопоточное программирование перестаёт быть традиционным кошмаром проблем синхронизации и начинает доставлять удовольствие, как и положено программированию. :)

Например в Limbo (основной язык программирования в OS Inferno) единственный способ взаимодействия между нитями это каналы: один процесс может попытаться отправить любую структуру данных в канал (при этом он заблокируется если никто не пытается принимать данные из этого канала), другой процесс может попытаться принять данные из канала (при этом он тоже заблокируется, если никто не пытается отправлять данные в канал). Разумеется, передача данных через канал — операция атомарная. Это всё. (Ну, на самом деле недавно добавили ещё одну фичу — буферизованные каналы: в такой канал можно отправить данные n раз (n == размер буфера) не блокируясь при отправке даже если никто не считывает данные из канала.)

Фактически, каналы в Limbo и Ваши очереди, которые по условию задачи есть изначально — очень схожи. Подумайте, может не стоит усложнять систему плодя кучу «стандартных» методов синхронизации, а лучше вместо этого разрабатывать архитектуру приложения иначе, в стиле CSP?
Ещё есть stackless python, который также использует каналы и тасклеты и который я очень люблю :)

Дело в том что большая часть кода действительно написана на очередях, так как это единственный способ взаимодействия с другими процессами. И мы не пишем «стандартные» методы к которым все привыкли. Я хотел написать о представлении «стандартного» IPC очередями, просто как задачку для пытливого ума, поэтому и старался абстрагироваться от языков. И никто в итоге не понял :)))

У канала есть существенное ограничение: наличие по крайней мере 2 endpoint'а.
Это вредная абстрактная задачка. Лучше взять абстрактную задачку изменения сложной архитектуры какого-нить приложения, использующего все эти семафоры, мьютексы и блокировки на простую архитектуру использующую CSP. Я вот что-то подобное планирую написать на хабр, как руки дойдут. Вообще, со сложностью современного софта надо активно бороться, и не путём введения новых уровней сложности, новых слоёв дырявых абстракций, etc. — как это принято сейчас делать.

А здравые ограничения нужны, чтобы не переусложнять без нужды. В том же Inferno нет неблокирующего I/O. Такое вот ограничение. Немеряно упрощает жизнь, чес-слово! :)
Нет блокирующего IO может быть?
Нет, как раз только блокирующее I/O и есть. Нити очень лёгкие, поэтому I/O делается по такому принципу: для чтения fd запускается одна нить (она в цикле читает fd в блокирующем режиме и считанные данные отправляет в другую нить через канал), для параллельной записи в тот же fd запускается другая нить (получает в цикле данные из канала от другой нити и пишет в fd в блокирующем режиме). Мультиплексировать fd (select/poll/epoll), кстати, тоже нельзя, мультиплексирование есть только для каналов.
Only those users with full accounts are able to leave comments. Log in, please.

Please pay attention