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

Введение. Проблема взаимоисключения

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

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

Операция Count++ не является атомарной. Код операции Count++ будет преобразован компилятором в машинный код, который выглядит примерно так:

(1) MOV EAX, [Count]  ;   значение из Count помещается в регистр 
(2) INC EAX      ;        значение регистра увеличивается на 1 
(3) MOV [Count], EAX ;    значение из регистра помещается обратно в Count

В мультипрограммной системе с разделением времени может наступить неблагоприятная ситуация перемешивания (interleaving'а), когда поток T₁ выполняет шаг (1), затем вытесняется потоком T₂ , который выполняет шаги (1)-(3), а уже после этого поток T₁ заканчивает операцию, выполняя шаги (2)-(3). В этом случае результирующее приращение переменной Count будет равно 1 вместо правильного приращения - 2.

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

Для устранения условий состязания необходимо обеспечить каждому потоку эксклюзивный доступ к разделяемым данным. Такой прием называется взаимоисключением (mutual exclusion). Часть кода потока, выполнение которого может привести к race condition, называется критической секцией (critical section). Например, операции (1)-(3) в примере, приведенном выше, являются критическими секциями обоих потоков. Таким образом, взаимоисключение необходимо обеспечить для критических секций потоков.

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

while (some condition) {	    
entry section	   
 critical section	   
 exit section	   
 remainder section
	}

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

Переменная-замок

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

shared int lock = 0;
 T1                                       T2
        while (some condition) {
         while(lock); 
         lock = 1;
                critical section
          lock = 0;
                remainder section
}

К сожалению, предложенное решение не всегда обеспечивает взаимоисключение. Вследствие того, что действие-пролог, состоящее из двух операций while(lock); lock = 1; не является атомарным, существует отличная от нуля вероятность вытеснения потока между этими операциями. При этом управление может перейти ко второму потоку, который, узнав, что переменная lock все еще равна 0, может войти в свою критическую секцию.

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

TSL команды

Многие вычислительные архитектуры имеют инструкции, которые могут обеспечить атомарность последовательности операций при входе в критическую секцию. Такие команды называются Test and_Set Lock или TSL командами. Если представить себе такую команду как функцию

int TSL (int *target){ 
int tmp = *target; 
*target = 1; 
return tmp; 
}

то, заменив в предыдущем примере последовательность операций while(lock); lock = 1; на TSL(lock), мы получаем решение проблемы взаимоисключения.

Семейство Interlocked-функций

Входящее в состав Win32 API семейство выполняющихся атомарно Interlocked-функций дает ключ к решению многих проблем синхронизации. Например, функция

LONG InterlockedExchangeAdd( PLONG plAddend, LONG lncrement);

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

InterlockedExchangeAdd (Count,  1);

В MSDN можно прочитать и про другие Interlocked-функции. Например, в качестве TSL инструкции, необходимой для решения проблемы входа в критическую секцию, можно применить функцию InterlockedCompareExchange.

Реализация Interlocked-функций зависит от аппаратной платформы. На x86-процессорах они выдают по шине аппаратный сигнал, закрывая для других процессоров конкретный адрес памяти.

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

Прогон программы синхронизации с помощью переменной замка

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

#include <windows.h>
#include <stdio.h>
#include <math.h>

int Sum = 0, iNumber=5, jNumber=300000;

DWORD WINAPI SecondThread(LPVOID){
  int i,j;
  double a,b=1.;
  
  for (i = 0; i < iNumber; i++)
  {
    for (j = 0; j < jNumber; j++)
    {
      Sum = Sum + 1;  a=sin(b);
    }
  }
  return 0;
}

void main(){
  int i,j;
  double a,b=1.;
  HANDLE  hThread;
  DWORD  IDThread;

  hThread=CreateThread(NULL, 0, SecondThread, NULL, 0, IDThread);
  if (hThread == NULL) return;    

  for (i = 0; i < iNumber; i++)
  {
    for (j = 0; j < jNumber; j++)
    {
      Sum = Sum - 1;  a=sin(b);
    }
	printf(" %d ",Sum);	
  }	  
	  
 WaitForSingleObject(hThread, INFINITE); // ожидание окончания потока SecondThread
 printf(" %d ",Sum);	
 }

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

Рекомендуется ввести в данную программу синхронизацию с помощью глобальной переменной-замка, включив в нее операции while(lock) ; и lock=1 ; и добиться предсказуемости в работе программы.

Поскольку ситуация, в которой квант времени, выделенный потоку, истекает между while(lock) ; и lock=1 ; маловероятна, можно смоделировать ее искусственно, введя между этими операциями паузу (функция Sleep, например). Наконец, желательно реализовать правильное решение путем опроса и модификации переменной замка с помощью TSL-инструкции (функция InterlockedCompareExchange ).

Спин-блокировка

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

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

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

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

Critical Sections

В составе API ОС Windows имеются специальные и эффективные функции для организации входа в критическую секцию и выхода из нее потоков одного процесса в режиме пользователя. Они называются EnterCriticalSection и LeaveCriticalSection и имеют в качестве параметра предварительно проинициализированную структуру типа CRITICAL_SECTION.

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

CRITICAL_SECTION cs; 
DWORD WINAPI SecondThread() 
{ 
 InitializeCriticalSection(cs);

EnterCriticalSection(cs); 
… критический участок кода
LeaveCriticalSection(cs); 
} 

main () 
{
InitializeCriticalSection(cs);
CreateThread(NULL, 0, SecondThread,…);


EnterCriticalSection(cs); 
… критический участок кода
LeaveCriticalSecLion(cs); 
DeleteCriticalSection(cs);
}

Функции EnterCriticalSection и LeaveCriticalSection реализованы на основе Interlocked-функций, выполняются атомарным образом и работают очень быстро. Существенным является то, что в случае невозможности входа в критический участок поток переходит в состояние ожидания. Впоследствии, когда такая возможность появится, поток будет "разбужен" и сможет сделать попытку входа в критическую секцию. Механизм пробуждения потока реализован с помощью объекта ядра "событие" (event), которое создается только в случае возникновения конфликтной ситуации.

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

Прогон программы

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

Синхронизация потоков с использованием объектов ядра

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

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

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

DWORD WaitForSingleObject(HANDLE hObject, DWORD dwMilliseconds);

где hObject - описатель ожидаемого объекта ядра, а второй параметр - максимальное время ожидания объекта.

Поток создает объект ядра при помощи семейства функций Create ( CreateSemaphore, CreateThread и т.д.), после чего объект посредством описателя становится доступным всем потокам данного процесса. Копия описателя может быть получена при помощи функции DuplicateHandle и передана другому процессу, после чего потоки смогут воспользоваться этим объектом для синхронизации.

Другим, более распространенным способом получения описателя является открытие существующего объекта по имени, поскольку многие объекты имеют имена в пространстве имен объектов. Имя объекта - один из параметров Create -функций. Зная имя объекта, поток, обладающий нужными правами доступа, получает его описатель с помощью Open -функций. Напомним, что в структуре, описывающей объект, имеется счетчик ссылок на него, который увеличивается на 1 при открытии объекта и уменьшается на 1 при его закрытии.

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

Семафоры

Известно, что семафоры, предложенные Дейкстрой в 1965 г., представляет собой целую переменную в пространстве ядра, доступ к которой, после ее инициализации, может осуществляться через две атомарные операции: wait и signal (в ОС Windows это функции WaitForSingleObject и ReleaseSemaphore соответственно).

wait(S):  если S <= 0 процесс блокируется 
   (переводится в состояние ожидания);    
              в противном случае S = S - 1;                               
signal(S):  S = S + 1

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

Ниже приведен пример синхронизации программы async с помощью семафоров.

#include <windows.h>
#include <stdio.h>
#include <math.h>

int Sum = 0, iNumber=5, jNumber=300000;
HANDLE hFirstSemaphore, hSecondSemaphore;

DWORD WINAPI SecondThread(LPVOID)
{
  int i,j;
  double a,b=1.;
    for (i = 0; i < iNumber; i++)
  {
    WaitForSingleObject(hSecondSemaphore, INFINITE); 
    for (j = 0; j < jNumber; j++)
    {
      Sum = Sum + 1;  a=sin(b); 
     }
    
     ReleaseSemaphore(hFirstSemaphore, 1, NULL);
    }
  return 0;
}

void main()
{
  int i,j;
  HANDLE  hThread;
  DWORD  IDThread;
  double a,b=1.;

  hFirstSemaphore = CreateSemaphore(NULL, 0, 1, "MyFirstSemaphore");
  hSecondSemaphore = CreateSemaphore(NULL, 1, 1, "MySecondSemaphore1");
  hThread=CreateThread(NULL, 0, SecondThread, NULL, 0, IDThread);
  if (hThread == NULL) return;    
  
  for (i = 0; i < iNumber; i++)
  {
	WaitForSingleObject(hFirstSemaphore, INFINITE);
        for (j = 0; j < jNumber; j++)
    {
      Sum = Sum - 1;  a=sin(b);
	}
    	printf(" %d ",Sum);	
	ReleaseSemaphore(hSecondSemaphore, 1, NULL);  
  }	  

WaitForSingleObject(hThread, INFINITE); // ожидание окончания потока SecondThread
CloseHandle(hFirstSemaphore);
CloseHandle(hSecondSemaphore);
printf(" %d ",Sum);	
return;
}

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

Мьютексы

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

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

События

Объекты "события" - наиболее примитивные объекты ядра. Они предназначены для информирования одного потока другим об окончании какой-либо операции. События создаются функцией CreateEvent. Простейший вариант синхронизации: переводить событие в занятое состояние функцией WaitForSingleObject и в свободное - функцией SetEvent.

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

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

Суммарные сведения об объектах ядра

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

В частности, существуют следующие свойства объектов:

Синхронизация в ядре

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

Одна из проблем связана с тем, что код ядра зачастую работает на приоритетных IRQL (уровни IRQL рассмотрены в лекции 3 ) уровнях "DPC/dispatch" или "выше", известных как "высокий IRQL". Это означает, что традиционные средства синхронизации, связанные с приостановкой потока, не могут быть использованы, поскольку процедура планирования и запуска другого потока имеет более низкий приоритет. Вместе с тем существует опасность возникновения события, чей IRQL выше, чем IRQL критического участка, который будет в этом случае вытеснен. Поэтому в подобных ситуациях прибегают к приему, который называется "запрет прерываний" , . В случае Windows этого добиваются, искусственно повышая IRQL критического участка до самого высокого уровня, используемого любым возможным источником прерываний. В результате критический участок может беспрепятственно выполнить свою работу.

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

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

В случае низких IRQL синхронизация осуществляется традиционным образом - при помощи объектов ядра.

Заключение

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