Task03 (Задание 3)

Задание 3.Построение сети временных автоматов для решения задачиотказоустойчивого планирования работ в вычислительнойсистеме (UPPAAL) (10 баллов).Формулировка заданияДано:Дан набор программ (далее работ), каждая из которых может быть выполнена на одном измножества процессоров. На набор работ и их выполнение наложены следующие ограничения:1. Работы при выполнении не могут быть прерваны, а также не мигрируют междупроцессорами при их выполнении.2.

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

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

Возможны следующие варианты МОО: использование приёмочного теста(AT), N-версионное программирование (NVP_0_1), N-версионное программирование сиспользованием аппаратного резервирования (NVP_1_1), восстановление блоками (RB_1_1) иликонтрольные точки (CP). Подробное описание функционирования МОО можно найти вметодических указаниях.Требуется:1. (4 балла) Описать шаблоны автоматов для процессоров и работ. Создать сеть временныхавтоматов, позволяющих построить расписание выполнения работ на процессорах без учётарезерва процессора и МОО для критической работы.Подсказка: необходимо создать два типа параметризованных шаблонов отдельно дляпроцессора, отдельно для работ.

Каждый процессор и работа это экземпляр шаблона сзаданными параметрами. Взаимодействие между процессорами и работамирекомендуется осуществлять путём посылок сообщений через канал. Также возможноиспользование глобальных переменных.2. (1 балл) Проверить выполнение следующих свойств: отсутствие тупиков при выполнении модели; каждая задача выполнится, хотя бы на одном процессоре.В зависимости от варианта задания найти расписание, выполняющееся за минимальное время(min_time) или с минимальным общим временем простоя процессоров (min_delay).

Оценитьскорость работы UPPAAL при различных вариантах обхода дерева решений (search order)Подсказка: такое расписание можно найти путём проверки временных свойств ипоследовательного уменьшения(увеличения) ожидаемого времени.3. (3 балла) Построить модель построения отказоустойчивого расписания дополнив модель,разработанную в п.1. Необходимо промоделировать отказ CPU_1 в момент времени равный 15, атакже восстановление работы после отказа. Также необходимо промоделировать работу МООдля критической работы.4. (1 балл) Проверить выполнение следующих свойств: отсутствие тупиков при выполнении модели; каждая задача выполнится, хотя бы на одном процессоре.В зависимости от варианта задания найти расписание для модели из п.3, выполняющееся заминимальное время (min_time) или с минимальным общим временем простоя (min_delay)процессоров.

Оценить скорость работы UPPAAL при различных вариантах обхода дереварешений (search order).5. (1 балл) Описать полученные в п.2 и п.4 результаты в виде отдельного файла. Файл долженсодержать результаты для моделей, построенных в п.1 и п.3. Результаты должны включатьрезультаты проверки свойств, описание построенного оптимального расписания, времени егоработы или простоя процессоров (в зависимости от варианта), приведены оценки для работыUPPAAL при различных вариантах обхода дерева решений. Также включить в этот файл выводыо возможностях системы UPPAAL и удобстве или неудобстве работы в нём.На выполнение задания отводится три недели. Последний срок сдачи задания – 18 декабря.Требования к файлам решения:Сданнаязадачаприсылаетсянаvolkanov@lvk.cs.msu.suписьмомReliability-Task3-Solution. Решение задачи должно включать в себя 6 файлов:стемой1. Файл с исходными данными year_group_surname_3.csv2.

Файлы year_group_surname_3_1.xml и year_group_surname_3_1.q с моделью и запросамина UPPAAL для модели построения расписания из п.1.3. Файлы year_group_surname_3_3.xml и year_group_surname_3_3.q с моделью и запросамина UPPAAL для модели построения отказоустойчивого расписания из п.3.4. Текстовый файл year_group_surname_ucomparision.txt с описанием выводов п.5Присланная до 23:59 (московское время) 18 декабря задача принимается (БЕЗ ШТРАФА),далее –3 балла за каждую неделю просрочки.Методические указания по выполнению задания:1.

Пример исходных данныхПусть дан вот такой файл исходных данных.ЗадачаABCDECPU_133632CPU_242531CPU_1CГорячий_РезервRB_1_111Критерийmin_timeЗависимостиA,BBDНапример, строкаC65A,Bозначает, что задача C выполняется 6 единиц времени на CPU_1 и 5 единиц времени на CPU_2 и неможет быть начата, пока не выполнены задачи A,B.Граф зависимостей по приведённым данным имеет такой вид:Возможно построение расписания такого вида:Но оптимальным (для п.1) в случае критерия минимизации времени (min_time) являетсяследующее расписание:СтрокаCPU_1Горячий_Резерв1означает, что CPU_1 находится в горячем резерве и переключение на резервную копию занимает 1единицу времени.СтрокаCRB_1_11означает, что для критической задачи C используется МОО RB_1_1 и время проведения тестаравно 1 единице времени.СтрокаКритерийmin_timeозначает, что в качестве критерия оптимальности расписания является минимизация временивыполнения расписания.2.

Работа в случае отказа процессора CPU_1В зависимости от варианта задания возможны следующие варианты резерва процессора: отсутствие резерва; горячий резерв; тёплый резерв; холодный резерв.Ниже описано как функционирует система после отказа для различных вариантов резервапроцессора и список параметров, которые задаются в исходных данных.2.1 Отсутствие резерваПараметры:В этом случае, если в момент отказа процессора на нём выполнялась работа, то она должназаново запуститься на другом процессоре. После момента отказа на процессоре CPU_1 никакиеработы не выполняются.2.2 Горячий резервПараметры:<время_переключения_на_резерв>В этом случае, если в момент отказа процессора на нём выполнялась работа, то онаприостанавливается.

В течении заданного параметром времени происходит переключение нарезервную копию CPU_1 и работа продолжает своё выполнение с точки останова. Послемомента отказа работы выполняются на резервной копии процессора CPU_1.2.3 Тёплый резервПараметры:В этом случае, если в момент отказа процессора на нём выполнялась работа, то онаостанавливается. Затем данная работа мгновенно перезапускается с начала на резервной копииCPU_1, то есть работа начинает выполняться с самого начала.

После момента отказа работывыполняются на резервной копии процессора CPU_1.2.4 Холодный резервПараметры: <время_переключения_на_резерв>В этом случае, если в момент отказа процессора на нём выполнялась работа, то онаостанавливается. В течении заданного параметром времени происходит переключение нарезервную копию CPU_1. После переключения работа перезапускается с начала на резервнойкопии CPU_1, то есть работа начинает выполняться с самого начала.

После момента отказаработы выполняются на резервной копии процессора CPU_1.3. Работа МООВ зависимости от варианта задания возможны следующие варианты МОО: приёмочный тест (AT); N-версионное программирование (NVP_0_1); N-версионное программирование с использованием аппаратного резервирования(NVP_1_1); восстановление блоками (RB_1_1); контрольные точки (CP).Ниже описано как функционирует каждый МОО и список параметров, которые задаются висходных данных.3.1 Приёмочный тест (AT)Параметры:<время_тестирования>Данный МОО включает модуль тестирования результатов работы.

В этом случае послевыполнения работы запускается приёмочный тест. Время работы теста определяется параметром<время_тестирования>. Если тест не пройден, то результат является ошибочным. Припостроении расписания считать, что тест всегда отрабатывает успешно.3.2 N-версионное программирование (NVP_0_1)Параметры:<время_работы_голосователя>Данный МОО включает модуль принятия решений (голосователь) и 3 независиморазработанных версий работы. Все 3 версии работают последовательно на одном процессоре,результат их работы обрабатывает голосователь.