Программная реализация синхронизации
Сначала кратко поговорим о том, как же оператор await может быть реализован на практике. Фактически на однопроцессорной системе исполнение оператора await аналогично исполнению программы обработки прерывания. В этом случае сигнал прерывания можно рассматривать как оповещение о том, что логическое условие приняло значение "истина", а действие является программой обработки прерывания, которая своей первой командой запрещает прерывания. В мультипроцессорных системах нужно также обеспечить, чтобы контексты программ обработки прерываний не пересекались.
Теперь перейдем к частным случаям синхронизации, которые могут быть реализованы и без использования механизма обработки прерываний. Сначала рассмотрим условную синхронизацию, а затем проблему взаимного исключения.
Задача условной синхронизации
Для постановки этой задачи рассмотрим два потока thread_l и thread_2, которые работают следующим образом. Поток thread_1 выполняет некоторые действия, а затем ждет наступления события event, после которого выполняет другие действия. В свою очередь поток thread_2 также выполняет некоторые действия, а после их завершения оповещает поток thread_1 о наступлении события event. Затем поток thread_2 выполняет оставшиеся действия. Такая синхронизация работы потоков и называется задачей условной синхронизации.
Схематически программный код потоков thread_1 и thread_2, который решает поставленную задачу условной синхронизации, приведен ниже.
bool event = false; // событие event
void thread_l() // поток thread_l
{
actions_before_event(); // действия до наступления события
while(!event); // ждем, пока событие не произошло
actions_after_event(); // действия после наступления события
}
void thread_2() // поток thread_2
{
some_actions(); // действия, о которых оповещает событие
event = true; // отмечаем о наступлении события
other_actions(); // действия, происходящие после события
}
Рассматривая этот код, во-первых, заметим следующее — фактически наступление некоторого события равносильно выполнению некоторого действия. Поэтому событие часто и определяют как действие. В потоке thread_1 это действие обозначается функцией some_actions ().
Во-вторых, как видно из приведенного программного кода, для решения задачи условной синхронизации для двух потоков достаточно определить глобальную булеву переменную event, начальное значение которой установить в false. Затем в потоке thread_2 установить значение этой переменной в true после наступления события event. Тогда поток thread_1 ждет наступления события event посредством оператора while(!event), который циклически проверяет значение булевой переменной event до тех пор, пока эта переменная не примет значение true. Очевидно, что подобным образом задача условной синхронизации может быть решена и для произвольного количества потоков, ждущих наступления события event.
Задача взаимного исключения
Теперь рассмотрим задачу взаимного исключения. Чтобы упростить рассуждения, эта задача будет сформулирована только для двух параллельных потоков. Сначала предположим, что два параллельных потока работают с одним и тем же ресурсом, который в этом случае называется разделяемым или совместно используемым ресурсом. Далее считаем, что в каждом потоке программный код, который осуществляет доступ к этому ресурсу, заключен в свою критическую секцию. Тогда задача взаимного исключения для двух потоков может быть сформулирована следующим образом: обеспечить двум потокам взаимоисключающий доступ к некоторому совместно используемому ресурсу. Причем решение этой задачи должно удовлетворять следующим требованиям:
□ требование безопасности — в любой момент времени в своей критической секции может находиться только один поток;
□ требование поступательности — потоки не могут блокировать работу друг друга, ожидая разрешения на вход в критическую секцию;
□ требование справедливости — каждый поток получает доступ в критическую секцию за ограниченное время.
Ниже приведено простейшее из известных решений задачи взаимного исключения для двух потоков, которое было опубликовано Гэри Л. Петерсоном в 1981 году.
bool xl = false;
bool x2 = false;
int q; // номер потока, которому предоставляется очередь входа в
// критическую секцию
void thread_l() // поток thread_l
{
while(true)
{
non_critical_section_l(); // код вне критической секции
xl = true; // поток thread_l хочет войти в критическую секцию
q = 2; // предоставить очередь потоку thread_2
while(х2 && q == 2); // ждем, пока в критической секции находится
// поток thread_2
critical_section_l(); // входим в критическую секцию
xl = false; // поток thread_l находится вне критической секции
}
}
void thread_2() // поток thread_2
{
while(true)
{
non_critical_section_2(); // код вне критической секции
х2 = true; // поток thread_2 хочет войти в критическую секцию
q = 1; // предоставить очередь потоку thread_l
while(xl && q == 1); // ждем, пока в критической секции находится
// поток thread_l
critical_section_2(); // входим в критическую секцию
х2 = false; // поток thread_2 находится вне критической секции
Примитивы синхронизации
Примитивом синхронизации называется программное средство высокого уровня для решения задач синхронизации. Обычно примитивы синхронизации реализованы как объекты ядра операционной системы, которые предназначены для решения задач синхронизации потоков и процессов. В пользовательских программах доступ к примитивам синхронизации выполняется или посредством вызова функций, которые работают с объектами синхронизации, или при помощи специальных инструкций, которые встроены в язык программирования. Часто языки программирования, в которые встроены объекты синхронизации, называются языками системного программирования.
Мы рассмотрим реализацию примитивов синхронизации только для случая однопроцессорных систем. Поэтому непрерывность действий будем обеспечивать запрещением прерываний. Теперь перейдем непосредственно к реализации примитивов синхронизации. Для этих целей будем использовать символический код в стиле языка программирования C++, избегая при этом деталей реализации функций, которые затруднят изучение сути вопроса.
Во-первых, чтобы избежать "занятия активным ожиданием", будем блокировать исполнение потоков. Для этого с каждым примитивом синхронизации свяжем очередь заблокированных потоков. Ниже приведена спецификация такой очереди:
class Thread { /* ... */ }; // класс потоков
class ThreadQueue // класс очередей потоков
{
Thread* tp; // список потоков
void IncludeThreadToList(Threads t); // включить поток в список
Threads ExcludeThreadFromList(); // исключить поток из очереди
void SuspendThread(Threads t); // заблокировать поток
void ResumeThread(Threads t); // разблокировать поток
public:
ThreadQueue(): tp(NULL) {} // конструктор
-ThreadQueue() { /* очищаем список потоков */ } // деструктор
void EnqueueThread(Threads t) // поставить поток в очередь
{
IncludeThreadToList(t);
SuspendThread(t);
}
bool DequeueThread() // исключить поток из очереди
{
if(tp == NULL)
return false;
else
{
ResumeThread(ExcludeThreadFromList());
return true;
}
}
};
Теперь можно перейти к реализации примитивов синхронизации. Рассмотрим реализацию только двух примитивов синхронизации: condition (условие) и semaphore (семафор), наиболее часто встречающихся на практике. Другие примитивы синхронизации могут быть реализованы подобным им образом.
Критические секции
В операционных системах Windows проблема взаимного исключения для параллельных потоков, выполняемых в контексте одного процесса, решается при помощи объекта типа critical_section, который не является объектом ядра операционной системы. Для работы с объектами типа critical_section используются следующие функции:
// инициализация критической секции
VOID InitializeCriticalSection(LPCRITICAL_SECTION lpCriticalSection);
// вход в критическую секцию
VOID EnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection);
// попытка войти в критическую секцию
BOOL TryEnterCriticaisection(LPCRITICAL_SECTION lpCriticalSection);
// выход из критической секции
VOID LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection);
// разрушение объекта критическая секция
VOID DeleteCriticalSection(LPCRITICAL_SECTION lpCriticalSection);
Каждая из этих функций имеет единственный параметр, указатель на объект типа CRITICAL_SECTION. Все эти функции, за исключением TryEnterCriticaisection, не возвращают значения. Функция TryEnterCriticaisection возвращает ненулевое значение, если поток вошел в критическую секцию или уже находится в ней, в противном случае функция возвращает значение false. Отметим также, что функция TryEnterCriticaisection поддерживается только операционной системой Windows 2000.
Кратко рассмотрим порядок работы с этими функциями. Для этого предположим, что при проектировании программы мы выделили в параллельных потоках критические секции, в которых используется ресурс, разделяемый этими потоками. Тогда мы определяем в нашей программе объект типа critical_section и считаем, что имя этого объекта логически связано с используемым разделяемым ресурсом. Перед тем как начать работу с объектом типа critical_section, его необходимо инициализировать. Для этого и предназначена функция initiaiizecriticaisection. После инициализации нашего объекта типа critical_section мы в каждом из параллельных потоков пред входом в критическую секцию вызываем функцию Entercriticaisection, которая исключает одновременный вход в критические секции, выполняющиеся в параллельных потоках и связанные с нашим разделяемым ресурсом. После завершения работы с разделяемым ресурсом поток должен покинуть свою критическую секцию, что выполняется посредством вызов функции LeaveCriticalSection. После окончания работы с объектом типа critical_section необходимо освободить все системные ресурсы, которые использовались этим объектом. Для этой цели служит функция DeleteCriticalSection.