2009 overview ИУС РВ (1185197), страница 6
Текст из файла (страница 6)
Ресурс при этом перейдет в состояние «занят».В схематичном виде поведение процессов может быть представлено следующим образом.Процесс A попадает в критическую область в момент времени T1. В момент времени T2 процессB пытается попасть в критическую область, но ему это не удается, поскольку в критическойобласти уже находится процесс A, а два процесса не должны одновременно находиться вкритических областях. Поэтому процесс B приостанавливается до наступления моментавремени T3, когда процесс A выходит из критической области. В момент времени T4 процесс Bпокидает критическую область.Процесс A попадает вкритическую областьПроцесс A покидаеткритическую областьПроцесс AПроцесс B пытаетсяПроцесс B попадает впопадасть вкритическую областькритическую областьПроцесс B покидаеткритическую областьПроцесс BT1T2Процесс BблокированT3T4При взаимодействии процессов возможны следующие проблемы:Смертельный захват, тупик (Deadlock). Обычно побочные эффекты этой ситуацииназываются более прозаично – «зацикливание» или «зависание».
А причина этого может бытьдостаточно проста – «задачи не поделили ресурсы». Пусть, например, Задача A захватиларесурс клавиатуры и ждет, когда освободится ресурс дисплея, а в это время Задача B, успевзахватить ресурс дисплея, ждет теперь, когда освободится клавиатура. В таких случаяхрекомендуется придерживаться тактики «или все, или ничего». Другими словами, если задачане смогла получить все необходимые для дальнейшей работы ресурсы, она должна освободитьвсе, что уже захвачено, и повторить попытку только через определенное время. Другимрешением, которое уже упоминалось, является использование серверов ресурсов.Инверсия приоритетов (Priority inversion).
Представим, что у нас естьвысокоприоритетная Задача A, среднеприоритетная Задача B и низкоприоритетная Задача C.Пусть в начальный момент времени Задачи A и B блокированы в ожидании какого-либовнешнего события. Допустим, получившая в результате этого управление Задача C захватилаРесурс A, но не успела его отдать, как была прервана Задачей A. В свою очередь, Задача A припопытке захватить Ресурс A будет блокирована, так как этот ресурс уже захвачен Задачей C.Если к этому времени Задача B находится в состоянии готовности, то управление после этогополучит именно она, как имеющая более высокий, чем у Задачи C, приоритет. Теперь Задача Bможет занимать процессорное время, пока ей не надоест, а мы получаем ситуацию, когдавысокоприоритетная Задача A не может функционировать из-за того, что необходимый ейресурс занят низкоприоритетной Задачей C.Блокировка (Lockout).
Процесс ожидает ресурс, который никогда не освободится.Голодовка (Starvation). Процесс монополизировал процессор.Взаимоблокировки. Выгружаемые и невыгружаемые ресурсы. Условия возникновениявзаимоблокировок. Граф ресурсов. Стратегии решения проблемы взаимоблокировок.Обнаружение тупиков и восстановление работоспособности системы.В компьютерной системе существует большое количество ресурсов, каждый из которыхможет использоваться в конкретный момент времени только одним процессом. Часто процессдля выполнения задачи нуждается в исключительном доступе не к одному, а к несколькимресурсам. Предположим, что имеется два процесса A и B.
Процесс A имеет в исключительномдоступе ресурс R1, процесс B – ресурс R2. Если при этом процессу A для продолжения работыпотребуется ресурс R2, то его запрос на получение ресурса будет отклонен до тех пор, покаресурс не будет освобожден процессом B. Если же при этом процессу B для продолженияработы окажется необходимым иметь в исключительном доступе ресурс R1, то и процесс Bокажется, как и процесс A, заблокированным. Такая ситуация называется тупиком, тупиковойситуацией или взаимоблокировкой.Система может зайти в тупик, когда процессам предоставляются исключительные правадоступа к ресурсам. С рассматриваемой здесь точки зрения ресурсы могут быть разделены надва типа: выгружаемые и невыгружаемые. Выгружаемый ресурс можно безболезненно забратьу владеющего им процесса.
Образцом такого ресурса является память. Невыгружаемыйресурс, в противоположность выгружаемому, - это такой ресурс, который нельзя забрать утекущего процесса без уничтожения результатов вычислений. Если в момент записи компактдиска внезапно забрать у процесса устройство для записи и передать его другому процессу, врезультате получим испорченный компакт-диск.Вообще говоря, взаимоблокировки касаются невыгружаемых ресурсов. Потенциальныетупиковые ситуации, в которые вовлечены выгружаемые ресурсы, обычно можно разрешить спомощью перераспределения ресурсов от одного процесса другому.Взаимоблокировки или тупиковые ситуации формально можно определить так:Группа процессов находится в тупиковой ситуации, если каждый процесс из группыожидает события, которое может вызвать только другой процесс из той же группы.Так как все процессы находятся в состоянии ожидания при возникновении блокировки, тони один из них не будет причиной какого-либо события, которое могло бы активировать любойдругой процесс в группе, и все процессы продолжат ждать до бесконечности.
В этой моделипредполагается наличие только одного потока у каждого процесса и отсутствие прерываний,способных активизировать заблокированный процесс. Условие отсутствия прерыванийнеобходимо, чтобы предотвратить ситуацию, когда тот или иной заблокированный процессактивизируется, скажем, по сигналу тревоги и затем приводит к событию, которое освободитдругие процессы в группе. В большинстве случаев событием, которого ждет каждый процесс,является возврат какого-либо ресурса, в данный момент занятого другим участником группы.Исследования показали, что для возникновения ситуации взаимоблокировки должнывыполняться 4 условия:1. Условие взаимного исключения.
Каждый ресурс в данный момент времени илиотдан одному процессу, или доступен.2. Условие удержания и ожидания. Процессы, в данный момент удерживающиеполученные ранее ресурсы, могут запрашивать новые ресурсы.3. Условие отсутствия принудительной выгрузки ресурса. У процесса нельзяпринудительным образом забрать ранее полученные ресурсы. Процесс, владеющийими, должен сам освободить ресурсы.4. Условиециклическогоожидания.Должнасуществоватькруговаяпоследовательность из двух или более процессов, каждый из которых ждет доступак ресурсу, удерживаемому следующим членом последовательности.Для того, чтобы произошла взаимоблокировка, должны выполниться все четыре условия.Если хоть одно условие отсутствует, тупиковая ситуация невозможна.Условия возникновения тупиков можно смоделировать, используя направленные графы.Графы имеют два вида узлов: процессы, показанные кружочками, и ресурсы, изображающиесяквадратиками.
Ребро, направленное от узла ресурса к узлу процесса (от квадрата к кругу),означает, что ресурс ранее был запрошен процессом, получен и в данный момент используетсяданным процессом. Ребро, направленное от процесса к ресурсу (от круга к квадрату), означает,что процесс в данный момент блокирован и находится в состоянии ожидания доступа к этомуресурсу.ASDTRBUCНа рисунке выше показаны следующие ситуации. Ресурс R в настоящий момент времениотдан процессу A. Процесс B ждет ресурс S.
Процессы C и D находятся в состояниивзаимоблокировки: процесс C ожидает ресурс T, удерживаемый в настоящий момент процессомD. Процесс D не освобождает ресурс T, так как B ждет ресурс U, используемый процессом C.Оба процесса могут ждать до бесконечности.Вообще говоря, при столкновении с взаимоблокировками используются четыре стратегии:1.
Пренебрежение проблемой в целом. Если вы проигнорируете проблему, возможно,затем она проигнорирует вас.2. Обнаружение и восстановление. Позволить взаимоблокировке произойти,обнаружить ее и предпринять какие-либо действия.3. Динамическое избежание тупиковых ситуаций с помощью аккуратногораспределения ресурсов.4. Предотвращение с помощью структурного опровержения одного из четырехусловий, необходимых для взаимоблокировки.Рассмотрим каждый из этих четырех методов.Самым простым подходом является «страусовый алгоритм»- притвориться, что проблемавообще не существует.
Большая часть операционных систем, включая UNIX и Windows,игнорируют эту проблему. Они исходят из предположения, что большинство пользователейпредпочтут иметь дело со случающимися время от времени взаимоблокировками, чем справилом, по которому всем пользователям разрешается только один процесс, один открытыйфайл и т.д.Вторая техника представляет собой обнаружение и восстановление.
При использованииэтого метода система не пытается предотвратить попадание в тупиковые ситуации. Вместоэтого она позволяет взаимоблокировке произойти, старается определить, когда это случилось, изатем совершает некие действия к возврату системы к состоянию, имевшему место до того, каксистема попала в тупик. Рассмотрим эту технику на примере простого варианта: в системесуществует только один ресурс каждого типа. Для такой системы можно сконструировать графресурсов. Если граф ресурсов содержит один или более циклов, то произошлавзаимоблокировка и блокирован любой процесс, являющийся частью цикла.
Если в графе нетциклов, система не попала в тупик.В качестве примера рассмотрим систему с семью процессами, обозначенными буквами отA до G, и шестью ресурсами, обозначенными буквами от R до W. Состояние системы в данныймомент времени соответствует следующему списку:• Процесс A занимает ресурс R и хочет получить ресурс S.• Процесс B ничего не использует, но хочет получить ресурс T.• Процесс C ничего не использует, но хочет получить ресурс S.• Процесс D занимает ресурс U и хочет получить ресурсы S и T.• Процесс E занимает ресурс T и хочет получить ресурс V.••Процесс F занимает ресурс W и хочет получить ресурс S.Процесс G занимает ресурс V и хочет получить ресурс U.RABCSDFUWGTEVИз построенного графа ресурсов видно, что он содержит цикл и процессы D,E,Gзаблокированы.
Процессы A,C,F не попали в тупик, потому что любому из них можнопредоставить ресурс S, после чего процесс, получивший ресурс, закончит работу и вернетресурс. Затем два других процесса по очереди также могут получить ресурс и успешновыполнить свою работу.Обнаружив тупик, необходимо ликвидировать взаимоблокировку. Рассмотрим методывосстановления работоспособности системы.Восстановление при помощи принудительной выгрузи ресурсов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
