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

68
При закрытии описателя происходит модификация атрибута, указывающего на то, что запись теперь недействительна. Далее про- исходит декремент счетчика ссылок у объекта. Если значение счет- чика ссылок достигает нуля, происходит удаление объекта из памяти ядра операционной системы.
Важное преимущество объектов ядра – возможность их ис- пользования для синхронизации потоков, принадлежащих разным процессам. Для этой цели нужно уметь передавать описатели объек- тов между процессами. Их можно передавать путем наследования, именования и дублирования.
При наследовании вначале необходимо модифицировать атри- бут наследования в таблице описателей процесса. Это можно сде- лать непосредственно при создании описателя, как показано ниже.
SECURITY_ATTRIBUTE sa; sa.nlength = sizeof(sa); sa.lpSecurityDescriptor=NULL; /*NULL – защита по умол- чанию; определяет, кто может пользоваться объектом
(при NULL – создатель процесса и администраторы) */ sa.bInheritHandle=TRUE; /*наследовать описатель*/
HANDLE hMutex = CreateMutex (&sa, FALSE, NULL);
Можно воспользоваться функциями GetHandleInformation и
SetHandleInformation для изменения атрибутов описателя уже после создания объекта ядра.
Наследование описателей происходит следующим образом
(рис. 8.2). При создании процесса функцией CreateProcess для него создается новая таблица описателей. В эту таблицу копируются все записи родительского процесса, имеющие атрибут наследования.
Записи помещаются по тем же смещениям, по которым размещались исходные записи родительского процесса. Для каждой скопирован- ной записи производится инкремент счетчика ссылок у связанного с ней объекта ядра.
Дочерний процесс может использовать ссылки на унаследо- ванные объекты ядра. Для передачи значений унаследованных опи- сателей в дочерний процесс обычно используется командная строка или переменные окружения. Если дочерний процесс уже создан, то нельзя воспользоваться механизмом наследования.

69
Рис. 8.2. Схема наследования описателя в Windows
При создании объекта ядра может быть указано его имя:
HANDLE mutex = CreateMutex(NULL, FALSE, “SomeMutex”);.
В данном случае любой процесс может получить доступ к
объекту ядра по имени, если такой доступ разрешен настройками безопасности. При повторном вызове функции Create проводится проверка: имеется ли объект ядра с данным именем и типом. Если объект с таким именем и типом уже существует, то функция не со- здает новый объект, а возвращает описатель существующего объек- та (при этом остальные параметры в вызове игнорируются). При необходимости можно проверить, создан ли объект ядра или полу- чен описатель ранее созданного объекта: if(GetLastError()==ERROR_ALREADY_EXISTS){
/*если создан ранее*/
}.
Механизм ссылки на объекты ядра подходит для всех случаев взаимодействия, когда можно определить соглашения на имена со- здаваемых объектов. Этот механизм также часто используется для контроля количества запущенных экземпляров приложения.
Универсальным способом передачи описателей объектов ядра между процессами является дублирование описателей. Дублирова- ние выполняется функцией DuplicateHandle:
2 ссылки
2.Увеличение счетчика ссы- лок
1.Копирование записи с сохранением смещения
Handle1
Handle2 =
Handle1

70
BOOL DuplicateHandle(
HANDLE hSourceProcessHandle,/*описатель исходного процесса*/
HANDLE hSourceHandle,
/*дублируемый описатель процесса-источника*/
HANDLE hTargetProcessHandle, /*процесс-приемник*/
PHANDLE phTargetHandle,
/*описатель в процессе- приемнике*/
DWORD dwDesiredAccess,
/*настройка атрибутов дублируемого описателя*/
DWORD dwQptions.
В дублировании принимают участие (в общем случае) три про- цесса: процесс, выполняющий дублирование, процесс – источник и процесс – приемник. Если источником или приемником является управляющий процесс, то вместо соответствующего описателя поме- щается вызов функции GetCurrentProcess. Особенностью дублирова- ния является то, что необходимо использовать механизм межпро- цессного взаимодействия для передачи продублированного описателя в процесс – приемник. Функция DuplicateHandle его сформирует, но нужно также поставить в известность сам процесс – приемник о том, что в его таблицу описателей добавлен новый описатель.
Теперь рассмотрим объекты синхронизации и специфические для каждого объекта функции процедурной синхронизации.
События используются при реализации кооперативной син- хронизации, когда один поток ждет поступления данных от другого.
При наступлении события объект переходит в сигнальное состояние.
Если событие не наступило – находится в несигнальном состоянии.
В зависимости от того, каким образом осуществляется перевод со- бытия в несигнальное состояние, существуют два типа событий: со- бытие со сбросом вручную и событие с автоматическим сбросом.
Оба типа объектов создаются функцией CreateEvent:
HANDLE CreateEvent(
PSECURITY_ATTRIBUTES sa,/*атрибуты безопасности*/
BOOL fManualReset,/*тип объекта TRUE – со сбросом вручную*/
BOOL fInitialState,/*начальное состояние события*/
LPCTSTR name);/*имя события*/.

71
Для управления событием используются следующие функции:
SetEvent – устанавливает событие в сигнальное состояние; ResetEvent – устанавливает событие в несигнальное состояние; PulseEvent – уста- навливает в сигнальное состояние и сбрасывает в несигнальное.
Функция PulseEvent выполняет разблокирование потоков, если таковые имеются в момент ее вызова. События с автоматическим сбросом целесообразно использовать, если происходит периодиче- ское ожидание завершения события. В данном случае вместо ком- бинации вызовов WaitForSingleObject/ResetEvent достаточно ис- пользовать один вызов WaitForSingleObject.
Семафоры – универсальные объекты процедурной синхрони- зации, предложены Э. Дейкстра. Семафоры выполняют роль счет- чика числа доступных ресурсов. С семафорами определены две опе- рации. Для возврата ресурсов в пул доступных ресурсов использует- ся операция увеличения счетчика (up-операция или V-операция).
Для захвата ресурсов используется операция уменьшения счетчика
(down-операция или P-операция). Если счетчик ресурсов принимает значение ноль, то поток блокируется до тех пор, пока ресурс не бу- дет возвращен в пул другим потоком с использованием up или V- операции. В любой момент счетчик не может быть больше макси- мального числа ресурсов и меньше нуля.
Семафор создается при помощи функции CreateSemaphore:
HANDLE CreateSemaphore(
PSECURITY_ATTRIBUTES sa, /*атрибуты безопасности*/
LONG lInitialCount,/*начальное значение счетчика
(ресурсов)*/
LONG lMaxCount,/*предельное значение счетчика
(ресурсов)*/
LPCTSTR name);/*имя семафора*/.
Инкремент счетчика семафора выполняется при помощи вы- зова функции BOOL ReleaseSemaphore (HANDLE, LONG Re- leaseCount,
LPLONG lpPreviousCount). В ней, в отличие от абстракт- ных операций up или V, можно указать, насколько следует увели- чить счетчик (параметр ReleaseCount), и узнать его предыдущее зна- чение (параметр lpPreviousCount). Декремент счетчика выполняется

72 при помощи любой функции ожидания, примененной к семафору, например WaitForSingleObject.
Мьютекс (MUTEX –MUTualEXclusion, взаимное исключение)
– бинарный семафор, специально предназначенный для решения задачи взаимного исключения, защиты критической секции. Для со- здания мьютекса используется функция CreateMutex:
HANDLE CreateMutex(
PSECURITY_ATTRIBUTES sa,/*атрибуты безопасности*/
BOOL fInitialOwner,/*признак, является ли поток, создающий мьютекс его владельцем*/
LPCTSTR name);/*имя мьютекса*/.
Операция освобождения мьютекса (up или V операция) вы- полняется вызовом функции BOOL ReleaseMutex (HANDLE). Опе- рация захвата мьютекса выполняется при помощи любой функции ожидания, например WaitForSingleObject.
Мьютекс можно рассматривать как бинарный семафор. Также мьютекс похож на критическую секцию. От семафора мьютекс от- личается тем, что он имеет атрибут владения (как критическая сек- ция). Отличие от критических секций состоит в том, что при помо- щи мьютекса можно синхронизировать потоки в разных процессах и указывать таймаут.
Если поток владеет мьютексом, то вызов функции ожидания с этим мьютексом завершится успешно, при этом увеличится внут- ренний счетчик рекурсий. Функция ReleaseMutex выполняет декре- мент счетчика рекурсий и освобождает мьютекс, если счетчик до- стигает значения ноль. Также ведет себя и критическая секция.
Если попытаться освободить мьютекс из протока, который им не владеет, то возникнет ошибка и функция GetLastError вернет зна- чение ERROR_NOT_OWNED.
Если поток, владеющий мьютексом, завершается, то мьютекс переходит в несигнальное состояние и может быть использован дру- гими потоками. Вызов функции ожидания с таким мьютексом будет выполнен, но функция
GetLastError вернет ошибку
WAIT_ABANDONED.
Пример задачи об ограниченном буфере. Проиллюстрируем применение семафоров и мьютексов для решения одной из класси-

73 ческих задач синхронизации – задаче об ограниченном буфере, так- же известной как проблема производителя и потребителя.
Два процесса совместно используют буфер ограниченного размера. Один из них (производитель) помещает данные в этот бу- фер, а другой (потребитель) – считывает их оттуда. Требуется обес- печить ожидание процесса-производителя – когда буфер заполнен и ожидание процесса-потребителя – когда буфер пуст. В других слу- чаях процессы могут добавлять (производитель) и извлекать (потре- битель) данные из буфера.
Приведем программу на псевдокоде с условными операциями для семафоров, мьютексов и буфера, иллюстрирующую решение проблемы для одного производителя и одного потребителя. semaphore mutex = 1;// защита критического
// ресурса – буфера semaphore empty = 100; //число пустых сегментов буфера semaphore full = 0; // число полных сегментов буфера
// код процесса – производителя void producer(){ int item; while(1){ item=produce_item();// создать данные,
//помещаемые в буфер down(&empty); // уменьшить счетчик пустых
// сегментов буфера down(&mutex);// вход в критическую секцию insert_item(item);// поместить в буфер
// новый элемент up(&mutex); //выход из критической секции up(&full); //увеличить счетчик
// полных сегментов буфера
}
}
// код процесса – потребителя void consumer(void){ int item; while(1){ down(&full); // уменьшить счетчик
// полных сегментов буфера

74 down(&mutex);// вход в критическую секцию item = remove_item(;// извлечь элемент
// из буфера up(&mutex); //выход из критической секции up(&empty); //увеличить счетчик
// пустых сегментов буфера consume_item(item);// обработать элемент
}
}
Заметим, что семафоры в приведенном примере используются по-разному. Семафор mutex служит для реализации взаимного ис- ключения, то есть конкурентной синхронизации. В реальной про- грамме для операционной системы Windows его необходимо реали- зовывать при помощи мьютекса или критической секции. Семафоры full и empty используются для задания определенной последователь- ности событий при кооперативной синхронизации. В реализации для
Windows уместно использовать семафоры. Таким образом, проблема об ограниченном буфере – пример гибридной проблемы, где встре- чается как кооперативная, так и конкурентная синхронизация.
Лекция 9. Тупики и защита от них
Определение тупика. Условие возникновения тупика. Моделирова- ние блокировок. Стратегии борьбы с блокировками: игнорирование проблемы, обнаружение и восстановление, динамическое избега- ние тупиковых ситуаций, предотвращение тупиков при помощи устранения одного из условий их возникновения.
Определение тупика. Процедурные методы синхронизации более удобны в применении, чем методы синхронизации на основе разделяемых переменных. Однако при некорректном их использова- нии возможно возникновение еще одного типа ошибок синхрониза- ции, известного как проблема тупиков (deadlock).
Группа процессов находится в тупиковой ситуации, если каж- дый процесс из группы ожидает событие, которое может вызвать только другой процесс из этой же группы.
Условия возникновения тупика. В большинстве случаев со- бытием, которого ждет каждый процесс, является освобождение ре- сурса. В 1971 году Коффман с соавторами доказали, что для возник-

75 новения ситуации блокировки в системе процессов и ресурсов должны выполняться четыре условия:
1. Условие взаимного исключения. Каждый ресурс в любой момент отдан ровно одному процессу или доступен.
2. Условие удержания и ожидания. Процессы, удерживающие полученные ранее ресурсы, могут запрашивать новые.
3. Условие отсутствия принудительной выгрузки. У процесса нельзя забрать ранее полученный ресурс. Процесс, владеющий ре- сурсом, должен сам освободить его.
4. Условие циклического ожидания. Должна существовать круговая последовательность из двух и более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим чле- ном последовательности.
Для возникновения блокировки должны выполняться все че- тыре условия. Если хотя бы одно условие отсутствует, блокировка невозможна.
Моделирование блокировок. В 1972 году Холт предложил метод моделирования условий возникновения тупика, используя ориентированные графы. Графические обозначения диаграмм Холта
(рис. 9.1). Графы имеют два типа узлов. Кругом обозначают про- цесс, квадратом – ресурс. Ребро, направленное от ресурса (квадрат) к процессу (круг) обозначает, что ресурс был ранее запрошен про- цессом, получен и в данный момент используется. Ребро, направ- ленное от процесса к ресурсу, означает, что процесс в данный мо- мент блокирован и находится в состоянии ожидания доступа к дан- ному ресурсу.
Рис. 9.1. Условные обозначения на диаграммах Холта
Процесс
Владение ресурсом
Ресурс
P
R
Запрос ресурса
P
R

76
Простейший тупик в системе из двух процессов и двух ресур- сов представлен графом Холта (рис.9.2).
Рис. 9.2. Простейший тупик
Рассмотрим, каким образом может возникнуть показанная на рис.9.2 ситуация. Пусть имеются функции потоков T1 и T2, код ко- торых показан ниже. В качестве ресурсов выступают мьютексы M1 и M2. В начальный момент нет запросов и захваченных ресурсов.
DWORD T1(PVOID){
DWORD T2(PVOID){
(1)WaitforSingleObject(M1,-1);
(2)
WaitforSingleObject(M2,-1);
(3)
WaitforSingleObject(M1,-1);
(4)WaitforSingleObject(M2,-1);
(5)--------------тупик----------------------------
//критическая секция
//критическая секция
ReleaseMutex(M1);
ReleaseMutex(M1);
ReleaseMutex(M2);
ReleaseMutex(M2);
}
}
В момент времени (1) поток T1 выполняет захват мьютекса
M1. Так как мьютекс свободен, происходит успешный захват. Это показано ребром M1

T1. Далее в момент (2) планировщик может передать управление потоку T2, который выполняет захват свобод- ного мьютекса M2. На графе (рис.9.2) появляется ребро M2

T2.
Продолжая вычисления, поток T2 выполняет запрос мьютекса M1, но так как мьютекс M1 уже заблокирован, поток переходит в состо- яние «ожидание» на мьютексе M1. На графе это показано ребром
T2

M1. В момент (4) управление передается потоку T1, который выполняет попытку захватить мьютекс M2, уже принадлежащий по- току T2, и тоже переходит в состояние ожидания. Цикл на графе
M1
M2
T1
T2

77
Холта, обозначающий состояние тупика, замыкается ребром
T1

M2.
Рассматривая данный простейший сценарий возникновения тупика, можно сделать следующие выводы. Во-первых, тупики воз- никают не при каждом исполнении. Например, если бы на шаге (2) планировщик не выполнил переключение контекста на поток T2, а дал возможность потоку T1 выполнить захват мьютекса M2, тупик бы не возник. Во-вторых, аккуратным планированием можно избе- жать блокировок. То есть планировщик, обладая некоторой инфор- мацией о необходимых потокам ресурсах, мог бы исключить пере- ключение контекста, вызвавшее блокировку. В-третьих, блокировки можно обнаружить. При переходе процесса в состояние ожидания при запросе ресурса можно выполнить анализ графа ресурсов и про- цессов на наличие цикла, то есть тупика.
Стратегии борьбы с блокировками. Рассмотрим стратегии предотвращения блокировок, вытекающие их моделей Холта и
Коффмана.
«Страусовый алгоритм». Допущение, что блокировки в си- стеме можно игнорировать. Усилия, затраченные на преодоление блокировок, могут себя не оправдать. Например, область памяти, в которой исполняется ядро операционной системы, ограничена. Так- же имеют предел таблицы процессов, таблицы открытых файлов и таблицы других системных ресурсов. Допустим, в операционной системе можно открыть n файлов, и каждый из N запущенных про- цессов открыл по n/N файлов. Далее, если каждый из процессов бу- дет периодически повторять попытки открыть еще по одному файлу, возникнет тупик. Большая часть операционных систем, включая
UNIX и Windows, игнорируют эту проблему. Полное ее решение включало бы неприемлемые с инженерной точки зрения ограниче- ния на использование ресурсов процессами.
Обнаружение и восстановление. Данная стратегия состоит в том, чтобы дать возможность произойти блокировке, обнаружить ее и предпринять действия для ее исправления. Существует несколько способов восстановления из тупика.
Принудительная выгрузка заключается в том, чтобы взять ре- сурс у одного процесса, отдать другому процессу и затем возвратить назад. Такая возможность зависит от свойств ресурса. Например, в