Доклад. Методы организации взаимного исключения алгоритм Петерсона
 Скачать 51.96 Kb.
|
|
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Уфимский государственный авиационный технический университет» Кафедра ГИС Доклад Дисциплина: «Аппаратное и программное обеспечение вычислительных систем» Тема: «Методы организации взаимного исключения: алгоритм Петерсона» Выполнил: ст. группы ИСТ-111м: Фаридонов А.И. Проверил: к.т.н., доцент Г.И. Рыжов Уфа – 2022 Взаимное исключение (англ. mutual exclusion) — свойство построения параллельных программ, которое используется в целях предотвращения состояния гонки (англ. race condition); Оно требует, чтобы один поток исполнения никогда не входил в критическую секцию одновременно с тем, как другой параллельный поток выполнения вошел в свою критическую секцию. Критическая секция (англ. critical section) — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения. Проблема, с которой связаны взаимные исключения, является проблемой совместного использования ресурсов. Решение этой проблемы — делать доступным общий ресурс только тогда, когда процесс находится в определенном сегменте кода, называемом критической секцией. И контролировать доступ к общему ресурсу, контролируя каждое взаимное выполнение той части программы, в которой будет использоваться ресурс. Успешное решение этой проблемы должно иметь по крайней мере три свойства: Взаимное исключение (англ. mutual exclusion): только один поток может быть в критической секции. Условия прогресса: Отсутствие взаимоблокировок (англ. deadlocks): если несколько потоков пытаются войти в критическую секцию, то хотя бы один из них должен войти в критическую секцию за конечное время. Отсутствие голодания (англ. starvation-freedom): если какой-то поток пытается войти в критическую секцию, то он войдет в критическую секцию за конечное время Порядок перехода между состояниями Если процесс хочет войти в критический раздел, он должен сначала выполнить раздел try и подождать, пока он не получит доступ к критическому разделу. После того, как процесс выполнил свой критический раздел и завершился с общими ресурсами, ему необходимо выполнить раздел выхода, чтобы освободить их для использования другими процессами. Затем процесс возвращается в некритический раздел. Non-Critical Section: Операция находится вне критической секции; этот процесс не использует или не запрашивает общий ресурс. Trying: Процесс пытается войти в критический раздел. Critical Section: В этом разделе разрешен доступ к общему ресурсу. Exit: Процесс выходит из критического раздела и делает доступный общий ресурс другим процессам.  Рисунок 1 - Порядок перехода между состояниями Простейший алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в 1981 г. Хотя изначально был сформулирован для 2-поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Гарантирует взаимное исключение, отсутствие взаимной блокировки и отсутствие голодания.  Корректность алгоритма Взаимное исключение: Потоки 0 и 1 никогда не могут попасть в критическую секцию в один момент времени Таким образом, если оба процесса находятся в критической секции, должно быть want[0] and want[1] and waiting=0 and waiting=1, но такого не может быть одновременно и мы пришли к противоречию. Отсутствие взаимной блокировки Для того, чтобы оба процесса находились в ожидании, необходимы противоположные значения переменной waiting, что невозможно. Отсутствие голодания В алгоритме Петерсона процесс не будет ждать дольше, чем один вход в критическую секцию: после выполнения unlock() и повторного захода в lock() процесс установит себя как ждущего и попадёт в цикл, который не завершится, пока не отработает другой процесс. Обобщение Алгоритм Петерсона для N потоков. Гарантирует взаимное исключение, отсутствие блокировки и отсутствие голодания. Но алгоритм не очень честный. "Невезучий" поток может ждать пока другие потоки O(N2) раз войдут в критическую секцию (квадратичное ожидание). |