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

Размещено на http://www.allbest.ru/

ДИПЛОМНАЯ РАБОТА

на тему: «Синхронизация потоков»

Глава 1. Синхронизация потоков

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

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

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

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

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

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

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

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

На рис. 8.1 показано, что может случиться, когда две несинхронизированные потоки разделяют общий ресурс, например ячейку памяти. Оба потока увеличивают значение переменной N на единицу, но в силу специфики очередности, в которой могут выполняться потоки, окончательное значение N равно 5, тогда как правильным значением является 6. Заметьте, что представленный здесь частный результат не обладает ни повторяемостью, ни предсказуемостью; другая очередность выполнения потоков могла бы привести к правильному результату. В SMP-системах эта проблема еще более усугубляется.

Размещено на http://www.allbest.ru/

Рис. 8.1. Разделение общей памяти несинхронизированными потоками

Критические участки кода

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

Основная проблема состоит в том, что имеется критический участок кода (critical section) (в данном примере -- код, который увеличивает N на 1), характеризующийся тем, что если один из потоков приступил к его выполнению, то никакой другой поток не должен входить в данный код до тех пор, пока его не покинет первый поток. Проблему критических участков кода можно считать разновидностью проблемы состязаний, поскольку первый поток "состязается" со вторым потоком в том, чтобы завершить выполнения критического участка еще до того, как его начнет выполнять любой другой поток. Таким образом, мы должны так синхронизировать выполнение потоков, чтобы можно было гарантировать, что в каждый момент времени код будет выполняться только одним потоком.

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

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

while (Flag) Sleep (1000);

Flag = TRUE;

N++;

Flag = FALSE;

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

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

DWORD WINAPI ThFunc(TH_ARGS pArgs) {

volatile DWORD N;

… N++; …

}

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

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

Класс памяти volatile

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

Функции взаимоблокировки

Если все, что требуется -- это увеличение, уменьшение или обмен значениями переменных, как в нашем первом простом примере, то функций взаимоблокировки (interlocked functions) вам будет вполне достаточно. Функции взаимоблокировки проще в использовании, обеспечивают более высокое быстродействие по сравнению с другими возможными методами и не приводят к блокированию потоков. Двумя членами этого семейства функций, которые представляют для нас интерес, являются функции InterlockedIncrement и InterlockedDecrement. Обе функции применяются по отношению к 32-битовым целым числам со знаком.

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

Задача инкрементирования N, представленная на рис. 8.1, может быть реализована посредством единственной строки кода:

InterlockedIncrement(&N);

N -- это целое число типа long со знаком, и функция возвращает его новое значение, несмотря на то, что другой поток мог изменить значение N еще до того, как поток, вызвавший функцию InterlockedIncrement, успеет воспользоваться возвращенным значением.

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

Локальная и глобальная память

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

DWORD N;

DWORD WINAPI ThFunc (TH_ARGS pArgs) {

…

N = 2 * pArgs->Count; …

}

Резюме: безопасный многопоточный код

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

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

2. В тех случаях, когда функцию могут вызывать несколько потоков, а какой-либо специфический для состояния потока параметр, например счетчик, должен сохранять свое значение в течение промежутков времени, отделяющих один вызов функции от другого, значение параметра состояния должно храниться в TLS или в структуре данных, выделенной специально для этого потока, например, в структуре данных, передаваемой потоку при его создании. Использовать стек для сохранения постоянно хранимых (persistent) значений не следует. Применение необходимой методики при построении безопасных многопоточных DLL иллюстрируют программы 12.4 и 12.5.

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

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

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

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

Объекты синхронизации потоков

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

1. Поток, выполняющийся в контексте одного процесса, может дожидаться завершения другого процесса с использованием функции ExitProcess путем применения к дескриптору процесса функций ожидания WaitForSingleObject или WaitForMultipleObject. Тем же способом поток может организовать ожидание завершения (с помощью функции ExitThread или выполнения оператора return) другого потока.

2. Блокировки файлов, предназначенные для частного случая синхронизации доступа к файлам.

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

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

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

Предостережение

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

Рассмотрение двух других объектов синхронизации -- таймеров ожидания и портов завершения ввода/вывода -- отложено до главы 14. Эти типы объектов требуют использования методик асинхронного ввода/вывода Windows, которые описываются в указанной главе.

Объекты критических участков кода

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

В качестве простого механизма реализации и применения на практике концепции критических участков кода Windows предоставляет объект CRITICAL_SECTION.

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

Для инициализации и удаления переменной типа CRITICAL_SECTION используются, соответственно, функции InitializeCriticalSection и DeleteCriticalSection:

VOID InitializeCriticalSection(LPCRITICAL_SECTION lpCriticalSection)

VOID DeleteCriticalSection(LPCRITICAL_SECTION lpCriticalSection)

Функция EnterCriticalSection блокирует поток, если на данном критическом участке кода присутствует другой поток. Ожидающий поток разблокируется после того, как другой поток выполнит функцию LeaveCriticalSection. Говорят, что поток получил права владения объектом CS, если произошел возврат из функции EnterCriticalSection, тогда как для уступки прав владения используется функция LeaveCriticalSection. Всегда следите за своевременной переуступкой прав владения объектами CS; несоблюдение этого правила может привести к тому, что другие потоки будут пребывать в состоянии ожидания в течение неопределенного времени даже после завершения выполнения потока-владельца.

Мы часто будем говорить о блокировании и разблокировании объектов CS, а вхождение в CS будет означать то же, что и блокирование CS.

VOID EnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection)

VOID LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection)

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

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

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

BOOL TryEnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection)

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

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

Настройка спин-счетчика

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

Для настройки счетчика занятости, или спин-счетчика (spin-count), предназначены две функции, одна из которых, SetCriticalSectionSpinCount, обеспечивает динамическую настройку счетчика, а вторая, InitializeCritical-SectionAndSpinCount, выступает в качестве замены функции Initialize-CriticalSection. Настройка спин-счетчика рассматривается в главе 9.

Использование объектов CRITICAL_SECTION для защиты разделяемых переменных

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

- Общее количество полученных запросов.

- Общее количество отправленных ответов.

- Количество запросов, обрабатываемых в настоящее время всеми потоками сервера.

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

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

CRITICAL_SECTION cs1;

volatile DWORD N = 0, М;

/* N -- глобальная переменная, разделяемая всеми потоками. */

InitializeCriticalSection (&cs1);

…

EnterCriticalSection (&cs1);

if (N < N_MAX) { M = N; M += 1; N = M; }

LeaveCriticalSection (&cs1);

…

DeleteCriticalSection (&cs1);

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

Программа 8.1 демонстрирует, насколько полезными могут быть объекты CS.

Пример: простая система "производитель/потребитель"

Программа 8.1 иллюстрирует, насколько полезными могут быть объекты CS. Кроме того, эта программа демонстрирует, как создаются защищенные структуры данных для хранения состояний объектов, и знакомит с понятием инварианта (invariant) -- свойства состояния объекта, относительно которого гарантируется (путем соответствующей реализации программы), что оно будет истинным за пределами критического участка кода.

Рис. 8.2. Разделение общей памяти синхронизированными потоками

Описание задачи приводится ниже.

- Имеются два потока, производитель (producer) и потребитель (consumer), работающие в полностью асинхронном режиме.

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

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

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

- В качестве средства контроля целостности данных производитель вычисляет простую контрольную сумму[28] данных таблицы, которая далее сравнивается с аналогичной суммой, вычисленной потребителем, дабы удостовериться в том, что данные не были повреждены при их передаче из одного потока в другой. Данные, полученные при обращении к таблице в моменты ее обновления, будут недействительными; использование объектов CS гарантирует, что этого никогда не произойдет. Инвариантом блока сообщения (message block invariant) является корректность контрольной суммы для содержимого текущего сообщения.

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

Программа 8.1.simplePC: простая система "производитель/потребитель"

/* Глава 8. simplePC.с */

/* Поддерживает два потока -- производителя и потребителя. */

/* Производитель периодически создает буферные данные с контрольными */

/* суммами, или "блоки сообщений", отображаемые потребителем по запросу */

/* пользователя. */

#include "EvryThng.h"

#include

#define DATA_SIZE 256

typedef struct msg_block_tag { /* Блок сообщения. */

volatile DWORD f_ready, f_stop; /* Флаги готовности и прекращения сообщений. */

volatile DWORD sequence; /* Порядковый номер блока сообщения. */

volatile DWORD nCons, nLost;

time_t timestamp;

CRITICAL_SECTION mguard; /* Структура защиты блока сообщения. */

DWORD checksum; /* Контрольная сумма содержимого сообщения. */

DWORD data[DATA_SIZE]; /* Содержимое сообщения. */

} MSG_BLOCK;

/* Одиночный блок, подготовленный к заполнению новым сообщением. */

MSG_BLOCK mblock = { 0, 0, 0, 0, 0 };

DWORD WINAPI produce(void*);

DWORD WINAPI consume(void*);

void MessageFill(MSG_BLOCK*);

void MessageDisplay(MSG_BLOCK*);

DWORD _tmain(DWORD argc, LPTSTR argv[]) {

DWORD Status, ThId;

HANDLE produce h, consume_h;

/* Инициализировать критический участок блока сообщения. */

InitializeCriticalSection (&mblock.mguard);

/* Создать два потока. */

produce_h = (HANDLE)_beginthreadex(NULL, 0, produce, NULL, 0, &ThId);

consume_h = (HANDLE)_beginthreadex (NULL, 0, consume, NULL, 0, &ThId);

/* Ожидать завершения потоков производителя и потребителя. */

WaitForSingleObject(consume_h, INFINITE);

WaitForSingleObject(produce_h, INFINITE);

DeleteCriticalSection(&mblock.mguard);

_tprintf(_T("Потоки производителя и потребителя завершили выполнение\n"));

_tprintf(_T("Отправлено: %d, Получено: %d, Известные потери: %d\n"), mblock.sequence, mblock.nCons, mblock.nLost);

return 0;

}

DWORD WINAPI produce(void *arg)

/* Поток производителя -- создание новых сообщений через случайные */

/* интервалы времени. */

{

srand((DWORD)time(NULL)); /* Создать начальное число для генератора случайных чисел. */

while (!mblock.f_stop) {

/* Случайная задержка. */

Sleep(rand() / 100);

/* Получить и заполнить буфер. */

EnterCriticalSection(&mblock.mguard);

__try {

if (!mblock.f_stop) {

mblock.f_ready = 0;

MessageFill(&mblock);

mblock.f_ready = 1;

mblock.sequence++;

}

} __finally { LeaveCriticalSection (&mblock.mguard); }

}

return 0;

}

DWORD WINAPI consume (void *arg) {

DWORD ShutDown = 0;

CHAR command, extra;

/* Принять ОЧЕРЕДНОЕ сообщение по запросу пользователя. */

while (!ShutDown) { /* Единственный поток, получающий доступ к стандартным устройствам ввода/вывода. */

_tprintf(_T("\n**Введите 'с' для приема; 's' для прекращения работы: "));

_tscanf("%c%c", &command, &extra);

if (command == 's') {

EnterCriticalSection(&mblock.mguard);

ShutDown = mblock.f_stop = 1;

LeaveCriticalSection(&mblock.mguard);

} else if (command == 'c') { /* Получить новый буфер для принимаемых сообщений. */

EnterCriticalSection(&mblock.mguard);

__try {

if (mblock.f_ready == 0) _tprintf(_T("Новые сообщения отсутствуют. Повторите попытку.\n"));

else {

MessageDisplay(&mblock);

mblock.nCons++;

mblock.nLost = mblock.sequence - mblock.nCons;

mblock.f_ready = 0; /* Новые сообщения отсутствуют. */

}

} __finally { LeaveCriticalSection (&mblock.mguard); }

} else {

tprintf(_T("Такая команда отсутствует. Повторите попытку.\n"));

}

}

return 0;

}

void MessageFill(MSG_BLOCK *mblock) {

/* Заполнить буфер сообщения содержимым, включая контрольную сумму и отметку времени. */

DWORD i;

mblock->checksum = 0;

for (i = 0; i < DATA_SIZE; i++) {

mblock->data[i] = rand();

mblock->checksum ^= mblock->data[i];

}

mblock->timestamp = time(NULL);

return;

}

void MessageDisplay(MSG_BLOCK *mblock) {

/* Отобразить буфер сообщения, отметку времени и контрольную сумму. */

DWORD i, tcheck = 0;

for (i = 0; i < DATA_SIZE; i++) tcheck ^= mblock->data[i];

_tprintf(_T("\nВремя генерации сообщения № %d: %s"), mblock->sequence, _tctime(&(mblock->timestamp)));

_tprintf(_T("Первая и последняя записи: %х %х\n"), mblock->data[0], mblock->data[DATA_SIZE - 1]);

if (tcheck == mblock->checksum) _tprintf(_T("УСПЕШНАЯ ОБРАБОТКА ->Контрольная сумма совпадает.\n"));

else tprintf(_T("СБОЙ ->Несовпадение контрольной суммы. Сообщение запорчено.\n"));

return;

}

Комментарии, к примеру, простой системы "производитель/потребитель"

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

- Объект CRITICAL_SECTION является частью объекта (блока сообщения), защиту которого он обеспечивает.

- Каждый доступ к сообщению осуществляется на критическом участке кода.

- Типом переменных, доступ к которым осуществляется разными потоками, является volatile.

- Использование обработчиков завершения гарантирует, что объекты CS будут обязательно освобождены. Хотя в данном случае эта методика и не является для нас существенной, она дополнительно гарантирует, что вызов функции LeaveCriticalSection не будет случайно опущен впоследствии при изменении кода программы. Имейте также в виду, что обработчик завершения ограничен использованием средств С, и его не следует использовать совместно с C++.

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

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

- Одним из инвариантных свойств, которые гарантируются этой программой, является то, что контрольная сумма блока сообщения будет всегда корректной вне критических участков кода. Другим инвариантным свойством является следующее: 0 <= nLost + nCons <= sequence

Об этом важном свойстве далее еще будет идти речь.

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

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

Мьютексы Объект взаимного исключения (mutual exception), или мьютекс (mutex), обеспечивает более универсальную функциональность по сравнению с объектом CRITICAL_SECTION. Поскольку мьютексы могут иметь имена и дескрипторы, их можно использовать также для синхронизации потоков, принадлежащих различным процессам. Так, два процесса, разделяющие общую память посредством отображения файлов, могут использовать мьютексы для синхронизации доступа к разделяемым областям памяти.

Объекты мьютексов аналогичны объектам CS, однако, дополнительно к возможности их совместного использования различными процессами, они допускают конечные периоды ожидания, а мьютексы, покинутые (abandoned) завершающимся процессом, переходят в сигнальное состояние.[29] Поток приобретает права владения мьютексом (или блокирует (block) мьютекс) путем вызова функции ожидания (WaitForSingleObject или WaitForMultipleObjects) по отношению к дескриптору мьютекса и уступает эти права посредством вызова функции ReleaseMutex.

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

При работе с мьютексами мы будем пользоваться функциями CreateMutex, ReleaseMutex и OpenMutex.

HANDLE CreateMutex(LPSECURITY_ATTRIBUTES lpsa, BOOL bInitialOwner, LPCTSTR lpMutexName)

BOOL ReleaseMutex(HANDLE hMutex)

bInitialOwner -- если значение этого флага установлено равным True, вызывающий поток немедленно приобретает права владения новым мьютексом. Эта атомарная операция позволяет предотвратить приобретение прав владения мьютексом другими потоками, прежде чем это сделает поток, создающий мьютекс. Как следует из самого его названия (initial owner -- исходный владелец), этот флаг не оказывает никакого действия, если мьютекс уже существует.

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

Возвращаемое значение имеет тип HANDLE; значение NULL указывает на неудачное завершение функции.

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

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

BOOL ReleaseMutex(HANDLE hMutex)

Спецификация POSIX Pthreads поддерживает мьютексы. Имеются следующие основные функции:

- pthread_mutex_init

- pthread_mutex_destroy

- pthread_mutex_lock

- pthread_mutex_unlock

Функция pthread_mutex_lock является блокирующей и поэтому эквивалентна функции WaitForSingleObject в случае ее применения к дескриптору мьютекса. Функция pthread_mutex_trylock осуществляет опрос и не является блокирующей, соответствуя функции WaitForSingleObject в случае ее применения с нулевым значением интервала ожидания. Потоки Pthreads не поддерживают конечные интервалы ожидания и не предлагают средств, аналогичных Windows-объектам CRITICAL_SECTION.

Покинутые мьютексы

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

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

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

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

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

- Имеется два связных списка, список А и список В, каждый из которых содержит идентичные структуры и поддерживается рабочими потоками.

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

- В других ситуациях допускается нахождение элемента только в одном из списков, но не в обоих одновременно. Мотивация. Указанными списками могут быть списки сотрудников отделов А и В, когда некоторым сотрудникам разрешена работа одновременно в двух отделах.

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

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

static struct {

/* Инвариант: действительность списка. */

HANDLE guard; /* Дескриптор мьютекса. */

struct ListStuff;

} ListA, ListB;

…

DWORD WINAPI AddSharedElement(void *arg) /* Добавляет общий элемент в списки А и В. */

{ /* Инвариант: новый элемент либо находится в обоих списках, либо не находится ни в одном из них. */

WaitForSingleObject(ListA.guard, INFINITE);

WaitForSingleObject(ListB.guard, INFINITE);

/* Добавить элемент в оба списка … */

ReleaseMutex(ListB.guard);

ReleaseMutex(ListA.guard);

return 0;

}

DWORD WINAPI DeleteSharedElement(void *arg) /* Удаляет общий элемент из списков А и В. */

{

WaitForSingleObject(ListB.guard, INFINITE);

WaitForSingleObject(ListA.guard, INFINITE);

/* Удалить элемент из обоих списков … */

ReleaseMutex(ListB.guard);

ReleaseMutex(ListA.guard);

return 0;

}

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

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

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

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

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

Сравнительный обзор: мьютексы и объекты CRITICAL_SECTION

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

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

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

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

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

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

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

Синхронизация куч

В NT для синхронизации доступа к кучам (глава 5) предусмотрены две функции -- HeapLock и HeapUnlock. В каждой из этих функций единственным аргументом является дескриптор. Эти функции удобно применять в тех случаях, когда используется флаг HEAP_NO_SERIALIZE, или когда потоку необходимы права исключительного доступа к куче.

Семафоры

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

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

К функциям управления семафорами относятся CreateSemaphore, OpenSemaphore и ReleaseSemaphore, причем последняя функция может инкрементировать значение счетчика на 1 и более. Эти функции аналогичны своим эквивалентам, предназначенным для управления мьютексами.

HANDLE CreateSemaphore(LPSECURITY_ATTRIBUTES lpsa, LONG lSemInitial, LONG lSemMax, LPCTSTR lpSemName)

Параметр lSemMax, значение которого должно быть равным, по крайней мере, 1, определяет максимально допустимое значение счетчика семафора. Параметр lSemInitial -- начальное значение этого счетчика, которое должно удовлетворять следующему условию: 0? lSemInitial? lSemMax и никогда не должно выходить за пределы указанного диапазона. Возвращение функцией значения NULL указывает на ее неудачное выполнение.

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

BOOL ReleaseSemaphore(HANDLE hSemaphore, LONG cReleaseCount, LPLONG lpPreviousCount)

Обратите внимание на возможность получения предыдущего значения счетчика, определяемого указателем lpPreviousCount, которое он имел до освобождения объекта синхронизации при помощи функции ReleaseSemaphore, но если необходимости в этом нет, то значение упомянутого указателя следует установить равным NULL.

Число, прибавляемое к счетчику семафора (cReleaseCount), должно быть больше 0, но если выполнение функции ReleaseSemaphore приводит к выходу значения счетчика за пределы допустимого диапазона, то она завершается с ошибкой, возвращая значение FALSE, а значение счетчика семафора остается неизменным. Предыдущим значением счетчика следует пользоваться с осторожностью, поскольку оно могло быть изменено другими потоками. Кроме того, невозможно определить, достиг ли счетчик максимально допустимого значения, поскольку не предусмотрено средство, отслеживающее увеличение счетчика в результате его освобождения. Пример использования предыдущего значения счетчика семафора приведен на Web-сайте книги.

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

Использование семафоров

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

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

Опасность возникновения условий состязаний в программе sortMT (программа 7.2) иллюстрирует другое возможное применение семафоров, связанное с управлением точным количеством потоков, которые должны находиться в пробужденном состоянии. Можно создать все потоки, не приостанавливая их. После этого все они сразу же переходят к ожиданию перехода в сигнальное состояние семафора, инициализированного значением 0. Далее, главный поток вместо того, чтобы освобождать потоки, просто вызывает функцию ReleaseCount с увеличением счетчика, например, на 4 (или на любое другое значение, соответствующее количеству потоков), в результате чего возможность выполняться получат четыре потока.

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

Ограниченность семафоров

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

/* hsem - дескриптор семафора. Максимальное значение счетчика семафора равно 2. */

…

/* Уменьшить значение счетчика семафора на 2. */

WaitForSingleObject(hSem, INFINITE);

WaitForSingleObject(hSem, INFINITE);

…

/* Увеличить значение счетчика семафора на 2. */

ReleaseSemaphore(hSem, 2, &PrevCount);

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

...