Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Алгоритм Деккера и Петерсона



Алгоритм Деккера и Петерсона

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

 

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

 

  1. процесс может войти в свой критический участок тогда и только тогда, когда другие процессы не находятся в своих критических участках
  2. если некоторый процесс находится в своем критическом участке и некоторый другой процесс захочет войти в свой критический участок, то это должно быть запрещено, то есть процесс должен быть заблокирован (переведен в ожидание)
  3. многие процессы захотят войти в свой критический участок, но это может сделать только один
  4. процессы должны проходить свои критические участки как можно быстрее, не должны зацикливаться на своих критических участках. Если такое произошло, то ОС должна отменить режим взаимоисключения, чтобы другие процессы могли продолжить вычисление
  5. процессы вне своих критических участков не должны мешать другим процессам входу в свои критические участки

 

 

Собственно алгоритм:

 

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); // увеличиваем количество свободного места на единицу. Это разлепляет производителей

    ИспользоватьПолученныеДанные(); // радостно съедаем полученую из буфера нямку

}

}



Алгоритм Деккера и Петерсона

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

 

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

 

  1. процесс может войти в свой критический участок тогда и только тогда, когда другие процессы не находятся в своих критических участках
  2. если некоторый процесс находится в своем критическом участке и некоторый другой процесс захочет войти в свой критический участок, то это должно быть запрещено, то есть процесс должен быть заблокирован (переведен в ожидание)
  3. многие процессы захотят войти в свой критический участок, но это может сделать только один
  4. процессы должны проходить свои критические участки как можно быстрее, не должны зацикливаться на своих критических участках. Если такое произошло, то ОС должна отменить режим взаимоисключения, чтобы другие процессы могли продолжить вычисление
  5. процессы вне своих критических участков не должны мешать другим процессам входу в свои критические участки

 

 

Собственно алгоритм:

 

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; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.017 с.)
Главная | Случайная страница | Обратная связь