Контрольная работа по "Информатике"

Вопрос: «Заблокирована ли эта система и если да, то какие процессы в этом участвуют?»

Чтобы ответить на этот вопрос, мы можем составить  граф ресурсов (рис. 3.3, а). Этот граф содержит один цикл, который виден при визуальном обследовании. Цикл показан на рис. 3(б). Изучая его, можно заметить, что процессы D, E и G заблокированы. Процессы А, С и F не попали в тупик, потому что любому из них можно предоставить ресурс 5, после чего процесс, получивший ресурс, закончит свою работу и вернет ресурс. Затем два других процесса по очереди могут получить ресурс и также успешно выполнить свою работу.

Рис. 3. Граф ресурсов (а); цикл, извлеченный из а (б)

Рассмотрим  простой алгоритм, который изучает  граф и завершается или когда  находит цикл, или когда показывает, что циклов в этом графе не существует. Он использует одну структуру данных — список узлов L. Во время работы алгоритма на ребрах графа будет ставиться метка, говорящая о том, что их уже проверили, это делается во избежание повторной проверки. Алгоритм работает, осуществляя пять перечисленных ниже шагов.

1. Для каждого  узла N в графе выполняются следующие  пять шагов, где N является начальным  узлом.

2. Задаем начальные  условия: L — пустой список, все  ребра не маркированы.

3. Текущий узел  добавляем в конец списка L и  проверяем количество появлений  узла в списке. Если узел присутствует в двух местах, граф содержит цикл (записанный в список L) и работа алгоритма завершается.

4. Для заданного  узла смотрим, выходит ли из  него хотя бы одно немаркированное  ребро. Если да, то переходим  к шагу 5, если нет, то переходим к шагу 6.

5. Случайным  образом выбираем любое немаркированное  исходящее ребро и отмечаем  его. Затем по нему переходим  к новому текущему узлу и  возвращаемся к шагу 3.

6. Теперь мы  зашли в тупик. Удаляем последний  узел из списка и возвращаемся  к предыдущему узлу, то есть тому, который был текущим перед тупиковым узлом. Обозначаем его текущим узлом и возвращаемся к шагу 3. Если это первоначальный узел, граф не содержит циклов и алгоритм завершается. Этот алгоритм по очереди берет каждый узел в качестве корня того, что, как он надеется, окажется деревом, и выполняет в дереве поиск в глубину. Если в процессе обхода алгоритм возвращается к уже встречавшемуся узлу, то он нашел цикл. Если алгоритм обходит все ребра из какого-нибудь заданного узла, то он возвращается к предыдущему узлу. Если он возвращается к корню и не может идти дальше, то подграф текущего узла не содержит циклов. Если данное свойство сохраняется для всех узлов, значит, полный граф не содержит циклов, а система не заблокирована. Алгоритм далеко не оптимален, однако он приведен лишь для демонстрации подхода. На практике применяются более сложные алгоритмы.

??? Вопрос 26. Поиск взаимоблокировки при использовании нескольких ресурсов каждого типа

Когда в системе существует несколько экземпляров некоторых из ресурсов, для обнаружения взаимоблокировок необходим другой метод, который основан на матрицах, и обнаруживающем тупики среди n n процессов, от 1 P до n P . Пусть m — это число классов ресурсов, причем в системе 1 E ресурсов класса 1, 2 E ресурсов класса 2 и Ei , ресурсов класса i (где 1 ≤ i ≤ m ). E — это вектор существующих ресурсов. Он передает общее количество имеющихся в наличии экземпляров каждого ресурса. Например, если класс 1 представляет собой накопители на магнитных лентах, то 2 1 E = означает, что в системе есть два магнитофона. В любой момент времени некоторые из ресурсов могут оказаться занятыми и, соответственно, недоступны. Пусть A будет вектором доступных ресурсов, где i A равно количеству экземпляров ресурса i , доступных в текущий момент (то есть не использующихся). Если оба накопителя на магнитной ленте заняты, A1 = 0 . Теперь нам нужны два массива: C — матрица текущего распределения и R — матрица запросов, i -я строка в матрице C говорит о том, сколько представителей каждого класса ресурсов в данный момент использует процесс i P . Таким образом, ij C - это количество экземпляров ресурса j , которое занимает процесс i . Аналогично, ij R — это количество экземпляров ресурса j , которые хочет получить процесс i P . Эти четыре структуры показаны на рис. 4.

Рис. 4. Четыре структуры  данных, необходимые для алгоритма  обнаружения тупиков

Для этих четырех  структур данных существует важный инвариант. В принципе каждый ресурс или занят, или свободен. Другими словами, если сложить все экземпляры ресурса, предоставленные процессам и доступные в данный момент, то в результате мы получим существующее в системе количество экземпляров этого класса ресурсов.

Вопрос 27. Алгоритмы  восстановления работоспособности  системы после обнаружения взаимоблокировки

Восстановление  при помощи принудительной выгрузки ресурсов. Иногда можно отобрать ресурс у его текущего владельца и отдать его другому процессу. Способность забирать ресурс у процесса, отдавать его другому процессу и затем возвращать назад так, чтобы исходный процесс этого не замечает, в значительной мере зависит от свойств ресурса. Выйти из тупика таким образом зачастую трудно или невозможно. Выбор приостанавливаемого процесса главным образом зависит от того, какой процесс владеет ресурсами, которые легко могут быть у него отняты. Во многих случаях требуется ручное вмешательство.

Восстановление  через откат. Если разработчики системы знают, что есть вероятность взаимоблокировки, они могут организовать работу таким образом, чтобы процессы периодически создавали контрольные точки. Созданные процессом контрольные точки означают, что состояние процесса записывается в файл, в результате чего впоследствии процесс может быть возобновлен из этого файла. Контрольные точки содержат не только образ памяти, но и состояние ресурсов, то есть информацию о том, какие ресурсы в данный момент предоставлены процессу. Когда взаимоблокировка обнаружена, достаточно понять, какие ресурсы нужны процессам. Чтобы выйти из тупика, процесс откатывается к тому времени, перед которым он получил данный ресурс, для чего запускается одна из его контрольных точек. Вся работа, выполненная после этой контрольной точки, теряется. В результате процесс вновь запускается с более раннего момента, когда он не занимал тот ресурс, который теперь предоставляется одному из процессов, попавших в тупик. Если возобновленный процесс вновь пытается получить данный ресурс, ему придется ждать того момента, когда ресурс опять станет доступен.

Восстановление  путем уничтожения процессов. Простейший способ выхода из тупика заключается в уничтожении одного или нескольких процессов. Легче всего уничтожать те процессы, которые можно запустить сначала без всяких болезненных эффектов. При этом могут быть уничтожены как процессы, входящие в цикл взаимоблокировки, так и процессы, не находящиеся в цикле, но владеющие ресурсами, необходимыми заблокированным процессам. В большинстве систем процессы запрашиваются не все сразу, а поочередно. Система должна уметь решать, является ли предоставление ресурса безопасным или нет, и предоставить его процессу только в первом случае.

Основные алгоритмы, позволяющие предотвращать взаимоблокировки, базируются на концепции безопасных состояний. Говорят, что состояние безопасно, если оно не находится в тупике и существует некоторый порядок планирования, при котором каждый процесс может работать до завершения, даже если все процессы вдруг захотят немедленно получить максимальное количество ресурсов.

??? Вопрос 28. Модель траектории ресурсов при уклонении от взаимоблокировок

Основные алгоритмы,  позволяющие предотвращать взаимоблокировки,  базируются на концепции безопасных состояний.  Перед тем как начать описывать алгоритм, сделаем небольшое отступление, чтобы взглянуть на идею безопасности с точки зрения простого для понимания графического метода. Несмотря на то, что графический подход не переносится напрямую в пригодный к употреблению алгоритм, он дает прекрасное интуитивное понимание существа вопроса.

На рис. 5  представлена модель для системы  с двумя процессами и двумя  ресурсами,  например принтером и плоттером.  Горизонтальная ось отображает номера команд,  выполняемых процессом А.  По вертикальной оси показаны номера команд,  выполняемых процессом В. В команде I₁ процесс А запрашивает принтер, в команде I₂ ему требуется плоттер.  Принтер и плоттер освобождаются командами I₃ и I₄ соответственно. Процессу В необходим плоттер с команды I₅ по команду I₇ и принтер с команды I₆ по команду I₈ .  Каждая точка на диаграмме представляет совместное состояние двух процессов.  Изначально система находится в точке p , когда ни один процесс еще не выполнил ни одну инструкцию. Если планировщик запустит процесс А первым, мы попадем в точку q , в которой процесс А выполнил какое-то количество команд, а процесс В еще ничего не сделал.  В точке q траектория становится вертикальной,  показывая,  что планировщик решил запустить в работу процесс В. При наличии одного процессора все отрезки траектории могут быть только вертикальными или горизонтальными,  но не наклонными.  Кроме того,  движение всегда происходит на север или восток  (вверх и вправо), и никогда на юг или запад (вниз и влево), так как процессы не могут работать в обратном направлении.  Когда процесс А пересекает линию I₁ на отрезке от точки r до точки s ,  он запрашивает и получает принтер. Когда процесс В достигает точки t, он запрашивает плоттер.

Особенно интересны  заштрихованные области.  Область  со штриховкой из верхнего левого угла в правый нижний представляет промежуток времени,  когда оба процесса занимают принтер.  Правило взаимного исключения делает попадание в эту область невозможным.  Вторая заштрихованная область соответствует тому,  что оба процесса используют плоттер, и это также невозможно.  Если система войдет в прямоугольник, ограниченный линиями I₁ и I₂ по сторонам и линиями I₅ и I₆ сверху и снизу, она в конце концов доберется до пересечения линий I₂ и I₆ ,  попадет в тупик.  В этот момент процесс А запросит плоттер,  а процесс В потребует принтер,  но оба ресурса будут к тому времени заняты.  Получается,  что небезопасным является целый прямоугольник,  и в него нельзя входить.  В точке t единственно безопасный вариант состоит в том, чтобы оставить процесс А работать до тех пир,  пока он не достигнет команды I₄ .  После нее любая траектория дойдет до точки u .

Важный для понимания момент заключается в том,  что в точке t процесс В запрашивает ресурс.  Система должна принять решение:  предоставлять его или нет.  Если выдается разрешение,  система попадает в небезопасную область и в итоге блокируется. Чтобы избежать тупика, нужно приостановить процесс В до тех пор, пока процесс А не запросит и не освободит плоттер.

??? Вопрос 29. Безопасное и небезопасное состояние при уклонении от взаимоблокировок

Алгоритмы предотвращения взаимоблокировок,  которые мы будем  изучать дальше,  используют информацию рис. 4.  В любой момент времени существует текущее состояние, составленное из величин Е, А, С и R. Говорят, что состояние безопасно, если оно не находится в тупике и существует некоторый порядок планирования,  при котором каждый процесс может работать до завершения, даже если все процессы вдруг захотят немедленно получить свое максимальное количество ресурсов.  Проще всего проиллюстрировать эту идею на примере с одним ресурсом.  На рис. 6,  а у нас есть состояние, в котором процесс А занимает 3 экземпляра ресурса, но ему в итоге могут потребоваться 9 экземпляров. Процесс В в настоящий момент занял 2 экземпляра, но позже ему могут понадобиться всего 4. Процесс С владеет двумя, но может потребовать еще 5  штук.  В системе есть всего 10  экземпляров данного ресурса, 7  из них уже распределены, три пока свободны.

Состояние на рис. 6(а)  безопасно,  потому что существует такая последовательность предоставления ресурсов,  которая позволяет  завершиться всем процессам. А именно,  планировщик может просто запустить в работу только процесс В на то время, пока он запросит и получит два дополнительных экземпляра ресурса,  что приведет к состоянию,  изображенному на рис. 6(б).  Когда процесс В закончится,  мы получим состояние рис. 7(в). Затем планировщик может запустить процесс С, что со временем приведет нас к ситуации рис. 6(г).  По завершении процесса С,  получим рис. 6(д)  Теперь процесс А наконец может занять необходимые ему шесть экземпляров ресурса и также успешно завершиться.  Таким образом,  состояние на рис. 6(а)  является безопасным,  потому что система может избежать тупика с помощью аккуратного планирования процессов.  Разница между безопасным и небезопасным состоянием заключается в следующем: в безопасном состоянии система может гарантировать, что все процессы закончат свою работу, а в небезопасном состоянии такой гарантии дать нельзя.

??? Вопрос 30. Алгоритм банкира для одного типа ресурса

Алгоритм планирования, позволяющий избегать взаимоблокировок, был разработан Дейкстрой (Dijkstra) и носит название алгоритма банкира. Он представляет собой расширение алгоритма обнаружения тупиков, о котором было рассказано ранее. Модель алгоритма основана на примере банкира в маленьком городке, имеющего дело с группой клиентов, которым он выдал ряд кредитов. Алгоритм проверяет, ведет ли выполнение каждого запроса к небезопасному состоянию. Если да, то запрос отклоняется. Если удовлетворение запроса к ресурсу приводит к безопасному состоянию, ресурс предоставляется процессу. На рис. 7(а) видим четырех клиентов: А, В, С и D, каждый из которых получил определенное количество единиц кредита (например, 1 единица равна 1 К долларов). Банкир знает, что не всем клиентам понадобится их максимальный кредит немедленно, поэтому он зарезервировал только 10 единиц, а не все 22, которые требуются клиентам. (Чтобы провести аналогию с компьютерной системой, считаем, что клиенты — процессы, единицами, скажем, являются накопители на магнитной ленте, а банкир — ОС.)

Клиенты вращаются  в соответствующем бизнесе, время  от времени прося у банка ссуды (то есть запрашивая ресурсы). В некоторый момент возникает ситуация, показанная на рис. 7(б). Это состояние безопасно, потому что остались две единицы и банкир может задержать все обращения, кроме запросов клиента или процесса С, таким образом, позволяя процессу С завершиться и вернуть все четыре отданных ему ресурса. Имея на

руках четыре единицы, банкир может отдать их или клиенту D, или В, обеспечивая их необходимыми единицами и т. Д. Рассмотрим, что  могло бы произойти, если бы в ситуации на рис. 7(б) был бы

удовлетворен  запрос еще одной единицы для  клиента В. Мы попали бы в состояние  рис. 7(в), не являющееся безопасным. Если бы все клиенты вдруг запросили  максимальные ссуды, то банкир не смог бы их обеспечить и мы попали бы в тупик. Небезопасное состояние не обязано приводить к взаимоблокировке, так как клиентам

не обязательно  потребуется весь доступный кредит, но банкир не может рассчитывать на такую ситуацию. Алгоритм банкира  рассматривает каждый запрос по мере поступления и проверяет, приведет ли его удовлетворение к безопасному состоянию. Если да, то процесс получает ресурс, иначе запрос откладывается на более позднее время. Чтобы понять, является ли состояние безопасным, банкир проверяет, может ли он предоставить достаточно ресурсов для завершения работы какого-либо клиента. Если да, то эти ссуды считаются погашенными, после чего проверяется следующий ближайший к пределу займа клиент и т. Д. Если, в конце концов, все ссуды могут быть погашены, состояние является безопасным и исходный запрос можно удовлетворить.