Востокин С.В.. Операционные системы. Экзаменационные вопросы по разделам дисциплины. Учебник предназначен для студентов специальности Фундамен тальная информатика и информационные технологии
 Скачать 2.09 Mb.
|
|
Агрессивная оптимизация. Реализация синхронизации с ис- пользованием разделяемых переменных и примитива test and set lock имеет максимальное быстродействие. Однако является достаточно сложной в силу ряда эффектов. Эффект агрессивной оптимизации возникает, когда компиля- тор на основе предположения о неизменяемости переменной вне текущего потока сохраняет ее значение в регистре, тем самым нарушает логику работы программы. Например, в коде, показанном ниже, используется флаг g_fFinished для ожидания завершения опе- рации в потоке с функцией CalcFunc. volatile BOOL g_fFinished = FALSE; /*volatile – загружаем значение из памяти при каждом обращении к переменной (отключает оптимизацию кода компилятором).*/ int main( ) { CreateThread (…, CalcFunc,…); while (g_fFinished = = FALSE); } DWORD WINAPI CalcFunc (PVOID) { … g_fFinished = TRUE; } Если не использовать ключевое слово volatile, то возникнет риск того, что значения флага загрузятся в регистр процессора перед вычислением while и в дальнейшем проверяться будет значение из регистра. То есть ждущий процесс никогда не увидит окончания вы- числений. Голодание. При реализации спин-блокировки возможна ситу- ация, когда поток длительное время опрашивает условие входа в критическую секцию. Периодически это условие оказывается ис- 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 Счетчик ссылок Объект ядра Таблица объектов ядра процесса 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, игнорируют эту проблему. Полное ее решение включало бы неприемлемые с инженерной точки зрения ограниче- ния на использование ресурсов процессами. Обнаружение и восстановление. Данная стратегия состоит в том, чтобы дать возможность произойти блокировке, обнаружить ее и предпринять действия для ее исправления. Существует несколько способов восстановления из тупика. Принудительная выгрузка заключается в том, чтобы взять ре- сурс у одного процесса, отдать другому процессу и затем возвратить назад. Такая возможность зависит от свойств ресурса. Например, в 78 случае необходимости можно временно прервать процесс печати и предоставить принтер другому процессу. При восстановлении через откат процесс периодически сохра- няет свое состояние, создавая контрольные точки. Это означает, что его состояние записывается в файл и впоследствии процесс может быть возобновлен из этого файла. Чтобы выйти из тупика процесс, занимающий необходимый ресурс, откатывает к тому моменту вре- мени, перед которым он получил данный ресурс. Освободившийся ресурс отдается другому процессу, попавшему в тупик. Простейшим способом выхода из блокировки является уни- чтожение одного или нескольких процессов, находящихся в цикле взаимоблокировки. В некоторых случаях имеются процессы без по- бочных эффектов, которые можно перезапустить, не нарушая работу системы. Например, процедуру компиляции всегда можно повто- рить заново. Рассмотрим простейший случай обнаружения тупика, когда каждый тип ресурсов системы представлен единственным ресурсом. Например, такая система могла бы иметь один сканер, одно устрой- ство записи дисков, один принтер и так далее. Обнаружение тупика в случае единственности ресурса каждо- го типа состоит из двух этапов: в текущем состоянии необходимо построить граф Холта, далее найти на нем цикл по какому-либо ал- горитму. Рассмотрим пример системы из семи процессов, состояние ко- торых описывает таблица. Процесс Захват ресурса Ждет ресурс A R S B - T C - S D U S, T E T V F W S G V U 79 Рис. 9.3. Граф Холта, показывающий состояние тупика процессов D,V и G Граф Холта, построенный по таблице, показан на рис.9.3. По визуальной модели состояния системы процессов видно, что про- цессы D, E, G (вместе с ними и процесс B) находятся в тупике. Про- цессы А, C и F могут завершить исполнение и высвободить занима- емые ресурсы, поскольку любому из них можно предоставить ре- сурс S. Для анализа графа большей размерности может применяться следующий алгоритм. Используем список L для хранения посещен- ных узлов и пометки для пройденных ребер. Алгоритм применяется для каждого узла графа. Шаг 1. Начальные условия: имеется текущий узел, список L пустой, ребра не маркированы. Шаг 2. Текущий узел добавляем в конец списка L. Если теку- щий узел присутствует в списке два раза, то граф содержит цикл (записанный в L). Алгоритм завершается. Шаг 3. Если из текущего узла выходит немаркированное реб- ро, переходим к шагу 4, иначе переходим к шагу 5. R S T V U W A B C D E F G 80 Шаг 4. Выбираем любое немаркированное ребро, маркиру- ем его, по нему переходим к новому текущему узлу. Переходим к шагу 2. Шаг 5. Удаляем последний узел из списка. Предпоследний узел объявляем текущим. Возвращаемся к шагу 3. Если перед шагом 5 в списке был только начальный узел, то граф не содержит циклов. Алгоритм завершается. Теперь рассмотрим общий случай обнаружения тупика, если имеется один или несколько типов ресурсов представленных не од- ним, а сразу несколькими ресурсами. В системе имеется m типов ресурсов. E = (e 1 , e 2 , …, e m ) – век- тор существующих ресурсов, в котором e j - количество ресурсов типа j (1 j m). A = (a 1 , a 2 , …, a m ) – вектор доступных ресурсов. В си- стеме имеется n процессов. Матрица текущего распределения ресур- сов С имеет вид: C= nm n m m c c c c c c c 1 2 21 1 12 11 , где ij c – количество ресурсов типа j, полученных процессом i. Матрица запросов ресурсов R имеет вид: R= nm n m m r r r r r r r 1 2 21 1 12 11 , где r ij - количество ресурсов типа j, запрашиваемых процессом i. С учетом условия взаимного исключения для ресурсов выпол- няется соотношение j n i j ij e a c 1 81 Алгоритм обнаружения тупиков состоит из следующих шагов. Все процессы не маркированы. Шаг 1. В матрице R ищем строку, соответствующую немарки- рованному процессу, которая меньше либо равна А (r j a j ). Шаг 2. Если такая строка i найдена, то маркируем соответ- ствующий процесс, прибавляем строку номером i матрицы C к век- тору А, возвращаемся к шагу 1. Шаг 3. Если немаркированных процессов нет, то алгоритм за- вершается. Если после завершения алгоритма остаются немаркированные процессы, то они находятся в тупике. Пример. Требуется определить, находится ли система процесс- ресурс в тупике. E=(4, 2, 3, 1) A=(2, 1, 0, 0) 0120 2001 0010 C 2100 1010 2001 R Убедимся в выполнении условия взаимного исключения для ресурсов: сложим строки матрицы C и вектор A, получим вектор E. 1 2 3 2 2 2 0 3 - 4 2 2 1 2 - 4 2 3 1 1- A ( , , , ) маркируем й процесс A ( , , , ) маркируем й процесс A ( , , , ) маркируем й процесс Выполняя последовательность шагов алгоритма, маркируем все процессы. Следовательно нет процессов, находящихся в тупике. Избегание взаимных блокировок. В первом примере показано, что, выбирая определенный порядок планирования среди несколь- ких возможных, планировщик избегает тупика. Стратегию поведе- ния планировщика в случае двух процессов и произвольного коли- чества ресурсов (в каждом типе имеется 1 ресурс) представляет диа- грамма траектории ресурсов (рис. 9.4). 82 Рис. 9.4. Диаграмма траектории ресурсов Диаграмма представляет собой первый квадрант координат- ной плоскости. Оси являются временными, представляя события процесса А и процесса B. Для определенности свяжем отсчеты вре- мени процесса А со следующими событиями: 1 – захват принтера, 2 – захват плоттера, 3 – освобождение принтера, 4 – освобождение плоттера. На временной оси процесса B отмечаются следующие со- бытия: 1 – захват плоттера, 2 – захват принтера, 3 – освобождение плоттера, 4 – освобождение принтера. С учетом введенных обозначений точка на диаграмме траек- тории ресурсов представляет состояние системы. Она может дви- гаться только вверх и вправо. В некоторых областях диаграммы си- стема не может находиться по правилу исключения для ресурса. Об- ласти называются, соответственно, области исключения ресурса (рис. 9.4). Если во время планирования точка, обозначающая состояние системы, попадет в область Х, то со временем в системе возникнет блокировка, так как точка не может двигаться вниз и влево. Любое состояние в области серого цвета является безопасным состоянием. А B 1 2 3 4 1 2 3 4 Области ис- ключения ре- сурсов Тупик 83 В таком состоянии планировщик путем аккуратного планирования ресурсов может избежать возникновения тупика (рис. 9.4). Алгоритм Банкира для одного типа ресурсов. Анализ диа- граммы траектории ресурсов показал, что цель алгоритма планиро- вания – проверить приводит ли удовлетворение запроса на ресурс к выходу из безопасного состояния системы. Пусть имеется один ресурс некоторого типа. Воспользуемся аналогией работы планировщика с поведением банкира, кредитую- щего клиентов. Запишем состояние системы в виде таблицы распре- деления ресурсов, в которой A, B, C – имена клиентов банка (про- цессы); второй столбец – выданные клиенту кредиты (ресурсы); тре- тий столбец – число кредитов, необходимых клиентам. Внизу под- писано число свободных кредитов у банкира. Вначале проверим, является ли текущее состояние безопас- ным. То есть сможем ли мы предложить стратегию обслуживания клиентов, удовлетворяющую все запросы на кредиты. Для этого бу- дем давать ссуду только тем клиентам, запросы которых в кредитах мы можем покрыть полностью при текущем количестве свободных кредитов у банка. Ниже показана такая стратегия обслуживания. A 3 9 A 3 9 A 3 9 A 3 9 A 0 - B 2 4 B 4 4 B 0 - B 0 - B 0 - C 2 7 C 2 7 C 2 7 C 0 - C 0 - Свободно 3 Свободно 1 Свободно 5 Свободно 7 Свободно 10 Теперь допустим, что в рассмотренном безопасном состоянии клиент A выставил запрос на один кредит. Рассмотрим гипотетиче- ское состояние, возникающее при удовлетворении такого запроса. A 3 9 +1 A 4 9 A 4 9 A 8 9 B 2 4 B 2 4 B 0 - B 0 - C 2 7 C 2 7 C 2 7 C 2 7 Свободно 3 Свободно 2 Свободно 4 Свободно 0 Небезопасно Небезопасно Небезопасно 84 Мы видим, что возникает состояние, в котором не хватает одного кредита для удовлетворения запроса как клиента А (показа- но выше), так и клиента C (определяется аналогично). Оказавшись в таком состоянии, банкир признает банкротство, так как вынуж- ден отказать всем не обслуженным клиентам. То есть система ока- зывается в тупике, следовательно запрос процессом A одного ре- сурса приводит к выходу из безопасного состояния и должен быть отклонен. Предотвращение при помощи устранения одного из условий возникновения тупика. Если удастся предложить стратегию работы с ресурсами, в которой исключено хотя бы одно из условий Хоффма- на, тупик не возникнет. 1. Атака взаимного исключения. Пример использования оче- реди печати показывает, что можно избежать захвата принтера. 2. Атака условия удержания и ожидания. Если все ресурсы за- прашиваются одновременно, то тупиков не возникнет. Например, можно использовать функцию WaitForMultipleObjects. 3. Атака условия отсутствия принудительной выгрузки. Реали- зуется при обработке транзакций. Каждый процесс готов освободить захваченные ресурсы по запросу менеджера транзакций. 4. Атака условия циклического ожидания. Если все ресурсы пронумерованы и каждый процесс имеет право захватывать ресурс только с большим порядковым номером, чем номера уже захвачен- ных ресурсов, то тупика не возникнет. Экзаменационные вопросы по разделу III 1. Абстракция процесса, управление процессами в многозадачной операционной системе. Определение процесса. Диаграмма со- стояния, контекст, дескриптор процесса. Квантование и приори- тетное планирование. Нити (потоки исполнения). 2. Функциональные возможности многозадачности в ОС Windows. Способы использования многозадачности в приложениях. 3. Планировщик ОС Windows. Класс и уровень приоритета. Пере- ключение контекста. Потоки, не являющиеся готовыми. Дина- мический приоритет. 85 4. Эффект инверсии приоритетов. Пример возникновения инвер- сии. Способы преодоления. 5. Мультипроцессорная обработка в ОС Windows. Термины, вызо- вы API, их назначение. 6. Состояние состязания. Пример возникновения и способ преодо- ления. 7. Средства синхронизации в режиме пользователя в ОС Windows. Функции, реализующие атомарные операции, объект «критиче- ская секция». 8. Задача о критической секции. Алгоритм Питерсона для двух процессов. Условия задачи. Объяснение принципа работы алго- ритма. 9. Предотвращение агрессивной оптимизации кода с использова- нием модификатора volatile. Эффект голодания, пример возник- новения. 10. Эффект ложного разделения переменных. Пример влияния кэш- линий на скорость исполнения многопоточных программ. 11. Управление объектами ядра в ОС Windows. Описатель объекта. Таблица описателей объектов процесса. Создание, наследование, именование, дублирование описателей. 12. Средства синхронизации в режиме ядра в ОС Windows. Собы- тия, семафоры, мьютексы. 13. Эффект взаимоблокировки или возникновения тупика. Опреде- ление, условия возникновения, моделирование графами Холта. 14. Стратегия «обнаружение-устранение» для борьбы с взаимобло- кировками. Применение графов Холта и матриц распределения ресурсов. 15. Стратегия избегания блокировок. Диаграмма траектории ресур- сов. Алгоритм банкира для одного вида ресурсов. 16. Предотвращение блокировок путем исключения условий их воз- никновения. |