База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

Оглавление

1.  Задание

2.  Описание процесса

3.  Построение метамодели «асинхронный процесс»

4.  Свойства процесса

4.1 Эффективность

4.2 Управляемость

4.3 Простота

5.  Операции над процессом

5.1 Репозиция

5.2 Редукция

5.3 Композиция

6.  Построение сети Петри

7.  Анализ свойств мест с. Петри на ограниченность и безопасность

8.  Анализ свойств переходов с. Петри на живость и устойчивость

9.  Заключение

Список использованной литературы

1. Задание

Целью расчетно-графического задания является получение опыта в конструировании метамодели «асинхронный процесс» и модели «сеть Петри» и в исследовании их свойств.

Предлагается выполнить следующее:

1.  Выделить компоненты рассматриваемого процесса.

2.  Сформировать множество ситуаций рассматриваемого процесса.

3.  Описать модель «асинхронный процесс».

4.  Определить траектории выполнения процесса и классы эквивалентности ситуаций и сделать вывод о свойствах рассматриваемого процесса (эффективность, управляемость, простота).

5.  Определить множество дополнительных ситуаций для возобновления процесса (если они есть) и построить полную или частичную репозицию процесса.

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

7.  Определить два подпроцесса на базе исследуемого, выбрать удобный вид композиции (последовательную или параллельную) и построить ее.

8.  Описать составляющие модели «асинхронный процесс», используя понятия модели «сеть Петри».

9.  Провести анализ свойств мест сети Петри на ограниченность и безопасность.

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

2. Описание процесса

асинхронный репозиция редукция сеть пери

В качестве вычислительного процесса был выбран процесс со следующим названием: «Запись информации на магнитный носитель». Кратко опишем его суть.

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

Процесс записи опишем следующей последовательностью команд и операций: магнитный диск вставлен в дисковод и готов для записи (часть магнитной поверхности уже может содержать какую-либо информацию). Дисковод состоит из множества механических деталей и механизмов, управление которыми осуществляет микроконтроллер – устройство, которое получает команды от центрального процессора и выполняет их.

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

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

После того, как данные записаны, производится контроль записи (верификация или CRC (проверка контрольной суммы)). Такая операция необходима для проверки правильности записанной информации. В случае ошибки записи, специальный регистр (Data Error Register) устанавливается в единицу и запись прекращается. Головки при этом отводятся от поверхности.

Успешная запись всех секторов завершается сбрасыванием в 0 регистра ошибок данных. Регистр, содержащий количество секторов для записи так же обнуляется. Головки отводятся от поверхности магнитного носителя и контроллер выдает сигнал по шине данных процессору об окончании операции ввода/вывода.

3. Построение метамодели «асинхронный процесс»

Прежде всего, выделим компоненты рассматриваемого процесса:

1.  N	2.  Обозначение	3.  Описание
4.  1	5.  K	6.  Микроконтроллер дисковода. Работает (K+)
7.  2	8.  S	9.  Свободное место. Есть в наличии (S+) или нет (S-)
10.  3	11.  E	12.  Регистр, сигнализирующий ошибку. Произошла ошибка (E+)
13.  4	14.  P	15.  Механизм позиционирования головки записи. Задействован (P+)
16.  5	17.  W	18.  Головка записи. Записывает информацию (W+)
19.  6	20.  C	21.  Блок контроля правильности записи (crc check). Проводится проверка (C+)
22.  7	23.  F	24.  Fat таблица. Обновление fat таблицы после записи (F+)

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

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

25.  Ситуация	26.  K	27.  S	28.  E	29.  P	30.  W	31.  C	32.  F	33.  Описание
34.  S1	35.  1	36.  0	37.  0	38.  0	39.  0	40.  0	41.  0	42.  Контроллер активен и ожидает команду от процессора на запись
43.  S2	44.  1	45.  1	46.  0	47.  0	48.  0	49.  0	50.  0	51.  Есть свободное место для записи
52.  S3	53.  1	54.  0	55.  1	56.  0	57.  0	58.  0	59.  0	60.  Места нет. Регистр ошибки устанавливается в код ошибки.
61.  S4	62.  1	63.  1	64.  0	65.  1	66.  0	67.  0	68.  0	69.  Головка подводится на нужный сектор
70.  S5	71.  1	72.  1	73.  0	74.  0	75.  1	76.  0	77.  0	78.  Запись информации в сектор
79.  S6	80.  1	81.  1	82.  0	83.  0	84.  0	85.  1	86.  0	87.  Проверка валидности записанных данных
88.  S7	89.  1	90.  1	91.  0	92.  1	93.  0	94.  0	95.  1	96.  Успешная запись, головки отводятся от поверхности, обновляется таблица fat.
97.  S8	98.  1	99.  1	100.1	101.0	102.0	103.0	104.0	105.Некорректная запись информации.

Назовем асинхронным процессом четверку <S,F,I,R>, в которой: S - непустое множество ситуаций;

F - отношение непосредственного следования ситуаций, определенное на множестве S´S (FÌ S´S);

I - множество инициаторов (IÌS), т.е. таких ситуаций из S, для которых если iFS_k, iÎI, S_kÎI, то из S_kFS_l следует, что S_lÏI;

R - множество результантов (RÌS), т.е. таких ситуаций из S, для которых, если rFS, rÎR, то SÎR.

Согласно этому определению, имеем для рассматриваемого процесса:

P=<S,F,I,R>

S={ }

I={},

Где -инициирует запись

-инициирует проверку записанных данных

R={ }, где

-нет места для записи

-успешная запись

-ошибка записи информации

Выпишем все возможные траектории процесса:

 - не хватает места для записи

 - успешный процесс записи

 - ошибка записи

 - неудачная проверка записанных данных

 - удачная проверка записанных данных

4. Свойства процесса

Рассмотрим свойства асинхронного процесса.

 

4.1 Эффективность

Пусть задан АП, у которого :

1.  для любого sÎS \ R найдется rÎR такой, что sMr;

2.  для любого sÎS \ I найдется iÎI такой, что iMs;

3.  не найдется ситуации S_i и S_j таких, что (S_iÏR)&(S_jÏR)&(S_iMS_j)&(S_jMS_i).

АП, удовлетворяющий свойствам 1 - 3, будет называться эффективным , т.е. из инициаторов эффективного процесса все траектории ведут в результанты (свойство 1 и 3), и каждая из траекторий, приводящих к результанту, начинается в каком-либо инициаторе (св. 1 и 2). Эффективность АП оставляет место недетерминированности, т.е. возможно, что из некоторого инициатора процесс попадает в разные результанты, но он не содержит ориентированных циклов вне ситуаций, принадлежащих I и R.

Вывод: данный процесс не является эффективным (не выполняется свойство 3), так как процесс содержит цикл  вне ситуаций, принадлежащих I и R.

4.2 Управляемость

 

Если в эффективном АП каждая допустимая последовательность классов ведет из начального класса в один и только один заключительный класс, то такой процесс называется управляемым. Таким образом, в управляемом АП вводится ограничение на степень недетерминизма: все траектории из любого инициатора ведут в один заключительный класс.

Для определения того факта, является процесс управляемым или нет, разобьем множество ситуаций S на классы эквивалентности.

 ,

где класс  - начальный, а классы  - заключительные.

Вывод: данный процесс не является управляемым, так как из начального класса  можно попасть в заключительный класс , а также в класс . То есть не выполняется условие детерминированности.

4.3 Простота

 

Пусть в эффективном АП:

1.  для любых iÎI и sÎS из iFs Þ sÏI;

2.  для любых sÎS и rÎR из sFr Þ sÏR

(т.е. из инициатора (результанта) нельзя попасть в другой инициатор (результант) т.е. каждая траектория содержит в точности по одному инициатору и результанту). АП, удовлетворяющий свойствам 1 и 2 будет называться простым.

Вывод: процесс не является простым. Траектории

содержат по 2 инициатора (отмечены подчеркиванием)

5. Операции над процессами

 

5.1 Репозиция

Репозицией АП задается механизм перехода от результанта к инициаторам

Репозицией АП P = <S,F,I,R> назовем эффективный АП P' = <S', F', I', R'>, такой, что S' Í IÈRÈS^D, I' Í R, R' Í I.

Ситуации S' репозиции могут содержать лишь те ситуации из исходного процесса, которые являются лишь инициаторами или результантами, и, кроме того, некоторые дополнительные ситуации из S^D, отсутствующие в описании исходного АП.

Отношение F' задает траектории переходов от элементов из I' Í R к элементам R' Í I, возможно через дополнительные ситуации из S^D.Если I' = R, R' = I, то репозицию назовем полной. Если F' = Æ , то репозиция не существует, в остальных случаях она называется частичной.

Для рассматриваемого процесса имеем:

P' = <S', F', I', R'>

S' Í I È R È S^D = {  }S^D = Æ

I'={ }R'={  }

F':(повторить процесс записи сначала)

(повторить проверку записи данных)

Траектории переходов, которые задает отношение F' показаны на рисунке пунктирной стрелкой.

Вывод: таким образом, построена частичная репозиция асинхронного процесса, суть которой – получение механизма его возобновления. Семантически репозиция означает повтор операции записи (при успешной записи) и повтор операции проверки записанных данных (в случае возникновения ошибки записи).

5.2 Редукция

 

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

Пусть задан неприведенный АП Р = <S,F,I,R>, ситуации которого структурированы по 2-му способу. Образуем р-блочное разбиение множества S процесса Р, в ситуациях каждого блока которого входная компонента принимает фиксированное значение x_j, 1jp.

Выберем r<p различных значений входной компоненты (составляющих множество X*Ì X). Ситуации, входящие в те блоки разбиения, которые соответствуют выбранным значениям входной компоненты составляют подмножество S*, S*Ì S.

Для каждого инициатора s_iÎI постоим множество ситуаций S(s_i), встречающихся на траекториях процесса Р, ведущих из указанного инициатора.

Образуем множество S(X*), как объединение тех множеств S(s_i), для которых справедливо

S(s_i)S*, т.е. S(X*) =

Построим также F(X*) = F Ç (S(X*)´S(X*)), I(X*) = I Ç S(X*), R(X*) = R Ç S(X*).

Назовем процесс P(X*) = <S(X*), F(X*), I(X*), R(X*)> редукцией неприведенного процесса P = <S,F,I,R> по выбранному множеству Х* значений входной компоненты.

Для рассматриваемого процесса имеем:

106.Ситуация	107.K	108.S	109.E	110.P	111.W	112.C	113.F
114.S1	115.1	116.0	117.0	118.0	119.0	120.0	121.0
122.S2	123.1	124.1	125.0	126.0	127.0	128.0	129.0
130.S3	131.1	132.0	133.1	134.0	135.0	136.0	137.0
138.S4	139.1	140.1	141.0	142.1	143.0	144.0	145.0
146.S5	147.1	148.1	149.0	150.0	151.1	152.0	153.0
154.S6	155.1	156.1	157.0	158.0	159.0	160.1	161.0
162.S7	163.1	164.1	165.0	166.1	167.0	168.0	169.1
170.S8	171.1	172.1	173.1	174.0	175.0	176.0	177.0

S={ }

Выберем в качестве значений входной компоненты первые три элемента вектора.

Выпишем множество X={ 100, 110, 101, 111 }

Редукцию сделаем по следующему множеству X*={100, 101}, то есть семантически рассмотрим ситуацию, когда нет свободного места для записи.

Тогда S* = { }.

Рассмотрим траектории процесса:

 (подходит, так как ситуации принадлежат S*)

 (не подходит, т.к.  не принадлежат S*)

 (не подходит)

 (не подходит)

 (не подходит)

Образуем множество S(X*)={ }, I(X*)={},R(X*)= {}

F(X*):

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

5.3 Композиция

Обозначим исходный процесс как P2. Для него имеем:

S2={  }I2={}R2={ }

Рассмотрим новый процесс P1, состоящий из следующих компонент:

178.N	179.Обозначение	180.Описание
181.1	182.K	183.Контроллер дисковода
184.2	185.P	186.Дисковод работает. Есть электропитание (P+)
187.3	188.D	189.Диск вставлен в дисковод (D+)

190.Ситуация	191.K	192.PW	193.D
194.S1	195.1	196.1	197.0
198.S2	199.1	200.1	201.1

Для процесса P1 имеем: S1={  }I1={  }R1={  }

Построим последовательную композицию процессов P1 и P2.

Х*={1}

Построим редукцию процесса P2 по X*.

S2*={ }

Траектории:

(подходит)

(подходит)

(подходит)

(подходит)

(подходит)

Следовательно: S2 (X*) = { }  I2 (X*) = { } R2 (X*)= {  }

Далее построим редукцию процесса P1 по X*.

S1*={  }

Траектории:

Следовательно: S1(X*) = { } I1 (X*) = {  } R1 (X*)= {  }

Теперь построим процесс P3.

Для процесса P3 имеем: S3={  I3={  }R3={  }

202.Ситуация	203.K	204.S	205.E	206.P	207.W	208.C	209.F	210.PW	211.D
212.S1	213.1	214.0	215.0	216.0	217.0	218.0	219.0	220.1	221.0
222.S2	223.1	224.0	225.0	226.0	227.0	228.0	229.0	230.1	231.1
232.S3	233.1	234.0	235.0	236.0	237.0	238.0	239.0	240.1	241.1
242.S4	243.1	244.1	245.0	246.0	247.0	248.0	249.0	250.1	251.1
252.S5	253.1	254.0	255.1	256.0	257.0	258.0	259.0	260.1	261.1
262.S6	263.1	264.1	265.0	266.1	267.0	268.0	269.0	270.1	271.1
272.S7	273.1	274.1	275.0	276.0	277.1	278.0	279.0	280.1	281.1
282.S8	283.1	284.1	285.0	286.0	287.0	288.1	289.0	290.1	291.1
292.S9	293.1	294.1	295.0	296.1	297.0	298.0	299.1	300.1	301.1
302.S10	303.1	304.1	305.1	306.0	307.0	308.0	309.0	310.1	311.1

Вывод: таким образом построена последовательная композиция процессов P1 и P2 . Семантически ситуации процесса P1 предшествуют ситуациям процесса P2. Их суть – процесс подготовки носителя к записи информации.

6. Построение сети Петри

Сетью Петри называется пятерка N = <P, T, M₀, H, F>, где

Р = {p₁,...,p_n} - конечное непустое множество условий

T = {t₁,...,t_m} - конечное непустое множество событий

 - функция инцидентности

М₀ : Р ® {0, 1, 2,...} - начальная разметка.

Сеть Петри есть модельная интерпретация АП.Ситуациями в сети является начальная разметка М₀ и все разметки, достижимые от М₀, т.е. МÎR(N). Отношение F для любой возможной разметки М задает все разметки, которые могут непосредственно следовать за М. Очевидно, что на множестве R(N) можно определить отношение эквивалентности разметок и задать отношение F непосредственного следования для классов эквивалентности.

Построим сеть Петри для следующей траектории рассматриваемого процесса:

, что семантически соответствует успешному процессу записи данных.

Выпишем значения компонент. Компонента E во всех ситуациях равна 0, поэтому эта компонента не учитывается при построении сети Петри.

312.	313.K	314.S	315.W	316.P	317.C	318.F
319.	320.1	321.0	322.0	323.0	324.0	325.0
326.	327.1	328.1	329.0	330.0	331.0	332.0
333.	334.1	335.1	336.1	337.0	338.0	339.0
340.	341.1	342.1	343.0	344.1	345.0	346.0
347.	348.1	349.1	350.0	351.0	352.1	353.0
354.	355.1	356.1	357.0	358.0	359.0	360.1

Формальное описание:

N=<>

 

7. Анализ свойств мест с. Петри на ограниченность и безопасность

Место (условие) р в сети N = (P,T,F,W,M₀) называется ограниченным, если существует число n такое, что для любой достижимой в сети разметки М справедливо неравенство М(р)  n. Сеть называется ограниченной, если любое ее место ограниченно.

Множество достижимых разметок R(N) конечно, если и только если N - ограниченная сеть.

Место р называется безопасным, если для любого МÎ R(N): М(р)  1, соответственно сеть безопасна, если все ее места безопасны. Любая достижимая в безопасной сети разметка представляет собой вектор из 0 в 1.

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

Изобразим граф разметок. (см. рис.).

Вывод:

Все места в сети ограничены, так как для любого места p: M(p)£n (n=1). Следовательно сеть ограниченная.

Все места являются безопасными, так как для любого места p: M(p) £1. Следовательно сеть безопасная (это значит, что все разметки состоят из 0-ей и 1-иц).

8. Анализ свойств переходов с. Петри на живость и устойчивость

Переход t в сети Петри N = (P,T,F,W,M₀) называется потенциально живым при разметке МÎR(N), если существует M’ÎR(N,M) : M’³ F(p,t), т.е. существует достижимая от М разметка М’, при которой переход t может работать.

Если М = М₀, то t называется потенциально живым в сети N.

Переход t – мертвый при М, если он не является потенциально живым при М. Переход t - мертвый, если он мертвый при любой достижимой в сети разметке.

Переход t в сети Петри называется живым, если для любого MÎR(N) cсуществует M’Î R(N,M) : M ³ F(p,t), т.е. он потенциально живой при любой достижимой в сети разметке. Сеть называется живой, если все ее переходы живы.

Переход t называется потенциально мертвым, если существует MÎR(N), такая, что при любой разметке M’ÎR(N,M) переход t не может работать.

Переход t называется устойчивым в сети N, если t’ÎT \ {t}, MÎR(N) : (M ³ F(p,t)) Ç (M ³ F(p,t’))Þ(M ³ (F(p,t)+F(p,t’))), т.е. если переход t может сработать, то никакой другой переход не может сработав, лишить его этой возможности.

Сеть N устойчива, если все ее переходы устойчивы.

Вывод:

Все переходы сети потенциально живы (то есть существует разметка, достижимая от текущей разметки, при которой переход t может сработать), следовательно вся сеть N является живой.

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

9. Заключение

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

Список использованной литературы

1. Конспект лекций по ТВП;

2. А.В. Гордеев, А.Ю. Молчанов, Системное программное обеспечение.

Оглавление 1. Задание 2. Описание процесса 3. Построение метамодели «асинхронный процесс» 4. Свойства процесса 4.1 Эффективность 4.2 Управляемость 4.3 Простота 5. Операции над процессом 5.1 Репозиция 5

 

• 14:21 05 Июля 2016
  Российско-китайский медуниверситет откроет магистерскую программу по TCM
• 01:21 05 Июля 2016
  На форуме МГУ Россия и Китай обсудят научно-образовательное сотрудничество
• 11:00 04 Июля 2016
  Реморенко: "ЕГЭ-туризм" в России сходит на нет
• 10:52 04 Июля 2016
  Летняя российско-австрийская школа откроется в Москве
• 15:31 01 Июля 2016
  В СПбГУ могут воссоздать географический факультет

Заказать уникальную работу