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

3.5 Предотвращение тупиковых ситуаций

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

3.5.1 Линейное упорядочение ресурсов

Пусть все ресурсы полностью упорядочены от 1 до r. Мы можем наложить следующее ограничение: процесс не может запрашивать ресурс Rk, если он удерживает ресурс Rh и при этом k < h.

Просто видеть, что, используя это правило, мы никогда не будем входить в тупики. (Для доказательства применим метод доказательства от противного).

Приведем пример того, как применяется это правило. Пусть есть процесс, который использует ресурсы, упорядоченные как A, B, C, D, E, следующим способом:

Тогда процесс может делать следующее:

захватить (A); захватить (B); захватить (C);

использовать C;

использовать A, C;

использовать A, B, C;

освободить (A); освободить (B); захватить (E);

использовать C и E;

освободить (C); освободить (E); захватить (D);

использовать D;

освободить (D);

Стратегия этого типа может использоваться, когда мы имеем несколько ресурсов. Эту стратегию просто применять, при этом степень параллелизма уменьшается не слишком сильно.

3.5.2 Иерархическое упорядочение ресурсов

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

Тогда если процесс хочет использовать ресурсы 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 Защита информации

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

Поддержание логической целостности данных при конкурентном доступе к ним должно осуществляться как на уровне ОС, так и на уровне прикладных программ. В самой ОС существует множество структур данных требующих такой защиты. Метод решения – это, в первую очередь, корректная разработка как системного, так и прикладного ПО. Наиболее простым и универсальным является использование блокировок с помощью семафоров (см. “Семафоры”). Для упрощения разработки прикладного ПО целесообразно вынести заботу о целостности данных на системное программное обеспечение, так, например большие массивы однородных данных имеет смысл хранить с использованием реляционных систем управления базами данных (РСУБД, RDBMS), при разработке которых уже учтены возможные проблемы поддержания логической целостности данных.