рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ - раздел Философия, Государственный Комитет Российской Федерации По Рыболовству ...

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПО РЫБОЛОВСТВУ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

 

 

И.М.Лазарева

 

ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

Допущено Ученым советом МГТУ в качестве учебного пособия для студентов по дисциплине «Теория вычислительных процессов» для специальности 230105.65 «Программное обеспечение вычислительной техники и автоматизированных систем»

 

Мурманск


УДК 004 (075.8)

ББК 32.97 я 73

Л 17

 

Лазарева, И.М. Теория вычислительных процессов: учеб. пособие по дисциплине «Теория вычислительных процессов» для специальности 230105.65 «Программное обеспечение вычислительной техники и автоматизированных систем» / И.М.Лазарева. – Мурманск: Изд-во МГТУ, 2008. – 145 с.

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

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

The theory forming the foundation necessary for the correct problem setting and solving in the field of information science is considered in the manual. The base data on the models the most frequently applied for presenting and analyzing the processes occurring in computer systems are represented. The fundamentals of theoretical programming including the matters of program verification are stated.

It is intended for university students of the specialized field 230105.65 “Software for computers and computer-based systems”.


ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ. 5

РАЗДЕЛ 1. Введение в теорию асинхронных процессов. 7

Тема 1.1. Понятие вычислительного процесса. Основные свойства. 7

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

Тема 1.2. Операции над асинхронными процессами. 20

Репозиция процесса. 25

Редукция процесса. 31

Композиция процессов. 37

РАЗДЕЛ 2. Модельная интерпретация асинхронного процесса. 44

Тема 2.1. Сетевая объектная модель – сеть Петри. 45

Модельная интерпретация асинхронного процесса с помощью сети Петри 52

Тема 2.2. Анализ сетей Петри. 54

Свойства сетей Петри. 54

Дерево достижимости. 58

Матричные уравнения. 62

РАЗДЕЛ 3. Протоколы и интерфейсы.. 63

Тема 3.1. Согласование асинхронных процессов и организация интерфейсов 63

Тема 3.2. Протокол согласования. Согласующий асинхронный процесс 67

Тема 4.1. Механизмы взаимодействия процессов. 74

Тема 4.2. Решение проблемы взаимного исключения. 79

Блокировка памяти. 82

Операция “Проверка и установка”. 86

Семафорные операции. 90

Тема 4.2. Проблемы тупиков и методы борьбы с ними. 96

Понятие тупика. Модель Холта. 96

Методы борьбы с тупиками. 100

Задача об обедающих мудрецах. 109

РАЗДЕЛ 5. Введение в теорию схем программ. 111

Стандартные схемы программ. 116

РАЗДЕЛ 6. Методы формальной спецификации и верификации программ 120

Тема 6.1. Основные принципы верификации программ.. 120

Тема 6.2. Доказательство правильности программ.. 125

Метод индуктивных утверждений. 127

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА.. 137

 

 


 

ВВЕДЕНИЕ

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

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

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

Далее эта модель исследуется, полученные для модели выводы и результаты сверяются с поведением реального процесса. Если полученные результаты сильно расходятся с наблюдаемыми фактами, модель следует либо уточнить, либо отвергнуть и строить совершенно новую. Целью математического моделирования является описание и объяснение (хотя бы на качественном уровне) поведения системы, предсказание ее поведения в будущем и, если возможно, управления процессом.

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

Для указанной метамодели может быть построена модельная интерпретация с помощью сети Петри. Основные положения теории сетей Петри рассматриваются в разделе 2 данного пособия.

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

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

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

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

Таким образом, в результате освоения данного курса студенты будут знать и уметь использовать:

- формальные модели вычислительных процессов и структур;

- основные классы моделей и методы решения задач анализа моделей;

- сетевые модели вычислительных процессов – сети Петри;

- методы управления процессами, протоколы взаимодействия объектов вычислительных структур;

- основные классы схем программ и программных механизмов.

 

РАЗДЕЛ 1. Введение в теорию асинхронных процессов

Тема 1.1. Понятие вычислительного процесса. Основные свойства

Работа таких устройств описывается с помощью дискретных переменных. Этот факт не исключает использования непрерывных переменных, но дискретные… Типичный пример системы с конечным числом состояний - управление обменом…

Примеры графического представления фрагментов асинхронных процессов

 

 

Рис.1.1 Рис.1.2

 

Асинхронный процесс может быть описан направленным графом, вершинами которого являются ситуации, а дуги представляют отношение непосредственного следования. На рис.1.1 представлен вариант, когда за s1 может непосредственно следовать s3.; на рис. 1.2 – вариант, когда s1 F s2, s2 F s3 . То есть изучение семантики процесса может показать, что из ситуации s1 в ситуацию s3 процесс попадает только через ситуацию s2 , хотя s1 является причиной и s2 , и s3 .

 

Введем новые термины и понятия.

Пусть имеется последовательность (возможно, бесконечная) ситуаций s(1)...s(i)s(i+1)..., где s(i) - элемент, стоящий в последовательности на i-ом месте. (Место именно в этой последовательности, а не в процессе, напр., s1,s2,s4,s5 , где si – обозначение ситуации в процессе, будет представлено в последовательности s1(1),s2(2),s4(3),s5(4)).

 

Определение 1.2. Для АП можно составить множество последовательностей ситуаций, в которых для любого места i , кроме последнего, справедливо s(i) F s(i+1) и таких, что ни одна из последовательностей не является частью другой.

Такие последовательности называются допустимыми.

 

Каждая допустимая последовательность ситуаций описывает возможный ход процесса смены ситуаций - траекторию АП и соответствует реализации АП.

Из этого следует, что можно построить отношение М, соответствующее отношению F , такое что, если для пары ситуаций si, sj существует траектория si в sj, то si М sj.

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

 

Пример: Рассмотрим АП Р= <S, F, I, R>,

Где S={s1,s2,s3,s4,s5,s6} множество ситуаций, для которых отношение F задается графом

Рис.1.3

Рассмотрим последовательности ситуаций s(1), s(2), s(3), s(4):

допустимые – недопустимые –
s1, s3, s4, s5 s2, s3, s4, s6 s2, s3, s4, s5 s1, s3, s4, s6 s3, s4, s6 s1, s3, s4
или  
допустимые – недопустимые –
s1, s3, s4, s5 s2, s3, s4, s5 s3, s4, s6 s1, s3, s4, s6 s1, s3, s4

 

Определение траектории как допустимой последовательности ситуаций осуществляется исходя из семантики процесса.

 

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

1) для любой sÎS R найдется rÎR такая, что s M r;

2) для любой sÎS I найдется iÎI такая, что i M s;

3) не найдется ситуаций si и sj таких, что (siÏR)&(sjÏR)&(si M sj)&(sj M si).

 

Определение 1.3. АП, удовлетворяющий свойствам 1) - 3), будет называться эффективным.

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

Эффективность АП оставляет место недетерминированности, т.е. возможно, что из некоторого инициатора процесс попадает в разные результанты.

Пример: Рассмотрим АП Р= <S, F, I, R>,

Где S={s1,s2,s3,s4,s5,s6} множество ситуаций, для которых отношение F задается графом

Рис.1.4

Если для этого АП

I = {s1, s4}, R = {s5},

то АП не является эффективным, т.к. не выполняется свойство 1).

Если

I = {s1}, R = {s2, s3, s5, s6},

то АП не является эффективным, т.к. не выполняется свойство 2).

Если

I = {s1, s4}, R = {s5, s6},

то АП не является эффективным, т.к. не выполняется свойство 3).

 

Заметим, что если

I={s1,s4}, R= {s3,s5,s6},

то не выполняется ограничение определения АП: s3 F s2, но s3ÎR, а s2ÏR.

 

Вариант эффективного АП: I={s1, s4}, R={s2,s3,s5,s6}. Конец примера.

 

Для некоторых подмножеств множества ситуаций S можно определить отношение Е:

1) для si, sjÎS имеет место отношение Е: si E sj, если si M sj и sj M si;

2) для любых sÎS: s E s.

Условие 1) обеспечивает симметричность и транзитивность отношения Е (транзитивность Е следует из транзитивности М), а 2) - рефлексивность Е, следовательно, Е - отношение эквивалентности.

 

Отношение Е позволяет построить разбиение =(S1,...,Sp) множества S на классы эквивалентности.

Для классов эквивалентности определим отношение F непосредственного следования классов.

Все допустимые последовательности классов эквивалентности, определенные отношением Е, конечны. В допустимых последовательностях классов можно выделить начальные и конечные элементы, которые будут называться начальными и заключительными классами эквивалентности.

На основании введенных понятий можно сформулировать следующие утверждения:

1. Если некоторая ситуация s является инициатором и sÎS(j), где S(j) - класс эквивалентности, стоящий на j-ом месте в некоторой допустимой последовательности, все ситуации классов S(1),...,S(j) в этой последовательности является инициатором.

2. Если некоторая ситуация s является результантом и sÎS(j), то все ситуации из классов S(j),S(j+1),...,S(q), где S(q) - заключительный класс, являются результантами.

3. Для эффективного АП любой начальный класс состоит только из инициаторов, а любой заключительный класс только из результантов.

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

 

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

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

 

Пример: Рассмотрим АП с множеством ситуаций S={s1,s2,...,s10} и отношением F, заданным на рисунке 1.5:

 

Рис.1.5

 

Рис.1.6

 

Разбиение АП на классы эквивалентных ситуаций. На рисунке 1.6 показано отношение F для классов эквивалентности множества ситуаций этого АП.

 

Если I={s1,s2,s3,s4}, R={s7,s8,s9,s10}, легко убедиться, что этот процесс является управляемым. Если отношение F дополнить парой s2 F s4, то полученный АП становится неуправляемым (но остается эффективным).

 

Введем понятия, которые окажутся полезными при рассмотрении некоторых АП.

 

Определение 1.5. Если ситуации si и sk некоторого АП связаны отношением siМsk (si Fn sk), то фрагмент процесса, содержащий все части траекторий, ведущие из si в sk , назовем переходом si - sk.

 

В дальнейшем также будет использоваться следующий класс АП.

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

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

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

(то есть каждая траектория содержит в точности по одному инициатору и результанту).

 

Определение 1.6. АП, удовлетворяющий свойствам 1),2) будет называться простым.

 

Определение 1.7. Протоколом простого АП будет называться отношение

Q Í I´R

Протокол простого АП можно рассматривать как простой АП, в котором за каждым инициатором непосредственно следует результант. Поэтому в протоколе простого АП множество ситуаций состоит лишь из инициаторов и результантов:

S = IÈR

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

Протокол является удобной формой "вход-выходного" описания АП.

 

Тема 1.2. Операции над асинхронными процессами

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

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

1 способ.

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

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

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

Пример: Рассмотрим процесс печати фрагмента текста с помощью лазерного принтера.

Описание принципа работы лазерного принтера.

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

Лазер, управляемый микроконтроллером, генерирует тонкий световой луч, отражающийся от вращающегося зеркала. Этот луч, приходя на барабан, изменяет его электрический заряд в точке прикосновения. Таким образом, на барабане возникает скрытая копия изображения.

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

Бумага втягивается из подающего лотка и с помощью системы валиков перемещается к барабану. Перед самым барабаном бумаге сообщается статический заряд. Затем бумага соприкасается с барабаном и притягивает, благодаря своему заряду, частички тонера от барабана.

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

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

1. М – память:

+ содержит задание на печать;

- свободна.

2. P – бумага для печати:

+ имеется;

- отсутствует.

3. C – коронирующий провод:

+ работает;

- ожидает.

4. L – лазер:

+ работает;

- ожидает.

5. B – барабан:

+ заряжен;

- очищен.

6. T- тонер:

+ нанесен;

- отсутствует.

7. V – система валиков для подачи бумаги:

+ работает;

- ожидает.

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

1. Загрузка данных для печати в память принтера:

M+ P- C- L- B- T- V-

2. Подача бумаги:

M+ P+ C- L- B- T- V+

3. Отсутствие бумаги:

M+ P- C- L- B- T- V+

4. Коронирующий провод распределяет электрический заряд на некоторый сектор барабана:

M+ P+ C+ L- B+ T- V-

5. На этом же секторе лазер изменяет электрический заряд в точке прикосновения:

M+ P+ C- L+ B+ T- V-

6. На места, обработанные лазером, наносится тонер:

M+ P+ C- L- B+ T+ V-

7. Перенос изображения на бумагу:

M+ P+ C- L- B+ T- V+

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

S1 = (1,0,0,0,0,0,0)

S2 = (1,1,0,0,0,0,1)

S3 = (1,0,0,0,0,0,1)

S4 = (1,1,1,0,1,0,0)

S5 = (1,1,0,1,1,0,0)

S6 = (1,1,0,0,1,1,0)

S7 = (1,1,0,0,1,0,1)

Граф отношения непосредственного следования:

 
 

 


Рис1.7

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

· ситуации-инициаторы:

S1 = (1,0,0,0,0,0,0) - загрузка данных для печати в память принтера;

S2 = (1,1,0,0,0,0,1) - подача бумаги;

· ситуации-результанты:

S3 = (1,0,0,0,0,0,1) - отсутствие бумаги;

S7 = (1,1,0,0,1,0,1) - перенос изображения на бумагу.

Таким образом, можно определить асинхронный процесс, моделирующий процесс печати с помощью лазерного принтера, как

P=<S, F, I, R>, где S = {S1, S2, S3, S4, S5, S6, S7},

F = {(S1, S2), (S1, S3), (S2, S4), (S4, S5), (S5, S6), (S6, S7)},

I = { S1, S2 },

R = { S3, S7 }.

2 способ.

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

При выделении как входной, так и выходной компоненты ситуация Si представима тройкой:

Si = (xj, yk, zl),

где xj - значение входной компоненты, xjÎX, 1≤ j≤ p,

yk - значение выходной компоненты, ykÎY, 1≤ k≤ q,

zl - значение компоненты, не являющихся входной или выходной,

zlÎZ, 1≤ L≤ n.

Пример: структурируем ситуации описанной выше модели работы лазерного принтера по второму способу:

х = (М Р), где М – память,P – бумага для печати;

y = (Т V), где T– тонер, V– система валиков для подачи бумаги;

z = (C L B), где C – коронирующий провод, L – лазер, B – барабан.

 

Множество входных компонент: Х = {10, 11}.

Множество выходных компонент: Y = {00, 01, 10}.

Множество Z = {000, 101, 011, 001}.

 

Результат структурирования:

S1 = (1,0,0,0,0,0,0)

S2 = (1,1,0,0,0,0,1)

S3 = (1,0,0,0,0,0,1)

S4 = (1,1,1,0,1,0,0)

S5 = (1,1,0,1,1,0,0)

S6 = (1,1,0,0,1,1,0)

S7 = (1,1,0,0,1,0,1)

 

Репозиция процесса

Такой механизм задается репозицией АП.   Определение 1.8. Репозицией АП P = <S, F, I, R> назовем эффективный АП

Редукция процесса

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

Композиция процессов

Пусть все или некоторые значения выходных компонент у1 ситуации из S1 соответствует всем или некоторым значениям входных компонент х2 ситуации из… Обозначим проекции множества пар соответствующих друг другу значений компонент… Пусть P2п(Х2*) – получился полностью приведенный процесс и Y1** = Y1*,

РАЗДЕЛ 2. Модельная интерпретация асинхронного процесса

Асинхронный процесс по существу является общей моделью описания динамики поведения параллельно функционирующих асинхронных систем.

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

АП можно понимать, как метамодель порождающую различные частные динамические модели.

 

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

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

2. функционирует ли она эффективно;

3. могут ли в ней возникнуть ошибки и аварийные ситуации - имеются ли потенциально узкие места;

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

 

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

1) модельная интерпретация, состоит в том, что основные понятия АП (ситуация, отношение, инициатор, результант) ставятся в соответствие понятиям частных моделей, вводятся дополнительные ограничения на АП (могут остаться не интерпретируемыми).

2) предметная интерпретация, согласуется с приложением и зависит от специфики решаемой задачи.

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

 

Тема 2.1. Сетевая объектная модель – сеть Петри

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

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

 

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

Кружки (позиции, места) - соответствуют условиям, барьеры (переходы) - соответствуют событиям.

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

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

Если же дуга идет от барьера к кружку, то она показывает, какое условие (назовем его выходным) выполняется в результате наступления события.

Условие может быть одновременно и входным и выходным для некоторого события.

Условие имеет емкость:

- условие не выполнено (емкость = 0)

- условие выполнено (емкость = 1)

- условие выполнено с n-кратным запасом (емкость = n, n – целое, n > 0).

Примеры условий:

- наличие данного для операции в программе;

- состояние некоторого регистра в устройстве ЭВМ;

- наличие деталей в конвейере и т.п.

 

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

Емкость условия указывается точками или числами в кружках. В этом случае говорят, что условие маркировано (размечено).

 

Пример графического представления сети Петри приведен на рис.2.1.

 
 

 


Рис.2.1. Пример графического представления сети Петри

 

Формально сеть Петри можно определить следующим образом:

 

Определение 2.1. Сетью Петри называется пятерка

À = <P, T, F, W, M0>, где

Р = {p1, ..., pn} – конечное непустое множество условий;

T = {t1, ..., tm} – конечное непустое множество событий;

F Í P ´ T È T ´ P - отношение инцидентности;

W – функция кратности дуг: F ® N, N – множество натуральных чисел;

М0 - функция начальной разметки: Р ® N È {0}.

 

Функция кратности дуг W сопоставляет каждой дуге число n>0 (кратность дуги). Если n>1, то в графическом представлении сети число n выписывается рядом с короткой чертой, пересекающей дугу. Часто такая дуга может заменяться пучком из n дуг, соединяющих соответствующие элементы сети. Принято дугу, кратность которой равна 1, никак не помечать.

Сеть, в которой имеют место только дуги кратности 1, называют ординарной (см. рис.2.1).

Функция начальной разметки M0 сопоставляет каждому месту p Î P некоторое число M(p) Î N È {0} (разметка места).

 

Разметкой сети À называется функция М : Р ® N È {0}.

Если все места сети À считать строго упорядоченными, то разметку сети (в том числе и начальную) можно задать как вектор чисел M = (m1, m2,…, mn) такой, что для любого i, 1£ i £ n , mi =M(pi).

 

На основе отношения инцидентности F и функции кратности дуг W можно ввести функцию инцидентности F: P ´ T È T ´ P ® N È {0}, которая определяется как

Функционирование сети Петри описывается формально с помощью множества последовательностей срабатываний и множества достижимых в сети разметок. Эти понятия определяются через правила срабатывания переходов сети.

Обозначим:

I(t) = {pÎP | F(p,t) = n}- множество условий, влияющих на события;

O(t) = {pÎP | F(t,p) = n}- множество условий, зависящих от события;

I(p) = {tÎT | F(t,p) = n}- множество событий, влияющих на условия;

O(p) = {tÎT | F(p,t) = n}- множество событий, зависящих от условия.

Определение 2.2. Событие ti возможно при разметке М, если для любого pj Î I(ti) (условия, влияющего на событие) M(pj) ³ F(pj, ti).

 

Определение 2.3. Реализация (срабатывание) события ti есть смена разметки М, при которой оно возможно, разметкой М’ по следующему правилу:

M’(pj) = M(pj) - F(pj, ti) + F(ti, pj), pjÎP.

 

Будем говорить, что разметка М’ следует за разметкой М и записывать этот факт М М’.

 

Определение 2.4. Множество событий T’ Í T совместно возможно при разметке М, если для любого pj Î I(ti) :

M(pj) ³ F(pj, ti) , ti Î T’,

M (pj) - ( F (pj, ti) - F (ti, pj)) ³ 0 , pjÎP.

 

Определение 2.5. Реализацией множества событий Т’ Í T будем называть смену разметки М, при которой Т’ совместно возможны, разметкой М’ по следующему правилу:

M’(pj) = M(pj) - F (pj, ti) + F (ti, pj) , pj Î P

 

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

 

 

 
 

 

 


Рис.2.2. Пример функционирования сети Петри

 

Пояснение.

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

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

Невозможное событие наступить не может.

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

В приведенном выше примере события t1 и t2 являются возможными, но после реализации одного из них, например t2, другое t1 становится невозможным.

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

Конец пояснения.

 

Обозначим через R(À) множество всех разметок сети À, достижимых от разметки М0 (включая М0).

Возможные изменения разметок в сети, происходящие в результате срабатывания ее переходов, удобно изображать в виде графа разметок. Граф разметок – это ориентированный граф, множество вершин которого образовано множеством R(À) –достижимых в À разметок.

Пример 2.1. Рассмотрим сеть, заданную графически на рис.2.3, и построим для нее граф разметок (рис.2.4).

 
 

 

 

 


Рис. 2.3. Сеть Петри для примера 2.1.

 

 
 

 


t1 t2

 
 

 


t1 t2

 

       
   


t1 t2 t3

 

t1 t2 t3

 

           
     


t1 t2 t3 t3

 

           
     
 


t1 t3 t3

 
 
0,3,1,1


. . . . .

t3 t3

. . . . .

Рис.2.4. Граф разметок сети Петри в примере 2.1.

Конец примера.

Определение 2.6. Разметку М, при которой ни одно из событий сети À невозможно, будем называть тупиковой.

 

Определение 2.7. Разметка М* достижима в сети À от разметки М, если существует последовательность следующих друг за другом маркировок (разметок) от М к М*.

 

Модельная интерпретация асинхронного процесса с помощью сети Петри

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

Свойства сетей Петри

Из определения правил срабатывания переходов сети следует, что для реализации события достаточно, чтобы каждое его входное условие имело некоторое… Однако при работе сети Петри общего вида некоторые ее места могут накапливать…  

Дерево достижимости

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

Анализ безопасности и ограниченности

Краткое обоснование. Присутствие символа w в дереве достижимости означает, что для произвольного положительного целого k существует достижимая… Отсутствие символа w в дереве достижимости означает, что множество достижимых…  

Анализ покрываемости

Задача покрываемости требует для заданной разметки М’ определить, достижима ли разметка М” ³ М’. Такая задача решается путём простого перебора вершин дерева достижимости. При этом ищется такая вершина х, что М[x] ³ М’. Если такой вершины не существует, то маркировка М’ не является покрываемой. Если она найдена, то М[x] определяет покрывающую маркировку для М’. Если компонента маркировки М[x], соответствующая некоторой позиции p совпадает с w, то конкретное её значение может быть вычислено. В этом случае на пути от начальной маркировки к покрывающей маркировке имеется повторяющаяся последовательность переходов, запуск которой увеличивает значение маркировки в позиции p. Число таких повторений должно быть таким, чтобы значение маркировки в позиции p превзошло или сравнялось с М’(p).

 

Анализ живости

Утверждение 2. Переход t сети Петри является потенциально живым, тогда и только тогда, когда он метит некоторую дугу в дереве достижимости этой сети.

Доказательство очевидно.

 

Ограниченность метода дерева достижимости

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

 

Матричные уравнения

  Определение 2.18. Матричный вид сети Петри À=<P, T, F, W, M0>… D-[k,i]=F(pi,tk) – кратность дуги, ведущей из позиции pi в переход tk.

РАЗДЕЛ 3. Протоколы и интерфейсы

Тема 3.1. Согласование асинхронных процессов и организация интерфейсов

 

Современные дискретные системы и ЭВМ строятся на основе модульного принципа: устройства машин, сами машины, равно как и программное обеспе­чение, выполняются в виде отдельных функциональных и структурных единиц (модулей). Последние могут объе­диняться (комплексироваться), образуя сложные системы. Организация модулей в систему с необходимостью пред­полагает взаимодействие между модулями, что требует значительных временных, аппаратурных и программных ресурсов. Фундаментальным понятием, отражающим аспект взаимодействия модулей в системе, является по­нятие интерфейса.

 

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

 

Иногда интерфейсом называют и сами техни­ческие средства, созданные в соответствии с этими пра­вилами.

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

Совокупность правил и средств, составляющих струк­туру интерфейса принято делить на три уровня: механический, электрический и логический.

Механический (конструктивный) уровень определяет совокупность требований, которым должны удовлетворять узлы интерфейсной аппаратуры — кабель, линии связи, разъемные соединения, интерфейсные карты (адапте­ры) и т. п.

Электрический уровень интерфейса оговаривает до­пуски на параметры входных и выходных электрических сигналов, токовые нагрузки на источник сигнала. Они зависят от принятой элементной базы.

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

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

 

Определение 3.2. Под протоколом информационного обмена (далее для краткости — просто протоколом) обычно понимают свод правил, которых нужно придерживаться, чтобы обеспе­чить упорядоченный информационный обмен между двумя или более объектами.

 

Термин «протокол» часто используется в литературе по вычислительной технике и системам управления. Его появление обусловлено неко­торым сходством с понятием дипломатического протокола (совокупность правил, регулирующих порядок различных дипломатических актов) и протокола заседания (обла­ченное в письменную форму изложение хода заседания).

Способы задания, анализа и синтеза интерфейсного взаимодействия являются предметом специальной теории протоколов (информационного об­мена). Не­смотря на некоторые успехи этой теории, на практике для описания интерфейсных протоколов чаще всего при­меняются неформальные или полуформальные средства, такие, как естественный язык, временные диаграммы, циклограммы или блок-схемы алгоритмов. Вследствие этого они чрезвычайно громоздки и допускают неоднозначное толкование.

При состав­лении протоколов требуется удовлетворение несколько требований:

- компактное представление правил обмена, их однозначное толкование,

- возможность проверки задания на полноту и непротиворечивость,

- возможность перехода от протоколов непосредственно к синтезу интерфейсного устройства.

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

Использование теории асинхронных процессов позволит дать формальное толкование понятия «протокол», описать интерфейс и его протокол.

 

Согласованные асинхронные процессы

Пусть заданы два приведенных процесса:

P1п= <S1, F1, I1, R1> и P2п = <S2, F2, I2, R2>

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

Элементы подмножества Y1* значений выходной компоненты ситуаций первого процесса (Y1* Í Y1) семантически эквивалентны элементам подмножества Х2* значений входной компоненты ситуаций второго процесса 2* Í Х2), а элементы подмножества Y2* значений выходной компоненты ситуаций второго процесса (Y2* Í Y2) - элементам подмножества X1* значений вход­ной компоненты ситуаций первого процесса 1* Í Х1).

Осуществим, если это возможно, последовательную композицию процессов Р1п и Р2п, считая, что Y1* = Х2* (либо Y2* = X1*). Результатом композиции является асинхронный процесс Р1,2п (либо Р2,1п). В ситуациях асинхронного процесса Р1,2п (либо Р2,1п) выделим входную компоненту, совпадаю­щую со входной компонентой ситуаций P1п ( либо P2п). Пост­роим, если это возможно, замыкание Р1,23 (либо Р2,13) асинхронного процесса Р1,2п (либо Р2,1п), считая, что поэлементно Y2* = X1* (либо Y1* = Х2*). На основании введенных ранее понятий редук­ции и замыкания АП нетрудно показать, что Р1,23 = Р2,13.

Ситуации построенного таким образом асинхронного процесса имеют следующую структуру:

s = (u, v, z),

где и = у1 = х2, v = у2 = х1, z = (z1, z2), причем компонен­ты u и v принимают значения из множеств U ÍY1* = Х2* и V Í Y2* = Х1* соответственно.

 

Определение 3.3. Два асинхронных процесса будем на­зывать согласованными относительно множеств U и V, если результатом применения к ним последовательной композиции и замыкания является автономный процесс, заданный на непустом множестве ситуаций, компоненты и и v которых являются отождествленными входными и выходными компонентами ситуаций этих процессов.

 

Тема 3.2. Протокол согласования. Согласующий асинхронный процесс

Пусть задан асинхронный процесс P = <S, F, I, R>, в ситуациях которого выделены входная х и выходная у компоненты, определенные на множествах X и Y соот­ветственно. Построим проекции:

1) S(X ´ Y) множества S на X ´ Y,

2) F(X ´ Y) множества F на X ´ Y´ X ´ Y,

3) I(X ´ Y) множества I на X ´ Y,

4) R(X ´ Y) множества R на X ´ Y.

Определение 3.4. Асинхронный процесс

P(X ´ Y) = <S(X ´ Y), F(X ´ Y), I(X ´ Y), R(X ´ Y)> назовем проекцией процесса Р на X ´ Y.

 

Определение 3.5. Проекцию автономного процесса Р31,2, полученного в результате согласования процессов P1п и Р2п, на U´ V будем называть протоколом R(U, V) согла­сования Р1п и Р2п относительно множеств U и V.

Протокол R(U,V) является формальным заданием протокола обмена, он реализуется процессом Р31,2.

Построим проекции согласованных процессов Р1п и Р2п на U ´ V.

Очевидно, что эти проекции обладают свой­ствами

I1(U´ V) Í R2(U´ V),

I2(U´ V) Í R1(U´ V),

F1(U´ V) È F2(U x V) = F31,2 (U´ V).

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

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

 

Имеется по крайней мере три случая, когда эта задача не решается:

1) иногда значения выходной компоненты одного АП не эквивалентны значениям входной компоненты другого, например, из-за различия физических параметров сигналов, представляющих эти значения (несогласуемые непосредственно уровни сигналов, их различная физическая природа, различная кодировка сигналов, имеющих один и тот же смысл, и т. д.);

2) может оказаться, что множества U и V, относи­тельно которых АП удалось согласовать, включают не все значения, требуемые протоколом обмена, и из-за этого протокол обмена не реализуется или реализуется не в полном объеме;

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

В этих случаях устройства соединяются не непосред­ственно, а через дополнительный блок, называемый адаптером.

 

Согласующий асинхронный процесс

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

s1 = (x1, у1, z1), s2 = (x2, у2, z2), sc = (у1, у2, x1, x2, zС),

(для ситуаций процесса Рсп, соответствующего адаптеру, компоненты у1 и у2 являются входными, а x1 и x2 - вы­ходными).

Пара АП Р1п, Рсп согласована относительно множеств U1, V1 допустимых значений компонент у1, х1. Процессы Р2п и Рсп согласованы относительно множеств U2, V2 до­пустимых значений компонент у2, х2. Такая композиция АП Р1п, Р2п и Рсп может быть представлена в виде автономного АП P1С2, заданного на ситуациях вида

s1c2=(s1, sC, s2).

Определение 3.6. Назовем Рсп асинхронным процес­сом, согласующим АП Р1п и Р2п, если в процессе P1c2:

1) существует такая ситуация si1c2 с компонентой si1 Î R1, что любая траектория процесса P1c2 из si1c2 неизбежно ведет к ситуации sj1c2 с компонентой sj2 Î I2 и

2) существует такая ситуация sk1c2 с компонентой sk2 Î R2 , что любая траектория процесса P1c2 из sk1c2 не­избежно ведет к ситуации sl1c2 с компонентой sl1 Î I1.

 

Иными словами, процесс Рсп будет согласующим лишь в том случае, если среди его ситуаций найдутся такие, что появление некоторого значения входной компоненты y1(либо y2) по достижении результанта процессом Р1(либо Р2) с неизбежностью вызывает такое изменение выходной ком­поненты х2(либо x1), которое приводит в процессе Р2(либо Р1) к переходу от результанта к инициатору.

 

Пример 3.1. Рассмотрим систему, состоящую из канального процессора КП, адаптера Ад и двух абонентов — Аб1 и Аб2 (рис. 3.1).

 

Рис. 3.1. Схема системы в примере 3.1.

 

КП, Аб1 и Аб2 связаны общей магистралью данных. Каждое из этих устройств имеет возможность передавать информацию в магистраль и принимать ее из магистрали. Система работает по принципу «ведущий — ведомый» и осуществляет обмен информа­цией между КП и абонентами. Роль ведущего играет КП, а ведо­мых — абоненты. КП устанавливает адрес А абонента и затем сиг­нал запроса а = 1. По адресу А и этому сигналу адаптер выраба­тывает либо а1 = 1, либо а2 = 1, которые являются сигналами, инициирующими прием или передачу информации.

После оконча­ния работы с информацией соответствующий абонент устанавлива­ет сигнал bi = 1. Приняв от абонента bi = 1, адаптер отвечает сигналом b = 1. После этого начинается процесс отключения або­нента: КП устанавливает а = 0 (при этом он может менять адрес), по которому адаптер сбрасывает в 0 тот сигнал аi, который был равен 1. В ответ на аi = 0 i-й абонент устанавливает bi = 0, после чего адаптер выставляет b = 0, и система оказывается в ис­ходном состоянии.

Рассмотрим сеть Петри, описывающую взаимодействие указанных устройств на уровне установления и разрыва свя­зи (протокол установления и разрыва связей) (рис.3.2).

Рис.3.2. Сеть Петри, моделирующая взаимодействие системы в примере 3.1

 

Эта сеть Петри описывает согласованный АП и состоит из че­тырех фрагментов, относящихся к перечисленным выше уст­ройствам. В силу того, что КП может обратиться только к одному из абонентов, точка может появиться либо в условии 5, либо в условии 6, а значит, либо в 7, либо в 8, но не в обоих одновременно.

Для выделенных фрагментов перечислим ситуации, являющие­ся инициаторами и результантами.

Результанты фрагмента КП:

1)маркировка условий 4 и 7 — установка адреса Аб1 и сигна­ла а = 1;

2)маркировка условий 4 и 8 — установка адреса Аб2 и сигнала а = 1;

3)маркировка условий 2 и 4 — установка а = 0.

Инициатором фрагмента КП является результант 1) фрагмента Ад.

Результанты фрагмента Ад:

1) маркировка условия 9 — установка b = 1 или b = 0;

2) маркировка условия 11 — установка а1 = 1 или а1 = 0;

3) маркировка условия 13 — установка а2 = 1 или а2 = 0.

Инициаторы фрагмента Ад — результанты фрагментов КП, Аб1 и Аб2.

Фрагмент Аб1: результант — маркировка условия 14 (установка b1 = 1 или b1 = 0),

инициатор — результант 2) фрагмента Ад.

Фрагмент Аб2: результант — маркировка условия 15 (установка b2 = 1 или b2 = 0),

инициатор — результант 3) фрагмента Ад.

 

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


РАЗДЕЛ 4. Взаимодействие процессов

Тема 4.1. Механизмы взаимодействия процессов

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

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

Определение 4.1. Параллельными называются такие последовательные вычислительные процессы, которые одновременно находятся в каком-либо активном состоянии.

Два параллельных процесса могут быть независимыми либо взаимодействующими.

Определение 4.2. Независимыми являются процессы, множества переменных которых не пересекаются.

 

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

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

 

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

 

Определение 4.4. Ресурсы, которые не допускают одновременного использования несколькими процессами, называются критическими.

 

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

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

Определение 4.5. Конкурирующие процессы действуют относительно независимо, но имеют доступ к общим переменным.

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

 

Рассмотрим проблемы, возникающие при взаимодействии параллельно работающих процессов.

 

Пример 4.1. Рассмотрим работу конкурирующих процессов Р1 и Р2 с общей переменной Х. Пусть оба процесса асинхронно, независимо один от другого, изменяют (например, увеличивают) значение переменной Х, считывая ее значение в локальную область памяти RI (I=1,2), при этом каждый процесс выполняет некоторые последовательности операций во времени (табл.4.1). Здесь можно рассмотреть не все операторы каждого из процессов, а только те, в которых осуществляется работа с общей переменной Х. Каждому из операторов присваивается некоторый условный номер.

 

№ оператора Процесс Р1   № оператора Процесс Р2
R1:=X R1:=R1+1 X:=R1   R2:=X R2:=R2+1 X:=R2

 

Таблица 4.1. Представление процессов в примере 4.1

 

Поскольку процессы могут иметь различные скорости исполнения, то может иметь место любая последовательность выполнения операций во времени. Если сначала будут выполнены все операции процесса Р1, а уже потом — все операции процесса Р2 (или, наоборот, сначала операции 4-6, а затем — операции 1-3), то в итоге переменная Х получит значение, равное Х+2 (рис. 4.1).

Однако, если в промежуток времени между выполнением операций 1 и 3 будет выполнена хотя бы одна из операций 4-6 (рис. 4.2), то значение переменной Х после выполнения всех операций будет не (Х+2), а (Х+1).

 

 

Р1: (1) R1:=X; (2) R1:=R1+1; (3)X:=R1;

 

Р2: (4)R2:=Х; (5) R2:=R2+1; (6) X:=R2;

 

Рис. 4.1. Первый вариант развития событий при выполнении процессов

 

 
 


Р1: (1) R1:=X; (2) R1:=R1+1; (3) X:=R1;

 

Р2: (4) R2:=X; (5) R2:=R2+1; (6) X:=R2;

 

Рис. 4.2. Второй вариант развития событий при выполнении процессов

 

В результате имеет место очень серьезная ошибка и, к при этом, неисправимая, так как ее нельзя проконтролировать. Например, если бы процессы Р1 и Р2 осуществляли продажу билетов и переменная Х фиксировала количество уже проданных, то в результате некорректного взаимодействия было бы продано несколько билетов на одно и то же место.

Конец примера.

 

Пример 4.2. Взаимодействие сотрудничающих процессов удобно всего рассматривать в схеме “производитель-потребитель” или, как часто говорят — “поставщик-потребитель”.

Допустим, что “поставщик” — это процесс, который определяет порции информации (сообщения) другому процессу, имя которого “потребитель”. Например, процесс пользователя, порождающий строки для вывода, может выступать как “поставщик”, а процесс, который выводит эти строки на печать, — как “потребитель”.

В этом случае между процессами “поставщик” и “потребитель” будем иметь очередь заполненных буферов, содержащих сообщения. Когда “поставщик” хочет послать очередное сообщение, он добавляет в конец этой очереди еще один буфер. “Потребитель”, чтобы получить сообщение, забирает из очереди буфер, который стоит в ее начале. Такое решение, хотя и кажется тривиальным, требует, чтобы “поставщик” и “потребитель” синхронизировали свои действия. Например, они должны следить за количеством свободных и заполненных буферов. “Поставщик ” может передавать сообщения только до тех пор, пока имеются свободные буферы. Аналогично, “потребитель” может получать сообщения только если очередь не пуста.

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

Конец примера.

 

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

 

Тема 4.2. Решение проблемы взаимного исключения

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

 

Определение 4.7. Те места в процессах, в которых происходит обращение к критическим ресурсам, называются критическими секциями или критическими интервалами.

 

 
 

 

 


Рис.4.3. Пример взаимодействующих процессов

 

На рис.4.3 А, В, С – разделяемый ресурс, Р1, Р2 – процессы.

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

Следующая ниже сеть Петри моделирует механизм взаимного исключения для двух конкурирующих процессов P1 и P2. (рис.4.4).

             
   
Р1 Р2
 
   
 
S1
   
S2
 
 
T1
   
T2
 
 
S3
     
S4
 
 
 
T3
   
T4
 
 
S5
     
S6
 
 

 

 


 

Рис.4.4. Модель механизма взаимного исключения

 

Позиция m представляет условие «критическая секция свободна», разрешающее вход в критическую секцию. Попытка процесса P1 (P2) войти в критическую секцию осуществляется после помещения фишки в его позицию s1 (s2). Такая попытка может увенчаться успехом, если в позиции m содержится фишка. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск t1 запретит запуск перехода t2, вынуждая процесс P2 ждать, пока процесс P1 выйдет из своей критической секции, и возвратит фишку обратно в позицию m.

Взаимодействие сотрудничающих процессов в задаче «поставщик-потребитель может быть промоделировано следующей ниже сетью Петри (рис.4.5)

 

 

       
 
Поставщик
 
Потребитель

 
 

 


 

Рис.4.5. Сеть Петри, моделирующая задачу «поставщик-потребитель»

 

Позиция B представляет буфер, каждая фишка соответствует сообщению, которое произведено, но еще не использовано.

 

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

· в любой момент времени только один процесс должен находиться в своей критической секции;

· ни один процесс не должен находиться в своей критической секции бесконечно долго;

· ни один процесс не должен ждать бесконечно долго входа в свой критический интервал. В частности:

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

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

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

 

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

- блокировка памяти,

- специальные команды типа «проверка и установка»,

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

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

 

Блокировка памяти

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

Семафорные операции

Понятие семафорных механизмов было введено Дейкстрой.

Семафор – переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: «закрытия» и «открытия», названных соответственно Р- и V-операциями. Эти операции являются примитивами относительно семафора, который указывается в качестве параметра операций. Здесь семафор выполняет роль вспомогательного критического ресурса, так как операции Р и V неделимы при своем выполнении и взаимно исключают друг друга.

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

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

 

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

Обобщенный смысл примитива Р(S) состоит в проверке текущего значения семафора S, и если оно не меньше нуля, то осуществляется переход к следующей за примитивом операции. В противном случае процесс снимается на некоторое время с выполнения и переводится в состояние «пассивного ожидания». Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо него на процессоре может исполняться другой процесс, который реально совершает полезную работу.

Операция V(S) связана с увеличением значения семафора на единицу и переводом одного или нескольких процессов в состояние готовности к центральному процессору.

Отметим еще раз, что операции P и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра.

Рассмотрим первый вариант алгоритма работы семафорных операций, который приведен в листинге 4.1.

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

 

P(S): S:=S-1;

If S<0 then WAIT(S); {остановить процесс и поместить его в

очередь ожидания к семафору S}

V(S): If S<0 then RELEASE(S); {поместить один из ожидающих

процессов очереди семафора S в очередь готовности};

S:=S+1;

 

Листинг 4.1. Вариант реализации семафорных примитивов

 

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

InitSem (Имя_семафора, Начальное_значение_семафора);

Попытаемся на примере двух конкурирующих процессов Р1 и Р2 проанализировать использование данных семафорных примитивов для решения проблемы критического интервала. Схема, иллюстрирующая это решение, представлена рис.4.10.

 

 

P1 P2

InitSem (S, 1);

       
 
   

 


Рис. 4.10. Модель использования семафорных операций

 

Семафор S имеет начальное значение, равное 1. Если процессы Р1 и Р2 попытаются одновременно выполнить примитив P(S), то это удастся успешно сделать только одному из них. Предположим, это сделал процесс Р2, тогда он закрывает семафор S, после чего выполняется его критический интервал. Процесс Р1 в рассматриваемой ситуации будет заблокирован на семафоре S. Тем самым будет гарантировано взаимное исключение.

После выполнения примитива V(S) процессом Р2 семафор S открывается, указывая на возможность захвата каким-либо процессом освободившегося критического ресурса. При этом производится перевод процесса Р1 из заблокированного состояния в состояние готовности.

На уровне реализации возможно одно из двух решений в отношении процессов, которые переводятся из очереди ожидания в очередь готовности при выполнении примитива V:

· процесс его активизации (выборка из очереди готовности) вновь пытается выполнить примитив Р, считая предыдущую попытку неуспешной;

· процесс при помещении его в очередь готовности отмечается как успешно выполнивший примитив Р.

Тогда при его активизации управление будет передано не на повторное выполнение примитива Р, а на команду, следующую за ним.

 

Рассмотрим первый способ реализации.

Пусть процесс Р2 в некоторый момент времени выполняет операцию P(S). Тогда семафор S становится равным нулю. Пусть далее процесс Р1 пытается выполнить операцию P(S). Процесс Р1 в этом случае «засыпает» на семафоре S, так как значение семафора S равнялось нулю, а теперь станет равным (-1). После выполнения критического интервала процесс Р2 выполняет операцию V(S), при этом значение семафора S становится равным нулю, а процесс Р1 переводится в очередь готовности. Пусть через некоторое время процесс Р1 будет активизирован, то есть выведен из состояния ожидания, и сможет продолжить свое исполнение. Он повторно пытается выполнить операцию P(S), однако это ему не удается, так как S=0. Процесс Р1 «засыпает» на семафоре, а его значение становится равным (-1). Если через некоторое время процесс Р2 попытается выполнить P(S), то он тоже «уснет». Таким образом, возникнет так называемая тупиковая ситуация, так как «будить» процессы Р1 и Р2 некому.

При втором способе реализации тупиковой ситуации не будет. Действительно, пусть все происходит также до момента окончания исполнения процессом Р2 примитива V(S). Пусть примитив V(S) выполнен и S=0. Через некоторое время процесс Р1 активизировался. Согласно данному способу реализации, он сразу же попадает в свой критический интервал. При этом никакой другой процесс не попадает в свой критический интервал, так как семафор остался закрытым. После исполнения своего критического интервала процесс Р1 выполнит V(S). Если за время выполнения критического интервала процесса Р1 процесс Р2 не делал попыток выполнить операцию P(S), семафор S установился в единицу. В противном случае значение семафора будет не больше нуля. Но в любом варианте после завершения операции V(S) процессом Р1 доступ к критическому ресурсу со стороны процесса Р2 будет разрешен.

 

Заметим, что возникновение тупиков возможно в случае несогласованного выбора механизма реактивации процессов из очереди, с одной стороны, и выбора алгоритмов семафорных операций – с другой.

Возможен другой алгоритм работы семафорных операций – листинг 4.2.

P(S): If S>=1

then S:=S-1

else WAIT (S); {остановить процесс и поместить в очередь

ожидания к семафору S}

V(S): If S<=0

then RELEASE (S); {поместить один из ожидающих

процессов очереди семафора S в очередь готовности};

S:=S+1;

 

Листинг 4.2.Второй вариант реализации семафорных примитивов

 

Здесь вызов WAIT (S) означает, что супервизор ОС должен перевести задачу в состояние ожидания, причем очередь процессов связана с семафором S. Вызов RELEASE (S) означает обращение к диспетчеру задач с просьбой перевести первый из процессов, стоящих в очереди S, в состояние готовности к исполнению.

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

Действительно, пусть Р2 в некоторый момент времени выполнит операцию P(S). Тогда семафор S становится равным нулю. Пусть далее процесс Р1 пытается выполнить операцию P(S). Процесс Р1 в этом случае «заснет» на семафоре S, так как S=0, причем значение S не изменится. После выполнения своего критического интервала процесс Р2 выполнит операцию V(S), при этом значение семафора S станет равным единице, а процесс Р1 переведется в очередь готовности. Если через некоторое время процесс Р1 будет активизирован, он успешно выполнит P(S) и войдет в свой критический интервал.

 

Анализ рассмотренных задач показывает, что, несмотря на очевидные достоинства (простота, независимость от количества процессов, отсутствие “активного ожидания”), семафорные механизмы имеют и ряд недостатков. Семафорные механизмы являются слишком примитивными, так как семафор не указывает непосредственно на синхронизирующее условие, с которым он связан, или на критический ресурс. Поэтому при построении сложных схем синхронизации алгоритмы решения задач порой получаются весьма непростыми, ненаглядными и затруднительными для доказательства их правильности.

 

Тема 4.2. Проблемы тупиков и методы борьбы с ними

Понятие тупика. Модель Холта

  Определение 4.8. Говорят, что в мультипрограммной системе процесс находится в…  

Методы борьбы с тупиками

Проблема борьбы с тупиками становится все более актуальной и сложной по мере развития и внедрения параллельных вычислительных систем. При… qпредотвращение тупика; qобход тупика;

Задача об обедающих мудрецах

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

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

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

Всякий раз, когда философ пытается дотянуться до своей левой вилки, его левый сосед мгновенно перехватывает вилку. Таким образом, может оказаться, что сидящий философ никогда не приступит к еде, что приведёт к его гибели.

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

В этой сети Петри позиция пi, iÎ{1,2,3,4,5}, представляет условие «i-тая палочка свободна». В начальной маркировке каждая из этих позиций имеет фишку. Каждому мудрецу iÎ{1,2,3,4,5} соответствует две позиции: позиция дi – представляющая условие «i-тый мудрец думает»; и позиция еi. – представляющая условие «i-тый мудрец ест». В начальной маркировке каждая позиция дi содержит фишку, а каждая позиция еi пуста.

 
 

Рис.4.12. Сеть Петри, моделирующая систему обедающих мудрецов

 

Каждому мудрецу iÎ{1,2,3,4,5} также соответствует два перехода: переход начi – представляющий событие «начало приёма пищи i-тым мудрецом»; и переход завi – представляющий событие «завершение приёма пищи i-тым мудрецом».

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

 

РАЗДЕЛ 5. Введение в теорию схем программ

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

 

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

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

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

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

 

Теоретическое программирование сформировалось на основе двух моделей вычислений:

- последовательных программ с памятью или операторных программ;

- рекурсивных программ.

 

Обе модели строятся над абстрактной алгебраической системой <D,F,Р>, образованной предметной областью D, конечным набором (сигнатурой) функциональных F = {f1, f2, … , fm} и предикатных P={p1,…,pn} символов с заданным для каждого символа числом его аргументов (арностью).

 

Определение класса программ слагается из трех частей:

- схемы программ (синтаксиса)

- интерпретации;

- семантики.

 

Определение 5.1. Схема программ – это конструкционный объект, показывающий, как строятся программы с использованием сигнатуры и других формальных символов.

 

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

Определение 5.3. Семантика – это способ сопоставления каждой программе результата ее выполнения.

 

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

 

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

 

Понятие схемы программы принадлежит советскому математику А.А.Ляпунову, которое он ввел в 1953г., исходя из общей концепции необходимости и возможности формализации процесса программирования.

 

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

 

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

-модель позволяет изучать свойства достаточно широких классов программ, а не отдельных конкретных программ;

-сохраняет все интересующие исследователя свойства и особенности рассматриваемого класса программ;

-позволяет игнорировать несущественные для данной проблемы свойства, например, синтаксические детали;

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

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

 

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

 

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

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

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

 

Пример 5.1.

 

Программа вычисления факториала   начало целые х, у; ввод (х); у := 1; m: если х = 0 то на m1; у := х * у; х := х – 1; на m; m1: вывод (у); конец   Схема программы   начало ввод (х); у := а; m: если p(x) то на m1; у := g (х, у); х := h (х); на m; m1: вывод (у); конец

 

Стандартные схемы программ

  Исследование стандартных схем составляет основное содержание общей теории схем… Каждый оператор в такой схеме является либо преобразователем - оператором, изменяющим состояние памяти, либо…

РАЗДЕЛ 6. Методы формальной спецификации и верификации программ

Тема 6.1. Основные принципы верификации программ

Понятие корректности (правильности) подразумевает соответствие проверяемого объекта некоторому эталонному объекту или совокупности формализованных эталонных характеристик и правил.

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

Программная спецификация – это документ, в котором формулируются в требованиях к программе.

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

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

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

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

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

В этом случае доказательство правильности состоит из доказательства того, что:

- программа, будучи запущенной, в конце концов, будет закончена;

- после окончания программы будет справедливо утверждение о правильности.

Проиллюстрируем эти идеи на примере очень простой программы.

 

Пример 6.1. Предположим, что нужно вычислить произведение двух любых целых чисел M, N, причем M ³ 0 и операцию умножения использовать нельзя. Для этого можно использовать операцию сложения и вычислить сумму из M слагаемых (каждое равно N). В результате получим M*N.

Рассмотрим блок-схему, реализующую такое вычисление (рис.6.1).

 

 

 

 


Рис.6.1. Блок-схема, реализующая задачу в примере 6.1.

 

Нужно доказать, что приведенная программа правильно вычисляет произведение двух любых целых чисел M и N при условии, что M ³ 0, то есть если программа выполняется с целыми числами M и N, где M ³ 0, то она в конце концов окончится (достигнув точки 5) со значением J = M * N.

Сформулируем все необходимые утверждения и сопоставим их различным точкам блок-схемы (рис.5.2).

 

 

 
 

 


M, N – целые значения, M ³ 0 - Утверждение о данных

 

при каждом попадании в эту точку J = I * N - Утверждение об инварианте цикла

 

на последнем шаге цикла в этой точке I = M. -Утверждение о конечности цикла

 

попадаем в эту точку с J = M * N - Утверждение о правильности программы

 

 

Рис.6.2. Блок-схема с введенными утверждениями о правильности

 

Чтобы удостовериться в правильности работы блок-схемы можно проверить ее на некоторых фиксированных данных, например, M = 3, N = 5. Результат дожжен быть равен 15, то есть в точку 5 мы должны прийти со значением J = 15.

Трассировка на фиксированных данных приведена в табл.6.1.

Число проходов N через точку 2 Значение I Значение J

 

Таблица 6.1. Трассировка блок-схемы на фиксированных данных

Таким образом, можно убедиться, что при M = 3 и N = 5 блок-схема работает верно. Хотя это и укрепляет уверенность в правильности работы программы, но тем не менее никак не доказывает, что программа будет работать правильно при всех возможных значениях M и N.

Обобщим трассировку для некоторых произвольных значениях M и N.

Трассировка на символьных данных приведена в табл. 6.2.

 

Число проходов N через точку 2 Значение I Значение J
. . . . . . . . .
M +1 M M*N

 

Таблица 6.2. Трассировка блок-схемы на символьных данных

 

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

Как определить, какие значения I и J должны стоять после этого пробела? Как можно быть уверенным, что именно такие?

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

Ответ на второй вопрос требует доказательства.

 

Тема 6.2. Доказательство правильности программ

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

Рассмотрим доказательство правильности программы представленной в примере 6.1. Из таблицы 6.2 следует, что всякий раз, когда попадаем в точку 2, имеем J = I * N.

Попробуем доказать это методом индукции по n – числу проходов через точку 2.

 

Для доказательства справедливости некоторого высказывания в момент прохождения через какую-либо из точек внутреннего цикла нужно:

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

2. Показать что, если при очередном (n-ом) попадании в эту точку высказывание справедливо, то оно справедливо и в следующий раз (если, конечно, мы попадем в эту точку n+1 раз). То есть выполнение цикла не нарушает истинности высказывания – инвариант цикла.

 

Проведем доказательство блок-схемы в рассмотренном выше примере.

1. Докажем, что при попадании в точку 2: J = I * N:

a. При первом попадании в точку 2 имеем I = 0, J = 0, следовательно

J = I * N = 0 * N = 0 справедливо;

b. Предположим, что в точке 2 справедливо выражение J = I * N для In и Jn, т.е. Jn, = In * N, далее выполняется цикл и получается новое значение

In+1 , Jn+1 : In+1 = In + 1, Jn+1 = Jn + N,

Jn+1 = In * N + N (по гипотезе индукции) = (In + 1) * N = In+1* N ч.т.д.

 

2. Докажем, что на последнем шаге цикла в точке 2: I = M.

a. При первом попадании в точку 2: I = 0. При последующих попаданиях I увеличивается на единицу. Так как M в программе нигде не изменяется и M³0, то очевидно в какой-то момент I станет равным M.

 

3. Если в точке 2: I = M, то следовательно J = I * N = M * N. Истинность I = M приведет к переходу в точку 5 с J = M * N ч.т.д.

 

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

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

 

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

 

Для верификации программ необходимы три языка:

-язык записи контролируемых текстов программ;

-язык формулировки условий верификации;

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

 

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

 

Метод индуктивных утверждений

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

Проиллюстрируем использование описанного выше подхода на следующей структуре (рис. 6.3)

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

Следовательно, первым, вероятно, нужно доказать утверждение 2, а затем использовать для доказательства утверждения 1.

 

 
 

 

 


1 -- При каждом попадании в эту точку цикла справедливо утверждение 1

 

 

2 -- При каждом попадании в эту точку цикла справедливо утверждение 2

 

 

Рис.6.3. Пример блок-схемы с вложенными циклами

 

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

 

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

Введем два определения.

 

Определение 6.1. Пусть А – некоторое утверждение, описывающее предполагаемые свойства данных в программе, а С – утверждение о правильности. Будем говорить, что программа частично правильна (по отношению к А и С), если при каждом выполнении ее с данными, удовлетворяющими А, будет справедливо утверждение С при условии, что программа закончится.

 

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

 

Определение 6.2. Будем называть программу полностью правильной (по отношению к А и С), если она частично правильна (по отношению к А и С) и заканчивается при всех данных, удовлетворяющих А.

 

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

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

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

Для каждого пути в программе, ведущего из точки n, связанной с утверждением Аn, в точку n+1, связанную с утверждением Аn+1 (при условии, что на этом пути нет точек с каким-либо дополнительным утверждением), докажем, что если мы попали в точку n и справедливо утверждение Аn, а затем прошли от точки n до точки n+1, то при попадании в точку j справедливо утверждение Аn+1.

Для цикла точки n и n+1 могут быть одной и той же точкой.

 

Опираясь на этот подход, докажем теорему.

 

Теорема 6.1. Если можно выполнить все действия, предусмотренные описанным методом индуктивных утверждений для некоторой программы, то эта программа частично правильна (относительно А и С).

 

Доказательство.

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

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

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

1. Пусть в процессе выполнения программы мы попали в точку n=1. Нужно показать, что в этой точке утверждение справедливо. Но первая точка – это начало программы, и с ней связано утверждение о данных А. Оно справедливо по определению.

2. Пусть мы дошли до некоторой n-ой точки, с ней связано утверждение А и пусть это утверждение справедливо (гипотеза индукции). Покажем это для n+1 точки. Очевидно, что между точками n и n+1 существует некоторый путь. Так как мы уже использовали метод индуктивных утверждений, то, следовательно, и уже рассмотрели этот путь и показали, что если находимся в n-ой точке со справедливым утверждением Аn, а затем проходим из n-ой в n+1 точку, то при ее достижении будет справедливо утверждение Аn+1. Из этого факта вместе с гипотезой о справедливости утверждения Аn следует, что при попадании в n+1 точку справедливо утверждение Аn+1. Ч.т.д.

 

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

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

 

Пример 6.2. Пусть требуется доказать, что приведенная на рисунке 1 блок-схема устанавливает переменную МАХ равной максимальному значению в двумерном массиве Х.

Указанные на блок-схеме утверждения (рис.6.4) – индуктивные утверждения, необходимые для доказательства частичной правильности программы. Так как все утверждения имеют аналогичную форму и начинаются с фразы: «При достижении этой точки справедливо», то это начало фразы мы опускаем. Утверждение о конечности программы не указано на блок-схеме, поскольку доказательство этого утверждения будет проводиться отдельно от доказательства частичной правильности.

 


Х – массив вещественных чисел,

состоящий из M строк и N столбцов, M³1, N ³1

1 £ I £ M+1 и

MAX= Х[1,1], если I = 1;

иначе МАХ= максимальное из

значений элементов в первых I-1 строках массива Х

 

МАХ – максимальное

значение в массиве Х

 

1£ I £ M и 1 £ J £ N+1 и

МАХ=Х[1,1], если I=1, J=1;

иначе МАХ= максимальное

из значений элементов в первых I-1 строках и первых J-1 элементов в I-й строке массива Х

 

 

Рис.6.4. Блок-схема программы в примере 6.2.

 

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

1. Путь из точки 1 в точку 2.

Предположим, что мы находимся в точке 1 и связанное с ней утверждение справедливо, т.е. данные удовлетворяют исходному допущению. Перейдем из точки 1 в точку 2. Нужно показать, что после перехода в точку 2 связанное с этой точкой утверждение будет справедливо. Если мы попали в точку 2 из точки 1, то имеем I = 1 и МАХ = Х[1,1]. Так как М ³ 1, то очевидно, что 1 £ I=1 £ M+1. Поскольку МАХ = Х[1,1] и I = 1, то утверждение о МАХ справедливо.

2. Путь из точки 2 в точку 3.

Предположим, что мы находимся в точке 2 и справедливо связанное с нею утверждение. Перейдем из точки 2 в точку 3. Требуется показать, что при попадании в точку 3 будет справедливо утверждение, связанное с этой точкой. Если мы дошли до точки 3 (из точки 2), то имеем J = 1, а значение МАХ осталось неизменным. Так как N³1, 1 £ J=1 £ N+1, а значение I после точки 2 не изменилось, то 1 £ I £ M+1. Однако если мы пришли из точки 2 в точку 3, то известно, что проверка I £ M была истинной, и, комбинируя это отношение с 1 £ I £ M+1, получаем 1 £ I £ M. Если I = 1 и J = 1, то из утверждения 2 получим МАХ = Х[1,1]. В противном случае (т.е. при I ¹1) из утверждения 2 получаем, что МАХ равно максимальному из значений элементов в первых I – 1 строках массива Х или, более точно, максимальному из значений элементов в первых I – 1 строках и из значений первых J – 1 = 1 – 1 = 0 элементов в I-й строке. Таким образом, очевидно, что при переходе из точки 2 в точку 3 утверждение, связанное с точкой 3, оказывается справедливым.

3. Путь из точки 3 через точки 4, 5 к точке 3.

Предположим, что мы находимся в точке 3 и справедливо связанное с нею утверждение. Пройдем через точки 4, 5 к точке 3. Нужно показать, что при возврате в точку 3 соответствующее утверждение останется справедливым. Пусть I и J в исходном положении в точке 3 принимают значения In и Jn . Мы имеем 1 £ In £ M и 1 £ Jn £ N+1. При возврате в точку 3 через точки 4 и 5 получим In+1 = In и Jn+1 = Jn +1. Следовательно, опять имеем 1 £ In+1 = In £ M. Если мы проходим по этому пути, то проверка Jn £ N была истинной. Из этого, а также из соотношения 1 £ Jn £ N+1 получаем 1 £ Jn £ N. Таким образом, при возврате в точку 3 снова имеем 1 < 2 £ Jn+1 = Jn +1 £ N+1. На всем пути перехода в точку 3 значение МАХ не изменялось, и известно, кроме того, что истинна проверка Х[In,Jn] £ MAX. Если учесть истинность утверждения о МАХ до «прохода» по указанному пути, то данное утверждение остается истинным и при возврате в точку 3 с In+1 = In и Jn+1 = Jn +1. Так как Х[In,Jn] £ MAX, то неизменное значение МАХ снова будет максимальным из значений элементов в первых In+1 – 1 = In – 1 строках и из значений первых Jn+1 – 1 = (Jn +1) – 1 = Jn элементов в In-й строке массива Х.

4. Путь из точки 3 через точки 4, 6 в точку 3.

Рассуждения для этого пути аналогичны приведенным для предыдущего пути, за исключением того, что при возврате в точку 3 МАХ будет иметь значения Х[In,Jn]. Кроме того, так как выбран этот путь, проверка Х[In,Jn] £ MAX была ложной и, следовательно, MAX < Х[In,Jn]. Таким образом, Х[In,Jn] больше максимального из значений элементов первых In – 1 строк и Jn -1 элементов в In-й строке. Отсюда следует, что при возврате в точку 3 значение МАХ остается максимальным из значений элементов первых In+1 – 1 = In – 1 и первых Jn+1 – 1 = (Jn +1) – 1 = Jn элементов в In+1 = In-й строке массива Х.

5. Путь из точки 3 через точку 7 в точку 2.

Предположим, что мы находимся в точке 3 и справедливо связанное с нею утверждение. Перейдем из точки 3 через точку 7 в точку 2. Нужно показать, что при возврате в точку 2 будет справедливо связанное с нею утверждение. Из точки 3 в точку 7 мы попадем только тогда, когда ложна проверка J £ N. Но из утверждения, относящегося к точке 3, известно, что 1 £ J £ N+1. Отсюда можно заключить, что J = N+1. Пусть I в точке 3 принимает значение In. Утверждение в точке 3 гласит: 1 £ In £ M и МАХ равно максимальному из значений элементов первых In – 1 строках и первых J -1 = (N+1) – 1 = N элементов в In-й строке массива Х. Но так как в массиве Х существует только N столбцов, то МАХ равно максимальному из значений элементов In строках массива Х. Значение МАХ между точками 3 и 2 не изменялось, а значение I изменилось и стало равным I+1. Так как в точке 3 было справедливо отношение 1 £ In £ M, то это означает, что 1 < 2 £ In+1 = In +1 £ M+1 справедливо в точке 2. Следовательно, при достижении точки 2 будет справедливо утверждение: МАХ равно максимальному из значений элементов в первых I - 1 = (In + 1) – 1 = In строках массива Х.

6. Путь от точки 2 в точку 8.

Предположим, что мы находимся в точке 2 и справедливо соответствующее утверждение и мы переходим в точку 8. Необходимо показать, что при достижении точки 8 будет справедливо связанное с нею утверждение. Из точки 2 перейдем в точку 8, если была ложной проверка I £ M. Однако в точке 2 было справедливо неравенство 1 £ I £ M+1; следовательно, можно заключить, что I = M+1. Значение МАХ при переходе из 2 в 8 не изменялось, и, таким образом, из утверждения, относящегося к точке 2, можно заключить, что при попадании в точку 8 МАХ равно максимальному из значений элементов в первых I -1 = (M+1) – 1 = M строках массива Х. Но массив Х содержит только М строк; следовательно, МАХ равно максимальному из значений элементов Х.

 

Таким образом, мы доказали частичную правильность программы. Осталось еще удостовериться, что программа закончится. Отметим, что единственными местами в программе, где изменяются I и J, являются «изолированные» части двух итерационных блоков, управляющих увеличением параметра цикла. Так как значение J увеличивается на 1, а значение N при выполнении внутреннего цикла не изменяется (путь через точки 3, 4, 5, 3 или через точки 3, 4, 6, 3), то значение J должно в конце концов превысить значение N. Таким образом, попадая в точку 3, мы когда-нибудь (после конечного числа выполнений внутреннего цикла) должны попасть в точку 7, а затем в точку 2. При каждом попадании в точку 2 мы затем попадем либо в точку 8 и процесс закончится, либо в точку 3. Если мы попали в точку 3, только что было показано, как в конце концов дойдем до точки 7 и вернемся в точку 2. При этом значение I будет увеличиваться на 1, а значение M останется неизменным. Следовательно, после конечного числа шагов значение I станет больше значения М. В этот момент мы перейдем из точки 2 в точку 8, и программа закончится. Таким образом, доказана конечность представленной программы. Если это доказательство объединить с предыдущем доказательством частичной правильности, то из этого последует и полная правильность программы.

 

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

Предлагается генерировать инварианты непосредственно по тексту программы и использовать их как для доказательства корректности компонент программы, так и для проверки ее завершаемости.

В настоящее время проводятся работы по созданию автоматизированных верификаторов программ, написанных на различных языках программирования.

 

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах./ Под ред. В.И.Варшавского. - М.: Наука, 1986. – 256 с.

2. Питерсон Дж. Теория сетей Петри и моделирование систем. - М.: Наука, 1984. – 264 с.

3. Гордеев А.В. Системное программное обеспечение: Учеб./Гордеев А.В., Молчанов А.Ю.- СПб.: Питер, 2001. – 736 с.

4. Дейкстра Э. Взаимодействие последовательных процессов // Языки программирования (под ред.Ф.Женюи). М.: Мир, 1972. С. 9 – 86.

5. Дейтл Г. Введение в операционные системы. В двух томах /Пер. с англ. Л. А. Теплицкого, А. Б. Ходулева, Вс. С. Штаркмана под редакцией Вс. С. Штаркмана. – М.: Мир, 1987. – 876 с.

6. Хоар Ч. Взаимодействующие последовательные процессы. – М.: Мир, 1989. – 264 с.

7. Котов В.Е. Введение в теорию схем программ. - Новосибирск: Наука, 1978. – 256 с.

8. Котов В. Е., Сабельфельд В. К. Теория схем программ Новосибирск: Наука, 1978. – 225 с.

9. Непомнящий В.А., Рякин О.М. Прикладные методы верификации программ/ Под ред. А.П.Ершова. – М.: Радио и связь, 1992. – 256 с.

10. Андерсон Р. Доказательство правильности программ: Пер.с англ. –М.: Мир, 1982. – 163 с.

– Конец работы –

Используемые теги: Теория, вычислительных, процессов0.058

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

Что будем делать с полученным материалом:

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

Еще рефераты, курсовые, дипломные работы на эту тему:

Критические точки – это точки, контролируемые при переходе от процесса к процессу. Для описываемого процесса критическими точками являются:
На сайте allrefs.net читайте: Критические точки – это точки, контролируемые при переходе от процесса к процессу. Для описываемого процесса критическими точками являются:...

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

Устранение слабых сторон заводского технологического процесса, а также снижения трудоемкости и себестоимости технологического процесса механической обработки путем перевода технологического процесса с устаревших моделей оборудования на более современные
Графическая часть содержит 10 листов формата А1, в качестве приложений приведены спецификации на разработанные нами приспособления и… Объектом разработки является технологический процесс механической обработки… Эффективность данного производства, его технический прогресс, качество выпускаемой продукции во многом зависят от…

По курсу Теория информационных процессов и систем
ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ... Московский государственный институт электроники и математики... Технический университет...

Управление взаимодействием процессов в вычислительных сетях. Семиуровневая модель протоколов взаимодействия открытых систем
Компьютерные сети бывают различных видов: например по их масштабу и территории они подразделяются на локальные(LAN) и глобальные(WAN), по уровню… Функции компьютеров, входящих в сеть можно разделить на три вида: •… При этом многообразии характеристик и устройств различных сетей необходимы правила, по которым все составляющие сети…

Понятие и сущность нового уголовного процесса. Сущность уголовного процесса как отрасли права. Принципы уголовного процессуального права Украины
ОДЕССКАЯ ЮРИДИЧЕСКАЯ АКАДЕМИЯ... Экономико правовой факультет в г Симферополе... КАФЕДРА УГОЛОВНО ПРАВОВЫХ ДИСЦИПЛИН...

КОГНИТИВНЫЕ ПРОЦЕССЫ В ПСИХОЛОГИИ. По книге С.С. Магазова «Когнитивные процессы и модели»
Краткая история. В последние годы неуклонно растет интерес к изучению познавательных процессов. До начала 50-х годов вопросы, относящиеся к теории… Первые исследования были посвящены изучению механизмов восприятия. В настоящее… В настоящее время когнитология становится важным объектом исследования, необходимым для решения одной из…

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

Общая характеристика мартеновского процесса. Основной мартеновский процесс и его разновидности
Принцип регенерации тепла был использован Пьером Мартеном для плавки стали. Началом существования мартеновского процесса можно считать 8 апреля… В мартеновскую печь загружают шихту (чугун, скрап, металлический лом и др.),… Уже в начале ХХ в. в мартеновских печах выплавляли половину общего мирового производства стали. В мартеновских печах…

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

0.037
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам