Потоки и блокировки — всё по этой теме для программистов


Оглавление (нажмите, чтобы открыть):

Потоки и блокировки — всё по этой теме для программистов

Группа: Главные администраторы
Сообщений: 14349
Регистрация: 12.10.2007
Из: Twilight Zone
Пользователь №: 1

Здравствуйте, уважаемые Хабраюзеры!

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

При написании своих предыдущих постов мы совершили непростительную ошибку, начав рассматривать взаимные блокировки со сложных, но, как нам казалось, наиболее интересных случаев. Этого уважаемая аудитория Хабра, к сожалению, не оценила. Спешим исправиться, и, пусть не с первого раза, но все-таки подойти к рассмотрению проблемы блокировок с самого начала. Однако мы все же рассчитываем, что вы знаете, зачем нужны и какие бывают средства синхронизации при написании многопоточных программ.

Рецепты, описанные в этом посте весьма просты, но далеко не все даже профессиональные программисты используют осознанно, руководствуясь скорее ощущениями «почему-то кажется, что не стоит захватывать тот мьютекс из под захваченного этого». Так жили и мы долгие-долгие годы, когда в один ужасно ответственный момент не обнаружили, что на «железке», которую нужно срочно отправить заказчику, наш любимый софт не может и часа прожить без дедлока. Убив на решение этой задачи несколько дней работы своих ведущих программистов, мы приняли решение, которое изменило нашу жизнь – мы занялись суровой формализацией ситуаций взаимных блокировок, включающей строгие математические доказательства того, почему так можно делать, а так нельзя. Надо сказать, что исследование наше выродилось в кандидатскую диссертацию одного из сотрудников, но я не уверен, что использованный там формат изложения будет интересен здесь…

Итак, о блокировках с самого начала…

Природа взаимных блокировок

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

Традиционно принято считать, что причиной блокировок всегда являются мьютексы (mutex), однако это не совсем точно. Причиной блокировок могут являться любые средства и механизмы синхронизации, которые предполагают ожидание чего-либо одного потока со стороны другого, например, ожидание сигнала на переменной кондиции (condition variable) или, что значительно менее очевидно, ожидание завершение другого потока (wait/join thread). В теории, на самом деле, второй случай является тем же самым «ожиданием сигнала», однако ввиду неявности этой операции синхронизации, при поиске дедлоков о ней просто забывают, как о потенциальном источнике угрозы и часто не замечают в коде.

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

Несколько слов о модели многопоточных программ

Мы назвали эту модель – «моделью переходов» и представляет она собой совокупность ориентированных графов, где каждый граф представляет собой поток (субъект). Каждый граф имеет одну начальную вершину, соответствующую состоянию, когда ни одно средство синхронизации еще не задействовано, и имеет одну конечную вершину, соответствующую состоянию, когда ни одно средство синхронизации уже не задействовано. Предполагается, что при достижении конечной вершины поток автоматически начинается сначала. Все другие вершины графов представляют собой операцию в отношении того или иного средства синхронизации, например, L (lock) – захват мьютекса, U (unlock) – отпускание мьютекса и т.д. Для доказательств утверждений важно, что модель игнорирует время между выполнениями отдельных операций в отношении средств синхронизации, расширяя тем самым возможный диапазон динамик до бесконечности. Если аудитории Хабра интересна математическая и физическая суть модели, то я готов написать отдельный пост на эту тему, а здесь… всего лишь начало долгой, но интересной истории о многопоточном программировании.

Пример модели, состоящей из одного потока (субъекта):

В соответствии с данным рисунком, субъект может пройти по двум веткам: 0, L1, U1, 0 или 0, L1, L2, U2, U1, 0. Эта схема может рассматриваться, как конечный автомат, грамматика которого включает две фразы <0, L1, U1, 0>и <0, L1, L2, U2, U1, 0>. Будем считать, что время перехода между действиями в отношении средств синхронизации конечно, т.е. алгоритмически корректно. Не будем считать ошибкой синхронизации захват и удержание мьютекса в течение ожидания какого-либо действия пользователя, которое потенциально может никогда не наступить.

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

Простейшая взаимная блокировка с участием мьютексов

Пусть в нашей программе помимо потока (субъекта), приведенного на рисунке 1, есть еще один:

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

Ничего не мешает нашим двух независимым потокам выполниться так: поток 1 успел захватить мьютекс 1, затем планировщик переключил выполнение на поток 2, который захватил мьютекс 2, и после этого оба наших потока пытаются захватить мьютексы, которые уже захвачены – deadlock!

Назовем систему потоков (субъектов) несовместимой, если существуют хотя бы один вариант наложения цепочек их выполнения, при котором наступает ситуация взаимной блокировки. Соответственно, совместимой является такая система субъектов, для которой не существует динамики, при которой возможно возникновение ситуации взаимной блокировки.

Рассмотренные два субъекта являются несовместимыми, т.к. существует вариант наложения, приведенный на рисунке 3, при котором возникает ситуация взаимной блокировки. Отметим, что такие субъекты не обязательно будут приводить к блокировке (зависанию) программы. Динамика конкретной работы (время переходов между обращениями к средствам синхронизации) может быть такова, что найденный вариант наложения никогда не проявится в реальности. В любом случае, программный код, описываемый такой моделью, является потенциально опасным и блокировки могут проявиться при портировании на другую программную или аппаратную платформу, а также просто при изменении условий функционирования.

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

На рисунке 6 показан другой вариант совмещения цепочек выполнения для модели, представленной на рисунке 5, при котором возникает взаимная блокировка.

Прямо так и хочется сказать: Как страшно жить!

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

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

Всегда соблюдайте один и тот же порядок захвата мьютексов.

Если вы в одном потоке захватываете мьютекс 1, а затем мьютекс 2, то недопустимо захватывать их в ином порядке в другом потоке.

На самом деле, правило не так просто, как кажется на первый взгляд. Еще раз посмотрим внимательно на Рисунок 6. Там это правило нарушено, но это несколько неочевидно. Глядя на первый поток, мы фиксируем, что мьютекс 2 мы захватываем после мьютекса 1. Глядя на второй поток, мы фиксируем, что мьютекс 3 мы захватываем после мьютекса 2. Объединение этих наблюдений означает, что мьютекс 3 мы захватываем после мьютекса 1, что не выполняется в потоке 3. Результатом этого невыполнения является deadlock, который и показан на рисунке.

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

В заключение хотелось бы задать вопрос: интересна ли эта тема аудитории Хабра? Если да, то есть желание и возможность рассказать о чуть более интересных ситуациях, возникающих при использовании сигнальных переменных и, может быть, немного глубже окунуться в доказательную базу – это уже для искушенных программистов многопоточных приложений.

Проблемы многопоточности

Многопоточное программирование является далеко не простой задачей. При запуске множества потоков, получающих доступ к одним и тем же данным, могут возникать трудно выявляемые проблемы. То же самое верно в случае применения задач, Parallel LINQ и класса Parallel. Во избежание сложностей нужно изучить особенности обеспечения синхронизации и проблемы, которые могут возникать в случае использования множества потоков. В настоящей статье рассматриваются две такие проблемы — состязания за ресурсы и взаимоблокировки, а так же описываются проблемы параллелизма.

Состязания за ресурсы

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

Чтобы продемонстрировать состязание за ресурсы, ниже приведен пример, в котором определяется класс StateObject с полем int и методом ChangeState. В реализации ChangeState значение state проверяется на предмет равенства 5. Если это так, выполняется инкремент. Следующий оператор Trace.Assert немедленно проверяет, действительно ли state теперь имеет значение 6.

Кажется очевидным, что после инкремента переменной, имеющей значение 5, она должна быть равна 6. Однако это необязательно так. Например, если один поток только что выполнил оператор if (state == 5), планировщик может вытеснить его и запустить еще один поток. Второй поток попадет в тело if и, поскольку в переменной состояния по-прежнему содержится значение 5, оно будет инкрементировано до 6. После этого снова настанет черед выполнения первого потока, в результате чего в следующем операторе значение переменной состояния будет увеличено до 7. Именно здесь и возникает состязание за ресурсы с выводом соответствующего сообщения:

После запуска этой программы можно будет увидеть, как возникают состязания за ресурсы. То, сколько времени пройдет до возникновения первого состязания за ресурсы, зависит от используемой системы и компоновки программы — окончательной или отладочной. В случае если она компоновалась как окончательная версия, проблема будет возникать чаще, потому что код оптимизирован. Если в системе установлено несколько ЦП либо двух- или четырехядерные ЦП, на которых множество потоков могут выполняться одновременно, проблема тоже будет возникать чаще, чем в системе с одноядерным ЦП.

Из-за вытесняющей многозадачности в системе с одноядерным ЦП состязания также возникают, но не так часто. Ниже показан пример того, как может выглядеть выдаваемое программой сообщение. Здесь это сообщение информирует о том, что состязание за ресурсы возникло после 227 циклов. При каждом запуске приложения результаты будут выглядеть по-разному:

Избежать возникновения данной проблемы можно, заблокировав разделяемый объект. Это делается с помощью оператора lock. Внутрь блока кода, отвечающего за блокировку объекта состояния, может попадать только один поток. Из-за того, что этот объект разделяется среди всех потоков, в случае, если какой-то один из потоков уже заблокировал его, другой поток при достижении отвечающего за блокировку блока кода должен остановиться и ожидать своей очереди.

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

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

Потоки на пользовательском уровне. Потоки на уровне ядра

Обычно выделяют две общие категории потоков: потоки на уровне пользователя (user-level threads — ULT) и потоки на уровне ядра (kernel-level threads — KLT). Потоки второго типа в литературе иногда называются потоками, поддерживаемыми ядром, или облегченными процессами.

Потоки на уровне пользователя

В программе, полностью состоящей из ULT-потоков, все действия по управлению потоками выполняются самим приложением; ядро, по сути, и не подозревает о существовании потоков. На рис. 4.6,а проиллюстрирован подход, при котором используются только потоки на уровне пользователя. Чтобы приложение было многопоточным, его следует создавать с применением специальной библиотеки, представляющей собой пакет программ для работы с потоками на уровне ядра. Такая библиотека для работы с потоками содержит код, с помощью которого можно создавать и удалять потоки, производить обмен сообщениями и данными между потоками, планировать их выполнение, а также сохранять и восстанавливать их контекст.

Рис. 4.6. Потоки на пользовательском уровне и на уровне ядра

По умолчанию приложение в начале своей работы состоит из одного потока и его выполнение начинается как выполнение этого потока. Такое приложение вместе с составляющим его потоком размещается в едином процессе, который управляется ядром. Выполняющееся приложение в любой момент времени может породить новый поток, который будет выполняться в пределах того же процесса. Новый поток создается с помощью вызова специальной подпрограммы из библиотеки, предназначенной для работы с потоками. Управление к этой подпрограмме переходит в результате вызова процедуры. Библиотека потоков создает структуру данных для нового потока, а потом передает управление одному из готовых к выполнению потоков данного процесса, руководствуясь некоторым алгоритмом планирования. Когда управление переходит к библиотечной подпрограмме, контекст текущего потока сохраняется, а когда управление возвращается к потоку, его контекст восстанавливается. Этот контекст в основном состоит из содержимого пользовательских регистров, счетчика команд и указателей стека.

Все описанные в предыдущих абзацах события происходят в пользовательском пространстве в рамках одного процесса. Ядро не подозревает об этой деятельности. Оно продолжает осуществлять планирование процесса как единого целого и приписывать ему единое состояние выполнения (состояние готовности, состояние выполняющегося процесса, состояние блокировки и т.д.). Приведенные ниже примеры должны прояснить взаимосвязь между планированием потоков и планированием процессов. Предположим, что выполняется поток 2, входящий в процесс В (см. рис. 4.7). Состояния этого процесса и составляющих его потоков на пользовательском уровне показаны на рис. 4.7,а. Впоследствии может произойти одно из следующих событий.

  1. Приложение, в котором выполняется поток 2, может произвести системный вызов, например запрос ввода-вывода, который блокирует процесс В. В результате этого вызова управление перейдет к ядру. Ядро вызывает процедуру ввода-вывода, переводит процесс В в состояние блокировки и передает управление другому процессу. Тем временем поток 2 процесса В все еще находится в состоянии выполнения в соответствии со структурой данных, поддерживаемой библиотекой потоков. Важно отметить, что поток 2 не выполняется в том смысле, что он работает с процессором; однако библиотека потоков воспринимает его как выполняющийся. Соответствующие диаграммы состояний показаны на рис. 4.7,6.
  2. В результате прерывания по таймеру управление может перейти к ядру; ядро определяет, что интервал времени, отведенный выполняющемуся в данный момент процессу В, истек. Ядро переводит процесс В в состояние готовности и передает управление другому процессу. В это время, согласно структуре данных, которая поддерживается библиотекой потоков, поток 2 процесса В по-прежнему будет находиться в состоянии выполнения. Соответствующие диаграммы состояний показаны на рис. 4.7,в.
  3. Поток 2 достигает точки выполнения, когда ему требуется, чтобы поток 1 процесса В выполнил некоторое действие. Он переходит в заблокированное состояние, а поток 1 — из состояния готовности в состояние выполнения. Сам процесс остается в состоянии выполнения. Соответствующие диаграммы состояний показаны на рис. 4.7,г.

Рис. 4.7. Примеры взаимосвязей между состояниями потоков пользовательского уровня и состояниями процесса

В случаях 1 и 2 (см. рис. 4.7,6 и в) при возврате управления процессу В возобновляется выполнение потока 2. Заметим также, что процесс, в котором выполняется код из библиотеки потоков, может быть прерван либо из-за того, что закончится отведенный ему интервал времени, либо из-за наличия процесса с более высоким приоритетом. Когда возобновится выполнение прерванного процесса, оно продолжится работой процедуры из библиотеки потоков, которая завершит переключение потоков и передаст управление новому потоку процесса.

Использование потоков на пользовательском уровне обладает некоторыми преимуществами перед использованием потоков на уровне ядра. К этим преимуществам относятся следующие:

  1. Переключение потоков не включает в себя переход в режим ядра, так как структуры данных по управлению потоками находятся в адресном пространстве одного и того же процесса. Поэтому для управления потоками процессу не нужно переключаться в режим ядра. Благодаря этому обстоятельству удается избежать накладных расходов, связанных с двумя переключениями режимов (пользовательского режима в режим ядра и обратно).
  2. Планирование производится в зависимости от специфики приложения. Для одних приложений может лучше подойти простой алгоритм планирования по круговому алгоритму, а для других — алгоритм планирования, основанный на использовании приоритета. Алгоритм планирования может подбираться для конкретного приложения, причем это не повлияет на алгоритм планирования, заложенный в операционной системе.
  3. Использование потоков на пользовательском уровне применимо для любой операционной системы. Для их поддержки в ядро системы не потребуется вносить никаких изменений. Библиотека потоков представляет собой набор утилит, работающих на уровне приложения и совместно используемых всеми приложениями.

Использование потоков на пользовательском уровне обладает двумя явными недостатками по сравнению с использованием потоков на уровне ядра.

  1. В типичной операционной системе многие системные вызовы являются блокирующими. Когда в потоке, работающем на пользовательском уровне, выполняется системный вызов, блокируется не только данный поток, но и все потоки того процесса, к которому он относится.
  2. В стратегии с наличием потоков только на пользовательском уровне приложение не может воспользоваться преимуществами многопроцессорной системы, так как ядро закрепляет за каждым процессом только один процессор. Поэтому несколько потоков одного и того же процесса не могут выполняться одновременно. В сущности, у нас получается многозадачность на уровне приложения в рамках одного процесса. Несмотря на то, что даже такая многозадачность может привести к значительному увеличению скорости работы приложения, имеются приложения, которые работали бы гораздо лучше, если бы различные части их кода могли выполняться одновременно.

Эти две проблемы разрешимы. Например, их можно преодолеть, если писать приложение не в виде нескольких потоков, а в виде нескольких процессов. Однако при таком подходе основные преимущества потоков сводятся на нет: каждое переключение становится не переключением потоков, а переключением процессов, что приведет к значительно большим накладным затратам.
Другим методом преодоления проблемы блокирования является использование преобразования блокирующего системного вызова в неблокирующий. Например, вместо непосредственного вызова системной процедуры ввода-вывода поток вызывает подпрограмму-оболочку, которая производит ввод-вывод на уровне приложения. В этой программе содержится код, который проверяет, занято ли устройство ввода-вывода. Если оно занято, поток передает управление другому потоку (что происходит с помощью библиотеки потоков). Когда наш поток вновь получает управление, он повторно осуществляет проверку занятости устройства ввода-вывода.

Потоки на уровне ядра

В программе, работа которой полностью основана на потоках, работающих на уровне ядра, все действия по управлению потоками выполняются ядром. В области приложений отсутствует код, предназначенный для управления потоками. Вместо него используется интерфейс прикладного программирования (application programming interface — API) средств ядра, управляющих потоками. Примерами такого подхода являются операционные системы OS/2, Linux и W2K.
На рис. 4.6,6″ проиллюстрирована стратегия использования потоков на уровне ядра. Любое приложение при этом можно запрограммировать как многопоточное; все потоки приложения поддерживаются в рамках единого процесса. Ядро поддерживает информацию контекста процесса как единого целого, а также контекстов каждого отдельного потока процесса. Планирование выполняется ядром исходя из состояния потоков. С помощью такого подхода удается избавиться от двух упомянутых ранее основных недостатков потоков пользовательского уровня. Во-первых, ядро может одновременно осуществлять планирование работы нескольких потоков одного и того же процесса на нескольких процессорах. Во-вторых, при блокировке одного из потоков процесса ядро может выбрать для выполнения другой поток этого же процесса. Еще одним преимуществом такого подхода является то, что сами процедуры ядра могут быть многопоточными.
Основным недостатком подхода с использованием потоков на уровне ядра по сравнению с использованием потоков на пользовательском уровне является то, что для передачи управления от одного потока другому в рамках одного и того же процесса приходится переключаться в режим ядра. Результаты исследований, проведенных на однопроцессорной машине VAX под управлением UNIX-подобной операционной системы, представленные в табл. 4.1, иллюстрируют различие между этими двумя подходами. Сравнивалось время выполнения таких двух задач, как (1) нулевое ветвление (Null Fork) — время, затраченное на создание, планирование и выполнение процесса/потока, состоящего только из нулевой процедуры (измеряются только накладные расходы, связанные с ветвлением процесса/потока), и (2) ожидание сигнала (Signal-Wait) — время, затраченное на передачу сигнала от одного процесса/потока другому процессу/потоку, находящемуся в состоянии ожидания (накладные расходы на синхронизацию двух процессов/потоков). Чтобы было легче сравнивать полученные значения, заметим, что вызов процедуры на машине VAX, используемой в этом исследовании, длится 7 us, а системное прерывание — 17 us. Мы видим, что различие во времени выполнения потоков на уровне ядра и потоков на пользовательском уровне более чем на порядок превосходит по величине различие во времени выполнения потоков на уровне ядра и процессов.

Таблица 4.1. Время задержек потоков (ка) [ANDE92]

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

Комбинированные подходы

В некоторых операционных системах применяется комбинирование потоков обоих видов (рис. 4.6,в). Ярким примером такого подхода может служить операционная система Solaris. В комбинированных системах создание потоков выполняется в пользовательском пространстве, там же, где и код планирования и синхронизации потоков в приложениях. Несколько потоков на пользовательском уровне, входящих в состав приложения, отображаются в такое же или меньшее число потоков на уровне ядра. Программист может изменять число потоков на уровне ядра, подбирая его таким, которое позволяет достичь наилучших результатов.
При комбинированном подходе несколько потоков одного и того же приложения могут выполняться одновременно на нескольких процессорах, а блокирующие системные вызовы не приводят к блокировке всего процесса. При надлежащей реализации такой подход будет сочетать в себе преимущества подходов, в которых применяются только потоки на пользовательском уровне или только потоки на уровне ядра, сводя недостатки каждого из этих подходов к минимуму.

Другие схемы

Как уже упоминалось, понятия единицы распределения ресурсов и планирования традиционно отождествляются с понятием процесса. В такой концепции поддерживается однозначное соответствие между потоками и процессами. В последнее время наблюдается интерес к использованию нескольких потоков в одном процессе, когда выполняется соотношение многие-к-одному. Однако возможны и другие комбинации, а именно соответствие нескольких потоков нескольким процессам и соответствие одного потока нескольким процессам. Примеры применения каждой из упомянутых комбинаций приводятся в табл. 4.2.

Таблица 4.2. Соотношение между потоками и процессами

Соответствие нескольких потоков нескольким процессам

Идея реализации соответствия нескольких процессов нескольким потокам была исследована в экспериментальной операционной системе TRIX [SIEB83, WARD80]. В данной операционной системе используются понятия домена и потока. Домен — это статический объект, состоящий из адресного пространства и портов, через которые можно отправлять и получать сообщения. Поток — это единая выполняемая ветвь, обладающая стеком выполнения и характеризующаяся состоянием процессора, а также информацией по планированию.
Как и в других указанных ранее многопоточных подходах, в рамках одного домена могут выполняться несколько потоков. При этом удается получить уже описанное повышение эффективности работы. Кроме того, имеется возможность осуществлять деятельность одного и того же пользователя или приложения в нескольких доменах. В этом случае имеется поток, который может переходить из одного домена в другой.
По-видимому, использование одного и того же потока в разных доменах продиктовано желанием предоставить программисту средства структурирования. Например, рассмотрим программу, в которой используется подпрограмма ввода-вывода. В многозадачной среде, в которой пользователю позволено создавать процессы, основная программа может сгенерировать новый процесс для управления вводом-выводом, а затем продолжить свою работу. Однако если для дальнейшего выполнения основной программы необходимы результаты операции ввода-вывода, то она должна ждать, пока не закончится работа подпрограммы ввода-вывода. Подобное приложение можно осуществить такими способами.

  1. Реализовать всю программу в виде единого процесса. Такой прямолинейный подход является вполне обоснованным. Недостатки этого подхода связаны с управлением памятью. Эффективно организованный как единое целое процесс может занимать в памяти много места, в то время как для подпрограммы ввода-вывода требуется относительно небольшое адресное пространство. Из-за того что подпрограмма ввода-вывода выполняется в адресном пространстве более объемной программы, во время выполнения ввода-вывода весь процесс должен оставаться в основной памяти, либо операция ввода-вывода будет выполняться с применением свопинга. То же происходит и в случае, когда и основная программа, и подпрограмма ввода-вывода реализованы в виде двух потоков в одном адресном пространстве.
  2. Основная программа и подпрограмма ввода-вывода реализуются в виде двух отдельных процессов. Это приводит к накладным затратам, возникающим в результате создания подчиненного процесса. Если ввод-вывод производится достаточно часто, то необходимо будет либо оставить такой подчиненный процесс активным на все время работы основного процесса, что связано с затратами на управление ресурсами, либо часто создавать и завершать процесс с подпрограммой, что приведет к снижению эффективности.
  3. Реализовать действия основной программы и подпрограммы ввода-вывода как единый поток. Однако для основной программы следует создать свое адресное пространство (свой домен), а для подпрограммы ввода-вывода — свое. Таким образом, поток в ходе выполнения программы будет переходить из одного адресного пространства к другому. Операционная система может управлять этими двумя адресными пространствами независимо, не затрачивая никаких дополнительных ресурсов на создание процесса. Более того, адресное пространство, используемое подпрограммой ввода-вывода, может использоваться совместно с другими простыми подпрограммами ввода-вывода.

Опыт разработчиков операционной системы TRIX свидетельствует о том, что третий вариант заслуживает внимания и для некоторых приложений может оказаться самым эффективным.

Соответствие одного потока нескольким процессам

В области распределенных операционных систем (разрабатываемых для управления распределенными компьютерными системами) представляет интерес концепция потока как основного элемента, способного переходить из одного адресного пространства в другое (В последние годы активно исследуется тема перехода процессов и потоков из одного адресного пространства в другое (миграция). Эта тема рассматривается в главе 14, «Управление распределенными процессами».). Заслуживают упоминания операционная система Clouds и, в особенности, ее ядро, известное под названием Ra [DASG92]. В качестве другого примера можно привести систему Emerald [STEE95].

В операционной системе Clouds поток является единицей активности с точки зрения пользователя. Процесс имеет вид виртуального адресного пространства с относящимся к нему управляющим блоком. После создания поток начинает выполнение в рамках процесса. Потоки могут переходить из одного адресного пространства в другое и даже выходить за рамки машины (т.е. переходить из одного компьютера в другой). При переходе потока в другое место он должен нести с собой определенную информацию — такую, как управляющий терминал, глобальные параметры и сведения по его планированию (например, приоритет).

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

Вернуться в оглавление:Операционные системы

ЛЕКЦИЯ 5. Тема 6 Синхронизация процессов и потоков

Тема 6 Синхронизация процессов и потоков

6.1 Цели и средства синхронизации. Необходимость синхронизации и гонки. Критическая секция. Блокирующие переменные. Семафоры. Тупики.

Цели и средства синхронизации

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

Во многих операционных системах эти средства называются средствами межпроцессного взаимодействия — Inter Process Communications (IPC), что отражает историческую первичность понятия «процесс» по отношению к понятию «поток». Обычно к средствам IPC относят не только средства межпроцессной синхронизации, но и средства межпроцессного обмена данными.

Выполнение потока в мультипрограммной среде всегда имеет асинхронный характер. Очень сложно с полной определенностью сказать, на каком этапе выполнения будет находиться процесс в определенный момент времени. Даже в однопрограммном режиме не всегда можно точно оценить время выполнения задачи. Это время во многих случаях существенно зависит от значения исходных данных, которые влияют на количество циклов, направления разветвления программы, время выполнения операций ввода-вывода и т. п. Так как исходные данные в разные моменты запуска задачи могут быть разными, то и время выполнения отдельных этапов и задачи в целом является весьма неопределенной величиной.

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

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

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

При совместном использовании аппаратных ресурсов синхронизация также совершенно необходима. Когда, например, активному потоку требуется доступ к последовательному порту, а с этим портом в монопольном режиме работает другой поток, находящийся в данный момент в состоянии ожидания, то ОС приостанавливает активный поток и не активизирует его до тех пор, пока нужный ему порт не освободится. Часто нужна также синхронизация с событиями, внешними по отношению к вычислительной системе.

Ежесекундно в системе происходят сотни событий, связанных с распределением и освобождением ресурсов, и ОС должна иметь надежные и производительные средства, которые бы позволяли ей синхронизировать потоки с происходящими в системе событиями.

Для синхронизации потоков прикладных программ программист может использовать как собственные средства и приемы синхронизации, так и средства операционной системы. Например, два потока одного прикладного процесса могут координировать свою работу с помощью доступной для них обоих глобальной логической переменной, которая устанавливается в единицу при осуществлении некоторого события, например выработки одним потоком данных, нужных для продолжения работы другого. Однако во многих случаях более эффективными или даже единственно возможными являются средства синхронизации, предоставляемые операционной системой в форме системных вызовов. Так, потоки, принадлежащие разным процессам, не имеют возможности вмешиваться каким-либо образом в работу друг друга. Без посредничества операционной системы они не могут приостановить друг друга или оповестить о произошедшем событии. Средства синхронизации используются операционной системой не только для синхронизации прикладных процессов, но и для ее внутренних нужд. Обычно разработчики операционных систем предоставляют в распоряжение прикладных и системных программистов широкий спектр средств синхронизации. Эти средства могут образовывать иерархию, когда на основе более простых средств строятся более сложные, а также быть функционально специализированными, например средства для синхронизации потоков одного процесса, средства для синхронизации потоков разных процессов при обмене данными и т. д. Часто функциональные возможности разных системных вызовов синхронизации перекрываются, так что для решения одной задачи программист может воспользоваться несколькими вызовами в зависимости от своих личных предпочтений.

Необходимость синхронизации и гонки

Пренебрежение вопросами синхронизации в многопоточной системе может привести к неправильному решению задачи или даже к краху системы. Рассмотрим, например (рис. 6.1.1), задачу ведения базы данных клиентов некоторого предприятия. Каждому клиенту отводится отдельная запись в базе данных, в которой среди прочих полей имеются поля Заказ и Оплата. Программа, ведущая базу данных, оформлена как единый процесс, имеющий несколько потоков, в том числе поток А, который заносит в базу данных информацию о заказах, поступивших от клиентов, и поток В, который фиксирует в базе данных сведения об оплате клиентами выставленных счетов. Оба эти потока совместно работают над общим файлом базы данных, используя однотипные алгоритмы, включающие три шага.


1. Считать из файла базы данных в буфер запись о клиенте с заданным идентификатором.

2. Внести новое значение в поле Заказ (для потока А) или Оплата (для потока В).

3. Вернуть модифицированную запись в файл базы данных.

Рис. 6.1.1. Возникновение гонок при доступе к разделяемым данным

Обозначим соответствующие шаги для потока А как Al, A2 и A3, а для потока В как Bl, B2 и ВЗ. Предположим, что в некоторый момент поток А обновляет поле Заказ записи о клиенте N. Для этого он считывает эту запись в свой буфер (шаг А1), модифицирует значение поля Заказ (шаг А2), но внести запись в базу данных (шаг A3) не успевает, так как его выполнение прерывается, например, вследствие завершения кванта времени.

Предположим также, что потоку В также потребовалось внести сведения об оплате относительно того же клиента N. Когда подходит очередь потока В, он успевает считать запись в свой буфер (шаг В1) и выполнить обновление поля Оплата (шаг В2), а затем прерывается. Заметим, что в буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение.

Когда в очередной раз управление будет передано потоку А, то он, продолжая свою работу, запишет запись о клиенте N с модифицированным полем Заказ в базу данных (шаг A3). После прерывания потока А и активизации потока В последний запишет в базу данных поверх только что обновленной записи о клиенте N свой вариант записи, в которой обновлено значение поля Оплата. Таким образом, в базе данных будут зафиксированы сведения о том, что клиент N произвел оплату, но информация о его заказе окажется потерянной (рис. 6.1.2, а).

Сложность проблемы синхронизации кроется в нерегулярности возникающих ситуаций. Так, в предыдущем примере можно представить и другое развитие событий: могла быть потеряна информация не о заказе, а об оплате (рис. 6.1.2, б) или, напротив, все исправления были успешно внесены (рис. 6.1.2, в). Все определяется взаимными скоростями потоков и моментами их прерывания. Поэтому отладка взаимодействующих потоков является сложной задачей. Ситуации, подобные той, когда два или более потоков обрабатывают разделяемые данные и конечный результат зависит от соотношения скоростей потоков, называются гонками.

Рис. 6.1.2. Влияние относительных скоростей потоков на результат решения задачи

Критическая секция Критический участок

Важным понятием синхронизации потоков является понятие «критической секции» программы. Критическая секция — это часть программы, результат выполнения которой может непредсказуемо меняться, если переменные, относящиеся к этой части программы, изменяются другими потоками в то время, когда выполнение этой части еще не завершено. Критическая секция всегда определяется по отношению к определенным критическим данным, при несогласованном изменении которых могут возникнуть нежелательные эффекты. В предыдущем примере такими критическими данными являлись записи файла базы данных. Во всех потоках, работающих с критическими данными, должна быть определена критическая секция. Заметим, что в разных потоках критическая секция состоит в общем случае из разных последовательностей команд.

Чтобы исключить эффект гонок по отношению к критическим данным, необходимо обеспечить, чтобы в каждый момент времени в критической секции, связанной с этими данными, находился только один поток. При этом неважно, находится этот поток в активном или в приостановленном состоянии. Этот прием называют взаимным исключением. Операционная система использует разные способы реализации взаимного исключения. Некоторые способы пригодны для взаимного исключения при вхождении в критическую секцию только потоков одного процесса, в то время как другие могут обеспечить взаимное исключение и для потоков разных процессов.

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

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

Рис. 6.1.3. Реализация критических секций с использованием блокирующих переменных

Каждому набору критических данных ставится в соответствие двоичная переменная, которой поток присваивает значение 0, когда он входит в критическую секцию, и значение 1, когда он ее покидает. На рис. 6.1.3 показан фрагмент алгоритма потока, использующего для реализации взаимного исключения доступа к критическим данным D блокирующую переменную F(D). Перед входом в критическую секцию поток проверяет, не работает ли уже какой-нибудь поток с данными D. Если переменная F(D) установлена в 0, то данные заняты и проверка циклически повторяется. Если же данные свободны (F(D) = 1), то значение переменной F(D) устанавливается в 0 и поток входит в критическую секцию. После того как поток выполнит все действия с данными О, значение переменной F(D) снова устанавливается равным 1.

Блокирующие переменные могут использоваться не только при доступе к разделяемым данным, но и при доступе к разделяемым ресурсам любого вида.

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

Однако следует заметить, что одно ограничение на прерывания все же имеется. Нельзя прерывать поток между выполнением операций проверки и установки блокирующей переменной. Поясним это. Пусть в результате проверки переменной поток определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой поток занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому потоку, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом, был нарушен принцип взаимного исключения, что потенциально может привести к нежелательным последствиям. Во избежание таких ситуаций в системе команд многих компьютеров предусмотрена единая, неделимая команда анализа и присвоения значения логической переменной (например, команды ВТС, BTR и ВТ5 процессора Pentium). При отсутствии такой команды в процессоре соответствующие действия должны реализовываться специальными системными примитивами, которые бы запрещали прерывания на протяжении всей операции проверки и установки.

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

На рис. 6.1.4 показано, как с помощью этих функций реализовано взаимное исключение в операционных системах семейства Windows NT. Перед тем как начать изменение критических данных, поток выполняет системный вызов EnterCriticalSection(). В рамках этого вызова сначала выполняется, как и в предыдущем случае, проверка блокирующей переменной, отражающей состояние критического ресурса. Если системный вызов определил, что ресурс занят (F(D) — 0), он в отличие от предыдущего случая не выполняет циклический опрос, а переводит поток в состояние ожидания D) и делает отметку о том, что данный поток должен быть активизирован, когда соответствующий ресурс освободится. Поток, который в это время использует данный ресурс, после выхода из критической секции должен выполнить системную функцию LeaveCriticalSection(), в результате чего блокирующая переменная принимает значение, соответствующее свободному состоянию ресурса (F(D) — 1), а операционная система просматривает очередь ожидающих этот ресурс потоков и переводит первый поток из очереди в состояние готовности.

Рис. 6.1.4. Реализация взаимного исключения с использованием системных функций входа в критическую секцию и выхода из нее

Таким образом исключается непроизводительная потеря процессорного времени на циклическую проверку освобождения занятого ресурса. Однако в тех случаях, когда объем работы в критической секции небольшой и существует высокая вероятность в очень скором доступе к разделяемому ресурсу, более предпочтительным может оказаться использование блокирующих переменных. Действительно, в такой ситуации накладные расходы ОС по реализации функции входа в критическую секцию и выхода из нее могут превысить полученную экономию.

Семафоры — СЕМАФОРНЫЕ ПРИМИТИВЫ ДЕЙКСТРА

Обобщением блокирующих переменных являются так называемые семафоры Дийкстры. Вместо двоичных переменных Дийкстра (Dijkstra) предложил использовать переменные, которые могут принимать целые неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, получили название семафоров.

Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р и V. Пусть переменная S представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом.

§ V(S): переменная S увеличивается на 1 единым действием. Выборка, наращивание и запоминание не могут быть прерваны. К переменной S нет доступа другим потокам во время выполнения этой операции.

§ PCS): уменьшение S на 1, если это возможно. Если S=0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию Р, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также являются неделимой операцией.

Никакие прерывания во время выполнения примитивов V и Р недопустимы.

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную, которую по этой причине часто называют двоичным семафором. Операция Р заключает в себе потенциальную возможность перехода потока, который ее выполняет, в состояние ожидания, в то время как операция V может при некоторых обстоятельствах активизировать другой поток, приостановленный операцией Р.

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

Введем два семафора: е — число пустых буферов, и f — число заполненных буферов, причем в исходном состоянии е =N, a f =0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис. 6.1.5).

Поток-писатель прежде всего выполняет операцию Р(е), с помощью которой он проверяет, имеются ли в буферном пуле незаполненные буферы. В соответствии с семантикой операции Р, если семафор е равен 0 (то есть свободных буферов в данный момент нет), то поток-писатель переходит в состояние ожидания. Если же значением е является положительное число, то он уменьшает число свободных буферов, записывает данные в очередной свободный буфер и после этого наращивает число занятых буферов операцией V(f). Поток-читатель действует аналогичным образом, с той разницей, что он начинает работу с проверки наличия заполненных буферов, а после чтения данных наращивает количество свободных буферов.

Рис. 6.1.5. Использование семафоров для синхронизации потоков

В данном случае предпочтительнее использовать семафоры вместо блокирующих переменных. Действительно, критическим ресурсом здесь является буферный пул, который может быть представлен как набор идентичных ресурсов — отдельных буферов, а значит, с буферным пулом могут работать сразу несколько потоков, и именно столько, сколько буферов в нем содержится. Использование двоичной переменной не позволяет организовать доступ к критическому ресурсу более чем одному потоку. Семафор же решает задачу синхронизации более гибко, допуская к разделяемому пулу ресурсов заданное количество потоков. Так, в нашем примере с буферным пулом могут работать максимум N потоков, часть из которых может быть «писателями», а часть — «читателями».

Таким образом, семафоры позволяют эффективно решать задачу синхронизации Доступа к ресурсным пулам, таким, например, как набор идентичных в функциональном назначении внешних устройств (модемов, принтеров, портов), или набор областей памяти одинаковой величины, или информационных структур. Во всех этих и подобных им случаях с помощью семафоров можно организовать доступ к разделяемым ресурсам сразу нескольких потоков.

Приведенный выше пример позволяет также проиллюстрировать еще одну проблему синхронизации — взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch), или тупиками. Покажем, что если переставить местами операции Р(е) и Р(b) в потоке-писателе, то при некотором стечении обстоятельств эти два потока могут взаимно блокировать друг друга, Итак, пусть поток-писатель начинает свою работу с проверки доступности критической секции — операции Р(b), и пусть он первым войдет в критическую секцию. Выполняя операцию Р(е), он может обнаружить отсутствие свободных буферов и перейти в состояние ожидания. Как уже было показано, из этого состояния его может вывести только поток-читатель, который возьмет очередную запись из буфера. Но поток-читатель не сможет этого сделать, так как для этого ему потребуется войти в критическую секцию, вход в которую заблокирован потоком-писателем. Таким образом, ни один из этих потоков не может завершить начатую работу и возникнет тупиковая ситуация, которая не может разрешиться без внешнего воздействия.

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

На рис. 6.1.6, а показаны фрагменты соответствующих программ. Поток А запрашивает сначала принтер; а затем порт, а поток В запрашивает устройства в обратном порядке. Предположим, что после того, как ОС назначила принтер потоку А и установила связанную с этим ресурсом блокирующую переменную, поток А был прерван. Управление получил поток В, который сначала выполнил запрос на получение СОМ- порта, затем при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым потоком А. Управление снова получил поток А, который в соответствии со своей программой сделал попытку занять порт и был заблокирован, поскольку порт уже выделен потоку В. В таком положении потоки А и В могут находиться сколь угодно долго.

В зависимости от Соотношения скоростей потоков они могут либо взаимно блокировать друг друга (рис. 6.1.6, б), либо образовывать очереди к разделяемым ресурсам (рис. 6.1.6, в), либо совершенно независимо использовать разделяемые ресурсы (рис. 6.1.6, г).

Рис. 6.1.6. Возникновение взаимных блокировок при выполнении программы

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

Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть при любом соотношении взаимных скоростей потоков. Так, если бы в примере, показанном на рис. 6.1.6, поток А и поток В запрашивали ресурсы в одинаковой последовательности, то тупик был бы в принципе невозможен. Другой, более гибкий подход к предотвращению тупиков заключается в том, что ОС каждый раз при запуске задач анализирует их потребности в ресурсах и определяет, может ли в данной мультипрограммной смеси возникнуть тупик. Если да, то запуск новой задачи временно откладывается. ОС может также использовать определенные правила при назначении ресурсов потокам, например, ресурсы могут выделяться операционной системой в определенной последовательности, общей для всех потоков.

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

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

6.2 Понятие событийного программирования. Средства обработки сигналов.

Рассмотренные выше механизмы синхронизации, основанные на использовании глобальных переменных процесса, обладают существенным недостатком — они не подходят для синхронизации потоков разных процессов. В таких случаях операционная система должна предоставлять потокам системные объекты синхронизации, которые были бы видны для всех потоков, даже если они принадлежат / разным процессам и работают в разных адресных пространствах.

Примерами таких синхронизирующих объектов ОС являются системные семафоры, мьютексы, события, таймеры и другие — их набор зависит от конкретной ОС, которая создает эти объекты по запросам процессов. Чтобы процессы могли разделять синхронизирующие объекты, в разных ОС используются разные методы. Некоторые ОС возвращают указатель на объект. Этот указатель может быть доступен всем родственным Процессам, наследующим характеристики общего родительского процесса. В других ОС процессы в запросах на создание объектов синхронизации указывают имена, которые должны быть им присвоены. Далее эти имена используются разными процессами для манипуляций объектами синхронизации. В таком, случае работа с синхронизирующими объектами подобна работе с файлами. Их можно создавать, открывать, закрывать, уничтожать.

Кроме того, для синхронизации могут быть использованы такие «обычные» объекты ОС, как файлы, процессы и потоки. Все эти объекты могут находиться в двух состояниях: сигнальном и несигнальном — свободном. Для Каждого объекта смысл, вкладываемый в понятие «сигнальное состояние», зависит от типа объекта. Так, например, поток переходит в сигнальное состояние тогда, когда он завершается. Процесс переходит в сигнальное состояние тогда, когда завершаются все его потоки. Файл переходит в сигнальное состояние в том случае, когда завершается операция ввода-вывода для этого файла. Для остальных объектов сигнальное состояние устанавливается в результате выполнения специальных системных вызовов. Приостановка и активизация потоков осуществляются в зависимости от состояния синхронизирующих объектов ОС.

Потоки с помощью специального системного вызова сообщают операционной системе о том, что они хотят синхронизировать свое выполнение с состоянием некоторого объекта. Будем далее называть этот системный вызов Wait(X), где X — указатель на объект синхронизации. Системный вызов, с помощью которого поток может перевести объект синхронизации в сигнальное состояние, назовем Set(X).

Поток, выполнивший системный вызов Wait(X), переводится операционной системой в состояние ожидания до тех пор, пока объект X не перейдет в сигнальное состояние. Примерами системных вызовов типа Wait() и Set() являются вызовы WaitForSingleObject() и SetEvent() в Windows NT, DosSenWait() и OosSemSet() в OS/2, sleep() и wakeup() в UNIX.

Поток может ожидать установки сигнального состояния не одного объекта, а нескольких. При этом поток может попросить ОС активизировать его при установке либо одного из указанных объектов, либо всех объектов. Поток может в качестве аргумента системного вызова Wait() указать также максимальное время, которое он будет ожидать перехода объекта в сигнальное состояние, после чего ОС должна его активизировать в любом случае. Может случиться, что установки некоторого объекта в сигнальное состояние ожидают сразу несколько потоков. В зависимости от объекта синхронизации в состояние готовности могут переводиться либо все ожидающие это событие потоки, либо один из них.

Синхронизация тесно связана с планированием потоков, Во-первых, любое обращение потока с системным вызовом Wait(X) влечет за собой действия в подсистеме планирования — этот поток снимается с выполнения и помещается в очередь ожидающих потоков, а из очереди готовых потоков выбирается и активизируется новый поток. Во-вторых, при переходе объекта в сигнальное состояние (в результате выполнения некоторого потока — либо системного, либо прикладного) ожидающий этот объект поток (или потоки) переводится в очередь готовых к выполнению потоков. В обоих случаях осуществляется перепланирование потоков, при этом если в ОС предусмотрены изменяемые приоритеты и/или кванты времени, то они пересчитываются по правилам, принятым в этой операционной системе.

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

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

При поступлении от пользователя команды завершения приложения основной поток должен дождаться завершения всех серверных потоков и только после этого завершиться сам. Следовательно, процедура завершения должна включать вызов Wait(Xl, Х2, . ), где XI, Х2 — указатели на серверные потоки. В результате выполнения данного системного вызова основной поток будет переведен в состояние ожидания и останется в нем до тех пор, пока все серверные потоки не перейдут в сигнальное состояние, то есть завершатся. После этого OG переведет основной поток в состояние готовности. При получении доступа к процессору основной поток завершится.

Другой пример. Пусть выполнение некоторого приложения требует последовательных работ-этапов. Для каждого этапа имеется свой отдельный процесс. Сигналом для начала работы каждого следующего процесса является завершение предыдущего. Для реализации такой логики работы необходимо в каждом процессе, кроме первого, предусмотреть выполнение системного вызова Wait(X), в котором синхронизирующим объектом является предшествующий поток.

Мастер Йода рекомендует:  Текст, который продает, или как превратить посетителей в покупателей

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

Однако круг событий, е которыми потоку может потребоваться синхронизировать свое выполнение, отнюдь не исчерпывается завершением потока, процесса иди операции ввода-вывода. Поэтому в ОС, как правило, имеются и другие, более универсальные объекты синхронизации, такие как событие (event), мъютекс (nmtex), системный семафор и другие.

Мьютекс, как и семафор, обычно используется для управления доступом к данным.

В отличие от объектов-потоков, объектов-процессов и объектов-файлов, которые при переходе в сигнальное состояние переводят в состояние готовности все потоки, ожидающие этого события, объект — мьютекс «освобождает» из очереди ожидающих только один поток.

Работа мьютекса хорошо поясняется в терминах «владения». Пусть поток, который, пытаясь получить доступ к критическим данным, выполнил системный вызов Wait(X), где X — указатель на мьютекс. Предположим, что мьютекс находится в сигнальном состоянии, в этом случае поток тут же становится его владельцем, устанавливая его в несигнальное состояние, и входит в критическую секцию. После того как поток выполнил работу с критическими данными, он «отдает» мьютекс, устанавливая его в сигнальное состояние. В этот момент мьютекс свободен и не принадлежит ни одному потоку. Если какой-либо поток ожидает его освобождения, то он становится следующим владельцем этого мьютекса, одновременно мьютекс переходит в несигнальное состояние.

Объект-событие (в данном случае слово «событие» используется в узком смысле, как обозначение конкретного вида объектов синхронизации) обычно используется не для доступа к данным, а для того, чтобы оповестить другие потоки о том, что некоторые действия завершены. Пусть, например, в некотором приложении работа организована таким образом, что один поток читает данные из файла в буфер памяти, а другие потоки обрабатывают эти данные, затем первый поток считывает новую порцию данных, а другие потоки снова ее обрабатывают и так далее. В начале работы первый поток устанавливает объект-событие в несигнальное состояние. Все остальные потоки выполнили вызов Wait(X), где X — указатель события, и находятся в приостановленном состоянии, ожидая наступления этого события. Как только буфер заполняется, первый поток сообщает об этом операционной системе, выполняя вызов Set(X). Операционная система просматривает очередь ожидающих потоков и активизирует все потоки, которые ждут этого события.

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

Примером асинхронного сигнала является сигнал с терминала. Во многих ОС предусматривается оперативное снятие процесса с выполнений. Для этого пользователь может нажать некоторую комбинацию клавиш (Ctrl+C, Ctrl+Break), в результате чего ОС вырабатывает сигнал и направляет его активному процессу. Сигнал может поступить в любой момент выполнения процесса (то есть он является асинхронным), требуя от процесса немедленного завершения работы. В данном случае реакцией на сигнал является безусловное завершение процесса.

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

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

В распределенных системах, состоящих из нескольких процессоров, каждый из которых имеет собственную оперативную память, блокирующие переменные, семафоры, сигналы и другие аналогичные средства, основанные на разделяемой памяти, оказываются непригодными. В таких системах синхронизация может быть реализована только посредством обмена сообщениями.
ЛЕКЦИЯ 6

Тема 7 Управление памятью

Функции ОС по управлению памятью

Под памятью (memory) здесь подразумевается оперативная память компьютера. В отличие от памяти жесткого диска, которую называют внешней памятью (storage), оперативной памяти для сохранения информации требуется постоянное электропитание.

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

В ранних ОС управление памятью сводилось просто к загрузке программы и ее данных из некоторого внешнего накопителя (перфоленты, магнитной ленты или магнитного диска) в память. С появлением мультипрограммирования перед ОС были поставлены новые задачи, связанные с распределением имеющейся памяти между несколькими одновременно выполняющимися программами.

Функциями ОС по управлению памятью в мультипрограммной системе являются:

§ отслеживание свободной и занятой памяти;

§ выделение памяти процессам и освобождение памяти по завершении процессов;

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

§ настройка адресов программы на конкретную область физической памяти.

Помимо первоначального выделения памяти процессам при их создании ОС должна также заниматься динамическим распределением памяти, то есть выполнять запросы приложений на выделение им дополнительной памяти во время выполнения. После того как приложение перестает нуждаться в дополнительной памяти, оно может возвратить ее системе. Выделение памяти случайной длины в случайные моменты времени из общего пула памяти приводит к фрагментации и, вследствие этого, к неэффективному ее использованию. Дефрагментация памяти тоже является функцией операционной системы.

Защита памяти — это еще одна важная задача операционной системы, которая состоит в том, чтобы не позволить выполняемому процессу записывать или читать данные из памяти, назначенной другому процессу. Эта функция, как правило, реализуется программными модулями ОС в тесном взаимодействии с аппаратными средствами.

7.1 Алгоритмы распределения памяти. Распределение памяти фиксированными разделами. Распределение памяти динамическими разделами. Перемещаемые разделы.

Алгоритмы распределения памяти

Следует ли назначать каждому процессу одну непрерывную область физической памяти или можно выделять память «кусками»? Должны ли сегменты программы, загруженные в память, находиться на одном месте в течение всего периода выполнения процесса или можно ее время от времени сдвигать? Что делать, если сегменты программы не помещаются в имеющуюся память? Разные ОС по-разному отвечают на эти и другие базовые вопросы управления памятью. Далее будут рассмотрены наиболее общие подходы к распределению памяти, которые были характерны для разных периодов развития операционных систем. Некоторые из них сохранили актуальность и широко используются в современных ОС, другие же представляют в основном только познавательный интерес, хотя их и сегодня можно встретить в специализированных системах.

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

Рис. 7.2.1. Классификация методов распределения памяти

Распределение памяти фиксированными разделами

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

Очередной новый процесс, поступивший на выполнение, помещается либо в общую очередь (рис. 7.2.2, а), либо в очередь к некоторому разделу (рис. 7.2.2, 6).

Рис. 7.2.2 Распределение памяти фиксированными разделами: с общей очередью (а), с отдельными очередями (б)

Подсистема управления памятью в этом случае выполняет следующие задачи:

§ Сравнивает объем памяти, требуемый для вновь поступившего процесса, с размерами свободных разделов и выбирает подходящий раздел;

§ Осуществляет загрузку программы в один из разделов и настройку адресов. Уже на этапе трансляции разработчик программы может задать раздел, в котором ее следует выполнять. Это позволяет сразу, без использования перемещающего загрузчика, получить машинный код, настроенный на конкретную область памяти.

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

Такой способ управления памятью применялся в ранних мультипрограммных ОС. Однако и сейчас метод распределения памяти фиксированными разделами находит применение в системах реального времени, в основном благодаря небольшим затратам на реализацию. Детерминированность вычислительного процесса систем реального времени (заранее известен набор выполняемых задач, их требования к памяти, а иногда и моменты запуска) компенсирует недостаточную гибкость данного способа управления памятью.


Распределение памяти динамическими разделами

В этом случае память машины не делится заранее на разделы. Сначала вся память, отводимая для приложений, свободна. Каждому вновь поступающему на выполнение приложению на этапе создания процесса выделяется вся необходимая ему память (если достаточный объем памяти отсутствует, то приложение не принимается на выполнение и процесс для него не создается). После завершения процесса память освобождается, и на это место может быть загружен другой процесс. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера. На рис. 7.3.2 показано состояние памяти в различные моменты времени при использовании динамического распределения. Так, в момент t в памяти находится только ОС, а к моменту t1 память разделена между 5 процессами, причем процесс П4, завершаясь, покидает память. На освободившееся от процесса П4 место загружается процесс П6, поступивший в момент t3.

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

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

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

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

§ После завершения процесса корректировка таблиц свободных и занятых областей.

Рис. 7.1.3. Распределение памяти динамическими разделами

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

Распределение памяти динамическими разделами лежит в основе подсистем управления памятью многих мультипрограммных операционных системах 60-70-х годов, в частности такой популярной операционной системы, как OS/360.

Одним из методов борьбы с фрагментацией является перемещение всех занятых участков в сторону старших или младших адресов, так, чтобы вея свободная память образовала единую свободную область (рис. 7.2.4). В дополнение к функциям, которые выполняет ОС при распределении памяти динамическими разделами* в данном случае она должна еще время от времени копировать содержимое разделов из одного места памяти в другое, корректируя таблицы свободных и занятых областей. Эта процедура называется сжатием. Сжатие может выполняться либо при каждом завершении процесса, либо только тогда, когда для вновь создаваемого процесса нет свободного раздела достаточного размера. В первом случае требуется меньше вычислительной работы при корректировке таблиц свободных и занятых областей, а во втором — реже выполняется процедура сжатия.

Рис. 7.1.4. Распределение памяти перемещаемыми разделами

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

Хотя процедура сжатия и приводит к более эффективному использованию памяти, она может потребовать значительного времени, что часто перевешивает преимущества данного метода.

Концепция сжатия применяется и при использовании других методов распределения памяти, когда отдельному процессу выделяется не одна сплошная область памяти, а несколько несмежных участков памяти произвольного размера (сегментов). Такой подход был использован в ранних версиях OS/2, в которых память распределялась сегментами, а возникавшая при этом фрагментация устранялась путем периодического перемещения сегментов.

7.2 Страничное распределение. Сегментное распределение. Сегментно-страничное распределение. Совместное использование памяти. Защита памяти.

На рис. 7.2.1 показана схема страничного распределения памяти. Виртуальное адресное пространство каждого процесса делится на части одинакового, фиксированного для данной системы размера, называемые виртуальными страницами (virtual pages). В общем случае размер виртуального адресного пространства процесса не кратен размеру страницы, поэтому последняя страница каждого процесса дополняется фиктивной областью.

Вся оперативная память машины также делится на части такого же размера, называемые физическими страницами (или блоками, или кадрами). Размер страницы выбирается равным степени двойки: 512, 1024, 4096 байт и т. д. Это позволяет упростить механизм преобразования адресов.

Рис. 7.2.1. Страничное распределение памяти

При создании процесса ОС загружает в оперативную память несколько его виртуальных страниц (начальные страницы кодового сегмента и сегмента данных). Копия всего виртуального адресного пространства процесса находится на диске. Смежные виртуальные страницы не обязательно располагаются в смежных физических страницах. Для каждого процесса операционная система создает таблицу страниц — информационную структуру, содержащую записи обо всех виртуальных страницах процесса.

Запись таблицы, называемая дескриптором страницы, включает следующую информацию:

§ номер физической страницы, в которую загружена данная виртуальная страница;

§ признак присутствия, устанавливаемый в единицу, если виртуальная страница находится в оперативной памяти;

§ признак модификации страницы, который устанавливается в единицу всякий раз, когда производится запись по адресу, относящемуся к данной странице;

§ признак обращения к странице, называемый также битом доступа, который устанавливается в единицу при каждом обращении по адресу, относящемуся к данной странице.

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

При каждом обращении к памяти выполняется поиск номера виртуальной страницы, содержащей требуемый адрес, затем по этому номеру определяется нужный элемент таблицы страниц, и из него извлекается описывающая страницу информация. Далее анализируется признак присутствия, и, если данная виртуальная страница находится в оперативной памяти, то выполняется преобразование виртуального адреса в физический, то есть виртуальный адрес заменяется указанным в записи таблицы физическим адресом. Если же нужная виртуальная страница в данный момент выгружена на диск, то происходит так называемое страничное прерывание. Выполняющийся процесс переводится в состояние ожидания, и активизируется другой процесс из очереди процессов, находящихся в состоянии готовности. Параллельно программа обработки страничного прерывания находит на диске требуемую виртуальную страницу (для этого операционная система должна помнить положение вытесненной страницы в страничном файле диска) и пытается загрузить ее в оперативную память. Если в памяти имеется свободная физическая страница, то загрузка выполняется немедленно, если же свободных страниц нет, то на основании принятой в данной системе стратегии замещения страниц решается вопрос о том, какую страницу следует выгрузить из оперативной памяти.

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

Для хранения информации о положении вытесненной страницы в страничном файле ОС может использовать поля таблицы страниц или же другую системную структуру данных (например, дескриптор сегмента при сегментно-страничной организации виртуальной памяти).

Виртуальный адрес при страничном распределении может быть представлен в виде пары (р, sv), где р — порядковый номер виртуальной страницы процесса (нумерация страниц начинается с 0), a sv — смещение в пределах виртуальной страницы. Физический адрес также может быть представлен в виде пары (n, sf), где n — номер физической страницы, a sf — смещение в пределах физической страницы. Задача подсистемы виртуальной памяти состоит в отображении (р, sv) в (n, sf).

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

Первое из них состоит в том, что объем страницы выбирается равным степени двойки — 2 k . Из этого следует, что смещение s может быть получено простым отделением k младших разрядов в двоичной записи адреса, а оставшиеся старшие разряды адреса представляют собой двоичную запись номера страницы (при этом неважно, является страница виртуальной или физической). Например, если размер страницы 1 Кбайт (2 10 ), то из двоичной записи адреса 50718 = 101 000 111 0012 можно определить, что он принадлежит странице, номер которой в двоичном выражении равен 102 и смещен относительно ее начала на 1 000 111 0012 байт (рис. 8.4.2).

Рис. 7.2.2. Двоичное представление адресов

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

Второе свойство заключается в том, что в пределах страницы непрерывная последовательность виртуальных адресов однозначно отображается в непрерывную последовательность физических адресов, а значит, смещения в виртуальном и физическом адресах sv и sf равны между собой (рис. 7.2.3).

Рис. 7.2.3. При отображении виртуального адреса в физический смещение не изменяется

Отсюда следует простая схема преобразования виртуального адреса в физический (рис. 8.4.4). Младшие разряды физического адреса, соответствующие смещению, получаются переносом такого же количества младших разрядов из виртуального адреса. Старшие разряды физического адреса, соответствующие номеру физической страницы, определяются из таблицы страниц, в которой указывается соответствие виртуальных и физических страниц.

Итак, пусть произошло обращение к памяти по некоторому виртуальному адресу. Аппаратными схемами процессора выполняются следующие действия:

1. Из специального регистра процессора извлекается адрес AT таблицы страниц активного процесса. На основании начального адреса таблицы страниц, номера виртуальной страницы р (старшие разряды виртуального адреса) и длины отдельной записи в таблице страниц L (системная константа) определяется адрес нужного дескриптора в таблице страниц: a=AT+(pxL).

2. Из этого дескриптора извлекается номер соответствующей физической страницы — n.

3. К номеру физической страницы присоединяется смещение s (младшие разряды виртуального адреса).

Типичная машинная инструкция требует 3-4 обращений к памяти (выборка команды, извлечение операндов, запись результата). И при каждом обращении происходит либо преобразование виртуального адреса в физический, либо обработка страничного прерывания. Время выполнения этих операций в значительной степени влияет на общую производительность вычислительной системы, поэтому столь большое внимание разработчиков уделяется оптимизации виртуальной памяти.

Рис. 7.2.4.Схема преобразования виртуального адреса в физический при страничной организации памяти

Именно для уменьшения времени преобразования адресов во всех процессорах предусмотрен аппаратный механизм получения физического адреса по виртуальному. С той же целью размер страницы выбирается равным степени двойки, благодаря чему двоичная запись адреса легко разделяется на номер страницы и смещение, и в результате в процедуре преобразования адресов более длительная операция сложения заменяется операцией присоединения (конкатенации). Используются и другие способы ускорения преобразования, такие, например, как кэширование таблицы страниц — хранение наиболее активно используемых записей в быстродействующих запоминающих устройствах, в частности в регистрах процессора.

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

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

Наиболее популярным критерием выбора страницы на выгрузку является число обращений к ней за последний период времени. Вычисление этого критерия происходит следующим образом. Операционная система ведет для каждой страницы программный счетчик. Значения счетчиков определяются значениями признаков доступа. Всякий раз, когда происходит обращение к какой-либо странице, процессор устанавливает в единицу признак доступа в относящейся к данной странице записи таблицы страниц. ОС периодически просматривает признаки доступа всех страниц во всех существующих в данный момент записях таблицы страниц. Если какой-либо признак оказывается равным 1 (было обращение), то система сбрасывает его в 0, увеличивая при этом на единицу значение связанного с этой страницей счетчика обращений. Когда возникает необходимость удалить какую-либо страницу из памяти, ОС находит страницу, счетчик обращений которой имеет наименьшее значение. Для того чтобы критерий учитывал интенсивность обращений за последний период, ОС с соответствующей периодичностью обнуляет все счетчики.

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

Другим важным резервом повышения производительности системы является правильный выбор размера страницы. С одной стороны, чтобы уменьшить частоту страничных прерываний, следовало бы увеличивать размер страницы. С другой стороны, если страница велика, то велика и фиктивная область в последней виртуальной странице каждого процесса. Если учесть, что в среднем в каждом процессе фиктивная область составляет половину страницы, то в сумме при большом объеме страницы потери могут составить существенную величину. Из приведенных соображений еледует, что выбор размера страницы является сложной оптимизационной задачей, требующей учета многих факторов. На практике же разработчики ОС и процессоров ограничиваются неким рациональным решением, пригодным для широкого класса вычислительных систем. Типичный размер страницы составляет несколько килобайт, например, наиболее распространенные процессоры х86 и Pentium компании Intel, а также операционные системы, устанавливаемые на этих процессорах, поддерживают страницы размером 4096 байт (4 Кбайт).

Размер страницы влияет также на количество записей в таблицах страниц. Чем меньше страница, тем более объемными являются таблицы страниц процессов и тем больше места они занимают в памяти. Учитывая, что в современных процессорах максимальный объем виртуального адресного пространства процесса, как правило, не меньше 4 Гбайт (2 32 ), то при размере страницы 4 Кбайт (2 12 ) и длине записи 4 байта для хранения таблицы страниц может потребоваться 4 Мбайт памяти! Выходом в такой ситуации является хранение в памяти только той части таблицы страниц, которая активно используется в данный период времени — так как сама таблица страниц хранится в таких же страницах физической памяти, что и описываемые ею страницы, то принципиально возможно временно вытеснять часть таблицы страниц из оперативной памяти.

Именно такой результат может быть достигнут путем более сложной структуризации виртуального адресного пространства, при котором все множество виртуальных адресов процесса делится на разделы, а разделы делятся на страницы (рис. 8.4.5). Все страницы имеют одинаковый размер, а разделы содержат одинаковое количество страниц. Если размер страницы и количество страниц в разделе выбрать равными степени двойки (2 k и 2″ соответственно), то принадлежность виртуального адреса к разделу и странице, а также смещение внутри страницы можно определить очень просто: младшие k двоичных разрядов дают смещение, следующие п разрядов представляют собой номер виртуальной страницы, а оставшиеся старшие разряды (обозначим их количество т) содержат номер раздела.

Для каждого раздела строится собственная таблица страниц. Количество дескрипторов в таблице и их размер подбираются такими, чтобы объем таблицы оказался равным объему страницы. Например, в процессоре Pentium при размере страницы 4 Кбайт длина дескриптора страницы составляет 4 байта и количество записей в таблице страниц, помещающейся на страницу, равняется соответственно 1024. Каждая таблица страниц описывается дескриптором, структура которого полностью совпадает со структурой дескриптора обычной страницы. Эти дескрипторы сведены в таблицу разделов, называемую также каталогом страниц. Физический адрес таблицы разделов активного процесса содержится в специальном регистре процессора и поэтому всегда известен операционной системе. Страница, содержащая таблицу разделов, никогда не выгружается из памяти, в противном случае работа виртуальной памяти была бы невозможна.

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

Не нашли то, что искали? Воспользуйтесь поиском:

Многопоточность, блокировка доступа

Есть приведенный ниже код, суть в том, что функции Add() , Read() , Modify() , Remove() , вызываются извне и в хаотичном порядке, с разным периодом во времени.

Уже сломал голову, подскажите с помощью какой технологии языка C# мне организовать одновременный доступ к разным элементам массива MyList ? И чтобы во время удаления/добавления новых элементов, текущие процессы не сбивались с толку, например в потоке ReadThread в данную секунду обрабатывается 5ый элемент массива и в туже секунду потоком RemoveThread уничтожается 4ый, индекс 5ого измениться, как быть?

Делал объект Lock для каждой структуры свой и блокировал отдельные элементы MyList , но тоже не решило проблемы добавления, удаления.

2 ответа 2

В этой документации приведён полноценный пример использования. Краткая суть в том, что читать могут сразу несколько потоков. Писать может только один. Читающий поток может захотеть писать и тогда он запрашивает блокировку на запись , что предотвращает появление новых читателей, пока объект не освободится и не завершится запись. Читатели, на время, пока объект заблокирован и происходит запись, ждут. Максимальное время ожидания регулируется вами.

Для реализации более гранулированной блокировки вы можете объявить «корзины» для элементов, которые находятся в процессе чтения и «корзину» для элементов, находящихся в процессе правки, то есть использовать не один а два или более экземпляров ReaderWriterLockSlim . Однако, будьте осторожны. Грануляция блокировок всегда черевата мёртвыми блокировками (deadlock).

Представьте, что в вашем MyList два объекта и вы решили блокировать их отдельно. К вам одновременно приходят два запроса. Один — на чтение, другой на запись.

  1. Первый поток забрал первый элемент MyList на чтение.
  2. Второй поток забрать второй элемент MyList на запись.
  3. Первый поток начал ждать освобождения второго элемента. Он хочет его почитать.
  4. Второй поток начал ждать окончания чтения первого элемента. Он хочет его исправить.

Вы в ж. я хотел сказать в deadlock-е. Именно по этому так полезно указывать конечное значение timeout при обращении к ReaderWriterLockSlim .

Ну или сразу согласиться, что экземпляр ReaderWriterLockSlim будет один и на запись будет блокироваться весь ресурс целиком. Тогда deadlock-и вам не страшны.

Потоки и блокировки — всё по этой теме для программистов

В предыдущей части [2] было показано, как запустить задачу (task) на потоке (thread), как конфигурировать поток и как передать данные в обоих направлениях (в поток и из потока). Также описывалось, каким образом локальные переменные делаются приватными для потока, и как ссылки могут использоваться между потоками совместно, чтобы можно было обмениваться данными между потоками через общие поля класса.

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

Конструкции синхронизации можно поделить на 4 категории:

Простые методы блокировки. Суть этих методов в ожидании, когда другой поток завершится. Ожидание может быть задано на определенный период времени. К методам простой блокировки относятся Sleep, Join и Task.Wait.

Конструкции критических секций (locking constructs). Это вводит ограничение, что определенная секция кода может исполняться в любой момент времени только ограниченным количеством потоков. Исключительная блокировка (exclusive locking) встречается чаще всего — она позволяет в любой момент времени только одному потоку осуществлять доступ к общим данным, при этом другие потоки не могут помешать доступу. Стандартные конструкции исключительной блокировки это lock (Monitor.Enter/Monitor.Exit, см. далее «Locking»), Mutex (см. далее) и SpinLock (см. [3]). Конструкции не исключительной блокировки (nonexclusive locking) это Semaphore, SemaphoreSlim (см. далее) и блокировки reader/writer (см. [4]).

Конструкции сигнализации (signaling). Они позволяют потоку приостановиться, пока не придет оповещение от другого потока, что устраняет необходимость не эффективного опроса (каких-то общих флагов или переменных). Есть два используемых обычно устройства сигнализации (signaling devices): обработчики ожидания события (event wait handles, см. далее) и методы and Wait/Pulse класса Monitor [5]. Framework 4.0 представляет классы CountdownEvent (см. далее) и Barrier [6].

Не блокирующие конструкции синхронизации. Они защищают доступ к общему полю путем вызова примитивов процессора. Библиотека CLR и язык C# предоставляют следующие не блокирующие конструкции: Thread.MemoryBarrier, Thread.VolatileRead, Thread.VolatileWrite [7], ключевое слово volatile [8] и класс Interlocked [9].

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

[Что такое блокировка]

Поток считается заблокированным, когда его выполнение приостановлено по какой-то причине, такой как засыпание (Sleep) или ожидание завершения другого потока с помощью Join или EndInvoke. Заблокированный поток немедленно уступает текущий квант процессорного времени, и с этого момента не использует процессор, пока не будет удовлетворено условие снятия блокировки (blocking condition). Вы можете проверить, заблокирован ли поток, с помощью его свойства ThreadState:

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

Когда поток блокируется или разблокируется, операционная система (точнее — её планировщик, sheduler) выполняет так называемое переключение контекста (context switch). Эта операция влечет трату процессорного времени в несколько микросекунд.

Разблокировка происходит одним из 4 способов (кнопка питания на системном блоке компьютера не считается!):

• Удовлетворено условие блокировки
• Истек таймаут операции (если был указан таймаут)
• Работа потока была прервана с помощью Thread.Interrupt [10]
• Работа потока была оборвана с помощью Thread.Abort [10]

Поток не считается заблокированным, если его выполнение приостановлено через (устаревший) метод Suspend [11].

Блокировка против циклов опроса. Иногда должен поставить свои действия на паузу, пока не выполнится определенное условие. Конструкции сигнализации и критических секций эффективно решают эту проблему с помощью блокировки потока до момента, пока не будет удовлетворено условие. Однако есть более простая альтернатива: поток может ждать появления нужного условия в постоянно прокручивающемся цикле опроса. Пример:

О общем это очень затратный способ, бесполезно тратящий ресурс процессора: библиотека CLR и операционная система будут считать, что поток выполняет важное вычисление, и даст ему на это соответствующие выделенные ресурсы!

Иногда применяется гибрид между блокировкой и прокруткой с опросом:

Хотя такой вариант не слишком элегантен, он обычно намного более эффективен чем прямая прокрутка цикла без вызова Sleep. Хотя тут проблемы могут возникнуть из-за проблем конкурентного доступа к опрашиваемому флагу, по которому будет запущено продолжение действий. Правильное использование критической секции и сигналов помогает избежать этой проблемы.

Прокрутка с циклом опроса может быть редко эффективной только в тех случаях, когда Вы ожидаете удовлетворения условия в очень краткий промежуток времени (возможно в пределах нескольких микросекунд) потому что это позволяет избежать чрезмерной нагрузки на процессор и задержки на переключение контекста. Среда .NET Framework предоставляют для этого специальные методы и классы, что рассматривается в разделе описания параллельного программирования [3].

Состояния потока (ThreadState). Вы можете узнать, в каком из состояний находится поток, путем чтения свойства ThreadState. Это вернет флаги перечисления типа ThreadState, которые комбинируют 3 «слоя» данных по принципу побитного кодирования информации. Однако большинство этих бит избыточны, не используются или устарели. На диаграмме ниже показан один из «слоев»:

Следующий код преобразует ThreadState в одно из четырех наиболее полезных значений: Unstarted, Running, WaitSleepJoin и Stopped:

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

[Блокировка]

Исключительная, или монопольная блокировка (exclusive locking) используется, чтобы гарантировать, что только один поток в любой момент времени мог войти в определенную секцию кода. Есть две основные конструкции для exclusive locking, это lock и Mutex. Из этих двух конструкция lock работает быстрее и более удобен. Однако у Mutex есть ниша, в которой её блокировка может охватить приложения в различных процессах, работающих на компьютере (чем отличается процесс от потока см. [1]).

В этой секции мы начнем обсуждения с конструкции lock, и затем перейдем к рассмотрению Mutex и семафорам (для не исключительной блокировки, nonexclusive locking). Позже мы рассмотрим блокировки reader/writer [4].

Начиная с Framework 4.0 есть также структура SpinLock для сценариев кода, выполняющегося в условиях высокой конкуренции.

Начнем с примера следующего класса:


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

Вот так блокировка lock может исправить эту проблему:

Только один поток может в любой момент времени заблокировать объект синхронизации lock (в этом примере объект синхронизации _locker). Любые претендующие на доступ к lock-участку кода будут заблокированы, пока блокировка не будет снята (т. е. пока выполнение не выйдет за пределы lock-участка кода). Такой участок кода также называют критической секцией. Если больше одного потока претендуют на доступ к региону кода lock, то они ставятся в очередь готовности (ready queue), и доступ к критической секции будет даваться по принципу FIFO, т. е. первым запросил доступ — первым получит доступ (некая проблема здесь заключается в нюансах поведения планировщика Windows и библиотеки CLR, в результате чего этот порядок предоставления доступа иногда нарушается). Исключительные блокировки, как иногда говорят, принуждает к применению строго последовательного доступа (serialized access) к участку кода, защищенному lock, потому что доступ со стороны одного потока никогда не может перекрыть доступ другого. В нашем примере логика защиты применена внутри метода Go method, когда осуществляется доступ к полям _val1 и _val2.

Поток блокируется, пока оспариваемый участок критического кода находится в состоянии ThreadState WaitSleepJoin. При рассмотрении Interrupt и Abort будет описано, как заблокированный поток может быть принудительно освобожден другим потоком. Это довольно мощный метод, который может использоваться для завершения потока.

Конструкция Назначение Работает между процессами? Загрузка (*)
lock (Monitor.Enter / Monitor.Exit) Гарантирует, что только один поток в любой момент времени может получить доступ к ресурсу или секции кода. 20 нс
Mutex ДА 1000 нс
SemaphoreSlim (добавлено в Framework 4.0) Гарантирует, что не более указанного количества потоков могут получить доступ к ресурсу или секции кода. 200 нс
Semaphore ДА 1000 нс
ReaderWriterLockSlim (добавлено в Framework 3.5) Позволяет нескольким читающим потокам существовать вместе с одним записывающим. 40 нс
ReaderWriterLock (сильно устарело) 100 нс

Примечание (*): время, которое тратится на блокировку и разблокировку конструкции на одном и том же потоке (подразумевая, что другие потоки не блокируются), как это было измерено на процессоре Intel Core i7 860.

Monitor.Enter и Monitor.Exit. Оператор lock на C# фактически является «синтаксическим сахаром», т. е. обертками над вызовами методов Monitor.Enter и Monitor.Exit с блоком try/finally. Это представляет программисту упрощенную версию того, что реально происходит внутри метода Go в предыдущем примере:

Вызов Monitor.Exit без предшествующего вызова Monitor.Enter на одном и том же объекте приведет к выбрасыванию исключения.

Перезагрузки lockTaken. Код, который мы только что продемонстрировали, на компиляторах C# версия 1.0, 2.0 и 3.0 будет транслироваться из оператора lock.

Однако в этом коде есть тонкая уязвимость. Рассмотрим (маловероятное) событие исключения, которое выбрасывается с реализацией Monitor.Enter между вызовом Monitor.Enter и блоком try (при этом возможно будет вызван Abort на этом потоке, либо выбрасывание исключение OutOfMemoryException). В таком сценарии блокировка может не произойти. Если блокировка произошла, то она не будет освобождена — потому что мы никогда не войдем в блок try/finally. Это приведет к пропущенной блокировке (leaked lock).

Для устранения этой опасности разработчики CLR 4.0 добавили следующую перезагрузку для Monitor.Enter:

Параметр lockTaken равен false после этого метода если (и только если) метод Enter выбросил исключение и блокировка lock не была взята.

Вот корректный шаблон использования (в который C# 4.0 будет транслировать оператор lock):

TryEnter. Также предоставляет метод TryEnter, который позволяет задать таймаут либо в миллисекундах, либо через TimeSpan. Этот метод вернет true, если блокировка была получена, или false, если блокировка не была получена из-за таймаута метода. TryEnter может быть также вызван без аргумента, что «проверяет» блокировку lock, таймаут произойдет немедленно, если блокировка не может быть получена надлежащим способом.

Как и метод Enter, метод TryEnter перезагружен в CLR 4.0, чтобы принять аргумент lockTaken.

Выбор объекта синхронизации. Любой объект, видимый каждому из участвующих в общей работе потоков, может использоваться в качестве синхронизирующего объекта согласно одному жесткому правилу: это должен быть ссылочный тип (reference type). Синхронизирующий объект обычно имеет область доступа private (потому что это помогает инкапсулировать логику блокировки) и обычно это поле экземпляра или статическое поле. Синхронизирующий объект может иметь двойное назначение, т. е. он может быть встроен в защищаемый объект, как это делает поле _list в следующем примере:

Поле, выделенное для этой цели (такое как _locker в предыдущем примере), позволяет точное управление областью действия и гранулярностью блокировки. Объект текущего содержимого (containing object, this) — или даже его тип — также может использоваться в качестве объекта синхронизации:

Недостаток такого способа блокировки в том, что Вы не инкапсулируете отдельно логику блокировки, и становится сложнее защититься от глухой блокировки (deadlocking, см. ниже) и излишней блокировки (excessive blocking). Блокировка на типе также может просочиться через границы домена приложения (в пределах одного и того же процесса).

Также Вы можете реализовать блокировку lock на локальных переменных, захваченных lambda-выражениями или anonymous-методами.

Блокировка не ограничивает каким-либо образом доступ к самому объекту. Другими словами, x.ToString() не будет блокироваться, потому что другой поток вызвал lock(x); оба потока должны вызвать lock(x), чтобы блокировка произошла.

Когда применять блокировку? Как основное правило, Вам нужна блокировка вокруг доступа к любой записываемой общей переменной (writable shared field). Даже в простейшем случае — операция присваивания одиночного поля — нужно учитывать синхронизацию. В следующем классе ни метод Increment, ни метод Assign не будут потокобезопасными:

Ниже показаны потокобезопасные версии для Increment и Assign:

В не блокирующей синхронизации [12] мы рассмотрим случаи, когда возникает необходимость в такой синхронизации, и как барьеры на памяти и класс Interlocked [9] может предоставить альтернативу блокировке в этих ситуациях.

Блокировка и атомарность. Если группа переменных всегда читается и записывается в пределах одной и той же блокировки lock, можно сказать, что эти переменные читаются и записываются атомарно. Предположим, что поля x и y всегда читаются и назначаются внутри блокировки на объекте locker:

Можно сказать, что к x и y осуществляется атомарный доступ, потому выполнение кода в пределах блокировки не может быть разделено или вытеснено действиями в другом потоке, в результате чего посторонние действия никак не могут отдельно повлиять на x или y так, что результат вычислений станет недостоверным. Вы никогда не получите ошибку деления на 0, так как доступ к x и y реализован в одной исключительной блокировке (exclusive lock).

Атомарность, предоставленная блокировкой lock, нарушается, если произойдет выбрасывание исключения внутри блока lock. Например:

Если исключение сработало в результате вызова GetBankFee(), то банк потерял бы деньги. В этом случае нам нужно избегать проблем путем вызова GetBankFee заранее. Решение подобной проблемы для более сложных случаев — реализация логики отката (rollback) с помощью блока catch или finally.

Понятие атомарности инструкции это другая, хотя аналогичная концепция: инструкция считается атомарной, если она неделимо (её никак нельзя прервать, поделить на части) выполняется на нижележащем процессоре, см. описание не блокирующей синхронизации [12].

Вложенные блокировки. Поток можно повторно блокировать на одном и том же объекте вложенным (реентрантным) способом:

В этих сценариях объект разблокируется только когда произойдет выход из самого внешнего оператора lock, или будет выполнено соответствующее количество операторов Monitor.Exit.

Вложенная блокировка полезна, когда один метод вызывает другой в пределах критической секции lock:

Поток может быть заблокирован только на первом (самым внешним) операторе lock.

Глухие блокировки (deadlock). Глухая, или «мертвая» блокировка deadlock произойдет, когда два потока взаимно ждут освобождения ресурса, захваченного другим потоком, в результате ничего не происходит. Ниже приведена самая простая иллюстрация этой ситуации с двумя блокировками lock:

Программист может «наколбасить» и более сложные цепочки глухой блокировки с участием трех и большего количества потоков.

Библиотека CLR в стандартном окружении хоста не работает наподобие сервера SQL Server, не определяет автоматически глухие блокировки и не представляет автоматическое средство исправления таких блокировок путем останова одного из участников глухой блокировки. Глухая блокировка потоков заставляет их на неопределенное время прервать свое выполнение, если конечно Вы не предусмотрели таймаут блокировки. В итерации хоста SQL CLR, однако, deadlock-и автоматически определяются и выбрасывается (перехватываемое catch) исключение в одном из потоков, участвующих в глухой блокировке.

Deadlock одна из самых жестких проблем в многопоточности, особенно когда есть множество взаимосвязанных объектов. Фундаментальная сложность состоит в том, что Вы не можете быть уверены, что завершилась блокировка кода, который сам вызвал блокировку.

Например, Вы можете нечаянно заблокировать private-поле в своем классе x, не зная, что Ваш вызывающий код (или код, вызвавший вызывающего) уже заблокирован на поле b в классе y. Между тем другой поток делает обратное, создавая deadlock. Ирония тут в том, что проблема усиливается «хорошими» (изначально подразумеваемыми) шаблонами объектно-ориентированного стиля программирования, потому что принцип «скрывай детали кода внутри объектов» создает цепочки взаимосвязей, которые не очевидны для программиста, пока код не начнет выполняться в реальном времени.

Популярные советы избежать мертвых блокировок типа «блокируйте объекты в правильном порядке» тяжело применить на практике, хотя они могут помочь в простых случаях, примеры которых мы описывали. Лучшая стратегия — особенно внимательно применять блокировки вокруг вызова методов в объектах, которые могут ссылаться обратно на Ваш собственный объект. Тщательно взвесьте необходимость блокировки вокруг вызова методов в других классах, часто это делается, однако иногда — что мы рассмотрим позже — есть и другие опции реализации. Больше полагаясь на декларативность [13] и параллелизм обработки данных [14], не изменяемые типы (immutable types, см. далее) и не блокирующие конструкции синхронизации [12], можно снизить необходимость в блокировках.

Есть еще один способ почувствовать проблему: когда Вы вызываете другой код, содержащий блокировку, происходит скрытая инкапсуляция этой блокировки. Это не приведет к ошибке в библиотеке CLR или .NET Framework, но является фундаментальным ограничением блокировки в целом. Проблемам блокировки посвящены многие исследовательские проекты, включая Software Transactional Memory.

Другой сценарий мертвой блокировки возникнет, когда вызывается Dispatcher.Invoke (в приложении WPF) или Control.Invoke (в приложении Windows Forms) во время активной блокировки. Если случилось так, что UI запустил другой метод, который ждет на той же блокировке, то произойдет deadlock. Это часто можно исправить простым вызовом BeginInvoke вместо Invoke. Альтернативно Вы можете освободить свою блокировку перед вызовом Invoke, хотя это не будет работать, если вызывающий код запустил блокировку. Invoke и BeginInvoke будут рассматриваться далее в секции «Rich Client Applications и Thread Affinity».

Производительность. Блокировка работает быстро: Вы можете ожидать, что захват и освобождение критической секции lock займет меньше 20 наносекунд на поколении компьютеров 2010 года, если к этой секции блокировки не было конкурентного доступа. Если же был случай конкурентного доступа, то последующие затраты на переключение контекста введут трату процессорного времени примерно около микросекунды, хотя этот интервал может быть больше, если учесть время, за которое смена состояния потока будет реально обработана планировщиком. Вы можете избежать трат на переключение контекста с помощью класса SpinLock [3] — если блокировка происходит очень коротко.

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

Mutex. Мьютекс подобен C# lock, но он может работать между несколькими процессами. Другими словами, Mutex может действовать как в пределах компьютера, так и в пределах приложения.

Захват и освобождение Mutex в случае отсутствия конкурентных попыток доступа занимает несколько микросекунд — примерно в 50 раз медленнее, чем работает критическая секция lock.

С классом Mutex можно вызвать метод WaitOne для блокировки и ReleaseMutex для разблокировки. Закрытие или избавление от (disposing) Mutex автоматически освободит его. Так же, как и с оператором lock, Mutex может быть освобожден только в том потоке, который получил этот Mutex.

Общее использование для межпроцессного Mutex применяется для гарантии, что только один экземпляр программы может быть запущен в любой момент времени. Вот как это делается:

Если приложение запущено по управлением службы терминала (Terminal Services) от имени определенного пользователя, то видимый в пределах всего компьютера Mutex обычно виден только для приложений в пределах одной терминальной сессии (т. е. только в сессии этого пользователя терминала). Чтобы сделать мьютекс видимым для всех сессий терминала, снабдите его имя префиксом Global\.

Семафор. Это объект, который похож на ночной клуб: у него есть определенная емкость, принудительно отслеживаемая вышибалой на входе. Будучи заполненным, клуб больше не может принять посетителей, что создает очередь снаружи. Тогда для каждой уходящей персоны зайдет одна персона из головы очереди. Конструктор семафора требует минимум 2 аргументов: количество доступных в настоящий момент мест и общая емкость семафора.

Семафор с емкостью, равной 1, работает подобно Mutex или lock, за исключением того, что у семафора нет «владельца» — он не обращает внимания на потоки (thread-agnostic). Любой поток может вызвать Release на Semaphore, в то время как с Mutex или lock, только один поток может получить блокировку и освободить её.

Есть две подобных по функционалу версии этого класса: Semaphore и SemaphoreSlim. Последний был представлен в Framework 4.0, и он оптимизирован для удовлетворения повышенных требований на малые задержки в параллельном программировании [14]. Также он полезен в традиционной многопоточности, потому что позволяет указать билет отмены (cancellation token [15]) для ожидания. Однако это нельзя использовать для сигнализации между процессами.

Semaphore вводит трату времени процессора около 1 микросекунды в вызове WaitOne или Release; SemaphoreSlim тратит на это около четверти микросекунды.

Семафоры могут быть полезные в пределах ограниченной многопоточности — они предотвращают ситуации, когда одну и ту же секцию кода выполняют слишком много потоков. В следующем примере 5 потоков пытаются войти в ночной клуб, в который разрешено войти за один раз только троим потокам:

Результат работы этого примера:

Если вместо оператора Sleep выполняется интенсивный дисковый ввод/вывод, то этот семафор улучшит общую производительность программы путем ограничения конкурентной активности с жестким диском.

Semaphore, если он именован, может работать между процессами точно так же, как и Mutex.

[Безопасность потоков (Thread Safety)]

Программа или метод считается потокобезопасным (thread-safe) если он не вводит никакой неопределенности в работе кода при наличии сценария многопоточности. Безопасность потоков достигается главным образом путем блокировки и уменьшения возможности по взаимодействию между потоками.

Типы общего назначения (general-purpose types) редко ориентированы на многопоточность по следующим причинам:

• Цена разработки потокобезопасного кода может быть значительной, в частности если разрабатываемый тип имеет множество полей (каждое поле потенциально может взаимодействовать в произвольном контексте многопоточности).
• Обеспечение потокобезопасности может повлечь дополнительные затраты процессорного времени, что снизит общую производительность кода (в частности затраты могут зависеть от того, используется ли в действительности этот тип несколькими потоками).
• Потокобезопасный тип вовсе не обязательно приведет к безопасному его использованию в программе. Также часто конечный код, включающий использование потокобезопасного типа, делает его потокобезопасность избыточной.

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

Однако здесь есть несколько способов «обмана», чтобы безопасно запустить большие и сложные классы в многопоточном окружении. Один из них — жертвовать гранулярностью путем обертки одной монопольной блокировкой больших секций кода — даже доступ ко всем объекту — принуждая применить последовательный доступ к объекту на верхнем уровне. Такая тактика фактически важна, если Вы хотите использовать не безопасный по отношению к многопоточности сторонний код (или большинство Framework-типов) в многопоточном контексте. Прием должен просто использовать одинаковую монопольную блокировку (exclusive lock), чтобы защитить доступ ко всем свойствам, методам и полям на не безопасном по отношению к потокам объекте. Это решение хорошо работает, если все методы объекта выполняются быстро (иначе будут иметь место большие блокировки).

Примитивные типы, к которым относятся некоторые типы .NET Framework, будучи инстанцированными, являются потокобезопасными только при доступе read-only. Ответственность за правильное их использование для потокобезопасности лежит на разработчике, обычно это верно для монопольных блокировок (исключение составляют сборки в библиотеке System.Collections.Concurrent).

Другой способ обмана — минимизация взаимодействия потоков путем минимизации количества общих данных. Это отличный подход, неявно используемый в приложениях среднего уровня, не сохраняющих свое состояние, и серверах веб-страниц. Поскольку могут одновременно поступить несколько клиентских запросов, вызываемые методы сервера должны быть потокозащищенными. Дизайн без сохранения состояния (stateless, популярный по причине хорошей масштабируемости) изначально ограничивает возможность взаимодействия между потоками, поскольку классы не сохраняют данные между запросами. Тогда взаимодействие потоков ограничивается только статическими полями, решение создать которые можно принять только в целях кэширования в памяти общих используемых данных, и предоставления инфраструктуры служб аутентификации и аудита.

Конечный этап реализации безопасности потоков состоит в использовании режима автоматической блокировки. Библиотека .NET Framework это точно делает, если вы разделяете ContextBoundObject на подклассы и применяете атрибут Synchronization для этого класса. Тогда каждый раз, когда вызывается метод или происходит обращение к свойству такого объекта, автоматически берется блокировка на весь объект, пока не выполнится полностью метод или не завершится доступ к свойству. Хотя это упрощает обеспечение безопасности потоков, возникают собственные проблемы: мертвые блокировки (deadlock), которые иначе не произошли бы, ухудшение параллелизма и непреднамеренная реентрантность. По этим причинам ручная блокировка обычно лучший выбор — по крайней мере пока не станет доступным упрощенный режим автоматической блокировки.

Безопасность потоков и типы .NET Framework. Блокировку можно использовать, чтобы превратить не безопасный по отношению к потокам код в потокобезопасный. Хорошее применение для этого библиотека .NET Framework: почти все её не примитивные типы, будучи инстанцированными, не являются потокобезопасными (для чего-то большего, чем доступ только на чтение). И все же они могут быть использованы в многопоточном коде, если любой доступ к любому имеющемуся объекту осуществляется через блокировку lock. Ниже приведен пример, где два потока одновременно добавляют элемент в одну и ту же коллекцию List, и затем делают перечисление списка в цикле:

В этом примере мы осуществляем блокировку на самом объекте _list. Если бы у нас было 2 взаимосвязанных списка, мы должны были бы выбрать общий объект, на котором можно было бы осуществить блокировку (мы могли бы выбрать для этого один из этих списков, но лучше использовать для блокировки отдельное, независимое поле).

Перечисление коллекций .NET также не является потокобезопасным в том смысле, что будет выброшено исключение, если список модифицируется во время процесса его перечисления. Вместо того, чтобы блокироваться на время до завершения перечисления, в этом примере мы просто сначала делаем копию элементов в массив. Это дает возможность избежать чрезмерной блокировки, если процесс перечисления списка может занять много времени (другое решение — использовать блокировку reader/writer [4]).

Блокировки вокруг потокобезопасных объектов. Иногда также нужно делать блокировку при доступе к потокобезопасным объектам. Для иллюстрации представим, что Framework-класс List был действительно потокобезопасным, и мы хотим добавить элемент в его список:

Независимо от того, является список потокобезопасным или нет, этот оператор определенно не является потокобезопасным! Для обеспечения потокобезопасности весь оператор if должен быть обернут в блокировку, чтобы предотвратить вытеснение в промежутке между проверкой и добавлением нового элемента. Та же самая блокировка затем нужна в любом месте, где мы модифицируем этот список. Например, следующий оператор также нуждается в обертке идентичной блокировкой (чтобы гарантировать, что процесс модификации не вытеснит предыдущий оператор):

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

Блокировка вокруг доступа к коллекции может привести к чрезмерной блокировке в среде высокой конкуренции потоков. Для этого Framework 4.0 предоставляет потокобезопасные очередь (queue), стек (stack) и словарь (dictionary).

Статические члены класса. Обертывание доступа к объекту вокруг пользовательской блокировки работает только если все конкурентные потоки учитывают и используют блокировки. Это может не иметь место, если объект широко доступен. Самый худший случай — статический (объявленный с ключевым словом static) член класса со снятым ограничением на доступ (объявлен с типом доступа public). Для примера представим: если статическое свойство DateTime.Now структуры DateTime, было бы не потокобезопасным, то два конкурентных доступа к нему дадут ошибочный результат или выбрасывание исключения. Единственный способ бороться с этим через внешнюю блокировку мог бы состоять в том, чтобы заблокировать доступ к самому типу — lock(typeof(DateTime)) — перед вызовом DateTime.Now. Это работало бы, только если все программисты согласились бы поступать подобным образом (что маловероятно). Кроме того, блокировка типа создает собственные проблемы.

По этой причине статические члены структуры DateTime (структура и класс на C# это по сути одно и то же) должны быть тщательно реализованы для обеспечения потокобезопасности. Ото общий шаблон поведения кода библиотеки .NET Framework: static-члены потокобезопасны; члены экземпляров (instance members) не потокобезопасны. Следование этому шаблону также целесообразно при написании типов для публичного использования, чтобы не создавать невозможные проблемы с безопасностью потоков. Другими словами, путем реализации статических методов потокозащищенными Вы программируете код типа, чтобы не исключать безопасность потоков для пользователей этого типа.

Мастер Йода рекомендует:  Примеры кода, синтаксически валидного и одинаково работающего в нескольких языках

Безопасность для использования в потоках статических методов это то, что Вы должны кодировать специально: оно не произойдет само собой, на основании объявления метода статическим!

Безопасность для потоков при доступе только на чтение. Реализация типов потокобезопасными для конкурентного доступа только на чтение (где это возможно) выгодна, поскольку это означает, что пользователи могут избежать чрезмерной блокировки. Многие типы из библиотеки .NET Framework следуют этому принципу: коллекции (collections), например, потокобезопасны для конкурентного доступа потоков на чтение.

Следование этому принципу простое: если Вы документируете тип как потокобезопасный для конкурентного доступа только на чтение, не записывайте в поля в методах, которые пользователь ожидает работающими только на чтение (или делайте блокировку вокруг записи). Например, в реализации метода ToArray() в коллекции Вы можете начать со сжатия внутренней структуры коллекции. Однако это сделало бы метод не потокобезопасным для пользователей, которые ожидают доступа только на чтение.

Безопасность потоков для только чтения одна из причин, по которой перечислители (enumerators) отделены от перечислений (enumerables): два потока могут одновременно перечислять элементы коллекции, потому что каждый получает отдельный объект перечислителя.

При отсутствии документации приходится платить предположением, что по своей природе любой метод работает только на чтение. Хороший пример это класс Random: когда Вы вызываете Random.Next(), его внутренняя реализация требует, чтобы это действие обновило внутреннее приватное значение seed. Таким образом, Вы должны либо делать блокировку вокруг использования класса Random, или поддерживать раздельные экземпляры этого класса для каждого потока.

Безопасность потоков в серверах приложений (Application Servers). Серверы приложений требуют многопоточности для обработки одновременных запросов от клиентов. Приложения WCF, ASP.NET и Web Services неявно используют многопоточность; то же самое верно для приложений сервера Remoting, которые используют сетевой канал, такой как TCP или HTTP. Это означает, что когда Вы пишете код на стороне сервера, то должны учитывать безопасность потоков, если есть возможность взаимодействия среди потоков при обработке запросов клиентов. К счастью, такая возможность редка; типичный класс сервера либо не сохраняет состояния (stateless, не имеет полей), либо содержит модель активации, которая создает отдельный экземпляр объекта на каждый потупивший запрос от клиента. Взаимодействие обычно возникает только через статические поля, иногда используемые для кэширования в памяти частей базы данных в целях улучшения производительности.

Например, предположим, что у Вас есть метод RetrieveUser, который делает запрос к базе данных:

Если этот метод вызывался часто, то Вам следует улучшить производительность путем кэширования результатов в статическом словаре (static Dictionary). Вот решение, учитывающее безопасность потоков:

Мы должны, как минимум, делать блокировку вокруг чтения и обновления словаря для гарантии безопасности потоков. В этом примере мы выбрали практический компромисс в блокировке между простотой и производительностью. Наш дизайн потенциально создает очень малую потенциальную не эффективность: если 2 потока одновременно вызовут этот метод с одним и тем же ранее не запрашиваемым id, то метод RetrieveUser был бы вызван дважды — и словарь получил бы ненужное обновление. Блокировка вокруг всего метода предотвратила бы это, но создала бы еще меньшую эффективность: весь кэш был бы заблокирован на время вызова RetrieveUser, в течение этого времени другие потоки блокировались бы при запросе любого пользователя.

Rich Client Applications и Thread Affinity. Обе библиотеки Windows Presentation Foundation (WPF) и Windows Forms следуют моделям на основе родственности потоков (thread affinity). Хотя каждая из библиотек имеет отдельную реализацию, обе очень похожи по своим функциям.

Объекты, которые создают rich client, основаны главным образом на DependencyObject в случае применения WPF, или на Control в случае Windows Forms. Эти объекты имеют родственность потоков. Это означает, что только поток, который который объект инстанцирует, может впоследствии получить доступ к его членам. Нарушение правила приведет либо к не предсказуемому поведению, либо к выбросу исключения.

Положительно то, что Вам не нужно делать блокировку вокруг доступа к объекту UI. Недостаток же в том, что если нужно вызвать член объекта X, который был создан другим потоком Y, то Вы должны перенаправить (marshal) запрос на вызов объекту Y. Вы явно можете делать это следующим образом:

• В WPF вызовите Invoke или BeginInvoke на элементе объекта Dispatcher.
• В Windows Forms вызовите Invoke или BeginInvoke на элементе управления (control).

Invoke и BeginInvoke оба принимают делегата, который обращается к методу на целевом элементе управления, который Вы хотите запустить. Invoke работает синхронно: вызывающий код блокируется, пока перенаправление (marshal) не завершиться. BeginInvoke работает асинхронно: вызвавший его код немедленно получает обратно управление, и маршалированный запрос ставится в очередь (с использованием той же самой очереди сообщений, которая поддерживает события клавиатуры, мыши и таймера).

Предположим, что у нас есть окно, которое содержит текстовое поле ввода (text box) с именем txtMessage, содержимое которого мы хотим обновлять рабочим потоком. Вот пример для WPF:

Подобный код используется для Windows Forms, за исключением что мы вместо Dispatcher.Invoke вызовем метод Invoke (принадлежащий классу формы Form):

Framework предоставляет две конструкции для упрощения этого процесса:

• BackgroundWorker [16]
• Продолжения для Task [17]

Рабочие потоки против потоков UI. Полезно думать о приложениях rich client, что они имеют две категории потоков: потоки графического интерфейса пользователя (UI threads) и рабочие потоки (worker threads). Потоки UI инстанцируют (и впоследствии «владеют») элементами графического интерфейса UI; рабочие потоки не инстанцируют и не владеют элементами UI. Worker-потоки обычно выполняют длинные вычисления, такие как выборка/получение данных (если бы эти вычисления были короткими, то надобности в рабочих потоках не было бы).

Большинство приложений rich client имеют один поток UI (который также является главным потоком приложения) и этот поток периодически порождает рабочие потоки — либо напрямую, либо с использованием класса BackgroundWorker [16]. Эти рабочие потоки маршалируют свои обращения обратно в главный поток UI, чтобы обновлять состояние органов управления или чтобы сообщать о прогрессе выполнения операции.

Итак, когда у приложения может быть несколько потоков UI? Основной такой сценарий возникает, когда у Вас приложение с несколькими окнами верхнего уровня, что часто называют приложением Single Document Interface (SDI); пример такого приложения Microsoft Word. Каждое окно SDI обычно показывает само себя как отдельное «приложение» на панели задач, и часто работает функционально изолированно от других окон SDI. Путем назначения каждому такому окну своего собственного потока UI, приложение может более отзывчивым.


Immutable-объекты. Не мутируемый (immutable) объект это такой объект, который нельзя изменить — снаружи или внутри. Поля immutable-объекта обычно декларируются как read-only, и они полностью инициализируются в момент конструирования объекта.

Немутируемость это признак функционального программирования, где вместо мутирования объекта Вы создаете новый объект с другими свойствами. LINQ следует этой парадигме. Немутируемость также важна в многопоточности, чтобы избежать проблем с общим записываемым состоянием — путем устранения (или минимизации) записываемых данных.

Один из шаблонов использования немутируемых объектов — инкапсуляция группы связанных полей для минимизации задержек блокировок. Чтобы привести простой пример, предположим, что у нас есть два поля, и мы хотим читать/записывать эти поля атомарно:

Вместо того, чтобы реализовать блокировку вокруг этих полей, мы могли бы определить следующий immutable-класс:

Тогда мы могли бы определить одно поле такого типа на объекте блокировки:

Теперь мы можем читать/записывать значения такого типа без удержания блокировки для большего количества присваиваний, чем одно:

Для чтения объекта сначала получаем копию объекта (в блокировке). Затем можно прочитать его значения без необходимости удерживать блокировку:

Технически последние 2 строки кода потокобезопасны благодаря предшествующей блокировке, выполняющей неявный барьер памяти (см. [7] в 4 части этой документации).

Обратите внимание, что это свободный от блокировки способ обеспечить целостность группы связанных полей. Но это не предотвратит данные от изменения, когда Вы впоследствии работаете с ними — для этого обычно нужна блокировка. В 5 части этой документации мы рассмотрим больше примеров немутируемости для упрощения многопоточности, включая PLINQ [13].

Также можно безопасно назначить новый объект ProgressStatus на основе его предыдущего значения (например, можно «инкрементировать» значение PercentComplete) — без блокировки больше одной строки кода. Фактически мы можем делать это без использования одиночной блокировки через использования явные барьеров памяти Interlocked.CompareExchange и ожидание в цикле (spin-wait). Это продвинутая техника, которую мы опишем позже в секции, посвященной параллельному программированию [3].

[Сигнализация с обработкой ожидания события]

Обработка ожидания события (event wait handle) используется для сигнализации. Это способ обмена состоянием, когда один поток ждет поступления оповещения от другого. Event wait handle это самый простой вариант конструкций сигнализации, и он не связан с событиями C#. Event wait handle доступны через три функции: AutoResetEvent, ManualResetEvent и (из Framework 4.0) CountdownEvent. Первые два основаны на общем классе EventWaitHandle откуда они наследуют весь свой функционал.

Конструкция Назначение Работает между процессами? Загрузка (*)
AutoResetEvent Позволяет потоку однократно разблокироваться, когда будет получен сигнал от другого потока. ДА 1000 нс
ManualResetEvent Позволяет потоку разблокироваться навсегда, когда он получил сигнал от другого потока (до сброса). ДА 1000 нс
ManualResetEventSlim (добавлено в Framework 4.0) 40 нс
CountdownEvent (введено в Framework 4.0) Позволяет потоку разблокироваться, когда он получил заранее определенное количество сигналов. 40 нс
Barrier (добавлено в Framework 4.0) Реализует барьер выполнения потока. 80 нс
Wait и Pulse Позволяет потоку блокироваться до момента удовлетворения пользовательского условия. 120 нс для Pulse

Примечание (*): время, которое тратится на сигнал и ожидание в конструкции на одном и том же потоке (подразумевая, что другие потоки не блокируются), как это было измерено на процессоре Intel Core i7 860.

AutoResetEvent. AutoResetEvent похож на билетный турникет: установка в него билета позволяет пройти через него одному человеку. Префикс auto в имени класса отражает факт, что открытие турникета автоматически закрывается, или сбрасывается (reset) после выполнения через него нескольких шагов. Поток ожидает на турникете, или блокируется, путем вызова WaitOne (ждет этого «one» турникета, пока он открывается), и билет вставляется путем вызова метода Set. Если несколько потоков вызовут WaitOne, то позади турникета растет очередь (как и в случае с блокировками, справедливость первого доступа по отношению к моменту постановки в очередь может иногда нарушаться из-за нюансов реализации операционной системы). Билет может поступить от одного потока; другими словами, любой (не заблокированный) поток с доступом к объекту AutoResetEvent может установить Set на нем для освобождения одного заблокированного потока.

Вы можете создать AutoResetEvent двумя способами. Первый использует его конструктор:

Замечание: передача true в этот конструктор эквивалентно немедленному вызову Set на объекте. Второй способ создает AutoResetEvent следующим образом:

В примере ниже запускается поток, чья работа состоит в простом ожидании сигнала от другого потока:

Пример выведет следующее:

Если Set был вызван, когда нет ни одного потока ожидающего потока, то дескриптор ожидания остается открытым, пока какой-нибудь поток не вызовет WaitOne. Это поведение помогает избежать гонок между потоками в голове очереди турникета при определении потока, вставляющий билет («Упс, билет был вставлен слишком быстро, неудача, теперь нужно ждать неопределенно долго!»). Однако повторяющиеся вызовы Set на турникете, на котором нет ожидания, не даст возможности пройти всей компании потоков: пройдет только один, и все предыдущие «билеты» будут потрачены впустую.

Вызов Reset на AutoResetEvent закрывает турникет (если он открыт) без ожидания или блокировки.

WaitOne принимает не обязательный параметр timeout, и он вернет false если ожидание окончилось по причине истечения таймаута и сигнал не за это время не был получен.

Как только Вы закончили работу с дескриптором ожидания, можете вызвать его метод Close, чтобы освободить ресурсы операционной системы. Альтернативно Вы можете просто бросить все ссылки на дескриптор ожидания и позволить сборщику мусора когда-нибудь позже выполнить работу по утилизации дырок (мусора) в памяти (дескрипторы ожидания реализуют шаблон расформирования, который вызывается через финализирующий метод Close). Это один из нескольких сценариев, где возможно приемлемо полагаться на такое поведение, потому что дескрипторы ожидание слабо загружают операционную систему (асинхронные делегаты [2] полагаются на тот же самый механизм для реализации своего дескриптора ожидания IAsyncResult).

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

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

Решение для главного потока в том, чтобы главный поток ждал, пока рабочий поток не будет готов к приему нового сигнала. Это можно реализовать с другим AutoResetEvent следующим образом:

Вывод этого примера:

В примере использовалось сообщение null, чтобы дать указание рабочему потоку завершиться. С потоками, которые работают в бесконечном цикле, важно предусмотреть стратегию завершения!

Очередь генератор/потребитель. Очередь producer/consumer является общим требованием обмена данными между потоками. Вот как этот работает:

• Настраивается очередь, чтобы описать рабочие элементы, или данные, над которыми осуществляется обработка.
• Когда требуется выполнение задачи, она ставится в очередь, позволяя вызывающему коду выполнять другие действия.
• Один или большее количество потоков работают в фоновом режиме, собирая и обрабатывая поставленные в очередь элементы.

Достоинство этой модели в том, что присутствует прецизионное управление, сколько рабочих потоков может быть запущено одновременно. Это позволяет Вам ограничить не только траты процессорного времени, но и других ресурсов. Например, если задачи выполняют интенсивный дисковый ввод/вывод, у Вас может быть только один рабочий поток, чтобы избежать исчерпание ресурсов операционной системы для других приложений. Другой тип приложения может иметь 20 рабочих потоков. Вы также можете добавлять или удалять рабочие потоки во время во время жизни очереди. Пул потоков CLR сам по себе является разновидностью очереди producer/consumer.

Очередь producer/consumer обычно содержит элементы, над которыми выполняется (одинаковая) обработка. Например, элементами данных могут быть имена файлов, и обработка может шифровать эти файлы.

В примере ниже мы используем один AutoResetEvent для подачи сигнала рабочему потоку, когда он ожидает на пустой очереди (другими словами, ожидание происходит, когда вся работа выполнена). Мы завершим рабочий поток постановкой в очередь null-задачи:

Чтобы гарантировать потокобезопасность, здесь мы используем блокировку для защиты доступа к коллекции Queue . Мы также явно закрываем дескриптор ожидания его методом Dispose, поскольку мы могли потенциально создать и уничтожить множество экземпляров этого класса во время жизни приложения.

Вот метод главного потока, которым тестируется очередь:

Вывод этого примера:

Framework 4.0 предоставляет новый класс BlockingCollection [18], который реализует функционал очереди producer/consumer. Наша написанная вручную очередь producer/consumer все еще актуальна — она не только показывает AutoResetEvent и безопасность потоков, но также является базой для более сложных структур. Например, если Вы хотите получить ограниченную очередь блокировки (с ограничением на количество поставленных в очередь задач), и также хотите поддерживать отмену (и удаление) поставленных в очередь элементов, этот код предоставит отличную начальную точку для программирования. Пример очереди producer/consume будет впоследствии использоваться при обсуждении Wait и Pulse [19].

ManualResetEvent. ManualResetEvent функционирует как обычные ворота. Вызов Set открывает ворота, позволяя любому количеству потоков вызвать WaitOne чтобы пройти через них. Вызов Reset закрывает ворота. Потоки, которые вызвали WaitOne на закрытых воротах, будут заблокированы; когда ворота откроются в следующий раз, они все запустятся одновременно. Кроме этих отличий, ManualResetEvent работает наподобие AutoResetEvent.

С AutoResetEvent Вы можете сконструировать ManualResetEvent двумя способами:

Framework 4.0 предоставил другую версию ManualResetEvent, которая называется ManualResetEventSlim. Она оптимизирована для коротких времен ожидания — с возможностью как опции работать с циклом ожидания на установленное количество итераций. Также это более эффективная управляемая (managed) реализация, позволяющая остановить Wait через CancellationToken [15]. Однако это нельзя использовать для сигнализации между процессами. ManualResetEventSlim не подкласс WaitHandle; однако он предоставляет свойство WaitHandle, которое возвратит основанный на WaitHandle объект, который будет вызван (с профилем производительности традиционного дескриптора ожидания).

Ожидание сигнализации AutoResetEvent или ManualResetEvent занимает около 1 микросекунды (предполагая, что нет блокирования).

ManualResetEventSlim и CountdownEvent (см. ниже) могут быть в 50 раз быстрее для сценариев короткого ожидания, из-за того, что они не полагаются на операционную систему и разумно используют циклы прокрутки.

Однако в большинстве сценариев потери от классов сигнализации сами по себе не создают узкое место. Исключение составляет код с жестким одновременным выполнением, что будет обсуждаться в части 5 (см. [14]) этой документации.

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

CountdownEvent. Позволяет Вам ждать больше одного потока. Этот класс был введен в Framework 4.0, и для него разработана эффективная, полностью управляемая (managed) реализация.

Если Ваша программа работает на предыдущей версии .NET Framework, то не все еще потеряно! Позже мы покажем, как написать аналог CountdownEvent с использованием Wait и Pulse [20].

Для использования CountdownEvent инстанцируйте этот класс с количеством потоков (или счетчиком, count), которые Вы хотите ждать:

Вызов Signal декрементирует count; вызов Wait блокирует поток, пока count не дойдет до 0. Пример:

Проблемы, для которых предназначен CountdownEvent, можно иногда решить проще путем использования конструкций структурированного параллелизма, которые рассматриваются в части 5 [14] (PLINQ и класс Parallel).

Вы можете добавлять увеличение значения для счетчика CountdownEvent вызовом AddCount. Однако если счетчик уже достиг нуля, AddCount выбросит исключение: Вы не можете «отменить» сигнал события CountdownEvent путем вызова AddCount. Чтобы избежать возможности срабатывания исключения, используйте вместо этого другой метод TryAddCount, который вернет false, если счет достиг до 0.

Для отмены сигнала события обратного счета вызовите Reset: это одновременно отменит сигнал конструкции и сбросит счетчик к своему оригинальному значению.

Наподобие ManualResetEventSlim, CountdownEvent публикует свойство WaitHandle для сценариев, где некоторый другой класс или метод ожидает объект, основываясь на WaitHandle.

Создание EventWaitHandle для взаимодействия между процессами. Конструктор EventWaitHandle позволяет создавать «именованный» EventWaitHandle, который может работать между несколькими процессами (чем процесс отличается от потока, см. [2]). Имя это просто строка, и у неё может быть любое значение, которое не содержит нежелательного конфликта с каким-то другим именем! Если это имя уже используется на компьютере, где работают процессы, то Вы получите ссылку на тот же самый нижележащий EventWaitHandle; иначе операционная система создаст новый. Пример:

Если каждое из двух приложений запустят этот код, то они могут обмениваться сигналами друг с другом: дескриптор ожидания (wait handle) может работать на всех потоках обоих процессов.

Дескрипторы ожидания и Thread Pool. Если в Вашем приложении есть несколько потоков, которые тратят большинство своего времени на дескрипторе ожидания (wait handle), то можно уменьшить трату ресурсов вызовом ThreadPool.RegisterWaitForSingleObject. Этот метод принимает делегата, который выполняется, когда прошел сигнал дескриптора ожидания. Пока идет ожидание, это не связывает поток:

Пример выведет следующее:

Когда прошел сигнал на дескриптор ожидания (или когда истек таймаут), делегат запустится на потоке пула.

В дополнение к дескриптору ожидания и делегату RegisterWaitForSingleObject принимает объект «черного ящика», который передается Вашему методу делегата (наподобие ParameterizedThreadStart), а также таймаут в миллисекундах (–1 означает ожидание без таймаута) и bool-флаг, показывающий, однократный ли это запрос или повторяющийся.

RegisterWaitForSingleObject в частности важен в сервере приложения, который должен обрабатывать множество одновременных запросов. Предположим, что Вам нужно блокировать выполнение на ManualResetEvent и просто ждать WaitOne:

Если 100 клиентов вызовут этот метод, то 100 потоков сервера были бы заняты на время блокирования. Замена _wh.WaitOne на RegisterWaitForSingleObject позволяет методу выполнить немедленный возврат, не теряя потоки:

Объект данных, переданный в Resume, позволяет продолжить обработку любых текущих данных.

WaitAny, WaitAll и SignalAndWait. В дополнение к методам Set, WaitOne и Reset это статические методы класса WaitHandle, решающие более сложные задачи синхронизации. Методы WaitAny, WaitAll и SignalAndWait выполняют операции сигнализации и ожидания на нескольких дескрипторах. Дескрипторы ожидания могут быть разных типов (включая Mutex и Semphore, поскольку они также выводятся из абстрактного класса WaitHandle). ManualResetEventSlim и Countdown также могут принять участие в этих методах через их свойства WaitHandle.

WaitAll и SignalAndWait имеют странное соединение с устаревшей (legacy) архитектурой COM: эти методы требуют, чтобы вызывающая сторона была в многопоточном окружении — модель, меньше всего подходящая для функциональной совместимости. Главный поток приложения WPF или Windows Forms, например, в этом режиме не может взаимодействовать с буфером обмена (clipboard). Мы кратко рассмотрим альтернативы ниже.

WaitHandle.WaitAny ждет любого из массива дескрипторов ожидания; WaitHandle.WaitAll атомарно ждет всех имеющихся дескрипторов. Это означает следующее, если Вы ждете на двух AutoResetEvents:

• WaitAny никогда не закончится «защелкиванием» обоих событий.
• WaitAll никогда не закончится «защелкиванием» только одного события.

SignalAndWait вызовет Set на одном WaitHandle, и затем вызовет WaitOne на другом WaitHandle. После сигнализации первого дескриптора произойдет переход на начало очереди в ожидании второго дескриптора; это помогает ему успешно выполниться (хотя операция не будет реально атомарной). Вы можете думать про этот метод как «замену» одного сигнала на другой, и использование его на паре EventWaitHandles, чтобы установить два потока на «встречу» в одном моменте времени. Этот трюк выполнит AutoResetEvent или ManualResetEvent. Первый поток выполнит следующее:

В то же время другой поток выполнит противоположное:

Альтернативы WaitAll и SignalAndWait. WaitAll и SignalAndWait не будут работать в одном потоке. К счастью, есть альтернативы. В случае SignalAndWait редко когда надо использовать иго семантику перехода по очереди: в нашем примере «встречи» было бы допустимо просто вызывать Set на первом дескрипторе ожидания, и затем вызвать WaitOne на другом, если бы дескрипторы ожидания использовались только для встречи. В классе Barrier [6] мы рассмотрим другой вариант для реализации встречи потоков.

В случае WaitAll при некоторых ситуация альтернативой будет использование метода Invoke класса Parallel, который будет рассматриваться в части 5 [14]. Также мы рассмотрим продолжение задачи и продолжения (Tasks и continuations), и посмотрим, как TaskFactory из ContinueWhenAny предоставляет альтернативу для WaitAny.

Во всех других сценариях ответом будет низкоуровневый подход, который решает все проблемы сигнализации: Wait и Pulse [5].

[Контексты синхронизации]

Альтернативой для ручной блокировки является блокировка декларативная. Путем наследования из ContextBoundObject и применения атрибута Synchronization Вы инструктируете библиотеку CLR применить блокировку автоматически. Пример:

Результат работы этого примера:

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

Как это работает? Подсказка находится в атрибуте пространства имен Synchronization: System.Runtime.Remoting.Contexts. ContextBoundObject можно рассматривать как «remote» (дальний) объект, что означает перехват всех его вызовов. Чтобы этот перехват был возможен, когда мы инстанцируем AutoLock, CLR в действительности вернет прокси — объект с теми же методами и свойствами, что и объект AutoLock, который работает как промежуточный. Именно через это и происходит автоматическая блокировка. В целом перехват занимает около микросекунды для каждого вызова метода.

Автоматическая синхронизация не может использоваться ни для защиты статических членов типа, ни для классов, которые не были унаследованы от ContextBoundObject (например, Windows Form).

Блокировка применяется внутри точно так же. Вы можете ожидать, что следующий пример выведет тот же самый результат, как и предыдущий пример:

Обратите внимание, что здесь вставлен оператор Console.ReadLine. Поскольку только один поток может выполнить код в любой момент времени в объекте этого класса,, то три новых потока останутся заблокированными в методе Demo, пока метод Test не завершится, это потребовало для завершения ReadLine. В результате мы получили тот же результат, что и ранее, но только после нажатия на клавишу Enter. Это хороший метод потокобезопасности, подходящий для устранения проблем любой полезной многопоточности в классе.

Далее, мы не решили проблему, описанную ранее: если бы AutoLock был классом коллекции, например, мы все еще нуждались в блокировке вокруг оператора наподобие следующего, подразумевая, что он запущен из другого класса (если классом этого кода не был самостоятельно синхронизируемый ContextBoundObject):

Контекст синхронизации может быть расширен вне области действия одного объекта. По умолчанию, если синхронизируемый объект инстанцирован из кода другого объекта, то оба они используют один и тот же контекст (другими словами, одну большую блокировку!). Это поведение можно поменять указанием целочисленного флага в конструкторе атрибута Synchronization, используя константы, определенные в классе SynchronizationAttribute:

Константа Назначение
NOT_SUPPORTED Эквивалентно не использованию атрибута Synchronized.
SUPPORTED Подсоединяется к существующему контексту синхронизации, если инстанцирован из другого объекта синхронизации, иначе остается не синхронизированным.
REQUIRED (по умолчанию) Подсоединяется к существующему контексту синхронизации, если инстанцирован из другого объекта синхронизации, иначе создает новый контекст.
REQUIRES_NEW Всегда создает новый контекст синхронизации.

Таким образом, если объект класса SynchronizedA инстанцирует объект класса SynchronizedB, они получат отдельные контексты синхронизации, если SynchronizedB был декларирован так:

Чем больше область действия контекста синхронизации, тем проще им управлять, но тем менее это полезно для параллелизма. Кроме того, отдельные контексты синхронизации вводят deadlock-и. Пример:

Поскольку каждый экземпляр Deadlock создан внутри Test — не синхронизированном классе — каждый экземпляр получает свой собственный контекст синхронизации, и таким образом собственную блокировку. Когда два объекта вызывают друг друга, у deadlock займет много времени (если быть точным, то 1 секунду). Проблема была бы особенно коварной, если бы классы Deadlock и Test были бы написаны разными командами программистов. Это в отличие от явных блокировок, где deadlock-и обычно более очевидны.

Реентрантность. Потокобезопасный метод иногда называют реентрантным (повторно входимым), потому что он может быть безопасно вытеснен в любой части своего выполнения тем же самым методом, и затем вызван снова в другом потоке без какого-либо вредного влияния. В общем смысле условия, ориентированные на безопасное многопоточное выполнение и реентрантность рассматривают либо как синонимы, либо как связанные друг с другом понятия.

У реентрантности есть однако более зловещий оттенок в автоматических режимах блокировки. Если атрибут Synchronization примененный с аргументом реентрантности, равен true:

то блокировка контекста синхронизации будет временно освобождена, когда выполнение покинет этот контекст. В предыдущем примере это препятствовало бы возникновению deadlock, что очевидно было бы желательно. Однако побочный эффект состоит в том, что во время этого промежуточного периода любой поток может вызвать любой метод оригинального объекта (повторно войти в контекст синхронизации, «re-entering»), в результате произойдут все сложности многопоточного выполнения, которых стараются избежать в первую очередь. Это проблема реентрантности.

Из-за того, что [Synchronization(true)] применяется на уровне класса, этот атрибут превращает любой метод, выходящий из контекста, в троянского коня для реентрантности.

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

Это высвечивает фундаментальную уязвимость автоматической синхронизации: расширенная область, к которой применена блокировка, может на самом деле вводить трудности, которые иначе могли и не возникать. К этим сложностям относятся deadlock, реентрантность и урезанный параллелизм выполнения, тогда ручная блокировка может быть более приемлемой не только для простых сценариев.

32 подводных камня OpenMP при программировании на Си++

Аннотация

С распространением многоядерных систем задача параллельного программирования становится все более и более актуальной. Данная область, однако, является новой даже для большинства опытных программистов. Существующие компиляторы и анализаторы кода позволяют находить некоторые ошибки, возникающие при разработке параллельного кода. Многие ошибки никак не диагностируются. В данной статье приводится описание ряда ошибок, приводящих к некорректному поведению параллельных программ, созданных на основе технологии OpenMP.

Введение

Параллельное программирование появилось уже достаточно давно. Первый многопроцессорный компьютер был создан еще в 60-х годах прошлого века. Однако до недавних пор прирост производительности процессоров обеспечивался в основном благодаря росту тактовой частоты, и многопроцессорные системы были редкостью. Сейчас рост тактовой частоты замедляется, и прирост производительности обеспечивается за счет использования нескольких ядер. Многоядерные процессоры приобретают широкое распространение, и в связи с этим задача написания параллельных программ приобретает все большую и большую актуальность. Если ранее для увеличения производительности программы пользователь мог просто установить процессор с большей тактовой частотой и большим кешем, то теперь такой подход невозможен и существенное увеличение производительности в любом случае потребует усилий от программиста.


В связи с тем, что параллельное программирование начинает набирать популярность только сейчас, процесс распараллеливания существующего приложения или написания нового параллельного кода может вызвать проблемы даже для опытных программистов, так как данная область является для них новой. Существующие компиляторы и анализаторы кода позволяют диагностировать лишь некоторые из возможных ошибок. Остальные ошибки (а таких большинство) остаются неучтенными и могут существенно увеличить время тестирования и отладки, особенно с учетом того, что такие ошибки почти всегда воспроизводятся нестабильно. В данной статье рассматривается язык Си++, поскольку к коду именно на этом языке чаще всего предъявляются требования высокой производительности. Так как поддержка технологии OpenMP встроена в Microsoft Visual Studio 2005 и 2008 (заявлено соответствие стандарту OpenMP 2.0), мы будем рассматривать именно эту технологию. OpenMP позволяет с минимальными затратами переделать существующий код — достаточно лишь включить дополнительный флаг компилятора /openmp и добавить в свой код соответствующие директивы, описывающие, как именно выполнение программы будет распределено на несколько процессоров.

В данной статье рассматриваются далеко не все ошибки, которые могут возникнуть при программировании на Си++ с использованием OpenMP и не диагностируются при этом компилятором или существующими статическими или динамическими анализаторами кода. Тем не менее, хочется надеяться, что приведенный материал поможет лучше понять особенности разработки параллельных систем и избежать множества ошибок.

Также стоит отметить, что данная статья носит исследовательский характер, и ее материал послужит при разработке статического анализатора VivaMP, предназначенного для поиска ошибок в параллельных программах, создаваемых на основе технологии OpenMP. Мы будем рады получить отзыв о статье и узнать новые паттерны параллельных ошибок.

По аналогии с одной из использованных статей [1] ошибки в данной статье разделены на логические ошибки и ошибки производительности. Логические ошибки это ошибки, приводящие к неожиданным результатам, то есть к некорректной работе программы. Под ошибками производительности понимаются ошибки, приводящие к снижению быстродействия программы.

Прежде чем перейти к рассмотрению конкретных ошибок, определим некоторые специфические термины, которые будут использоваться в этой статье:

Директивами (directives) назовем собственно директивы OpenMP, определяющие способ распараллеливания кода. Все директивы OpenMP имеют вид #pragma omp .

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

Параллельной секцией (section) назовем фрагмент кода, на который распространяется действие директивы #pragma omp parallel.

Данная статья предполагает, что читатель уже знаком с основами OpenMP и собирается применять эту технологию в своих программах. Если же читатель еще не знаком с OpenMP, для первоначального знакомства можно посмотреть документ [2]. Более подробное описание директив, выражений, функций и глобальных переменных OpenMP можно найти в спецификации OpenMP 2.0 [3]. Также эта спецификация продублирована в справочной системе MSDN Library, в более удобной форме, чем формат PDF.

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

Логические ошибки

1. Отсутствие /openmp

Начнем с самой простейшей ошибки: если поддержка OpenMP не будет включена в настройках компилятора, директивы OpenMP будут попросту игнорироваться. Компилятор не выдаст ни ошибки, ни даже предупреждения, код просто будет выполняться не так, как этого ожидает программист.

Поддержку OpenMP можно включить в диалоговом окне свойств проекта (раздел «Configuration Properties | C/C++ | Language»).

2. Отсутствие parallel

Директивы OpenMP имеют достаточно сложный формат, поэтому сначала рассмотрим простейшие ошибки, которые могут возникнуть при неправильном написании самих директив. Ниже приведены примеры корректного и некорректного кода:

Первый фрагмент кода успешно скомпилируется, и директива #pragma omp for будет попросту проигнорирована компилятором. Таким образом, цикл, вопреки ожиданиям программиста, будет выполняться только одним потоком, и обнаружить это будет достаточно затруднительно. Помимо директивы #pragma omp parallel for, эта ошибка может возникнуть и с директивой #pragma omp parallel sections.

3. Отсутствие omp

Ситуация, аналогичная предыдущей, возникнет, если в директиве OpenMP не написать ключевое слово omp [4]. Рассмотрим простой пример.

При выполнении этого кода сообщение «me» будет выведено два раза вместо ожидаемого одного. При компиляции компилятор выдаст предупреждение: «warning C4068: unknown pragma». Однако предупреждения могут быть отключены в настройках проекта, либо предупреждение может быть проигнорировано программистом.

4. Отсутствие for

Директива #pragma omp parallel может относиться как к блоку кода, так и к одной команде. В случае цикла for это может приводить к неожиданному поведению:

Если программист хотел распределить выполнение этого цикла на два потока, ему следовало использовать директиву #pragma omp parallel for. В этом случае цикл выполнился бы 10 раз. Однако, при запуске приведенного выше кода цикл будет выполняться по одному разу в каждом потоке, и вместо ожидаемых 10 раз функция myFunc будет вызвана 20 раз. Исправленная версия кода должна выглядеть следующим образом:

5. Ненужное распараллеливание

Применение директивы #pragma omp parallel к большому участку кода при невнимательности программиста может вызывать неожиданное поведение, аналогичное предыдущему случаю:

В силу забывчивости или неопытности программист, желающий распределить выполнение цикла на два потока, написал слово parallel внутри секции кода, уже распределенного на два потока. В результате выполнения этого кода функция myFunc, как и в предыдущем примере, будет выполнена 20 раз, вместо ожидаемых 10 раз. Исправленный код должен выглядеть так:

6. Неправильное применение ordered

Применение директивы ordered может вызвать проблемы у начинающих программистов, не слишком хорошо знакомых с OpenMP [1]. Приведем пример кода:

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

7. Переопределение количества потоков внутри параллельной секции

Перейдем к рассмотрению более сложных ошибок, которые могут возникнуть при недостаточном знании стандарта OpenMP. Согласно спецификации OpenMP 2.0 [3], количество потоков нельзя переопределять внутри параллельной секции. В Си++ это приводит к ошибкам во время выполнения программы и ее аварийному завершению. Пример:

8. Попытка использовать блокировку без инциализации переменной

Согласно спецификации OpenMP 2.0 [3], переменные, использующиеся для блокировки, необходимо инциализировать перед использованием, вызвав функцию omp_init_lock или omp_init_nest_lock (в зависимости от типа переменной). В С++ попытка использования (установка блокировки, снятие блокировки, проверка блокировки) неинициализированной переменной приводит к ошибке во время выполнения программы.

9. Попытка снять блокировку не из того потока, который ее установил

Если блокировка установлена одним потоком, попытка ее снятия из другого потока может привести к непредсказуемым результатам [3]. Рассмотрим пример:

В Си++ этот код приводит к ошибке во время выполнения программы. Поскольку операции установки и снятия блокировки по сути аналогичны входу в критическую секцию и выходу из нее, каждый из использующих блокировку потоков должен выполнять обе операции. Корректная версия кода будет выглядеть следующим образом:

10. Попытка использования блокировки как барьера

Функция omp_set_lock блокирует выполнение потока до тех пор, пока переменная, использующаяся для блокировки, не станет доступна, то есть до тех пор, пока тот же самый поток не вызовет функцию omp_unset_lock. Следовательно, как уже говорилось в описании предыдущей ошибки, каждый поток должен содержать вызовы обеих функций. Однако, начинающий программист, недостаточно хорошо понимающий принципы работы OpenMP, может попытаться использовать функцию omp_set_lock в качестве барьера, то есть вместо директивы #pragma omp barrier (эту директиву нельзя использовать внутри параллельных секций, к которым применяется директива #pragma omp sections). В результате возникнет следующий код.

В результате выполнения этого фрагмента кода программа иногда будет зависать, а иногда — выполняться нормально. Зависеть это будет от того, какой поток завершается последним. Если последним будет завершаться поток, в котором выполняется блокировка переменной без ее освобождения, программа будет выдавать ожидаемый результат. Во всех остальных случаях будет возникать бесконечное ожидание освобождения переменной, захваченной потоком, работающим с переменной некорректно. Аналогичная ситуация будет возникать и при использовании функции omp_test_lock в цикле (а именно так эту функцию обычно и используют). В этом случае поток будет бесконечно «топтаться на месте», так и не дождавшись освобождения переменной.

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

11. Зависимость поведения от количества потоков

Количество параллельных потоков, создаваемых при выполнении приложения, в общем случае не является постоянной величиной. По умолчанию оно, как правило, равняется числу установленных на компьютере процессоров. Однако, число потоков может также задаваться программистом вручную (например, с помощью функции omp_set_num_threads, или выражения num_threads, которое имеет больший приоритет, чем эта функция). Помимо указанной функции и выражения существует еще и переменная среды OMP_NUM_THREADS, имеющая наименьший приоритет. Следовательно, число потоков является весьма ненадежным числом, к тому же значение этого числа по умолчанию может оказаться разным на разных компьютерах. Поведение вашего кода ни в коем случае не должно зависеть от количества выполняющих его потоков, если только вы не уверены до конца в том, что вам это действительно нужно.Рассмотрим пример некорректного кода, взятый из статьи [5]. Приведенная ниже программа должна по замыслу программиста вывести на экран все буквы английского алфавита.Некорректно:

На практике, однако, будет выведено только 24 буквы из 26. Причина проблемы заключается в том, что 26 (число букв) делится на 4 (число потоков) с остатком. Следовательно, оставшиеся две буквы не будут выведены на экран. В качестве исправления можно либо отказаться от использования количества потоков в вычислениях и переписать код иначе, либо распределить вычисления на корректное число потоков (например, 2). Допустим, программист решил отказаться от использования количества потоков в своих вычислениях и возложить распределение работы между потоками на компилятор. В этом случае исправленная версия кода будет иметь следующий вид.Корректно:

Все итерации будут гарантированно выполнены. Если необходимо задать способ распределения итераций между потоками, можно воспользоваться выражением schedule. Распределением работы между потоками теперь занимается компилятор, и он не забудет про две «лишние» итерации. К тому же, код оказался намного короче и понятнее.

12. Некорректное использование динамического создания потоков

В OpenMP слово dynamic встречается в двух контекстах: в выражении schedule(dynamic) и в переменной среды OMP_DYNAMIC, что вносит некоторую путаницу. Важно понимать разницу между этими двумя случаями и не считать, что выражением schedule(dynamic) можно пользоваться, только если переменная OMP_DYNAMIC имеет значение true. На самом деле эти случаи никак друг с другом не связаны.

Выражение schedule(dynamic) означает, что поделенные на куски (chunks) итерации цикла будут распределяться между потоками динамически — освободившись, поток будет брать следующую «порцию». В частности, в предыдущем примере это означало бы, что каждый из четырех потоков выведет по 6 букв, после чего тот поток, который освободится первым, выведет последние 2 буквы.

Переменная OMP_DYNAMIC задает возможность динамического определения числа потоков компилятором. Проблема заключается в том, что эта переменная имеет больший приоритет, чем даже выражение num_threads. Следовательно, если выполнение кода как-то зависит от количества выполняющих его потоков, поведение может стать некорректным, и это — еще один аргумент в пользу того, чтобы не писать зависящий от количества потоков код.Опыт показывает, что в Visual Studio 2008 переменная OMP_DYNAMIC по умолчанию имеет значение false. Однако, нет никаких гарантий, что это не изменится в будущем. В спецификации OpenMP [3] сказано, что значение этой переменной зависит от конкретной реализации. Следовательно, если в предыдущем примере программист решил пойти по легкому пути и все же использовать в своих вычислениях число потоков, вместо того, чтобы переписывать код, ему следует позаботиться о том, что это число потоков будет именно таким, как он указал. В противном случае на четырехпроцессорной машине код начнет работать некорректно.

13. Одновременное использование общего ресурса

Если бы в предыдущем примере вывод производился не по одной букве в произвольном порядке, а хотя бы по две, проявилась бы еще одна проблема параллельного программирования — одновременное использование общего ресурса (которым в данном случае является консольное окно). Рассмотрим пример.

Вопреки ожиданиям программиста, на двухпроцессорной машине этот код, скорее всего, выведет нечто вроде следующих двух строчек:

Причина такого поведения заключается в том, что операция вывода строки на экран не является атомарной. Следовательно, два потока будут выводить свои символы одновременно. Та же самая ситуация возникнет при использовании стандартного потока вывода cout, а также любого другого объекта, доступного обоим потокам.

Если возникает необходимость выполнить какое-либо действие, изменяющее состояние такого объекта, из двух потоков, необходимо позаботиться о том, чтобы это действие выполнялось только одним из потоков в каждый момент времени. Для этого можно использовать директиву critical, или блокировку (о том, что именно предпочтительнее с точки зрения производительности, будет рассказано ниже).

14. Незащищенный доступ к общей памяти

Эта ошибка описана в статье [1]. По своей сути она аналогична предыдущей — если несколько потоков одновременно изменяют значение переменной, результат может быть непредсказуемым. Однако эта ошибка все же рассматривается отдельно от предыдущей, потому что в этом случае решение будет несколько иным. Поскольку операция над переменной может быть атомарной, в целях оптимизации быстродействия лучше использовать директиву atomic. Подробные рекомендации по поводу того, какой именно способ лучше использовать для защиты общей памяти, будут приведены ниже.

Еще одно возможное решение — использовать выражение reduction. В этом случае каждый поток получит собственную копию переменной a, выполнит с ней все необходимые действия, а затем произведет указанную операцию, чтобы объединить получившиеся значения с исходным.

При таком изменении кода в случае двух потоков будет выведена строка «a=2».

15. Использование директивы flush с указателем

Директива flush служит для того, чтобы потоки обновили значения общих переменных. Например, если один поток установил значение доступной обоим потокам общей переменной а, равное 1, это не гарантирует, что другой поток, обратившись к той же переменной, получит значение 1. Еще раз подчеркнем, что данная директива обновляет именно значения переменных. Если в коде имеется доступный обоим потокам указатель на какой-либо объект, вызов директивы flush обновит только значение этого указателя, но не состояние объекта. Более того, в стандарте OpenMP [3] явно сказано, что переменная-аргумент директивы flush не должна быть указателем.

На самом деле этот код содержит две ошибки — уже упоминавшуюся ранее одновременную работу с общим объектом и использование flush с указателем. Следовательно, если метод myFunc изменяет состояние объекта, результат выполнения этого кода будет непредсказуемым. Для того, чтобы исправить эти ошибки, достаточно избавиться от одновременного использования общего объекта. Дело в том, что директива flush неявно выполняется при входе в критическую секцию и при выходе из нее (об этом будет подробнее рассказано позднее).

16. Отсутствие директивы flush

Согласно спецификации OpenMP [3], эта директива неявно выполняется во многих случаях (полный список этих случаев будет приведен ниже, в описании одной из ошибок производительности). Понадеявшись на это, программист может не использовать эту директиву там, где она действительно необходима. Директива flush не выполняется в следующих случаях:

  • При входе в параллельную секцию директивы for.
  • При входе и при выходе из секции директивы master.
  • При входе в параллельную секцию директивы sections.
  • При входе в секцию директивы single.
  • При выходе из секции директивы for, single или sections, если к директиве применено выражение nowait (вместе с неявным барьером эта директива убирает и неявную директиву flush).

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

17. Отсутствие синхронизации

Помимо необходимости применения директивы flush, программист должен помнить еще и о синхронизации потоков, не полагаясь при этом на OpenMP.

Исправленная версия кода из предыдущего примера отнюдь не гарантирует, что в консольное окно будет выведено число «2». Да, выполняющий секцию поток выведет значение переменной а, актуальное на момент вывода. Однако, нет никакой гарантии того, что потоки войдут в секцию single одновременно. В общем случае может быть взято как значение «1», так и «2». Такое поведение вызвано отсутствием синхронизации потоков. Директива single означает лишь то, что соответствующая секция должна быть выполнена одним потоком. А этим потоком с равной вероятностью может оказаться и тот, который завершился первым. Тогда на экран будет выведена цифра «1». Аналогичная ошибка описана в статье [6].

Неявная синхронизация потоков в виде директивы barrier выполняется только при выходе из секции директивы for, single или sections, если к директиве не применено выражение nowait, которое отменяет неявную синхронизацию. Во всех остальных случаях программист должен заботиться о синхронизации сам.

Эта версия кода является полностью корректной — на экран всегда будет выведена цифра «2». Отметим, что в этой версии кода директива flush отсутствует — она неявно включена в директиву barrier.

Теперь рассмотрим еще один весьма интересный пример отсутствия синхронизации, взятый из MSDN [7].

Проблема здесь заключается в том, что при завершении параллельной секции не делается синхронизация. В результате, на момент завершения процесса некоторые из потоков могут еще существовать, и они не получат извещения о том, кто процесс завершен. Реально деструктор для переменной threaded_var будет вызван только в главном потоке. Поскольку эта переменная является параметром директивы threadprivate, ее копии, созданные в других потоках, не будут уничтожены, и возникнет утечка памяти. Чтобы этого избежать, необходимо реализовать синхронизацию вручную.

18. Внешняя переменная задана как threadprivate не во всех модулях

Начиная с этой ошибки, мы переходим к самому неприятному виду ошибок — к ошибкам, связанным с моделью памяти OpenMP. В принципе, ошибки, связанные с одновременным доступом к общим переменным, тоже можно было бы отнести к этой категории, поскольку они касаются переменных, являющихся аргументами выражения shared (все глобальные переменные в OpenMP считаются shared по умолчанию).

Прежде чем перейти к рассмотрению конкретных ошибок отметим, что практически все они, так или иначе, связаны с переменными, являющимися параметрами выражения private (а также его вариаций — директивы threadprivate и выражений firstprivate и lastprivate). Большинство этих ошибок можно избежать, если отказаться от директивы threadprivate и выражения private, и вместо этого просто объявлять соответствующие переменные как локальные переменные в параллельных секциях.

Теперь, когда вы предупреждены, перейдем к рассмотрению конкретных ошибок. Начнем с директивы threadprivate. Эта директива применяется, как правило, к глобальным переменным, в том числе и к внешним переменным, объявленным в другом модуле. В этом случае директива должна быть применена к переменной во всех модулях, в которых она встречается. Это правило описано в уже упомянутой выше статье MSDN [7].

Частным случаем этого правила является другое правило, приведенное в той же статье: директиву threadprivate нельзя применять к переменным, объявленным в динамически подключаемой библиотеке, которая будет загружаться с помощью функции LoadLibrary или ключа линковщика /DELAYLOAD (в этом случае функция LoadLibrary используется неявно).

19. Неинициализированные локальные переменные

При входе в поток для переменных, являющиеся параметрами директивы threadprivate, а также выражений private и lastprivate, создаются локальные копии. Эти копии являются неинициализированными по умолчанию. Следовательно, любая попытка работы с ними без предварительной инициализации приведет к ошибке во время выполнения программы.

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

20. Забытая директива threadprivate

Поскольку директива threadprivate применяется к переменной лишь единожды, и обычно она используется для глобальных переменных, объявленных в начале модуля, про нее легко забыть — например, когда возникает необходимость что-то изменить в большом модуле, созданном полгода назад. В результате глобальная переменная, вопреки ожиданиям программиста, может оказаться не общей, как должно быть по умолчанию, а локальной для потока. Согласно спецификации OpenMP [3], значения таких переменных после соответствующей параллельной секции являются непредсказуемыми.

Поведение приведенной выше программы будет полностью соответствовать документации — иногда в консольное окно будет выводиться число «6» — то самое значение, которое ожидает программист, а иногда — «0», что, в принципе, более логично, так как именно это значение было присвоено переменной до входа в параллельную секцию. Теоретически такое же поведение должно наблюдаться, если вместо директивы threadprivate режим доступа к переменной «а» будет определяться выражениями private или firstprivate. Но на практике с компилятором среды Visual Studio 2008 описанное поведение удалось воспроизвести только с директивой threadprivate, именно поэтому этот пример и приведен в данной статье. К тому же такой вариант наиболее вероятен. Тем не менее, это не означает, что в других реализациях поведение будет корректным, поэтому следует учитывать и другие два варианта.

К сожалению, посоветовать хорошее решение в данном случае трудно, так как отказ от директивы threadprivate изменит поведение кода в других участках программы, а передать переменную, указанную в этой директиве, в выражение shared нельзя по правилам синтаксиса OpenMP. Единственное, что можно посоветовать в этой ситуации — использовать другую переменную.

В этой версии кода переменная «a» как бы становится общей на время выполнения определенной параллельной секции. Конечно, это решение не является лучшим, но за то оно гарантирует, что старый код не изменит своего поведения.

В общем случае начинающим программистам рекомендуется использовать выражение default(none), которое заставит явно указывать режим доступа ко всем используемым в параллельной секции переменным. Это, конечно, потребует написания большего количества кода, но в результате удастся избежать многих ошибок, к тому же код станет более понятным.

21. Забытое выражение private

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

На первый взгляд может показаться, что эта ошибка эквивалентна предыдущей, но это не так. В предыдущем случае вывод производился после параллельной секции, а здесь значение переменной берется внутри параллельной секции. В результате, если значение переменной перед циклом равно нулю, в случае двухпроцессорной машины, вместо ожидаемого числа «10» в консольное окно будет выведено число «5», потому что работа будет разделена пополам между потоками. Следовательно, каждый поток увеличит свое локальное значение переменной a лишь пять раз вместо ожидаемых десяти раз. Более того, значение переменной, получается, будет зависеть от количества потоков, выполняющих код параллельной секции. Кстати, эта ошибка возникнет и в случае использования выражения firstprivate вместо private.

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

22. Некорректное распараллеливание работы с локальными переменными

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

В данном случае программист хотел увеличить значение локальной копии переменной в каждом из потоков на 101 и для этого использовал директиву sections. Однако, поскольку в директиве отсутствовало слово parallel, дополнительного распараллеливания не произошло. Работа распределилась на те же потоки. В результате на двухпроцессорной машине один поток выведет «1», а другой выведет «100». При большем количестве потоков результаты будут еще более неожиданными для программиста. Отметим, что если бы переменная «а» не была локальной (private), такой код был бы вполне корректным. Однако в случае локальной переменной секции необходимо распараллелить дополнительно.

23. Неосторожное применение lastprivate


Напомним, что эта директива после параллельной секции присваивает переменной значение из лексически последней секции, либо из последней итерации цикла. Согласно спецификации, если переменной не присваивается значение в упомянутом фрагменте кода, ее значение после окончания соответствующей параллельной секции является неопределенным. Рассмотрим пример, аналогичный предыдущему.

Такой код теоретически может привести к ошибке. На практике это воспроизвести не удалось. Однако, это не значит, что ошибка не возникнет никогда.

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

24. Непредсказуемые значения threadprivate-переменных в начале параллельных секций

Эта ошибка описана в спецификации OpenMP [3]. Если изменить значение переменной, объявленной как threadprivate, начальное значение переменной в параллельной секции окажется непредсказуемым.

К сожалению, пример, приведенный в спецификации, не компилируется в Visual Studio, потому что компилятор этой среды не поддерживает динамическую инициализацию переменных, фигурирующих в директиве threadprivate. Поэтому приведем свой собственный, менее сложный, пример.

В результате выполнения этого кода один из потоков выведет значение 5, а другой выведет 10. Если убрать инициализацию переменной а до директивы threadprivate, один из потоков начнет выводить 0, а второй — по-прежнему 10. Избавиться от непредсказуемого поведения удастся лишь убрав второе присваивание. В этом случае оба потока будут выводить значение 5 (если первое присваивание все же оставить). Конечно, такие исправления изменят поведение кода. Они описаны здесь лишь для того, чтобы более четко показать поведение OpenMP в данном случае. Вывод здесь может быть только один: никогда не полагайтесь на компилятор в вопросах инициализации локальных переменных. В случае private и lastprivate попытка использования неинициализированных переменных вызовет уже описанную ранее ошибку во время выполнения программы, которую, по крайней мере, можно относительно легко локализовать. Но директива threadprivate, как видите, может давать непредсказуемые результаты без всяких ошибок. Вообще от использования этой директивы лучше всего отказаться. В этом случае код станет намного более предсказуемым и понятным.

25. Некоторые ограничения локальных переменных

В спецификации OpenMP приведено множество ограничений, касающихся локальных переменных. Некоторые из этих ограничений проверяются компилятором автоматически, однако, есть и такие, которые не проверяются:

  • Переменная в выражении private не должна иметь ссылочный тип.
  • Если переменная в выражении lastprivate является экземпляром класса, в этом классе должен быть определен конструктор копирования.
  • Переменная в выражении firstprivate не должна иметь ссылочный тип.
  • Если переменная в выражении firstprivate является экземпляром класса, в этом классе должен быть определен конструктор копирования.
  • Переменная в выражении threadprivate не должна иметь ссылочный тип.

Фактически, это два требования: а) переменная не должна быть указателем б) если переменная является экземпляром класса, для нее должен быть определен конструктор копирования. Причины этих ограничений вполне очевидны — если переменная будет указателем, каждый поток получит по локальной копии этого указателя, и в результате все потоки будут работать через него с общей памятью. Ограничение насчет конструктора копирования тоже весьма логично — если в классе имеется поле, хранящее ссылку, корректно скопировать такой объект почленно не получится и в результате все потоки будут, опять же, работать с той же самой памятью.

Пример в данном случае займет много места и вряд ли необходим. Достаточно лишь запомнить общее правило. Если требуется создать локальную копию объекта, массива или какой бы то ни было области памяти, адресуемой по ссылке, то соответствующая ссылка должна оставаться общей переменной. Делать ее локальной бессмысленно. Содержимое памяти нужно либо копировать явно, либо (в случае объектов) доверить это компилятору, который использует конструктор копирования.

26. Локальные переменные не помечены как таковые

Данная ошибка описана в статье [1]. Суть ее заключается в том, что переменная, которая по замыслу программиста должна была быть локальной, не была помечена как локальная и, следовательно, используется как общая, поскольку этот режим доступа применяется ко всем переменным по умолчанию.

Для диагностики этой ошибки рекомендуется уже упоминавшееся выше использование выражения default(none).

Как видно, данная ошибка весьма обобщенная, и привести конкретный пример достаточно трудно. Однако, в одной из статьей [9] описана ситуация, в которой эта ошибка проявляется вполне явно.

Смысл программы очень прост — массив записей с двумя полями заполняется из двух потоков. Один поток заполняет одно поле записей, другой — другое. Потом делается проверка — все ли записи заполнены правильно.

Ошибка здесь заключается в том, что в цикле для счетчика используется общая переменная i. В результате при выполнении программы в некоторых случаях будет выводиться сообщение «OpenMP Error!», в других — возникать ошибка access violation, и лишь изредка будет выводиться «OK!». Для того, чтобы исправить эту ошибку, достаточно объявить переменную-счетчик как локальную переменную.

Мастер Йода рекомендует:  Подготовка к интервью на Front-end разработчика

В статье [1] имеется аналогичный пример, касающийся именно циклов for (он выделен как отдельная ошибка). Там сказано, что переменная-счетчик для цикла for, к которому применяется директива OpenMP for, должна быть объявлена как локальная. С первого взгляда может показаться, что там рассматривается абсолютно такая же ситуация, однако, это не так.

Дело в том, что, согласно станадрту OpenMP, переменная, использующаяся в качестве счетчика в цикле, неявно преобразуется из общей в локальную, даже если она является параметром выражения shared. Компилятор, делая это преобразование, не выдает никаких предупреждений. Именно этот случай описан в статье [1] и в этой ситуации преобразование действительно делается. Однако, в нашем примере вместо директивы for используется директива sections, и такое преобразование не производится.

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

27. Параллельная работа с массивом без упорядочивания итераций

Во всех предыдущих примерах в циклах for, распределенных на несколько потоков, не использовалась директива ordered (за исключением примера, в котором рассматривался непосредственно синтаксис этой директивы). Причина этого заключается в том, что во всех этих примерах порядок выполнения итераций был для нас несущественен. Однако, существуют ситуации, в которых эта директива необходима. В частности, она необходима, если выполнение одной итерации как-либо зависит от результата выполнения предыдущих. Рассмотрим пример.

Теоретически эта программа должна вывести последовательность из нулей. Однако, на двухпроцессорной машине будет выведено некоторое количество нулей и некоторое количество пятерок (это связано с тем, что итерации как правило делятся между потоками пополам). Проблема легко решается с помощью директивы ordered.

Ошибки производительности

1. Ненужная директива flush

Все рассмотренные ранее ошибки влияли на поведение программы и являлись в той или иной мере критическими. Теперь же рассмотрим ошибки, которые повлияют лишь на производительность программы, не затрагивая логики ее работы. Эти ошибки описаны в статье [1].

Как уже упоминалось ранее, директива flush во многих случаях выполняется неявно. Следовательно, явное использование flush в этих случаях будет лишним. Лишняя директива flush, особенно если соответствующие переменные не будут указаны в качестве параметров директивы (в этом случае делается синхронизация всей общей памяти), может существенно замедлить выполнение программы.

Приведем случаи, в которых эта директива присутствует неявно и использовать ее нет нужды:

  • В директиве barrier
  • При входе и при выходе из параллельной секции директивы critical
  • При входе и при выходе из параллельной секции директивы ordered
  • При входе и при выходе из параллельной секции директивы parallel
  • При выходе из параллельной секции директивы for
  • При выходе из параллельной секции директивы sections
  • При выходе из параллельной секции директивы single
  • При входе и при выходе из параллельной секции директивы parallel for
  • При входе и при выходе из параллельной секции директивы parallel sections

2. Использование критических секций или блокировок вместо atomic

Директива atomic работает быстрее, чем критические секции, поскольку некоторые атомарные операции могут быть напрямую заменены командами процессора. Следовательно, эту директиву желательно применять везде, где требуется защита общей памяти при элементарных операциях. К таким операциям, согласно спецификации OpenMP, относятся операции следующего вида:

Здесь х — скалярная переменная, expr — выражение со скалярными типами, в котором не присутствует переменная х, binop — не перегруженный оператор +, *, -, /, &, ^, |, >. Во всех остальных случаях применять директиву atomic нельзя (это проверяется компилятором).

Вообще, с точки зрения убывания быстродействия, средства защиты общих данных от одновременной записи располагаются так: atomic, critical, omp_set_lock.

3. Ненужная защита памяти от одновременной записи

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

Переменную не нужно защищать от одновременной записи в следующих случаях:

  • Если переменная является локальной для потока (а также, если она участвует в выражении threadprivate, firstprivate, private или lastprivate)
  • Если обращение к переменной производится в коде, который гарантированно выполняется только одним потоком (в параллельной секции директивы master или директивы single).

4. Неоправданно большое количество кода в критической секции

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

Следовательно, применение критических секций там, где они не нужны, нежелательно. В критические секции не рекомендуется помещать вызовы сложных функций, а также код, не работающий с общими переменными, объектами или ресурсами. Дать конкретные рекомендации тут достаточно трудно — в каждом случае программист должен сам определить, какой код вносить в критическую секцию, а какой — не вносить.

5. Слишком частое применение критических секций

Как уже упоминалось в предыдущем пункте, вход в критическую секцию и выход из нее требуют определенного времени. Следовательно, частые входы в критическую секцию могут существенно замедлить программу. Чтобы избежать этого, рекомендуется насколько возможно снижать число входов в критические секции. Рассмотрим несколько измененный пример из статьи [1].

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

Такое простое исправление может существенно увеличить производительность вашего кода, и им не стоит пренебрегать.

Заключение

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

1. Отсутствие /openmp

При создании проекта нужно сразу же включить соответствующую опцию.

2. Отсутствие parallel

Необходимо тщательно следить за синтаксисом используемых директив.

3. Отсутствие omp

Необходимо тщательно следить за синтаксисом используемых директив.

4. Отсутствие for

Необходимо тщательно следить за синтаксисом используемых директив.

5. Ненужное распараллеливание

Необходимо тщательно следить за синтаксисом используемых директив и четко представлять себе их назначение.

6. Неправильное применение ordered

Необходимо тщательно следить за синтаксисом используемых директив.

7. Переопределение количества потоков внутри параллельной секции

Количество потоков нельзя изменять внутри параллельной секции.

8. Попытка использовать блокировку без инциализации переменной

Переменная, использующаяся для блокировки, должна быть обязательно инициализирована функцией omp_init_lock.

9. Попытка снять блокировку не из того потока, который ее установил

Каждый из потоков, использующих блокировку, должен содержать вызов как блокирующей (omp_set_lock, omp_test_lock), так и разблокирующей (omp_unset_lock) функции.

10. Попытка использования блокировки как барьера

Каждый из потоков, использующих блокировку, должен содержать вызов как блокирующей (omp_set_lock, omp_test_lock), так и разблокирующей (omp_unset_lock) функции.

11. Зависимость поведения от количества потоков

Поведение вашего кода не должно зависеть от числа исполняющих его потоков.

12. Некорректное использование динамического создания потоков

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

13. Одновременное использование общего ресурса

Одновременный доступ к общему ресурсу должен быть защищен критической секцией или блокировкой.

14. Незащищенный доступ к общей памяти

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

15. Использование директивы flush с указателем

Применять директиву flush к указателю бессмысленно — при этом обновится значение указателя, но не памяти, на которую он ссылается.

16. Отсутствие директивы flush

Отсутствие директивы flush может привести к чтению или записи некорректных данных.

17. Отсутствие синхронизации

Отсутствие синхронизации также может привести к чтению или записи некорректных данных.

18. Внешняя переменная задана как threadprivate не во всех модулях

Если переменная, фигурирующая в директиве threadprivate, является внешней, она должна быть объявлена как threadprivate во всех модулях, в которых она встречается. Вообще от использования директивы threadprivate и выражений private, firstprivate, lastprivate лучше отказаться. Вместо этого рекомендуется объявлять локальные переменные в коде параллельной секции, а соответствующие начальные и конечные присваивания (если они необходимы) производить с общей переменной.

19. Неинициализированные локальные переменные

По умолчанию локальные переменные, фигурирующие в выражениях private и lastprivate являются неинциализированными. Брать их значения без предварительной инициализации нельзя. Вообще от использования директивы threadprivate и выражений private, firstprivate, lastprivate лучше отказаться. Вместо этого рекомендуется объявлять локальные переменные в коде параллельной секции, а соответствующие начальные и конечные присваивания (если они необходимы) производить с общей переменной.

20. Забытая директива threadprivate

Забытая директива threadprivate может повлиять на поведение всего модуля. Вообще от использования директивы threadprivate и выражений private, firstprivate, lastprivate лучше отказаться. Вместо этого рекомендуется объявлять локальные переменные в коде параллельной секции, а соответствующие начальные и конечные присваивания (если они необходимы) производить с общей переменной.

21. Забытое выражение private

Необходимо четко контролировать режим доступа к переменным. Новичкам рекомендуется использовать выражение default(none), чтобы режим доступа всегда приходилось задавать явно. Вообще от использования директивы threadprivate и выражений private, firstprivate, lastprivate лучше отказаться. Вместо этого рекомендуется объявлять локальные переменные в коде параллельной секции, а соответствующие начальные и конечные присваивания (если они необходимы) производить с общей переменной.

22. Некорректное распараллеливание работы с локальными переменными

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

23. Неосторожное применение lastprivate


Нужно четко представлять себе, какое именно значение будет в итоге записано в переменную после выполнения параллельной секции, если переменная объявлена как lastprivate. Вообще от использования директивы threadprivate и выражений private, firstprivate, lastprivate лучше отказаться. Вместо этого рекомендуется объявлять локальные переменные в коде параллельной секции, а соответствующие начальные и конечные присваивания (если они необходимы) производить с общей переменной.

24. Непредсказуемые значения threadprivate-переменных в начале параллельных секций

Значение переменной, объявленной как threadprivate, является непредсказуемым в начале параллельной секции, особенно если переменной до этого присваивалось какое-либо значение. Вообще от использования директивы threadprivate и выражений private, firstprivate, lastprivate лучше отказаться. Вместо этого рекомендуется объявлять локальные переменные в коде параллельной секции, а соответствующие начальные и конечные присваивания (если они необходимы) производить с общей переменной.

25. Некоторые ограничения локальных переменных

Локальные переменные не должны быть ссылками (при этом через них будет производиться одновременный доступ к одной и той же общей памяти) и экземплярами классов, не имеющих конструктора копирования (если в классе содержатся ссылки, объект может быть скопирован некорректно).

26. Локальные переменные не помечены как таковые

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

27. Параллельная работа с массивом без упорядочивания итераций

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

1. Ненужная директива flush

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

2. Использование критических секций или блокировок вместо atomic

Для защиты элементарных операций лучше использовать директиву atomic. Использование критических секции и блокировок менее предпочтительно, поскольку оно замедляет работу программы.

3. Ненужная защита памяти от одновременной записи

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

4. Неоправданно большое количество кода в критической секции

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

5. Слишком частое применение критических секций

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

Таблица 1 — Краткий список основных ошибок.

Вообще все ошибки можно разделить на три основные категории:

  • Незнание синтаксиса OpenMP.
  • Непонимание принципов работы OpenMP.
  • Некорректная работа с памятью (незащищенный доступ к общей памяти, отсутствие синхронизации, неправильный режим доступа к переменным, и т. п.).

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

Как бы то ни было, все эти ошибки в большинстве случаев можно легко диагностировать автоматически, средствами статического анализатора. На данный момент диагностику некоторых (лишь очень немногих) из них выполняет Intel Thread Checker. Некоторые ошибки диагностируются компиляторами, отличными от компилятора Visual Studio. Однако специализированного инструмента пока не существует. В частности, Intel Thread Checker обнаруживает одновременный доступ к общим переменным, некорректное использование директивы ordered и отсутствие ключевого слова for в директиве #pragma omp parallel for [1].

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

В данный момент авторами начата работа над статическим анализатором кода (рабочее название VivaMP), который будет диагностировать все перечисленные выше ошибки и, возможно, некоторые другие. Этот анализатор сможет существенно упростить поиск ошибок при разработке параллельных приложений (напомним, что почти все эти ошибки воспроизводятся нестабильно) и их устранение. Дополнительную информацию вы можете получить на странице, посвященной проекту VivaMP.

Список использованных источников

  • Michael Suess, Claudia Leopold, Common Mistakes in OpenMP and How To Avoid Them — A Collection of Best Practices.
  • OpenMP Quick Reference Sheet.
  • OpenMP C and C++ Application Program Interface specification, version 2.0.
  • Yuan Lin, Common Mistakes in Using OpenMP 1: Incorrect Directive Format.
  • Richard Gerber, Advanced OpenMP Programming.
  • Yuan Lin, Common Mistakes in Using OpenMP 5: Assuming Non-existing Synchronization Before Entering Worksharing Construct.
  • MSDN Library article on ‘threadprivate’ OpenMP directive.
  • Andrey Karpov, Evgeniy Ryzhkov, Adaptation of the technology of the static code analyzer for developing parallel programs.
Найдите ошибки в своем C, C++, C# и Java коде

Предлагаем попробовать проверить код вашего проекта с помощью анализатора кода PVS-Studio. Одна найденная в нём ошибка скажет вам о пользе методологии статического анализа кода больше, чем десяток статей.

Потоки на пользовательском уровне. Потоки на уровне ядра

Обычно выделяют две общие категории потоков: потоки на уровне пользователя (user-level threads — ULT) и потоки на уровне ядра (kernel-level threads — KLT). Потоки второго типа в литературе иногда называются потоками, поддерживаемыми ядром, или облегченными процессами.

Потоки на уровне пользователя

В программе, полностью состоящей из ULT-потоков, все действия по управлению потоками выполняются самим приложением; ядро, по сути, и не подозревает о существовании потоков. На рис. 4.6,а проиллюстрирован подход, при котором используются только потоки на уровне пользователя. Чтобы приложение было многопоточным, его следует создавать с применением специальной библиотеки, представляющей собой пакет программ для работы с потоками на уровне ядра. Такая библиотека для работы с потоками содержит код, с помощью которого можно создавать и удалять потоки, производить обмен сообщениями и данными между потоками, планировать их выполнение, а также сохранять и восстанавливать их контекст.

Рис. 4.6. Потоки на пользовательском уровне и на уровне ядра

По умолчанию приложение в начале своей работы состоит из одного потока и его выполнение начинается как выполнение этого потока. Такое приложение вместе с составляющим его потоком размещается в едином процессе, который управляется ядром. Выполняющееся приложение в любой момент времени может породить новый поток, который будет выполняться в пределах того же процесса. Новый поток создается с помощью вызова специальной подпрограммы из библиотеки, предназначенной для работы с потоками. Управление к этой подпрограмме переходит в результате вызова процедуры. Библиотека потоков создает структуру данных для нового потока, а потом передает управление одному из готовых к выполнению потоков данного процесса, руководствуясь некоторым алгоритмом планирования. Когда управление переходит к библиотечной подпрограмме, контекст текущего потока сохраняется, а когда управление возвращается к потоку, его контекст восстанавливается. Этот контекст в основном состоит из содержимого пользовательских регистров, счетчика команд и указателей стека.

Все описанные в предыдущих абзацах события происходят в пользовательском пространстве в рамках одного процесса. Ядро не подозревает об этой деятельности. Оно продолжает осуществлять планирование процесса как единого целого и приписывать ему единое состояние выполнения (состояние готовности, состояние выполняющегося процесса, состояние блокировки и т.д.). Приведенные ниже примеры должны прояснить взаимосвязь между планированием потоков и планированием процессов. Предположим, что выполняется поток 2, входящий в процесс В (см. рис. 4.7). Состояния этого процесса и составляющих его потоков на пользовательском уровне показаны на рис. 4.7,а. Впоследствии может произойти одно из следующих событий.

  1. Приложение, в котором выполняется поток 2, может произвести системный вызов, например запрос ввода-вывода, который блокирует процесс В. В результате этого вызова управление перейдет к ядру. Ядро вызывает процедуру ввода-вывода, переводит процесс В в состояние блокировки и передает управление другому процессу. Тем временем поток 2 процесса В все еще находится в состоянии выполнения в соответствии со структурой данных, поддерживаемой библиотекой потоков. Важно отметить, что поток 2 не выполняется в том смысле, что он работает с процессором; однако библиотека потоков воспринимает его как выполняющийся. Соответствующие диаграммы состояний показаны на рис. 4.7,6.
  2. В результате прерывания по таймеру управление может перейти к ядру; ядро определяет, что интервал времени, отведенный выполняющемуся в данный момент процессу В, истек. Ядро переводит процесс В в состояние готовности и передает управление другому процессу. В это время, согласно структуре данных, которая поддерживается библиотекой потоков, поток 2 процесса В по-прежнему будет находиться в состоянии выполнения. Соответствующие диаграммы состояний показаны на рис. 4.7,в.
  3. Поток 2 достигает точки выполнения, когда ему требуется, чтобы поток 1 процесса В выполнил некоторое действие. Он переходит в заблокированное состояние, а поток 1 — из состояния готовности в состояние выполнения. Сам процесс остается в состоянии выполнения. Соответствующие диаграммы состояний показаны на рис. 4.7,г.

Рис. 4.7. Примеры взаимосвязей между состояниями потоков пользовательского уровня и состояниями процесса

В случаях 1 и 2 (см. рис. 4.7,6 и в) при возврате управления процессу В возобновляется выполнение потока 2. Заметим также, что процесс, в котором выполняется код из библиотеки потоков, может быть прерван либо из-за того, что закончится отведенный ему интервал времени, либо из-за наличия процесса с более высоким приоритетом. Когда возобновится выполнение прерванного процесса, оно продолжится работой процедуры из библиотеки потоков, которая завершит переключение потоков и передаст управление новому потоку процесса.

Использование потоков на пользовательском уровне обладает некоторыми преимуществами перед использованием потоков на уровне ядра. К этим преимуществам относятся следующие:

  1. Переключение потоков не включает в себя переход в режим ядра, так как структуры данных по управлению потоками находятся в адресном пространстве одного и того же процесса. Поэтому для управления потоками процессу не нужно переключаться в режим ядра. Благодаря этому обстоятельству удается избежать накладных расходов, связанных с двумя переключениями режимов (пользовательского режима в режим ядра и обратно).
  2. Планирование производится в зависимости от специфики приложения. Для одних приложений может лучше подойти простой алгоритм планирования по круговому алгоритму, а для других — алгоритм планирования, основанный на использовании приоритета. Алгоритм планирования может подбираться для конкретного приложения, причем это не повлияет на алгоритм планирования, заложенный в операционной системе.
  3. Использование потоков на пользовательском уровне применимо для любой операционной системы. Для их поддержки в ядро системы не потребуется вносить никаких изменений. Библиотека потоков представляет собой набор утилит, работающих на уровне приложения и совместно используемых всеми приложениями.

Использование потоков на пользовательском уровне обладает двумя явными недостатками по сравнению с использованием потоков на уровне ядра.

  1. В типичной операционной системе многие системные вызовы являются блокирующими. Когда в потоке, работающем на пользовательском уровне, выполняется системный вызов, блокируется не только данный поток, но и все потоки того процесса, к которому он относится.
  2. В стратегии с наличием потоков только на пользовательском уровне приложение не может воспользоваться преимуществами многопроцессорной системы, так как ядро закрепляет за каждым процессом только один процессор. Поэтому несколько потоков одного и того же процесса не могут выполняться одновременно. В сущности, у нас получается многозадачность на уровне приложения в рамках одного процесса. Несмотря на то, что даже такая многозадачность может привести к значительному увеличению скорости работы приложения, имеются приложения, которые работали бы гораздо лучше, если бы различные части их кода могли выполняться одновременно.

Эти две проблемы разрешимы. Например, их можно преодолеть, если писать приложение не в виде нескольких потоков, а в виде нескольких процессов. Однако при таком подходе основные преимущества потоков сводятся на нет: каждое переключение становится не переключением потоков, а переключением процессов, что приведет к значительно большим накладным затратам.
Другим методом преодоления проблемы блокирования является использование преобразования блокирующего системного вызова в неблокирующий. Например, вместо непосредственного вызова системной процедуры ввода-вывода поток вызывает подпрограмму-оболочку, которая производит ввод-вывод на уровне приложения. В этой программе содержится код, который проверяет, занято ли устройство ввода-вывода. Если оно занято, поток передает управление другому потоку (что происходит с помощью библиотеки потоков). Когда наш поток вновь получает управление, он повторно осуществляет проверку занятости устройства ввода-вывода.

Потоки на уровне ядра

В программе, работа которой полностью основана на потоках, работающих на уровне ядра, все действия по управлению потоками выполняются ядром. В области приложений отсутствует код, предназначенный для управления потоками. Вместо него используется интерфейс прикладного программирования (application programming interface — API) средств ядра, управляющих потоками. Примерами такого подхода являются операционные системы OS/2, Linux и W2K.
На рис. 4.6,6″ проиллюстрирована стратегия использования потоков на уровне ядра. Любое приложение при этом можно запрограммировать как многопоточное; все потоки приложения поддерживаются в рамках единого процесса. Ядро поддерживает информацию контекста процесса как единого целого, а также контекстов каждого отдельного потока процесса. Планирование выполняется ядром исходя из состояния потоков. С помощью такого подхода удается избавиться от двух упомянутых ранее основных недостатков потоков пользовательского уровня. Во-первых, ядро может одновременно осуществлять планирование работы нескольких потоков одного и того же процесса на нескольких процессорах. Во-вторых, при блокировке одного из потоков процесса ядро может выбрать для выполнения другой поток этого же процесса. Еще одним преимуществом такого подхода является то, что сами процедуры ядра могут быть многопоточными.
Основным недостатком подхода с использованием потоков на уровне ядра по сравнению с использованием потоков на пользовательском уровне является то, что для передачи управления от одного потока другому в рамках одного и того же процесса приходится переключаться в режим ядра. Результаты исследований, проведенных на однопроцессорной машине VAX под управлением UNIX-подобной операционной системы, представленные в табл. 4.1, иллюстрируют различие между этими двумя подходами. Сравнивалось время выполнения таких двух задач, как (1) нулевое ветвление (Null Fork) — время, затраченное на создание, планирование и выполнение процесса/потока, состоящего только из нулевой процедуры (измеряются только накладные расходы, связанные с ветвлением процесса/потока), и (2) ожидание сигнала (Signal-Wait) — время, затраченное на передачу сигнала от одного процесса/потока другому процессу/потоку, находящемуся в состоянии ожидания (накладные расходы на синхронизацию двух процессов/потоков). Чтобы было легче сравнивать полученные значения, заметим, что вызов процедуры на машине VAX, используемой в этом исследовании, длится 7 us, а системное прерывание — 17 us. Мы видим, что различие во времени выполнения потоков на уровне ядра и потоков на пользовательском уровне более чем на порядок превосходит по величине различие во времени выполнения потоков на уровне ядра и процессов.

Таблица 4.1. Время задержек потоков (ка) [ANDE92]

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

Комбинированные подходы

В некоторых операционных системах применяется комбинирование потоков обоих видов (рис. 4.6,в). Ярким примером такого подхода может служить операционная система Solaris. В комбинированных системах создание потоков выполняется в пользовательском пространстве, там же, где и код планирования и синхронизации потоков в приложениях. Несколько потоков на пользовательском уровне, входящих в состав приложения, отображаются в такое же или меньшее число потоков на уровне ядра. Программист может изменять число потоков на уровне ядра, подбирая его таким, которое позволяет достичь наилучших результатов.
При комбинированном подходе несколько потоков одного и того же приложения могут выполняться одновременно на нескольких процессорах, а блокирующие системные вызовы не приводят к блокировке всего процесса. При надлежащей реализации такой подход будет сочетать в себе преимущества подходов, в которых применяются только потоки на пользовательском уровне или только потоки на уровне ядра, сводя недостатки каждого из этих подходов к минимуму.

Другие схемы

Как уже упоминалось, понятия единицы распределения ресурсов и планирования традиционно отождествляются с понятием процесса. В такой концепции поддерживается однозначное соответствие между потоками и процессами. В последнее время наблюдается интерес к использованию нескольких потоков в одном процессе, когда выполняется соотношение многие-к-одному. Однако возможны и другие комбинации, а именно соответствие нескольких потоков нескольким процессам и соответствие одного потока нескольким процессам. Примеры применения каждой из упомянутых комбинаций приводятся в табл. 4.2.

Таблица 4.2. Соотношение между потоками и процессами

Соответствие нескольких потоков нескольким процессам

Идея реализации соответствия нескольких процессов нескольким потокам была исследована в экспериментальной операционной системе TRIX [SIEB83, WARD80]. В данной операционной системе используются понятия домена и потока. Домен — это статический объект, состоящий из адресного пространства и портов, через которые можно отправлять и получать сообщения. Поток — это единая выполняемая ветвь, обладающая стеком выполнения и характеризующаяся состоянием процессора, а также информацией по планированию.
Как и в других указанных ранее многопоточных подходах, в рамках одного домена могут выполняться несколько потоков. При этом удается получить уже описанное повышение эффективности работы. Кроме того, имеется возможность осуществлять деятельность одного и того же пользователя или приложения в нескольких доменах. В этом случае имеется поток, который может переходить из одного домена в другой.
По-видимому, использование одного и того же потока в разных доменах продиктовано желанием предоставить программисту средства структурирования. Например, рассмотрим программу, в которой используется подпрограмма ввода-вывода. В многозадачной среде, в которой пользователю позволено создавать процессы, основная программа может сгенерировать новый процесс для управления вводом-выводом, а затем продолжить свою работу. Однако если для дальнейшего выполнения основной программы необходимы результаты операции ввода-вывода, то она должна ждать, пока не закончится работа подпрограммы ввода-вывода. Подобное приложение можно осуществить такими способами.

  1. Реализовать всю программу в виде единого процесса. Такой прямолинейный подход является вполне обоснованным. Недостатки этого подхода связаны с управлением памятью. Эффективно организованный как единое целое процесс может занимать в памяти много места, в то время как для подпрограммы ввода-вывода требуется относительно небольшое адресное пространство. Из-за того что подпрограмма ввода-вывода выполняется в адресном пространстве более объемной программы, во время выполнения ввода-вывода весь процесс должен оставаться в основной памяти, либо операция ввода-вывода будет выполняться с применением свопинга. То же происходит и в случае, когда и основная программа, и подпрограмма ввода-вывода реализованы в виде двух потоков в одном адресном пространстве.
  2. Основная программа и подпрограмма ввода-вывода реализуются в виде двух отдельных процессов. Это приводит к накладным затратам, возникающим в результате создания подчиненного процесса. Если ввод-вывод производится достаточно часто, то необходимо будет либо оставить такой подчиненный процесс активным на все время работы основного процесса, что связано с затратами на управление ресурсами, либо часто создавать и завершать процесс с подпрограммой, что приведет к снижению эффективности.
  3. Реализовать действия основной программы и подпрограммы ввода-вывода как единый поток. Однако для основной программы следует создать свое адресное пространство (свой домен), а для подпрограммы ввода-вывода — свое. Таким образом, поток в ходе выполнения программы будет переходить из одного адресного пространства к другому. Операционная система может управлять этими двумя адресными пространствами независимо, не затрачивая никаких дополнительных ресурсов на создание процесса. Более того, адресное пространство, используемое подпрограммой ввода-вывода, может использоваться совместно с другими простыми подпрограммами ввода-вывода.

Опыт разработчиков операционной системы TRIX свидетельствует о том, что третий вариант заслуживает внимания и для некоторых приложений может оказаться самым эффективным.

Соответствие одного потока нескольким процессам

В области распределенных операционных систем (разрабатываемых для управления распределенными компьютерными системами) представляет интерес концепция потока как основного элемента, способного переходить из одного адресного пространства в другое (В последние годы активно исследуется тема перехода процессов и потоков из одного адресного пространства в другое (миграция). Эта тема рассматривается в главе 14, «Управление распределенными процессами».). Заслуживают упоминания операционная система Clouds и, в особенности, ее ядро, известное под названием Ra [DASG92]. В качестве другого примера можно привести систему Emerald [STEE95].

В операционной системе Clouds поток является единицей активности с точки зрения пользователя. Процесс имеет вид виртуального адресного пространства с относящимся к нему управляющим блоком. После создания поток начинает выполнение в рамках процесса. Потоки могут переходить из одного адресного пространства в другое и даже выходить за рамки машины (т.е. переходить из одного компьютера в другой). При переходе потока в другое место он должен нести с собой определенную информацию — такую, как управляющий терминал, глобальные параметры и сведения по его планированию (например, приоритет).

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

Вернуться в оглавление:Операционные системы

Синхронизация процессов и потоков

Процессом (process) называется экземпляр программы, загруженной в память. Этот экземпляр может создавать нити (thread), которые представляют собой последовательность инструкций на выполнение. Важно понимать, что выполняются не процессы, а именно нити.

Причем любой процесс имеет хотя бы одну нить. Эта нить называется главной (основной) нитью приложения.

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

В зависимости от ситуации нити могут находиться в трех состояниях. Во-первых, нить может выполняться, когда ей выделено процессорное время, т.е. она может находиться в состоянии активности. Во-вторых, она может быть неактивной и ожидать выделения процессора, т.е. быть в состоянии готовности. И есть еще третье, тоже очень важное состояние — состояние блокировки. Когда нить заблокирована, ей вообще не выделяется время. Обычно блокировка ставится на время ожидания какого-либо события. При возникновении этого события нить автоматически переводится из состояния блокировки в состояние готовности. Например, если одна нить выполняет вычисления, а другая должна ждать результатов, чтобы сохранить их на диск. Вторая могла бы использовать цикл типа «while( !isCalcFinished ) continue;», но легко убедиться на практике, что во время выполнения этого цикла процессор занят на 100 % (это называется активным ожиданием). Таких вот циклов следует по возможности избегать, в чем оказывает неоценимую помощь механизм блокировки. Вторая нить может заблокировать себя до тех пор, пока первая не установит событие, сигнализирующее о том, что чтение окончено.

Синхронизация нитей в ОС Windows

В Windows реализована вытесняющая многозадачность — это значит, что в любой момент система может прервать выполнение одной нити и передать управление другой. Ранее, в Windows 3.1, использовался способ организации, называемый кооперативной многозадачностью: система ждала, пока нить сама не передаст ей управление и именно поэтому в случае зависания одного приложения приходилось перезагружать компьютер.

Все нити, принадлежащие одному процессу, разделяют некоторые общие ресурсы — такие, как адресное пространство оперативной памяти или открытые файлы. Эти ресурсы принадлежат всему процессу, а значит, и каждой его нити. Следовательно, каждая нить может работать с этими ресурсами без каких-либо ограничений. Но. Если одна нить еще не закончила работать с каким-либо общим ресурсом, а система переключилась на другую нить, использующую этот же ресурс, то результат работы этих нитей может чрезвычайно сильно отличаться от задуманного. Такие конфликты могут возникнуть и между нитями, принадлежащими различным процессам. Всегда, когда две или более нитей используют какой-либо общий ресурс, возникает эта проблема.

Пример. Несинхронизированная работа нитей: если временно приостановить выполнение нити вывода на экран (пауза), фоновая нить заполнения массива будет продолжать работать.

Именно поэтому необходим механизм, позволяющий потокам согласовывать свою работу с общими ресурсами. Этот механизм получил название механизма синхронизации нитей (thread synchronization).

Этот механизм представляет собой набор объектов операционной системы, которые создаются и управляются программно, являются общими для всех нитей в системе (некоторые — для нитей, принадлежащих одному процессу) и используются для координирования доступа к ресурсам. В качестве ресурсов может выступать все, что может быть общим для двух и более нитей — файл на диске, порт, запись в базе данных, объект GDI, и даже глобальная переменная программы (которая может быть доступна из нитей, принадлежащих одному процессу).

Объектов синхронизации существует несколько, самые важные из них — это взаимоисключение (mutex), критическая секция (critical section), событие (event) и семафор (semaphore). Каждый из этих объектов реализует свой способ синхронизации. Также в качестве объектов синхронизации могут использоваться сами процессы и нити (когда одна нить ждет завершения другой нити или процесса); а также файлы, коммуникационные устройства, консольный ввод и уведомления об изменении.

Любой объект синхронизации может находиться в так называемом сигнальном состоянии. Для каждого типа объектов это состояние имеет различный смысл. Нити могут проверять текущее состояние объекта и/или ждать изменения этого состояния и таким образом согласовывать свои действия. При этом гарантируется, что когда нить работает с объектами синхронизации (создает их, изменяет состояние) система не прервет ее выполнения, пока она не завершит это действие. Таким образом, все конечные операции с объектами синхронизации являются атомарными (неделимыми.

Работа с объектами синхронизации

Чтобы создать тот или иной объект синхронизации, производится вызов специальной функции WinAPI типа Create. (напр. CreateMutex). Этот вызов возвращает дескриптор объекта (HANDLE), который может использоваться всеми нитями, принадлежащими данному процессу. Есть возможность получить доступ к объекту синхронизации из другого процесса — либо унаследовав дескриптор этого объекта, либо, что предпочтительнее, воспользовавшись вызовом функции открытия объекта (Open. ). После этого вызова процесс получит дескриптор, который в дальнейшем можно использовать для работы с объектом. Объекту, если только он не предназначен для использования внутри одного процесса, обязательно присваивается имя. Имена всех объектов должны быть различны (даже если они разного типа). Нельзя, например, создать событие и семафор с одним и тем же именем.

По имеющемуся дескриптору объекта можно определить его текущее состояние. Это делается с помощью т.н. ожидающих функций. Чаще всего используется функция WaitForSingleObject. Эта функция принимает два параметра, первый из которых — дескриптор объекта, второй — время ожидания в мсек. Функция возвращает WAIT_OBJECT_0, если объект находится в сигнальном состоянии, WAIT_TIMEOUT — если истекло время ожидания, и WAIT_ABANDONED, если объект-взаимоисключение не был освобожден до того, как владеющая им нить завершилась. Если время ожидания указано равным нулю, функция возвращает результат немедленно, в противном случае она ждет в течение указанного промежутка времени. В случае, если состояние объекта станет сигнальным до истечения этого времени, функция вернет WAIT_OBJECT_0, в противном случае функция вернет WAIT_TIMEOUT. Если в качестве времени указана символическая константа INFINITE, то функция будет ждать неограниченно долго, пока состояние объекта не станет сигнальным.

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


Критические секции

Объект-критическая секция помогает программисту выделить участок кода, где нить получает доступ к разделяемому ресурсу, и предотвратить одновременное использование ресурса. Перед использованием ресурса нить входит в критическую секцию (вызывает функцию EnterCriticalSection). Если после этого какая-либо другая нить попытается войти в ту же самую критическую секцию, ее выполнение приостановится, пока первая нить не покинет секцию с помощью вызова LeaveCriticalSection. Используется только для нитей одного процесса. Порядок входа в критическую секцию не определен.

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

Пример. Синхронизация нитей с помощью критических секций.

Взаимоисключения

Объекты-взаимоисключения (мьютексы, mutex — от MUTual EXclusion) позволяют координировать взаимное исключение доступа к разделяемому ресурсу. Сигнальное состояние объекта (т.е. состояние «установлен») соответствует моменту времени, когда объект не принадлежит ни одной нити и его можно «захватить». И наоборот, состояние «сброшен» (не сигнальное) соответствует моменту, когда какая-либо нить уже владеет этим объектом. Доступ к объекту разрешается, когда нить, владеющая объектом, освободит его.

Две (или более) нити могут создать мьютекс с одним и тем же именем, вызвав функцию CreateMutex. Первая нить действительно создает мьютекс, а следующие — получают дескриптор уже существующего объекта. Это дает возможность нескольким нитям получить дескриптор одного и того же мьютекса, освобождая программиста от необходимости заботиться о том, кто в действительности создает мьютекс. Если используется такой подход, желательно установить флаг bInitialOwner в FALSE, иначе возникнут определенные трудности при определении действительного создателя мьютекса.

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

  • Дочерний процесс, созданный при помощи функции CreateProcess может наследовать дескриптор мьютекса в случае, если при создании мьютекса функцией CreateMutex был указан параметр lpMutexAttributes.
  • Нить может получить дубликат существующего мьютекса с помощью функции DuplicateHandle.
  • Нить может указать имя существующего мьютекса при вызове функций OpenMutex или CreateMutex.

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

Для синхронизации нитей одного процесса более эффективно использование критических секций.

Пример. Синхронизация нитей с помощью мьютексов.

События

Объекты-события используются для уведомления ожидающих нитей о наступлении какого-либо события. Различают два вида событий — с ручным и автоматическим сбросом. Ручной сброс осуществляется функцией ResetEvent. События с ручным сбросом используются для уведомления сразу нескольких нитей. При использовании события с автосбросом уведомление получит и продолжит свое выполнение только одна ожидающая нить, остальные будут ожидать дальше.

Функция CreateEvent создает объект-событие, SetEvent — устанавливает событие в сигнальное состояние, ResetEvent — сбрасывает событие. Функция PulseEvent устанавливает событие, а после возобновления ожидающих это событие нитей (всех при ручном сбросе и только одной при автоматическом), сбрасывает его. Если ожидающих нитей нет, PulseEvent просто сбрасывает событие.

Пример. Синхронизация нитей с помощью событий.

Семафоры

Объект-семафор — это фактически объект-взаимоисключение со счетчиком. Данный объект позволяет «захватить» себя определенному количеству нитей. После этого «захват» будет невозможен, пока одна из ранее «захвативших» семафор нитей не освободит его. Семафоры применяются для ограничения количества нитей, одновременно работающих с ресурсом. Объекту при инициализации передается максимальное число нитей, после каждого «захвата» счетчик семафора уменьшается. Сигнальному состоянию соответствует значение счетчика больше нуля. Когда счетчик равен нулю, семафор считается не установленным (сброшенным).

Функция CreateSemaphore создает объект-семафор с указанием и максимально возможного начального его значения, OpenSemaphore – возвращает дескриптор существующего семафора, захват семафора производится с помощью ожидающих функций, при этом значение семафора уменьшается на единицу, ReleaseSemaphore — освобождение семафора с увеличением значения семафора на указанное в параметре число.

Пример. Синхронизация нитей с помощью семафоров.

Защищенный доступ к переменным

Существует ряд функций, позволяющих работать с глобальными переменными из всех нитей, не заботясь о синхронизации, т.к. эти функции сами за ней следят – их выполнение атомарно. Это функции InterlockedIncrement, InterlockedDecrement, InterlockedExchange, InterlockedExchangeAdd и InterlockedCompareExchange. Например, функция InterlockedIncrement атомарно увеличивает значение 32-битной переменной на единицу, что удобно использовать для различных счетчиков.

Для получения полной информации о назначении, использовании и синтаксисе всех функций WIN32 API необходимо воспользоваться системой помощи MS SDK, входящей в состав сред программирования Borland Delphi или CBuilder, а также MSDN, поставляемым в составе системы программирования Visual C.

Классические задачи теории многопоточности средствами C#

Сегодня мы снова пройдемся по классической теории. На этот раз мы будем заниматься многопоточностью, а если точнее, то синхронизацией потоков. Конечно, большое число процессов позволяет более полно использовать мощности вашего компьютера. Однако, когда ваши потоки требуют взаимодействия друг с другом, часто возникают проблемы. Во многих языках программирования многопоточности уделяется большое значение, в том числе и синхронизации. Вот мы и посмотрим какое выражение нашла эта теория в языке высокого уровня C# и порешаем известные задачи о взаимодействии нескольких процессов.

Основы теории

Начнем с рассмотрения основных понятий теории. В каждый момент времени можно описать выполнение программы с помощью ее состояния. Состояние складывается из значений всех переменных программы. Процесс выполняет последовательность операторов, которые в свою очередь разбиваются на последовательность неделимых действий. Такие действия изменяют состояние программы неделимым образом.

Выполнение программы можно представить как последовательность чередующихся неделимых действий, принадлежащих разным потокам (в этом посте я буду использовать понятия процесс и поток как синонимы). Такая последовательность называется историей (напоминает теорию транзакций, не правда ли?). В случае одного процесса такая история может быть только одна, но в контексте многопоточности мы получаем огромное число возможных историй. Цель синхронизации заключается в том, чтобы исключить нежелательные истории из программы.

Для задач будут представлены классические решения на псевдокоде и то, как их можно реализовать на C#. При этом некоторые конструкции псевдокода, нужно дополнительно пояснить. Для синхронизации используются два основных приема: взаимное исключение и условная синхронизация. Взаимное исключение реализуется за счет крупномодульных неделимых действий, то есть неделимых действий, выполняющихся как одно неделимое. Такая последовательность обозначается в псевдокоде угловыми скобками. Таким образом сложение и присвоение значений в следующем операторе будет выполнено неделимым образом:

Условная синхронизация — другой прием для управления взаимодействием процессов. Она позволяет “усыпить” процесс до выполнения некоторого условия. Синтаксис такой: 0) s = s — 1; > . В этом примере процесс доходит до условия того, что значение s положительно, и в случае невыполнения этого условия висит и ничего не делает. Как только значение станет положительным, процесс преодолеет условие и неделимым образом уменьшит a на единицу.

Блокировки и барьеры

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

Задача критической секции

В этой задаче N процессов многократно повторяют сначала критическую а затем некритическую секции. Под критической секцией понимается последовательность операторов, содержащих работу с некоторым общим ресурсом, то есть работу, которую в один момент времени должен выполнять только один процесс. Задача состоит в том, чтобы разработать такие вход и выход из критической секции, которые удовлетворяют следующим свойствам:

  1. Взаимное исключение. Очевидное свойство, требующее того, что в каждый момент времени в секции находится только один процесс.
  2. Отсутствие взаимной блокировки. При желании входа в секцию несколькими потоками, хотя бы один это сделает.
  3. Отсутствие излишних задержек. Если процесс хочет войти в секцию и там нет других процессов, он это осуществит.
  4. Возможность входа. Процесс, который хочет войти в секцию, когда-нибудь сделает это.

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

Алгоритм Питерсона

Рассмотри вариант алгоритма, который решает задачу с двумя потоками. Его идея заключается в том, что при одновременной попытке процессов войти в критическую секцию, решение о том, какой из них это сделает, принимается на основе переменной (last), хранящей информацию о последнем покинувшем секцию потоке. Псевдокод алгоритма:

Настал момент обсудить как может быть реализован оператор await. Один из вариантов называется активное ожидание. Он заключается в том, что поток ждет своей очереди в пустом цикле, пока не будет выполнено условие синхронизации. Такой подход можно использовать и в C#, но это крайне не рекомендуется. Проблема в том, что активное ожидание не освобождается от времени CPU, а наоборот тратит ресурсы, заставляя думать, что делает полезную работу. Вместо этого лучше использовать метод Sleep(), который по-настоящему блокирует поток на заданное время. Напишем код метода для Питерсона на C# для одного потока с использованием гибридного подхода, который включает и активное ожидание и блокировку.

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

Алгоритм билета

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

В этом коде используется операция FA (Fetch and Add). Это операция реализована на многих машинах и выполняется неделимым образом. Она работает так: FA(var, incr):

Алгоритм поликлиники

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

Проверка (turn[i], i) > (turn[j], j) нужна для разрешения ситуации, когда так вышло, что у двух процессов оказался один и тот же номер очереди. В таком случае, мы сравниваем номера самих потоков. Именно это и означает такая запись.

Барьеры

Барьером называют точку в программе, преодолеть которую можно только дождавшись всех потоков. Такие конструкции часто встречаются в итеративных методах, требующих синхронизации по окончании каждой итерации. Возможность повторного использования — еще одно важное условие реализации барьера, так как, как правило, те же самые процессы будут преодолевать этот барьер на следующей итерации.

Синхронизация с управляющим процессом

Для начала решим эту задачу с использованием отдельного процесса для координации рабочих потоков. Реализация содержит два массива флагов, соответствующих процессам. Первый массив сигнализирует координатору, что потоки подошли к барьеру, а благодаря второму они узнают от координатора, что можно продолжать работу. Псевдокод алгоритма:

Проблема такого решения в том, что мы тратим отдельный поток на синхронизацию вместо того, чтобы использовать его для вычислений. Другая проблема заключается в том, что время преодоления каждого барьера пропорционально числу рабочих потоков, так как координатор обходит их в цикле. Для решения этих проблем можно использовать древовидную структуру оповещения потоков. Тогда время будет пропорционально логарифму от числа потоков, но возникнет новая проблема: разные потоки выполняют разную работу при достижении барьера. Поэтому мы рассмотрим еще один класс алгоритмов для реализации барьеров, решающий и эту проблему.

Симметричные барьеры

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

Теперь возникает задача расширения этой реализации на случай большего числа потоков. Для этого необходимо организовать систему связей, такую что в результате каждый из потоков знал, что все остальные тоже достигли барьера. Есть разные способы решения этой задачи. Рассмотрим два примера. Схема барьера-бабочки:

Схема барьера с распространением:

В языке C# для решения этой задачи существует класс Barrier. Для использования этого класса необходимо:

  1. Создать экземпляр, указав количество потоков, которые будут встречаться одновременно (можно изменить это значение позднее путем вызова методов AddParticipants() / RemoveParticipants()).
  2. Каждый поток, ожидающий встречи, должен вызвать метод SignalAndWait().

Семафоры

Семафоры нашли свое место во всевозможных библиотеках многопоточного и параллельного программирования, и сейчас мы разберемся какими их придумали теоретики когда-то давным давно (1962 г.).

Определение

Семафор — это обычная целочисленная неотрицательная переменная, с которой можно работать только с помощью двух специальных неделимых операций P и V. Для определения семафора используется ключевое слово sem. Пусть s — семафор, тогда операции P и V определяются следующим образом:

Семафоры изначально обеспечивают взаимное исключение, поэтому с их помощью можно проще решить уже рассмотренные задачи.

Критические секции

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

Здесь используются двоичный семафор, то есть семафор, который может принимать только два значения — ноль и один. Такие семафоры принято называть мьютексами (mutex).

Барьеры

Для организации барьера необходимо использовать массив мьютексов, по одному для каждого процесса. Операция V сигнализирует о достижении барьера потоком, а на операциях P он дожидается остальных. Рассмотрим пример кода для двух потоков:

Такую реализацию легко превратить в вариант с N потоками с помощью схем бабочки или распределения.

Очередь Производитель-Потребитель

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

Мы рассмотрим решение этой задачи, организовав кольцевой буфер (buf). Переменные front и rear хранят информацию об индексах первого сообщения в очереди и первой пустой ячейки после сообщения в конце очереди, соответственно. Обращение к индексам при записи и чтении элементов из буфера производится по модулю длины массива. Для понимания того, есть ли возможность писать и читать в буфер используются семафоры full и empty. Для организации же взаимного исключения для потоков одного типа применим мьютексы mutexD и mutexF.

Использование в современных языках

Почти в любом языке, поддерживающим многопоточность, есть такие конструкции как семафоры и мьютексы. Не является исключением и C#. Помимо того, что мьютекс является двоичным семафором, в языках программирования между этими двумя объектами есть еще одно отличие. Освободить мьютекс может только тот процесс, который его установил.

Класс Mutex языка C# имеет два основных метода для организации синхронизации между потоками. Метод WaitOne() получает блокировку, блокируя поток, если это необходимо. Для снятия блокировки используется метод ReleaseMutex(). На практике класс Mutex используется редко, так почти ту же функциональность предоставляет класс Monitor и конструкция lock (читай дальше).

Конструктор класса Semaphore имеет два параметра: вместимость потоков семафора и количество еще доступных мест. Аналогично мьютексу он имеет два важных синхронизирующих метода: WaitOne() и Release(). Semaphore с емкостью, равной единице, соответствует Mutex, за исключением того, что не имеет потока хозяина, то есть любой поток может вызвать Release() для семафора.

Реализовать паттерн Производитель-Потребитель на языке C# можно разными способами. По моему мнению наиболее простым и правильным будет использование класса BlockingCollection , который инкапсулирует все необходимое.

Мониторы

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

Синтаксис и семантика

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

  1. Взаимное исключение. Процедуры монитора по определению выполняются со взаимным исключением. Программисту не требуется заботиться об этом.
  2. Условные переменные. Этот новый тип данных (cond), который может принадлежать монитору. Каждая условная переменная по сути своей является очередью. При создании монитора такая очередь пуста. Она используется для приостановки потоков. В очередь добавляются потоки и ожидают сигнала для продолжения выполнения. Есть три основные операции для работы с условными переменными:
    1. empty(cv). Определяет пуста ли очередь условной переменной cv.
    2. wait(cv). Процесс блокируется на условной переменной cv.
    3. signal(cv). При вызове этого метода происходит проверка содержит ли очередь переменной cv потоки, и, в случае положительного результата, первый поток очереди будет освобожден.
  3. Порядок сигнализации. При вызове операции signal, поток находится в мониторе и “выпускает на свободу” еще другой поток. Так как монитор обеспечивает взаимное исключение, только один из них может продолжить выполнение. Для разрешения этого конфликта есть два пути:
    1. Сигнализировать и продолжить. Сигнализирующий процесс остается в мониторе, а извлеченный из очереди условной переменной отправляется в очередь потоков ожидающих на блокировке монитора.
    2. Сигнализировать и ожидать. В этом случае запускаемый процесс возвращается к выполнению своего кода, а процесс, который его запустил, возвращается на блокировку монитора.

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

Задача о читателях и писателях

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

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

Есть два вида процессов и два вида действий на процесс, поэтому получаем четыре процедуры. Они представлены в коде ниже. Также необходимо вести учет читающих и пишущих процессов — переменные nr и nv. Для условной блокировки потоков используются переменные oktowrite и oktoread.

Отмечу, что последняя процедура монитора использует метод signall_all() — одно из типичных расширений стандартных мониторов, позволяющее снять все потоки с условной переменной.

Реализация мониторов в C#

Класс Monitor языка C# достаточно точно отражает ту теорию, что была сегодня рассказана, за отличием того, что в этом мониторе используется лишь одна условная переменная. Как следствие просто разделяют две очереди — очередь готовности (входная) и очередь ожидания (на условной переменной).

Для входа в монитор используется метод Enter(), в который аргументом передается разделяемый ресурс, который хотим заблокировать. При выходе указывается метод Exit(), а метод Wait() отправляет поток в очередь ожидания. Для снятия потоков с этой очереди используются 2 метода — Pulse() и PulseAll(), которые соответствуют signal() и signal_all() в нашей нотации. Интересно, что для первого из них используется порядок “сигнализировать и ожидать”, но для второго “сигнализировать и продолжить” (в этом случае альтернатив нет).

Класс Monitor достаточно широко используем в языке C#, поэтому для операций входа и выхода был создан синтаксический сахар. В результате мы имеем конструкцию lock(), в которую передаем имя разделяемого ресурса, и в фигурных скобках после нее можем писать код, исполняющийся внутри монитора.

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

Заключение

Задачи и концепции, которые сегодня были рассмотрены, возникли достаточно давно (например, задача критической секции возникла в начале 60-х годов). Тем не менее, они регулярно встречаются в сегодняшней практике. Я считаю, что любой программист должен знать как решать эти задачи, а для того чтобы лучше понимать, почему современные средства для работы с многопоточностью работают именно так, можно обратиться к классической теории, на которой все основано. Для более плотного знакомства с темой: Основы многопоточного, параллельного и распределенного программирования. Г. Эндрюс.

P.S. Интересное наблюдение: чем ближе экзамен, тем длиннее пост…

Written on December 4th, 2020 by Alexey Kalina

Добавить комментарий