Лекции

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ Н. Э. БАУМАНА

КАФЕДРА СИСТЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ И УПРАВЛЕНИЯ

Черненький В.М.

Описание параллельных процессов

Записал: Гуща А.В.

Москва 2013

1

Содержание

3.1Алгоритмическая модель процесса. АМП . . . . . . . . . . . . . . 17

3.2Структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.3Операторно-параметрические схемы . . . . . . . . . . . . . . . . . 20

3.4Áëîê . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.1Ресурсы. Конфликты за ресурсы . . . . . . . . . . . . . . . . . . . 26

4.2Методы разрешения конфилктов . . . . . . . . . . . . . . . . . . . 26

4.2.1Синхронизация . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.2.2Семафоры . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.2.3Контроллеры . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.3Потоковые схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2

6.2Проверка генераторов случайных чисел . . . . . . . . . . . . . . . 40

6.2.1Проверка на равномерность . . . . . . . . . . . . . . . . . . 40

6.2.2Провека на коррелируемость . . . . . . . . . . . . . . . . . 40

6.3Генерация случайных чисел с произвольным законом распределения 41

3

1Лекция 1. 03.09.2013

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

1.1Понятие процесса

Система - совокупность параметров.

Система ::= P = fP1; P2; :::; P4g

Параметр - имя и его значение.

Pi ::=< èìÿ >< значение >

Введем понятие множества значений параметра - множество значений, которые может принимать параметр:

(p) ::= fp^jg

В нашем случае это множество обычно дискретно и конечно.

Введем понятие пространства состояний системы (многомерное пространство):

n

Y

S ::= (pi) = (p1) (p2)::: (pn)

i=1

Пример:

(a) = f1; 2; 3g

(b) = fx1; x2; x3g

Пространство состояний которых являются 9 точек на двумерной плоскости, на одной оси значения (a), на другой (b).

Точка в пространстве состояний, описывает все значения параметров системы.

4

Вводим понятие времени T - множество моментов времени изменения параметров системы:

T ::= ft1; t2; :::; tk; :::g

Любой ti определяет момент изменения любого параметра системы. Введем понятия графика системы (функциональное соответствие):

F : T ! S

Процесс - это есть кортеж пространства состояний, времени, графика и альфа.

Z ::=< S; T; F; >

n

Y

S ::= (pi)

i=1

T::= ft1; t2; :::; tk; :::g

- линейный порядок на множестве T . Множестов T должно быть линейно

упорядочено. Альфа может быть неявно задано в множестве T , но должно быть задано (иначе моделировать время невозможно).

F : T !f S

Главная проблема - определение параметров системы. Это основная зада- ча моделирования. Далее определеяется множество состояний параметров, пространство состояний, времени.

При дискретном множестве состояний в T входят только моменты измене-

íèÿ состояния системы.

Подпроцесс - часть процесса, плотное (не содержит точки, разбивающие подпроцесс) подмножество процесса.

Объект - подмножество состояния параметров системы.

O P = fP1; P2; :::; P4g

5

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

Разбиение на объекты может быть полным и не полным (есть параметры, которые не входят ни в один объект). Все параметры системы можно отнести к объектам:

Процесс в объекте O:

ZO =< SO; TO; FO; O >

Y

S ::= (pi)

8pi2O

6

FO : TO ! SO

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

Операция свертки процесса - зададим как алгоритм, см рисунок.

.

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

7

Операция развертки Операция синтеза. Обратная операции сверкти. Строит процесс более детальны Z1 по заданному процессу Z2, состояния синтезиру- ются по некоторому заданному закону.

Операция проецирования Проекция процесса, заданного в пространстве состояний, в подпространство состояния (процесс в объекте).

Рисунок...

Z =< S; T; F; >

Zo =< So; To; Fo; o >

Возьмем систему из двух параметров:

P = fa; bg

(a) = f1; 2; 3; 4; 5g

(b) = f ; ; ; ; g

S = (a) (b)

T =< t1; t2; t3; t4; t5; t6; t7 >

F : T ! S

Выделим два объекта:

O1 = fag

O2 = fbg

8

Если нам известен процесс в системе, то мы всегда можем построить процесспроекцию в любом объекте системы.

Суммирование процессов Обратная операция операции проекции. Имеем:

Z1 =< S1; T1; F1; 2 >

Z2 =< S2; T2; F2; 2 >

Получаем:

Z3 = Z1 + Z2

Z3 =< S3; T3; F3; 3 >

S3 = S1 [ S2

T3 = T1 [ T2

F3 = F1F2

Проблемы построения F3 возникает, когда F1 è F2 отображают в одном и òîì æå ti на одну и ту же координату пространства S3 различные значения. Если все оси разные или отображают в разные моменты времени. Если при сложении нет проблем, то операция сложения называется корректной.

Операция сложения всегда корректна при:

Непересекающихся осях пространств S1, S2;

Совпадающих значениях при разных моментах времени;

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

Чтобы построить процесс в системе, строим процесс в объектах и складыва-

åì.

10