section1_4.tex

{ %section1_4
	\subsection{Методы синхронизации в параллельных программах}
	\parВ параллельных программах разработчик часто сталкивается с проблемой синхронизации между потоками. Как правило, проблемы возникают при доступе к памяти и одновременном выполнении каких-то критических участков кода - критических секций.
	\par\textbf{Критической областью} называют секцию программы, которая должна выполняться с исключительным правом доступа к разделяемым данным, на которые имеются ссылки в этой программе. Процесс, готовящийся войти в критическую область, может быть задержан, если любой другой процесс в это время выполняется в подобной критической области.
	\parВ этом разделе будут подробно рассмотрены механизмы синхронизации потоков на программном уровне.
	\parСуществуют следующие методы решения проблем синхронизации потоков:
		\begin{itemize}
			\item\textbf{Атомарные операции} - операции, которые выполняются целиком или не выполняются вовсе. Например, транзакция к БД является атомарной операцией. Когда два потока пытаются инкрементировать одну и ту же ячейку памяти несинхронизированно, значение может увеличиться на 2, а может и на 1 в зависимости от поведения потоков, так как операция инкрементации представляет собой как минимум 3 ассемблерные инструкции. Чтобы избежать этого стоит объявлять тип данных атомарным (если таковой есть в данном языке программирования/библиотеке). Частным случаем атомарных операций являются read-modify-write операции: compare-and-swap, test-and-set, fetch-and-add. Подробнее проблема реализации атомарных операций будет поднята в разделе\\~\ref{atomic:section} \textit{Атомарность операций в многопоточной программе}.
			\item\textbf{Семафор} - объект, ограничивающий число потоков, которые могут войти в эту область кода. Как правило это число задается при инициализации семафора. Затем при захвате семафора потоком проверяется количество потоков, захвативших семафор. Если максимальное количество потоков достигнуто, то поток будет ждать пока какой-то из потоков, вошедших в область кода, освободит его. Часто использование семафоров неоправданно, так как накладные расходы на создание и поддержку семафора большие. Также следует избегать ''утечки семафора'', ситуации, при которой поток не выходит из семафора при окончании выполнения области кода если программист забыл освободить ресурс.
			\item\textbf{Reader/writer semaphore} предоставляет потокам права \textit{только} на чтение или запись, причем во время записи данных одним потоком остальные потоки не имеет доступа к ресурсу. Однако в таких семафорах может быть проблема \textit{ресурсного голодания (starvation)}, при котором пока потоки будут читать данные, другие потоки не смогут записать данные долгий промежуток времени или наоборот. Частным решением этой проблемы при равном приоритете потоков может быть поочередный доступ потоков в очереди к доступи и записи.
			\item\sloppy{\textbf{Мьютекс} - частный случай семафора, при котором данную область кода может захватывать только один поток. В случае, если мьютекс обслуживает несколько критических секций, только один поток может находиться в любой из критических секций. Часто используется при организации управления критическими секциями, так как ''легче'' классического семафора (достаточно хранить одну булеву переменную вместо счетчика), но в отличии от него, предполагается, что один и тот же поток будет захватывать и освобождать мьютекс. Следует отметить, что в стандарте языка C++11 кроме стандартного мьютекса существуют разные его модификации:  \textit{recursive\textunderscore mutex} - мьютекс, допускающий повторный вход в критическую секцию этим же потоком, \textit{timed\textunderscore mutex} - мьютекс с таймером захвата и  \textit{recursive\textunderscore timed\textunderscore mutex}, совмещающий достоинства обеих версий.}
			\item\textbf{Spinlock (циклическая блокировка)} - блокировка, при которой поток в цикле ожидает освобождения ресурса. Не всегда является оптимальным решением, так как ожидающий поток работает во время ожидания. Внутри секции кода необходимо избегать прерываний исполнения потока, чтобы избежать deadlock'a.
			\item\textbf{Seqlock (последовательная блокировка)} - механизм синхронизации, предназначенный для быстрой записи переменной несколькими потоками. В ядре Linux работает следующим образом: поток ждет, пока критическая секция освободится(spinlock); при входе в секцию инкрементируется счетчик, поток делает свою работу. При выходе из секции поток проверяет значение счетчика. Если значение счетчика не изменилось, значит в данный момент никто не записывал данные и поток выходит из критической секции, иначе он считывает значение переменной заново.
			\item\textbf{Knuth–Bendix сompletion algorithm} - одним из решений проблем синхронизации является алгоритм Кнута-Бендикса из курса дискретной математики. С его помощью можно перейти от последовательной программы к каскадной. Однако не для всех программ этот алгоритм работает, иногда он может уйти в бесконечный цикл или завершиться с ошибкой.
			\item\textbf{Barrier (барьер)} - участок кода, в котором синхронизируется состояние потоков. Например, если для функции в главном потоке требуется чтобы все дочерние потоки закончили свою работу, можно поставить барьер перед ней. Тогда она будет ждать завершения работы дочерних потоков, после чего все потоки продолжат свою работу. Примером реализации барьера может быть критическая секция, код которой разрешается выполняться только последнему потоку, запросившему выполнение. Остальные потоки должны ожидать его. Для этого необходимо знать, сколько потоков должно прийти в барьер.
			\item\textbf{Неблокирующие алгоритмы.} Часто бывает полезно не использовать стандартные приемы блокировки, а сделать алгоритм неблокирующим. В таком случае программист должен самостоятельно гарантировать, что критические секции кода не будут выполняться одновременно и целостность разделяемой памяти. Также плюсом таких алгоритмов является безопасная обработка прерываний. Для реализации таких алгоритмов часто используются другие технологии синхронизации: read-modify-write, CAS (см. раздел~\ref{atomic:section}) и другие.
			\item\textbf{RCU (read-copy-update)} - алгоритм, позволяющий потокам эффективно считывать данные, оставляя обновление данных на конец работы алгоритма, гарантируя при этом релевантные данные. Только один поток может писать данные, но читать данные могут сразу несколько потоков. Достигается это, например, путем атомарной подмены указателя (CAS). Старые версии данных хранятся для прошлых обращений, пока на них есть хотя бы один указатель. Существуют более новые инструменты для замены указателя: отдельная взаимная блокировка для писателей или механизм membarrier, использующийся в последних версия Linux. RCU может быть полезен при организации структур данных без явных блокировок.
			\item\textbf{Монитор} - объект, инкапсулирующий в себе мьютекс и служебные переменные для обеспечение безопасного доступа к методу или переменной несколькими потоками. Характеризует монитор то, что в один момент только один поток может выполнять любой из его методов. Например, если у нас существует класс (в терминах C++) Account имеющий методы add\textunderscore money(),\\sub\textunderscore money(), то имеет смысл сделать его монитором, чтобы не было конфликтов при проведении операций с аккаунтом.
		\end{itemize}
		\parОднако не обязательно организовывать параллельные вычисления используя синхронизации или блокировки. Некоторые технологии предлагают альтернативный подход к параллельным вычислениям: 
		\begin{itemize}
			\item\textbf{Программная транзакционная память} - модель памяти, в которой операции, производимые над ячейками памяти атомарны. Плюсы использования: простота использования (заключения блоков кода в блок транзакции), отсутствие блокировок, однако при неправильном использовании возможно падение производительности, а также невозможность использования операций, которые нельзя отменить внутри блока транзакции. В компиляторе GCC поддерживается с версии 4.7 следующим образом: 
				\begin{enumerate}
					\item\textunderscore \textunderscore transaction\textunderscore atomic \{ … \} — указание, что блок кода — транзакция;
					\item\textunderscore \textunderscore transaction\textunderscore relaxed \{ … \} — указание, что небезопасный код внутри блока не приводит к побочным эффектам;
					\item\textunderscore \textunderscore transaction\textunderscore cancel — явная отмена транзакции;
					\item attribute((transaction\textunderscore safe)) — указание транзакционно-безо-пасной функции;
					\item attribute((transaction\textunderscore pure)) — указание функции без побочных эффектов.
				\end{enumerate}
			\item\textbf{Модель акторов} - математическая модель параллельных вычислений, в которой программа представляет собой объектов-акторов, которые взаимодействуют между собой и могут создавать новых акторов, отправлять и посылать сообщения друг другу. Предполагается параллелизм вычислений внутри одного актора. Каждый актор имеет адрес, на который можно отправить сообщение. Каждый актор работает в отдельном потоке. Модель акторов используется для организации электронной почты, некоторых веб-сервисов SOAP и тд.
		\end{itemize}
	\parНесмотря на большое количество методов синхронизации чаще всего надо исходить из решаемой задачи. Например, если мы хотим сделать общую инкрементируемую целочисленную переменную для нескольких потоков, нет смысла создавать mutex или semaphore, более оптимально сделать переменную атомарной. Всегда надо учитывать накладные расходы на создание блокировок и время разработки.
}