Многопоточное программирование (стр. 2 )

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

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

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

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

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

При построении Grid-систем особую актуальность обретают проблемы защиты. Цель защиты — перекрыть доступ к ресурсам и информации для тех пользователей, которые не имеют соответствующих привилегий. Таким пользователем может стать и собственник, предоставивший свой компьютер в аренду или по договору на время простоя.

Базовыми элементами защиты являются:

•аутентификация — проверка подлинности участника взаимодействия с системой;

•механизм авторизации — проверка допустимости затребованной операции;

•конфиденциальность и целостность данных — защита от нелегитимного доступа;

•биллинг и аудит — способность контролировать и подсчитывать объем использованных ресурсов и обеспечиваемых ими служб;

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

Классификация Фенга (1972)

Две характеристики

·  n – количество бит в машинном слове, обрабатываемых параллельно (обычно совпадает с длиной машинного слова)

·  m – количество слов, обрабатываемых одновременно вычислительной системой (ширина битового слоя)

Максимальная степень параллелизма (пиковая производительность)

P = n x m

Преимущество: введение единой числовой метрики.

Недостатки:

·  Нет различия между процессорными матрицами, векторно-конвейерными и многопроцессорными системами

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

Классы систем по Фенгу:

·  Разрядно-последовательные, пословно-последовательные (n = m = 1)

·  Разрядно-параллельные, пословно-последовательные (n > 1, m = 1)

·  Разрядно-последовательные, пословно-параллельные (n = 1, m > 1)

·  Разрядно-параллельные, пословно-параллельные (n > 1, m > 1)

Классификация Хендлера

Данная классификация была введена для устранения недостаток предыдущих рассмотренных классификаций. Рассмотрим её основные особенности.

В данной классификации для параллельных системы вводится функция вида:

T(C) = (k x k’, d x d’, w x w’),

где

k – Число процессоров, работающих параллельно

k' – Глубина макроконвейера из отдельных процессоров

d – Число АЛУ в каждом процессоре, работающих параллельно

d' – Глубина конвейера из функциональных устройств АЛУ

w – Число разрядов в слове, обрабатываемых АЛУ одновременно

w' – Число ступеней в конвейере функциональных устройств АЛУ

x – отражает конвейерный принцип обработки (прохождение данных сначала через одну подсистему, затем через другую)

+ – отражает возможность независимого использования процессоров разными задачами

v – операция альтернативы, показывающая возможные альтернативные режимы работы системы

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

2.6  Производительность параллельных компьютеров

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

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

Иное название данного вида оценки производительности – теоретическая производительность. Данная метрика определяется как число команд, выполняемых компьютером в единицу времени.

Единица измерения пиковой производительности, определяемой таким образом: MIPS – Million Instructions per Second. Эта единица измерения получила широкое распространение.

Альтернативный способ определения производительности – вычисление максимального количества вещественных операций, выполняемых в единицу времени. В этом случае применяется другая известная единица измерения FLOP – Floating Point Operations per Second.

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

Для устранения недостатка пиковой производительности используются различные синтетические тесты, называемые бенчмарками. Приведём примеры наиболее известных бенчмарков, применяемых для оценки производительности параллельных вычислительных систем:

·  LINPACK – решение системы уравнений.

·  STREAM – четыре небольших цикла, работающих с очень длинными векторами.

Если несколько процессоров составляют ВС, то важной характеристикой ее эффективности эффективности (основные составляющие эффективности — производительность, надежность, стоимость) при специализированном использовании (например, в составе АСУ) является коэффициент загрузки процессоров kЗ. Для его определения находят коэффициенты загрузки процессоров

Если P0 — производительность одного процессора, то реальная производительность ВС, состоящей из n процессоров, при решении данной задачи (!) составляет

PBC = n kЗ P0.

P0 определяется классом решаемых задач.

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

Известны несколько подходов к формированию тестов, по которым определяется производительность P0 единичных ЭВМ или процессоров ВС.

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

Для вычислительных задач применялась (утвержденная ГОСТом) смесь "Гибсон-3". Она хорошо отражала архитектуру ЕС ЭВМ, воспроизводящей архитектуру IBM. Однако ранее говорилось о тенденции повышения уровня языка пользователя, об аппаратной поддержке ЯВУ. Смесь Гибсона, приведенная ниже, не отражает этих тенденций. Набор операций примитивен, соответствует ЭВМ ранних поколений. Интерпретация в ней "языковых" операций затруднительна и уменьшает точность оценки. Ее использование определялось требованиями советских ГОСТов.

Смесь "Гибсон-3" 1. Загрузка регистра без индексации 31 %

2. Загрузка регистра с индексацией 18 %

3. Проверка условия и переход 17 %

4. Сравнение 4 %

5. Сдвиг на 3 разряда 4 %

6. Логическая операция "И" 2 %

7. Команды с минимальным временем выполнения 5 %

8. Сложение с фиксированной запятой 6 %

9. Умножение с фиксированной запятой 0,6 %

10. Деление с фиксированной запятой 0,2 %

11. Сложение с плавающей запятой 7 %

12. Умножение с плавающей запятой 4 %

13. Деление с плавающей запятой 1,5 %

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

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

2.Ядра. Ядро — небольшая программа, часть решаемой задачи. Характеристики ядра могут быть точно измерены. Известны ядра Ауэрбаха: коррекция последовательного файла и файла на диске, сортировка, обращение матрицы и др.

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

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

5.У нас в стране в аналогичном применении больше известна модель вычислительной нагрузки.

Она применяется на уровне решения вопроса: какие вычислительные средства поставить в систему или заказать их разработку?

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

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

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

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

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

•сценарий параллельного ввода-вывода информации с учетом ее объема;

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

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

Однако все эти тесты не дают ответ на традиционный вопрос: какое количество операций в секунду выполняет ВС? Все усложняющаяся структура и расширяющееся множество "нетрадиционных" операций затрудняют ответ.

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

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

Пример — проблема оценки ЦП с многофункциональным АЛУ: как их загружать для реальной оценки (сколько их реально будут загружено в каждом такте), какой поток обмена с ОП предполагать и т. д.?

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

Одна и та же задача решается на известной ЭВМ, для которой (из-за ее более простой организации) известно значение производительности или быстродействия; например, ЕС 1066 имеет производительность 5,5 млн оп./с. Однопроцессорный МВК "Эльбрус-2" контрольную физическую задачу решает за 6,5 часа, ЕС 1066 — за 21 час. Значит, эквивалентная производительность "Эльбрус-2" в комплектации с единственным процессором составляет ∼ 5,5 × 21/6,5 = 17,6 млн оп./с (в сравнении с ЕС 1066). Аналогично проводилось сравнение с ЭВМ БЭСМ-6.

На этапе испытаний ВС при оценке производительности складывается больше определенности по будущему режиму ее эксплуатации. Есть возможность построения контрольной задачи (КЗ), (развивающей идеи бенчмарок), использующую всю ВС. КЗ строится на основе типовых задач аналогичных систем управления, использует развиваемый прототип системы, воссоздает реальный режим решения. Для КЗ оценивается количество так называемых алгоритмических операций (аналог того, что отражено в смеси Ветстоуна). Т. е. можно максимально приблизить вычислительную нагрузку ВС к реальной ожидаемой. Это — современный комплексный подход, когда КЗ, составленная для всей ВС как для единой установки, учитывает не только использование процессоров, но и затраты на организацию вычислительного процесса, издержки ОС, интенсивность параллельного обмена информацией, организацию помехозащищенного вычислительного процесса.

Относительно последнего следует подчеркнуть: строятся контрольные задачи, по которым производительность оценивается с учетом надежности.

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

В этом смысле под надежностью ВС будем понимать вероятность решения поставленной перед ней задачи.

Тогда надежность ВС в составе сложной системы управления определяется следующими факторами:

•вероятностью пребывания в исправном состоянии в момент начала цикла управления;

•вероятностью пребывания в исправном состоянии в течение всего цикла управления;

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

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

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

1.Одной из определяющих характеристик надежности является коэффициент готовности К Г

где Tвосст — среднее время восстановления (в т. ч. ремонта) после отказа. Т. е. к началу цикла управления с вероятностью КГ ВС приступит к решению своей задачи.

2.Если ВС приступила к решению задачи, то возможны три варианта:

◦в течение всего времени t решения задачи (или t — цикл управления) ВС работала безотказно. Т. е. без каких-либо осложнений задача решена в предположении, что программы составлены правильно;

◦произошел сбой (не усложняя проблемы, учитывая обычную быстротечность процессов, считаем, что сбой — единственный);

◦произошел отказ.

Примечание. Сбой — самоустранимый отказ. В результате случайных наводок в некоторой цепи может появиться или пропасть сигнал. Сбои приводят (по классификации разработчиков МВК "Эльбрус") к синхронным и асинхронным авариям. При синхронной аварии (ее вызывают преимущественно сбои в ЦП) может быть установлена и повторена команда, при исполнении которой авария произошла. При многочисленных передачах информации внутри ВС используются коды, исправляющие ошибки. Значит, в этом случае сбои также приводят к синхронным авариям.

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

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

Напомним модель надежности.

Пусть λ1 — частота сбоев (количество сбоев в единицу времени), найденная как одна из характеристик данной ЭВМ; λ2 — частота отказов; λ1 + λ2 = λ. Тогда λ t — количество сбоев и отказов за интересующее нас время t— цикл управления.

Разобьем отрезок t на множество n элементарных отрезков. Можно считать вероятность сбоя или отказа на таком элементарном отрезке равной λt/ n. Вероятность бессбойной и безотказной работы на элементарном отрезке равна 1 − λt/ n. Вероятность того, что на всех элементарных отрезках не произойдет сбоя или отказа, приведет к нахождению степени n этого выражения, а далее найдем предел (рис. 12.3)

Тогда p2(t)+ p3(t) = 1 - e-λ t, и разделив пропорционально частотам событий, получим

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

P = KГ P1(t) + KГ P2(t) Pвосст + KГ P3(t) Pрез = KГ(P1(t) + P2(t)Pвосст + P3(t)Pрез).

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

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

Практически (в АСУ) времени для этого нет. Используют методы программного (алгоритмического) контроля. Например, пусть производится интегрирование уравнения движения летательного аппарата с необходимой точностью. После получения очередных значений координат производится приближенная линейная экстраполяция для получения тех же координат на основе предыдущих положений объекта. Тогда точно полученные координаты должны попасть в определенную - окрестность координат, полученных приближенно. Так производится оценка достоверности результатов. Т. е. программно-алгоритмический контроль основан на способности предсказания ограниченной области, которой должны принадлежать результаты счета.

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

Как правило, использование сигнала аппаратного контроля следующее. Программа делится на сегменты некоторого рекомендуемого объема - по времени выполнения и по количеству команд программы, — разделенные контрольными точками. Выход на контрольную точку сопровождается запоминанием или дублированием всей необходимой информации для того, чтобы следующий сегмент мог при необходимости перезапуститься (произвести малый рестарт), если во время его выполнения произойдет сбой. Используют при этом и расслоение памяти, запоминая необходимые данные для рестарта в других модулях памяти, т. е. предусматривая возможность отказов модулей памяти. Рестарт с предыдущей (т. е. ближайшей) контрольной точки производится только в случае сбоя и в целом требует затрат значительно меньших, чем двойной просчет и программно-алгоритмический контроль.

Резервирование. Применяется во всех ответственных случаях специального использования ВС. В дополнение к одной, основной ЭВМ используются одна и более резервных. Резервные, как правило, не связаны с внешними объектами или объектами управления. С ними связана основная, а они могут дублировать ее работу, реализуя двойной просчет с анализом на совпадение или участвуя в мажоритарной схеме контроля, когда общее число ЭВМ больше двух и когда с помощью мажоритарного устройства на выходе всех ЭВМ производится "голосование": результаты счета считаются правильными, если получены большинством ЭВМ.

Иногда резервируют не отдельно ЭВМ, а весь комплекс — ЭВМ плюс внешние устройства памяти, связи и обмена. Такой комплекс называют линейкой.

Различают горячий и холодный резерв.

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

Повышение характеристик надежности управляющего ВК можно видеть на примере роста коэффициента готовности ВК. Пусть для одной ЭВМ К Г = 0,9.

Тогда использование двух (одна резервная) одинаковых ЭВМ обеспечивает

KГ(2) = KГ)2 = 0,99("две девятки");

Использование трех (две резервные) одинаковых ЭВМ обеспечивает

KГ(3) = KГ)3 = 0,999 ("три девятки").

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

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

Особенности обеспечения надежности ВС

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

Построение многопроцессорных ВС (в России — семейства МВК "Эльбрус") привело к пересмотру всех традиционных представлений о надежности.

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

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

Вышел из строя один из 10 процессоров ВС, — отказ ли это ВС? Ответ зависит от конкретной системы, решаемых задач, временного режима их решения, от требований к производительности, принимаемых мер по обеспечению устойчивого вычислительного процесса и т. д. Произошел сбой процессора, при котором сработал малый рестарт, перезапустивший весь процесс или процесс с контрольной точки. Потери времени на этот рестарт не приведут к необратимому нарушению работы всей системы? Т. е. это — действительно сбой или отказ? Тем более сбои в работе ОС или та категория сбоев, которая приводит к перезапуску ВС — к большому рестарту: загрузке ОС и работе с начала. В "Эльбрусе-2" большой рестарт выполняется более чем за 3 секунды. К чему это отнести — к сбою или отказу? Это зависит от системы, в которой используется ВС.

Таким образом, в проблемно-ориентированных ВС проблема сбоев и отказов решается комплексно в соответствии с применением ВС.

Использование в ВС большого числа однотипных устройств с учетом идеи виртуальных ресурсов вносит особенности и в понятие резервирования. Реализуется структурное резервирование (развивает идеи скользящего резервирования), на основе которого при отказах производится реконфигурация системы: продолжение ее функционирования при изменившемся количестве устройств одной специализации. В этом смысле говорят о "живучести" системы.

В связи с изложенным, в МВК "Эльбрус-2" одним из механизмов, обеспечивающих "живучесть" комплекса, является система автоматической реконфигурации и перезапуска при сбоях и отказах (САР). Она включает в себя специальную аппаратуру, распределенную по модулям МВК, системные шины, программные средства ОС.

Аппаратно выполняются следующие действия:

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

2.Передача информации об аварии по специальным шинам (а мы думали, что связь между модулями ВС — только через коммутатор!) в другие модули.

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

4.Системная реакция на аварию: либо запуск специальных процедур ОС (малый рестарт), либо перезапуск комплекса (большой рестарт).

Программно выполняются следующие действия:

1.Сбор и обработка диагностической информации аварийного модуля.

2.Попытка вернуть его в рабочую конфигурацию в предположении, что авария — в результате сбоя.

3.Сохранение в системном журнале информации об аварии.

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

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

Возникновение асинхронной аварии на процессе ОС всегда завершается большим рестартом.

Оценка надежностных характеристик ВС при испытаниях

1.Согласуют контрольную задачу (КЗ) или комплекс КЗ, с помощью которых будут производить испытание ВС. В основу КЗ берут те алгоритмы или их аналоги, которые как можно ближе соответствуют назначению ВС в составе системы управления. Хороших показателей испытаний добиваются тогда, когда в состав КЗ включают модели управляемых объектов и таким образом строят замкнутый контур управления объектом. Модели объектов могут учитывать случайные возмущения, и, следовательно, управление становится реальным. Такие КЗ наглядны, результативны, бесспорны, поскольку опираются на принцип "удача — неудача".

2.Согласуют определение основных событий и состояний. Например,

◦малый рестарт считать обнаруженным сбоем с восстановлением;

◦"неудачный" цикл управления считать сбоем без восстановления;

◦большой рестарт считать отказом, где его время — время восстановления;

◦выход из конфигурации числа процессоров, снижающих более чем на 20% производительность ВС (2 процессора из 10 в МВК "Эльбрус-2"), считать отказом;

◦реконфигурацию, не снижающую более чем на 20% производительность, считать отказом с переходом на резерв;

Аналогичные соглашения принимаются и насчет памяти, внешней памяти, ПВВ и ППД, обеспечивающих выполнение КЗ.

3.Объявляют прогон — циклическое непрерывное решение КЗ (комплекса КЗ) в течение значительного времени (например, 5 суток), достаточного для набора статистики.

4.Набирают статистику по ВС в целом и по группам устройств. Обычно разграничивают центральную часть и периферию. Непосредственно снимают те показатели, о которых говорилось выше:

◦среднее время T0 безотказной работы;

◦среднее время Tвосст восстановления;

◦частоту λ1 сбоев; из них — число "восстановленных" для определения Pвосст;

◦частоту λ2 отказов, из них — число приведших к успешной реконфигурации для нахождения Pрез.

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

3  Основы многопоточных программ

3.1  Основные определения

Процессы

Процесс (process) – совокупность действий процессора и необходимых ресурсов для обеспечения выполнения инструкций программы

Состав процесса

Области памяти данных и программ

Стек

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

Состояние

Типичные состояния процесса

Остановлен

Процесс не использует процессор

Терминирован

Процесс закончился, но ещё не удалён

Ожидает

Процесс ждёт событие

Готов

Готов к выполнению, но ожидает освобождения процессора

Выполняется

Процесс выполняется процессором

Межпроцессное взаимодействие

Межпроцессное взаимодействие – способ передачи информации между процессами

Виды межпроцессного взаимодействия

Разделяемая память

Семафоры

Сигналы

Почтовые ящики

События

Событие – оповещение процесса со стороны ОС о возникновении межпроцессного взаимодействия

Примеры событий

Принятие семафором требуемого значения

Поступление сигнала

Поступление сообщения в почтовый ящик

Потоки

Поток (поток управления, задача, нить, thread) – одна из параллельно (асинхронно) выполняющихся ветвей процесса

Особенности потоков

В процессе присутствует единственный главный поток

Все потоки одного процесса работают в едином адресном пространстве

Общие переменные и код

Нет необходимости использовать специальные средства взаимодействия*

Каждый поток имеет собственный стек

Каждый поток имеет собственное состояние

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

Дополнительные определения

Ресурс – объект (устройство, память), необходимый процессу или потоку для выполнения заданных действий

Приоритет – целое число, определяющее важность каждого процесса или потока в ОС

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

3.2  Виды ресурсов

Виды ресурсов по природе

Аппаратные ресурсы

Процессор

Область памяти

Периферийные устройства

Прерывания

Программные ресурсы

Программа

Данные

Файлы

Сообщения

Виды ресурсов по характеристикам

Активные

Способны изменять и создавать информацию (процессор)

Пассивные

Способны хранить информацию (память)

Локальные

Относятся к одному процессу

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

Разделяемые

Относятся к нескольким процессам

Удаляются только после окончания использования их последним процессом

Постоянные

Для работы требуют операций «захватить» и «освободить»

Временные

Для работы требуют операций «создать» и «удалить»

Виды разделяемых ресурсов

Некритичные

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

Примеры: жёсткий диск в целом, сетевая карта, видеокарта

Критичные

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

Примеры: разделяемая память при её модификации

3.3  Типы взаимодействия процессов

Типы взаимодействия процессов

Независимые процессы

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

Сотрудничающие процессы

Процессы разделяют канал коммуникации: один пишет, другой читает

Процессы работают по очереди: один работает, второй ожидает завершения работы первого

Конкурирующие процессы

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

Процессы используют критические секции

Процессы используют взаимные исключения (мьютексы)

Определения

Критическая секция – участок программного кода, который допускается выполнять только единственным потоком (процессом)

Взаимное исключение (мьютекс, mutual exclusion, mutex) – способ синхронизации потоков за счёт использования захвата совместно используемого ресурса, также называемого мьютексом

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

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

Основные проблемы синхронизации процессов и потоков

Блокировка (lockout)

Поток ожидает ресурс, который не освободится никогда

Тупик (deadlock)

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

Застой (starvation)

Поток монополизировал процессор

3.4  Основные средства синхронизации

Безопасное и небезопасное взаимодействие

Безопасное взаимодействие – целостность информации и неделимость действий при взаимодействии обеспечиваются операционной системой

Небезопасное взаимодействие – целостность информации и неделимость действий при взаимодействии обеспечиваются приложением

Разделяемая память

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

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

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

Операции

Создать – создаётся объект (файл), недоступный для использования

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

Отсоединить – объект разделяемой памяти отсоединяется от адресного пространства процесса

Удалить – процесс сообщает ОС о том, что больше не будет использовать разделяемую память, реально объект разделяемой памяти будет удалён после окончания его использования последним процессом

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

Например, пусть методом "разделяй и властвуй" производится распараллеливание сортировки слиянием. Известны оценки сложности такой сортировки (как функции параметра n — длины последовательности).

2. Механизм семафоров. Различают двоичные семафоры, имеющие значения "открыт" и "закрыт", и семафоры-счетчики. "Закрытие" увеличивает их на единицу, "открытие" — уменьшает на единицу.

Анализ задач и, в частности, задач обработки больших массивов данных (баз данных и баз знаний) показал целесообразность совместной реализации этих двух принципов в многопроцессорной вычислительной системе. В одном семафоре, назовем его комбинированным, в действительности воплощены два семафора: двоичный и счетчик:

В начале считывания из массива выполняется операция Сб := Сб+ 1; при окончании считывания — операция Сб := Сб - 1. Значение Сб 0 означает: семафор C "закрыт по считыванию".