Алгоритмическое решение задачи с использованием сетей Петри

КУРСОВАЯ РАБОТА

по дисциплине: «Теория вычислительных процессов»

на тему: «Применение семафорных механизмов в решении задач

синхронизации. Решение задачи «Об обедающих философах»

Исполнитель: Катаев А. Г., студент 2 курса, группа АВп-14

Руководитель: Кочержинская Ю. В., к.т.н., доцент кафедры ВТиП

Работа допущена к защите "_____" _________ 2015г. ______________

(подпись)

Работа защищена "_____" _______ 2015г. с оценкой ______ _______

(оценка) (подпись)

Магнитогорск, 2015

За курсовой в вк https://vk.com/kataevaleksandr
За курсовой в вк https://vk.com/kataevaleksandr

За курсовой в вк https://vk.com/kataevaleksandr

Содержание

АННОТАЦИЯ 4

ВВЕДЕНИЕ 5

1. ТЕОРИТИЧЕСКИЙ ВОПРОС 7

1.1. Семафор Дейкстры 7

1.1.1. Основные понятия 7

1.1.2. Двоичный семафор 7

1.1.3. Семафоры общего вида 8

1.1.4. Создание семафора 8

1.2. Семафоры и прерывания 10

1.3. Мьютекс 11

1.3.1. Создание мьютекса 11

1.4. Мёртвая блокировка (Deadlock) 13

2. ПРАКТИЧЕСКАЯ ЧАСТЬ 14

2.1. Постановка задачи 14

2.2. Алгоритмическое решение задачи с использованием сетей Петри 15

2.3. Решение задачи в программных кодах 15

2.3.1. Программный код приложения «Философ» 15

2.3.2 Программный код приложения «Стол» 18

2.4. Пример работы программы 22

2.5. Выводы по практической части 23

ЗАКЛЮЧЕНИЕ 24

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 25

АННОТАЦИЯ

В данной курсовой работе рассмотрены методы применения семафорных механизмов в решении задач синхронизации. Объем работы 25 страниц, на которых размещены шесть рисунков и одна таблица, 2 раздела: теоретическая часть и практическая. При написании курсовой работы было использовано пять источников информации.

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

ВВЕДЕНИЕ

Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году. Он предложил использовать переменные, которые могут принимать целые неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, получили название семафоров.

Семафор начинает действовать с назначенного для него начального отсчета. Всякий раз, когда поток получает права владения эти объектом (через функцию ожидания), счетчик в семафоре уменьшается на единицу. И всякий раз, когда поток уступает свои права владения объектом владения этим объектом, счетчик в семафоре увеличивается на единицу. Как только счетчик в семафоре достигнет нуля, семафор блокируется в несигнальном состоянии и ни один из потоков не может получить к нему доступ.

Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р (от датского слова proberen — проверять) и V (от verhogen увеличивать). Пусть переменная S представляет собой семафор. Тогда классическое определение действия V(S) и P(S) операций выглядит следующим образом:

P(S):	ЕСЛИ S = 0 ТО процесс блокируется; ИНАЧЕ S = S – 1;
V(S):	S = S + 1;

Эта запись означает следующее:

- при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1.

Если оно меньше или равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1. Успешная проверка и уменьшение являются неделимой операцией.

- при выполнении операции V над семафором S к его значению просто прибавляется 1. Во время выполнения этой операции к переменной S нет досту…..

ПРАКТИЧЕСКАЯ ЧАСТЬ

Постановка задачи

Исходные данные для задачи: представим себе парк, по аллеям которого прогуливаются N философов. В центре парка расположена столовая, в которой накрыт круглый стол. В центре стола стоит миска с рисом, а вокруг неё расположены N тарелок и N палочек. Если философ проголодался (это происходит за определенный промежуток времени для каждого философа), он входит в столовую, занимает свободное место за столом, накладывает себе в тарелку рис, берет две палочки и принимается за еду. Затем философ некоторое неопределённое время кушает. Утолив голод, философ возвращает палочки на стол и покидает столовую. В случае если все N философов одновременно придут в столовую, займут все места за столом и возьмут по палочке, система окажется заблокированной, т.к. ни один из философов не сможет приступить к еде.

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

Алгоритмическое решение задачи с использованием сетей Петри - student2.ru Схематическое изображение задачи − Рисунок 2