Сегодня мы с вами поговорим, закончим то, что с вами начинали в прошлый раз. Мы не договорились с вами об очереди Майкла Скотта. Сейчас мы ее немножко, так сказать, пройдем, да, и по лог-фри алгоритмам вы можно считать, что вы будете такими уже полупрофессиональными разработчиками, значит, и вторая лабораторная работа вам уже просто так. Семечки щелкать будете. После этого у нас сегодня такая, ну...
тема немножко за спойлеру кто работал с россию никто знает что это проверка арси you вот хорошо что вы знаете сегодня что-то новое я думаю что значит как идея она вам понравится но не что ж очередь макрос код the lock free очередь макрос код а и так это очередь обыкновенная это означает что вы имеете Значит, FIFO, чистый FIFO, то есть First In, First Out, и это именно очередь. Метода 2, NQ, DQ. И очередь Майкла Скотта устроена так, что вы имеете более одной точки входа в ваше приложение, это означает, что вы потенциально можете совершенно параллельно, то есть прямо физически параллельно добавлять элементы и удалять элементы из очереди. Как устроена очередь? Очередь устроена несложно.
Всегда есть в очереди один элемент, Sentinel. Он существует независимо от того, полна очередь или пуста. И есть 2 ссылки. Head и Tail.
Head, соответственно, указатель, ссылка на голову. Tail, ссылка на хвост. Сам элемент состоит из двух частей.
Первая, непосредственно, сами данные. Если они серенькие, то данных нет. Это как раз-таки вот такой псевдоэлемент. И вторая часть, это ссылка на следующий элемент.
Ссылка сейчас такая перечеркнутая, означает, что null. Когда мы... добавляем что-то в очередь у нас должен быть лог free алгоритм давайте подумаем как бы мы это делали то есть вот что мы должны сделать в первую очередь чтобы добавить в очередь новый элемент создать правильно абсолютно правильно значит я беру и допустим у меня есть уже один элемент уже есть один элемент до в очереди желтенький уже есть я хочу добавить новый элемент я его создаю все создал вот у меня созданный новый элемент каким-то потоком вот такие такие вот тараканы в виде микросхем это потоки которые хотят добавить и удалить элементы все создал дальше вот есть предложение перевесить указатель на хвост на новый элемент вот представьте что допустим мы перевесили к сам указатель ссылку последнего элемента на наш новый что у нас получилось у нас получилось что хвост ссылается на новый элемент и допустим наш поток заснул на миллион лет значит другой поток который захочет добавить что должен будет сделать но скорее всего тоже хвост взять и перекинуть на свой элемент означает что тот поток который добавлял перед этим когда проснется не очень понятно как он дальше в структуру данных свой элемент строит раз у нас уже хвост будет ссылаться на следующий.
Так он же или перекинул, или не перекинул. Зачем ему понимать? Он перекинул или не перекинул, верно.
Но, вот смотрите, задача потока какая? Добавить элемент в очередь. То есть после вызова метода enqueue мы должны гарантировать, что элемент в этой очереди появился и он доступен другим потокам для того, чтобы они могли его взять.
Если я сейчас перекинул tail на новый элемент, то... и за стопорю, допустим, поток, который добавляет, то как у меня будет добавлять следующий поток? Тоже будет перекидывать tail?
Или нет? Ну, скорее всего, потому что алгоритм, видимо, тоже будет перекидывать tail. У меня получится, возможно, сотни элементов, которые хотели бы добавиться, но получается, что tail будет только на последнем, и что будут делать те, которые проснутся? можно вопрос у нас у нас очередь реализована на списке или на массиве поскольку у меня есть ссылка да вот с одного элемента на другой то тут это такая списочная структура данных а к мы добавляем добавляем в т.л.
забираем из хода но мы добавляем в конец очереди забираем с головы до в итоге есть предположение что нужно как-то одновременно у предыдущего установить next да и перекинуть tail но как у нас делает только одно перекидывание да но верно утверждение что действительно мне нужно взять и сделать некоторые касс на элементе который до который значит был на лом да вот у меня было так была такая ситуация я беру и ввожу свой элемент вот в эту структуру данных Он хотя бы у меня теперь связан, то есть я знаю, что у меня последний элемент, если я буду идти с головы, это мой новый элемент. Но по большому счету мне надо еще, конечно, хвост пофиксить, то есть нужно еще и действительно хвост перевесить. А если вот в текущий момент придет какой-нибудь поток?
Вот, хорошо. Допустим, действительно придет еще один поток. Первый поток заснул, приходит второй поток. И ему тоже нужно добавить элемент.
А мы не можем, если придет другой поток, просто посмотреть на хвост, если у хвоста есть что-то следующее, пойти в это следующее? Мы можем так сделать, почти что куда-то в следующий элемент, если у хвоста есть последователи. Но так мы, скажем так, несколько понизим производительность потенциальной работы со структурой данных, потому что потенциально у меня может быть у этого элемента получаться такой вот большой-большой, если первый поток надолго заснул, да?
то все остальные будут ждать, по большому счету, я буду добавлять элементы в конец, а не очень понятно и постоянно именно ходить по всей структуре данных для того, чтобы найти последний элемент. Зачем я тогда делал tail? Я как раз таки делал его, чтобы быстро прям к нему обращаться.
Вот помните, мы, так сказать, говорили о том, что вот... в параллельном программировании, но иногда в жизни тоже. Мы особенно в wait-free алгоритмах наблюдаем некоторые явления, когда все-таки какие-то потоки иногда делают то, что им не свойственно, или делают что-то для системы в целом.
Вот вы сейчас как новый поток, который пришел и хочет добавить элемент, предыдущий поток его не успел, допустим, добавить, остановился вот на том слайде, который сейчас у меня есть. Я вижу... что точно ситуация немножко неконсистентная, потому что я иду по тейлу, вижу последний элемент и вижу, что у последнего элемента ссылка следующая не на ал, а на какой-то новый элемент. Это я вот сейчас вижу, да? Потому что я ее уже подменил.
Можно, наверное, переставить ссылку. Я аж вижу, что что-то не так, давайте я это исправлю. Значит, действительно, просто... А тоже подкассу надо переставлять. Да, конечно.
тот поток который будет добавлять узел если он успеет он сделает 2 касс как сейчас показано на слайде то есть он взят тоже кассам возьмет и перекинет с желтого элемента на фиолетовый фиолетовый сиреневый сиреневый население вот если бы другой поток раньше пришел и захотел добавить другой поток это бы сделал а первого потока на самом деле без разницы когда он проснется он сделает он попытается пофиксить хвост у него не получится потому что каст не пройдет но это будет означать что прошел он у кого-то другого то есть тот и другой уже помог ему пофиксить хвост понятно если по поднимите руки кому понятно хорошо все спасибо значит хорошо А если есть только один поток, предположим, и он как бы не доставил, мы должны это увидеть, если будем читать? То есть какая у нас тут договоренность? Предположим, пишет только один поток, он сделал первый касс и уснул.
И пришел поток читать, и он дочитал до самого конца, до тейла, и видит, что там есть next. Вот он должен увидеть это? Или может ли он не увидеть и считает себя это нормальным?
Это вы уже говорите как раз-таки о ситуации, когда мы хотим реализовать метод получения из очереди. Нет, я просто начал думать, мы рассчитываем, что другой поток придет, если что, и доделает. Да, но в данном случае, если другой поток не придет и не доделает, это означает, что не придет никакой поток, добавляющий в очередь.
То есть придут только потоки, которые будут брать из очереди. А потоки, которые будут брать из очереди, им хвост безразличен. Им важна голова. Значит, голова, мы будем брать голову, да, вот таким образом.
То есть если мы хотим взять из очереди элемент, мы просто берем, смотрим на голову, перекидываем ссылку через первый элемент, и мой прошлый такой вот искусственный элемент отправляется в мусор. А из элемента, который был вот здесь вот желтеньким, он становится сереньким, то есть мы из него забираем данные, да. И, значит, получается, что мы получили вот эти вот новые данные в наш поток, который захотел взять.
данные с начала очереди. Если вот здесь хвост был бы не пофикшен, а вот сюда бы ссылался, это бы не помешало этому потоку взять данные. Более того, значит, даже если он будет не пофикшен следующим потоком, да, то все равно поток, у который забирает элементы, тоже это не помешает забрать данные.
Но поток, который забирает данные, тоже может проявить солидарность и... Если что, пофиксить хвост, если видит, что хвосты отпали. Таким образом, мы гарантируем в этой очереди, что всегда хвост отстает не более чем на один элемент от реального хвоста.
Потому что если кто-то видит, что хвост не пофикшен, он его фиксит. Ну и, возможно, только одна ситуация, когда действительно вот есть один поток, он подзаснул и хвост не пофикшен. Понятен ответ?
Понятно. А можем чуть-чуть конкретизировать, как чтение происходит? Мы в нашей структуре берем по ссылке head и смотрим следующий элемент после head. То есть мы берем и смотрим вот эту вот ссылку и делаем CAS с head на вот этот элемент. Один CAS, естественно.
То есть вот таким образом. таким образом если мы прочли и каст не удался мы тогда мы пытаемся сделать еще раз прочесть и еще раз делать касс как обычно блок при вот видите ваш любимый значит atomic reference здесь есть 2 лабораторная работа томик reference и если посмотреть на код сейчас станет чуть более понятно вот это добавление в очередь то код добавления очередь он имеет следующую логику здесь очень подробные слайды Мы создаем новый элемент. То есть я практически буду читать, что на слайде. Значит, мы пытаемся добавить элемент, пока у нас не получится. Берем хвост и работаем с хвостом.
Если так получается, что следующий элемент у меня null у хвоста, вот как здесь, то есть все штатно, да, я перешел по хвосту, вижу желтый элемент, и следующий элемент у меня null. Тогда я предполагаю, что мне нужно сделать касс и заменить вот эту вот ссылку на свой новый элемент, который я создал. При этом надо понимать, что вполне возможная ситуация, когда я проверил next равно null. Типа да, равно null. И уже в следующей строке он уже не null, потому что другому потоку больше повезло и он уже добавил свой элемент.
Но ничего страшного, у меня просто этот касс не пройдет. Я просто еще раз зайду на этот круг. И важно то, что я... вот в этом круге не буду ходить по всей структуре данных я добавляю хвост и у меня сразу есть на него ссылка и беру с головы и у меня сразу есть на нее ссылка значит если у меня получилось добавить да тогда я пытаюсь сделать пофиксить свой хвост вот здесь ты у компаирен цен и важно что мне безразличен результат этой операции потому что если у меня получилось ну хорошо то есть я пофиксил свой хвост если у меня не получилось Это означает только то, что за меня кто-то его пофиксил.
И мне можно к этому не возвращаться. Если я заранее вижу, что хвост не пофикшен, вот заранее вижу, да, то я просто фиксию хвост чей-то, не свой. Понятно? Причем результат, опять же, не важен.
Да, тоже. Потому что могут 10 потоков попытаться одновременно пофиксить чей-то хвост. Это тоже как бы возможно.
значит когда толпа решает помочь дальше но поможет один если мы говорим про удаление элемента то есть про взятие его из очереди до декью то если очередь пуста мы кидаем исключение и тут также бесконечном цикле мы берем уже только теперь голову до head значит проверяем если у нас голова и хвост равны тогда понятно у нас список пуст на все слои с на один элемент а вот если не пуст тогда мы если видим что нужно пофиксить хвост фиксируем хвост на самом деле это не обязательно для потока который читает берет без этого тоже будет работать но почему бы не пофиксить вот если все в порядке тогда мы просто берем и делаем 1 касс на голове, соответственно, для того, чтобы взять новый элемент, так же, как на этом слайде с графическим отображением получения элементов. Идеологически нужно что понимать? Почему эта очередь показательна с точки зрения подхода к проектированию и разработке лог-фреструктур данных? Здесь мы видим такой базовый момент, как если мы что-то делаем больше, чем одним кассом, то мы обязательно должны заставить кого-то что-то сделать.
Почему? Если мы, допустим, не будем заставлять кого-то что-то сделать, это означает, что мы косвенно заставим другие потоки ждать, пока тот поток, который должен, что-то не сделает. Ну не сделает второй или третий касс, сколько у нас кассов будет при операции. А если мы заставляем ждать, это уже не лог-фри алгоритм.
То есть мы имеем на самом деле такую искусственную блокировку, только она не явная, не митус мы захватили, но логически все равно это блокировка, потому что поток чем-то своим занимается или ничем не занимается, и это влияет на другие потоки. И это уже не логфри. Мы не гарантируем прогресс системы, а гарантировать мы должны.
Поэтому если мы делаем больше одной атомарной операции, мы, к сожалению, должны все-таки заставить кого-то доделывать работу за других. Это даже получается хуже, чем лог, потому что другие потоки будут активно ожидать при этом. Да, если мы этого не будем делать, другие потоки действительно будут активно ожидать. Это такой спинлог фактически будет, такой скрытый спинлог.
Очередь Майкла Скотта сама по себе работает, как вы видите, достаточно понятно, и на ней основываются многие структуры данных на более высоком уровне. С точки зрения точек линеризации, о которых мы с вами немножко в прошлый раз говорили, то при добавлении, очевидно, точка линеризации у нас это как раз-таки тот касс, когда мы успешно добавили наш новый элемент в очередь. Потому что сразу после него, неважно, буду я фиксить хвост, не буду, засну я, не засну, этот элемент уже доступен для того, чтобы другие потоки его получали.
При удалении здесь... В успешном случае тоже это CAS, где мы забираем элемент непосредственно из очереди. Ну и в случае, если очередь пуста, это место, когда мы считаем хвост этой очереди. Но это так уже менее важно. Вот такая очередь Майкла Скотта.
То есть для добавления нам нужно два CAS, для удаления один CAS и обязательный так называемый helping потоков, взаимопомощь, для того, чтобы реализовать корректно блок фристиле все это дело. Вопросы по очереди. По очереди задавайте вопросы по очереди. Структура данных действительно базовая, достаточно понятная и несложная.
Все, поздравляю нас. С множеством так не получается легко. С этом?
С этим. Да. с этому вас так я тоже там видел статьях некоторые слова про версию но там все как-то выглядит значительно сложнее да с этом посложнее посложнее но на самом деле с точки зрения я бы сказал так Это не сложнее на порядок, это немножко посложнее. То есть ваша лабораторная работа, она не на порядок сложнее, вот в очереди Майкла Скотта, она вот там, ну, немного сложнее.
Но идеологически, поскольку у вас там действительно есть момент, скорее всего, который будет реализован больше, чем одной атомарной операции, наверное, значит, то вам... В некоторых случаях, которые, к сожалению, скорее всего, линчек не выгребет, или уже там выдаются вопросы некоторые, или мы зададим вам их на устной защите, возможна ситуация, когда у вас будет вот... Самое плохое, что у вас может быть на самом деле, это вот такой вот искусственный спинлок.
То есть вот как раз в вашей лабораторной работе второй есть много мест, где можно его получить. Где, значит, если придумать какие-нибудь там хитрые случаи, значит, действительно получится так, что если не будет хелпинга, то все будет плохо. Причем это на самом деле...
есть и реализации где без взаимопомощи потоков у вас все будет работать корректно но я не буду говорить какие все с лог free можно считать мы сейчас немножко так под закончили сейчас мы тоже будем рассматривать некоторые алгоритм синхронизации весьма по специфичный называется россию расшифровывается как read copy update Никак не нужно ассоциировать расшифровку, аббревиатуру с тем, что сейчас мы будем с вами рассматривать и пытаться как-то замэпить и логически догадаться, что должно произойти по этому названию. К сожалению, название во многом историческое. И даже в некоторых ресурсах некорректно написано суть этого дела. Задача какая? У вас есть структура данных.
Неважно какая. Совершенно неважно какая. древесная, списочная, значит, там какая-нибудь там массивы.
И вы знаете, что юзкейс работы с этой структурой данных такой, что у вас есть много читателей и достаточно мало писателей, ну, в пределе один. И вы можете жертвовать писателями, в том плане жертвовать производительностью писателей, в пользу производительности читателей. То есть вы хотели бы, чтобы ваши читатели максимально быстро получали данные, отрабатывали поиск в вашей структуре значит и все такое количество элементов читали при этом писатели могут работать с этой структурой но читатель все должно быть потоку безопасно при этом читатели и писатели должны работать параллельно при этом читатели не должны делать ничего для того, чтобы обеспечить потокобезопасность.
То есть у них нет права никакого захвата никаких примитивов синхронизации. Значит, предположим, что у вас есть, допустим, три потока, и вы работаете сейчас. Представьте, что вы разработчики ядра операционной системы. Вы кто-нибудь писал модуль ядра операционной системы?
Или само ядро, но само ядро, наверное, говорят, я вот модуль ядра операционной системы. Но все равно представьте себя, что вот вы именно находитесь не в юзерспейсе, а вот вы находитесь именно в керниевом спейсе, и вы реализуете вот такой примитив синхронизации, который мы сейчас с вами рассмотрим. И считаете, что, допустим, у вас есть два потока, три потока. Напомните, как вам удобнее, сверху вниз или снизу их номеровать. Сверху, хорошо, вот первый поток, второй поток, третий поток, это читатели, и есть один поток писателей, writer.
Значит, читатель как-то вот так читает, значит, вот эти вот, значит, всякие прямые, да, что они у меня обозначают? Точно так же, как и вот в линеаризации, когда мы рассматриваем с вами, считайте, что это работа с вашей структурой данных, некоторая логическая операция, у вас есть у вас структура данных. поиск, добавление, удаление, там, по счет количества и так далее.
Вот это некоторая операция, которая начинается, вы ищете элемент, и здесь вы заканчиваете эту операцию, вы его нашли, ну или не нашли. То есть это просто длительность этой операции. Вы, значит, читатель, в начале операции как бы вызывает, ну, как бы вызывает, ну, сейчас я скажу, значит, такую функцию, называется RCU Read Log.
И в конце, соответственно, вызывает RCU read unlock. Но вот в нашем случае сейчас вот обе этих функции имеют пустую реализацию. Там ничего нет, ни одной строчки. Это первое ограничение. Потоки, которые у нас читают, вот как-то так читают.
Считайте, что поскольку вы в Kernel Space, это потоки, которые пришли из юзерспейса, и им нужно что-то прочитать в структурах данных ядра. Выделить память, кто-то локатор, какое-нибудь дерево локации памяти читает. Ну а работа с одной структурой данных. И вот этот один вызов гарантируется, что когда ваш поток какой-то делает этот вызов, то считайте, что это какой-то поток занырнул в Kernel Space, здесь что-то сделал и вынырнул из Kernel Space.
Третий поток как-нибудь, ну в принципе не так важно, как-нибудь вот так вот. и тут пришел писатель структура данных считайте у меня сейчас такая списочная и в этой списочной структуре данных у меня обычно допустим вот пример данных на трех элементах да если я хочу удалить элемент как вы понимаете мы в ядре операционной системы вы разработчики ядра операционной системы значит что вы пишете вряд ли на java значит вы скорее всего пишите на языке программирования без сборщика мусора это си или плюсы на это и рассчитывать так вот опасная ситуация может возникнуть только тогда когда писатель не добавляет элементы вот в такую списочную структуру почему если мы добавили элемент но ничего страшного я добавил элемент я просто ссылку перекинул у меня новые потоки как которые читают мою структуру просто пойду по новому пути потому что я добавил элемент просто они будут его видеть ничего страшного не будет а вот если я удаляю какой-то элемент из очереди то допустим удаляю но и зоне из него не обязательно из очереди и структуру данных если я его хочу удалить то на самом деле у меня есть две фазы на английском языке они называются по-разному первая фаза это фаза перегидывания ссылки называется фаза remove то что фаза вот по-русски это Удалить и удалить, то есть одно слово у нас есть. А затем вторая фаза это физически освободить память, то есть удалить этот элемент, там, delete, именно с точки зрения освобождения памяти. Вторая фаза это, соответственно, delete. Иногда называется reclamation.
Рекламейшн, помните, safe memory reclamation на прошлом занятии было в АБА, да? такие механизмы безопасного освобождения памяти. Так вот, в любом случае у меня есть remove и delete.
По-русски удалить и удалить. И вот эту ссылку поменять я могу потокобезопасно. Это атомарная операция, касса какой-нибудь вызову, ничего страшного.
А вот удалить этот элемент физически на самом деле уже не так просто. Потому что я не могу гарантировать, что на этот элемент... никто из моих читателей сейчас не смотрит то что никто здесь не находится если я его удалю пока здесь кто-то находится из читателей то читатель там проснется или продолжить работу и все все метащин фолд память освобождена все плохо да я там делать поэтому значит писатель сначала делает вот это вот так называемая ремувал то есть перекидывает фактически ссылку да и делает это, ну, допустим, вот здесь. Вот в этот момент у меня закончился вот этот вот шаг удаления. Дальше, ну, шаг удаления, removal.
Дальше я должен на самом деле логически подождать, пока у меня не завершатся те потоки, вернее, не завершатся те операции, которые, которые я... пересекли вот это вот временную ось давайте у меня поскольку все три пересекли но чтобы было там чуть менее единообразно так я здесь все-таки так вот сделаю так вот то есть здесь потенциально первый и второй поток могли как-то идти по структуре данных и наткнуться на этот элемент все потоки которые будут начинать свои операции после вот этой зеленой линии они находятся безопасности они идут сначала структуры данных они уже сюда не дойдут потому что пройдут по новой ссылке понятно но мне нужно дождаться как минимум как минимум вот этого момента примерно да вот этот поток и как минимум вот этого момента для того чтобы вот здесь уже совершить непосредственно то, что называется рекламейшн. То есть сделать делит моего элемента. Почему мы его раньше все-таки не можем сделать? Потому что он может быть кем-то использован, мы кому-то можем закарабтить выполнение.
Да, потому что если вот этот поток и вот этот поток теоретически могут находиться или где-то вот здесь и уже прочитать вот этот указатель и начать сюда переходить. или какой-то поток мог здесь заснуть прямо на этом элементе и потом проснется а у элемента уже нет вот этот вот период который здесь указан он называется так называемый grace period который писатель должен как-то подождать если у нас будет такой механизм и вот здесь будет метод метод допустим синхрон айс rcu который вызывает только писатель да и вот он как-то реализован и вот писатель должен подождать пока остальные читатели не завершат вот эти свои работы при том что читатели напомню да не должны делать ничего то есть вот эта реализация методов полностью пустая мы находимся в ядре операционной системы и работаем со структурами данных ядра операционной системы Там действительно много таких структур данных, которые требуют очень частого чтения, но сильно более редкого изменения. Поэтому в пределе мы можем считать, что у меня вообще один писатель. Если у меня несколько потоков захотят поменять структуру данных, я на них отдельный мьютус поставлю, они все равно будут последовательно работать.
То есть это не страшно. Собственно, вопрос. Что я должен написать?
в реализации вот этого метода SynchronizeCircu для того, чтобы обеспечить вот такое вольготное существование читателей с возможным некоторым гноблением писателей, потому что я заставляю его ждать. Чтобы облегчить вам догадки и ответы на вопрос, сейчас мы будем считать, что вы будете предлагать свои реализации в некотором небольшом ограничении. Ограничение состоит в том, что ваше ядро операционной системы, считайте, что ваше ядро собрано. Вот я показываю, какое у меня сейчас ядро. 5, 14, 18, 100. И показываю сейчас некоторые флаги, с которыми оно собрано.
Конкретно сейчас считайте, значит, что ваше ядро собрано без флага, без вот этого флага, то, что он не установлен, то, что он равен false. То есть, config preempt. даже вот этот вот я бы сказал флаг не установлен конфиг print 0 в вашей версии ну надо сначала узнать что это за флаг то есть все таки не очень понятно что это значит этот флаг означает что вы запрещаете планировщику операционной системы, в ядре операционной системы, естественно, брать и прерывать любой системный вызов.
То есть, если системный вызов произошел, и какой-то поток спустился в Kerning Space, и начал в том числе вот эти операции, это означает, что обязательно он... закончит свой квант времени планирования после выхода из вот этой функции. То есть не может быть такого, что вы начали читать структуру данных, начали там что-то искать, и вас планировщик взял и снял, значит, с исполнения на ядре процессора, а потом когда-то поставил, когда, соответственно, появилось время. То есть считайте, что системные вызовы непрерываемы.
То есть вы сделали системный вызов, и вы уверены в том, что вас не снимут с ядра процессора. Понятно флаг, что значит? Хорошо. Вот, я помог. должны ли мы отследить когда все читатели закон системные вызовы но в принципе да главное нам на самом деле чтобы вот эти первые 2 читатель закончили 3 нам уже безразличен потому что но он не читал в тот момент когда мы перекидывали ссылку это означает что он точно когда начнет читать уже не сможет попасть на вот этот вот удаляем элемент а это вот давайте вот подумаем То есть вы предлагаете, чтобы посчитать, как потоки завершают свои операции.
Хорошо, как не узнать, что каждый поток завершил хотя бы одну операцию. Понятно, что я не спрашиваю прямо... Я, естественно, не ожидаю, что вы мне расскажете реализацию в терминах функции драйв-операционной системы. Нет, конечно, это не так. Я ожидаю от вас некоторого логического заключения, как бы вы сделали вот эту функцию на словах, но при этом все-таки на уровне абстракции чуть-чуть ниже, чем дождаться, пока каждый из потоков завершит хотя бы одну операцию.
Но это можно сделать многими вариантами. Каким из вариантов вы бы хотели это сделать, если так? То есть приведу пример. Что можно было бы сделать?
Допустим, вы же в ядре операционной системы, вы же можете все, вы видите все. Вы можете действительно взять, посмотреть на все потоки, которые есть сейчас в операционной системе, во всех процессах. И посмотреть. вызывают ли они сейчас конкретно системные вызовы, связанные с вашей структурой данных.
Это вы можете сделать. Вы можете проанализировать стэк каждого потока. Это все в вашей власти. Но это будет, конечно, жутко непроизводительно, потому что потоков может быть тысяча.
И пока вы будете смотреть, что кто-то, значит, ну, то есть это будет просто очень долго. Но это теоретически возможно. Это один из возможных вариантов. Я так.
он не до проработан специально да я его не полностью рассказываю вот а ваши какие мысли вот и помните да что я ограничение какое мы вели сейчас а теоретически можем а тамар на получить список тех потоков которые на момент вызова но вот этого моменты проверки находятся в ядре А там марно мы... То есть мы можем как-то узнать, что какие-то потоки уже в этом квадратике находятся? Вот эти квадратики, конкретно сейчас, и то, что мы сейчас делаем, мы работаем с какой-то одной из сотен структур данных ядра операционной системы.
Мы можем действительно узнать, какие потоки находятся сейчас в Kernel Space. Но они не обязательно будут работать с вот этой структурой данных. Мы можем узнать, какие потоки работают с этой структурой данных, но тогда нам нужно будет через сложный интерфейс понимать, какой код они вызывают. Причем на уровне того, какой системный вызов они вызвали.
Это возможно. Просто я думал, что если у нас есть список таких потоков, мы можем, воспользовавшись подсказкой про выключенную опцию, можно их попробовать прервать. А вы никак не должны влиять на читателей.
Они работают, работают. Все. Можно? Сейчас, секундочку. Вот сейчас есть предложение завести счетчик.
Если мы будем заводить счетчик, значит, вот эти потоки должны что-то сделать вот в этой функции. Они там ничего не должны делать. Никакого инкремента. Даже вот, даже такой операции. В чате, ой, не в чате, в зуме.
Да, можно еще раз про вот этот флажок? У нас планировщик, он работает на уровне потоков? Планировщик всегда работает на уровне потоков, да, и в данном случае у вас просто есть гарантия, что если какая-то функция чтения вашей структуры данных началась, то она обязательно закончится в один квант времени планирования этого потока. То есть не будет...
Да. Я немножко не понимаю, у нас как бы физически тогда может быть такая картинка, что вот один читает и другой читает, если у нас должно закончиться в один квант времени. А вот у меня прям эта картинка, вот один читает и другой читает. Вот у этого потока квант времени может быть вот такой вот, да?
У этого потока квант времени вот такой вот. И у нас одновременно идут кванты времени. Да, они же выделяются на физические ядра независимо условно. Вы планируете потоки на все ядра вашей многоядерной системы. Поэтому они, конечно, работают физически параллельно, и кванты времени у них могут не пересекаться.
должны ли мы отслеживать этот вызов этих функций это вообще идея конечно хорошая значит вот но я вот сюда думаю зря я их пишу не зря с самого начала считайте что их вообще нету значит этих функций то есть не просто у них пустая реализация да но и вот вот пока что даже их не существует а если мы на момент проверки вот grace период при вызове синхрониз мы повысим приоритет своего потока и будем считать, что если он встал на выполнение, значит все остальное оттуда. То есть каким-то образом дождаться и понять, что заставить другие потоки сняться с исполнения, так как у нас выключена опция, мы сразу поймем, что значит они завершили все, что они делали, и мы можем дальше делать рекламейшн. У вас интересная мысль, значит это...
вытеснить остальные потоки, сделать так, чтобы вы встали на их место. Попытаться, да. Но вы можете занять только одно ядро. Более того, вы вызываете эту функцию SynchronizeRCU, и вы уже вызываете ее на каком-то ядре, который вам уже дали. То есть вы оттуда и так уже всех вытеснили.
Вытеснить остальных потоков, остальные потоки вернее. То есть как вы предлагаете остальные потоки вытеснить? 8 раз вызвать синхронайзер CU и сказать, что 8 ядер занять параллельно?
Нам нужен семафор по количеству ядер в отдельных потоках запустить, когда он там накопится, мы будем знать, что точно все вытеснилось. Но он как бы установится, и после этого они сразу... уйдут, чтобы дальше читать или читали.
Ну, смотрите, на самом деле у вас очень правильное направление мысли сейчас. Абсолютно правильное, да? Я немножко подскажу.
Значит, вот в этой функции будет всего две строчки. Первая строчка будет состоять из цикла. Понятно, что псевдоход, типа, по каждому из... Вот по каждому чему. по каждому ядру да не потоку а по каждому ядру то есть их там 48 16 ну сколько их вот у вас есть в операционной системе сейчас именно по каждому вычислитель нему ядру вы же ядро операционной системы вы знаете сколько физических ядер у вас есть правильно вы же сами собственно их и распределяете потоки по ядра вы же ядро и вот второй строчкой что вы будете делать на каждом ядре Вы почти уже сказали на самом деле правильно.
Что вам достаточно сделать на каждом ядре? Хоть что-нибудь. Правильно, ничего. То есть на самом деле вам достаточно просто, чтобы вас туда переключили. И можно там ничего не делать, сразу уходить.
Это будет означать, что на этом ядре точно предыдущий поток завершил свой системный вызов. Потому что есть гарантия, что у вас ядро собрано с конфигом, с флагом, что вот одна линия и один системный вызов. То есть вы просто проходитесь по всем ядрам, там 2, 4, 1, и пытаетесь на них действительно залезть.
Так что в некотором роде вытеснение оно работает, только здесь вы их не то чтобы вытесняете, а вы просите поставить себя в очередь на исполнение на этом ядре планировщика операционной системы. И когда вы проходите по каждому ядру, то все это означает, что действительно вы гарантированно после вот этой вот синей черты. Может быть вы сильно после, но точно не до. Таким образом вы делаете так, что никакой читатель в... потокобезопасной структуре данных с возможностью добавления и удаления параллельного ничего не делает для обеспечения этой потокобезопасности.
Zero overhead для читателя. Никакого лока, ничего и никакого касса. Код без примитива синхронизации. Почувствовали, значит, мощь RCU?
Хорошо. Поднимите руки, кому понятно, значит, что это сейчас. Хорошо, хорошо, хорошо.
Молодцы, опустили руки. Значит... Какую ситуацию мы все-таки не обрабатываем данными двумя строчками кода?
В тех же ограничениях, которые мы сейчас работаем, да, но вот очевидно, что мы не обрабатываем ситуацию, значит, вот там, без того ограничения, которое я сейчас там вел, я скажу, как она обрабатывается. Но сейчас вот даже с учетом того ограничения, какую еще ситуацию, реальную ситуацию, для которой написан код, в ядре операционной системы, еще дополнительный, но все-таки мы здесь пока не учитываем. Но читатель может что-то странное сделать и никогда не завершится. То есть как-то заблокировать ядро полностью на себе.
Не знаю, правда, как. Но с этим мы ничего не можем сделать ни при каких обстоятельствах. На самом деле обрабатывается в ядре операционной системы, но обрабатывается специальным механизмом детекции дедлоков.
То есть когда ваш процесс, любой процесс, любой поток любого процесса слишком долго сидит в системном вызове, во-первых, это означает ошибку внутри ядра операционной системы, потому что никакой системный вызов не должен позволять, если понятно, он не блокирующий, долго в себе сидеть. И ядро мониторит в себе такие ситуации, там есть специальный механизм, и оно вам тогда честно признается, что извините, как бы у меня... Тут дедлог, меня лучше перезагрузить или обратитесь в поддержку разработчикам ядра. С этим мы ни в каком случае ничего не можем сделать. А вот то, с чем все-таки в случае отсутствия ошибок в ядре операционной системы мы можем все-таки что-то сделать.
То есть мы сейчас говорим о том, что то, что сейчас у нас написано, вот концептуально, что оно как бы не работает в каком-то случае. Да, и это случай обрабатывается во всех ваших ядрах. Пока мы шли по ядрам, то те потоки, после которых мы встали на ядры, гарантированно все-таки закончили чтение.
Там уже ничего плохого случиться не могло. Они начнут читать с начала структуры данных, следующее свое чтение, вот это вот. Все будет хорошо.
То есть логической ошибки, логической ошибки здесь мы никакой сейчас не совершили. Ошибка чисто техническая. Мы не обрабатываем одну техническую ситуацию.
Нельзя сказать, что вы часто с ней встречаетесь, но она существует в мире. Ну, два кристалла, может, или два процессора. Может быть, хоть чуть...
Ну, здесь мы по любому количеству процессоров проходимся, да, поскольку для операционной системы уровень абстракции процессоров, он как бы существует, да, но здесь мы по логическим ядрам идем, да, для всех процессоров. Но, действительно, в этих двух строчках, как вы понимаете, ошибка в этих двух строчках технической, да, вот, тут не так много... написано чтобы то есть вряд ли ошибка в форе но скорее всего не не сопротивить этот код с компилятором все в порядке будет у вас кстати говоря вот вот сейчас было от части правильное направление мысли с точки зрения ошибки Ну, может быть, есть.
Кэши не когерентное отрывание. С кэшами считаем, что мы здесь хорошие замечания в плане когерентности кэши и всего такого. В этом коде действительно учитываются всякие барьеры памяти, модели памяти.
Считаем, что они учитываются все корректно. Возможно, у какого-то конкретного процессора просто физически нет такой операции, что он ничего не делает, что он не умеет ничего не делать, например. вот такая вот какой-то год мы же должны ему на исполнении какую-то операцию команду скормить может такой команды нет это такой философский вопрос вы должны сделать так чтобы планировщик вас поставил на ядро то что вы сразу скажете что вам нечего делать это уже значит такое дело техники у процессора действительно может не быть операции ничего не делать хотя она Ну, в некотором роде есть, потому что вот вы же включаете компьютер, да, у вас процессор, загрузка процессора не стопроцентная, да, вот он же что-то-то делает, значит, вот в это время, но у него же частота-то не плавает, есть, да, механизмы подстройки частоты процессора в зависимости от его нагрузки, они вот там в ноутбуках часто очень у вас применяются, да, или в некоторых серверных решениях, чтобы меньше энергии тратилось, но в общем случае у вас вот это вот свободное время.
процессор же действительно ничего не делает с точки зрения полезной операции поэтому процессора есть вида такая штука вам здесь достаточно просто даже не то что ничего не делать а просто попросить планировщика то есть фактически себя же с точки зрения ядра операционной системы следующем поставить себя ну как я сказал то что вы скажете что вам сразу нечего делать это уже считать что вы здесь сразу там елт вызываете передачу управления другому потоку, потому что вам нечего делать. А там не могут быть проблемы, что вот это вызывается на каком-то ядре, и он проходит по себе же? Проходится по себе же, по себе же. В принципе, я понял вас, что мы здесь написали по любому ядру, и одно из этих ядер, это то, на котором мы сейчас исполняемся, естественно, здесь можно сделать исключение для этого ядра, но даже если мы не делаем, мы просто еще раз на своем же ядре тоже ничего не сделаем, это будет немножко неоптимально, но не ошибочно, скажем так.
Ну что ж, пришло время, видимо... Пришло время немножко раскрыть карты. Ну что ж, уже очевидная такая подсказка. Значит, как вы понимаете, она тоже в конфиге ядра операционной системы. Значит, и если ваше ядро собрано...
с поддержкой замены процессора на горячую или добавления еще десятка процессоров на горячую без выключения вашего компьютера или ноутбука, то эта ситуация не обработается этим кодом, потому что пока мы идем по ядрам, их количество может поменяться. И эта ситуация реально обрабатывается в ядре операционной системы, и вот код этой обработки из ядра операционной системы. Сейчас конкретно вот в этих строчках, которые вы видите, указан код, который без вот этого if-and-def, без config hotplug CPU. Hotplug подключение на горячую CPU, понятно, да, центральный процессор.
Когда этот флаг… То есть прям реально пустые скобочки? Да, это реально пустые скобочки, потому что в случае, если я компилирую ядро без поддержки этой функциональности, у меня должна быть функция, но которая… ничего не делает. Ничего не надо делать в этом случае.
А если все-таки у меня ядро скомпилировано с поддержкой такой функциональности, то вот этот код выше, не надо осознавать, что он делает. Он обрабатывает, это код, причем RCU. Это код, потому что вот видите, RCU, нижнее подчеркивание, все как мы пришли в этот момент.
Этот код, который реально обрабатывает ситуацию, значит, сначала начало вытаскивания процессора, потом окончание вытаскивания процессора, ну и наоборот. такого двухэтапного введения нового процессора в строй вашей операционной системы. Вот, наверное, вы не часто на горячую заменяли процессоры в ваших материнских платах, и не надо этого делать, они на это не рассчитаны.
Значит, если у вас, конечно, дома не специализированный процессор, не специализированное такое серверное решение. Возможно, кто-то из вас видел или знает о специализированных серверах подобного рода, иногда их называют еще... ну их несколько там видов картинку я сейчас просто покажу какой-нибудь какую-нибудь вот такую допустим вот blade сервера где у вас можно на горячую заменять вот такие вот платы значит на которых в том числе прямо процессор общего назначения и это делается на горячую для увеличения или уменьшения производительности замены вышедших из строя элементов когда мы не можем допустить чтобы вообще эта машина перестала работать то есть у нас нет возможности ее перезагрузить и выключить да значит у них обычно как видите там два резервные блоки питания да ну такие мощные железы и вот такие были сервера с и реально просто еще процессору туда прям добавляете значит и операционка сразу их подхватывает и повышает свою производительность И это заложено в ядре операционной системы.
В том числе в механизме синхронизации, который мы сейчас с вами прошли. Винда умеет работать на таких серверах. Реализовано ли это с помощью именно, ну скажем так, то есть тот же самый код там написан или нет, тут черт его знает, конечно, да, но винда тоже может работать на подобных решениях.
Правда, редко на самом деле. применяют, потому что, скажем так, понятно, как отрабатывает на этом деле Linux, но бывают проблемы с пиндовыми решениями. Все-таки это не самая частая ситуация, которая отлаживается обычно.
Ну и всякие такие методы, вот RCU, Cleanup, DeadCPU, значит, да, вот они действительно есть для операционной системы. Конкретно здесь это, видите, такая вот kernel, структура данных RCU. tree.c в ядре операционной системы существует более 107 структур данных не видов структур данных не как бы 107 разных видов деревьев а именно 107 разных по назначению структур данных 130 вот которые применяют именно технику синхронизации rc у который мы с вами сейчас рассмотрели вот такую идеологию потому что действительно для ядра операционной системы очень важно производительность читателей часто часто до И во многом производительность современных операционных систем, именно такая, как она есть, то есть достаточно, скажем так, для наших нужд, именно из-за подобного подхода ко многим структурам данных в ядре операционной системы.
А если вот эту опцию, которая запрещает прерывать читателей, выключить, наоборот, включить, там возможно реализация RCU или это уже... Возможно, безусловно. Как работает это дело, если мы разрешаем внутри этот системный вызов прерывать?
Если мы его разрешаем прерывать, у нас теряется инвариант, что если мы прошлись по всем ядрам, то обязательно закончилась операция. Инвариант потеряли, нехорошо. Но здесь элегантное решение просто берется и добавляется... Вот здесь было как раз предложение добавить счетчик, просто добавляется счетчик.
Добавляется счетчик так называемой эпохи структуры данных. Это называется GP, Grace Period. Вот у меня сейчас, я специально не заканчиваю расшалку экрана.
Вот это реализация RCU с применением как раз-таки Grace Period в общем случае. Идеологически, мы сейчас более подробно это рассмотрим просто на другом примере. Идеологически, вы можете считать, что у вас есть...
всего одна эпоха, то есть один счетчик на всю структуру данных, который инкрементирует только писатель. Только писатель. А читатели, когда начинают читать, просто копируют себе этот счетчик, а в конце инкрементируют у себя этот счетчик, только у себя.
И писатель просто ждет, пока все читатели не перейдут как бы в следующую эпоху. Он проходит по счетчиком всех читателей то есть проходит не по ядрам до физическим а по счетчиком всех читателей это накладывает ограничение то что читатели сначала должны зарегистрироваться в структуре данных что типа вот я читатель я буду вообще с этой структуры данных работать есть такой overhead но ядре все равно получается достаточно быстро и вот джипе нам grace period number как раз таки это и есть вот этот счетчик и механизм синхронизации в общем случае относится к классу эпох based synchronization алгоритмов. Эпох based означает, что они основаны на каких-то эпохах, которые синхронизируются между читателями и писателями.
Это не единственный алгоритм, который основан на эпох based, основывается на этой идеологии, но один из таких наиболее применяемых. Вот, значит, RCU readlock, кстати говоря, вот, Мы сейчас заворачиваемся с вами в такой код операционной системы, ядра операционной системы, где очень часто можно встретить приблизительно вот такие фразы, как сейчас выделено у меня на слайде. Причем, значит, там сверху еще страничка комментария, а вот и снизу, соответственно, то есть не надо сейчас читать дальше реально, это не принесет вам счастья. Но много кода многопоточного в ядре. снабжено подобным началом комментариев значит то есть комментарий специально разделяется на то что можно осознать значит для того чтобы один раз прочитать код а все остальное нужно читать тем кто условно хочет от код реально менять но и понимать что действительно что он действительно может еще повлиять помните да ошибку которая год было значит с барьерами значит вот отчасти она обусловлена некоторые такой вот сложностью так сказать в принципе кода который вы видите.
Причем, видите, всякие барьеры памяти, acquire, rcu, log, acquire, вы уже знаете, что это за слова такие, acquire, release, semantics, все такое. И это тоже все, естественно, здесь используется. Более того, даже вот инкрементирование, значит, вот это вот grace period number предваряется, как видите, уже вы знаете даже вот эту функцию, SMP, write memory barrier. То есть тоже предваряется явным вызовом барьера памяти, но понятно в ядре операционной системы.
Комментариев, кстати говоря, даже внутри кода подобного, он действительно нетривиальный. Как видите, иногда даже больше, чем самого кода, что часто считается не очень хорошим тонным программированием. Код должен быть самодокументированным, естественно, не нужно писать обычные комментарии в промышленном коде. Но в данном случае действительно... Тут не то чтобы каждая строчка требует размышлений, но без комментариев было бы, конечно, совсем грустно.
При том, что все имена методов и переменных, они реально названы по-человечески. То есть, видите, там RCU, for each node, but first. Понятно, что делает метод, но зачем он это делает, непонятно без комментариев. Ну ладно. Это мы с вами посмотрели.
так грейс период и такой кернил space rc сейчас я так во первых спрошу значит если вопросы по кернил space rc и сейчас мы если нет перейдем еще к юзер space rc и вот это вот грейс период мы еще там разберем если по нему вдруг есть вопросы сейчас еще мы догоним это дело по концепции rc you принципе и по реализации и в кернил space почему она называется ирси и расширяется как там вид копии апдейт до классическое понимание значит этой техники заключается в том что вы имеете некоторую структуру данных и работаете следующим образом вот у вас есть там структура данных какая-то ты вы ее читаете вот вы читаете делайте ее копию копий до делаете ее копию с этой копией делаете изменения у себя локально допустим удаляете элемент и делаете апдейт апдейт всей структуры данных прямо вот раз был один указатель считаю ссылающиеся на эту структуру данных и вы должны подменить этот указатель на вашу новую структуру данных но уже измененную и к сам естественно если не получилось еще раз читаете копируете меняете еще такое это Тоже как бы lock-free, но это вот lock-free, который мы не ожидаем, как я напомню, от вас в лабораторной работе. То есть не нужно копировать всю структуру данных. Это будет работать, но это работает недостаточно производительно, как меню.
В общем случае, RCU работает так, как я с вами вот сейчас здесь разъяснял. Видите, здесь нет никакого ни read, ну хорошо, read, наверное, есть, но никакого копии здесь точно нет. То есть в общем случае так получилось, что этот примитив синхронизации использовался для подобных структур данных, которые имели... Мы же сюда тоже можем применить RCU, к такой технике работать, но это не обязательно. Лучше не так думать, лучше просто разделять читателей и писателей и не заставлять постоянно делать копирование всей структуры данных.
то есть не то чтобы это как-то там просто рандомное название это задание такое можно применять россию и так как вот я сейчас рассказал да но это недостаточно сказать общий случай еще образа хорошо теперь посмотрим на юзер на тот же самое все you только как бы мы его реализовывали в юзер спейсе то есть не не в ядре операционной системы сейчас меняем личину да теперь вы не разработчики ядра операционной системы теперь вы профессиональные разработчики лог free алгоритмов и механизмов сейф memory рекламейшн вот слайды которые вы сейчас видите это слайды максима хижинского значит разработчиков библиотека библиотеки липси дес значит вот это слайды с конференции плюсы россия 2015 года ими воспользуемся максим один из самых квалифицированных разработчиков там блоков и алгоритмов и значит наверное он в питере как раз сейчас живет работает так что не дал окрасу поменял работу и по-прежнему на конференциях иногда выступает, сейчас уже поменьше, но тем не менее. То есть если на какой-нибудь конференции вот фамилию Хижинского, значит, увидите, знайте, что там будет что-то такое жесткое, параллельное, значит, производительное и многопоточное. Так, ну, значит, здесь вот на этом слайде на самом деле указано то, что мы совершенно безразличны к тому, что потоки делают добавление, да, insert, это не важно, потому что у нас в нашей структуре данных, здесь, допустим, на примере мэпа, Если у нас писатели добавляют, читатели не упадут ни на чем, потому что ничего не удаляется.
Они просто пойдут по новым ссылкам. Опасно тогда, когда у нас идет удаление. И в этом случае как раз таки видите, вот здесь такая идеологическая картинка. Мы находимся сначала в первой эпохе. Писатель во время удаления меняет эпоху всей структуры данных.
И вот этот вот метод там RCU-Sync ждет, пока все читатели не перейдут во вторую эпоху. Картинка очень похожа на то, что мы сейчас с вами рассматривали, только на примере юзерспейса. Все то же самое.
И теперь непосредственно реализация. Вот как это все реализовано. Сразу скажу, что некоторые вещи сейчас я попрошу вообще не учитывать. Но вы понимаете почему. Так, не понял.
А, понял. Первое. Во-первых, Global CTL.
Control, да, это как раз-таки есть глобальная эпоха структуры данных. Обычный атомик, целое число, просто счетчик. На самом деле, вот этот вот, так сказать, счетчик, мы, конечно, можем его инкрементировать, и в ядре действительно он прямо инкрементируется, честно. Здесь конкретно в UserSpace версию, вот...
Используется счетчик из одного бита. Почему? Потому что на самом деле нам не важно, сколько раз поменялась эпоха.
Нам важно только то, что она поменялась. А то, что она поменялась, ну и поэтому нам достаточно менять ее с нолика на единичку, ждать пока, соответственно, поменяется эпоха у других. И наоборот, потом с единички на нолик тоже ждать, пока поменяется эпоха у других.
Нам не важно, сколько раз поменялась эпоха. Для понимания можно... думать, что мы просто инкрементируем счетчик. Это абсолютно общий случай. В ядре так реализовано.
Здесь небольшая оптимизация. Сделано это здесь только для того, чтобы внутри еще добавить вот этот вот nested counter, счетчик вложенности. Здесь реализован RCU с возможностью вложенного захвата. То есть рекурсивный RCU.
Вот сразу говорю, на это даже сейчас не смотреть. Вот не существует этого счетчика вложенности сейчас. Так вот, есть Global CTE, глобальная эпоха, и есть Mutex. Причем этот Mutex только для писателей.
Только для писателей. То есть, возможно, теоретически, что разные потоки захотят писать, но мы их все сразу сажаем на этот Mutex. Редкий случай, когда мы в одной и той же структуре данных часть потоков сажаем на примитив синхронизации, а часть не сажаем. Для каждого читателя у нас организована вот такая структура данных из...
двух полей. Первое поле это локальный, локальная эпоха. Тот же самый Atomic, только без Global, просто CTL. И второй это указатель на следующую такую же структуру данных, только другого потока.
Чтобы можно было потоку писателю пройтись по всему списку вот этих вот структур данных, по всем потокам читателям, начиная с любого из них. Когда какой-то поток хочет работать со структурой данных, обычно он долгое время это делает. И он сначала регистрируется, ему выдается такая вот RCU ThreadData, и поток начинает работать со структурой данных в терминах чтения и записи.
Что делает читатель? Читатель делает следующее. Кстати, помните TLS?
Вы уже знаете, что это такое. ThreadLocalStorage. Это именно то, что вы знаете. Что делает читатель?
Читатель при входе в секцию чтения, это аналог вызова метода RCU ReadLog, который у меня был здесь, только здесь он называется RCU Enter. Мы входим в RCU. Берет свою локальную структуру данных и здесь ничего не происходит. Вот этих строчек нету. И последней строчки тоже нету.
Значит, это учет как раз-таки вложенности вызовов. Сейчас не нужно об этом думать. И выполняется только вот та строка, которую я сейчас подсвечиваю. Это как раз-таки получение глобальной эпохи и сохранение ее в локальную эпоху.
То есть просто... присваивание локальной эпохи значение из глобальной эпохи и все понятно хорошо когда поток читатель закончил свою работу он точно также берет свои вот это вот локальную запись и меняет эпоху делает фич сап это нолик на иди шканичка на 0 то есть просто меняет свою локальную эпоху это важно локальную эпоху не глобальную все этот все что делает читатель то есть у читателя на самом деле достаточно тоже быстрая такая работа, он фактически делает лот из Atomic Store в Atomic и один раз атомарная операция FetchSupp. То есть фактически там две ассамблерные инструкции условно на начало чтения, одна ассамблерная инструкция на конец чтения.
И отмечу, что эти ассамблерные инструкции сильно легче, чем кассы. Ну что ж, следующее. Это то, что делает писатель. Писатель берет и захватывает примитив синхронизации, потому что только один писатель может писать в один момент времени, и ждет, считайте пока, что здесь один раз написано, ждет один раз, пока все читатели, вот реализация этой функции, мы меняем эпоху, напоминаю, только писатель меняет глобальную эпоху.
писатель меняет глобальную эпоху вот этим методом и ждет пока все потоки не выйдут из этой эпохи то есть просто проходит по всем потоком читателям и пока значит поток не вышел поток поток еще находится в этой эпохе значит он там ничего не делает этот поток писать просто ждет я вот напоминаю просто отдает процессорное время другим потоком собственно логика вся Не обязательно сейчас прямо вгрызаться и добито понимать эту логику. Главное понять принцип того, как это вообще работает с точки зрения Epoch-based Synchronization. Все-таки, если коротко, почему дважды? Вот.
Непонятно. Хорошо, хорошо. Значит, почему дважды? Смотрите.
Значит, дважды вот почему. Поскольку мы здесь с экономией, и у нас всего один, однобитовая, как ее называют-то? однобитовая эпоха, то у нас, возможно, такая ситуация неприятная. Вот тут есть специальный слайд, который, если зададут вопрос.
Значит, возможна ситуация вот какая. Смотрите, у нас есть код для читателей, и у нас есть вот эта вот строчка. Так вот, вот эта вот строчка на самом деле, это не атомарная операция.
Это две разные ассамбленные инструкции, где мы сначала на самом деле получаем значение из глобального счетчика. Ну и сохраняем его в какую-то такую псевдовременную переменную, там в регистр. А потом только сохраняем это значение.
То есть это все равно две ассамблевые инструкции, между которыми может пройти много времени. И с учетом этого может так получиться, что поток, который читатель, вот слева читатель, он получает вот эту переменную. Вот здесь tmp специально, значит, как бы искусственно введена. То, что он получил ее здесь, а присвоил свои локальные эпохи только вот на этой строке. И так получилось, что между этими особенными инструкциями вызвал RCU SYNC поток, нажал один раз flip and wait, flip and wait вызвал это ожидание.
Все, дождался, пока все потоки перейдут в другую эпоху. И так получилось, что получается, что... пока первый поток работает, работает.
Второй поток. Еще раз вызвал RCU-Sync, еще раз сделал Flip and Wait, дождался перехода снова в другую эпоху, и тут он дождался, потому что только вот здесь, между этими двумя RCU-Sync'ами произошло присваивание реальной глобальной эпохи, локальной эпохи. И в этом случае мы удалим узел тогда, когда все еще первый поток. может ходить по нашей структуре данных я осознаю что сейчас объяснение было сложным и вряд ли она понятно и вы его прочувствовали это нормально значит тут с первого раза нереально значит это В общем, принципиальный ответ следующий. Из-за того, что операция копирования глобальной эпохи в локальную фактически не атомарна, а это чтение и запись, то вот между этим чтением и записью может влезть поток писатель, уже подумав, что наш читатель работает и находится там в нужной эпохе.
И из-за этого, из-за вот этих там ноликов, единичек и обратного переключения, возможно некорректное удаление. Поэтому мы... перезакладываем ся и делаем вот этот флип-энд-вейд два раза значит на самом деле большинстве случаев ожидая больше чем надо ну и бог с ним мы заранее говорили что писатели у нас в не в приоритете они могут ждать и дольше чем значит может быть было бы логично вот такое такое вот объяснение а мы игры а разве мы гарантированно починим проблему до Мы гарантированно подчиним эту проблему.
На самом деле это боевой код, который сейчас на слайде. Это действительно код, который используется в библиотеке. Отсюда выкинуты только пространство имен и все такое, чтобы не захламлять слайд. Но именно такой код вы как раз-таки увидите в реализации. Более того, у вас на самом деле есть возможность использовать не просто библиотечные решения какие-то, а вы конечно...
Пробовали? Скорее всего, вы знаете, что есть пакет во всех современных дистрибутивах Linux, ну, давно достаточно на самом деле, который позволяет вам использовать примитивную сегментацию RCU, в том числе в юзерспейсе, без написания вашего прикладного кода, потому что, ну, это, как видите, не самая простая вещь. Вот он прямо так и называется, юзерспейс RCU.
Значит, если посмотреть, то теперь, после сегодняшнего занятия... вы можете осознать описание этого пакета. И, значит, вот оно, описание.
Значит, и видите, что, соответственно, есть стандартные решения RCU, Read, Copy, Update, Implementation, User Space, которые уже используются, ну, потенциально могут быть использованы в прикладном коде, в том числе и в User Space, уже как библиотечные решения. Примерно прочитали, да? Вот он.
Действительно такой пакет есть. Что получается? Получается, что мы сегодня с вами рассмотрели такой не самый тривиальный примитив синхронизации RCU. До этого было, видите, мы разгонялись, простенький Michael Scott, в принципе там более-менее понятно, что происходит. А в RCU мы с вами пролезли немножко через ядро операционной системы, посмотрели на страшный код самого RCU в одной из структур данных, в реальном дереве, которое вот в ядре, значит, реализовано.
Как я сказал, более сотни структур данных. используют RCU в современном мире операционной системы, это очень активно используемый там примитив синхронизации. И вообще вот эта вот идеология эпох-бэй синхронизейшн, она хорошо работает, когда у вас есть действительно юзкейс десятков читателей, которые должны работать с почти зеро вархедом.
Ну а один инкремент и одно сложение, это как вы понимаете, одно присваивание, там все равно чтение, это копейки. То есть это ну... Вы на журнализации больше теряете в разы. В этом плане есть, конечно, за что бороться, но более эффективных способов на самом деле сейчас особо не придумано для такого юсткейса конкретно.
Сложно ли это реализовывать или поддерживать? В принципе, не так уж сложно. Другое дело, что в таком прикладном коде имеет смысл всего-то использовать, где вы… действительно вот уперлись производительность ну и вам вот но недостаточно стандартного контейнера который вот потокобезопасный даже там лукфришный какой-нибудь да вам нужно еще быстрее и вы знаете что у вас конкретно писатели могут там подождать или их очень мало читали действительно много и вот это знание да но на самом деле его нельзя ниоткуда получить да только вы знаете как инженеры вот вашей примерной области что у вас действительно такая ситуация все равно структуры данных в Большей части стандартных библиотек, естественно, особенно те, которые входят в стандартный язык программирования, конечно, рассчитывают на какие-то более общие юзкейсы, которые покрывают более стандартные ситуации. Но если у вас будет вот такая ситуация в вашей жизни, теперь вы знаете, во всяком случае, что есть такой подход, вы можете его и просмотреть, и реализовать, и попробовать.
Вопросы? Корректно будет сказать, что в такой структуре, если мы использовали такой подход, у нас wait-free на чтение? Да.
Да. То есть у нас даже более, получается, сильные гарантии или нет? У нас действительно, вот здесь такой прямо интересный случай, когда у нас правда wait-free на чтение, то есть мы гарантированно читаем за один проход, да, всегда, значит, без всяких циклов.
Но вот тот случай, я вначале говорил, это вот как раз здесь можно сейчас прочувствовать, да, что структура данных не обязательно вся lock-free или wait-free, а может быть wait-free методы. вот чтение причем это значимый метод мы ради этого собственно и старались вот метод там записи или изменения структуры данных мутации он не то что не выйти он не лог не ни разу до его нас митокс там при этом и вот настолько разные до получаются то есть abstraction free то есть не лог free и не вреда и вайки и вот они соответствуют в одной структуре данных да это действительно возможно и это так еще вопросы Еще был вопрос. Если я захочу для какой-то цели в своем прикладном коде на языке, например, на Java, к примеру, реализовать такое, насколько это может иметь смысл и какие у меня могут быть инструменты, кроме того, чтобы вызывать через GNI или какую-то еще штуку именно системный C-шный код?
В случае Java, конечно... GNI такой не самый приятный механизм в реализации вообще в принципе, значит, да, и это уже скорее, когда уж вынуждены мы что-то вот плюсовое такое из Java напрямую использовать, не можем это растянуть на сервисе, надо делать. Мне кажется, что особого смысла прям заиспользовать C-шный код поначалу, во всяком случае, смысла не имеет.
Вот реализация RCU, даже если вы будете ее писать с нуля на Java, это два небольших класса. Ну там, это не то, чтобы сложно Все абстракции есть на Java для того, чтобы это делать, и Atomic, и ThreadLocalStorage, все есть. Производительность, конечно, будет пониже, чем на плюсах, но все для этого есть, никуда там залезать в кишки не нужно. И это несложно, действительно. То есть, посмотрев на код даже в libcds, вот RCU по тем слайдам, которые я показывал, вполне можно это вот прям один в один на Java перенести.
То есть проблем быть не должно. Я бы все-таки перенес, не вызывая. Код там несложный.
он сложный к бы логически да но он несложный вот это не не миллионы строк кода несколько сотен насколько можно это сделать на java можно как видите на можно реально вот так по факту получается что не часто конечно я реально не знаю вот приложение которое использовало версию на java боевого хотя я сейчас не сильно искал но могу сказать что вот эта техника используется тогда когда действительно нужно прям гарантированная производительность гарантированная а Как мы знаем, есть небольшое, так сказать, противоречие. Гарантированную производительность Java в принципе не может предоставить. То есть у вас всегда будет просадка на деоптимизацию и просадка небольшая на старт. Иногда бывает просадка в зависимости от сборщика мусора, что вы там используете на сборку.
Вот такие алгоритмы используются там, где действительно нам нужно гарантировать полностью константную производительность. Тут скорее просто... не из того, что невозможно это на Java сделать, а из-за того, что класс систем, где обычно нужны подобные подходы, он не соответствует классу систем, где обычно применяются языки со сборщиком мусора.