petri
Моделирование параллельных процессов. Сети Петри. Курс для системных архитекторов, программистов, системных аналитиков, проектировщиков сложных систем управления

 

купить в нашем магазине

Фрагменты книги

 

О чем эта книга?

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

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

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

Авторы: Мараховский  В. Б.,  Розенблюм  Л. Я.,  Яковлев  А. В. 

  
 
 Мараховский В. Б.  yakovlev rosenblum

Мараховский Вячеслав Борисович - профессор кафедры «Вычислительные системы и программные технологии»  Института «Информационных технологий и управления» Санкт-Петербургского государственного политехнического университета. С 1993 по 2007 г. – заведующий лаборатории логического проектирования вычислительных устройств, профессор  департамента вычислительной техники университета Айзу (Япония). Является автором и соавтором около 250 научных публикаций,  в том числе  четырех монографий  и 89 изобретений.

Яковлев  Александр Владимирович - лауреат престижного гранта "Исследователя-Мечтателя" (Dream Fellow), финансируемого Британским научно-исследовательским советом по инженерным и физическим наукам (EPSRC), на период 2011-2013 гг. С 1991 года преподает в Университете г. Ньюкасла-на-Тайне, Великобритания, где он является профессором и возглавляет исследовательскую группу по проектированию микроэлектронных систем в Школе Электротехники и Электроники. Доктор технических наук (DSc) от Университета Ньюкасла с 2006 г.  Основные интересы:  моделирование и проектирование асинхронных систем, параллельных процессов, систем с низким потреблением энергии, систем реального времени и высоконадежных систем-на-кристалле.

Розенблюм Леонид Яковлевич -   в течение 20 лет занимался с коллегами наукой и приложениями (например, разработкой новой схемотехники и надежных бортовых компьютеров) в Вычислительном центре Ленинградского отделения Математического института им. Стеклова Академии наук, доцент кафедры математического обеспечения ЭВМ в ЛЭТИ, адъюнкт-профессор в Бостонском университете, исследователь в Гарвардском университете. Соавтор/автор 4 книг, около двух сотен ведомственных изданий, учебных пособий, статей  и обзоров, более 40 авторских свидетельств на изобретения.

Рецензенты:

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

Материалы книги:

     

 

Скачать Оглавление

Скачать фрагмент
главы 1

Скачать фрагмент
главы 2

 

Оглавление

Глава 1. Асинхронный процесс

ГЛАВА 1. АСИНХРОННЫЙ ПРОЦЕСС
1.1. ОПРЕДЕЛЕНИЕ АСИНХРОННОГО ПРОЦЕССА

  • Понятие асинхронности
  • Концепция асинхронного процесса
  • Спецификация асинхронного процесса
  • Протокол асинхронного процесса

1.2. КЛАССИФИКАЦИЯ

  • Автономный асинхронный процесс
  • Эффективный асинхронный процесс
  • Управляемый асинхронный процесс
  • Простой асинхронный процесс

1.3. РЕПОЗИЦИЯ

  • Композиция асинхронного процесса и его репозиции
  • Приведенный асинхронный процесс
  • Конвейерный асинхронный процесс

1.4. СТРУКТУРИРОВАНИЕ
1.5. РЕДУКЦИЯ 

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

1.6. КОМПОЗИЦИЯ

  • Параллельная композиция
  • Последовательная композиция
  • Замыкание

1.7. КОММЕНТАРИЙ. НЕДОСТАТКИ МОДЕЛИ АСИНХРОННОГО ПРОЦЕССА
1.8. УПРАЖНЕНИЯ

Глава 2. Сети Петри

ГЛАВА 2. СЕТИ ПЕТРИ
2.1. РЕТРОСПЕКТИВА СЕТЕЙ ПЕТРИ
2.2. ОПИСАНИЕ МОДЕЛИ
2.3. ДИАГРАММА МАРКИРОВОК

  • Отношения между событиями
  • Сети Петри как модельная интерпретация асинхронных процессов
  • Два начала сетей Петри: статическое и динамическое

2.4. КЛАССИФИКАЦИЯ СЕТЕЙ ПЕТРИ

  • Зачем нужна классификация сетей Петри 
  • Классификация по динамическим ограничениям
  • Классификация по статическим ограничениям

2.5. ЗАДАЧИ И АЛГОРИТМЫ АНАЛИЗА
2.5.1. Первая группа методов анализа

  • Задача достижимости
  • Модификации задачи достижимости
  • Алгоритм порождения диаграммы маркировок
  • Свойства диаграмм маркировок
  • Сводимость задач достижимости
  • Задача живости Сети Петри

2.5.2. Вторая группа методов анализа
2.5.3. Третья группа методов анализа

  • Дедлоки
  • Ловушки

2.5.4. Оценки вычислительной сложности проблем анализа сетей Петри
2.6. АНАЛИЗ: МАТРИЧНЫЙ ПОДХОД

  • Анализ на свойства структурной ограниченности и живости
  • Инвариантные и согласованные сети Петри
  • Решение задачи достижимости

2.7. ФУНКЦИОНАЛЬНЫЕ ВОЗМОЖНОСТИ

  • Сведения из теории формальных грамматик и языков
  • Генерирование формальных языков сетями Петри

2.8. ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ. ИНТЕРПРЕТАЦИЯ СЕТЕЙ ПЕТРИ

  • Пример спецификации конечного автомата сетью Петри
  • Использование сетей Петри в параллельном программировании
  • Пример моделирования аппаратных средств
  • Моделирование конвейерных процессов

2.9. УПРАЖНЕНИЯ

Глава 3. Другие сетевые модели, родственные Сетям Петри

3.1. СЕТИ СО ВЗВЕШЕННЫМИ ДУГАМИ

  • Преобразование сети с взвешенными дугами в ординарную сеть Петри
  • Пример спецификации химической реакции сетью с взвешенными дугами
  • Проверка отсутствия маркера в некоторой позиции

3.2. РАСКРАШЕННЫЕ СЕТИ
3.3. СЕТИ С ТОРМОЗЯЩИМИ ДУГАМИ (ИНГИБИТОРНЫЕ СЕТИ ПЕТРИ)
3.4. ПРИОРИТЕТНЫЕ И ВРЕМЕННЫЕ СЕТИ
3.5. СИНХРОННЫЕ И САМОМОДИФИЦИРУЕМЫЕ СЕТИ
3.6. СТОХАСТИЧЕСКИЕ СЕТИ ПЕТРИ
3.7. ОЦЕНОЧНЫЕ СЕТИ

  • Примитивы оценочных сетей
  • Мотивы появления оценочных сетей

3.8. СЕТИ ПОТОКОВ ДАННЫХ
3.9. РАЗРЕШИМОСТЬ ЗАДАЧ АНАЛИЗА
3.10. УПРАЖНЕНИЯ

Глава 4. Динамическая логика

4.1. ДИАГРАММЫ ПЕРЕХОДОВ И ИХ КЛАССИФИКАЦИЯ

  • Состояния бинарной диаграммы переходов
  • Бифуркантное состояние
  • Классы диаграмм переходов

4.2. СХЕМЫ МАЛЛЕРА

  • Гипотезы о задержках в логических элементах и проводах
  • Самосинхронные схемы
  • Диаграммы Маллера
  • Понятие динамической логики
  • Задача построения рабочего цикла

4.3. МАРКИРОВАННЫЕ ГРАФЫ
4.4. СИГНАЛЬНЫЕ ГРАФЫ

  • Построение кумулятивной диаграммы по маркированному графу
  • Свойства кумулятивных диаграмм
  • Связь сигнальных графов с диаграммами переходов
  • Нормальность сигнального графа
  • Понятия одновременности и предшествования сигналов
  • Анализ сигнального графа на свойства регулярности и нормальности

4.5. УПРАЖНЕНИЯ

Глава 5. Параллельное программирование

ГЛАВА 5. ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ. ЗАДАЧИ КООРДИНАЦИИ И СИНХРОНИЗАЦИИ ВЗАИМОДЕЙСТВУЮЩИХ ПРОЦЕССОВ

5.1. АНОМАЛИИ ДИНАМИКИ

  • Поведенческий и структурный дедлоки
  • Эффект “каннибализма”
  • Эффект “голодной смерти”
  • Свойства “справедливости” и “голодания”

5.2. ЗАДАЧА ОБ ОБЕДАЮЩИХ ФИЛОСОФАХ
5.3. ЗАДАЧИ ВЗАИМНОГО ИСКЛЮЧЕНИЯ И СЕМАФОРЫ

  • Семафоры Дейкстры
  • Семафоры Цикритзиса и Бринч-Хансена
  • Семафоры Агервалы и Вентилборга

5.4. ЗАДАЧА “ПРОИЗВОДИТЕЛИ – ПОТРЕБИТЕЛИ”

  • Фрагмент спецификации Г. Дейтела
  • Программа Д. Цикритзиса и Ф. Бернстайна

5.5. ЗАДАЧА “ЧИТАТЕЛИ – ПИСАТЕЛИ”
5.6. ЗАДАЧА О КУРИЛЬЩИКАХ
5.7. МЕХАНИЗМ РАНДЕВУ
5.8. СЕМАНТИКА ВЗАИМОДЕЙСТВУЮЩИХ ПРОЦЕССОВ

  • Пошаговая детализация действий программ
  • Взаимные переходы между двумя формами семантик
  • Проверка условий справедливого решения конфликта
  • Выводы

5.9. ЗАКЛЮЧЕНИЕ
5.10. УПРАЖНЕНИЯ

Глава 6. Принципы аппаратной реализации

6.1. ОСОБЕННОСТИ САМОСИНХРОННОЙ СХЕМОТЕХНИКИ
6.2. СИНТЕЗ ПО МОДЕЛИ МАЛЛЕРА

  • Редукция диаграммы переходов
  • Кратные состояния
  • Проверка спецификации на полумодулярность
  • Проекции диаграмм переходов
  • Устранение противоречивости диаграмм переходов
  • Свойства логических переменных полумодулярных диаграмм переходов
  • Стандартные реализации самозависимых переменных
  • Метод совершенной реализации схемы Маллера 5

6.3. СТАНДАРТНЫЕ РЕАЛИЗАЦИИ ФРАГМЕНТОВ СЕТЕЙ ПЕТРИ

  • Реализация многовходовых C-элементов Маллера
  • Моделирование продвижения маркера в сети Петри элементом Давида
  • Прямая трансляция сетей Петри в логические схемы
  • Минимальный базис реализации сетей Петри методом прямой трансляции

6.4. ПРИНЦИПЫ КОМПОЗИЦИИ
6.4.1. Дополнительные модули

  • Модуль преобразования фазовой дисциплины
  • Модуль многократного вхождения оператора
  • Модуль управления циклом

6.4.2. Реализация неустойчивых сетей Петри

  • Реализация сетей Петри с вершинами свободного выбора
  • Явление электронного арбитража
  • Электронные арбитры
  • Ограниченные арбитры
  • Неограниченные арбитры
  • Реализация неустойчивых ограниченных сетей Петри

6.5. УПРАЖНЕНИЯ

Глава 7. Протоколы информационного обмена

7.1. КЛАССИФИКАЦИЯ ИНТЕРФЕЙСОВ
  7.1.1. Классификация по топологии

  • Интерфейсы с кольцевой структурой
  • Интерфейсы с радиальной структурой
  • Интерфейсы с магистральной структурой
  • Интерфейсы со смешанной структурой

  7.1.2. Классификация по способу передачи данных
  7.1.3. Классификация по принципу реализации

  • Синхронные интерфейсы
  • Асинхронные интерфейсы
  • Самосинхронные интерфейсы

  7.1.4. Классификация интерфейсов по назначению
7.2. ЗАДАНИЕ ПРОТОКОЛОВ
  7.2.1. Протокол чтения данных в интерфейсе «Общая шина»
  7.2.2. Примерная процедура проектирования протокола
  7.2.3. Разработка описания протокола, его анализа и  реализации.

  • Оценка сложности аппаратной и программной поддержки протокола
  • Сервисный уровень протокола
  • Построение структурной модели интерфейсного протокола
  • Формализация описания интерфейсного протокола
  • Синтез средств сопряжения
  • Реализация протоколов

  7.2.4. Формальная модель протокола информационного обмена физического уровня
  7.2.5. Пример использования сети Петри для задания протокола обмена
7.3. ВЕРИФИКАЦИЯ ПРОТОКОЛОВ
  7.3.1. Верификация эффектов взаимодействия

  • Выбор способа анализа протокола
  • Выбор совокупности желаемых эффектов

  7.3.2. Выявление свойств протоколов

  • Анализ асинхронного протокола «чередующегося бита»
  • Модель с идеальным каналом
  • Модель с искажением сообщения в канале
  • Модель с потерей сообщений
  • Модель с ложным срабатыванием механизма таймаута
  • Модель без ограничений на емкость канала и число срабатываний таймаута
  • Модель с буферированным каналом

  7.3.3. Описание протоколов сигнальными графами и диаграммами переходов
7.4. УПРАЖНЕНИЯ

Глава 8. Примеры решения прикладных задач

8.1. ЛОГИЧЕСКОЕ УПРАВЛЕНИЕ

  • Первый пример — "Управление манипулятором"
  • Второй пример — "Управление движением вагонеток"

8.2. ПРОТОКОЛЫ АСИНХРОННЫХ СХЕМ
8.3 ИНФОРМАЦИОННЫЙ ОБМЕН
8.4. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ

  • Пример 1
  • Пример 2

8.5. УПРАЖНЕНИЯ

 

 

купить в нашем магазине