Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Алгоритм Деккера и ПетерсонаСтр 1 из 3Следующая ⇒
Алгоритм Деккера и Петерсона Взаимоисключение - возможность одному процессу приостановить остальные.
Критическая секция - участок кода, в котором должен находиться только один процесс.
Собственно алгоритм:
shared int ready[2] = {0,0}; // готовность ко входу shared int turn; // чья очередь
while (условие) { // пролог ready[i] = 1; // сообщаем о желании войти в КС turn = 1 - i; // даем возможность входа другому процессу while(ready[i-1] && (turn == 1-i)) ; // если очередь оказалась не нашей, ждем пока он не выйдет из КС // критическая секция ... // эпилог ready[i] = 0; // сообщаем о выходе из КС }
Требования к программной реализации:
• Не используется аппаратная поддержка
• Нет предположений о скорости процессоров и их количестве
• В критической секции только один процесс
• Условие ограниченного ожидания - если один процесс решил войти в свою критическую секцию, это не должно продолжаться неограниченно долго.
Для большего числа процессов используется алгоритм булочной, заключающийся в выдаче номерков. Механизм синхронизации. Семафоры. В 1965 разработан Дейкстрой (Dijkstra). Семафор - представляет из себяя целочисленную переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента её инициализации осуществляется только через две атомарные операции: • P(S) -- операция пролога критической секции – Пока S=0 процесс блокируется – Когда S>0, S=S-1 • V(S) -- операция эпилога критической секции – S = S +1 Операция V атомарна автоматически, атомарность P надо обеспечивать -- программистом, аппаратным обеспечением или ОС. Для задачи “потребитель-производитель” критической операцией будет любая работа с буфером.
semaphore mutex = 1; // бтв, я нихуц не понял почему переменные названы semaphore empty = N; // именно так, ибо смысл у них обратный их semaphore full = 0; // названиям. Так что я бы full ó empty . void Prod() { // производитель while (1) { Произвести(); // производим нечто P(empty); // проверяем наличие места в буфере. Если полон (empty==0), залипаем, иначе уменьшаем количество места в нем на единицу P(mutex); // залипаем если сейчас между P(mutex) и V(mutex) находится другой процесс ПоложитьВБуфер(); V(mutex); // освобождаем mutex . Остальные процессы могут ходить сюда отныне V(full); // увеличиваем количество элементов в буфере. Это разлепляет ожидающих потребителей } }
void Cons() { // потребитель while (1) { P(full); // проверяем есть ли в буфере что-нибудь. Если пуст (full==0), залипаем, иначе уменьшаем количество элементов на единицу. P(mutex); // залипаем если сейчас между P(mutex) и V(mutex) находится другой процесс ИзвлечьИзБуфера(); V(mutex); // освобождаем mutex . Остальные процессы могут ходить сюда отныне V(empty); // увеличиваем количество свободного места на единицу. Это разлепляет производителей ИспользоватьПолученныеДанные(); // радостно съедаем полученую из буфера нямку } } Алгоритм Деккера и Петерсона Взаимоисключение - возможность одному процессу приостановить остальные.
Критическая секция - участок кода, в котором должен находиться только один процесс.
Собственно алгоритм:
shared int ready[2] = {0,0}; // готовность ко входу shared int turn; // чья очередь
while (условие) { // пролог ready[i] = 1; // сообщаем о желании войти в КС turn = 1 - i; // даем возможность входа другому процессу while(ready[i-1] && (turn == 1-i)) ; // если очередь оказалась не нашей, ждем пока он не выйдет из КС // критическая секция ... // эпилог ready[i] = 0; // сообщаем о выходе из КС }
Требования к программной реализации:
• Не используется аппаратная поддержка
• Нет предположений о скорости процессоров и их количестве
• В критической секции только один процесс
• Условие ограниченного ожидания - если один процесс решил войти в свою критическую секцию, это не должно продолжаться неограниченно долго.
Для большего числа процессов используется алгоритм булочной, заключающийся в выдаче номерков. |
Последнее изменение этой страницы: 2019-05-08; Просмотров: 236; Нарушение авторского права страницы