Task01 (Задание 1)

Задание 1.Потенциальные и достижимые состояния программы (10баллов).َФормулировка заданияДано:Дан текст программы на языке С с функциями f и g.Предполагается, что функции f и g выполняются параллельно, в двух разных потоках управления(процессах) P_f и P_g соответственно.

Будем считать состоянием модели программы совокупностьзначений счѐтчиков команд c_f и c_g процессов P_f и P_g, значения глобальных и локальныхпеременных заданной программы.Неинициализированные переменные принимают специальное значение, обозначаемое символом #,лежащее вне диапазона MININT..MAXINT.Требуется:1. (1 балл) Оценить размер множества потенциальных состояний программы. Ответ обосновать.2. (2 балла) Оценить размер множества достижимых состояний программы.

Ответ обосновать. Вобосновании описать множество достижимых состояний с помощью линейных равенств инеравенств на языке C.Например, (c_f == 3 && a < 5) || (c_g == 4 && b > d).3. (7 баллов) Написать программу на языке С, которая вычисляет и записывает в текстовой файлstates.txt множество достижимых состояний заданной программы для заданных значенийпараметров функций, а также выводит в стандартный поток вывода количество достижимыхсостояний.На выполнение задания отводится три недели.Требования к файлам решения:Решение задачи должно включать в себя 3 файла:1.Исходная формулировка задачи с именем task.txt2.Описание решения пп.

1-2 в текстовом файле с именем solution.txt. Текстовый файлдолжен быть в одной из кодировок: utf8, cp1251 (Windows), koi8-r. Файлы другихформатов (doc, pdf, etc) не принимаются.3.Файл group_surname.c с программой подсчёта состояний (group - номер вашей группы,surname - ваша фамилия латиницей).Требования к программе:1.Программа должны вычислять множество достижимых состояний программы, присланнойвам на почту, для заданных значений параметров функций f и g.2. Программа должна уметь выводить множество состояний в текстовой файл в формате:значение счётчика f, значение счётчика g, значение h, значение f.x, значение f.y, значениеg.x, значение а.y, (через запятую) по одному состоянию в строке.

Значения счётчиковнумеруются с 0. Первая строка файла должна содержать описание формата вывода, аименно: c_f, c_g, h, f.x, f.y, g.x, g.y. Обратите внимание, что смена состояния программыпроисходит после выполнения соответствующего оператора программы (например,присваивания).3. Программа должны выполняться в консоли. Обязательными входными параметрамиявляются значения параметров функций a и b в следующем порядке:имя_программы <f_a> <f_b> <g_a> <g_b>Также должны поддерживаться параметры:-file имя_файла - запись состояний в указанный файл,-count - вывод общего количества состояний программы в стандартный поток вывода.При запуске без параметров (либо с недостаточным количеством параметров)программа должна выводить информацию о программе, авторе, годе написания ипараметрах запуска.4.

Исходный код программы должен содержать информацию об авторе и годе написанияпрограммы.5.Программа должна быть написана на языке ANSI C либо ANSI/ISO C++.6.Программа должна успешно компилироваться компилятором gcc со следующимипараметрами: gcc -O2 -Wall -Werror -Wformat-security -Wignored-qualifiers -Winit-self-Wswitch-default -Wfloat-equal -Wshadow -Wpointer-arith -Wtype-limits -Wempty-body-Wlogical-op -Wstrict-prototypes -Wold-style-declaration -Wold-style-definition -Wmissingparameter-type -Wmissing-field-initializers -Wnested-externs -Wno-pointer-sign.7.Допускается использование только библиотек stdlib, STL, iostream и stdio.8.Текст программы должен быть снабжён исчерпывающими комментариями.

Какминимум, должны быть прокомментированы все объявления функций, операторыветвления и линейные участки программы.9.Программа должна быть написана самостоятельно. При заимствовании фрагментовкода из open-source проектов должен быть указан автор кода. Заимствовать код изрешений предыдущих лет не допускается.

Если будет обнаружено, что несколькоприсланных решений написаны одним человеком, оценка будет снижена для всехпохожих работ. Для анализа схожести кода будут использованы соответствующиеинструментальные средства.Чек-лист и штрафыСтандартные ошибкиШтрафНеправильная тема письма-1Нет task.txt-2Нет solution.txt-3Нетобоснованиясостоянийчислапотенциальных-1Нет обоснования числа достижимых состояний-2Нет разметки операторов заданной программыномерамиКод своей программы не откомментирован-2Состояние меняется до выполнения оператора-2Неправильные входные параметры или форматвывода-2Отсутствуют терминальные состояния-2Дублирующиеся состояния-2Потерянные состояния-3-1Методические указания по выполнению задания:1.

Оценка числа потенциальных состояний программы.При оценке количества потенциальных состояний программы оценивается мощность множествасостояний данной программы. Поток управления программы при этом не учитывается. Такимобразом, необходимо оценить мощность множеств значений счётчиков управления двухпроцессов, множеств возможных значений их параметров и локальных переменных, а такжеразделяемой переменной. Далее требуется оценить мощность множества потенциальныхсостояний программы в соответствии с определением, данным в формулировке задачи.ПримерПусть нам дана следующая программа:int h;void f(int a){h = a;if (h < a) {h = 0 ;}}void g(){int x;x = h;}Пронумеруем её строки следующим образом:1:a;2:3:int h;void f(int a){h =4:}if(h < a) {h = 0;}1:x;2:3:void g(){int}x = h;Приняв мощность множества значений типа int за 232, мы получим оценку числа потенциальныхсостояний в 4*3*296 = 12*296.2.Оценка числа достижимых состояний программы.Для оценки числа достижимых состояний программы необходимо оценить ограничения,накладываемые на множество потенциальных состояний потоком управления программы.Ограничения на множество возможных значений счѐтчика управления проистекают изнедостижимости отдельных операторов программы.

Ограничения на множество возможныхзначений переменных программы проистекает из набора операторов присваивания,присутствующих в программе, и их достижимости.Рекомендуется следующая последовательность действий:1) исходя из присутствующих в программе операторов присваивания, более точно оценитьмножества допустимых значений переменных программы.2) для каждой точки программы, начиная с начальной, оценить возможные значения параметров,локальных и разделяемых переменных в данной точке, описав диапазоны значений припомощи линейных неравенств. Это позволит оценить количество возможных различныхсостояний для каждой точки программы.3) исходя из полученных данных, выявить недостижимые операторы программы.4) подкорректировать построенные линейные неравенства с учѐтом недостижимости отдельныхоператоров.5) сложить полученные оценки для отдельных точек программы.

При этом рекомендуетсявыполнять генерализацию с целью упрощения записи количества состояний, получая неточную оценку, а оценку сверху.ПримерОценим множества допустимых значений переменных программы из предыдущего примера.1.-216 <= a <= 216 (входной параметр типа int),2.h = {#, a, 0}3. x = {#, h}Разметим программу из предыдущего примера линейными неравенствами:int h;void f(int a){h = a;if(h < a) {h = 0;}4:1:2:3:}//h = #, -2^16 <= a <= 2^16, x = #//h = a, -2^16 <= a <= 2^16, x = {#, a}//недостижимо//h = a, -2^16 <= a <= 2^16, x = {#, a}void g(){int x; // h = {#, a}, -2^16 <= a <= 2^16, x = #x = h; // h = {#, a}, -2^16 <= a <= 2^16, x = #}// h = {#, a}, -2^16 <= a <= 2^16, x = {#,a}1:2:3:Таким образом, число достижимых состояний программы можно оценить сверху числом 36*2 32 =2*2*3*3*232 (мощность мн-ва допустимых значений h * мощность мн-ва допустимых значений x *количество достижимых операторов f * количество достижимых значений g * мощность мн-ва допустимыхзначений параметра a).3.

Программа, вычисляющая количество достижимых состояний.•Изменение состояния программы происходит после выполнения оператора, вызвавшегоданное изменение,•В частности, это потребует введения т.н. терминальных состояний, в которые программапереходит после выполнения последнего оператора.• Помните, что в множестве нет одинаковых элементов, и множество состояний - неисключение.Сроки сдачи в 2014/2015 учебном году:Для получения заданияvolkanov@lvk.cs.msu.suприслатьписьмостемойReliability-Task1-RequestнаЗадача сдаётся в МЗ 758 14:35• 23.09 (приоритет у 420 группы)• 30.09 (приоритет у 421 группы)• 07.10 (интерливинг)Сданная задача присылается на volkanov@lvk.cs.msu.su письмом с темой Reliability-Task1-SolutionПрисланная до 23:59 (московоское время) 7 октября задача принимается (БЕЗ ШТРАФА), далее –1балл за каждую неделю.В исключительных случаях возможна сдача по почте.Вариант для самостоятельного решенияint h;void f(int a, int b){int x, y;x = 3;y = 5;h = b;if (h > b – x) {x = 4;}if (x > 7) {x = 3;}if (x > 1) {y = 1;}h = y;}void g(int a, int b){int x, y;x = 8;y = 2;h = a;x = 3;h = x + b;if (y > 5) {y = 1;}y = 1;while (x > 4) {if (h > 0)break;if (x > 10) {h = a + b;h = b + x;}y = 4;}}.