Многопроцессорный вычислительный комплекс на основе коммутационной матрицы с симметричной обработкой заданий всеми процессорами

если (semaphore.value >= 0)

{

Vprim(semaphore.lock); вернуть (0);

}

/* следует перейти в состояние приостанова */

если (проверяются сигналы)

{

если (имеется сигнал, прерывающий нахождение в состоянии приостанова)

увеличить (semaphore.value);

если (сигнал принят в режиме ядра)

{

Vprim(semaphore.lock);

вернуть (-1);

}

в противном случае

{

Vprim(semaphore.lock);

longjmp;

}

}

}

поставить процесс в конец списка приостановленных по семафору;

Vprim(semaphore.lock);

выполнить переключение контекста;

проверить сигналы (см. выше);

вернуть (0);

}

В начале выполнения алгоритма операции P ядро с помощью функции Pprim

предоставляет процессу право исключительного доступа к семафору и уменьшает

значение семафора. Если семафор имеет неотрицательное значение, текущий

процесс получает доступ к критическому участку. По завершении работы

процесс сбрасывает блокировку семафора (с помощью функции Vprim), открывая

доступ к семафору для других процессов, и возвращает признак успешного

завершения. Если же в результате уменьшения значение семафора становится

отрицательным, ядро приостанавливает выполнение процесса, используя

алгоритм, подобный алгоритму sleep: основываясь на значении приоритета,

ядро проверяет поступившие сигналы, включает текущий процесс в список

приостановленных процессов, в котором последние представлены в порядке

поступления, и выполняет переключение контекста.

Алгоритм V

/*

Операция над семафором типа V

входная информация: адрес семафора

выходная информация: отсутствует

*/

{

Pprim(semaphore.lock);

увеличить (semaphore.value);

если (semaphore.value <= 0)

{

удалить из списка процессов, приостановленных по семафору, первый по счету

процесс;

перевести его в состояние готовности к запуску;

}

Vprim(semaphore.lock);

}

Операция V получает исключительный доступ к семафору через функцию Pprim и

увеличивает значение семафора. Если очередь приостановленных по семафору

процессов непустая, ядро выбирает из нее первый процесс и переводит его в

состояние "готовности к запуску". Операции P и V по своему действию похожи

на функции sleep и wakeup. Главное различие между ними состоит в том, что

семафор является структурой данных, тогда как используемый функциями sleep

и wakeup адрес представляет собой всего лишь число. Если начальное значение

семафора - нулевое, при выполнении операции P над семафором процесс всегда

приостанавливается, поэтому операция P может заменять функцию sleep.

Операция V, тем не менее, выводит из состояния приостанова только один

процесс, тогда как однопроцессорная функция wakeup возобновляет все

процессы, приостановленные по адресу, связанному с событием. С точки зрения

семантики использование функции wakeup означает: данное системное условие

более не удовлетворяется, следовательно, все приостановленные по условию

процессы должны выйти из состояния приостанова. Так, например, процессы,

приостановленные в связи с занятостью буфера, не должны дальше пребывать в

этом состоянии, если буфер больше не используется, поэтому они

возобновляются ядром. Еще один пример: если несколько процессов выводят

данные на терминал с помощью функции write, терминальный драйвер может

перевести их в состояние приостанова в связи с невозможностью обработки

больших объемов информации. Позже, когда драйвер будет готов к приему

следующей порции данных, он возобновит все приостановленные им процессы.

Использование операций P и V в тех случаях, когда устанавливающие

блокировку процессы получают доступ к ресурсу поочередно, а все остальные

процессы - в порядке поступления запросов, является более предпочтительным.

В сравнении с однопроцессорной процедурой блокирования (sleep-lock) данная

схема обычно выигрывает, так как если при наступлении события все процессы

возобновляются, большинство из них может вновь наткнуться на блокировку и

снова перейти в состояние приостанова. С другой стороны, в тех случаях,

когда требуется вывести из состояния приостанова все процессы одновременно,

использование операций P и V представляет известную сложность. Если

операция возвращает значение семафора, является ли она эквивалентной

функции wakeup?

while (value(semaphore) < 0)

{

V(semaphore);

};

Если вмешательства со стороны других процессов нет, ядро повторяет цикл до

тех пор, пока значение семафора не станет больше или равно 0, ибо это

означает, что в состоянии приостанова по семафору нет больше ни одного

процесса. Тем не менее, нельзя исключить и такую возможность, что сразу

после того, как процесс A при тестировании семафора на одноименном

процессоре обнаружил нулевое значение семафора, процесс B на своем

процессоре выполняет операцию P, уменьшая значение семафора до –1.

Процесс A продолжит свое выполнение, думая, что им возобновлены все

приостановленные по семафору процессы. Таким образом, цикл выполнения

операции не дает гарантии возобновления всех приостановленных процессов,

поскольку он не является элементарным. Рассмотрим еще один феномен,

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

Предположим, что два процесса, A и B, конкурируют за семафор. Процесс A

обнаруживает, что семафор свободен и что процесс B приостановлен; значение

семафора равно -1. Когда с помощью операции V процесс A освобождает

семафор, он выводит тем самым процесс B из состояния приостанова и вновь

делает значение семафора нулевым. Теперь предположим, что процесс A, по-

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

Производя операцию P, процесс приостановится, поскольку семафор имеет

нулевое значение, несмотря на то, что ресурс пока свободен. Системе

придется "раскошелиться" на дополнительное переключение контекста. С другой

стороны, если бы блокировка была реализована на основе однопроцессорной

схемы (sleep-lock), процесс A получил бы право на повторное использование

ресурса, поскольку за это время ни один из процессов не смог бы

заблокировать его. Для этого случая схема sleep-lock более подходит, чем

схема с использованием семафоров. Когда блокируются сразу несколько

семафоров, очередность блокирования должна исключать возникновение

тупиковых ситуаций. В качестве примера рассмотрим два семафора, A и B, и

два алгоритма, требующих одновременной блокировки семафоров. Если бы

алгоритмы устанавливали блокировку на семафоры в обратном порядке, как

следует из рисунка,

последовало бы возникновение тупиковой ситуации; процесс A на одноименном

процессоре захватывает семафор SA, в то время как процесс B на своем

процессоре захватывает семафор SB. Процесс A пытается захватить и семафор

SB, но в результате операции P переходит в состояние приостанова, поскольку

значение семафора SB не превышает 0. То же самое происходит с процессом B,

когда последний пытается захватить семафор SA. Ни тот, ни другой процессы

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

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

взаимной блокировки, устанавливающие наличие опасной ситуации и

ликвидирующие ее. Тем не менее, использование таких алгоритмов "утяжеляет"

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

захватывать несколько семафоров, довольно ограничено, легче было бы

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

до того, как они будут иметь место. Если, к примеру, какой-то набор

семафоров всегда блокируется в одном и том же порядке, тупиковая ситуация

никогда не возникнет. Но в том случае, когда захвата семафоров в обратном

порядке избежать не удается, операция CP предотвратит возникновение

тупиковой ситуации:

если операция завершится неудачно, процесс B освободит свои ресурсы, дабы

избежать взаимной блокировки, и позже запустит алгоритм на выполнение

повторно, скорее всего, тогда, когда процесс A завершит работу с ресурсом.

Чтобы предупредить одновременное обращение процессов к ресурсу, программа

обработки прерываний, казалось бы, могла воспользоваться семафором, но из-

за того, что она не может приостанавливать свою работу (см. главу 6),

использовать операцию P в этой программе нельзя. Вместо этого можно

использовать "циклическую блокировку" (spin lock) и не переходить в

состояние приостанова, как в следующем примере:

while (! CP(semaphore));

Операция повторяется в цикле до тех пор, пока значение семафора не превысит

0; программа обработки прерываний не приостанавливается и цикл завершается

только тогда, когда значение семафора станет положительным, после чего это

значение будет уменьшено операцией CP. Чтобы предотвратить ситуацию

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

"циклическую блокировку". Иначе выполнение процесса, захватившего семафор,

будет прервано еще до того, как он сможет освободить семафор; если

программа обработки прерываний попытается захватить этот семафор, используя

"циклическую блокировку", ядро заблокирует само себя. В качестве примера

обратимся к рисунку:

В момент возникновения прерывания значение семафора не превышает 0, поэтому

результатом выполнения операции CP всегда будет "ложь". Проблема решается

путем запрещения всех прерываний на то время, пока семафор захвачен

процессом.

3.4 Тупиковые ситуации

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

мультипрограммирования, для выполнения их работы нужно два ресурса,

например, принтер и диск. На рисунке показаны фрагменты соответствующих

программ.

Пусть после того, как процесс А занял принтер (установил блокирующую

переменную), он был прерван. Управление получил процесс В, который сначала

занял диск, но при выполнении следующей команды был заблокирован, так как

принтер оказался уже занятым процессом А. Управление снова получил процесс

А, который в соответствии со своей программой сделал попытку занять диск и

был заблокирован: диск уже распределен процессу В. В таком положении

процессы А и В могут находиться сколь угодно долго.

В зависимости от соотношения скоростей процессов, они могут либо совершенно

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

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

Тупиковые ситуации надо отличать от простых очередей, хотя и те и другие

возникают при совместном использовании ресурсов и внешне выглядят похоже:

процесс приостанавливается и ждет освобождения ресурса. Однако очередь -

это нормальное явление, неотъемлемый признак высокого коэффициента

использования ресурсов при случайном поступлении запросов. Она возникает

тогда, когда ресурс недоступен в данный момент, но через некоторое время он

освобождается, и процесс продолжает свое выполнение. Тупик же, что видно из

его названия, является в некотором роде неразрешимой ситуацией.

В рассмотренных примерах тупик был образован двумя процессами, но взаимно

блокировать друг друга могут и большее число процессов.

Проблема тупиков включает в себя следующие задачи:

предотвращение тупиков,

распознавание тупиков,

восстановление системы после тупиков.

Тупики могут быть предотвращены на стадии написания программ, то есть

программы должны быть написаны таким образом, чтобы тупик не мог возникнуть

ни при каком соотношении взаимных скоростей процессов. Так, если бы в

предыдущем примере процесс А и процесс В запрашивали ресурсы в одинаковой

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

предотвращению тупиков называется динамическим и заключается в

использовании определенных правил при назначении ресурсов процессам,

например, ресурсы могут выделяться в определенной последовательности, общей

для всех процессов.

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

процессами, использующими много ресурсов, распознавание тупика является

нетривиальной задачей. Существуют формальные, программно - реализованные

методы распознавания тупиков, основанные на ведении таблиц распределения

ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет

обнаружить взаимные блокировки.

Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения

все заблокированные процессы. Можно снять только часть из них, при этом

освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть

некоторые процессы в область свопинга, можно совершить "откат" некоторых

процессов до так называемой контрольной точки, в которой запоминается вся

информация, необходимая для восстановления выполнения программы с данного

места. Контрольные точки расставляются в программе в местах, после которых

возможно возникновение тупика. Из всего вышесказанного ясно, что

использовать семафоры нужно очень осторожно, так как одна незначительная

ошибка может привести к останову системы. Для того чтобы облегчить

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

синхронизации, называемое монитором. Монитор - это набор процедур,

переменных и структур данных. Процессы могут вызывать процедуры монитора,

но не имеют доступа к внутренним данным монитора. Мониторы имеют важное

свойство, которое делает их полезными для достижения взаимного исключения:

только один процесс может быть активным по отношению к монитору. Компилятор

обрабатывает вызовы процедур монитора особым образом. Обычно, когда процесс

вызывает процедуру монитора, то первые несколько инструкций этой процедуры

проверяют, не активен ли какой-либо другой процесс по отношению к этому

монитору. Если да, то вызывающий процесс приостанавливается, пока другой

процесс не освободит монитор. Таким образом, исключение входа нескольких

процессов в монитор реализуется не программистом, а компилятором, что

делает ошибки менее вероятными.

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

которых имеет собственную оперативную память, семафоры и мониторы

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

реализована только с помощью обмена сообщениями.

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), при разработке

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

данных.

Стоит отметить, что данный аспект защиты данных, безусловно, имеет решения,

однако осознание их необходимости в каждом конкретном случае и корректная

реализация требуют достаточной квалификации разработчика, а также

некоторого дополнительного расхода системных ресурсов.

Защита от несанкционированного доступа к данным в общем случае представляет

собой более сложную задачу, решение которой может привести к противоречию с

основными функциями вычислительной системы. Можно сказать, что удобство

пользования вычислительной системой обратно пропорционально степени ее

защищенности от несанкционированного доступа.

Основная модель защиты от несанкционированного доступа в настоящее время

это доступ на основе определения прав групп и отдельных пользователей на

использование ресурсов, каждый из которых имеет список управления доступом,

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

умолчанию доступ запрещен, при конфликте записей в списке выбирается

наиболее ограничивающий вид доступа.

Наиболее важные требования к подсистеме безопасности таковы:

Владелец ресурса должен иметь возможность управлять доступом к ресурсу.

ОС должна защищать объекты от несанкционированного использования другими

процессами. Например, система должна защищать память так, чтобы ее

содержимое не могло читаться после освобождения процессом, и после удаления

файла не допускать обращения к данным файла.

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

идентифицировать себя, вводя уникальное имя входа в систему и пароль.

Система должна быть способна использовать эту уникальную идентификацию для

контроля действий пользователя.

Администратор системы должен иметь возможность контроля связанных с

безопасностью событий. Доступ к этим контрольным данным должен быть

ограничен администратором.

Система должна защищать себя от внешнего вмешательства типа модификации

выполняющейся системы или хранимых на диске системных файлов.

Прежде чем пользователь сможет сделать что-либо в системе, он должен

произвести вход в систему с указанием имени и пароля. В случае успешного

входа в систему создается уникальный маркер доступа данного пользователя,

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

доступа к ресурсам. Данный маркер доступа копируется для всех порожденных

пользователем процессов в системе, таким образом, любой процесс имеет

полномочия, определенные ранее для владельца процесса.

Такое построение подсистемы безопасности в ОС позволяет выполнить все

вышеперечисленные требования, однако существует возможность

непосредственного доступа к данным путем электрического подключения к

системе (например, к линии связи удаленного терминала) или приема

электромагнитных излучений ЭВМ. Решение по предотвращению таких

возможностей должно приниматься в каждом конкретном случае, однако наиболее

общие методы это экранирование ЭВМ и линий связи, их физическая защита, а

также шифрование информации при ее передаче и хранении (а возможно и при ее

обработке).

4 Литература

“Вычислительные комплексы, системы и сети”

А. М. Ларионов, С. А. Майоров, Г. И. Новиков

Ленинград, ЭНЕРГОАТОМИЗДАТ, 1987

(к разделу “Структурная схема МПВК”)

“The design of the UNIX operating system”

Maurice J. Bach

Prentice-Hall, 1986, ISBN 0-13-201757-1 025

(к разделу “Семафоры”)

“Сетевые операционные системы”

Н. А. Олифер, В. Г. Олифер,

Информационно-аналитические материалы Центра Информационных Технологий

(к разделу “Тупики”)

Курс лекций “Introduction to Distributed Systems and Networks” (CIS 307)

Giorgio Ingargiola, Associate Professor of Computer and Information Science

Department.

Университет г. Темпль (шт. Филадельфия, США)

(к разделу “Предотвращение тупиков”)

“Операционная система UNIX”

С. Д. Кузнецов

Информационно-аналитические материалы Центра Информационных Технологий

(к разделу “Нити”)

“Сетевые ОС для SMP-платформ”

Е. Ленгрен

“Открытые Системы” № 2(10)/95 стр. 16

(к разделу “Симметричная многопроцессорная обработка”)

“Спецификация многопроцессорных систем компании Intel”

А.А. Мячев

“Открытые Системы” № 3(11)/95 стр. 56

(к разделу “Симметричная многопроцессорная обработка”)

“Ресурсы Windows NT Server и Workstation версия 3.5”

Microsoft Press, 1995

(к разделу “Защита информации”)

-----------------------

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

Страницы: 1, 2, 3, 4