Материалы для студентов→ Курсовая работа /

Алгоритм деккера и алгоритм петерсона и их применение для разрешения проблемы критических интервалов. решение задачи «о синхронизации стрелков

Скачать файл
Добавил: fafnir
Размер: 343.44 KB
Добавлен: 30.04.2015
Просмотров: 894
Закачек: 7
Формат: docx

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

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Магнитогорский государственный технический университет 

им. Г.И. Носова»

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

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

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

на тему: «Алгоритм Деккера и алгоритм Петерсона и их применение для 

разрешения проблемы критических интервалов. Решение задачи «О 

синхронизации стрелков»»

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

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

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

         (подпись)

                    

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

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

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


Содержание

2


ВВЕДЕНИЕ

В   определенных   операционных   системах   есть   такие   совместно   работающие     процессы, 

которые сообща могут использовать некоторое общее хранилище данных. У каждого из процессов 

есть   возможность     считывать   что-либо   из   общего   хранилища   данных   и   записывать   туда 

информацию. Хранилище  - это  участок в основной памяти в структуре данных ядра или же файл  

общего доступа. Существуют ситуации, в которых  несколько процессов одновременно считывают 

или записывают данные и в зависимости  от того, какой из них был первым, выводится конечный 

результат. Такие ситуации  называют состояниями состязания.  

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

является предотвращение проблем в этой и любых других ситуациях, которые будут связаны с 

конкурентным использованием памяти и файлов, то есть запрет одновременной записи и чтения 

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

исключение, а именно, в тот момент, когда один процесс использует  общие данные,   другому 

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

исключение, является важным моментом разработки операционной системы.

Проблему   исключения   состояний   состязания   можно     определить   следующим   образом. 

Определенный     интервал  времени  процесс  занят  внутренними  расчетами  и другими  задачами, 

которые не приводят  к состояниям состязания. В другие интервалы времени процесс обращается к 

совместно используемым данным или выполняет любое другое действие, которое может привести 

к состязанию. Фрагмент программы, в которой происходит обращение к совместно используемым 

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

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

избежать состязаний. Поставленное требование исключает состязание, но, несмотря на это, его 

недостаточно для верной совместной работы параллельных процессов и успешного использования 

общих данных. Для этого должны выполняться следующие условия.

1.

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

2.

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

3.

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

других процессов.

4.

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

секцию.

3


Первый,   кто   разработал   программное   решение   проблемы   взаимного   исключения,   которое   не 

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

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

устаревшим. 

4


1. ПРОЦЕССЫ

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

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

выполняемой   задаче.   Процесс   является   основной,   исторически   первой   и   наиболее   известной 

единицей работы вычислительных систем. 

Компоненты   процесса   –   это   выполняющаяся   программа,   ее   данные,  ресурсы     (например 

память) и состояние выполнения.  Обычно, у процесса есть собственное адресное пространство, 

характеризующееся следующей информацией:

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

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

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

• регистры.

Большой   объем   такой   информации   делает   дорогими   операции   создания   и   переключения 

процессов.

                  Потребность   в   легковесных   процессах     появилась   еще   на   однопроцессорных 

вычислительных   машинах,   но   для   использования     на     многопроцессорных   машинах   с   общей 

памятью они стали необходимы. Стоит отметить, что процессы делятся на независимые, то есть не 

требующие   какой-либо   синхронизации   и   обмена   информацией,   и   на   взаимодействующие. 

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

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

Процессы   могут   взаимодействовать   двумя   основными   способами,   если   будет   выполняться 

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

способы:

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

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

При   взаимодействии   через   внешнюю   память   процессы   должны   синхронизовать   свое 

выполнение. Различают два вида синхронизации – взаимное исключение критических интервалов 

5


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

взаимное исключение.

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

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

Критический  интервал (секция) — это объект синхронизации потоков, который позволяет 

предотвратить единовременное  выполнение какого-либо  набора операций несколькими потоками. 

Критический интервал выполняет те же задачи, что и мьютекс. 

Различия   между   мьютексом   и   критическим   интервалом     существуют   лишь 

терминологические, например, захват мьютекса аналогичен процедуре, называющейся входом в 

критический   интервал,   а   снятие   блокировки   мьютекса   аналогично   выходу   из   критического 

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

меньше,   чем   подобные   операции   мьютекса,   это   обуславливается   отсутствием   необходимости 

обращаться к ядру операционной системы.

Разница между критическим интервалом и мьютексом в операционных системах Microsoft 

Windows заключается в том, что мьютекс  - это объект ядра и может использоваться  несколькими 

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

потоков процесса, к которому он принадлежит.

У   критических   интервалов   Windows   существует   оптимизация,   которая   заключается   в 

использовании атомарно изменяемой переменной наряду с объектом «событие синхронизации» 

ядра.   Атомарное   увеличение   переменной   на   1,   называется   захватом   критического   интервала. 

Переход к ожиданию на событии ядра происходит только тогда, когда значение переменной до 

захвата было уже больше 0, то есть происходит реальное «соревнование» двух или более потоков 

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

секции обходятся без обращений к ядру.

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

Принцип взаимоисключения является общим принципом, который положен в основу всех 

механизмов синхронизации процессов.

  Он заключается в следующем: каждый процесс,   который 

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

с ним использования этого ресурса.

6


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

интервалов должны выполняться следующие условия: 

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

процесс;

• любой процесс, который хочет войти в критический интервал, при условии, если на данный 

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

разрешение без какой-либо задержки;

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

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

интервала бесконечно долго; 

Взаимное исключение критических интервалов в однопроцессорной ЭВМ заключается в 

блокировке внешних прерываний (возможно нарушение управления внешними устройствами, 

возможны внутренние прерывания при работе с виртуальной памятью), а так же в блокировке 

переключения на другие процессы, например MONO или MULTI.

Рассмотрим верное поведение процессов на рисунке 1. Процесс А попадает в критическую 

область   в   момент   времени   Т1.   Позже,     в   момент   времени   Т2,   процесс   Б   пытается   попасть   в 

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

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

Поэтому процесс  Б на время переходит в стадию  приостановления, пока процесс А выходит из 

критического интервала (момент времени Т3). Затем процесс  B  покидает критическую область 

(момент времени Т4), и всё возвращается в состояние, когда ни одного процесса в критической 

области не было.

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

7


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

Общим   подходом   к построению   механизмов   синхронизации  

с использованием 

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

Примитив  взаимоисключения – это  программная  конструкция, которая обеспечивает реализацию  

взаимоисключений для параллельных  процессов.

В общем  виде  можно указать два примитива  взаимоисключений:

• примитив вход   взаимоисключения   –   с   его   помощью   фиксируется   захват   критического 

ресурса   данным   процессом   и   устанавливается   запрет   на   использование его другими  

процессами;

• примитив выход взаимоисключения – с его помощью процесс сообщает об освобождении 

им критического ресурса.

Один   из   простых   алгоритмов синхронизации,   где примененяется   примитив взаимоисключения 

состоит в следующем. Главный

 процесс запускает  в работу два параллельных процесса П1 и П2, 

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

работы с критическим ресурсом. Эти области обрамляются примитивами вход_взаимоисключения 

и   выход_взаимоисключения.  

  В случае   с   двумя процессами эти примитивы работают  

следующим образом. После того, как процесс П1 выполняет примитив вход_взаимоисключения и 

при условии, что   процесс П2 находится вне своего критического участка,   П1 входит в свой 

критический участок, выполняет работу с критическим ресурсом, а затем выполняет примитив 

выход_взаимоисключения, то есть показывает, что он вышел из своего критического участка. Если 

П2 находится на своем критическом участке и П1 выполняет вход_взаимоисключения, то процесс 

П1 переводится в состояние ожидания, пока П2 не выполнит выход_взаимоисключения. Лишь 

после этого П1 может выйти из состояния ожидания и войти в свой критический участок.  Если  

вход_взаимоисключения   выполняется   одновременно   двумя   процессами,   то   одному   из   них 

операционная   система   позволяет   продолжить   работу,   а другой   переводит   в   состояние 

ожидания.

 Всю эту схему можно посмотреть на рисунке 2.

8


Рисунок 2 – Схема применения примитивов взаимоисключения

9


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

Алгоритм Деккера является первым известным точным решением взаимного исключения 

без запрещения прерываний. Название алгоритма связано с голландским математиком Теодором 

Деккером,   который   разработал   решение   данной   проблемы.   Алгоритм   позволяет   двум   потокам 

совместно использовать одноразовый ресурс без конфликтов, используя для связи лишь общую 

память.

Алгоритм Деккера имеет следующие ограничения:

1.

Алгоритм рассчитан строго на 2 процесса;

2.

При   ожидании   ресурса,   процессы   впустую   тратят   процессорное   время,   так   как     не 

снимаются с очереди на обслуживание;

3.

При попытке одновременного попадания двух процессов в  критическую секцию, алгоритм 

позволяет войти  лишь одному процессу; 

4.

При   нахождении   одного   из   процессов   в   критической   секции,   другой   процесс   будет 

находиться в ожидании. 

Нужно   отметить,   что   использование   таких   алгоритмов   в   операционной   системе   Реального 

Времени нежелательно, из-за того, что заблокированный процесс не снимается с обслуживания и 

напрасно расходует процессорное время.

Алгоритм   Деккера основан на использовании 3-х переменных:   ПР1 (процесс 1),   ПР2 

(процесс 2) и  ОЧЕРЕДЬ.

1.

Если   первый   процесс   хочет   войти   в   свой   критический   интервал,   то   переменная   ПР2 

принимает значение  TRUE, т.е. значение переменной ОЧЕРЕДЬ   показывает чьё именно 

сейчас право войти в критический интервал.

2.

Если   ПР1=  TRUE,   а   ПР2=FALSE,   то   независимо   от   значения   переменной   ОЧЕРЕДЬ 

исполняется ПР1.

3.

Если ПР1=  TRUE  и ПР2=  TRUE, то дальше исполняется процесс,   который определяется 

значением переменной ОЧЕРЕДЬ.

  Завершив своё исполнение этот процесс сбрасывает флаг своего исполнения в  FALSE  и меняет 

значение переменной ОЧЕРЕДЬ на противоположное. Диапазон значений переменной ОЧЕРЕДЬ 

обычно   колеблется   в   пределах   [0;1]   или   [1;2].   Значение   переменной   ОЧЕРЕДЬ   по   сути   тоже 

является флагом.

10


Begin integer C1,C2, очередь;

C1:=0; C2:=0; очередь=1;

begin

ПРОЦЕСС_1: begin C1:=1;

do while (C2=C1)

 if (очередь=2) then

begin

C1:=0;

do while (очередь=2);

end;

end;

/* Критический участок ПРОЦЕССА_1 */

C1=0;

очередь=2; 

/*Оставшаяся часть процесса*/

end;

ПРОЦЕСС_2: begin C2:=C1;

do while (C1=1);

if (очередь=1) then

begin

C2:=0;

do while (очередь=1);

end;

C2=1;

end;

end;

/* Критический участок ПРОЦЕССА_2 */

C2=0;

очередь=1;

/*Оставшаяся часть процесса*/

end;

end;

11


end.

Алгоритм

 

Деккера

 

обеспечивает взаимное

 

исключение,

 

невозможность 

возникновения deadlock или starvation. (Deadlock – это ситуация, при которой несколько процессов 

находятся   в   состоянии   бесконечного   ожидания   ресурсов,   занятых   самими   этими   процессами; 

starvation – это зависание процессов). 

Одним из преимуществ данного алгоритма является то, что он не требует специальных Test-

and-set инструкций (атомарная операция чтения, модификации и записи),  следовательно, он легко 

переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно 

назвать   его   применимость   к   случаю   только   с   двумя   процессами   и   использование Busy 

waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы 

должны проводить минимальное количество времени внутри критической секции).

Современные операционные системы   обеспечивают примитивы синхронизации более общие и 

гибкие по сравнению с Алгоритмом Деккера. Однако, следует заметить, что в случае отсутствия 

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

выхода из неё будут являться очень действенными при использовании этого алгоритма.

Многие современные микропроцессоры исполняют инструкции не по порядку. Алгоритм не 

будет работать на SMP-машинах (Symmetric Multi Processing – симметричная мультипроцессорная 

обработка), оборудованных такими CPU (central processing unit  - центральное обрабатывающее 

устройство), если не использовать барьеры памяти.

Таким   образом,   алгоритм   Деккера   удобен   в   случаях,   если   используется   ограниченное 

количество   процессов,   с   увеличением   количества   процессов   будет   пропорционально   расти 

количество   используемых   элементов   (Пр1,   ...,   Прn),   а   также   количество   фрагментов   кода, 

разрешения войти в критический участок для каждого из процессов. 

Для упрощения использования алгоритма Деккера в случае нескольких процессов в 1981 

году,   Петерсоном   был   предложен   собственный   алгоритм,   позволяющий   организовать 

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

12


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

Алгоритм   Петерсона   –   это   программный   алгоритм   взаимного   исключения   потоков   без 

запрещения   прерываний.   Он   был     предложен   в  1981   году  Гарри   Петерсоном   из   университета 

Рочестер (США). В основу алгоритма Петерсона лег алгоритм Деккера. Изначально алгоритм был 

сформулирован  для 2-поточного случая, но он может быть обобщен для произвольного количества 

потоков. Алгоритм не основан   на использовании таких команд процессора, которые запрещают 

прерывания, блокировки шины памяти, в нём используются только общие переменные памяти и 

цикл   ожидания   входа   в   критическую   секцию   кода,   поэтому   условно   алгоритм   называют 

программным.    Алгоритм  Петерсона  учитывает  отсутствие   атомарности  в  операциях  чтения   и 

записи переменных и может применяться без использования команд управления прерываниями.

Алгоритм работает следующим образом: у каждого процесса есть своя переменная flag[i] и 

общая переменная turn. Хранение всех переменных происходит в общей памяти. Факт захвата 

ресурса   запоминается   в   переменной   flag   ,   в   переменной   turn   –   номер   захватившего   ресурс 

процесса.

Когда   исполняется   пролог   критической   секции,   процесс   Pi   заявляет   о   готовности   к 

выполнению   критического   участка   и   сразу   предлагает   другому   процессу   приступить   к   его 

выполнению. В случае, когда оба процесса подошли к прологу единовременно, они оба объявят о 

своей готовности и предложат друг другу выполняться. При этом каждое предложение следует 

друг  за другом. Тем самым работу в критическом участке продолжит процесс, которому было 

сделано последнее предложение.

flag[0]  = 0

flag[1]  = 0

turn       = 0

P0: flag[0] = 1                  

 P1: flag[1] = 1

turn = 1                    

 turn = 0

while( flag[1] && turn == 1 );    

 while( flag[0] && turn == 0);

// ожидаем                   

 // ожидаем

// начало критической секции    

 // начало критической секции

  ...                              ...

                

...  

 // её конец

   

 // её конец 

  flag[0] = 0             

                flag[1] = 0

Сначала процесс устанавливает флаг занятости, потом – номер процесса соседа. После этих 

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

если флаг занятости установлен, и номер процесса соответствует номеру соседа.    

13


 Еще один вариант реализации алгоритма Петерсона:

  void mut_excl(int me /* 0 or 1 */)

  {

      static int loser;

      static int interested[2] = {0, 0};

      int other; /* локальная переменная */

       other = 1 - me;

       interested[me] = 1;

       loser = me;

       while (loser == me && interested[other])

           ;

       /* критическая секция*/

       interested[me] = 0;

  }

Алгоритм Петерсона, разработанный в 1981 году, состоит из двух процедур, написанных на С.

#define FALSE 0

#define TRUE 1

#define N 2

int turn; int interested[N];

void enter_region(int process)

{

int other;

other=1-process;

interested[process]=TRUE;

turn=process;

while(turn==process && interested[other]==TRUE)  {   } // Пустой цикл

}

void leave_region(int process)

{

interested[process]=FALSE;

}

При попытке обратиться к критическому ресурсу процесс вызывает функцию enter_regian, 

передавая в неё свой номер. Если критический ресурс в это время уже занят, то функция войдёт в 

так называемый "тугой" цикл ожидания, пока ресурс не будет освобождён. Освобождение ресурса 

14


производится   функцией   leave_regian.   Данный   алгоритм   основан   на   идее,   так   называемого, 

активного ожидания, т.е. на постоянном опросе состояние собственной переменной блокировки во 

время нахождения в "тугом" цикле. Неэффективность главного алгоритма заключается в том, что 

тратится много процессорного времени на режим активного ожидания во время занятости ресурса 

другими процессами. 

 Существуют приёмы синхронизации, позволяющие избежать "активного ожидания":

1.

 Блокировка. Этот механизм используется для управления параллельным доступом к 

ресурсам.   Если   какая-либо   операция   получает   доступ   к   ресурсу,   то   механизм 

блокировки отклоняет попытку получения доступа к этому же ресурсу со стороны 

других процессов или других операций. Наиболее часто в качестве ресурсов в этом 

способе   выступают   данные,   а   сам   механизм   соответственно   применяется   при 

разработке СУБД.

2.

Множественная блокировка. Данный механизм представляет собой использование 

сразу нескольких блокировок по отношению к одному ресурсу. При использовании 

данного   механизма   приходится   учитывать   возможность   возникновения   взаимной 

блокировки.   Это   тупиковая   ситуация,   которая   может   возникнуть,   когда   две 

транзакции   находятся   во   взаимном   ожидании   освобождения   блокировки, 

удерживаемой каждой из них.

  Каждая   система   проводит   собственную   политику   разрешения   тупиковых   ситуаций. 

Существует 3 основных подхода:

Предотвращение возникновения тупиковых ситуаций. Этот подход состоит в том, 

что систему нельзя допускать до опасного состояния, поэтому при создании системой запроса, 

который   может   привести   к   тупику,   система   предпринимает   меры   для   избежания   опасного 

состояния. Принудительно отбирает ресурс у процесса для предотвращения тупиковой ситуации. 

Плюсом   такого   подхода   является   отсутствие   свершившихся   тупиковых   ситуаций.   Минусом   - 

большая   нагрузка   на   диспетчера   системы   и   трата   ресурсов   (не   всегда   обоснованная)   на 

высчитывание потенциальных возможностей тупиковых ситуаций.

Автоматическое обнаружение тупиковых ситуаций.   Данный метод допускает, что 

система   может   попасть   в   тупиковую   ситуацию,   и   для   разрешения   такой   ситуации   в   системе 

присутствует механизм, позволяющий вывести систему из тупика. Этот механизм состоит из двух 

основных частей. I часть отвечает за идентификацию тупиковой ситуации и, в развитых системах, 

15


за классификацию тупика. II часть применяет принудительную политику разрешения тупиковой 

ситуации.   Плюсом   такого   подхода   является   экономия   системных   ресурсов   на   просчитывание 

тупиковых   ситуаций.   Минусом   отсутствие   всех   видов   тупиков   в   имеющемся   механизме 

разрешения.

Разрешение   тупиковых   ситуаций   при   участии   оператора.   Метод   основан   на 

следующей   точке   зрения:   система   попадает   в   тупиковые   ситуации   достаточно   редко,   и 

предусматривать   специальные   механизмы   их   разрешения   не   нужно.   В   случае   возникновения 

тупиковой ситуации у системы есть оператор, который поможет её разрешить (например, нажав 

кнопку   reset).   Плюсом   такого   подхода   является   упрощение   и   ускорение   системы.   Минусом 

является то, что программное обеспечение для таких систем должно предусматривать серьёзные 

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

ложится на разработчиков прикладного программного обеспечения (ППУ). 

16


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

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

Исходные данные для задачи:  имеется цепь стрелков и офицер. Каждый находящийся в 

цепи солдат может общаться только со своими соседями справа и слева. Офицер размещается на 

фланге   цепи   и   может   подавать   команды   только   крайнему   в   цепи   стрелку.   Общее   количество 

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

стрелков цепи после подачи команды офицером. 

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

Данная   задача   решается   при   помощи   автоматной   модели   поведения   стрелка.   В   течение 

работы   программа   –   стрелок   может   находиться   в   одном   из   следующих   состояний:   Сон   (I’m 

sleeping);   Прямой   счет   (My  index  is  *);   Обратный   счет   (I’m  ready);   Открытие   огня   (Fire!).   В 

состояние   прямого   счета   и   обратного   счета   стрелок   переходит   в   случае   изменения   состояния 

соседних  стрелков. В состояние  прямого счета  стрелка переводит  изменение состояния соседа 

слева,   в   состояние   обратного   счета   переводит   изменение   соседа   справа.   Полный   алгоритм 

описывается с помощью автоматной модели, изображенной на рисунке 3.

• q0 – состояние сна «I’m sleeping». Если стрелок левофланговый и получил приказ «Fire!», то

он переходит в следующее состояние – q1 .

• q1 - левофланговый стрелок, при условии существования соседа справа (index+1) (стрелок не 

должен   быть   правофланговым)   запоминает   свой   номер   и   сразу   сообщает   его   правому 

соседу (indexR). Если сосед справа правофланговый !(index+1), то стрелок переходит в 

состояние – q2 .

• если   слева   есть   сосед   (index-1)   (стрелок   не   левофланговый),   то   он   сообщает 

правофланговому стрелку свой номер, и в следующую секунду тот отвечает ему «I’m ready» 

(index-1L) и приступает к обратному счету.

• после   завершения   обратного   отсчёта   (index=0)   стрелок   начинает   стрелять,   после   чего 

переходит в состояние сна q0 до следующего приказа.

17


Рисунок 3 – Автоматная модель поведения стрелка

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

• В данном фрагменте кода создается процесс «стрелки»:

int main(int argc, char* argv[]) {

hWatchdog = CreateSemaphore(NULL, 0, 1, "watchdog");

// запускаем процессы стрелков

for(int i = 0; i < COUNT; i++) {

processes[i] = startProcess(i);

}

• Создание процесса «офицер»:

PROCESS_INFORMATION startProcess(int index) {

std::stringstream ss;

ss << "Rifleman.exe " << index << " " << COUNT;

STARTUPINFO cif;

ZeroMemory(&cif,sizeof(STARTUPINFO));

PROCESS_INFORMATION pi;

18


CreateProcess(NULL, (LPTSTR)ss.str().c_str(), NULL,

NULL, FALSE, CREATE_NEW_CONSOLE,

NULL, NULL, &cif, &pi);

return pi;

}

• Взаимодействие двух процессов – «офицер» и «стрелки»:

HANDLE hFirstRiflemanSemaphore = 

OpenSemaphore(SEMAPHORE_ALL_ACCESS, FALSE, "rifleman0");

ReleaseSemaphore(hFirstRiflemanSemaphore, 1, NULL);

• Уничтожение процесса «стрелки»:

for(int i = 0; i < COUNT; i++) { // завершаем процессы стрелков

TerminateProcess(processes[i].hProcess, NO_ERROR);

}

return 0;

• Уничтожение процесса «офицер»:

while (1) {

...

else if (GetAsyncKeyState(VK_ESCAPE)) {

break;

}

На рисунке 4 отображено графическое решение задачи о стрелках. 

19


Рисунок 4 – Фрагмент работы программы

20


ЗАКЛЮЧЕНИЕ

В   данной   работе   были   освещены   такие   темы,   как   процессы   и   их   взаимодействия, 

критические секции и принцип их взаимоисключения, а так же рассмотрели алгоритм Деккера и 

алгоритм Петерсона. 

Алгоритм   Деккера   –   п

ервое   известное   корректное   решение   проблемы взаимного   исключения 

в конкурентном   программировании. Он   позволяет   двум   потокам   выполнения   совместно 

использовать   неразделяемый   ресурс   без   возникновения   конфликтов,   используя   только общую 

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

процессов, более удобной будет являться его модификация, известная как алгоритм Петерсона. 

Одним   из   преимуществ   алгоритма   является   то,   что   он   не   требует   специальных Test-and-

set инструкций   и   вследствие   этого   он   легко   переносим   на   разные   языки   программирования   и 

архитектуры компьютеров. Таким образом, данный алгоритм оптимизирует управление работой 

многозадачных операционных и многопроцессорных вычислительных систем.

Современные операционные системы предоставляют примитивы синхронизации более общие 

и   гибкие   по  сравнению  с  алгоритмом  Деккера.   Тем   не  менее,  следует  отметить,  что  в  случае 

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

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

В   ходе   работы   была   решена   задача   "О   синхронизации   стрелков".   В   ней   было 

продемонстрировано   взаимодействие   двух   процессов   с   помощью   семафоров,   а   именно 

взаимодействие процесса «офицер» и процесса «стрелки». 

21


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

1. А. О. Ключев, П. В. Кустарев, Д. Р. Ковязина, Е. В. Петров. Программное обеспечение встроенных  

вычислительных систем. Учебное пособие. ИТМО. Санкт-Петербург, 2009. 92-95 с.

2. А. А. Безбогов, А. В. Яковлев, Ю. Ф. Мартемьянов. Безопасность операционных систем. Учебное 

пособие. Издательство «Машиностроение-1». Москва, 2007  

3. Э.   Таненбаум.   Современные   операционные   системы,   2   издание.   Издательство   «Питер».   Санкт-

Петербург, 2002

4. Ю. В. Кочержинская. Курс лекций по дисциплине «Теория вычислительных процессов», 2014г.

5. «Средства

 

коммуникации

 

процессов»

 

-

 

[Электронный

 

ресурс].

 URL: 

http://txt.rushkolnik.ru/docs/index-7896.html  (дата обращения 09.12.2014)

22