Организация МОС МПВС по принципу симметричной обработки (стр. 3 )

семафоры процессу В открыты. Во время его работы с буфером S¢3 =0, его признак «закрыто», и, следовательно, доступ другим процессам закрыт, пока В не выполнит заключительную операцию V(S3) и не восстановит единичное значение семафора S3. Кроме этого заключительной операцией V(S1)= S1+1 отмечается, что в буфере освободилось ещё одно место для приема сообщений. В граничных ситуациях дополнительно вводится операция восстановления действительных значений семафоров.

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

Если буфер пустой, то S2=0, и процесс-читатель В блокируется по операции , для того, чтобы он не тратил машинное время на бесполезные попытки чтения пустого буфера и освободил процессор до разблокирования процессором-писателем А по его заключительной операции с последующим восстановлением действительного числа накопленных сообщений.

3.3.4. Тупики в распределении ресурсов между параллельными процессами.

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

Непрекращающееся взаимное разблокирование двумя и более заблокированными параллельными вычислительными процессами называется тупиком (клинчем – мертвыми объятиями).

Так как выход из тупика связан с большими затратами (в ВС общего назначения – машинного времени, а в специализированных ВС систем автоматизации – восстановления управляемых объектов после возможных аварий), для уменьшения вероятности его возникновения при проектировании МОС проводят тщательное моделирование взаимодействия параллельных процессов во всевозможных режимах функционирования ВС, используя аппарат сетей Петри и его модификации (например Е-сети).

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

Например, в системе из двух процессов Р1 и Р2 может возникнуть тупик из-за взаимного обращения в области данных Д1 и Д2 друг друга, где t1, t2, t3, t4 – моменты времени начала работы процессов с областями данных, причем t3, t4> t1, t2.

 

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

Известны 3 способа предотвращения и разрешения тупиковой ситуации:

1)  Статическое предотвращение;

2)  Динамическое предотвращение;

3)  Распознавание и анулирование тупиков.

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

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

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

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

Распознавание и анулирование тупиков – сложная, до конца не решенная проблема. Известно следующее её решение для МПВС и транспьютерных сетей. Для распознавания используется принцип образования в процессорах ошибки типа «Подвеска процесса у соседнего процессора». При возникновении тупика в ограниченной локальной совокупности процессоров, а не во всей системе, процессы в них приостанавливаются, и они укажут на превышение допустимых тайм-аутов друг у друга, а другие процессоры, соседствующие с контуром этой тупиковой области процессоров, могут отметить границы этой тупиковой области.

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

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

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

3.3.5. Системы и языки параллельного программирования.

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

ОВС-Фортран – для однородных вычислительных структур;

Параллельные Паскаль, С(СИ), АДА;

ОССАМ (Оккам) – для специализированных транспьютерных сетей.

Система параллельного программирования включает в себя:

1)  Языки параллельного программирования для написания подпрограмм параллельных фрагментов, задания операторов взаимодействия между ними и организации отказоустойчивых вычислений;

2)  Интерактивные трансляторы с автоматизированным распараллеливанием последовательных алгоритмов;

3)  Средства отладки параллельных программ: экранный редактор, синтаксический анализатор, средства структурного редактирования;

4)  Программы для оценки эффективности распараллеливания, ожидаемой производительности по сравнению с однопроцессорной ЭВМ и требуемой памяти.

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