Модедирование систем. Формализация и алгоритмизация процессов функционирования систем

  ФГАОУ ВПО «Уральский  Федеральный  Университет  им. первого Президента России Б.Н.Ельцина» 

  Кафедра Автоматика и управление в технических  системах 
 
 
 
 
 
 

  МОДЕЛИРОВАНИЕ СИСТЕМ.

  ФОРМАЛИЗАЦИЯ  И АЛГОРИТМИЗАЦИЯ ПРОЦЕССОВ ФУНКЦИОНИРОВАНИЯ СИСТЕМ

  Домашнее  задание

Вариант 11 
 
 
 
 

Студент

Гр. Р-390101                                                                       Чебыкин Д.В.

Преподаватель                                                                   Трофимова О.Г.                                                                                                                               
 
 
 
 
 
 
 
 
 
 

  Екатеринбург 

  2011 

Задание:

     Специализированное  вычислительное устройство, работающее в режиме реального времени, имеет  в своем составе два процессора, соединенные с общей оперативной  памятью. В режиме нормальной эксплуатации задания выполняются на первом процессоре, а второй является резервным. Первый процессор характеризуется низкой надежностью и работает безотказно лишь в течение 150 ± 20 мин. Если отказ  происходит во время решения задания, в течение 2 мин производится включение  второго процессора, который продолжает решение прерванного задания, а  также решает и последующие задания  до восстановления первого процессора. Это восстановление происходит за 20 ± 10 мин, после чего начинается решение  очередного задания на первом процессоре, а резервный выключается. Задания  поступают на устройство каждые 10 ± 5 мин и решаются за 5 ± 2 мин. Надежность резервного процессора считается идеальной.

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

1. Цель

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

     Метод решения – метод имитационного  моделирования 

2. Постановка  задачи:

     Задача  заключается в составлении и  исследовании модели вычислительной системы  и определении основных характеристик  моделируемой системы:

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

     Критерий  оценки эффективности процесса функционирования системы – количество решенных задач должно быть максимальным и одновременно с этим количество отказов процессора и прерванных задач должно быть минимальным

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

     Экзогенные  и эндогенные переменные модели определены на этапе построения концептуальной модели.

     Формализация  процесса функционирования исследуемой  системы представлено в абстрактной Q – схеме. 
 
 
 
 
 
 
 
 

3. Выдвижение  гипотезы:

     Загруженность первого процессора больше загруженности  второго процессора, так как время безотказной работы первого процессора больше времени его восстановления.

     Соотношение решенных задач на первом и втором процессорах составляет 4:1. 

4. Предположения:

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

5. Входные переменные модели

     Экзогенные  переменные (независимые) и управляемые.

     Интервал  времени (интенсивность) поступления  задачи t_пр±∆t_пр, где t_пр – средний интервал времени между поступлением задач на вычислительное устройство, ∆ t_пр половина интервала, в котором равномерно распределены значения времени поступления. Единицы измерения – минуты.

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

6. Выходные  переменные

     Эндогенные (зависимые) и неуправляемые

      Количество  решенных задач за заданный интервал времени работы устройства N_обс. 

7. Параметры модели экзогенные и  управляемые

     Время решения задачи на любом из процессоров - t_р±∆t_р, где t_р – среднее время решения задачи на процессоре, ∆t_р – 0,4 интервала решения задачи, в котором равномерно распределены значения.

     Время безотказной работы первого процессора - t_раб±∆t_раб, где t_раб – среднее время бесперебойной работы первого процессора, ∆t_раб – часть интервала бесперебойной работы первого процессора, в котором равномерно распределены значения.

     Время включения второго процессора, когда первый процессор выходит из строя - t_вкл.

     Время восстановления первого процессора - t_восст±∆t_восст, где t_восст – среднее время восстановления работоспособности первого процессора, ∆t_восст – половина интервала времени восстановления первого процессора, в котором равномерно распределены значения.

    Общее время работы устройства – T.

8. Параметры модели эндогенные и неуправляемые

     Загрузка  первого и второго процессоров - K₁, K₂ относительно единицы

     Количество  задач поступивших на решение  – N_з

      Число решенных задач – N_обс.

     Длина очереди – L

Количество  задач, решение которых будет  прервано N_прерв. Единицы измерений – количество задач.

      Число отказов процессора – N_отк. Единицы измерений – количество отказов. 

9. Степень влияния параметров на процесс функционирования системы в целом

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

     Воздействие внешней среды отсутствует.

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

     Функция поверхности отклика позволяет  ограничить экстренные реакции системы  и является совокупностью критериев  оценки эффективности.

     Концептуальная  модель исследуемой системы представлена в виде структурной схемы на рис. 1 и в виде Q схемы на рис. 2 

10. Функции отклика

K₁=f(t_пр±∆t_пр, t_р±∆t_р, t_раб±∆t_раб, L, t_восст±∆t_восст)

K₂=f(t_пр±∆t_пр, t_р±∆t_р, t_раб±∆t_раб, L, t_восст±∆t_восст, t_вкл)

N_прерв=f(t_пр±∆t_пр, t_р±∆t_р, t_раб±∆t_раб, N_отк, t_восст±∆t_восст)

N_обс=f(t_пр±∆t_пр, t_раб±∆t_раб, t_восст±∆t_восст, t_вкл, t_р±∆t_р)

L=f(t_пр±∆t_пр, t_р±∆t_р, N_отк, t_вкл)

N_отк=f(t_раб±∆t_раб, t_восст±∆t_восст) 

11. Целевые функции

K₁→max

t_пр±∆t_пр ↓, t_р±∆t_р ↑, t_раб±∆t_раб ↑, L ↑, t_восст±∆t_восст ↓

K₂ →max

t_пр±∆t_пр ↓, t_р±∆t_р ↑, t_раб±∆t_раб ↓, L ↑, t_восст±∆t_восст ↑, t_вкл ↑

N_прерв →min

t_пр±∆t_пр ↑, t_р±∆t_р ↑, t_раб±∆t_раб ↑, N_отк ↓, t_восст±∆t_восст ↑

N_обс→max

t_пр±∆t_пр↓, t_раб±∆t_раб↓, t_восст±∆t_восст↑, t_вкл↓, t_р±∆t_р↑

L →min

t_пр±∆t_пр ↑, t_р±∆t_р ↓, N_отк↓, t_вкл ↑

N_отк →min

t_раб±∆t_раб ↑, t_восст±∆t_восст ↑ 
 
 
 

12. Структурная схема модели системы  и ее описание

Рис. 1 Концептуальная модель системы в виде структурной  схемы

     На  структурной схеме (рисунок 1) изображены следующие элементы моделируемой системы:

• Входной поток заданий Х
• Пр1 – первый (основной) процессор
• Пр2 – второй (резервный) процессор
• Переключатель – выбирает направление движения задачи из памяти или «выбрасывает» задачу из системы.
• Память – оперативная память, которая соединяет два процессора

           Опишем каждый блок структурной схемы модели.

           Поступление заданий  на вход системы происходит в среднем  каждые 10 минут.

     Задания поступают на память, вместимость  которой одна задача, память, в свою очередь, подает сигнал на переключатель: есть ли в ней нерешенная задача. Если в момент времени, когда в памяти есть задача, приходит новая задача, переключатель отказывает ей в обслуживании. Таким образом, максимальная длина очереди – 2: одна задача хранится в памяти, ожидая обслуживания, вторая обрабатывается процессором.

     После памяти задача следует на основной процессор.

     Задача  решается на основном процессоре в  среднем за 5 минут. Этот процессор безотказно работает в среднем 150 минут. Когда процессор выходит из строя, он подает сигнал на переключатель, который меняет направление поступления задачи, и на резервный процессор, который начинает включаться (время включения – 2 минуты).

     Так же этот процессор отправляет нерешенную задачу обратно в оперативную  память.

     После включения резервного процессора задача из оперативной памяти поступает  на процессор и решается в нем  в среднем за 5 минут. Далее задачи идут на резервный процессор (до восстановления основного).

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

13. Q – схема модели системы и ее описание

Рис. 2 Концептуальная модель системы в виде Q – схемы.

Обозначения:

И –  источник задач

Н –  накопитель с емкостью L_н=2

кл –  клапан – определяет направление  движения задачи

К –  канал решает задачу 

14. Формализованная модель системы

      Источник  И имитирует процесс поступления  заданий, которые поступают с интервалом 10±5 минут в накопитель Н, с емкостью, которой хватит для всех попавших в него задач. Канал К1 соответствует основному процессору, канал К2 – включению второго процессора, канал К3 – резервному процессору. От источника задачи поступают в клапан 1, который передает все принятые задачи в накопитель Н. От накопителя Н задачи поступают в клапан 2, который управляется каналом К1. Если канал К1 исправен, то заявки поступают на клапан 3, который управляется каналом К1, если этот канал занят, то задачи ждут своей очереди. Решение задачи в канале К1 занимает 5±2 минуты. Канал К1 так же управляет клапаном 6, который в случае неисправности процессора переносит прерванные задачи N_прерв через клапан 2 на решение к вспомогательному процессору (вне очереди). Если основной процессор исправен, то решенные задачи с клапана 6 считаются выполненными N_обс.

      В случае неисправности основного процессора задачи с клапана 2 поступают на клапан 4, который управляется каналом К2.

      Если  процессор еще не включен, то задача с клапана 4 поступает в канал  К2 и включает его: время включения  – 2 минуты. Далее задача поступает  на клапан 5, который управляется  каналом К3. Время решения задачи в канале К3 - 5±2 минуты, если канал  К3 занят, то задача ждет своей очереди.

      Если  процессор включен, то задача с клапана 4 сразу переходит к клапану 5.

      После канала К3 задача считается решенной N_обс.

      После восстановления канала К1 (время восстановления 20±10 минут), канал К1 подает сигнал на клапан 2, который позволяет отправлять задачи на клапан 3.

Q={И, Н, К1, К2, К3, N_обс, кл1, кл2, кл3, кл4, кл5, кл6, L}

15. Расчеты

      Чтобы рассчитать N_обс, необходимо оценить работоспособность системы N_возм – число возможных решенных задач. Для этого посчитаем среднее число возможных решенных задач на первом и на втором процессорах. Для этого посчитаем среднее число отказов основного процессора в системе.

N_отк.ср=T/( t_раб.ср + t_{восст.ср})-1=3000/(150+20)-1≈17

      Из  этого значения можно сделать  вывод, что цикл работы первого процессора (в среднем 150 минут) будет повторяться 17 раз и еще 110 минут (для простоты расчета примем 18 полных раз), а цикл работы второго процессора (в среднем 20 минут) будет повторяться 17 раз.

  Отсюда посчитаем число решенных задач на первом и втором процессорах

N₁=(N_отк.ср +1)t_раб.ср/ t_р.ср=(17+1)*150/5=540

N₂=N_отк.ср(t_{восст.ср-} t_вкл)/ t_р.ср=17*20/5≈62

N_возм=N₁+N₂=540+62=602

      Таким образом получаем что система  способна решить в среднем 602 задания  за 3000 минут.

      Посчитаем среднее количество задач, которые  придут на выполнение – N_з.

N_з=T/t_пр.ср=3000/10=300

      Отсюда делаем вывод, что система решит все пришедшие на нее задачи –

N_обс= N_з= 300 шт. 

      Предположим (для простоты счета) что задача не будет прервана только при времени  решения t_р=5 минут и соответственно времени работы t_раб={130; 135; 140; 145; 150; 155; 160; 165; 170}. Вероятность того, что задача будет решена за 5 минут составляет 20%, а вероятность того, что основной процессор будет работать только заданные промежутки времени примерно 20%. В итоге получаем суммарную вероятность, что совпадут эти два события – 4%. Отсюда получаем, что число прерванных заданий будет равно 96% от общего числа отказов.

N_прерв=0,96*N_отк=0,96*17 ≈16

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

L_max= T/ t_пр.мин- N_{отк.макс}- (T- N_{отк.макс}(t_р.макс+ t_вкл)) / t_р.макс=3000/5-3000/(130+10)-(3000-

-3000(7+2)/(130+10) ≈177 

      Коэффициент загрузки – это отношение времени  работы процессора к общему времени  работы.

K₂=N_отк.срt_восст/T=17*20/3000=0,11