Файл: Оглавление Раздел I. Основные понятия.pdf

60 вующих во взаимодействии в цикле, последовательно выполняет четыре секции кода. white (1) {
< протокол входа – enter( )>;
< код в критической секции >;
< протокол выхода – leave( )>;
< код вне критической секции >;
}
Для решения задачи требуется выполнение четырех условий.
1. Процессы не должны находиться одновременно в критиче- ских секциях.
2. Не должно быть предположений о скорости выполнения процессов.
3. Процесс вне критической секции не должен блокировать другие процессы.
4. Если процесс начал выполнять протокол входа, то он рано или поздно должен войти в критическую секцию.
Решение задачи для двух процессов в алгоритме Петерсо-
на. С момента постановки задачи было предложено несколько ре- шений. В 1981 году Петерсон предложил наиболее компактный из известных вариантов решений задачи о критической секции для двух процессов. Он носит название алгоритм разрыва узла. Ниже показана последовательность синтеза этого алгоритма.
Для понимания сложности проблемы рассмотрим «наивный» алгоритм реализации протоколов входа и выхода из критической секции. int lock = 0 void enter( ) { while (lock != 0) /*ждем*/; lock = 1;
} void leave( ) { lock = 0; }
Очевидно, что такие протоколы не гарантируют выполнения условия взаимного исключения. Дело в том, что если два процесса одновременно будут выполнять проверку значения флага lock, то

61 они оба увидят разрешенное значение 0 и одновременно войдут в критическую секцию.
Поступим по-другому. Введем переменную turn, которая определяет очередь входа в критическую секцию. Если имеется два процесса, то пусть первый процесс входит в критическую секцию, если turn=0, а второй – если turn =1.
Этот способ обеспечивает выполнение условия взаимного ис- ключения. Однако не выполняется третье условие: остановившись вне критической секции, первый процесс заблокирует второй и наоборот.
Правильное решение совмещает оба подхода и выглядит сле- дующим образом. int turn = 0; int interested[2] = { FALSE, FALSE }; void enter( int process){ int other = 1–process; interested[process] = TRUE; turn = process; while(turn==process&& interested[other]==TRUE)/*ждем*/;
} void leave(int process){interested[process]=FALSE;}
Работа алгоритма основана на следующих заключениях. Мо- дификацию условий нужно выполнять до проверки, а не после. Для каждого из процессов нужно завести по флагу (массив interested).
Ненулевое значение флага свидетельствует о том, что соответству- ющий процесс готов войти в критический участок, поэтому каждый int turn = 0; while(TRUE){ while(turn!=0)/*ждем*/;
< критическая секция > turn = 1;
<вне критической секции>;
} while(TRUE){ while(turn!=1)/*ждем*/;
< критическая секция > turn = 0;
<вне критической секции>;
}

62 из процессов перед входом в критический участок должен выпол- нять проверку while (interested = = TRUE). Если два процесса одно- временно начинают выполнять проверку, то возникает тупик. Для разрешения тупика (разрыва узла) вводится вспомогательная пере- менная turn, которая в случае конфликта разрешает вход в критиче- скую секцию только одному процессу.

63 тинным. Тем не менее, поток не может войти в свою критическую секцию потому, что во время истинного значения условия входа по- ток не получает время процессора. Проблема решается введением задержек перед повторными попытками проверки условия входа.
Например, пусть два потока выполняют идентичный код и в началь- ный момент времени остановились на строке (1).
(1) while(1){
(2) while(InterlockedExchange(&x,1));
(3)
/*критическая секция*/
(4)
InterlockedExchange(&x,0)
(5) }
Когда первому потоку будет отведен квант времени, он в цик- ле выполняет строки (1)-(5). Так как строка (3) выполняется значи- тельно дольше, чем остальные строки, первый поток по истечении кванта остановится на ней. Далее квант времени выделяется второму потоку. Однако он в течение отводимого ему кванта сможет только выполнять цикл (2). Ситуация повторяется при каждом следующем обслуживании: второй поток не сможет войти в свою критическую секцию.
Ложное разделение. Еще один эффект связан с понижением быстродействия программы при неправильном объявлении пере- менных. Например, в объявлении, показанном ниже, две глобальные переменные объявлены вместе. Одна их них используется исключи- тельно в функции потока Thread1, а другая в функции потока
Thread2. volatile int x = 0;
// используется в Thread1( ) volatile int y = 0;
// используется в Thread2( )

64
Рис. 7.1. Переменные X и Y находятся в одной линии кэша, к ним невозможен одновременный доступ из разных процессоров
Потоки кажутся независимыми, однако это не так. Если поток
Thread1 выполняет операцию с переменной Х, поток Thread2 вы- нужден приостанавливать операцию с переменной Y и наоборот, из- за чего снижается быстродействие программы (рис. 7.1). Это проис- ходит потому, что для ускорения работы с памятью каждый из про- цессоров использует локальный кэш, однако загрузка значений в кэш производится не побайтно, а блоком. Обычно это участок памя- ти, выровненный по 32-байтной границе. Он называется кэш-линия.
Если две переменные попадают в одну кэш-линию, то эффект от ис- пользования кэш-памяти пропадает. Поэтому следует выравнивать переменные по границам кэш-линий или вводить фиктивные пере- менные, чтобы гарантировать, что переменные не попадут в одну кэш-линию.
Правильные объявления будут выглядеть следующим образом.
#define CACHE_LINE 32
#define CACHE_ALIGN __declspec(align(CACHE_LINE))
// используется в Thread1( ) volatile CACHE_ALIGN int x = 0;
// используется в Thread2( ) volatile CACHE_ALIGN int y = 0;
X
Y
ЦП 1
ЦП 2
X
Y
ОЗУ
Локальные кэши процес- соров
X
Y
X

65
Для того, чтобы избежать проблем, сопутствующих синхрони- зации с разделяемыми переменными при сохранении высокой ско- рости, в Windows реализована группа функций для организации критической секции. Функция InitializeCriticalSection используется для настройки структуры данных, служащей для управления крити- ческой секцией перед первым входом. Функция DeleteCriticalSection служит для перевода структуры управления критической секцией в исходное состояние. Функции EnterCriticalSection вместе с
TryEnterCriticalSection реализуют протокол входа в критическую секцию. Функция LeaveCriticalSection реализует протокол выхода из критической секции.
Дополнительно имеются функции
InitializeCriticalSectionAndSpinCount и SetCriticalSectionSpinCount для настройки числа попыток входа в критическую секцию перед переходом в режим ядра
(или возврата в случае
TryEnterCriticalSection).
Достоинством функций является высокое быстродействие.
Однако в них нельзя указать таймаут (аварийный выход через опре- деленное время), их нельзя применять для организации взаимодей- ствия между процессами, только для взаимодействия между потока- ми одного процесса. От этих недостатков свободны процедурные методы синхронизации.
Лекция 8. Процедурные методы синхронизации
в операционной системе Windows
Объекты синхронизации, функции ожидания. Управление объекта- ми ядра. События. Семафоры. Мьютексы. Пример задачи об ограни- ченном буфере.
Объекты синхронизации, функции ожидания. Процедурные методы синхронизации в Windows используются по отношению к объектам, реализованным в ядре операционной системы. Для такой синхронизации применяются только объекты ядра, которые могут находиться в сигнальном (свободном) и несигнальном (занятом) со- стоянии. К ним относятся рассмотренные ранее объекты: задания,

66 процессы, потоки. Эти объекты переходят в сигнальное состояние при завершении исполнения. Имеется группа объектов, используе- мых специально для синхронизации потоков и процессов, – это со- бытия, мьютексы, семафоры и таймеры. Отдельную группу образу- ют объекты, предназначенные для синхронизации ввода-вывода.
С точки зрения программиста все перечисленные объекты имеют общее свойство: их описатели можно использовать в функ- циях ожидания WaitForSingleObject, WaitForMultipleObject и неко- торых других. Если объект находится в несигнальном состоянии, то вызов функции ожидания с описателем объекта блокируется. Де- скриптор потока, который вызвал функцию, помещается в очередь этого объекта ядра, а сам поток переходит в состояние ожидания.
Когда объект ядра переходит в сигнальное состояние, выполняются действия, специфичные для данного типа объекта ядра. Например, может быть разблокирован один или все потоки, ожидающие на данном объекте ядра.
В функцию WaitForSingleObject передаются два параметра: описатель объекта и значение таймаута. Таймаут определяет пре- дельное время нахождения потока в блокированном состоянии. В функцию WaitForMultipleObjects передается массив описателей объ- ектов ядра. Для этого указывается адрес начала массива и количе- ство описателей в нем. Также указывается параметр, определяющий семантику ожидания на группе описателей: можно ждать перехода всех объектов ядра в сигнальное состояние или какого-то одного объекта. Указывается также таймаут.
При возврате из функции ожидания обычно требуется опреде- лить причину завершения функции. В случае ошибки функция воз- вращает значение WAIT_FAILED. Для уточнения состояния ошибки далее используют GetLastError и другие функции. В случае заверше- ния по таймауту возвращается значение WAIT_TIMEOUT. Если причиной возврата является переход в сигнальное состояние, воз- вращается значение WAIT_OBJECT_0.
Если выполняется ожидание на функции WaitForMultipleObjects, то, чтобы узнать, какой именно объект перешел в сигнальное состо- яние, нужно проверить, что значение, возвращенное функцией, не равно WAIT_FAILED и WAIT_TIMEOUT и вычесть из него кон- станту WAIT_OBJECT_0. В результате мы получим индекс описате-

67 ля объекта, перешедшего в сигнальное состояние, в массиве описа- телей, переданном в функцию WaitForMultipleObject.
Управление объектами ядра. Рассмотрим операции, относя- щиеся как к объектам, использующимся в функциях ожидания, так и к другим объектам ядра в операционной системе Windows.
Для создания объектов ядра используются индивидуальные для каждого объекта функции, имеющие префикс Create. Например, мьютекс может быть создан вызовом
HANDLE mutex=CreateMutex(NULL, FALSE, NULL).
Обычно первым параметром всех функций, создающих объек- ты ядра, является структура атрибутов безопасности, а последним – имя объекта.
Закрытие описателя любого объекта ядра выполняется вызо- вом функции CloseHandle.
Чтобы понять принцип работы функции, рассмотрим более детально, что представляет собой описатель объекта ядра (рис.8.1).
Для каждого процесса в ядре операционной системы создается таблица описателей. Запись в таблице содержит некоторые атрибуты описателя и указатель на объект ядра. На один и тот же объект ядра могут указывать несколько описателей – возможно из таблиц описа- телей разных процессов. В любом объекте ядра имеется специаль- ный атрибут для подсчета ссылок на объект. Значение описателя, используемое в адресном пространстве процесса, – это смещение на запись в таблице описателей процесса.
Рис. 8.1.Описатель объекта ядра в Windows
2 ссылки
Описатель –
HANDLE
Счетчик ссылок
Объект ядра
Таблица объектов ядра процесса