Speaker A
Всем привет. На прошлой лекции мы с вами познакомились с тем, как в операционных системах устроены потоки, и обнаружили одну очень важную проблему, а именно проблему синхронизации между потоками.
Лекция о синхронизации потоков: состояния гонки, атомарные операции std::atomic, критические секции и взаимные исключения в программировании.
Key Takeaways
- Общая память между потоками требует явной синхронизации, иначе результаты недетерминированы.
- Атомарные операции подходят для простых изменений одной переменной, но не для составных операций.
- Мьютексы защищают критические секции, а семафоры и условные переменные нужны для координации потоков.
What the video covers
- Потоки одного процесса работают с общей памятью, что создаёт риск состояния гонки (race condition).
- Три основные задачи параллельной работы: передача данных, взаимные исключения и координация выполнения (производитель-потребитель).
- Потоки обмениваются данными через общее адресное пространство, процессы — через IPC (каналы, сокеты, разделяемая память).
- Пример с инкрементом счётчика показывает потерю обновлений при неатомарной операции чтения-изменения-записи.
- Data race в C++ приводит к неопределённому поведению, компилятор может оптимизировать код без учёта гонок.
- std::atomic обеспечивает атомарность простых операций; на x86 атомарный инкремент соответствует инструкции ADD с префиксом lock.
- Атомарность отдельной операции не гарантирует согласованность последовательности операций — нужна критическая секция.
- Взаимные исключения (мьютексы) защищают критические секции от одновременного доступа нескольких потоков.
- Блокирующие ожидания требуют приостановки потока и последующего пробуждения; семафоры и условные переменные решают задачу производитель-потребитель.
- Блокировки чтения-записи создают риски голодания писателей или читателей и не гарантируют справедливости по стандарту C++.
Chapters
- 00:00Введение: задачи синхронизации потоков
- 06:00Состояние гонки и гонка данных
- 11:30Атомарные операции std::atomic
- 40:00Критические секции и взаимные исключения
- 48:00Программные алгоритмы блокировки и прерывания
- 52:30Блокирующие ожидания и семафоры
- 60:00Задача производитель-потребитель
- 81:40Блокировки чтения-записи и голодание
Full Transcript — Download SRT & Markdown
Speaker A
Потоки создаются в рамках одного процесса, и это позволяет коду, выполняющемуся в разных потоках, работать с общей памятью. И мы увидели, что может возникнуть состояние гонки, при котором один из потоков, обращающихся к общим данным, записывает эти данные, а другой поток либо пишет, либо читает. Это может привести к проблемам. И сегодняшняя лекция будет посвящена тому, как эти проблемы решаются и какие средства операционная система и стандартная библиотека вашего языка программирования предоставляет вам, чтобы обеспечить корректный доступ к общим данным.
Speaker A
При разработке, при параллельной работе потоков и процессов возникают три задачи. Значит, первая задача — это передача данных.
Speaker A
Например, если один процесс получает информацию из сети, а другой обрабатывает её, или же несколько потоков совместно работают с одной и той же очередью заданий. Вторая задача — это взаимные исключения.
Speaker A
Если несколько потоков изменяют общие данные, необходимо предотвратить конфликты, иначе они могут мешать друг другу и повреждать состояние программы.
Speaker A
Третья задача — это координация выполнения. Вот, давайте представим производителя и потребителя. Производитель, допустим, помещает данные в какую-нибудь очередь, а потребитель извлекает данные из этой очереди и как-то их обрабатывает. Потребитель не должен забирать элементы из пустой очереди. Он должен дождаться, пока там появятся данные от производителя. Потоки и процессы решают эти задачи немного по-разному. Потоки используют общее адресное пространство, и поэтому обмениваться данными им просто. Но из-за этого может возникнуть состояние гонки, или по-английски race condition.
Speaker A
У процессов адресное пространство изолировано, и для обмена информацией им нужны специальные механизмы межпроцессного взаимодействия, которые мы проходили. Например, это могут быть каналы, сокеты или разделяемая память.
Speaker A
Вот мы с вами сначала разберём синхронизацию на примере потоков, а уже на следующем занятии посмотрим, как те же самые идеи применяются к процессам.
Speaker A
Давайте посмотрим очень простую ситуацию. Есть у нас одна общая переменная, мы назовём её, допустим, counter. Изначальное её значение равно нулю. И два потока, поток А и поток Б, пытаются увеличить её на единицу.
Speaker A
Интуитивно ожидается, что результат будет равен двум, но это не обязательно. Так, значит, операция инкремента включает несколько действий. Надо прочитать значение из памяти, увеличить его, а потом записать обратно.
Speaker A
Представим, что у нас первый поток прочитал нолик. Затем второй поток тоже прочитал нолик. Оба они увеличили значение на единицу и после этого записали каждый свой результат. В итоге у нас в переменной counter после двух потоков окажется значение единица вместо двух.
Speaker A
То есть оба потока выполнили операцию инкремента, а результат — счётчик увеличился только один раз. Одно обновление оказалось потеряно. Такая проблема называется состоянием гонки. И особенно неприятно, что эта проблема не всегда возникает, а зависит она от порядка выполнения операций. Поскольку потоки в нашей программе работают независимо друг от друга, в каких-то запусках вы получите значение два, а в каких-то — значение единица. Более того, проблема может не проявляться на вашем компьютере, но проявляться на компьютере некоторых из ваших пользователей. Стоит также различать состояние гонки, то есть race condition, и гонку данных.
Speaker A
Data race. Data race — это более узкий термин, например, он используется в C++, в языке C и в других языках программирования. То есть когда несколько потоков обращаются к одной области памяти без необходимой синхронизации и хотя бы один из этих потоков выполняет запись, возникает гонка данных. Для обычных неатомарных переменных такая гонка приводит к неопределённому поведению. То есть говорить о том, как работает программа, уже бесполезно. И вот давайте посмотрим на похожий пример. У нас здесь есть два потока. Первый, э, 1 млрд раз увеличивает общий счётчик. Второй, соответственно, миллиард раз его уменьшает. Если бы мы считали, что каждая операция выполняется целиком и никакие изменения не теряются, то результат должен был бы быть равен нулю. Однако в зависимости от запуска мы можем получить вот такое странное число. То есть получается, что тот поток, который увеличивал счётчик, «победил» в 7,5 млн раз — то есть поглотил те изменения, которые были у второго потока.
Speaker A
Вот здесь классическая проблема состояния гонки. У нас есть переменная counter, и два потока без какой-либо синхронизации работают с этой переменной. Если компилятор обнаружит здесь гонку данных, он вправе оптимизировать код таким образом, исходя из того, что никаких гонок в программе нет. Поэтому нельзя гарантировать ни нулевой результат, ни какое-либо другое значение.
Speaker A
И даже если у вас вдруг программа каким-то чудом тысячу раз подряд напечатает нолик, вам может просто повезти. Это не означает, что она корректная.
Speaker A
Вы можете в Godbolt открыть эту ссылочку, несколько раз запустить и будете каждый раз получать разные результаты.
Speaker A
Один из способов решить эту проблему — использовать атомарные операции. В стандартной библиотеке C++ есть класс std::atomic. Это шаблонный класс, который позволяет сделать доступ к объекту атомарным. То есть такие операции, как инкремент и декремент, будут выполняться атомарным образом, и конкурирующие изменения не будут теряться. Даже если два потока одновременно выполнят операцию инкремента, в результате мы получим корректное итоговое значение, без потерянных обновлений.
Speaker A
На процессоре x86 атомарный инкремент превращается в обычную операцию ADD, которая берёт и прибавляет к значению в памяти, адрес которого передан в качестве аргумента функции, значение единицу. А атомарный инкремент соответствует той же самой команде, но с префиксом lock. Префикс lock обеспечивает необходимую аппаратную гарантию атомарности операций относительно других процессорных ядер.
Speaker A
То есть если несколько процессорных ядер работают с одной и той же областью памяти, префикс lock гарантирует, что мы не потеряем результаты.
Speaker A
Но надо понимать две вещи. Во-первых, std::atomic не обязательно реализуются одной инструкцией на любой архитектуре. Это зависит от типа переменной, от аппаратной платформы и от реализации стандартной библиотеки. А во-вторых, атомарность отдельной операции не означает атомарности произвольной последовательности операций. Представим программу, которая сначала проверяет баланс банковского счёта, затем списывает деньги и обновляет журнал транзакций. В этом случае одной атомарной операции будет недостаточно, и нужно защищать согласованность нескольких операций. Это приводит нас к понятию критической секции. Вы когда-нибудь слышали слово «критическая секция»?
Speaker A
Дело в том, что атомарные операции подходят для простых изменений отдельных переменных, но во многих случаях программа должна выполнить целую последовательность действий так, чтобы другой поток не вмешивался посередине.
Speaker A
Например, при работе с банковским счётом нужно проверить баланс, списать деньги и обновить информацию об операции. Если между этими действиями вмешается другой поток, данные могут оказаться несогласованными, и у вас либо появятся деньги из ниоткуда, либо пропадут в никуда.
Speaker A
Участок программы, который требует исключительного доступа к общему ресурсу, то есть только один из потоков имеет доступ к этому ресурсу, называется критической секцией. Чтобы защитить эту критическую секцию, используются взаимные исключения, или mutual exclusion по-английски.
Speaker A
Вот вы можете в годболте открыть эту ссылочку и несколько раз позапускать и будете каждый раз получать разные результаты.
Speaker A
Один из способов решить эту проблему - это использовать атомарные операции. В стандартной библиотеке C++ есть класс STD Atomic. Это шаблонный класс, который позволяет сделать доступ к объекту атомарным. То есть такие операции, как инкремент и декремент, будут выполняться атомарным образом. То есть конкурирующие
Speaker A
изменения не будут теряться. Даже если два потока одновременно будут выполнять операцию, один инкремент, другой инкремент, в результате мы получим так, ээ, в результате мы получим как бы нулевое изменение.
Speaker A
Э, на процессоре X86, э, атомарный инкремент превращается в обычную операцию AD, которая берёт и прибавляет к к [откашливается] значению в памяти, адрес которого передан в качестве аргумента функции значение единицу. А инкремент атомарный соответствует той же самой команде, но
Speaker A
перед которым есть префиix log. Префикслок обеспечивает необходимые аппаратная гарантия томарности операций относительно других процессорных ядер.
Speaker A
То есть, если несколько процессорных ядер работают вот с этой же областью памяти, э префиix log гарантирует, что мы не потеряем результаты.
Speaker A
Вот. Но надо понимать две вещи. Во-первых, STD АТОК не обязательно реализуются одной инструкцией на любой архитектуре. Это зависит от типа от типа переменной, какой здесь есть, от платформы, под которую вы, аппаратной платформы и реализации стандартной библиотеки.
Speaker A
А, во-вторых, атомарность отдельной операции не означает отомарности произвольной последовательности операций. Представим себе программу, которая снача сначала проверяет баланс банковского счёта, затем списывает деньги и обновляет журнал транзакции одной атомарной и обновляет журнал транзакций. Вот в этом случае одной атомарной операции вам
Speaker A
будет недостаточно и нужно защищать уже согласованность нескольких операций. Это нас приводит к такому понятию, как критическая секция. Вы когда-нибудь слышали слово критическая секция?
Speaker A
Вот. [откашливается] Дело в том, что атомарные операции подходят для простых изменений отдельных переменных, но во многих случаях программа должна выполнить целую последовательность действий так, чтобы другой поток не вмешивался посередине.
Speaker A
Например, при работе с банковским счётом нужно проверить баланс, списать деньги и обновить информацию об операции. Если между этими действиями какой-то другой поток вмешается, данные могут оказаться несогласованными, и у вас либо появятся деньги из ниоткуда, или пропадут в никуда. [откашливается]
Speaker A
Участок программы, которые требуют исключительного доступа к общему ресурсу, исключительного, то есть только один из потоков имеет доступ к этому ресурсу. Вот, называется критической секцией. Чтобы защитить эту критическую секцию, используются взаимные исключения или mutual exclusion по-английски. То есть один поток получает доступ к к
Speaker A
защищаемому ресурсу, а другие потоки, которым этот нужен ресурс, они ожидают, пока он не освободит доступ.
Speaker A
Вот в C++ для этого предусмотрен класс STD Mutex. В других языках есть подобные механизмы.
Speaker A
У Мютекса есть методы LCK и Unlock. Log - это, соответственно, захватить к если если был не захвачен, то вы сразу же его захватываете. Ну, точнее, ваш поток. А если какой-то другой поток раньше вас захватил этот, то ваш поток блокируется,
Speaker A
пока MКС не будет разблокирован и операционная система не решит вам этот отдать. Но и UNLC вызывать небезопасно.
Speaker A
А что, если между LOC и Unlock выбросится исключение, и выкса не разблокируете? Поэтому при работе с мютексами применяется идиома Ri, то есть используется стандартная обёртка STD loggard. В своём конструкторе он захватывает me utex, а в деструкторе освобождает. Поэтому даже если во время
Speaker A
работы функции update shared data у нас выбросится исключение, во время раскрутки стека вызовет деструктор Мьютекса, который, ой, некса, а деструктор переменной loggard, который этот разлочит. Ну или если мы обычным образом выйдем из этого блока, деструктор всё равно вызовется и
Speaker A
гарантированно разблокирует. Ээ, взаимные исключения относятся к участникам, которые используют один и тот же механизм блокировки для защиты одного ресурса.
Speaker A
Ээ, если какой-нибудь другой поток будет захватывать не этот, а какой-нибудь другой, то никакой как бы защиты не будет. То есть в критической секции у вас должен быть один и тот же, захватываемый разными потоками.
Speaker A
Ещё один, значит, важный вопрос. Операционная система не определяет автоматически, какие строки нашей программы образуют критическую секцию.
Speaker A
То есть для неё вот этого блока никакого не существует. То есть программист должен правильно организовать синхронизацию, используя представленные механизмы. Здесь это реализуется за счёт как раз того, что LOGA при входе при при своей инициализации захватывает к при разрушении освобождает.
Speaker A
Более подробно мы мьютексы позже рассмотрим. Давайте посмотрим, как что должно быть в программе, чтобы синхронизация была корректной. То есть нам недостаточно просто запретить одновременный вход в критическую секцию. У хорошего алгоритма синхронизации есть и другие важные свойства. Значит, первое свойство - это
Speaker A
Mutual Exclusion. Взаимное исключение. Два потока не должны одновременно выполнять критические секции, защищающие один ресурс.
Speaker A
Вот это основное требование безопасности. Второе - это возможность продвижения или прогресс. Если ресурс свободен и один или несколько потоков хотят в него войти, решение о следующем участнике не должно откладываться бесконечно из-за потоков, которые вообще не работают с этим
Speaker A
ресурсом. То есть те потоки, которые находятся вне критической секции, не должны помешать потокам, которые хотят войти, в эту критическую секцию зайти. Если это вдруг произойдёт, значит, ну, у нас программа зависнет.
Speaker A
Третье, это ограниченное ожидание. Bunded wting. Если поток запросил доступ, то другие участники не должны бесконечно его обгонять. То есть когда-нибудь ему должно всё равно повести. То есть эта вот проблема связана ещё называется проблемой голодания. То есть если какой-то из
Speaker A
потоков никак не может получить доступ к ресурсам, к ресурсу, все его другие потоки его его обгоняют. Это не очень хороший механизм синхронизации.
Speaker A
[откашливается] Также вы не должны строить решение о синхронизации на предположении, что один процессор работает быстрее другого или то, что планировщик всегда выбирает потоки в определённом порядке. То есть вы должны быть готовы к тому, что планировщик операционной системы как
Speaker A
угодно может переупорядочивать потоки, в любой момент пере передавать процессорное время от одного потока к другому.
Speaker A
Вы полагаться на всякие эти временные задержки не должны. [откашливается] Вот эти требования нам пригодятся дальше, когда мы будем рассматривать разные способы реализации взаимного исключения и увидим, что некоторые алгоритмы хорошо предотвращают состояние гонки, но плохо обеспечивают продвижение или тратят процессорное время на
Speaker A
ожидание. Есть [откашливается] два базовых подхода. Значит, первый базовый подход - это атомарные операции. Если нужно безопасно увеличить счётчик, создаём атомарную переменную. Э, и все операции над этой переменной выполняются как неделимые. То есть нельзя увидеть промежуточное состояние операции. Или мы
Speaker A
либо увидим состояние состояние этого объекта до операции, либо после. Второе - это взаимное исключения. Если требуется согласованно изменить несколько переменных или выполнить последовательность зависимых действий, то удобно защитить весь участок программы Мьютексом или каким-нибудь другим похожим примитивом синхронизации.
Speaker A
Вот. Но появляется вопрос, что происходит, когда поток хочет зайти в критическую секцию, а другой поток её уже занял?
Speaker A
Эриант первый. Можно постоянно проверять, освободился ли ресурс. Это называется активным ожиданием. То есть вы берёте и проверяете, свободно или не свободно. А можно приостановить выполнение этого потока и передать процессор другим задачам.
Speaker A
Мы разберём оба подхода и увидим, как атомарные инструкции, спинлоки, мютексы и механизмы операционной системы позволяют строить эффективную синхронизацию.
Speaker A
Давайте разберём, значит, взаимные исключения и безвейтинг. Мы разобрали, значит, что такое состояние гонки, критическая секция и взаимное исключения.
Speaker A
Теперь посмотрим, как взаимные исключения можно реализовать. Казалось бы, задача очень простая. Если один поток выполняет критическую секцию, остальные должны подождать.
Speaker A
Вот. Но как определить, что секция уже занята? И как гарантировать, что два потока не решат одновременно, будто ресурс освободился, и попробуют одновременно туда зайти.
Speaker A
Есть, значит, первый способ - это просто запретить прерывание, чтобы текущий поток не был вытеснен в неподходящий момент.
Speaker A
У процессора есть специальные инструкции, которые позволяют запретить реакцию на прерывание. Вот этот механизм действительно полезен, когда речь идёт о ядре операционной системы, и там действительно в определённые моменты приходится запрещать прерывание, но у этого есть серьёзное ограничение.
Speaker A
Второй подход - это согласовывать доступ к к ресурсу с помощью общих переменных. Мы рассмотрим несколько алгоритмов и увидим, что, казалось бы, вроде простая задача, а выглядит сложно.
Speaker A
Третий подход. Используют специальные атомарные инструкции у процессора, которые могут неделимо прочитать или изменить значение там переменной, отвечающей за блокировку.
Speaker A
Давайте начнём с одного из старейших способов защиты критических секций отключения, прерывания. Давайте представим с вами однопроцес однопроцессорную систему. То есть в каждый момент времени процессор выполняет только один из потоков, и в нужные моменты он переключается с одной задачи на другую.
Speaker A
Обычно операционная система может прервать его выполнение по сигналу таймера и передать процессор другому потоку.
Speaker A
Но что, если на время работы критической секции мы просто возьмём и запретим прерывание? Вот в X86 есть инструкция CLI. которая сбрасывает флаг разрешения прерывания в регистре флагов, а STI включает флаг реакции на прерывание. Соответственно, как можно сделать критическую секцию? Мы
Speaker A
запоминаем текущее состояние регистра флагов, выполняем инструкцию CLI, заходим в критическую секцию, выполняем полезные данные. Нас никто в этот момент прервать не может. После выхода из критической секции мы просто восстанавливаем состояние регистра флагов.
Speaker A
Но есть ограничения у такого способа. Отключение прерывания не запрещает все исключения. Есть маскируемые прерывания, [кашель] а есть ещё добровольная передача управления. То есть код внутри критической секции не должен блокироваться или вызывать планировщик.
Speaker A
Поэтому механизм запрета прерываний - это не универсальный способ, а специальный инструмент ядра операционной системы. Более того, операции запрета прерывания - это привилегированные операции, как правило. Ну вот на X86, например, это привилегированная операция. И в своей программе, которая в
Speaker A
пользовательском режиме выполняется, вы её выполнить не сможете. Вам вашу программу просто прибьют. Вот, казалось бы, мы нашли прекрасный способ, но он имеет свои ограничения. Первая проблема появилась с выходом многоядерных процессоров. В современной системе одновременно выполняются потоки на разных ядрах. И у каждого из этих ядер
Speaker A
есть свой набор регистров, включая регистр флагов. И если процессор номер ноль отключит прерывание, то это никак не останавливат не остановит процессор номер один. То есть представьте себе, что оба процессора работают с одной и той же областью памятью. Первый отключил
Speaker A
прерывание и приступил к обновлению данных, а второй тем временем продолжает выполнять свой поток и тоже изменяет те же самые данные. В итоге состояние гонки у нас никуда не исчезло. Второе - это безопасность.
Speaker A
Если мы пользовательской программе разрешим отключать прерывание, она может нарушить нарушить нормальную работу системы. Поэтому запрет прерываний - это слишком важная операция, чтобы позволять её пользователям.
Speaker A
Поэтому, когда ваша программа работает под управлением операционной системы в пользовательском режиме, вы не можете запрещать прерывания. Третья проблема - это отзывчивость.
Speaker A
Пока маскируемые прерывания отключены, процессор не может нормально обрабатывать соответствующие события от устройств и таймера, поэтому такой режим должен использоваться очень осторожно.
Speaker A
Однако отключение прерываний остаётся полезным инструментом внутри самой операционной системы, внутри её ядра. Вот, например, существует в в Линуксе там функция spinlock и QSA, который сочетает захват спинлока. Такой механизм синхронизации с отключением локальных прерываний и сохранением их предыдущего состояния.
Speaker A
Вот. Но для более общего механизма синхронизации потоков нужно другой подход выбрать. И давайте посмотрим программные способы решить проблему взаимной блокировки.
Speaker A
Давайте [откашливается] придумаем решение, которое сможет работать на нескольких процессорных ядрах. Самая очевидная идея завести общую переменную лог. То есть, если переменная равна единичке значит э ресурс занят. А если она равна нулю, значит ресурс свободен.
Speaker A
И вот мы хотим вот следующую блокировку сделать. То есть сперва организоваем цикл, в котором проверяем, не равна ли переменная нулю. Крутимся здесь. Пока она не равна нулю, значит какой-то другой другой поток её занял.
Speaker A
Потом мы берём и выставляем её в единичку, выполняем критическую секцию. После выхода из критической секции выставляем переменную в нолик.
Speaker A
Однако здесь есть ошибка, и вот она на в таблице показана. Первый поток прочитал значение переменной log равное нулю.
Speaker A
Второй поток тоже прочитал значение переменной log равное нулю. И оба они вышли из этого цикла. Поток b записал в переменную log единичку, но второй-то поток уже прошёл этот эту защиту и тоже записал туда единичку. В итоге у нас в критическую секцию зашли
Speaker A
два потока, хотя разрешено входить только одному. Всё, проблема не решена. А что, если проверить лок дважды?
Speaker A
На самом деле это не поможет, потому что другой поток всё равно может вмешаться после последней проверки.
Speaker A
Если вы что-нибудь такое напишите на C++ с использованием обычной переменной, это привёт приведёт к состоянию гонки и неопределённому поведению. Поэтому это вот псевдокод, он не работает. Никогда так не делайте.
Speaker A
Придумаем, давайте другой алгоритм, который не позволит двум потокам одновременно войти в критическую секцию. Но это не мы придумаем. Конечно же, придумали люди там в семидесятые-восьмидесятые годы. Одна из простейших идей - это строгое чередование.
Speaker A
То есть введём переменную turn. У нас здесь два потока, которые говорит о том, какому из потоков, какому из потоков разрешается войти в критическую секцию.
Speaker A
У нас есть два потока. У первого поток потока айдишник равен нулю, у второго единичка.
Speaker A
Вот. И мы здесь крутимся в этом цикле до тех пор, пока переменная чёрн, говорящая о том, кому можно зайти, не будет равна ой не будет равна айдишнику нашего потока.
Speaker A
Как только мы зашли, мы выполняем критическую секцию, а затем передаём ход другому. Ну, представим такую ситуацию. Поток А выполнил критическую секцию и передал ход потоку Б. А поток Б в это время занят какими-то долгими вычислениями, вообще не собирается работать с общим
Speaker A
ресурсом и, соответственно, туда не заходит. Тем временем поток А снова решил сюда зайти и и смотрит, хочет войти в критическую секцию, а не может, потому что он сам передал право перехода потоку Б.
Speaker A
Получается парадоксальная ситуация. Критическая секция свободна, но поток не может её занять. Это нарушает что? Требования прогресса или продвижения, которое мы рассматривали ранее. То есть поток не заинтересованный в критической секции, не должен мешать другим потокам. А здесь у нас он мешает. Понятно, почему
Speaker A
возникло? Поток А сказал, что сейчас очередь потока Б, а поток Б в эту очередь не заходит и переменную чёрн не меняет. А поток А из-за этого, из-за бездействия другого потока не может зайти.
Speaker A
[вздыхает] Вот. И вот у нас есть два алгоритма, которые не работают. И иногда бывает так, что мы можем два неработающих алгоритма, идеи двух неработающих алгоритмов объединить и получить один работающий алгоритм.
Speaker A
[откашливается] И в 1981 году Гэрри Птерсон предложил элегантное решение этой задачи для двух участников, для двух потоков. Значит, две идеи.
Speaker A
Первая - это флаги намерения, это wantн, да, два флага есть. А вторая, то есть, используя флаги намерения, поток сообщает, что хочет войти в критическую секцию. Для этого он свой элемент массива выставляет в true. [фыркает] А вторая переменная - это turn, которая
Speaker A
помогает разрешить конфликт, когда оба потока хотят войти одновременно. Рассмотрим функцию Enter. То есть поток хочет войти в критическую секцию. Каждый поток сообщает, что хочет войти в критическую секцию. Для этого он в свою переменную в свою переменную W записывает значение
Speaker A
true. Здесь я сейчас записал атомики. Почему? Потому что если тут не будет атомиков, то тогда это будет состояние гонки. Программа на C++ не будет иметь смысла, даже если она скомпилировалась и на X86 у вас заработала на каком-нибудь другом
Speaker A
э на другой процессорной архитектуре. Она так уже работать не будет. Ну, мы представим, перенесёмся мысленно в 1981 год, в котором архитектура была у компьютера более простая, и потоки действительно могли так вот в переменные записывать значения.
Speaker A
Итак, значит, мы записали в переменную W. Записываем true в свою переменную, а в переменную turn записываем, то есть разрешаем зайти туда другому потоку. То есть фактически поток уступает место другому потоку право первоочередного входа. После этого он проверяет два условия.
Speaker A
Во-первых, хочет ли другой поток зайти. Другой поток он вот переменную уворяет. И если другой поток хочет зайти и у него и сейчас очередь того потока, то мы ждём. Если же хотя бы любое из этих условий не выполняется, то есть если
Speaker A
сейчас наша очередь оказалась или другой поток не хочет зайти, то мы здесь не ожидаем. И получается после этого [откашливается] после этого мы зашли в критическую секцию.
Speaker A
Когда мы хотим выйти из критической секции, мы должны просто сбросить свой флаг э записать туда значение false. Это позволяет ожидающему потоку, который вот в этом цикле крутится, продолжить выполнение. Алгоритм удовлетворяет классическим требованиям взаимного исключения, продвижения и ограниченного ожидания при принятых предположениях,
Speaker A
что оба участника соблюдают протокол к соблюдают протокол. Вот критическая секция завершается. То есть между входом в критическую секцию и выходом из неё потоки там, ну, вечно не крутятся.
Speaker A
Ну и, соответственно, ожидающие потоки тоже продолжают получать процессорное время. Ээ оригинальный алгоритм рассматривался в модели последовательной согласованности памяти.
Speaker A
Что это означает? Это означает, что если мы какие-то записи в в каком-то порядке выполнили в разные переменные, все потоки увидят эти записи в этом же самом порядке.
Speaker A
Что ещё за странная фигня? Да. Ну, у нас могут быть две переменные. И ээ допустим вот есть переменная А и есть переменная B. И поток один записывает в переменную А единичку, а в переменную B он записал двойку. Вот. А второй поток,
Speaker A
ну, когда у нас модель согласованной памяти, второй поток, если знает, что делает первый поток, то он может быть уверен, что если он из переменной B прочитал двойку, то, значит, в переменную А действительно записалась единичка. И это работает, если у нас
Speaker A
последовательная модель, последовательная согласованность, последовательно согласованная модель памяти. Вот. Но бывают модели памяти такие, что если поток А записал в А единичку, а в B записал двойку, изначально там были нули в обоих переменных, то это не гарантирует, что для другого потока
Speaker A
эти записи произойдут в том же самом порядке. То есть второ для второго потока может выглядеть так, что переменная B модифицировалась раньше, чем переменная А. Ну вот так вот работают ядра параллельные. Это нужно для производительности.
Speaker A
[кашель] Поэтому вот если вы попробуете на обычных переменных написать на многоядерном процессоре, у вас это работать не будет. Поэтому здесь используются атомарные переменные.
Speaker A
И, в общем-то, алгоритм Питерсона был бы хорошим, если бы работал на многоядерных системах, современных процессорах. Он сейчас не работает.
Speaker A
Но он интересен с теоретической точки зрения. Он показывает, что задачу взаимного исключения можно решить без специальной инструкции захвата блокировки, то есть с помощью организованного обмена состояния между участниками, при условии, что модель памяти, ээ, ну, это позволяет сделать.
Speaker A
В реальных системах есть несколько проблем. Во-первых, классический алгоритм предназначен для двух потоков. Для большего количества потоков требуются другие более сложные решения.
Speaker A
У вас количество переменных будет расти. Во-вторых, алгоритм используют активное ожидание. Это означает, что если ресурс занят, вот поток, который хочет зайти в критическую секцию, будет постоянно опрашивать опрашивать опрашивать и тратить процессорное время не на полезную работу, а на ожидание. Ну и
Speaker A
в-третьих, современные процессоры и компиляторы не обязаны соблюдать тот порядок операций с с обычной памятью, которой нам кажется очевидным.
Speaker A
при чтении исходного кода. То есть процессор может изменить порядок выполнения и видимости операции над памятью, а компилятор переставить инструкции или хранить значения в регистрах.
Speaker A
Вы можете использовать тай, но valй вам всё равно не поможет. Поэтому прямая реализация алгоритма Питерсона с точки зрения C++ она некорректна.
Speaker A
Правильные способы решения требуют атомарных операций с соответствующими гарантиями порядка памяти. И давайте посмотрим, какую аппаратную поддержку предоставляют современные процессоры.
Speaker A
Вернёмся [откашливается] к самой простой идее. У нас есть переменная переменная log. У неё значение ноль означает свободная, единица занята. И мы знаем, что отдельная проверка и последующая за ней запись, то есть выполняющаяся как две разные операции, не обеспечивают взаимного исключения. То
Speaker A
есть между проверкой и записью в значении может какое-нибудь другое ядро вклинится. Вот. Но современные процессоры предоставляют инструкции, которые позволяют выполнить оба действия как одну атомарную операцию.
Speaker A
Такие инструкции относятся к категории read modify write операции, то есть операция, которая читает, модифицирует и записывает как единое целое.
Speaker A
Классический пример - это инструкция test and set. На её основе основан TSL log. Test and set log. Как работает инструкция TSL?
Speaker A
Она атомарно читает из переменной её значения и устанавливает блокировку. Ну и возвращает то значение, которое раньше было.
Speaker A
Вот, [вздыхает][тяжело вздыхает] допустим, как мы можем тогда log организовать? Мы в переменную можем с помощью команды TSL попытаться записать единицу и получить предыдущее значение. Если старое значение было нулём, значит, блокировка была свободнай, и мы успешно захватили эту блокировку. Если же старое значение
Speaker A
было единицей, значит блокировка уже кем-то занята, и мы можем крутиться. И свойство операции ТС - это то, что операция Томарна. Если два процессорных ядра одновременно попытаются захватить одну и ту же блокировку, то есть выполнить операцию ТС над одной и той же ячейкой
Speaker A
памяти, то они не смогут оба получить старое значение ноль, поскольку операции выполняются в согласованном атомарном порядке. То есть один из них увели увидит нолик как предыдущее значение, а другой увидит единицу. И, соответственно, тот, кто увидит единицу, поймёт, что он опоздал, и ему нужно
Speaker A
ждать, пока не увидит нолик. Есть ещё инструкция Exchange на X86, которая при обращении к памяти выполняет атомарный обмен.
Speaker A
Атомарный обмен - это у вас есть значение в памяти, и вы хотите записать туда новое значение, получить старое. Вот с помощью Exchange это можно сделать. Есть команда CMP Exchange, которая позволяет выполнить условный обмен, то есть сравнить значение с ожидаемым. И если
Speaker A
там получилось, то выполнить обмен. атомарные инструкции, они не обязательно всю прямо шину, по по которой данные из памяти в процессор ходят, не обязательно они обменивают. То есть современные процессоры обеспечивают атомарность через механизмы когрентности кшей. То есть и процессорные ядра
Speaker A
обмениваться друг с другом дополнительными служебными сигналами для того, чтобы синхронизировать свою кэш-память. Давайте посмотрим, как можно с помощью вот этой операции TSL выполнить просте создать простейший спинлок.
Speaker A
В стандартной библиотеке есть класс STD Atomic Flag. Это на это марный флаг, который идеально подходит для этой задачи. Он поддерживает две операции. Первая операция называется Test and set, то есть проверить значение и установить флаг в единицу. А вторая инструкция -
Speaker A
это кleр - это сбросить. Начнём. Ээ, мы хотим сделать спинлок, то есть это блокировка, в которой поток активно ожидает освобождения ресурса, то есть крутится в цикле, не отдаёт процессорное время кому-то другому.
Speaker A
Вот в методе Log операция Test and set атомарно устанавливает флаг в единицу и возвращает его предыдущее значение. Если раньше был флаг RSE, значит мы сумели захватить, наш поток сумел захватить.
Speaker A
То есть блокировка была свободна, и мы успешно установили её в true, и другой никто не сможет уже увидеть.
Speaker A
Если же операция возвращает true, то значит, что блокировка занята, цикл будет продолжаться, продолжаться, продолжаться.
Speaker A
Вот. То есть это и есть пинлок, то есть вместо перехода в состояние ожидания поток крутится как волчок на одной и той же на одном и том же атомарном флаге.
Speaker A
Для того, чтобы снять блокировку, необходимо просто вызвать метод clear. И тут ещё передаётся какая-то странная штука. STD Memory Order Acquire STD Memory Order Release.
Speaker A
Они нужны для того, чтобы согласовать доступ. правильно согласовать доступ к защищаемым ресурсам. Кстати, если вы ничего не передадите сюда, то у вас будет использоваться флаг, задающий последовательную согласованность памяти. То есть это более строгая штука. Но обычно, когда захватывают
Speaker A
блокировку, передают Memory Order Acquire в testet, а в Memory Order Release передают, точнее в в Clear передают memory order relase. Это нужно для того, чтобы, если вы внутри критической секции, то есть между вызовом log и UNLO выполнили какие-то операции модификации памяти,
Speaker A
необходимо, чтобы потоки, которые вдруг смогут туда зайти, то есть после вас в критическую секцию, увидели результаты, которые вы в память записали.
Speaker A
Почему они могут не увидеть? Потому что ядра не изменение, которое вы записали в память в одном ядре процессора, оно не мгновенно будет видно другим э ядрам. И вот memory order require, memory order list вот эту гарантию как раз обеспечивают. То есть
Speaker A
то, что было записано до записи с Memory Order Release, будет видно раньше, чем какой-то другой поток сможет с Memory Order Acquire вот эту переменную захватить. Соответственно, то, что внутри блокировки делалось, после выхода из блокировки другим потоком будет видно, когда они в
Speaker A
блокировку зайдут. Если вам пока непонятно, для чего это нужно, можете просто не передавать сюдарели. Будет использоваться самый строгий. А вообще у меня в лекции по параллельному программированию я про мери Order более подробно рассказываю.
Speaker A
Итак, мы реализовали простую блокировку, научились защищать критические секции. Этого достаточно. То есть, видите, тут 10 строчек. Ну, может быть, не 10, примерно 10 строчек. И уже мы сделали блокировку, которая в рамках одного процесса может защищать перемены. Но насколько она хороша?
Speaker A
[фыркает] Элае преимущество вот этого спинлока - это отсутствие необходимости блокировать поток через ядро операционной системы.
Speaker A
То есть системный вызов - это дорогая операция. Если критическая секция выполняется очень быстро, то есть внутри содержит буквально несколько, может быть, десятков примитивных операций, а или, может быть, несколько сотен инструкций. Действительно, иногда немного выгоднее немного подождать, покрутиться вот здесь на этой атомарной
Speaker A
переменной, чем обращаться к ядру и переключать контекст. Но если внутри такой критической секции будет выполняться длительная операция, ну, допустим, вы решили что-нибудь с диска прочитать, а диск у вас даже не SSD, а обычный.
Speaker A
И вот у вас на сколько-то там миллисекунд процессор, ну, будет занята блокировка и процессорное время вот тех потоков, которые пытаются туда войти, вот тратится на пустое ожидание.
Speaker A
Вот. То есть, если один поток захватил блокировку, а другой без остановки проверяет флаг, то второй поток может потратить огромное количество процессора на время. не выполнить никакой полезной работы.
Speaker A
Вот поэтому лучше использовать блокирующие ожидания. Э при блокирующем ожидании, если блокировка за Ну, если блокировка занята, то поток, которому не повезло, он засыпает, и процессорное время отдаётся тем, кто более удачливый. А ещё у спинлока, смотрите, какие есть недостатки.
Speaker A
Спинлок простой не гарантирует справедливого распределения доступа. То есть один поток может чисто вот из-за теории вероятности многократно захватывать блокировку, пока другой продолжает ждать.
Speaker A
Кроме того, когда несколько ядер процессора постоянно обращаются к одной атомарной переменной, то возникают дополнительные дополнительные расходы на обмен данными между их кэшами, между крышами ядер.
Speaker A
Вот. Особенно, значит, важно избегать длительных операций вводо-вывода под спинлоком. И что у нас, значит, есть?
Speaker A
Какие альтернативы? То есть мы начали с попытки защитить критическую секцию отключением прерываний. Этот метод может быть полезен внутри ядра, но не подходит для режима пользователя. Затем мы попробовали использовать общую переменную log.
Speaker A
Оказалось, что между проверкой её значения и захватом блокировки возникает состояние гонки. И мы разные алгоритмы рассмотрели. Строгое чередование вроде бы позволяет другому потоку не не входить, но страдает от чего? От там от голодания, да? То есть и в итоге там был алгоритм
Speaker A
Питерсона, который работал, работал, работал, пока не перестал на потому что на современных процессорах не работает.
Speaker A
Соответственно, поняли же мы, что для нормальной многозадачности, ой, точнее, нормальной синхронизации нам нужны атомарные операции, чтобы разные ядро процессора могли друг с другом договариваться в тот момент, когда они с одной общей памятью работают.
Speaker A
И мы увидели, что при использовании спинлоков, если поток не может захватить блокировку, он постоянно проверяет её и расходует в процессорное время. Если критическая секция короткая - это норм.
Speaker A
Если она длинная, это ожидание м ну как слишком не про непроизводительно расходуют процессорное время. Поэтому стоит рассмотреть ээ механизмы блокирующего ожидания.
Speaker A
Давайте посмотрим. Но прежде чем посмотрим про блокирующие, всё-таки уделим немножечко времени с пидлоком, как они в ядре Linux применяются.
Speaker A
А внутри ядра Linux там существуют разные варианты захвата спинлоков. Есть обычная функция спинлоlock. При успешном захвате спинлока отключается вытеснение текущей задачи.
Speaker A
Отключается вытеснение. Это означает, что планировщик не может обычным образом вытеснить задачу, пока она удерживает блокировку. Но есть важная особенность.
Speaker A
Функция spinlock не отключает аппаратные прерывания. И давайте сейчас представим себе следующую картину. Вот у нас есть два ядра. То есть один поток ядра в какой-то момент, вот у нас есть два потока, один момент захвати один поток ядра захватил
Speaker A
какую-нибудь блокировку, да? Ну, то есть переменную с помощью спинлока захватил. КС да и начал изменять некоторую общую структуру данных. В этот момент времени на том же процессорном ядре происходит аппаратное прерывание. То есть потока два, но аппаратное прерывание на одном
Speaker A
ядре пришло. Процессор приостановит выполнение текущего кода. То есть вот где-то в этот момент мы что-то выполняли и переходит в обработчик прерывания. Вот обработчик прерывания.
Speaker A
тоже пытается эту переменную захватить, а она уже захвачена. И обработчик прерывания крутится, крутится, крутится на этой переменной в надежде, что её освободят. А кто её должен освободить? Эту переменную освободить должен был тот фрагмент кода, вот участ участок, который её захватил,
Speaker A
но мы не можем её освободить, потому что текущий поток ожидает. То есть, если вы создадите к ижды у него вызовете лог, вызов если.
Speaker A
Ну, в одном и том же потоке. Вот поэтому какие есть альтернативы? В Linux предусмотрено три.
Speaker A
Ну ладно, может, не три уже. Ну короче, как минимум три. Спинлок. Эта функция захватывает блокировку, отключает вытеснение, но не запрещает прерывания. Такой вариант подходит, когда мы уверены, что защищаемая структура данных не используется обработчиком аппаратного прерывания, который может оказаться вызваться на
Speaker A
текущем же процессоре, и тогда мы зависнем. Вот. Но между разными процессорными ядрами возможность блокировки сохраняется. Вторая функция - это spinlock IRQ. IRQ interupt request переводится.
Speaker A
Вот эта функция дополнительно отключает локальные ээ реакцию на локальные преживания, то есть которое на текущем ядре происходит.
Speaker A
Соответственно, при выходе она что делает? Она разрешает прерывание. Её используют в тем в том случае, когда прерывания были на текущем ядре разрешены, то есть вы об этом знаете.
Speaker A
И есть функция spinlock и Q save. Она сохраняет состояние м сохраняет состояние, текущее состояние.
Speaker A
вот разрешены прерывания или не разрешены, отключает их, а потом, э, с помощью spinlock и Q restore восстанавливается состояние прерывания.
Speaker A
То есть, если были запрещены, она их запрещает, ой, разрешает. Нет, если были запрещены до входа, то и останутся запрещены. Если были разрешены, то их разрешат.
Speaker A
И вот в разных случаях в эти, ну, не вы, а разработчики ядра эти функции используют.
Speaker A
И значит, важное правило при работе с критической секции. Она должна быть короткой. Второе, нельзя вызывать операции, которые могут заблокировать выполняющийся поток или перевести его в сон.
Speaker A
Вот классический спинлок предназначен для использования в атомарном контексте, где блокирующее ожидание недопустимо. Что ещё за сон?
Speaker A
Мы, значит, рассмотрели спинлоки, и преимущество возможность быстро захватить блокировку без необходимости переключаться в между контекстами. Это работает, если ожидаем ожидание короткое. Вот поэтому есть другой подход - это блокирующее ожидание. Когда поток не может продолжить выполнение, он переходит из состояния runн в
Speaker A
состоянии blocked, то есть ожидание. В таком состоянии планировщик его исключают из числа потоков, которые готовы к выполнению и может передать процессор другой задаче. Когда происходит ожидаемое событие, другой поток или компонент ядра инициирует пробуждение.
Speaker A
При этом пробуждённый поток не обязательно начнёт сразу же немедленно выполняться. Сначала он переходит в какое состояние?
Speaker A
Состояние ready, то есть готов. И когда планировщик решит посмотреть, кого кому бы следующему выдать процессорное время, он может выбрать этот поток.
Speaker A
Таким образом, вот в отличие от Bing, если у нас поток работал работал работал ему понадобилось захватить, акс занят, он будет сидеть и долбиться в это во время этого Мьютекса выполнять бесполезную работу. И потом ему, может быть, повезёт, и он Мютекс только здесь
Speaker A
захватит. При блокирующем ожидании мы взяли, увидели, что мёток захвачен, отдаём текущий поток сейчас ничего не делает.
Speaker A
Процессорное время вот во время этого участка выполняет [кашель] выполняется кем-то другим. И мы выходим к выводу, что выбор между активным и блокирующим ожиданием зависит от ожидаемой продолжительности ожидания и стоимости переключения контекста. То есть иногда с пинлок сойдёт, а иногда лучше
Speaker A
ээ использовать блокирующие ожидания. Как операционные системы реализуют блокирующие ожидания? В основе лежат два действия: приостановка потока до наступления определённого события и его последующее пробуждение.
Speaker A
Вот эти операции называют [откашливается] сп. Сп означает не то, что вот есть функции слип, типа заснуть на столько секунд.
Speaker A
Здесь в терминах осуждается, что слип мы говорим планировщику, что хотим уснуть. Ак - это кто-то нас может взять и пробудить, но мы не можем сами себя пробудить, потому что мы уснули. Вот нас кто-то другой должен разбудить.
Speaker A
Когда это может быть полезно? Например, у нас есть потокпотребитель, который должен получить данные от потока производителя. Ну, допустим, поток производитель мм генерирует какие-нибудь там, не знаю, кадры ви кадры видео, а поток производитель должен эти кадры брать и компрессировать например или
Speaker A
анализировать. Вот. И они параллельно работают. Производитель должен, точнее потребитель сперва должен проверить, доступны ли данные. Если данных пока нет, то он должен приостановить выполнение. Ну, очередь пустая, и он не может там в спинлоке не хочет крутиться в спинлоке,
Speaker A
чтобы дождаться нужного момента. Вот поэтому он должен приостановить своё выполнение. И операционная система использует для этих [вздыхает] этих, как их там называют.
Speaker A
Для этого в операционной системе есть очередь ожидания weight Q. То есть поток регистрирует своё ожидание определённого условия и переводится в заблокированное состояние. Пока он ожидает, процессор выполняет другие задачи.
Speaker A
Когда производитель подготовит данные, он изменит соответствующее состояние и инициирует пробуждение. Операционная система переведёт ожидающий поток в состоянии готовности, после чего планировщик сможет возобновить его выполнение.
Speaker A
Вот. Но смотрите, какая есть тонкость. Представим себе, что производитель проверил условия вот и обнаружил, что данных нет. и говорит: "Я пойду спать". Но прежде, чем он успел заблокироваться, производитель добавил данные и отправил уведомления. Если уведомление никуда не сохраняется,
Speaker A
а вот просто вот, ну, мы отправили уведомление, и все, кто успел уснуть, они узнают об этом уведомлении, а те, кто ещё не успел, они, соответственно, не узнают. То есть, если между принятием решения о том, что надо поспать, и тем, как мы уснули, кто-то
Speaker A
другой захотел нас пробудить, то мы сигнал пробуждения, ну проигнорируем. И это может привести к чему? К потерянному пробуждению. Lost Wup.
Speaker A
Какие есть средства в операционных системах? Ну, в линуксовом ядре этой event и в на пользовательском уровне есть Fex, у которого можно Wupде, соответственно, уснуть. В винде это wait for single object - это дождаться наступления некого события, а севе - это
Speaker A
инициировать это событие. И давайте мы рассмотрим применение примитиво в синхронизации, которая есть в операционных системах, для решения нескольких классических задач. Первая задача называется производитель-потребитель.
Speaker A
[откашливается] То есть в предыдущем разделе мы узнали, как операционная система может блокировать потоки до наступления определённого события. Теперь давайте рассмотрим задачу, в которой такой механизм действительно необходим.
Speaker A
Это задача производитель-потребитель. Представим себе программу, в которой одни потоки принимают данные сети, а другие потоки их обрабатывают, и между ними находится общая общая очередь заданий. То есть вот эти потоки что-то считывают, сохраняют данные в общий буфер, а потоки
Speaker A
потребители должны отсюда извлекать данные, их обрабатывать. Ну, например, ээ вы загружаете веб-страницы и потом эти веб-страницы должны проверить на наличие каких-нибудь там искомых слов.
Speaker A
Ну например хотите вы сделать свой аналог Гуглу, да? То есть вам надо индексировать страницы.
Speaker A
Для этого вы должны загрузить страницы, а потом их обработать. [откашливается] Вот размер у буфера, как правило, бывает ограниченным.
Speaker A
[откашливается] Например, может содержать не более восьми элементов или не больше миллиона элементов, неважно. И возникают две независимые проблемы. Первое - это защита общих данных. То есть, если несколько потоков одновременно изменят внутреннее состояние очереди, то произойдёт повреждение данных состояния
Speaker A
гонки, и программа будет вести себя непредсказуемо. Вторая - это координация выполнения. То есть, если очередь у нас пустая, то потребитель не может извлечь элемент.
Speaker A
Ему необходимо дождаться того момента, когда данные появятся. Аналогично, производитель должен ожидать свободного места, если очередь заполнена до конца.
Speaker A
И если вы решили, давайте будем использовать кс, то одного мютекса недостаточно. Тек может защитить структуру данных, но сам по себе не сообщает, когда в ней появятся новые элементы.
Speaker A
Давайте посмотрим, ээ, что произойдёт, если мы попробуем наивным способом [кашель] это решить. [откашливается] Допустим, поток потребитель смотрит: "Если очередь пустая, то надо уснуть".
Speaker A
И мы засыпаем до тех пор, пока, ну, не наступит некое событие. А если нас разбудили, то мы должны вызвать поп, ну, извлечь данные.
Speaker A
Второй поток - это поток потребитель. Он, допустим, должен сделать пуш. Пока мы предположим, что не будем ограничивать очередь и пробудить потребителя надо.
Speaker A
Казалось бы, всё работает правильно. Вот. Но может произойти, что между проверкой и вызовом сплонировщик передал время производителю. Производитель добавил элемент и вызвал функцию Wup, чтобы пробудить этот поток. А этот поток не спит. И поэтому этот сигнал он проигнорирует.
Speaker A
Если вот когда мы войдём в слип, уже поздно, как бы, ну, будильник, грубо говоря, позвенел, а мы легли спать, и нас он уже не пробудит. Вот эта ошибка называется wcup или потерянное пробуждение.
Speaker A
Как решить эту задачу? Первое, сначала надо защитить общие данные. Ээ, в C++ для блокирующего ожидания используется класс STD Mutex.
Speaker A
Как он работает? Вы объявляете переменную типа STD Mutex. Затем с помощью loggard захватываете этот meute в конструкторе. Logard в деструкторе освобожда освобождаете.
Speaker A
Кажется, мы это сегодня уже видели, да? Вот он. Кроме logard есть ещё unlock. Он тоже в конструкторе захватывает, в деструкторе освобождает, но он ещё позволяет дополнительно явным образом освободить. То есть у logard нету никаких методов, есть только конструктор
Speaker A
и деструктор, а у unклока есть метод unlock. Но одного мютекса нам недостаточно, потому что не решает задачу ожидания события. Его задача просто пустить в критическую секцию только один поток. И нам нужен ещё один примитив синхронизации для решения задачи
Speaker A
потребители, поставщики - это условные переменные. Смотрите, вот у нас есть например очередь икс, который защищает её состояние. Потребитель хочет дождаться, когда очередь станет непустой. Сначала он должен с помощью SD unlock log захватить Mutex.
Speaker A
Затем ему нужно воспользоваться conditional ой condition переменной переменно условной переменной. Вызов у неё метод weight.
Speaker A
В метод weight мы должны передать объект блокировки. То есть вот в в нашем случае это uniclock.
Speaker A
И второе, что надо передать - это функцию, которая проверяет нужные условия. То есть, фактически, мы будем ждать до тех пор, пока вот эта функция, которую мы сюда передали, не вернёт true.
Speaker A
Жди, пока не наступит вот это условие. А какое это условие? Пока очередь не пуста. Это кто так должен ждать? Потребитель или поставщик?
Speaker A
Жди, пока очередь не пуста. Точнее, жди, пока очередь пуста. или жди, пока очередь не будет не пустой.
Speaker A
Вот так вот. Слишком много отрицаний. Это потребитель должен сдать. И после выхода из Wit гарантируется, что уже захвачен. То есть вы можете работать с общими данными для того, чтобы [кашель] сообщить, но чтобы другой поток потребитель мог нашему потоку сообщить, что пора бы
Speaker A
проснуться. Есть методы для отправки уведомлений. Есть Natify One, условной переменный и Natify All. Natify One один из потоков, которые ожидают, уведомляет, а Natify All уведомляет все потоки, которые ожидают.
Speaker A
И тут есть такая ещё штука, как ложное пробуждение. То есть стандарт C++ допускает ложное предупреждение, когда функция weight возвращается без соответствующего уведомления.
Speaker A
Можно вопрос? Да. А вот захват Мютекса - это атоманые операция или какие вообще всё?
Speaker A
Так, смотрите, захват Мьютекса сам по себе это не атомарная операция. Ну то есть она состоит из n инструкций. Есть под атамарными операциями мы подразумеваем инструкции.
Speaker A
Ну, инструкции, которые не могутчитать, это инструкции, которые выполняются как единое целое и не могут быть внутри прерваны.
Speaker A
Вот. То есть получается, мы можем, ну, как бы другой поток может вать захват. Другой поток не может прервать захват.
Speaker A
Да. Так, я вам немножко про условную переменную немного неправильно сказал. Смотрите, вот эта форма метода, то есть есть, который без предиката.
Speaker A
И если вы внутри вейт, ну, вызвали вейт без предиката, то может оказаться так, что вы выйдете из вейта, когда условие ещё не наступило.
Speaker A
То есть вам нужно обязательно проверить, не пуста ли очередь. И чтобы автоматизировать это, вот используйте форму с предикатом. То есть вас будут каждый раз вызывать, где вы проверяете условия. Если вы вернули true, значит, ожидание закончилось.
Speaker A
Давайте посмотрим, как решить задачу потребитель-поставщик с помощью Мьютекса и условных переменных. Мы будем здесь использовать кольцевой буфер фиксированный фиксированного размера, допустим, восемь элементов.
Speaker A
Переменная head указывает, откуда извлекать следующий элемент, а tail - это куда записывать новый. Переменная size хранит текущее количество элементов, которые там находятся.
Speaker A
Для того, чтобы мы могли между потоками организовать взаимодействие, нам необходимо две условные переменные: Notempty и not full.
Speaker A
Кто из них будет, кто из потребителя и поставщика будет ждать переменную notempt? Потребитель должен ждать события, пока не наступит событие темпти, а, соответственно, поставщик должен ждать, пока не не должен дать ждать события notф, то есть очередь не заполнена до конца, потому
Speaker A
что добавлять в эту очередь мы не можем, у нас фиксированное количество элементов. Фактически вот тут алгоритм работы продюсера. Продюсер ждёт свободное место, добавляет элемент и уведомляет потребителя о том, что появилось. Как он это делает?
Speaker A
С помощью метода weight он ждёт наступления события not full. [тяжело вздыхает] Для как переменная как условная переменная узнает, что событие notф или оно не notфу. Мы должны здесь проверять убедиться, что размер меньше, чем вместимость. То есть, если размер
Speaker A
меньше, чем вместимый, значит, мы, значит, кольцевой буфер не не полон и ожидание можно остановить. Дальше мы записываем в tail значение, которое хотим с помощью push добавить.
Speaker A
С помощью чего там с помощью дальше мы изменяем. Это кольцевой буфер, поэтому мы выполняем инкремент.
Speaker A
То есть после седьмого элемента мы будем записывать в нулевой и увеличиваем размер. После этого нам необходимо снять блокировку и вызвать Notify One, то есть пробудить поток, который ожидал. Где он ожидал?
Speaker A
Вот здесь. Ну, в смысле, поток, который внутри метода поп содержится. Мы должны его пробудить.
Speaker A
Как устроен метод поп? Он сначала захватывает тот же самый к и теперь проверяет только значение notempty. То есть очередь не пуста, не очередь, а буфер не пуст, если количество элементов там больше нуля.
Speaker A
Как только это условие выполнилось, значит, можно оттуда брать элементы. И мы берём из позиции головы значение, перемещаем голову, опять же, по циклическому буферу на единицу и уменьшаем размер. Дальше снимаем блокировку и уведомляем, кого мы уведомляем, поставщика о том, что очередь не пустая.
Speaker A
Если он вдруг ожидал, то после того, как мы убрали один из элементов, очередью она стала уже не полная она стала, и мы уведо пробуждаем потребителя.
Speaker A
Каким образом нише избегает той проблемы, о которой мы говорили пять на какой проблемы избегает впечатление состояния? и, э, как бы [откашливается] принятие решения и выполнение этого решения. То есть мы решили заснуть и заснули. И вот в этот момент там
Speaker A
А каким образом йкап проблема? Как решается проблема пропущенного ожидания? Да, [откашливается] она решается за счёт самой самого принципа работы вот этих переменных.
Speaker A
То есть мы, во-первых, мы должны захватить, чтобы гарантировать, что одновременно работать с ресурсом может кто-то один. А второе, мы вызываем здесь метод weight. И вот метод вызывается, когда блокировка уже захвачена.
Speaker A
И фактически, что он делает? Он берёт и проверяет вот это условие под блокировкой, пока никто переменную сайз не поменял. Вот вот эти все переменные какие тут у нас?
Speaker A
Переменная head, tail, size, содержимое буфера, они все меняются под мютексом. То есть только один поток может эти переменные модифицировать.
Speaker A
Так, почему всё работает корректно? Потому что изменения буфера защищены одним ютексом. Вот метод. Как работает метод?
Speaker A
Он освобождает к на время ожидания. То есть, если мы мы вызываем weight, захватили к, ну, точнее к уже захвачен, проверяем условие. Если оно ложно, токс освобождаем.
Speaker A
Это сам метод делает. И в результате мы даём другому потоку возможность ээ поместить данные в точе в тот буфер, из которого мы их читаем.
Speaker A
Эту же самую задачу можно решить с помощью другого примитива синхронизации семафора. То есть условные перемены позволяют ожидать изменения некоторого состояния, защищённого мютексом. Но существует другой подход к синхронизации - это семафоры. Его предложил DXRA в 1960х годах. В основе лежит счётчик
Speaker A
разрешений. Вот представим себе систему, в которой одновременно могут работать не более трёх клиентов. И мы создаём семафор со значением три.
Speaker A
Каждый клиент перед началом работы вызывает. DXRA называл эту операцию. это то есть уменьшает значение счётчика - это п. Почему п? Потому что он был какой-то не русский, и на его языке слово начиналось с буквы П.
Speaker A
Соответственно, релиз или вверх это звучало как в. Он то ли швед, то ли норвежец, к сожалению, не помню. Это словыван какой-то подкрашенный, весь подпудренный, как баба. Есть такой одно слово румын.
Speaker A
Итак, значит, две операции. Эквайр - это получить разрешение. А если разрешений нет то ждать.
Speaker A
Соответственно, добавит разрешение и при необходимости разбудить ожидающий поток. Ну, фактически семафор вот в нашем случае изначально равен трём. Каждый из клиентов уменьшает значение этого семафора. Тот, кто попытался эquire сделать, когда он равен нулю, тот засыпает. Вот если после релиза мы
Speaker A
увеличиваем счётчик, и если увеличив счётчик, его значение стало равно единица, то мы пробуждаем ожидающий поток. В стандартной библиотеке есть два класса: каунтинг семофор - это семафор со счётчиком, то есть передаётся туда количество начальное значение. Это не шаблонный класс, да? Оно
Speaker A
в конструктор семафора передаётся, ну, грубо говоря, количество разрешений. Есть бане семафор, это бинарный семафор, то есть есть только одно разрешение, то есть один только может клиент зайти.
Speaker A
Можно сказать, что Binary Simfor - это почти как Mutкс, да? Ну вот если у нас Mutкс - это одноместный туалет, да, то есть туда в него может зайти только один, то семафор - это туалет с несколькими кабинками, то есть зайти
Speaker A
могут туда несколько потоков, но лишнее должны ждать. [откашливается] Но BF и MКС - это разные всё-таки разные штуки. Почему? Потому что в случае с Мютексом должен вызвать тот поток, который сделал, захватил блокировку. А в случае с симафором ирелиз - это операции к потоку не
Speaker A
привязаны. То есть один из потоков может сделать экваер, а другой может сделать релиз. Как работает значение через семафоры?
Speaker A
[откашливается] У нашей ограниченной очереди Bounded Q есть две характеристики, за которыми нужно следить. Это количество свободных мест и количество готовых элементов.
Speaker A
И мы можем эти значения учитывать с помощью двух семафоров. Первый мы назовём семафор empти. Он отвечает за разрешение на добавление элементов. Изначально буфер пуст, поэтому у нас есть N свободных мест, то есть семафор заполнен, есть семафор, назовём его Full. Он отвечает
Speaker A
за разрешение на извлечение готовых элементов. Изначально данных нет, поэтому значение равно нулю. Рассмотрим работу производителя.
Speaker A
Производитель должен вызвать equire ути, да? То есть он получае должен получить право занять одно место в буфере. Что делает? Давайте вспомним. Эквар уменьшает значение.
Speaker A
Вот переменна Эмти изначально была равна N да вместимости. Значит, он выполняет и получает право занять одно место в буфере. Если свободного места нет, то есть было ноль как бы пустых мест, то производитель заблокируется до тех пор, пока не,
Speaker A
ну, его кто-то не разблокирует. После этого поток должен захватить к добавить элемент в очередь, освободить кс и после этого вызывает релиз на на семафоре full, сообщая о появлении ещё одного готового элемента.
Speaker A
И а потребитель действует симметрично, то есть он захватывает фул, то есть ему нужно потребителю узнать количество занятых, точнее, не узнать количество, попробовать захватить занятый обратиться к занятому элементу нашего массива.
Speaker A
Если получилось, то он захватывает к модифицирует буфер, снимает блокировку, и после этого он увеличивает количество пустых. Таким образом продюсер и консмер как бы действуют кооперативно. Каждый выполнив свою часть работы, пробуждает друг друго. Важно, значит, следующее сделать. Сначала надо дождаться
Speaker A
разрешения, а потом захватить. Если вы мюток захватите до, то у вас будет деadлок. То есть нельзя сначала захватить мюкса, потом ожидать фул или эмти, потому что если поток заблокировался, удерживая, другой участник не сможет изменить очередь и создать условия для его
Speaker A
пробуждения. И вот как будет выглядеть boun через coun. То есть, смотрите, [откашливается] так тут у меня что-то текст немножко съехал. Секундочку, давайте посмотрим на метод push. Сначала вызывается ути. Этот вызов гарантирует, что производитель получил разрешение занять один свободный слот.
Speaker A
Если все места заняты или уже зарезервированы другим производителями, то поток будет ждать. Затем мы захватываемкс, добавляем элемент в буфер и после освобождения Мьютекса, а Mutкс где освобождается? При выходе вот из этого блока вызывается фулрелиз. И и вот за этим фулрелизом
Speaker A
наблюдает кто? за фул, ой, за фулрелизом наблюдает, точнее, не наблюдает, а за него борется ээ вот консюмер. То есть это вот консюмер, консюмер, а это продюсер.
Speaker A
Продюсер соответственно пытается получить разрешение на доступ к занятому элементу. Если у него получилось это сделать, он захватывает, модифицируе, считывает данные из хеда. Это к хеду надо обращаться под мютексом. Почему? Потому что там есть другие консюмеры, так, которые могут тоже хед менять. Поэтому надо
Speaker A
только один консюмер может вносить изменения. Вот взяли мы, скопировали значение, продвинули. по кругу освободили Эмпти, а за Эти боре борется у нас уже продюсер. Вот видите, вот такая перекрёстная получилась синхронизация.
Speaker A
И вот мы познакомились, значит, с мьютексами, семафорами, условными переменными. Точнее, у нас есть условные переменные, есть семафоры.
Speaker A
И с их помощью мы решили одну и ту же задачу. когда что использовать. Давайте напомню.
Speaker A
В первом варианте мы использовали условную переменную. Состояние очереди хранилось в её собственных полях, например, в счётчике сайз.
Speaker A
Потребитель ожидал выполнению условия, то что сайз больше нуля, а производитель условия, что сайз меньше числа.
Speaker A
Условная переменная позволяла приостановить выполнение потока, пока состояние не изменится. Во втором случае мы использовали семафоры, и теперь возможность добавить или извлечь элемент определялось наличие соответствующего разрешения.
Speaker A
Вот различие заключается в том, где хранится информация, необходимая для продолжения работы. Условная переменная не имеет собственного счётчика событий.
Speaker A
То есть, если вызвать Notify One в момент, когда никто не ожидает, это уведомление не сохранится.
Speaker A
Но это не проблема для корректного построенного алгоритма, поскольку нужное состояние хранится в данных, защищённых Мьютексом.
Speaker A
И внутрий, вот, точнее, не внутри вей, а внутри функции, которую мы передаём в Weй, это условие проверяется при входе внутрь Wightй. Семофор наоборот, он содержит внутренний счётчик разрешений. Если вызвать релиз до того, как другой поток выполнит, то разрешение станет останется
Speaker A
доступным до последующего использования. Какой механизм лучше? Ээ смотрите, если поток ожидает сложного условия, которое зависит от нескольких полей объекта, то подходит вам condition variable.
Speaker A
А если задача, естественно, выражается под счётом доступных ресурсов, то семафор может оказаться проще. Вот таким образом мы рассмотрели задачу, решение задачи продюсеров-консмеров на основе условных переменных и семафора.
Speaker A
Давайте рассмотрим ещё одну задачу классическую - это читатели, писатели или readers writers. Как задача сформулирована? Давайте представим себе сервер, который Ой, куда это я всё Давайте представим себе сервер, который хранит некоторую общую конфигурацию.
Speaker A
Большинство потоков только хранит он её в памяти, не где-то там в базянах, в памяти. Большинство потоков только читают эти данные, получают параметры, допустим, подключения, настройки доступа или какую-то другую информацию. Но время от времени один из потоков должен эту
Speaker A
информацию, эту конфигурацию обновить. Возникает вопрос: обязательно ли защищать все обращения конфигурации обычным Ютексом? Если мы защитим Ютексом, это будет корректно, но неэффективно. Почему?
Speaker A
Потому что читатели, они же не меняют значение конфигурации, но будут вынуждены выстраиваться в очередь за получением доступа к чтению. Да, если читателям нужно только посмотреть, вот зачем их задерживать по очереди?
Speaker A
Вот чтобы как было бы лучше. Допустим, можно разрешить нескольким читателям одновременно работать с одним ресурсом, но только одному писателю разрешить модифицировать.
Speaker A
Причём, если писатель модифицирует, ну, если писатель получил доступ, то читатели должны дождаться, пока он выполнит запись.
Speaker A
Чем отличается задача Readers Writers от Produser Consumer? В первой задаче мы координировали производство и потребление элементов. Здесь же управляем разными режимами доступа к одним и тем же данным.
Speaker A
Давайте посмотрим, как с помощью семафоров можно эту задачу реализовать. Секундочку. Так, для этого нам понадобится два бинарных семафора и один счётчик.
Speaker A
Значит, первый семафор называется Coun Mutex. Он защищает переменную Readers, в которой хранится количество активных читателей. Второй семафор называется ресурс. Он защищает саму разделяемую структуру данных. То есть у нас есть некий объект, из которого многие потоки могут читать, но но только один может
Speaker A
писать. И пока он пишет, никто читать не может. Изначально ресурс у нас равен единице, то есть доступ к ресурсу свободен.
Speaker A
Как устроен читатель? Сначала он захватывает countс, чтобы безопасно увеличить счётчик читателей. Если после увеличения счётчика читателей счётчик стал равен единице, значит это первый активный читатель. И первый активный читатель вызывает downре resource, то есть он запрещает доступ к ресурсу.
Speaker A
Тем самым писателям будет запрещён доступ к данным. Почему? Потому что вот что делает писатель. Писатель тоже хочет сделать ресурс, но если первый читатель ресурсу захватил, то писатель будет ждать.
Speaker A
Дальше что он делает? После этого он освобождает countс. Coun meex мы освободили. Теперь поток выполняет данных.
Speaker A
После того, как читатель завершает работу, он должен уменьшить счётчик читателя. Ну, он собирается, потому что вы выходить, да, точнее, он что, а, а он count защищает счётчик читателей, да, потому что у нас есть readers, мы с помощью down этот
Speaker A
счётчик уменьшили. Если после уменьшения счётчика читателей их стало равно нулю, то значит мы были последним читателем.
Speaker A
И это значит, что мы можем как бы ресурс перевести вновь в единичку, чтобы писателям, ну, разрешить доступ писателям. И затем снимаем защиту с каутмютексом.
Speaker A
Писатель гораздо проще работает. Он пытается захватить ресурс, потом записывает данные и читает ресурс. [вздыхает] Давайте обратим внимание на какую особенность.
Speaker A
Семафор ресурс может быть захвачен первым читателем, а освобождён последним. Это допустимо именно потому, что семафор, в отличие от мютекса, не имеет привязки к потоку владельцу. То есть мы здесь не могли бы использовать под именем count. Должен быть семафор.
Speaker A
Вот таким образом мы построили так называемый readк из более простых механизмов. То есть много писателей, один читатель. У этого алгоритма есть серьёзный недостаток. Как вы думаете, какой?
Speaker A
Я вижу, [откашливается] что если читатели будут постоянно читать, то писатели никогда не смогут писать.
Speaker A
Да, если читатели будут постоянно читать, то писатели будут ждать, то есть писатель не сможет зайти.
Speaker A
То есть это немножко нечестно получается. То есть, если первый читатель захватил ресурс, пока он работает, появляется второй читатель, потом третий, четвёртый и так далее. Если новые читатели допускаются сразу, когда уже есть хотя бы один активный читатель, то счётчик
Speaker A
читателей может долго оставаться неравным нулю. Вот. А пока он нуля не достигнет, ресурс будет захвачен группой читателей, и писатель будет ждать. Эта ситуация называет голоданием.
Speaker A
То есть поток ожидает ресурс неопределённо долго, хотя другие потоки продолжают выполнять работу. Ээ можно изменить политику работы с этим ресурсом. Допустим, сейчас у нас предпочтение отдаётся читателям.
Speaker A
Э есть какой ещё вариант? Writer preferent. То есть новые читатели ждут, если появился ожидающий писатель.
Speaker A
Можно ещё организовать доступ с учётом порядка запросов. Вот, чтобы ручками не писать вот такой right log, в стандартной библиотеке есть SD shared log, то есть это к с двумя режимами доступа. У него есть метод log shared - это соответственно захватить
Speaker A
как читатель. И есть просто метод log и unlock - это захватить и освободить как писатель.
Speaker A
Соответственно, есть классы Share log и unique log. Share log используются читателями, Uniclock используется писателями. И давайте покажу на примере решения проблемы читателей и писателей на примере класса Save String. То есть у нас есть некая строка, хранящая данные, и мы
Speaker A
хотим безопасно из разных потоков с этими данными работать. То есть, чтобы не было состояния гонки, когда мы модифицируем переменную data, мы могли бы использовать обычный, но тогда читатели бы выстраивались в очередь.
Speaker A
Здесь мы используем shade mute, это позволяет читателям одновременно получать доступ. Читатель с помощью shalк захватывает meex. И если писатель сейчас не пишет, то мы сразу же без ожидания получаем блокировку и возвращаем результат.
Speaker A
А writter он пытается эксклюзивный доступ, то есть с помощью uniclock выполнить. Ну или с помощью, да, с помощью uniclock log.
Speaker A
И если у него получилось, значит, он записывает сюда данные. Кстати, вот вопрос. А может ли можем ли мы здесь вот из save string вернуть не не копию строки, которая тут хранится, а константную ссылку на строку? Почему бы нам так не сделать?
Speaker A
Мы тогда бы избежали копирования. Что будет, если мы вернём константную ссылку на ната при чтении?
Speaker A
Ну, получается, что когда у нас произойдёт любой брак после уже рида, то данные сразу же моментально.
Speaker A
Ээ, да, смотрите, если мы вернули ссылку на переменную, которая была защищена Мьютексом, она была защищена Мьютексом только когда мы внутри Рида находились.
Speaker A
И после этого у нас есть ссылка на вот эту переменную дета. А что, если в этот момент её кто-то пишет, и у нас будет состояние гонки?
Speaker A
е и будет неопределённое поведение. Если мы, например, после рейда сним на ту строку, то, ну, там, с каким-нибудь значением и ээ внутри условия там что-то соответственно мы ну что-то делаем, то у нас может произойти так, что теперь момент кода мы уже поменяем
Speaker A
строку и ссылка, соответственно, ну, значение подсылки тоже изменится. Тут всё ещё даже страшнее. Как устроена строчка? строчка хранит, ну, например, указательно данные где-то в куче.
Speaker A
И может оказаться так, что пока мы, пока читатель читает строку, писатель записывает в эту строку там, не знаю, какие-то ещё новые значения, это привод к необходимости реалкации. Реаллокация там перераспределяет память, и у нас там delete допустим вызвался пока
Speaker A
читатель читает, и всё у нас там грохнулось. Поэтому не надо возвращать ссылки. То есть из объекта, к которому предполагается доступ из нескольких потоков, ссылки наружу не не отдавайте, возвращайте копии.
Speaker A
Вот поговорим об эффективности и справедливости эр Writter Locker. Вот этот Shad Mtex, он, к сожалению, нечестный. там отдаёт предпочтение читателя.
Speaker A
Вот. Более того, если у нас маленькая структура данных, чтение, которая занимает всего лишь несколько инструкций, то управление режимами совместного исключительного доступа может потребовать дополнительных затрат.
Speaker A
Ещё одна ситуация, большая структура данных, которая часто читается, но редко изменяется. Shad может дать существенный выигрыш, потому что читатели могут выполнять свои операции параллельно.
Speaker A
Но если записи происходят часто, то писателям требуется исключительный доступ, и время будет уходить на ожидание. Ну и проблема соответственно со справедливостью. Стандарт C++ не гарантирует в каком порядке Shad Mex предоставляет доступ ожидающим читателям и писателям. Поэтому, если вам нужна
Speaker A
какая-то определённая политика доступа, то вам надо либо написать ручками, либо выбрать реализацию. которая будет давать соответствующие гарантии.
Speaker A
У меня в репозитории есть честный fair rлоlog. Вот можно посмотреть на его код. Как он устроен внутрик?
Speaker A
две условные переменные. И мы знаем количество активных читателей, количество ожидающих писателей и активен ли у нас писатель или не активен.
Speaker A
И как работает блокировка. ЛОК - это эксклюзивная блокировка. Её получает писатель. То есть писатель может войти, если нет активных читателей и нет активного писателя.
Speaker A
А когда писатель выходит, он уменьшает количество тактактак. А писатель-то один, он сбрасывает переменную фолs и если вдруг были ожидающие писатели, то он их будет.
Speaker A
Таким образом, ожидающие писатели будут получать уведомления. В противом случае он разрешает всем читателям зайти.
Speaker A
А при совместной блокировке читатель может войти, если нет активного писателя и нет ожидающих писателей. То есть, если в очередь выстроились писатели, то читатели тоже выстраиваются в очередь.
Speaker A
[вздыхает] И вот тут сколько строчек, сколько вот, ну, где-то 60 примерно 65 строчек. Стоит ли это того?
Speaker A
Вот смотрите, в ситуации, когда у нас много читателей и мало писателей, то shaмte работает процентов на 30 быстрее.
Speaker A
Когда у нас, ну, вот есть что, что тут происходит? Мы два писателя выполняют в первом случае 10.000 записей, а 10 читателей выполняют 100.000 записей каждый.
Speaker A
В том случае, когда у нас два писателя выполняют по 10.000 записей и 10 читателей по 10.000 записей, то есть примерно они сбалансированы, то есть записей в пять раз больше, чем чтений, то мы получаем прирост в четыре раза.
Speaker A
Это время всей работы, когда они взяли и всё сделали. И если у нас даже даже не все работы, а когда писатели все отработали, я не помню, что я уже там мерил, но получается в 23 раза, ой, во сколько?
Speaker A
В 22 раза быстрее. То есть когда у нас два писателя выполняют много записей, то есть сколько у нас 200.000 записей и 100.000чений чещений то проблема голодания писателей гораздо лучше решается. То есть вот тут 519 мсекунд с помощью Шейт Мьютекса
Speaker A
время занимало, а тут 23 миллисекунды 22 раза. То есть вы должны выбирать тот вариант синхронизации, который вам больше всего подходит.
Speaker A
Ну и давайте посмотрим, значит, как внутри операционной системы какие средства, как обычный к внутри операционной системы устроен.
Speaker A
[откашливается] Для пользовательского режима применяются вот в в Юникссе, ой, в Линуксе этот Futex расшифровается как Fast userspace Mutex.
Speaker A
Э, как он устроен? Сначала он пытается захватить блокировку с помощью атомарной операции в пространстве, в адресном пространстве пользователя.
Speaker A
Если блокировка свободная, то захват митекса завершается успешно, то есть переход в режим ядра не происходит.
Speaker A
Если же блокировка занята, то библиотека может вызвать операцию Fexight для того, чтобы заблокировать текущий поток.
Speaker A
Ядро Линукса проверяет значение соответствующего слова в памяти. Если оно совпадает с ожидаемым, то поток помещается в очередь ожидания.
Speaker A
Если же значение уже изменилось, то операция ожидания завершается без перехода в сон. Вот эта проверка нужна вот для того, чтобы решить следующую ситуацию. Между первоначальной проверкой в режиме пользователя и вызовом системного ожидания состояние блокировки могло измениться и чтобы не ждать лишний раз.
Speaker A
Вот. То есть, если вам надо синхронизироваться в рамках одного процесса и вам почему-то стандартный текст не подходит или его у вас нету, вдруг вы на C пишите, а не на C++, то используйте Fex.
Speaker A
Давайте, какие есть [вздыхает] ещё? Если вам нужен нужно взаимное исключение и вы пишите на плюсах, используйте SCD MUTEX.
Speaker A
Если вам надо писать на C, то вы используете mutext. Для ожидания условий condition variable в поексе это cont примитив синхронизации. Если счётчик разрешения, то каунтинг семоф в поксе это 7т.
Speaker A
Ну и шамк в пок соответствует RVТ. То есть вот такие вот типы. когда что использовать в посиксе, [откашливается] если вы даже на C++ пишите, вам всё равно может понадобиться вот использовать вот эти посексовские штуки.
Speaker A
Ээ почему стандарт C++ не гарантирует использование Мьютекса и в других переменных для меж для синхронизации между процессами. То есть и condition variable, countoun semфоры, они живут в адресном пространстве нашего процесса.
Speaker A
А в посиксе вот эти примитивы явно поддерживают межпроцессную синхронизацию. Например, при создании PET Mutext можно настроить атрибут процес shad. Это позволит использовать к с нескольким процессом, чтобы он корректно был размещён в доступной для них памяти.
Speaker A
Вот такие же аналогичные возможности есть у семафоров и других некоторых механизмов синхронизации. Вот в итоге вы должны выбирать конкретные примитивы с учётом того, взаимодействуют ли у вас потоки ээ или же требуется межпроцессное взаимодействие.
Speaker A
[вздыхает] И давайте посмотрим, что выбрать, какой механизм синхронизации. Если вам нужно просто атомарный счётчик изменить, используйте STD атомиic.
Speaker A
Э если вам нужно защитить общий ресурс или структуру данных, используйте мьютексы. Если нужно дождаться выполнения условия, то condition variable совместно с Мютексом, если надо учитывать свободные ресурсы, то каунтинг семофр, ну или его аналог, да.
Speaker A
Если нужно разрешить параллельное чтение нескольким читателям, то shame. Если вам нужна блокирующая синхронизация в Линуксе, то используйте Futкс. И мы с вами что рассмотрели? Две классические задачи. продюсер консуumр, то есть когда у вас есть некий поставщик поставщик данных
Speaker A
и консюмер, который эти данные получает и как-то обрабатывает. Вот вторая задача, которую мы рассмотрели - это читатели и писатели. Это совместное чтение и исключительная запись.
Speaker A
Вот смотрите, какой бы вы механизм не выбрали, остаётся необходимость правильно проектировать протокол доступа к данным. То есть даже если вы там будете использовать мьютексы, семафоры или атомарной перемен, не гарантируют корректности произвольной вашей программы. То есть вы запросто можете словить deadlock.
Speaker A
Ну как вот у вас есть два мьютекса А и B. Вы берёте, первый поток захватывает А, второй захватывает B, а второй пытается захватить B, а потом А.
Speaker A
И в итоге у вас потоки заблокировались. Поэтому вот когда речь заходят о многопоточности, это в ваша программа становится гораздо сложнее, на порядок.
Speaker A
Вот. Ээ крэши будут происходить, ээ, скорее всего, чаще, пока вы учитесь писать такие программы, будут происходить странные зависания, которые у вас не воспроизводится, а воспроизводится у ваших пользователей.
Speaker A
Вот. Тем не менее понимать, каким образом выполнять корректно синхронизацию нужно, потому что кто-то же должен багета исправлять, не только их делать.
Speaker A
И даже иишка не всегда может справиться. Вот [вздыхает] на этом как бы я ту часть, которая относилась к синхронизации потоков внутри одного процесса, я вам рассказал в первой.
Speaker A
Какой в первой? У нас четвёртая ведь уже лабораторная, да? В четвёртой лабораторной работе вы с этим всем э познакомитесь, но сначала я вам ещё третью допишу.
Speaker A
Остались ли у вас какие-то вопросы? Хоть что-то поняли? Отлично. [откашливается] Тогда в четвёртой лабораторной работе, кажется, в четвёртой, да, вот у вас будут задачи по работе с с этими примитивами синхронизации.
Speaker A
Познакомитесь. Можно сказать так, если ваша если вы не словили deadlock или крэш в процессе написания значит фактически ну и не познакомились. То есть обязательно словите, но потом исправьте. Да ладно, тогда давайте закончим лекцию на этом. Всем пока.
Topics:синхронизация потоковсостояние гонкиrace conditionstd::atomicмьютекскритическая секциясемаформногопоточностьC++взаимные исключения
