Файл: Курсовая работа по ТВП. Шишиморов Александр.docx

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Магнитогорский государственный технический университет им. Г.И. Носова»

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

Курсовая работа

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

на тему: «Алгоритм Деккера и алгоритм Петерсона и их применение для разрешения проблемы критических интервалов. Решение задачи «О синхронизации стрелков»»

Исполнитель: Шишиморов А. П., студент 2 курса, группа ЭАВбп-13

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

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

(подпись)

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

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

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

Содержание

ВВЕДЕНИЕ 3

1.ПРОЦЕССЫ 5

1.1Основные понятия о процессах 5

1.2Взаимодействие процессов. 5

2.КРИТИЧЕСКИЕ ИНТЕРВАЛЫ 6

2.1Понятие критических интервалов 6

2.2Взаимное исключение критических интервалов 6

2.2.1Примитив взаимоисключения 8

3.АЛГОРИТМ ДЕККЕРА 10

4.АЛГОРИТМ ПЕТЕРСОНА 13

5.ЗАДАЧА «О СИНХРОНИЗАЦИИ СТРЕЛКОВ» 17

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

5.2 Алгоритм решения задачи 17

5.3 Программная реализация задачи 18

ЗАКЛЮЧЕНИЕ 20

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 21

Введение

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

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

---

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

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

2. В программе недопустимы предположения о скорости или количестве процессоров.

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

4. Недопустима ситуация, в которой процесс постоянно ждет попадания в критическую секцию.

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

---

1. Процессы

   1. Основные понятия о процессах

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

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

• таблицы страниц или сегментов;

• дескрипторы файлов;

• заказы на ввод-вывод;

• регистры.

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

2. Взаимодействие процессов.

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

• посредством разделения внешней или оперативной памяти;

• посредством передачи сообщений.

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

2. Критические интервалы

   1. Понятие критических интервалов

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

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

---

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

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

---

2. Взаимное исключение критических интервалов

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

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

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

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

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

Взаимное исключение критических интервалов в однопроцессорной ЭВМ заключается в блокировке внешних прерываний (возможно нарушение управления внешними устройствами, возможны внутренние прерывания при работе с виртуальной памятью), а так же в блокировке переключения на другие процессы, например MONO или MULTI.

Рассмотрим верное поведение процессов на рисунке 1. Процесс А попадает в критическую область в момент времени Т1. Позже, в момент времени Т2, процесс Б пытается попасть в критическую область, но в связи с тем, что в критической области уже находится процесс А, ему это не удается, так как два процесса не могут одновременно находиться в критических областях. Поэтому процесс Б на время переходит в стадию приостановления, пока процесс А выходит из критического интервала (момент времени Т3). Затем процесс B покидает критическую область (момент времени Т4), и всё возвращается в состояние, когда ни одного процесса в критической области не было.

Рисунок 1 – Взаимное исключение с использованием критических интервалов

1. Примитив взаимоисключения

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

---