Страница: 16/18
Другая стратегия, которую мы можем использовать в случае, если ресурсы иерархически структурированы, должна блокировать их в иерархическом порядке. Пусть удерживание ресурсов представлено организованным в дерево. Мы можем блокировать любой узел или группу узлов в дереве. Ресурсы, в которых мы заинтересованы - узлы в дереве, обычно самого нижнего уровня в древовидном представлении иерархии. Тогда следующее правило гарантирует предотвращение тупиков: узлы, в настоящее время блокированные процессом, должны найтись на всех путях от корня до желательных ресурсов. Пример использования этого правила, с блокировкой одиночного ресурса одновременно:
|
|
Тогда если процесс хочет использовать ресурсы e, f, i, k он должен использовать команды в следующей последовательности:
блокировка (a);
блокировка (b);
блокировка (h);
освобождение (a);
блокировка (d);
освобождение (b);
блокировка (i);
блокировка (j);
освобождение (h);
блокировка (k);
освобождение (j);
блокировка (e);
блокировка (f);
освобождение (d);
3.5.3 Алгоритм банкира
Одна из причин, по которой этот алгоритм не используется в реальном мире широко – чтобы использовать его, операционная система должна знать максимальное количество ресурсов, в которых каждый процесс будет нуждаться когда-либо. Следовательно, например, запущенная на выполнение программа должна объявить, что она будет нуждаться не более чем, скажем, 400КБ памяти. Операционная система сохранит ограничение 400КБ и будет использовать его в вычислениях с целью предотвращения тупика.
Алгоритм Банкира пытается предотвращать тупик, путем предоставления или отказа предоставления ресурсов системы. Каждый раз, когда процесс нуждается в каком либо неразделяемом ресурсе, этот запрос должен быть одобрен банкиром.
Банкир - консервативен. Каждый раз, когда процесс делает запрос ресурса (“просит ссуду”), банкир осторожно рассматривает “банковские книги” и пытается определять, может или нет состояние тупика возникнуть в будущем, если запрос ссуды будет одобрен.
Алгоритм симулирует предоставление запрошенного ресурса и затем просматривает возникающее в результате выполнения запроса состояние системы.
После предоставления ресурса в системе останется некоторое количество этого ресурса свободным. Далее, проверяем другие процессы в системе. Мы требовали, чтобы каждый из них установил максимальное количество всех ресурсов системы, в которых они будут нуждаться, чтобы завершить выполнение, следовательно, мы знаем, сколько каждого ресурса каждый процесс удерживает и требует.
Если банкир имеет достаточно свободного ресурса чтобы гарантировать, что хотя бы один процесс может завершиться, тогда он может брать ресурс, удерживаемый этим процессом, и добавляет это к свободному объему ресурса. В этот момент банкир может рассматривать теперь больший свободный объем и делать попытку проверки, что другой процесс может завершиться, если требование будет выполнено. Если банкир может гарантировать, что все процессы в системе завершатся, то он одобряет рассматриваемый запрос.
Если, с другой стороны, в данный момент банкир не может гарантировать, что любые процессы завершатся, потому что недостаточно свободного ресурса удовлетворить самое малое требование, то может наступить состояние тупика. Это называется небезопасным состоянием. В этом случае рассматриваемый запрос будет отклонен и запрашивающий процесс обычно блокируется.
Эффективность алгоритма Банкира зависит значительно от его реализации. Например, если “банковские книги” сохраняются сортированными по размерам требований процессов, то добавление новой информации о процессах к таблице или уменьшение таблицы упрощено. Однако если таблица сохраняется в неупорядоченном виде, то добавление новой записи приводит к снижению эффективности таблицы.
3.6 Защита информации
Защита информации подразделяется на несколько практически независимых направлений, два из которых представляются наиболее значимыми: поддержание целостности данных при многозадачной и многопроцессорной обработке, а также защита от несанкционированного доступа к данным. Без реализации защиты по этим двум направлениям круг задач, эффективно решаемых в данной вычислительной системе, резко сужается. Другие источники угрозы для обрабатываемых данных либо значительно менее существенны, либо имеют очень специфические методы решения, непригодные в общем случае, как, скажем, защита от ошибочных действий законного, но неквалифицированного пользователя.
Реферат опубликован: 6/09/2006