Автор: Пользователь скрыл имя, 10 Мая 2012 в 22:51, курсовая работа
Алгоритм - точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время.
Процессы - выполнение пассивных инструкций компьютерной программы на процессоре ЭВМ.
Введение……………………………………………………………………...
Принцип взаимоисключения ……………………………………………….
Примитив взаимоисключения………………………………………………
Взаимодействие и взаимоисключение процессов…………………………
Варианты программного решения проблемы взаимоисключения……….
Правильное решение проблемы взаимоисключения……………………..
Алгоритм Деккера…………………………………………………………...
Доказательство правильности алгоритма Деккера......................................
Заключение…………………………………………………………………..
Список используемой литературы………………………………………...
Рис. 5.1. Попытки взаимных исключений
Проблема при первой попытке
заключается в том, что в ней
хранилось имя процесса, который
имел право входа в критический
раздел, в то время как в действительности
нам требуется информация об обоих процессах.
По сути, каждый процесс должен иметь собственный
ключ к критическому разделу, так что если
даже произойдет сбой одного процесса,
второй все равно сможет получить доступ
к критическому разделу. Для удовлетворения
этого условия определен логический вектор
flag, в котором flag[0] соответствует процессу
Р0, a flag[l] — процессу P1. Каждый процесс
может ознакомиться с флагом другого процесса,
но не может его изменить. Когда процессу
требуется войти в критический раздел,
он периодически проверяет состояние
флага другого процесса до тех пор, пока
тот не примет значение false, указывающее,
что другой процесс покинул критический
раздел. Процесс немедленно устанавливает
значение своего собственного флага равным
true и входит в критический раздел. По выходе
из критического раздела процесс сбрасывает
свой флаг, присваивая ему значение true.
Теперь разделяемые переменные выглядят
следующим образом:
enum boolean { false = 0, true = 1; };
boolean flag[2] = { false, false };
Этот алгоритм показан на рис. 5.1,b.
Теперь если произойдет сбой одного из
процессов вне критического раздела
(включая код установки
Описанное решение, по сути, оказывается
еще хуже предложенного ранее, поскольку
даже не гарантирует взаимного
Р0 выполняет инструкцию while и находит,
что значение flag[l] равно false;
P1 выполняет инструкцию while и находит,
что значение flag[0] равно false;
Р0 устанавливает значение flag [0] равным
true и входит в критический раздел;
Р1 устанавливает значение flag [1] равным
true и входит в критический раздел.
Поскольку после этого оба процесса одновременно оказываются в критическом разделе, программа некорректна. Проблема заключается в том, что предложенное решение не является независимым от относительной скорости выполнения процессов.
Поскольку процесс может изменить
свое состояние после того, как
другой процесс ознакомится с
ним, но до того, как этот другой процесс
войдет в критический раздел, вторая
попытка также оказалась
Как и ранее, если происходит сбой одного процесса в критическом разделе, включая код установки значения флага, то второй процесс окажется заблокированным (и соответственно, если сбой произойдет вне критического раздела, то второй процесс блокирован не будет).
Далее проверим гарантированность
взаимоисключения, проследив за процессом
Р0. После того как процесс Р0 установит
flag[0] равным true, P1 не может войти в критический
раздел до тех пор, пока туда не войдет
и затем не покинет его процесс Р0. Может
оказаться так, что процесс Р1 уже находится
в критическом разделе в тот момент, когда
Р0 устанавливает свой флаг. В этом случае
процесс Р0 будет заблокирован инструкцией
while до тех пор, пока Р1 не покинет критический
раздел. Аналогичные действия происходят
при рассмотрении процесса Р1.
Тем самым гарантируется взаимное исключение;
однако третья попытка порождает еще одну
проблему. Если оба процесса установят
значения флагов равными true до того, как
один из них выполнит инструкцию while, то
каждый из процессов будет считать, что
другой находится в критическом разделе,
и тем самым осуществится взаимоблокировка.
В третьей попытке установка
процессом флага состояния
Это уже совсем близко к корректному решению, хотя все еще и неверно, Взаимоисключение гарантируется (в чем можно убедиться, применяя те же рассуждения, что и при третьей попытке), однако рассмотрим возможную последовательность событий:
Р0 устанавливает значение flag[0] равным
true;
P1 устанавливает значение flag[l] равным
true;
Р0 проверяет f lag [ 1 ];
P1 проверяет flag [0];
Р0 устанавливает значение flag[0] равным
false;
P1 устанавливает значение flag[l] равным
false;
Р1 устанавливает значение flag[0] равным
true;
P1 устанавливает значение flag[l] равным
true.
Эту последовательность можно продолжать
до бесконечности и ни один из процессов
до бесконечности так и не сможет
войти в критический раздел. Строго
говоря, это не взаимоблокировка, так
как любое изменение
Хотя описанный сценарий маловероятен
и вряд ли такая последовательность продлится
сколь-нибудь долго, тем не менее теоретически
такая возможность имеется. Поэтому мы
вынуждены отвергнуть как неудачную и
четвертую попытку.
У нас должна быть возможность следить за состоянием обоих процессов, что обеспечивается массивом flag. Но, как показала четвертая попытка, этого недостаточно. Мы должны навязать определенный порядок действий двум процессам, чтобы избежать проблемы "взаимной вежливости", с которой только что столкнулись. С этой целью можно использовать переменную turn из первой попытки. В нашем случае эта переменная указывает, какой из процессов имеет право на вход в критический раздел.
Мы можем описать это решение следующим образом. Когда процесс Р0 намерен войти в критический раздел, он устанавливает свой флаг равным true,-а затем проверяет состояние флага процесса Р1. Если он равен false, Р0 может немедленно входить в критический раздел; в противном случае Р0 обращается к переменной turn. Если turn = 0, это означает, что сейчас — очередь процесса Р0 на вход в критический раздел, и Р0 периодически проверяет состояние флага процесса Р1. Этот процесс, в свою очередь, в некоторый момент времени обнаруживает, что сейчас не его очередь для входа в критический раздел, и устанавливает свой флаг равным false, давая возможность процессу Р0 войти в критический раздел. После того как Р0 выйдет из критического раздела, он установит свой флаг равным false для освобождения критического раздела и присвоит переменной turn значение 1 для передачи прав на вход в критический раздел процессу Р1.
boolean flag [2] ;
int turn;
void Р0 ()
{
while(true)
{
flag[0] = true;
while(flag[l])
if (turn == 1)
{
flag[0] = false;
while(turn == 1)
/* Ничего не делать */;
flag[0] = true;
}
/* Критический раздел */;
turn = 1;
flag[0] = false;
/* Остальной код */;
}
}
void P1()
{
while(true)
{
flag[l] = true;
while(flag[0])
if (turn == 0)
{
flag[l] = false;
while(turn == 0)
/* Ничего не делать */;
flag[l] = true;
}
/* Критический раздел */;
turn = 0;
flagfl] = false;
/* Остальной код */;
}
}
void main()
{
flag[0] = false;
flagfl] = false;
turn = 1;
parbegin(PO,PI);
}
Межпроцессное взаимодействие — набор способов обмена данными между множеством потоков в одном или более процессах. Процессы могут быть запущены на одном или более компьютерах, связанных между собой сетью. IPC-способы делятся на методы обмена сообщениями, синхронизации, разделяемой памяти и удаленных вызовов (RPC). ) Он позволяет двум потокам выполнения совместно использовать неразделяемый ресурс без возникновения конфликтов, используя только общую память для коммуникации.
Алгоритм
Деккера гарантирует взаимное исключение,
невозможность возникновения deadlock или starvation. Рассмотрим, почему справедливо
последнее свойство. Предположим, что
p0 остался внутри цикла «while flag[1]» навсегда.
Поскольку взаимная блокировка произойти
не может, рано или поздно p1 достигнет
своей критической секции и установит turn = 0 (значение turn будет оставаться постоянным пока p0 не
продвигается). p0 выйдет из внутреннего
цикла «while turn ≠ 0» (если он там находился).
После этого он присвоит flag[0] значение
true и будет ждать, пока flag[1] примет значение false (так как turn = 0, он никогда не выполняет
действия в цикле «while»). В следующий раз
когда p1 попытается войти в критическую
секцию, он будет вынужден исполнить действия
в цикле «while flag[0]». В частности, он присвоит flag[1] значение fals
Если модифицировать алгоритм так, чтобы действия в цикле «while flag[1]» выполнялись без проверки условия «turn = 0», то появится возможность starvation. Таким образом, все шаги алгоритма являются необходимыми.
Одним из преимуществ алгоритма
является то, что он не требует специальных Test-and-
Алгоритм Деккера гарантирует корректное решение проблемы взаимоисключения для двух потоков. Управляющие переменные ResourceThread1, ResourceThread1 обеспечивают взаимоисключение, переменная ThreadNum исключает возможность бесконечного откладывания. Если оба потока пытаются получить доступ к ресурсу, то поток, номер которого указан в ThreadNum, продолжает проверку возможности доступа к ресурсу (внешний цикл ожидания ресурса). Другой же поток в этом случае снимает свой запрос на ресурс, ожидает своей очереди доступа к ресурсу (внутренний цикл ожидания) и возобновляет свой запрос на ресурс.
Алгоритм Деккера может быть обобщен на случай произвольного количества потоков, однако такое обобщение приводит к заметному усложнению выполняемых действий. Кроме того, программное решение проблемы взаимоисключения потоков приводит к нерациональному использованию процессорного времени ЭВМ (потоку, ожидающему освобождения ресурса, постоянно требуется процессор для проверки возможности про-должения – активное ожидание (busy wait)).
Алгоритм учитывает следующие требования:
Заключение.
В ходе работы я ознакомилась с критическим разделом для двух процессов.
Проделав несколько вариантов программного решения проблемы взаимоисключения, я не получила нужного результата. Эти попытки привели меня к решению использовать алгоритм Деккера. Алгоритм Деккера это первое известное корректное решение проблемы взаимного исключения в конкурентном программировании. Этот алгоритм действительно решает данную проблему и гарантирует взаимное исключение.
Список используемой литература
Информация о работе Исследование алгоритмов (модель) взаимоисключения для двух процессов