Студопедия — Алгоритмы реализации взаимоисключений
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритмы реализации взаимоисключений






Алгоритм:

Блокирующая глобальная переменная(замок):

shared int lock = 0; // замок открыт

process1

while (lock); // пролог

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

lock = 1; // пролог

{к.с.}

locl = 0; // эпилог

Строгое чередование:

shared int turn = 0;

process I

while(turn!= I);

{к.с.}

turn = 1-i;

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

Алгоритм флагов готовности:

shared int ready[2]={0,0};

process I

ready[i]=1;

Прерывание оба процесса тут. Оба подняли флаги, тогда оба насмерть вешаются(взаим.блок).

while (ready[1-i]);

{к.с.}

ready[i]=0;

Алгоритм Пэтерсона (взаимной вежливости):

shared int ready[2]= {0,0}

shared int turn;

process I

ready[i]=1;

turn = 1 – I;

while(ready[1-i] && turn == 1- I)

{к.с.}

ready[i]=0;

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

 

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

Лучшее решение: блокировать только в момент, когда коду требуется обратиться к такому ресурсу. Такая секции кода называется критической секцией. В таком случае в стеке команд у процесса будет: пролог{ крит секция } эпилог. В момент входа и выхода в крит секцию требуется объявлять об этом системе.

Методы решения проблем взаимоблокировки:

1. однопрограммное выполнение. В прологе блокируются выполнение любых процессов с этими данными. В unix – psw используется для обновления pcb

2. блокирующая глобальна переменная (мьютекс/замок). При не атомарности между while и lock = 1, возникает одновременное использование крит секции.

shared int lock = 0;

процесс 1

while (lock);

lock = 1;

{крит секция}

lock = 0;

3. алгоритм строго чередовании (семафор) Недостаток – передача управлении над критической секцией когда другому процессу она не нужна.

i = 0 или 1;

shared int turn = 0;

процесс i:

while (turn!= i);

{крит секция}

turn = 1-i;

4. Алгоритм флагов готовности. Недостаток: при прерывание между ready[i] и while(ready[1-i]) возникает взаимоблокрировка.

shared int ready[2] = {0, 0};

процесс i:

ready[i] = 1;

while (ready[1-i]);

{ крит секция}

ready [i] = 0;

 

23. Семафоры Дейкстра. Решение проблемы «производитель-потребитель» с помощью семафоров.

Семафор (S) – целочисленная переменная >=0

p(S): пока S == 0 – блокировать процесс; S--; (атомарная операция)

v(S): S++ (атомарная операция)

 

Модель работы:

Producer ->buffer[n] -> Consumer; если буфер не полный – producer отправляет туда данные, иначе ждет. Consumer читает данные если есть, иначе ждет.

 

Объявим 3 семафора.

1. mutex = 1 (0 или 1)

2. empty = N (количество свободных мест в буфере)

3. full = 0 (сколько байт занято в буфере)

Producer:

while (true)

{

produce_item();

p(empty);

p(mutex)

put_item();

v(mutex);

v(full);

}

 

Consumer:

while (true)

{

p(full)

p(mutex)

get_item()

v(mutex)

v(empty)

consume_item()

}

 







Дата добавления: 2015-04-19; просмотров: 1051. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Тема 2: Анатомо-топографическое строение полостей зубов верхней и нижней челюстей. Полость зуба — это сложная система разветвлений, имеющая разнообразную конфигурацию...

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

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

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

Закон Гука при растяжении и сжатии   Напряжения и деформации при растяжении и сжатии связаны между собой зависимостью, которая называется законом Гука, по имени установившего этот закон английского физика Роберта Гука в 1678 году...

Характерные черты официально-делового стиля Наиболее характерными чертами официально-делового стиля являются: • лаконичность...

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия