Востокин С.В.. Операционные системы. Экзаменационные вопросы по разделам дисциплины. Учебник предназначен для студентов специальности Фундамен тальная информатика и информационные технологии
 Скачать 2.09 Mb.
|
|
Планировщик. В документации разработчика не описывается конкретный алгоритм планирования, так как он разный в разных версиях операционной системы Windows. Однако имеется возмож- ность адаптировать конкретный планировщик под нужды приложе- ния. Повлиять на алгоритм планирования можно путем управления классом и уровнем приоритета (priority class, priority level). Класс указывается при создании процесса с использованием функции CreateProcess. Существует 6 классов приоритета: IDLE_PRIORITY_CLASS – самый низкий класс приоритета, его имеют хранители экрана, средства сбора диагностики, средства индексирования и другие процессы фонового режима; BELOW_NORMAL_PRIORITY_CLASS – приоритет ниже, чем приоритет по умолчанию; NORMAL_PRIORITY_CLASS – приоритет по умолчанию; ABOVE_NORMAL_PRIORITY_CLASS – приоритет выше, чем по умолчанию; HIGH_PRIORITY_CLASS – приоритет процессов, непосред- ственно работающих с оборудованием, является приоритетом ре- ального времени; REALTIME_PRIORITY_CLASS – еще приоритет реального времени более приоритетен, чем системные потоки, работающие с диском, клавиатурой и мышью. Класс приоритета определяется с помощью функции GetPriorityClass и задается с помощью функции SetPriorityClass. Типичная ситуация изменения приоритета возникает, когда процессу нужно гарантировать непрерывное выполнение некоторой операции. Для этого кратковременно приоритет повышается, затем понижается. Внутри процесса устанавливаются относительные приоритеты для его потоков. Они называются уровнями приоритета или приори- тетами потока: 51 THREAD_PRIORITY_IDLE – минимальный приоритет для фоновых потоков простоя; THREAD_PRIORITY_LOWEST – более высокий приоритет для потоков простоя; THREAD_PRIORITY_BELOW_NORMAL – приоритет для менее приоритетных рабочих потоков; THREAD_PRIORITY_NORMAL – приоритет по умолчанию; THREAD_PRIORITY_ABOVE _NORMAL – приоритет для более приоритетных рабочих потоков; THREAD_PRIORITY_HIGHEST – приоритет реального вре- мени; THREAD_PRIORITY_TIME_CRITICAL – наивысший приори- тет реального времени. Уровень приоритета определяется с помощью функции GetThreadPriority и задается с помощью функции SetThreadPriority. Всем потокам по умолчанию назначается нормальный уровень при- оритета. Если возникает необходимость задать уровень приоритета при создании потока, то используется следующая последователь- ность вызовов. С использованием CreateThread создается поток в приостановленном состоянии с флагом CREATE_SUSPENDED. Да- лее устанавливается нужный уровень приоритета вызовом SetThreadPriority. Затем поток переводится в готовое состояние вы- зовом ResumeThread. Единицами планирования для диспетчера являются именно потоки, а не процессы. Для вычисления приоритета планирования, который называется базовым приоритетом (base priority), по специ- альным правилам выполняется комбинирование класса и уровня. Операционная система Windows использует 32 базовых приоритета (от 0 до 31). Старшие приоритеты от 16 до 31 относятся к приорите- там реального времени. Младшие приоритеты относятся к приори- тетам разделения времени. Приоритет 0 не назначается потокам пользователя, он зарезервирован за потоком обнуления страниц. Этот поток отвечает за очистку страниц, которые переходят от одно- го процесса к другому, в оперативной памяти. Это обеспечивает за- щиту объектов согласно требованию класса безопасности C2. В планировщике имеется 32 очереди потоков, в которые они попадают согласно своим приоритетам (рис. 6.1). Обслуживание, то есть назначение квантов процессорного времени внутри каждой 52 очереди, осуществляется по принципу карусели (round-robin). Кван- ты времени получают потоки, находящиеся в непустой очереди наивысшего приоритета. Для переключения контекста между пото- ками Windows использует следующую последовательность шагов: сохранить контекст только что завершившегося потока; поместить этот поток в очередь соответствующего прио- ритета; найти очередь наибольшего приоритета, содержащую го- товые потоки; удалить дескриптор потока из головы этой очереди, за- грузить контекст, приступить к исполнению. Рис. 6.1. Схема очередей планировщика Windows Некоторые потоки не находятся в структурах данных плани- ровщика, то есть не являются готовыми. Такими потоками являются потоки, созданные флагом SUSPENDED; остановленные командой SuspendThread; ожидающие события синхронизации (например, в функции WaitForSingleObject) или завершения ввода-вывода. Причины вытеснения текущего потока в планировщике Windows – истечение кванта времени; появление более приоритет- Дескриптор Очередь 0 Очередь 1 Очередь 2 Очередь 3 Очередь 4 Очередь 31 Дескриптор Дескриптор x x x x x x x x x x 53 ного готового потока; переход исполняющегося потока к ожиданию события или завершения ввода-вывода. Согласно описанной выше процедуре планирования низ- коприоритетные потоки не должны получать обслуживание при наличии более приоритетных потоков. Чтобы предотвратить данную нежелательную ситуацию для потоков разделения времени вводится динамический приоритет. Динамический приоритет используется для продвижения потоков при наличии более приоритетных. Плани- ровщик Windows кратковременно повышает приоритеты простаи- вающих готовых потоков. Процедура повышения приоритета (priori- ty boost) выполняется в случае, когда: процесс, содержащий поток, переходит на передний план; окно процесса получает событие от мыши и клавиатуры; наступило событие, которое ожидал поток или завершился ввод-вывод. В любом случае динамический приоритет не может быть меньше базового приоритета. По истечении каждого кванта динамический приоритет уменьшается на 1 до тех пор, пока не достигнет базового приоритета. Повышенный приоритет (priority boost) получают потоки с базовым приоритетом, не превышающим 15. Также в Windows имеется возможность изменения длительности квантов времени, назначаемых потокам. Инверсия приоритетов. Наличие приоритетов может приве- сти к неявной блокировке, когда более высокоприоритетный поток зависит от менее приоритетного потока. Например, ждет освобож- дения мьютекса, захваченного потоком. Рис. 6.2. Возникновение инверсии приоритетов 1 3 2 4 Критическая секция ResumeThread() WaitForSingleObject() ResumeThread() T 1 < T 2 < T 3 54 На рис. 6.2 показан сценарий возникновения инверсии прио- ритетов на примере трех потоков. Поток T1 имеет наименьший при- оритет, поток T3 наибольший приоритет, поток T2 имеет промежу- точный приоритет. Опишем последовательность возникновения ин- версии. Шаг 1. Поток T1 выполняет код в критической секции. Шаг 2. Появляется поток T3 с наивысшим приоритетом в го- товом состоянии. Следовательно, поток T1 вытесняется. Шаг 3. Поток T3, ожидая событие освобождения мьютекса, отдает управление потоку T1, потому что в данный момент поток T1 наиболее приоритетный поток в готовом состоянии. Шаг 4. Если в системе появляется готовый поток T2 в то вре- мя, как T1 не успел выйти из критической секции и освободить мьютекс, то поток T2 блокирует более приоритетный поток T3. Та- ким образом, происходит инверсия приоритета. В Windows 9x диспетчер обнаруживает зависимость более приоритетного потока от менее приоритетного потока, если эта за- висимость возникает через объект ядра, и повышает приоритет ме- нее приоритетного потока до уровня приоритета более приоритетно- го потока. Для предотвращения инверсии в современных версиях Widows планировщик учитывает время простоя готовых потоков и случайным образом повышает их динамический приоритет. Многопроцессорная обработка. В операционной системе Windows имеется возможность управлять назначением потоков на конкретный процессор. Для управления таким назначением исполь- зуются два атрибута. Атрибут thread affinity определяет привязку потока к опреде- ленной группе процессоров. Этот атрибут представляет собой бито- вую маску, его указание вынуждает поток исполняться на указанном подмножестве процессоров. Для установки битовых масок привязки к процессорам используются функции SetThreadAffinityMask и SetProcessAffinityMask. Для считывания значения битовых масок привязки к процессорам используются функции GetProcessAffinityMask и GetThreadAffinityMask. 55 Настройка привязки потока к процессорам может использо- ваться для отладки в обычных SMP (симметричных мультипроцес- сорных системах) при наблюдении за активностью потоков сред- ствами диспетчера задач. Основным применением является повы- шение производительности многопоточных приложений при испол- нении в архитектурах с неоднородным доступом к памяти (NUMA). Рис. 6.3. Архитектура с неоднородным доступом к памяти (NUMA) В таких архитектурах доступ по некоторым адресам памяти из заданного процессора может происходить быстро, а по некото- рым медленнее. Точно так же выделяются группы более и менее связанных между собой процессоров (рис.6.3). Зная топологию про- цессоров на компьютере и топологию задач приложения, удается оптимизировать приложение. Для получения данных о топологии имеются специальные функции. Если зависимые потоки поместить на один процессор, то они будут выполняться быстрее, так как будут обрабатываться через один внутренний кэш процессора, а не внеш- ний, как в противном случае (рис.6.3). Однако жесткая привязка по- токов к процессорам может снизить производительность. Для реко- мендации планировщику назначать, по возможности, поток на про- цессор имеется еще один атрибут – идеальный процессор (ideal processor). Чтение и установка этого атрибута выполняется функци- ями GetThreadIdealProcessor и SetThreadIdealProcessor. ЦП ЦП ЦП ЦП ОЗУ КЭШ 1 КЭШ 2 Тесно и слабо связанные процессоры 56 Лекция 7. Синхронизация с использованием разделяемых переменных Необходимость синхронизации на примере возникновения состоя- ния состязания. Аппаратная реализация синхронизации. Задача о критической секции. Решение задачи для двух процессов в алгорит- ме Петерсона. Проблемы использования разделяемых переменных: агрессивная оптимизация, голодание, ложное разделение. Необходимость синхронизации. Для того, чтобы параллель- но или псевдопараллельно выполняющиеся процессы могли решать общую задачу, их исполнение необходимо синхронизировать. Су- ществуют два типа задач синхронизации: конкурентные и коопера- тивные. Синхронизация при совместном использовании разделяемого ресурса. Например, имеется очередь заданий на печать, в которую добавляют свои задания независимо работающие процессы. Такой вид взаимодействия (тип синхронизации) называется конкурентным. Его отличительной особенностью является то, что остановка одного из процессов-участников вне протокола взаимодействия не влияет на возможность других процессов продолжать работу. Если речь идет об уведомлении одного процесса о завершении какой-либо операции другим процессом, выполняется кооператив- ное взаимодействие. Здесь, напротив, остановка любого участника со временем приведет к остановке всей системы процессов. Типич- ный пример такой синхронизации – буферизация данных, передава- емых по цепочке из процессов. При отсутствии синхронизации процессов при совместном ис- пользовании разделяемого ресурса возникает искажение данных, называемое «состоянием состязания» (race condition). Пусть разделя- емый ресурс – это глобальная переменная, используемая как счетчик числа обращений к некоторому ресурсу. При обращении к ресурсу процесс выполняет инкремент счетчика. Рассмотрим пример, иллю- стрирующий искажение данных даже для такого простого ресурса. Разделяемый ресурс – глобальная переменная типа long long g_x = 0; 57 Процессы представлены идентичными функциями потоков Thr1 и Thr2. DWORD WINAPI Thr1(PVOID) { /*обращение к ресурсу*/ g_x++; /*увеличение счетчика обращений*/ return 0; } DWORD WINAPI Thr2(PVOID) { /*обращение к ресурсу*/ g_x++; /*увеличение счетчика обращений*/ return 0; } Для управления потоками объявляются массив указателей на функции потока thr_arr и массив описателей потоков thr_hnd. LPTHREAD_START_ROUTINE thr_arr [2] = {Thr1, Thr2} HANDLE thr_hnd [2]; В функции main вначале запускаем наши потоки на исполне- ние вызовом CreateThread, проверяя и обрабатывая ошибки вызовом функции завершения процесса ExitProcess. Затем при помощи функ- ции WaitForMultipleObjects ожидаем завершения всех запущенных потоков. int main() { DWORD id; for (inti=0; i<2; i++) { thr_hnd [i] = CreateThread( NULL,0,thr_arr[i],NULL,0,&id); if (thr_hnd [i] = = NULL) ExitProcess(-1); } WaitForMultipleObjects( 2, thr_hnd, TRUE, INFINITE); return 0; } Очевидным кажется состояние переменной g_x=2 после за- вершения запущенных потоков. Однако истинное постусловие рас- 58 смотренной программы – g_x=1 g_x=2. Для того, чтобы понять почему значение переменной g_x может также оказаться равным 1, рассмотрим как представляется оператор g_x++ при компиляции программы. Столбцы Thr1 и Thr2 показывают ассемблерные ин- струкции потоков, а левый столбец – порядок исполнения этих ин- струкций на однопроцессорной машине. Показанный порядок вы- полнения инструкций возможен при переключении контекста в мо- мент выполнения инкремента. С учетом того, что каждый из пото- ков имеет индивидуальную копию регистра EAX, действия потока Thr2 будут потеряны. Итоговое значение g_x оказывается равным 1. Thr1 Thr2 /* g_x++ */ /* g_x++ */ (1) MOV EAX, [g_x] (2) MOV EAX, [g_x] (3) ADD EAX, 1 (4) MOV [g_x], EAX (5) ADD EAX, 1 (6) MOV [g_x], EAX Из-за «расщепления» команды инкремента возникает состоя- ние состязания (race condition). Для предотвращения этого эффекта необходимо, чтобы эти три ассемблерные команды выполнялись как единое целое. Для того, чтобы достичь неделимости инкремента и некото- рых других арифметических операций в программном интерфейсе Windows имеется группа функций с префиксом interlocked. При ис- пользовании функции InterlockedExchangeAdd правильный код под- счета обращений к ресурсу выглядит следующим образом. DWORD WinAPI Thr1(PVOID) { /*обращение к ресурсу*/ InterlockedExchangeAdd(&g_x,1);/*увеличение счетчика обращений*/ return 0; } Аппаратная реализация синхронизации. Для реализации неделимых операций в системе команд компьютеров имеется ин- струкция «проверить и установить блокировку» (test and set lock). 59 Данная инструкция реализует базовую атомарную операцию, ис- пользуя которую легко построить более сложные операции. Коман- да неделимым образом записывает ненулевое значение по адресу в памяти, одновременно сохраняя старое значение по этому адресу в регистре. enter: TSL Reg, [Lock] CMP Reg, #0;0 значит, что текущий поток ; выполнил блокировку JNE enter; и ему можно войти в критическую секцию ;выполняем неделимую последовательность команд leave: MOV [Lock], #0 Такой метод синхронизации называется спин-блокировка по- тому, что в цикле происходит постоянный опрос значения перемен- ной по адресу Lock. При использовании interlocked-функции InterlockedExchange реализация спин-блокировки выглядит следую- щим образом. BOOL g_ResInUse = FALSE; //перед неделимой последовательностью while(InterlockedExchange(&g_ResInUse,TRUE)==TRUE) Sleep(0); // после неделимой последовательности команд InterlockedExchange(&g_ResInUse,FALSE); Функция InterlockedExchange присваивает значение, передан- ное во втором параметре, переменной, адрес которой указан в пер- вом, и возвращает значение до модификации. Задача о критической секции. Помимо аппаратной реализа- ции возможна и программная реализация неделимой последователь- ности операций с использованием разделяемых переменных. Эдсгер Дейкстра в 1965 году сформулировал постановку задачи. Деккер описал первое корректное решение. Задача получила название задача о критической секции. Она формулируется следующим образом. Каждый из процессов, участ- 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, которая в случае конфликта разрешает вход в критиче- скую секцию только одному процессу. |