task1_var1 (Домашнее задание 1)

Анализ динамической планируемостинаборов задачАвтор курса: Балашов Василий ВикторовичE-mail: hbd@cs.msu.suАссистент: Селецкий Станислав ВалерьевичE-mail: leostas@lvk.cs.msu.suВариант 11КонтекстВ однопроцессорной вычислительной системе реального времени (ВС РВ) используется динамическое планирование выполнения задач по схеме с фиксированными приоритетами. Выполнение задач происходит с вытеснением. Для оценки планируемости набора задач используются формулы, описанные в лекциях [1].Требуется реализовать программу, оценивающую планируемость по этим формулам.2Входные данные1.

Дана информация о наборе задач для выполнения на ВС РВ с динамическим планированием. Про каждую задачу известно имя (текстовая строка) иследующие числовые параметры (натуральные числа):• период;• приоритет (чем выше значение, тем больше приоритет);• относительный директивный срок, не превосходящий период;• длительность выполнения.Информация о наборе задач содержится в XML-файле, структура которогоописана ниже.2. ВС РВ использует схему динамического планирования с фиксированнымиприоритетами.3ТребованияНеобходимо написать программу, которая:1.

Считывает входные данные из xml-файла;12. Проверяет описанные в [1] условия планируемости и выдаёт диагноз по планируемости (ответ «YES», если гарантируется выполнение всех задач с соблюдением директивных сроков или «NO» — в противном случае);3. В случае отрицательного ответа также выводит имя первой (по порядкууменьшения приоритета) задачи, для которой время отклика оказалось больше директивного срока.3.1Требования к программной реализации и оформлениюответаК заданию прилагается несколько наборов входных данных, оформленных ввиде XML-файлов. Для возможности самопроверки эти файлы сгруппированы впапки YES и NO в соответствии с правильными ответами на поставленную задачу.В качестве языка программирования необходимо использовать C или C++.

Полученная реализация должна удовлетворять следующим требованиям:1. Код программы должен быть чистым и аккуратным. Он должен содержатькомментарии в количестве, необходимом для его понимания. Подробнее простиль кодирования можно прочитать, например, в [2], [3].2. Архив с решением должен содержать Makefile, необходимый для сборки изапуска программы. В списке целей должны присутствовать цели all и clean(подробнее про написание и структуру Makefile’ов можно почитать, например, в [4]).3. Архив с решением должен содержать всё необходимое для сборки и запускапрограммы в linux-based операционной системе (в частности, проверяться задание будет на компьютере под управлением Ubuntu 12.04.5).

Если же у васв распоряжении имеется лишь копьютер на Windows, для проверки работоспособности решения на linux’e имеет смысл воспользоваться эмулятором [5]и/или виртуальной машиной.4. Все исходные файлы (за исключением Makefile’а) должны находиться в папкеsrc, включённой в архив с решением.5. Получаемый исполняемый файл должен быть назван по шаблону:prog_<studnum>_<groupnumber>, где studnum — номер студенческого билета. Например, мой файл назывался быprog_02100242_521.26. Имя входного XML-файла должно передаваться через аргументы команднойстроки.

Результат работы программы должен быть выведен в стандартныйпоток вывода. Сначала должен быть напечатан ответ на задачу (либо YES,либо NO), а на следующей строке в случае отрицательного ответа должно присутствовать имя задачи с нарушением условия на величину отклика.Пример запуска приложения:prog_02100242_521 input.xml7. Архив с решением должен содержать текстовый файл readme, содержащий:(a) ФИО сдающего задание;(b) номер группы;(c) список использованных библиотек, если функционала, предоставлямогостандартной, было недостаточно;(d) любую другую информацию на выбор сдающего, которая могла бы упростить и/или ускорить процесс приёма его задания.8.

Архив с решением должен иметь формат zip и имя ФамилияИО.zip (напримермоё решение имело бы имя SeletckiiSV.zip). Глубина вложенности — одинуровень (т.е. в самом архиве уже должны лежать все файлы, а не отдельнаяпапка с файлами).3.2Формат входного XML-файлаXML-файл с описанием набора задач имеет следующую структуру:• <system> — корневой элемент в описании ВС:– содержит элементы <task>;• <task> — описание задачи, имеет атрибуты:– name (строка) — имя задачи;– period (целое число) — период задачи;– priority (целое число) — приоритет задачи;– deadline (целое число) — относительный директивный срок;– duration (целое число) — длительность выполнения задачи.33.2.1Пример входного файла<system><task name="task1" period="100" priority="2" deadline="30"duration="15"/><task name="task2" period="195" priority="1" deadline="20"duration="20"/><task name="task3" period="250" priority="3" deadline="10"duration="30"/></system>4Процесс сдачи задания• Задание должно быть прислано на электронную почту leostas@lvk.cs.msu.suс копией на почту hbd@cs.msu.su (тема письма должна быть по шаблону:«[ICS][Task1] ФамилияИО».

ФамилияИО писать по-русски) не позднее 23:59:592 ноября 2015 года (мягкий дедлайн). Если задание будет прислано позднее00:00 3 ноября 2015 года, но до 23:59:59 9 ноября 2015 года (жёсткий дедлайн),то получаемая за него оценка умножается на коэффициент 0.7.• Задания, присланные позднее 00:00 10 ноября 2015 года, проверяться не будут.• Задания, требования по оформлению которых были нарушены, также проверяться не будут (информация о нарушении придёт в ответном письме).• В случае выявления значительных общих фрагментов программного кода вдвух или более сданных реализациях преподаватели имеют право аннулировать все реализации, содержащие общий фрагмент.

Критерий значительностиобщего фрагмента — на усмотрение преподавателей.4Литература[1] В. В. Балашов Информационно-управляющие системы реального времени(слайды лекций).[2] 90 рекомендаций по стилю написания(http://habrahabr.ru/post/172091/)программ[3] GoogleC++StyleGuide[HTML]styleguide.googlecode.com/svn/trunk/cppguide.html)наC++[HTML](https://google-[4] Makefile для самых маленьких [HTML] (http://habrahabr.ru/post/155201/)[5] Cygwin [HTML] (www.cygwin.com)[6] Google [HTML] (www.google.com)5.