Модель работы ЭВМ

Аннотация

В данной пояснительной записке рассматривается процесс моделирования работы САПР. Построение модели осуществляется последовательно, в несколько этапов:

описание моделирующей системы;

разработка структурной схемы;

построение временной диаграммы;

разработка Q-схемы;

построение укрупненного моделирующего алгоритма и, затем, детальной схемы моделирующего алгоритма;

описание математической модели.

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

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

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

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

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

1. Описание моделирующей системы

модель система алгоритм программа Из анализа задачи можно сделать вывод о том, что процессы, протекающие в нашей системе являются случайными. Действительно: необходимость в решении задачи может появиться в любой момент времени, время набора задания заранее неизвестно. Случайна и продолжительность выполнения задания на ЭВМ. Поэтому, данную систему можно отнести к классу систем массового обслуживания (СМО). СМО — это разновидность математических схем, разработанных в теории массового обслуживания для формализации процессов функционирования систем с преобладанием массового обслуживания (например, очереди любого вида, работа любой АТС, поток задач в вычислительный центр, поток неисправных приборов в ремонтную мастерскую и т. п.). Такие системы описываются при помощи терминов Q-схем (непрерывно-стохастических схем).

Потоки требований, потоки обслуженных требований и вообще все потоки в СМО обладают одним свойством — они случайны. Любой элементарный акт обслуживания в СМО можно разделить на две составляющих:

ожидание заявкой начала обслуживания;

собственно обслуживание заявки.

Таким образом, можно представить следующую схему элементарной СМО (рис. 1.1).

Рис. 1.1. Q-схема элементарной СМО.

Здесь:

И — источник заявок;

Н_i — i-ый накопитель заявок;

К_i — i-ый обслуживающий прибор;

W_i — поток заявок на обслуживание;

V_i — поток заявок, получивших отказ в обслуживании;

Y_i — поток обслуженных заявок.

Накопитель заявок Н_i характеризуется емкостью:

l_i = 0, L,

где l_i — количество заявок в настоящий момент;

L — емкость накопителя.

Канал обслуживания К_i характеризуется скоростью или интенсивностью обслуживания заявок.

Потоки W_i, V_i и Y_i являются потоками событий.

2. Структурная схема

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

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

режим нормального обслуживания, когда задание сразу начинает выполняться ЭВМ;

режим отказа в выполнении задания, когда ЭВМ уже занята расчетом другого задания.

3. Временная диаграмма

Процесс функционирования станции САПР можно представить на временной диаграмме (рис. 3.1).

Рис. 3.1. Временная диаграмма На диаграмме:

оси 1−5 — моменты прихода проектировщиков с заданием;

ось 6 — набор задания и выполнение его ЭВМ.

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

4. Q-схема системы

Все описанное выше есть, по сути, этап построения концептуальной модели системы. Следующим должен дать этап формализации модели. Так как описанные процессы являются процессами массового обслуживания, то для формализации задачи используем символику Q-схем. В соответствии с построенной концептуальной моделью и символикой Q — схем структурную схему данной СМО (рис. 2.1) можно представить в виде однофазной одноканальной Q-схемы с отказами, показанной на рис. 4.1, где И1-И5 — источники, К — канал.

Рис. 4.1. Структурная схема САПР в символике Q — схем Источники И1-И5 имитируют процесс прихода проектировщиков (в терминах Q-схем — заявок). Если канал К, имитирующий работу ЭВМ, занят, то заявка теряется, что соответствует уходу проектировщика необслуженным.

Поскольку все источники одинаковы и имеют одну и ту же интенсивность, то их можно заменить одним источником заявок с интенсивностью в 5 раз выше, чем у исходного. Тогда получим следующую упрощенную Q-схему, изображенную на рис. 4.2.

Рис. 4.2. Структурная схема САПР в символике Q — схем после упрощения

5. Укрупненная схема моделирующего алгоритма

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

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

При построении моделирующего алгоритма по принципу t или алгоритма с детерминированным шагом тщательно анализируются все потоки событий в моделируемой системе. Выбирается поток с максимальной интенсивностью событий, в нем определяется минимальный интервал времени между двумя соседними событиями и этот интервал принимается неизменным: t = const. По этому алгоритму в момент времени t_i производится просмотр состояний всех элементов системы, делаются необходимые изменения в состояниях, и считается, что далее в течение времени t в системе ничего не происходит. Очередной просмотр состояний элементов системы производится в момент времени t_i+t, и далее все повторяется с этой периодичностью.

В приведенном моделирующем алгоритме блоки 1, 2, 7 и 8 являются типовыми. Блоки 3, 4, 5 и 6 — это блоки, в которых содержатся операции, характерные для рассматриваемой СМО.

В соответствии с рассмотренными выше соображениями, при моделировании СМО целесообразно начинать просмотр элементов схемы от конца к началу, поэтому блоки 3 — 6 будут иметь следующее содержание:

Рис. 5. 1. Обобщенная схема моделирующего алгоритма процесса функционирования САПР блок 3: проверка условия окончания процесса моделирования работы системы;

блок 4: моделирование работы канала;

блок 5: поступление заявок на вход системы;

блок 6: переход к следующему моменту системного времени t_n.

6. Детальная схема моделирующего алгоритма

Блок 1

Блок-схема блока 1 приведена на рис. 6.1.1.

Рис. 6.1.1. Детальная блок-схема блока 1

Предназначен для ввода исходных данных. Назначение переменных:

ipz, dipz: интенсивность поступления заданий с каждого терминала и диапазон колебаний этого значения (например, 3±1: ipz = 3 и dipz = 1);

tiz, dtiz: время набора задания и диапазон колебаний этого значения;

tvz, dtvz: время выполнения задания на ЭВМ и диапазон колебаний этого значения;

T: время работы САПР.

Блок 2

Блок-схема блока 2 приведена на рис. 6.2.1. Предназначен для задания начальных значений. Назначение переменных:

A, B: соответственно минимальное и максимальное значение случайной величины (служебные переменные):

M, S: математическое ожидание и среднеквадратическое отклонение случайной величины:

Рис. 6.2.1. Детальная блок-схема блока 2

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

x01, x02, x03: начальные значения, необходимые для получения последовательности случайных чисел, равномерно распределенных на [0,1];

N, N1, N2: общее количество заявок, количество заявок, получивших отказ и количество обслуженных заявок соответственно;

tn: системное время;

tmg: процедура генерации момента времени прихода очередной заявки;

Tosv: момент времени освобождения канала;

Twork: временя работы канала.

Блок 3

Блок-схема блока 3 приведена на рис. 6.3.1.

Рис. 6.3.1. Детальная блок-схема блока 3

Предназначен для проверки окончания процесса моделирования, который прекращается когда системное время tn становится больше либо равным времени рабочего дня T*3600 (в секундах.

Блок 4

Блок-схема блока 4 приведена на рис. 6.4.1.

В блоке 4 производится моделирование работы канала.

Проверка состояния канала осуществляется внутри цикла блока 4.1. Если канал свободен (zk=0), то осуществляется переход к блоку 5 укрупненного моделирующего алгоритма.

Если состояние канала равно 1, т. е. в канале есть заявка, то необходимо проверить, закончилось ли время обслуживания этой заявки. Переходим к блоку 4.2.

Рис. 6.4.1. Детальная блок-схема блока 4

Если условие не выполняется, то заявка в этом канале еще не обслужена, поэтому переходим к блоку 5 укрупненного моделирующего алгоритма.

Если условие T (k)<=tn выполняется, то обслуживание заявки в этом канале закончено и мы переходим к блоку 4.3, в котором счетчик обслуженных заявок увеличивается на 1, и состояние канала становится равным 0 (канал свободен) и осуществляется переход к блоку 5 укрупненного моделирующего алгоритма.

Блок 5

Блок-схема блока 5 приведена на рис. 6.5.1.

В блоке 5 осуществляется взаимодействие источников с и каналом.

Рис. 6.5.1. Детальная блок-схема блока 5

В блоке 5.1 выясняется, поступила ли из источников за очередной интервал t заявка. Для этого сравнивается момент поступления очередной заявки tm с моментом системного времени tn.

Если tm>tn, то, значит, за очередной интервал t заявка из источника не поступала, поэтому осуществляется переход к блоку 6 укрупненного моделирующего алгоритма, в котором происходит переход к следующему моменту системного времени tn.

Если tm<=tn, то переходим к блоку 5.2, в котором проверяется состояние канала. Если канал занят (zk=1), то заявка получает отказ, при этом в блоке 5.5 счетчик отказов увеличивается на 1 и осуществляется переход к блоку 5.12, в котором генерируется момент времени прихода следующей заявки. После чего осуществляется переход к блоку 6 укрупненного моделирующего алгоритма.

Если же канал свободен (zk=0), то в блоке 5.3 осуществляется обращение к стандартной подпрограмме генерации времени обслуживания заявки и момент времени освобождения канала, которое запоминается в переменной Tosv. Затем осуществляется переход к блоку 5.4, в котором состояние канала становится равным 1 (канал занят). Далее переходим к блоку 5.6, в котором генерируется момент времени прихода следующей заявки. После чего осуществляется переход к блоку 6 укрупненного моделирующего алгоритма.

Блок 6

Блок-схема блока 6 приведена на рис. 6.6.1.

Рис. 6.6.1. Детальная блок-схема блока 6

В блоке 6.1 осуществляется переход к следующему моменту системного времени tn.

Блок 7

Блок-схема блока 7 приведена на рис. 6.7.1.

Рис. 6.7.1. Детальная блок-схема блока 7

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

Блок 8

Блок-схема блока 8 приведена на рис. 6.8.1.

Рис. 6.8.1. Детальная блок-схема блока 8

Предназначен для сохранения результатов моделирования в файл «results.txt».

7. Математическая модель

Определим необходимые переменные и уравнения математической модели. В нашем случае это будут:

— время набора и выполнения одного задания на ЭВМ;

— число выполненных заданий;

— число заданий, получивших отказ.

Уравнения модели:

где — вероятность отказа в обслуживании;

— коэффициент загрузки ЭВМ;

— суммарное время занятости ЭВМ;

T — общее имитируемое время работы СТО.

8. Описание машинной программы решения задачи

Листинг машинной программы решения задачи приводится в приложении 1. Программа написана на языке программирования высокого уровня Паскаль. Для нормальной работы программы необходима операционная система MS-DOS 6.22, «Windows 95» и выше, и около 50 Кб свободного пространства на жестком диске.

Все результаты моделирования сохраняются в текстовый файл на диск.

Назначение переменных:

T: переменная для хранения времени моделирования;

Twork: время работы ЭВМ;

zk: состояние канала;

N: общее количество заявок;

N1: количество заявок, получивших отказ;

N2: количество обслуженных заявок;

tm: момент времени прихода очередной заявки;

tn: момент системного времени;

dt: шаг моделирования;

tau: длительность обслуживания заявки;

Mtm, Mtau, Minp: математическое ожидание для tm, tau и времени набора задания соответственно (используется в нормальном законе распределения);

Stm, Stau, Sinp: среднеквадратическое отклонение для tm, tau и времени набора задания соответственно (используется в нормальном законе распределения);

x01, x02, x03: значения случайных величин, используемые для получения последовательностей псевдослучайных чисел, равномерно распределенных на [0,1], методом серединных квадратов.

Процедуры и функции:

GetRandom: функция возвращает значение случайной величины, равномерно распределенной на [0,1];

GetSum6: функция возвращает сумму шести случайных величин, равномерно распределенных на [0,1] (для нормального закона распределения);

tmg: функция генерирует момент времени прихода очередной заявки;

taug: функция генерирует продолжительность обслуживания заявки в канале;

inpg: функция генерирует продолжительность набора задания;

Work: процедура запоминает в переменной Tosv момент окончания обслуживания заявки в канале, а также подсчитывает общее время работы канала.

Все остальные переменные, процедуры и функции являются служебными и необходимы для нормального функционирования программы.

9. Результаты моделирования

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

Результаты моделированмя:

Вероятность отказа в приеме задания: 0.0

Коэффициент загрузки ЭВМ: 0.8124

Ok

Анализируя полученные данные, можно сделать следующие выводы:

вероятность отказа в обслуживании равна 0;

коэффициент загрузки ЭВМ равен 81%.

Другими словами, все проектировщики имеют возможность расчета всех своих задач на ЭВМ, причем сама ЭВМ загружена на 80% своей мощности.

10. Сравнение результатов имитационного моделирования и аналитического расчета характеристик

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

(10.1)

где

— интенсивность потока заявок;

— интенсивность потока обслуживания;

— относительная пропускная способность канала.

Для исходных данных, указанных в условии задачи:

тогда, подставляя в (10.1) найдем:

Таким образом, вероятность отказа в ремонте, полученная аналитическим методом равна 0,18 939.

Вероятность отказа в ремонте, полученная в результате имитационного моделирования равна 0.

Заключение

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

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

Рекомендации по совершенствованию алгоритма и программы моделирования:

повышение гибкости алгоритма;

увеличение удобства работы пользователя;

введение

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

сохранение в файл состояния системы в каждый момент системного времени;

выгрузка текущего состояния системы в файл с возможностью дальнейшей загрузки и продолжения процесса моделирования.

Советов Б.Я., Яковлев С. А. Моделирование систем. — М.:ВШ, 1995.

Советов Б.Я., Яковлев С. А. Моделирование систем. Практикум. — М.:ВШ, 1999.

Вентцель Е. С. Исследование операций. — М.:Сов. Радио, 1972.

Приложение 1

Листинг программы.

program SAPR;

uses Crt;

const

CntTerm = 5;

var

T, ipz, dipz, tiz, dtiz, tvz, dtvz: Integer;

zk, N, N1, N2, err: Integer;

xbase, xnext, x01, x02, x03: Real;

Twork, Tosv, tm, tn, dt, tau: Real;

A, B, Mtm, Mtau, Minp, Stm, Stau, Sinp: Real;

S: String;

ResFile: text;

{генерация СВ, равномерно распределенной на [0,1]}

function GetRandom (var x: Real): Real;

begin

xnext:= x*x;

Str (xnext:8:6, s); Val (Copy (s, 5,4), xbase, err);

x:= xbase/10 000;

GetRandom:= x;

end;

{генерация СВ, имеющей нормальный закон распределения}

function GetSum6 (var x0: Real): Real;

var k: Integer;

Sumk: Real;

begin

Sumk:= 0;

for k:= 1 to 6 do

Sumk:= Sumk + GetRandom (x0);

GetSum6:= Sumk;

end;

{генерация момента времени появления заявки}

function tmg: Real;

begin

tmg:= Stm*Sqrt (2)*(GetSum6 (x01) — 3)+Mtm;

N:= N + 1;

end;

{генерация времени набора задания}

function inpg: Real;

begin

inpg:= Sinp*Sqrt (2)*(GetSum6 (x03) — 3)+Minp;

end;

{генерация времени выполнения задания}

function taug: Real;

begin

taug:= Stau*Sqrt (2)*(GetSum6 (x02) — 3)+Mtau;

end;

procedure Work;

begin

tau:= inpg + taug;

Tosv:= tm + tau;

Twork:= Twork + tau;

end;

procedure DoIt;

var k: Integer;

begin

A:= Round (3600/(ipz + dipz)); B:= Round (3600/(ipz — dipz));

Mtm:= (A + B)/2; Stm:= Sqrt (B — Mtm);

dt:= A;

A:= tiz — dtiz; B:= tiz + dtiz;

Mtau:= (A + B)/2; Stau:= Sqrt (B — Mtau);

A:= tvz — dtvz; B:= tvz + dtvz;

Minp:= (A + B)/2; Sinp:= Sqrt (B — Minp);

x01:= 0.8442; x02:= 0.3618; x03:= 0.2436;

N:= 0; N2:= 0; N1:= 0; zk:= 0;

tn:= 0; tm:= tmg; Tosv:= 0; Twork:= 0;

while tn < T*3600 do

begin

{работа канала}

if zk = 1 then

begin

if Tosv <= tn then

begin

N2:= N2 + 1;

zk:= 0;

end;

end;

{взаимодействие источников с каналом}

if tm <= tn then

begin

if zk = 0 then

begin

Work;

zk:= 1;

end

else N1:= N1 + 1;

tm:= tm + tmg;

end;

tn:= tn + dt;

end;

end;

begin

WriteLn;

Write ('Время работы САПР (часов): '); ReadLn (T);

Write ('Интенсивность поступления заданий с каждого терминала (зад/час): '); ReadLn (ipz, dipz);

ipz:= ipz * CntTerm; dipz:= dipz * CntTerm;

Write ('Время набора задания (сек): '); ReadLn (tiz, dtiz);

Write ('Время выполнения задания (сек): '); ReadLn (tvz, dtvz);

DoIt;

Assign (ResFile, 'results.txt');

Rewrite (ResFile);

WriteLn (ResFile, 'Результаты моделированмя:');

WriteLn (ResFile);

Str ((N1/N):6:4, S);

WriteLn (ResFile, 'Вероятность отказа в приеме задания: '+S);

Str ((Twork/(T*3600)):6:4, S);

WriteLn (ResFile, 'Коэффициент загрузки ЭВМ: '+S);

WriteLn (ResFile, 'Ok');

Close (ResFile);

WriteLn ('Ok');

end.