Взаимное исключение процессов. Алгоритм Петерсона
 Скачать 188.06 Kb.
|
|
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ БРЯНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра «Информатика и программное обеспечение» РАСЧЁТНО-ГРАФИЧЕСКАЯ РАБОТА по курсу «ОПЕРАЦИОННЫЕ СИСТЕМЫ» Тема: Взаимное исключение процессов. Алгоритм Петерсона. Выполнил студент гр. О-19-МОА-ТП-Б ________________________Зорин К.В. «___»____________2020 г. Руководитель ______________________асс. Коптенок Е.В. «___»____________2020 г. БРЯНСК 2020 СОДЕРЖАНИЕ1.введение 3 2.Реализация алгоритма 4 3.Список использованных источников 7 введениеВ программе был реализован следующий алгоритм операционной системы: Алгоритм Петерсона. Алгоритм Петерсона - алгоритм параллельного программирования для взаимного исключения потоков исполнения кода. Принцип работы алгоритма заключается в том, что перед тем, как начать исполнение критической секции кода, поток должен вызвать специальную процедуру (назовем её enter()) со своим номером в качестве параметра. Она должна организовать ожидание потоком своей очереди входа в критическую секцию. После исполнения критической секции и выхода из неё поток вызывает другую процедуру (назовем её leave()), после чего уже другие потоки смогут войти в критическую область. Изначально был сформулирован для 2-поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Алгоритм условно называется программным, так как не основан на использовании специальных команд процессора для запрета прерываний, блокировки шины памяти и т. д., используются только общие переменные памяти и цикл для ожидания входа в критическую секцию исполняемого кода. . Рассмотрим работу алгоритма: реализация алгоритма Петерсона для n процессов на языке программирования С++. Критическая секция — это часть кода, которая требует исключительного доступа к ресурсам, и одновременно может выполняться только одним потоком. Выбор потока входящего в критическую секцию то же самое, что и выбор потоков, которые будут ждать, если у нас три потока, то нужно отсеять два и оставить один. Отсеивание будет происходить в два этапа: на нулевом этапе отсеивается один из потоков, на первом второй. Переменная flag для потока хранит номер этапа (+ 1), до которого он добрался. Каждая переменная turn соответствует своему этапу и хранит идентификатор последнего потока добравшегося до этого этапа. Поток может перейти к следующему этапу если выполняется хотя бы одно из условий. Нет потоков на том же этапе или впереди него, т. е. поток уже победил - цикл проверяющий значения flag всех потоков отвечает за это условие. Поток - не последний поток на данном этапе, т. е. пришел новый поток и записал в соответствующий turn свой идентификатор - проверка turn в код отвечает за это условие. Порядок входа в критическую секцию заключается в том, что если сразу несколько потоков конкурируют за enter, то в каком порядке они их получат? Нам бы хотелось, чтобы каждый из кандидатов завершил enter рано или поздно, но не хотелось бы, чтобы ожидание завершения enter было не ограниченным, и еще больше не хотелось бы ждать, пока другие входят и выходят из критической секции. Протестируем программу для 3 потоков(Рисунок 1).  Рисунок 1 Так как данный пример отображает всю суть работы алгоритма в последующих теста результат будет аналогичный. Для проверки программы проведем тест для двух потоков (Рисунок 3) и для четырёх потоков(Рисунок 2).  Рисунок 2  Рисунок 3 http://precious-cpp.blogspot.com/2010/10/blog-post.html?m=1 http://precious-cpp.blogspot.com/2010/10/2-n.html?m=1 Э. Таненбаум. Современные операционные системы = Modern Operating Systems. — «Питер», 2004. — С. 1040. — ISBN 5-318-00299-4. https://drive.google.com/file/d/101zfk0XX5avZasyMbs1nwtX6utwOAlGD/view?usp=sharing |