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

У каждого из процессов есть возможность считывать что-либо из общего хранилища данных и записывать туда информацию. Для того чтобы избежать состязания существуют различные способы, одним из основных является предотвращение проблем в этой и любых других ситуациях, которые будут связаны с конкурентным использованием памяти и файлов, то есть запрет одновременной записи и чтения разделяемых данных более чем одним процессом. Другими словами, требуется взаимное исключение, а именно, в тот момент, когда один процесс использует общие данные, другому процессу это делать будет запрещено. Определенный интервал времени процесс занят внутренними расчетами и другими задачами, которые не приводят к состояниям состязания. В случае, если получится избежать одновременного нахождения двух и более процессов в критических областях, удастся избежать состязаний.Вычислительный процесс - это абстрактный системный объект, который соответствует выполняемой задаче. Процесс является основной, исторически первой и наиболее известной единицей работы вычислительных систем. Обычно, у процесса есть собственное адресное пространство, характеризующееся следующей информацией: таблицы страниц или сегментов;Процессы могут взаимодействовать двумя основными способами, если будет выполняться условие того, что приложение реализовано в виде множества данных процессов. Рассмотрим эти способы: посредством разделения внешней или оперативной памяти;Критический интервал (секция) - это объект синхронизации потоков, который позволяет предотвратить единовременное выполнение какого-либо набора операций несколькими потоками. Различия между мьютексом и критическим интервалом существуют лишь терминологические, например, захват мьютекса аналогичен процедуре, называющейся входом в критический интервал, а снятие блокировки мьютекса аналогично выходу из критического интервала. Разница между критическим интервалом и мьютексом в операционных системах Microsoft Windows заключается в том, что мьютекс - это объект ядра и может использоваться несколькими процессами одновременно, а критический интервал служит для синхронизации только тех потоков процесса, к которому он принадлежит.Он заключается в следующем: каждый процесс, который обращает к критическим ресурсам, должен запретить для всех других процессов одновременного с ним использования этого ресурса. Для того чтобы было найдено решение проблемы взаимного исключения критических интервалов должны выполняться следующие условия: внутри критического интервала во всякий момент времени может находиться только один процесс; любой процесс, который хочет войти в критический интервал, при условии, если на данный момент времени ни один процесс не находится в критическом интервале, должен получить разрешение без какой-либо задержки; не один процесс не должен бесконечно долго ждать разрешения на вход в критический интервал, при условии, если ни один процесс не будет находиться внутри критического интервала бесконечно долго;В общем виде можно указать два примитива взаимоисключений: примитив вход взаимоисключения - с его помощью фиксируется захват критического ресурса данным процессом и устанавливается запрет на использование его другими процессами; примитив выход взаимоисключения - с его помощью процесс сообщает об освобождении им критического ресурса. Эти области обрамляются примитивами вход_взаимоисключения и выход_взаимоисключения. После того, как процесс П1 выполняет примитив вход_взаимоисключения и при условии, что процесс П2 находится вне своего критического участка, П1 входит в свой критический участок, выполняет работу с критическим ресурсом, а затем выполняет примитив выход_взаимоисключения, то есть показывает, что он вышел из своего критического участка. Если П2 находится на своем критическом участке и П1 выполняет вход_взаимоисключения, то процесс П1 переводится в состояние ожидания, пока П2 не выполнит выход_взаимоисключения.Алгоритм Деккера имеет следующие ограничения: Алгоритм рассчитан строго на 2 процесса; При попытке одновременного попадания двух процессов в критическую секцию, алгоритм позволяет войти лишь одному процессу; При нахождении одного из процессов в критической секции, другой процесс будет находиться в ожидании. Алгоритм Деккера основан на использовании 3-х переменных: ПР1 (процесс 1), ПР2 (процесс 2) и ОЧЕРЕДЬ. Если первый процесс хочет войти в свой критический интервал, то переменная ПР2 принимает значение TRUE, т.е. значение переменной ОЧЕРЕДЬ показывает чье именно сейчас право войти в критический интервал.Алгоритм не основан на использовании таких команд процессора, которые запрещают прерывания, блокировки шины памяти, в нем используются только общие переменные памяти и цикл ожидания входа в критическую секцию кода, поэтому условно алгоритм называют программным. Алгоритм работает следующим образом: у каждого процесса есть своя переменная flag[i] и общая переменная turn. Когда исполняется пролог критической секции, процесс Pi заявляет о готовности к выполнению критического участка и сразу предлагает др

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1.ПРОЦЕССЫ

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ процесс критический интервал алгоритм