|
Читайте также: |
Введем новый синхронизирующий процесс. Этот процесс имеет счетчик и очередь для процессов, ожидающих включения семафора. Для того чтобы выполнить операции P и V, процессы посылают синхронизирующему процессу сообщения, в которых указывают свои потребности, после чего ожидают получения подтверждения от синхронизирующего процесса.
После получения сообщения синхронизирующий процесс проверяет значение счетчика, чтобы выяснить, можно ли совершить требуемую операцию. Операция V всегда может быть выполнена, в то время как операция P может потребовать блокирования процесса. Если операция может быть совершена, то она выполняется, и синхронизирующий процесс посылает подтверждающее сообщение. Если процесс должен быть блокирован, то его идентификатор заносится в очередь блокированных процессов, и подтверждение не посылается. Позднее, когда какой-либо из других процессов выполнит операцию V, один из блокированных процессов удаляется из очереди ожидания и получает соответствующее подтверждение.
28 Тупики. Условия их возникновения.
Несколько процессов конкурируют за обладание конечным числом ресурсов. Если запрашиваемый процессом ресурс недоступен, ОС переводит данный процесс в состояние ожидания. В случае когда требуемый ресурс удерживается другим ожидающим процессом, первый процесс не сможет сменить свое состояние. Такая ситуация называется тупиком (deadlock). Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация, или "зависание системы", является следствием того, что один или более процессов находятся в состоянии тупика.
Тупики, однако, могут иметь место и в других ситуациях. В этом случае может получиться так, что один из процессов заблокировал записи, необходимые другому процессу, и наоборот. Таким образом, тупики могут иметь место как на аппаратных, так и на программных ресурсах.
Тупики также могут быть вызваны ошибками программирования. Например, процесс может напрасно ждать открытия семафора, потому что в некорректно написанном приложении эту операцию забыли предусмотреть. Другой причиной бесконечного ожидания может быть дискриминационная политика по отношению к некоторым процессам.
Ресурсами могут быть как устройства, так и данные.
29 Основные направления борьбы с тупиками
В исследованиях по проблеме тупиков можно выделить следующие четыре основные направления: 1. предотвращение тупиков; 2. обход тупиков; 3. обнаружение тупиков; 4. восстановление после тупиков.
При предотвращении тупиков целью является обеспечение условий, исключающих возможность возникновения тупиковых ситуаций.
Цель средств обхода тупиков заключается в том, чтобы можно было предусматривать менее жесткие ограничения, чем в случае предотвращения тупиков, и тем самым обеспечить лучшее использование ресурсов.
Методы обнаружения тупиков применяются в системах, которые допускают возможность возникновения тупиковых ситуаций как следствие либо умышленных, либо неумышленных действий программистов. Цель средств обнаружения тупиков — установить сам факт возникновения тупиковой ситуации, причем точно определить те процессы и ресурсы, которые оказались вовлеченными в данную тупиковую ситуацию.
Методы восстановления после тупиков применяются для устранения тупиковых ситуаций, с тем чтобы система могла продолжать работать, а процессы, попавшие в тупиковую ситуацию, могли завершиться с освобождением занимаемых ими ресурсов. Восстановление — это серьезная проблема, так что в большинстве систем оно осуществляется путем полного выведения из решения одного или более процессов, попавших в тупиковую ситуацию
30 Алгоритм банкира
Операционная система должна обеспечить распределение некоторого фиксированного числа t одинаковых лентопротяжных устройств между некоторым фиксированным числом пользователей и. Каждый пользователь заранее указывает максимальное число устройств, которые ему потребуются во время выполнения своей программы на машине. Операционная система примет запрос пользователя в случае, если максимальная потребность этого пользователя в лентопротяжных устройствах не превышает t.
Пользователь может занимать или освобождать устройства по одному. Возможно, что иногда пользователю придется ждать выделения дополнительного устройства, однако операционная система гарантирует, что ожидание будет конечным. Текущее число устройств, выделенных пользователю, никогда не превысит указанную максимальную потребность этого пользователя. Если операционная система в состоянии удовлетворить максимальную потребность пользователя в устройствах, то пользователь гарантирует, что эти устройства будут использованы и возвращены операционной системе в течение конечного периода времени.
Текущее состояние вычислительной машины называется надежным, если операционная система может обеспечить всем текущим пользователям завершение их заданий в течение конечного времени. В противном случае текущее состояние системы называется ненадежным.
Работают n пользователей. Пусть l(i) представляет текущее количество устройств, выделенных i пользователю. Если, например, пользователю 5 выделены четыре устройства, то l(5)=4. Пусть m(i) — максимальная потребность пользователя i, так что если пользователь 3 имеет максимальную потребность в двух устройствах, то m(3)=2. Пусть c(t) — текущая потребность пользователя, равная его максимальной потребности минус текущее число выделенных ему ресурсов. Если, например, пользователь 7 имеет максимальную потребность в шести устройствах, а текущее количество выделенных ему устройств составляет четыре, то мы получаем с (7)=m (7) - 1(7)=6 - 4=2.
Недостатки, из-за которых разработчик системы может оказаться вынужденным выбрать другой подход к решению проблемы тупиков.
1. Алгоритм банкира исходит из фиксированного количества распределяемых ресурсов. Поскольку устройства, представляющие ресурсы, зачастую требуют технического обслуживания либо из-за возникновения неисправностей, либо в целях профилактики, мы не можем считать, что количество ресурсов всегда остается фикс.
2. Алгоритм требует, чтобы число работающих пользователей оставалось постоянным. Подобное требование также является нереалистичным. Текущее число обслуживаемых пользователей непрерывно меняется, быть может, очень часто, каждые несколько секунд.
3. Алгоритм требует, чтобы банкир—распределитель ресурсов гарантированно удовлетворял все запросы за некоторый конечный период времени. Для реальных систем необходимы гораздо более конкретные гарантии.
4. Аналогично, алгоритм требует, чтобы процессы гарантированно возвращали выделенные им ресурсы в течение некоторого конечного времени. И опять-таки для реальных систем требуются гораздо более конкретные гарантии.
5. Алгоритм требует, чтобы пользователи заранее указывали свои максимальные потребности в ресурсах. По мере того как распределение ресурсов становится все более динамичным, все труднее оценивать максимальные потребности пользователя.
31 Обнаружение тупиков
Безопасное состояние системы – такое состояние, перевод системы в которое не приведет к созданию тупиков. Система в безопасном состоянии, если существует безопасная последовательность их всех процессов в системе. Безопасная последовательность – последовательность исполнения процессов, при которой каждый процесс использует только свободные ресурсы, либо ресурсы, освобождаемые процессом с меньшим номером после его завершения. Таким образом, если система в безопасном состоянии, тупиков нет. Если система в небезопасном состоянии, тупики возможны.
Граф распределения ресурсов новый вид дуг – дуги потребности. Она ведет из вершины-процесса в вершину-ресурс, обозначается пунктиром и означает, что процесс может потребовать данный ресурс. Дуга потребности преобразуется в дугу присваивания, когда система фактически выделяет данный ресурс процессу. При освобождении ресурса дуга присваивания преобразуется обратно в дугу потребности.
Алгоритм банкира – алгоритм распределения ресурсов операционной системой, обеспечивающий избежание тупиков. Его условия и принципы: возможны множественные экземпляры ресурсов; каждый процесс должен априорно обозначить свои максимальные потребности в ресурсах; при запросе ресурса возможно ожидание процесса; после получения ресурсов процесс должен вернуть их за ограниченный период времени. Для работы алгоритма используются вектор доступности ресурсов каждого вида, матрица максимальных потребностей процессов, матрица фактического выделения системой ресурсов процессам, матрица оставшихся потребностей процессов в ресурсах.
Алгоритм безопасности определяет, является ли состояние системы безопасным, путем построения безопасной последовательности процессов. Алгоритм моделирует последовательное освобождение ресурсов процессами после их завершения.
обнаружение тупиков: позволить системе войти в состояние тупика, применить алгоритм обнаружения тупиков и выполнить схему восстановления после тупика. Если каждый ресурс существует в единственном экземпляре, для обнаружения тупиков используется граф wait-for, в котором вершины соответствуют процессам, а дуга ведет из вершины A в вершину B, если процесс A ожидает процесса B.
Если имеются множественные экземпляры ресурсов, то для обнаружения тупиков используется алгоритм, аналогичный алгоритму построения безопасной последовательности процессов.
После обнаружения тупиков система определяет, какое минимальное число процессов необходимо прекратить для ликвидации тупика. Для выбора процесса-жертвы существует ряд критериев, например, приоритет процесса или оставшееся время его выполнения. При прекращении процесса его ресурсы освобождаются. При применении данной стратегии возможно голодание, если в качестве жертвы система все время выбирает один и тот же процесс.
32 Классификация средств реализации многозадачности
Используемые в операционной системе средства реализации многозадачности можно разделить на несколько групп:
-Взаимодействие с устройствами. Существуют как специализированные средства взаимодействия, специфичные для конкретного вида устройств, так и относительно универсальные средства, применимые к устройствам разных типов. примером являются средства асинхронного ввода-вывода.
-Средства управления потоками и волокнами. Когда процесс запускается, операционная система в нем самостоятельно создает первичный поток, начинающий исполнение кода этого процесса. Создание всех остальных потоков процесса требует специальных действий. Операционная система должна предоставлять средства для создания потоков, волокон, их завершения, приостановки или возобновления, изменения их характеристик.(прямые и косвенные)
-Взаимодействие потоков в рамках одного процесса. Потоки, работающие в рамках одного процесса, имеют возможность взаимодействовать друг с другом, используя общее адресное пространство процесса.
-Взаимодействие между процессами одного компьютера. необходимость взаимодействия различных процессов в рамках одной вычислительной системы. Раные процессы работают в изолированных друг от друга адресных пространствах, однако при этом существует возможность осуществить обмен данными через общую, разделяемую несколькими процессами, память.
-Взаимодействие между процессами разных компьютеров. В общем случае память разных компьютеров можно рассматривать как изолированную друг от друга. В этом случае для взаимодействия разных процессов потребуется пересылка сообщений, содержащих данные и некоторую управляющую информацию, между разными компьютерами (узлами сети).
33 Реализация процессов и потоков в ОС Windows
Симметричные потоки-потоки, исполняющие один и тот же код. Ассиметричные-различный код. Создание >Готовность <>выбран для исполнения >исполнение<> Ожидание >Промежуточное ожидание>Готовность. Исполнение> Завершение и Готовность
Ожидание-ввода вывода и приостановка процесса. Обычно в состоянии "Готовности" имеется очередь готовых к выполнению (running) потоков. В данном случае это состояние распадается на три составляющих. Это, собственно, состояние "Готовности (Ready)"; состояние "Готов. Отложен (Deferred Ready)", что означает, что поток выбран для выполнения на конкретном процессоре, но пока не запланирован к выполнению; и, наконец, состояние "Простаивает (Standby)", в котором может находиться только один выбранный к выполнению поток для каждого процессора в системе. "Переходное (Transition)" состояние в том случае, если стек ядра потока выгружен из памяти.
Планировщик вызывается при создании, завершении потока, по истечении кванта времени, при выходе (переходе в)из состояния ожидания, при изменении приоритета потока, при изменении привязки потоков процессора. Идеальный процессор-если поток был запущен на каком то процессоре, виндовс старается постоянно запускать на том же процессоре. При этом допускается вытеснение работающего процессора на идеальном процессоре.
34 Управление квантованием в ОС Windows
Процедура квантования времени (time-slicing). Время разделяется на небольшие интервалы. Перед началом каждого интервала принимается решение, какой именно поток выполнения будет отрабатываться на протяжении этого кванта времени. За счет частого переключения между задачами эмулируется многопоточная архитектура.
0t=t(n/n+1) –n-число процессов(увеличение дельта).
Квантование в виндовс осуществляется по тикам системного таймера. Длительность тиков 10 15 милисекунд. Чем больше число процессоров, тем больше число тиков. Каждый тик сист. таймера соответ. нескольким у.е. (в основном 3). Величина кванта от 2 до 12 тиков.
Есть специальная структура(хранится в реестре виндовс) win32 priority seporations-отвечает за динамическое изменение кванта, его размера(0-5 бит). Управление длительностью кванта связано с активностью процесса-фоновый или активный. Для фоновых увеличивается длительность кванта.
Для процессов находящихся долгое время ожидания может быть увеличивает приоритет и длительность кванта.
35 Управление приоритетами в ОС Windows
В Windows выделяется 32 уровня приоритетов. 0 соответствует самому низкому приоритету (приоритетом работает только спец. поток обнуления страниц), 31 - самому высокому. Этот диапазон делится на 3 части:
--Приоритет 0 - соответствует приоритету потока режим ожидания.
--Приоритеты с 1 по 15 – приоритеты исполняемых процессов.
--Приоритеты с 16 по 31 - соответствуют приоритетам "реального времени". Этот уровень достаточно высок для того, чтобы поток, работающий с таким приоритетом, мог реально помешать нормальной работе других потоков в системе - например, помешать обрабатывать сообщения от клавиатуры и мыши.
Для некоторого упрощения управления приоритетами в Windows выделяют "классы приоритета" (priority class), которые задают базовый уровень-6 приоритета, и "относительные приоритеты-7" потоков, которые корректируют указанный базовый уровень. Операционная система предоставляет набор функций для управления классами и относительными приоритетами потоков. базов ур:REALTIME 24; HIGH 13; ABOVE_NORMAL 10; NORMAL 8; BELOW_NORMAL 6;IDLE 4.
HIGHEST+2; BELOW_NORMAL -1; ABOVE_NORMAL +1; LOWEST -2; Normal 0.
36 Асинхронный ввод-вывод
Эффективность использования процессора можно было бы повысить, если бы существовала возможность выполнять код программы во время выполнения операций ввода-вывода. Конечно, это не всегда возможно или целесообразно. Например, если для продолжения работы программы необходимы данные, которые еще не получены, то нам все равно надо ожидать завершения ввода-вывода. Более того, структура приложения должна быть разработана с учетом специфики использования асинхронных операций ввода-вывода. В Windows для реализации асинхронного ввода-вывода предусмотрены функции типа ReadFile, WriteFile, ReadFileEx, WriteFileEx и др. и специальная структура OVERLAPPED, которая используется для взаимодействия с асинхронной операцией. Асинхронные операции применяются следующим образом:
- перед началом операции заполняется структура OVERLAPPED;
- вызывается нужная функция для выполнения ввода-вывода, которая ставит операцию в очередь и немедленно возвращает управление вызвавшей программе.
- программа продолжает свою работу независимо от хода выполнения операции ввода вывода.
Для начала надо описать необходимые переменные и открыть файл с разрешением асинхронных операций (FILE_FLAG_OVERLAPPED):
OVERLAPPED ov; DWORD dwWritten; BYTE buffer[ 5000000 ]; HANDLE fh = CreateFile("file.dat", FILE_READ_DATA|FILE_WRITE_DATA, FILE_SHARE_READ, (LPSECURITY_ATTRIBUTES)NULL, OPEN_ALWAYS, FILE_ATTRIBUTE_NORMAL|FILE_FLAG_OVERLAPPED, NULL);
if (fh == INVALID_HANDLE_VALUE) { /* возникла ошибка */ }
ZeroMemory(&ov, sizeof(OVERLAPPED)); FillMemory(buffer, sizeof(buffer), 123);
37 Асинхронные вызовы процедур
Для реализации асинхронного ввода-вывода в операционной системе предусмотрен специальный механизм, основанный на так называемых асинхронных вызовах процедур (Аsynchronous Procedure Call, APC). Это один из базовых механизмов, необходимый для нормального функционирования операционной системы. Практика показала, что такой механизм был бы эффективен и для реализации самих приложений. Для реализации этого механизма операционная система ведет списки процедур, которые она должна вызывать в контексте данного потока, с тем ограничением, что прерывать работу занятого потока в произвольный момент времени система не должна. Вызов процедур происходит, когда поток находится в состоянии ожидания оповещения. Поэтому для обслуживания накопившихся в очереди процедур необходимо перевести поток в специальное состояние ожидания оповещения (alertable waiting) – для этого Win32 API предусматривает специальный набор функций: например, SleepEx, WaitForSingleObjectEx.
VOID CALLBACK ApcProc(ULONG_PTR dwData)
{ /*... */ } int main(void) { QueueUserAPC(ApcProc, GetCurrentThread(), 0); /*... */ SleepEx(1000, TRUE); return 0; }
Обычно APC используются самой системой для реализации асинхронного ввода-вывода и некоторых других операций, но разработчикам также предоставлена функция QueueUserAPC, с помощью которой можно ставить в APC очередь запросы для вызова собственных функций.
38 Процессы, потоки и объекты ядра
ОС создает и манипулирует несколькими различными типами управляющих структур данных, называемых объектами ядра. К объектам ядра относятся процессы, потоки, файлы, семафоры, события, объекты взаимоисключения (mutex), каналы (pipe). Handle-структура, связанная с объектами ядра. Когда объект ядра больше не требуется, его обязательно следует закрыть при помощи универсальной функции CloseHandle.
Каждый объект ядра может находиться в одном из двух состояний: свободном и занятом. Каждый объект ядра имеет счетчик числа пользователей. При создании объекта ядра значение счетчика равно 1. Если при помощи соответствующей функции API поток получает идентификатор объекта ядра типа HANDLE, значение счетчика увеличивается на 1. Функция CloseHandle уменьшает значение счетчика, но объект ядра удаляется из системы если значение счетчика равно 0.
Механизмы доступа к объектам ядра: - Наследование, может ли поток наследовать объекты родителя. Приведет к копированию процесса с Handle. – По собственному уникальному имени, используется группа функций начинающаяся со слова Open. – Процесс владелец может передать Handle любому др. процессу DuplicateHandle, при этом могут быть ограничены права.
Для идентификации процессов и потоков используется Handle – описывает объекты ядра с учетом контекста защиты. Идентификаторы представляют уникальные номера процессов и потоков. Заканчиваются словом id. Функции для работы с Handle и идентификатором – GetCurrentProcess, GetCurrentThread-возвращают текущие описатели процесса и потока.
С каждым процессом и потоком связываются объекты ядра. Объекты ядра связанные с процессами и потоками – описатели. Завершение процесса или потока не приводит к удалению ядра. Функции изменения приоритетов – SetPriorityClass, Get… Thread. Изменение кратковременного приоритета GetProcess(Thread)PriorityPoost.
39 Реализация волокон в ОС Windows
Потоки пользователя являлись переходным этапом между "задачами" и "процессами": с точки зрения операционной системы использовались "задачи", которым выделялись и ресурсы, и процессорное время, тогда как разделение "задачи" на "потоки" осуществлялось непосредственно в самом приложении. В Windows для обозначения этих понятий использованы термины process (процесс), thread (поток) и fiber (волокно). Достаточно часто термин "thread" переводится на русский язык как "нить", а не "поток". Поток соответствует потоку ядра и планируется ядром операционной системы, а волокно соответствует потоку пользователя и планируется в приложении пользователя.
Реализация в Windows-В современных полновесных реализациях виндовс планировщик ядра выделяет процессорное время потокам. Управление волокнами возложено на приложения пользователя: Windows предоставляет набор функций, с помощью которых приложение может управлять созданными волокнами. Фактически для волокон реализуется невытесняющая многозадачность средствами приложения; с точки зрения операционной системы, все волокна должны быть созданы в рамках потоков и система никак не вмешивается в их планирование.
В целях уменьшения затрат на планирование потоков несколько изменен граф состояний потока. Переход из состояния "готовность" в состояние "выполнение» - выбранный к выполнению поток подготавливается к выполнению и переводится в состояние "выбран"; эта подготовка может осуществляться до наступления момента перепланирования, и в нужный момент достаточно просто переключить контекст выполняющегося потока на выбранный. Переход из состояния "ожидание" в "готовность": если ожидание было долгим, то стек потока может быть выгружен из оперативной памяти. В этом случае поток переводится в промежуточное состояние до завершения загрузки стека - в списке готовых к выполнению потоков находятся только те, которые можно начать выполнять без лишнего ожидания.
40 Пулы потоков, порт завершения ввода-вывода
Для реализации пула потоков необходимо создание некоторого количества потоков, занятых обслуживанием запросов, и диспетчера с очередью запросов. При наличии необработанных запросов диспетчер находит свободный поток и передает запрос этому потоку; если свободных потоков нет, то диспетчер ожидает освобождения какого-либо из занятых потоков. Такой подход обеспечивает, малые затраты на управление потоками, достаточно высокую загрузку процессоров и хорошую масштабируемость приложения.
Реализация - необходимо поддерживать очередь запросов и учитывать состояния потоков из пула (поток простаивает; поток выполняется; поток выполняется, но находится в состоянии ожидания). Также следует учитывать возможность выгрузки части данных в файл подкачки (например, выгрузка стека давно не используемого потока) - иногда быстрее подождать завершения работающего потока, чем активировать простаивающий. Для учета всех этих соображений необходимо реализовать поддержку пулов потоков ядром операционной системы, так как на уровне приложения некоторые нужные сведения просто недоступны.
В Windows такая поддержка реализована в виде порта завершения ввода-вывода. Этот объект ядра берет на себя функциональность, необходимую для организации очереди запросов и списков рабочих потоков, обеспечивая оптимальное управление пулом. С точки зрения разработчика приложения необходимо: -создать порт завершения ввода-вывода;
-создать пул потоков, ожидающий поступления запросов от этого порта;
-обеспечить передачу запросов порту.
Порт завершения создается с помощью функции HANDLE CreateIoCompletionPort(); Эта функция выполняет две разных операции - во-первых, она создает новый порт завершения, и, во-вторых, она ассоциирует порт с завершением операций ввода-вывода с заданным файлом. Обе эти операции могут быть выполнены одновременно одним вызовом функции, а могут быть исполнены раздельно. Более того, вторая операция - ассоциирование порта завершения ввода-вывода с реальным файлом - может вообще не выполняться.
В современных реализациях Windows предусмотрена возможность автоматического создания и управления пулом потоков с помощью функции BOOL QueueUserWorkItem(); Эта функция при необходимости создает пул потоков (число потоков в пуле определяется числом процессоров), создает порт завершения ввода-вывода и размещает в очереди порта запрос. Если нужный порт и пул потоков уже созданы, то она просто размещает новый запрос в очереди порта.
49 Управление потоками в ОС Windows
Создание потоков- Каждый поток начинает выполнение с некоторой входной функции. В первичном потоке используется одна из функций: WinMain() или main(). Для создания вторичного потока необходимо определить его входную функцию.
При необходимости можно создать поток в виртуальном адресном пространстве другого процесса.
Завершение потока можно организовать четырьмя способами:
- Функция потока возвращает управление (предпочтительный способ)
- Поток самоуничтожается вызовом функции ExitThread
- Один из потоков данного или стороннего процесса вызывает функцию TerminateThread
- Завершается процесс, содержащий данный поток
41 Память, локальная для потоков и волокон
В Windows предусмотрен механизм управления данными, локальными для потока (TLS, Thread Local Storage). Система предоставляет небольшой специальный блок данных, ассоциированный с каждым потоком. Память используется для передачи указателя на данные. В таком блоке возможно в общем случае хранение произвольных данных, обычно там размещаются указатели на данные большего объема, выделяемые в приложении для каждого потока. Windows предоставляет четыре функции, необходимые для работы с локальной для потока памятью. Функция DWORD TlsAlloc(void) выделяет в ассоциированной с потоком памяти двойное слово, индекс которого возвращается вызвавшей процедуре. Функция TlsFree освобождает выделенную ячейку. Если поток выделил некоторую ячейку в ассоциированном массиве, то все потоки данного процесса могут обращаться к ячейке с этим индексом - они получат доступ к ячейкам своих собственных ассоциированных массивов и не смогут узнать или изменить значения, сохраненные в этих ячейках другими потоками. TlsGetValue, возвращающая значение данной ячейки и TlsSetValue, изменяющая значение в соответствующей ячейке.
TLS память является общей для всех потоков процесса. Замечания: необходимо освобождать указатели, которые хранятся в TLS памяти; память начинает существовать, когда существуют потоки.
Windows поддерживает память, локальную для волокон, - так называемую FLS память, или Fiber Local Storage. При этом FLS память не зависит от того, какой именно поток выполняет данную нить. Для работы с FLS памятью Windows предоставляет набор функций, аналогичный Tls-функциям, отличие заключается только в функции выделения ячейки FLS памяти: DWORD FlsAlloc(PFLS_CALLBACK_FUNCTION lpCallback); Функция отличается от ее аналога TlsAlloc указателем на специальную необязательную процедуру FlsCallback, предоставляемую разработчиком. Эта процедура будет вызвана автоматически при освобождении ячейки FLS памяти, и разработчик может легко предоставить средства для освобожд. памяти, указатели на которую были сохранены в ячейках FLS памяти.
42 Синхронизация потоков ОС Windows
Основные средства взаимной синхронизации потоков:
-Мониторы, близкие к критическим секциям.
-События и мьютексы, имеющие соответ. аналоги среди объектов ядра.
Задачу синхронизации потоков различных процессов принято решать с помощью объектов ядра. Объекту ядра может быть присвоено имя, они позволяют задавать тайм-аут для времени ожидания и обладают еще рядом возможностей для реализации гибких сценариев синхронизации. Если поток выполняется, то он находится в занятом состоянии, а если поток успешно завершил ожидание семафора, то семафор находится в занятом состоянии.
Потоки находятся в состоянии ожидания, пока ожидаемые ими объекты заняты. Как только объект освобождается, ОС будит поток и позволяет продолжить выполнение. Для приостановки потока и перевода его в состояние ожидания освобождения объекта используется функция DWORD WaitForSingleObject(1,2); где 1 - описатель ожидаемого объекта ядра, а второй параметр - максимальное время ожидания объекта.
Поток создает объект ядра при помощи семейства функций Create (CreateSemaphore, CreateThread и т.д.), после чего объект посредством описателя становится доступным всем потокам данного процесса. Копия описателя может быть получена при помощи функции DuplicateHandle и передана другому процессу, после чего потоки смогут воспользоваться этим объектом для синхронизации.
43 События
Обычно событие - некоторый объект, который может находиться в одном из двух состояний: занятом или свободном.
В Windows различают события с ручным и с автоматическим сбросом (CreateEvent). События с ручным сбросом ведут себя обычным образом: функция SetEvent переводит событие в свободное состояние, а функция ResetEvent - в занятое. События с автоматическим сбросом переводятся в занятое состояние либо явным вызовом функции ResetEvent, либо ожидающей функцией WaitFor.... Поведение событий с ручным и автоматическим сбросом особенно различаются в случае, если несколько потоков ждут одного события, для события с ручным сбросом, при установке его в свободное состояние, выполнение могут продолжить все ожидающие потоки. Для события с автоматическим сбросом - только один, так как событие будет сразу переведено в занятое состояние. В некоторых случаях бывает надо перевести событие в свободное состояние, чтобы ожидающие на данный момент времени потоки могли продолжить свое выполнение, после чего снова вернуть в занятое. Вместо пары вызовов, SetEvent...ResetEvent, во время выполнения которых планировщик вполне может переключиться на другие потоки, целесообразно использовать функцию PulseEvent, которая как бы выполняет сброс и установку события, но в рамках одной операции.
44 Семафоры
Семафор представляет собой счетчик, который считается свободным, если значение счетчика больше нуля, и занятым при нулевом значении. При создании семафора задаются его максимально допустимое и начальное состояния. Ожидающие функции WaitFor... уменьшают значение свободного семафора на 1, если счетчик ненулевой, или переходят в режим ожидания до тех пор пока кто-либо не увеличит значение семафора. Увеличение счетчика осуществляется функцией ReleaseSemaphore.
Семафоры предназначены для ограничения числа потоков, имеющих одновременный доступ к какому-либо ресурсу.
P(S): пока S 0 процесс блокируется;
S = S – 1;
V(S): S = S + 1;
Эта запись означает следующее: при выполнении операции P над семафором S сначала
проверяется его значение. Если оно больше 0, то из S вычитается 1. Если оно меньше или
равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вы-
читается 1. При выполнении операции V над семафором S к его значению просто прибав-
ляется 1. В момент создания семафор может быть инициализирован любым неотрицатель-
ным значением.
45 Мьютексы
Объекты исключительного владения могут быть использованы в одно время не более чем одним потоком. В этом отношении мьютексы подобны критическим секциям, с той оговоркой, что работа с ними выполняется в режиме ядра (при использовании критических секций переход в режим ядра необязателен) и что мьютексы могут быть использованы для межпроцессного взаимодействия, тогда как критические секции реализованы для применения внутри процесса. Для захвата мьютекса используется ожидающая функция WaitFor..., а для освобождения - функция ReleaseMutex. При создании мьютекса функцией CreateMutex можно указать, чтобы он создавался сразу в занятом состоянии.
46 Ожидающие таймеры
Эти объекты предназначены для выполнения операций через заданные промежутки времени или в заданное время. Таймеры бывают периодическими или однократными, также их разделяют на таймеры с ручным сбросом и синхронизирующие.
Таймеры могут служить в качестве синхронизирующих объектов, а могут вызывать указанную разработчиком функцию, если поток в нужное время находится в ожидании оповещения. Следует подчеркнуть, что ожидающие таймеры обладают ограниченной точностью работы. При необходимости точно планировать время выполнения (например, в случае обработки потоков мультимедиа данных) надо использовать специальный таймер, предназначенный для работы с мультимедиа (функции timeGetSystemTime, timeBeginPeriod и др.).
47 Мониторы
Монитор обладает собственными переменными, определяющими его состояние. Значения этих переменных извне могут быть изменены только с помощью вызова функций-методов, принадлежащих монитору. В свою очередь, эти функции-методы могут использовать в работе только данные, находящиеся внутри монитора, и свои параметры.
Важной особенностью мониторов является то, что в любой момент времени только один процесс может быть активен, т. е. находиться в состоянии готовность или исполнение, внутри данного монитора. Поскольку мониторы представляют собой особые конструкции языка программирования, компилятор может отличить вызов функции, принадлежащей монитору, от вызовов других функций и обработать его специальным образом, добавив к нему пролог и эпилог, реализующий взаимоисключение. Так как обязанность конструирования механизма взаимоисключений возложена на компилятор, а не на программиста, работа программиста при использовании мониторов существенно упрощается, а вероятность возникновения ошибок становится меньше.
Нужны еще и средства организации очередности процессов. Для этого в мониторах было введено понятие условных переменных (condition variables), над которыми можно совершать две операции wait и signal.
Если функция монитора не может выполняться дальше, пока не наступит некоторое событие, она выполняет операцию wait над какой-либо условной переменной. При этом процесс, выполнивший операцию wait, блокируется, становится неактивным, и другой может войти в монитор.
Когда ожидаемое событие происходит, другой процесс внутри функции-метода совершает операцию signal над той же самой условной переменной. Это приводит к пробуждению ранее заблокированного процесса, и он становится активным
48 Управление процессами в ОС Windows
Создание процессов - используются функции CreateProcess, CreateProcessAsUser, CreateProcessWithLogonW. Функция CreateProcess создает новый процесс, который будет исполняться от имени текущего пользователя потока, вызвавшего эту функцию. Функция CreateProcessAsUser позволяет запустить процесс от имени другого пользователя, который идентифицируется его маркером безопасности (security token); однако вызвавший эту функцию поток должен принять меры к правильному использованию реестра, так как профиль нового пользователя не будет загружен. Функции CreateProcessWithTokenW и CreateProcessWithLogonW позволяют при необходимости загрузить профиль пользователя и, кроме того, функция CreateProcessWithLogonW сама получает маркер пользователя по известному учетному имени, домену и паролю. При создании процесса ему можно передать описатели каналов (CreatePipe), предназначенные для перенаправления stdin, stdout и stderr. Описатели каналов должны быть наследуемыми.
Для завершения процесса рекомендуется применять функцию ExitProcess, которая завершит процесс, сделавший этот вызов. В крайних случаях можно использовать функцию TerminateProcess, которая может завершить процесс, заданный его описателем. Этой функцией пользоваться не рекомендуется, так как при таком завершении разделяемые библиотеки будут удалены из адресного пространства уничтожаемого процесса без предварительных уведомлений - это может привести в некоторых случаях к утечке ресурсов.
50 Адресное пространство процесса и проецирование файлов
В Windows потоки работают в одном адресном пространстве процесса, поэтому обмен данными между ними в большинстве случаев сводится к доступу к общей разделяемой памяти. Иная ситуация в случае взаимодействия потоков, принадлежащим разным процессам: так как адресное пространство процессов изолировано друг от друга, то приходится принимать специальные меры для передачи данных из адресного пространства одного процесса в адресное пространство другого. Доступная пользователю часть адресного пространства процесса выделяется реально не в физической оперативной памяти, а в файлах, данные которых проецируются на соответствующие фрагменты адресного пространства. Выделение памяти без явного указания проецируемого файла приведет к тому, что область для проецирования будет автоматически выделяться в файле подкачки страниц. Важная особенность средств управления адресным пространством и проецированием файлов - они используют так называемую гранулярность выделения ресурсов. Это означает, что если вы попробуете спроецировать в память файл размером 100 байт, то в адресном пространстве будет занят фрагмент в 65536 байт длиной, из которого реально будут заняты первые 100 байт. Для управления адресным пространством предназначены функции VirtualAlloc, VirtualFree, VirtualLock и VirtualUnlock. С их помощью можно резервировать пространство в адресном пространстве процесса и управлять передачей памяти из файла подкачки страниц указанному диапазону адресов. Функции создания процессов (CreateProcess...) и загрузки библиотек (LoadLibrary), помимо специфичных действий, выполняют проецирование исполняемых файлов в адресное пространство процесса; при этом учитывается их деление на сегменты, наличие секций импорта, экспорта и релокаций. Обычные файлы проецируются как непрерывный блок данных на непрерывный диапазон адресов. Для явного проецирования файлов используется специальный объект ядра проекция файла (file mapping). Этот объект предназначен для описания файла, который может быть спроецирован в память, но реального отображения файла или его части в память при создании проекции не происходит. Описатель объекта "проекция файла" можно получить с помощью функций CreateFileMapping и OpenFileMapping. Для проецирования файла или его части в память предназначены функции MapViewOfFile, MapViewOfFileEx и UnmapViewOfFile.
51 Параллельные операции в.NET
Реализация параллельного выполнения кода в.NET основана на базовых механизмах, предоставляемых ядром Windows. Аналогично средствам ос средства.NET могут быть разделены на след. группы:
-Обработка асинхронных запросов. относятся средства для выполнения асинхронных операций ввода-вывода, средства для работы с очередями сообщений.
-Организация многопоточных приложений. относятся средства создания потоков, управления ими, включая пулы потоков, средства взаимной синхронизации, а также организация локальной для потоков памяти.
-Работа с различными процессами и доменами приложений.
Деление не является строгим - реальные средства "пересекают" границы этих категорий. При этом не все механизмы, предоставляемые операционной системой, нашли свое отражение в.NET; равно как многие механизмы, оставаясь внешне схожими с механизмами операционной системы, существенным образом изменились..NET не поддерживает волокна; операции асинхронного ввода-вывода основываются на использовании отдельных потоков, выполняющих фоновые синхронные операции ввода-вывода. Вообще говоря, использование фоновых потоков для выполнения специфических задач поддержки инфраструктуры.NET стало общим местом. При запуске.NET приложения автоматически создается пул потоков. Этот пул применяется в ситуациях, связанных с обработкой асинхронных запросов и асинхронного ввода-вывода, когда в рамках операционной системы реально использовался бы основной поток в состоянии ожидания оповещения.
52 Потоки и пул потоков в.NET
классы для реализации многопоточных приложений определены в пространстве имен System.Threading. Для описания собственных потоков предназначен класс Thread. Поток в.NET может находиться в одном из следующих состояний: незапущенном, исполнения, ожидания, приостановленном, завершенном и прерванном. Текущее состояние можно определить с помощью свойства Thread.ThreadState. После запуска поток можно перевести в состояние исполнения вызовом метода Thread.Start. Работающий поток может быть переведен в состояние ожидания явным или неявным вызовом соответствующих методов (Thread.Sleep, Thread.Join) или приостановлен с помощью метода Thread.Suspend(). Исполнение приостановленного потока можно возобновить вызовом метода Thread.Resume. Завершение функции потока нормальным образом переводит поток в состояние "завершен", а досрочное прекращение работы вызовом метода Thread.Abort переведет его в состояние "прерван". Для выполнения задержек в ходе выполнения потока предназначены два метода - Sleep, переводящий поток в состояние ожидания на заданное время. Для получения и задания приоритета потока используется свойство Thread.Priority. В.NET используются приоритеты Highest, AboveNormal, Normal, BelowNormal и Lowest. Пул потоков, используемый средой для реализации асинхронных операций ввода-вывода, вызова асинхронных процедур, обработки таймеров и других целей. Потоки могут добавляться в пул по мере надобности. Этот пул реализуется на основе пула потоков, управляемого операционной системой. Для взаимодействия с пулом потоков предусмотрен класс ThreadPool. Все домены приложений в рамках одного процесса используют общий пул потоков.
Можно управлять числом потоков в пуле (методы GetAvailableThreads, GetMaxThreads, GetMinThreads и SetMinThreads), можно ставить в очередь асинхронных вызовов собственные процедуры (метод QueueUserWorkItem) и назначать процедуры, которые будут вызываться при освобождении какого-либо объекта (метод RegisterWaitForSingleObject). Эти два метода имеют "безопасные" и "небезопасные" версии; последние отличаются тем, что в стеке вызовов асинхронных методов не будут присутствовать данные о реальном контексте безопас. потока, поставившего в очередь этот вызов, - будет использоваться контекст безопас. самого пула потоков.
53 Асинхронный ввод-вывод в.NET
Для реализации асинхронного ввода-вывода в.NET предназначен абстрактный класс System.IO.Stream. В этом классе определены абстрактные синхронные методы чтения Read и записи Write, а также реализация асинхронных методов BeginRead, EndRead, BeginWrite и EndWrite. Асинхронные методы реализованы с помощью обращения к синхронным операциям фоновыми потоками пула. На основе абстрактного класса Stream в.NET Framework реализуются потомки, осуществляющие взаимодействие с разного рода потоками данных. Так, например, System.IO.FileStream реализует операции с файлами, System.IO.MemoryStream предоставляет возможность использования байтового массива в качестве источника или получателя данных, System.IO.BufferedStream является "надстройкой" над другими объектами, производными от System.IO.Stream, и обеспечивает буферизацию запросов чтения и записи. Некоторые классы вне пространства имен Sytem.IO также являются потомками Stream. Так, например, класс System.NET.Sockets.NetworkStream обеспечивает сетевое взаимодействие.
При реализации собственных потомков класса Stream, возможно, будет иметь смысл переопределить абстрактные методы Read и Write, BeginRead, ReadByte.
54 Асинхронные процедуры в.NET
Для реализации вызова асинхронных процедур в.NET используются фоновые потоки пула, так же как для обработки асинхронных операций ввода-вывода. Класс ThreadPool предлагает два способа для вызова асинхронных процедур: явное размещение вызовов в очереди (QueueUserWorkItem) и связывание вызовов с переводом некоторых объектов в свободное состояние (RegisterWaitForSingleObject). Кроме того,.NET позволяет осуществлять асинхронные вызовы любых процедур с помощью метода BeginInvoke делегатов.
Статический метод ThreadPool.QueueUserWorkItem ставит вызов указанной процедуры в очередь для обработки. Если пул содержит простаивающие потоки, то обработка этой функции начнется немедленно. При постановке в очередь асинхронного вызова можно указать объект, который является аргументом асинхронной процедуры.
Второй способ вызова асинхронных процедур связан с использованием объектов, производных от класса System.Threading.WaitHandle (это события и мьютексы). Данный метод может быть использован для организации повторяющегося через определенные интервалы вызова асинхронных процедур. Последний способ связан с использованием методов BeginInvoke и EndInvoke делегатов. Использование BeginInvoke позволяет не только поставить в очередь вызов асинхронной процедуры, но также связать с завершением ее обработки еще один асинхронный вызов. Метод EndInvoke служит для ожидания завершения обработки асинхронной процедуры.
55 Синхронизация и изоляция потоков в.NET
.NET предоставляет в значительной мере близкий набор средств взаимодействия потоков и их взаимной синхронизации - атомарные операции, локальная для потока память, синхронизирующие примитивы и таймеры.
Атомарные операции -Платформа.NET предоставляет, аналогично базовой операционной системе Windows, набор некоторых основных операций над целыми числами, которые могут выполняться атомарно. Для этого предусмотрены четыре статических метода класса System.Threading.Interlocked, а именно Increment, Decrement, Exchange и CompareExchange.
Основные средства взаимной синхронизации потоков выделить:
- Мониторы, близкие к критическим секциям.
- События и мьютексы, имеющие соответствующие аналоги среди объектов ядра.
Класс Monitor, определенный в пространстве имен System.Threading, предлагает несколько статических методов для работы с записями синхронизации. Методы Enter и Exit являются наиболее применяемыми и соответствуют функциям EnterCriticalSection и LeaveCriticalSection операционной системы. Аналогично критическим секциям, мониторы могут использоваться одним потоком рекурсивно. Еще несколько методов класса Monitor - Wait, Pulse и PulseAll - позволяют при необходимости временно разрешить доступ к объекту другому потоку, ожидающему его освобождения, не покидая критической секции.
Любой параллельно выполняющийся фрагмент кода сохраняет полную возможность обращаться со всеми объектами, независимо от того, связаны они с какими-либо блокировками или нет.
56 Ожидающие объекты в.NET
.NET предоставляет базовый класс WaitHandle, служащий для описания объекта, который находится в одном из двух состояний: занятом или свободном. На основе этого класса строятся другие классы синхронизирующих объектов.NET, такие как события (ManualResetEvent и AutoResetEvent) и мьютексы (Mutex).
Существует три метода класса WaitHandle для ожидания освобождения объекта: метод WaitOne, являющийся методом объекта, и статические методы WaitAny и WaitAll. Метод WaitOne является оберткой вызова WaitForSingleObject Win32 API, а методы WaitAny и WaitAll - вызова WaitForMultipleObjects. Объекты класса WaitHandle и производных от него, представляя объекты ядра операционной системы, могут быть использованы для межпроцессного взаимодействия. Конструкторы производных объектов (событий и мьютексов) позволяют задать имя объекта ядра, предназначенное для организации общего доступа к объектам процессами. Потоки не являются наследниками класса WaitHandle в силу того, что для разных базовых платформ потоки могут быть реализованы в качестве потоков операционной системы или легковесных потоков. В последнем случае потоки.NET не будут иметь никаких аналогов среди объектов ядра операционной системы. Для синхронизации с потоками надо использовать метод Join класса Thread.
57 Архитектура процессов в ОС Linux
Процессы в линукс функционируют в двух режимах: системный и пользовательский. Системный-обработка системных вызовов. Пользовательский- выполнение пользовательского кода. Нельзя допускать процессы в системный режим. Для системных характерно FCFS, для пользовательских –RR. Для каждого процесса создается PCB блок. Он помещается в системную таблицу. Все системные таблицы находятся внутри ядра.
Дата добавления: 2015-12-01; просмотров: 69 | Нарушение авторских прав