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

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

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

Разрешение тупиковых ситуаций при участии оператора. Метод основан на следующей точке зрения: система попадает в тупиковые ситуации достаточно редко, и предусматривать специальные механизмы их разрешения не нужно. В случае возникновения тупиковой ситуации у системы есть оператор, который поможет её разрешить (например, нажав кнопку reset). Плюсом такого подхода является упрощение и ускорение системы. Минусом является то, что программное обеспечение для таких систем должно предусматривать серьёзные механизмы защиты собственных данных на случай возникновения тупика, т.е. вся нагрузка ложится на разработчиков прикладного программного обеспечения (ППУ).

---

5. Задача «о синхронизации стрелков»

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

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

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 до следующего приказа.

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

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

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

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;

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 отображено графическое решение задачи о стрелках.

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

---

Заключение

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

Алгоритм Деккера – первое известное корректное решение проблемывзаимного исключения вконкурентном программировании.Он позволяет двум потокам выполнения совместно использовать неразделяемый ресурс без возникновения конфликтов, используя толькообщую памятьдля коммуникации. Но алгоритм Деккера неудобен в случае использования более 2 процессов, более удобной будет являться его модификация, известная как алгоритм Петерсона. Одним из преимуществ алгоритма является то, что он не требует специальныхTest-and-setинструкций и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Таким образом, данный алгоритм оптимизирует управление работой многозадачных операционных и многопроцессорных вычислительных систем.

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

В ходе работы была решена задача "О синхронизации стрелков". В ней было продемонстрировано взаимодействие двух процессов с помощью семафоров, а именно взаимодействие процесса «офицер» и процесса «стрелки».

Список использованной литературы

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)

---