Программа реализации алгоритма работы с виртуальной памятью

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

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

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

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

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

Hарушение условия кругового ожидания. Трудно предложить разумную стратегию, чтобы избежать последнего условия из раздела «Условия возникновения тупиков» – циклического ожидания.

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

Один из немногих примеров упорядочивания ресурсов – создание иерархии спин-блокировок в Windows 2000. Спин-блокировка – простейший способ синхронизации (вопросы синхронизации процессов рассмотрены в соответствующей лекции). Спин-блокировка может быть захвачена и освобождена процессом. Классическая тупиковая ситуация возникает, когда процесс P1 захватывает спин-блокировку S1 и претендует на спин-блокировку S2, а процесс P2, захватывает спин-блокировку S2 и хочет дополнительно захватить спин-блокировку S1. Чтобы этого избежать, все спин-блокировки помещаются в упорядоченный список. Захват может осуществляться только в порядке, указанном в списке.

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

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

Сложность восстановления обусловлена рядом факторов.

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

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

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

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

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

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

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

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

Задание

(выполняются с использованием справочных изданий)

Создать модель, реализующую задачу об обедающих философах. Задача была предложена Дейкстрой и связана с пятью мудрецами, которые попеременно то думали, то ели. Мудрецы сидят за круглым большим столом, на котором много блюд китайской кухни. Между соседями лежит одна палочка для еды. Однако для приема китайской пищи необходимо две палочки, следовательно, каждый мудрец должен взять палочку слева и палочку справа: проблема заключается в том, что если все мудрецы возьмут палочки слева, и затем будут ждать, когда освободятся палочки с правой стороны, то они будут ждать вечно и умрут от голода (состояние тупика).

На рис.8.1. показано решение этой задачи с помощью сетей Петри. Позиции С1, … С5 представляют палочки для еды, и так как каждая из них первоначально свободна, то в начальной маркировке в каждой из этих позиций имеется фишка. Каждый мудрец представлен двумя позициями М_i и Е_i для состояний размышления и принятия пищи соответственно. Для того, чтобы мудрец перешел из состояния размышления в состояние принятия пищи, обе палочки (слева и справа) должны быть свободны.

При выполнении задания рекомендуется придерживаться следующей методики.

1. Используйте Вашу среду исследования функционирования операционной системы.

2. Для моделирования используйте 5 процессов.

3. Создайте легенду с использованием цветовой гаммы для состояний процессов.

4. Запустите процессы в соответствии с рис.8.1.

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

6. Смоделируйте ситуацию тупика.

7. Структура строки файла LOG.TXT должна быть следующей:

- время;

- наименование процесса (номер мудреца);

- состояние процесса (размышление, принятие пищи).

Рис.8.1. Задача об обедающих мудрецах.

Контрольные вопросы

1. Понятие тупиков, примеры.

2. Условия возникновения тупиков.

3. Предотвращение тупиков.

4. Способы борьбы с тупиками.

5. Алгоритм банкира.

Р а з д е л IX

Цель работы: Освоить алгоритмы и механизмы работы с виртуальной памятью.

Дата добавления: 2014-12-07