Алгоритм 2


Скачать 449.39 Kb.
НазваниеАлгоритм 2
страница2/5
Дата публикации06.05.2013
Размер449.39 Kb.
ТипДокументы
userdocs.ru > Информатика > Документы
1   2   3   4   5


Алгоритм Деккера (Dijkstra, 1965)

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

Код процесса 0

abFlags[0] = true; // (1)

while (abFlags[1]) // (2)

if (nTurn == 1) // (3)

{

abFlags[0] = false; // (4)

while (nTurn == 1) // (5)

/* пережидание */ ;

abFlags[0] = true; // (6)

}

// критический раздел

nTurn = 1; // (7)

abFlags[0] = false; // (8)

Код процесса 1

abFlags[1] = true; // (1)

while (abFlags[0]) // (2)

if (nTurn == 0) // (3)

{

abFlags[1] = false; // (4)

while (nTurn == 0) // (5)

/* пережидание */ ;

abFlags[1] = true; // (6)

}

// критический раздел

nTurn = 0; // (7)

abFlags[1] = false; // (8)


Комбинация 1 и 4.

(2) – не освободили ли;

(3) – наступила ли очередь;

(4) – освобождаем

(5) – пережидаем чужую очередь

(6) – опять хотим войти

^ Блокировка с двойной проверкой. Не работает в SMP системах (архитектура многопроцессорных компьютеров, в которой два или более одинаковых процессоров подключаются к общей памяти), т.к. выполняется не в том порядке. Для решения проблемы ставится «барьер» (барьер памяти) - операция сброса кэша.

Другая проблема: nTurn не меняется в цикле, и компилятор выносит вне цикла. Решение – сделать переменную volatile. volatile - это квалификатор переменной, говорящий компилятору, что значение переменной может быть изменено в любой момент и что часть кода, которая производит над этой переменной какие-то действия (чтение или запись), не должна быть оптимизирована.
Алгоритм Петерсона (Peterson, 1981)

Программный алгоритм взаимного исключения потоков исполнения кода, разработанный Г. Петерсоном в 1981 г. Хотя изначально был сформулирован для 2-х поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Алгоритм условно называется программным, так как не основан на использовании специальных команд процессора для запрета прерываний, блокировки шины памяти и т. д., используются только общие переменные памяти и цикл для ожидания входа в критическую секцию исполняемого кода.

Код процесса 0

abFlags[0] = true; // (1)

nTurn = 1; // (2)

while (abFlags[1] && // (3)

nTurn == 1) // (4)

/* пережидание */ ;

// критический раздел

abFlags[0] = false; // (5)

Код процесса 1

abFlags[1] = true; // (1)

nTurn = 0; // (2)

while (abFlags[0] && // (3)

nTurn == 0) // (4)

/* пережидание */ ;

// критический раздел

abFlags[1] = false; // (5)


Когда нарушается одно из условий, входим в критический раздел. (Также volatile).

В С++ 2011 появились атомарные операции, которые запрещают менять местами (тогда уже нельзя назвать чисто программным алгоритмом)

^ Обоснование корректности:

- abFlags[0] == true =>

P1 вне критического раздела => не сможет зайти в него.

P1 в критическом разделе => abFlags[1] == true => P0 не сможет зайти.

- Взаимная блокировка исключена <= противное: пусть P0 заблокирован => abFlags[1] == true и nTurn == 1. P0 может войти в критический раздел, если abFlags[1] == false или nTurn == 0. Случаи:

1. P1 не намерен входить в критический раздел. Это невозможно <= иначе abFlags[1] == false.

2. P1 ожидает входа в критический раздел. Это невозможно <= иначе если nTurn == 1 => P1 может в него войти.

3. P1 циклически монополизирует критический раздел. Это невозможно <= перед любой попыткой P1 должен дать такую же возможность P0, устанавливая nTurn = 0 (не успевает ) abFlags[1] = false).
Алгоритм Лампорта (Lamport, 1974)

Блокировка

void lock(int i)

{

abFlags[i] = true;

anNumbs[i] = 1 + *std::max(anNumbs, anNumbs + NUM_THREADS);

abFlags[i] = false;

for (int j = 0; j < NUM_THREADS; ++ j)

{

while (abFlags[j]) // ожидание получения Pj номера

/* пережидание */ ;

while (anNumbs[j] != 0 &&

std::make_pair(anNumbs[j], j) < std::make_pair(anNumbs[i], i))

/* пережидание */ ;

}

Работает для нескольких процессов (очередь с номерами).

В цикле проходим по всем процессам и пережидаем, пока всем присвоятся номера.

Алгоритм действует по следующим правилам: (Wiki)

1. Чтобы отправить сообщение процесс транслирует свое время всем остальных (шаг аналогичен запросу на вход в критическую секцию)

2. При приеме сообщения оно сохраняется вместе со временем и отправляется подтверждение, также помеченное временем

3. Сообщение может быть доставлено процессу, если от всех остальных потоков получены сообщения с большей временной меткой (шаг аналогичен работе критической секции)

void unlock(int i)

{ anNumbs[i] = 0;}
Аппаратные инструкции для поддержки взаимных исключений

Проверка и установка

Классическим параллельным примитивом является проверка и установка. Операция проверки и установки атомарно читает значение из какого-то места в памяти и записывает в него новое значение, возвращая старое. Как правило, в этом месте может находиться 0 или 1, и новым значением, которое записывает операция проверки и установки является 1, то есть «установка».

входные данные: i// по ссылке

начало

если i = 0, то i <-1 ;

вернуть “ложь” ;

иначе // i <> 0

вернуть “истина”;


входные данные: i// по ссылке

начало

t <- i ;

i <- 1 ;

вернуть (t = 0) ;

Код процесса i

int bLock = 0; // глобальная

// . . .

while (TestAndSet(&bLock))

/* пережидание */ ;

// критический раздел

bLock = 0;
-- - --

Эта реализация переносится на любое количество процессов.

Пример (X86)

enter_lock: tsl reg, flag

cmp reg, #0

jnz enter_lock

ret

Возвращает в регистр предыдущее значение флага. Сравниваем регистр с 0. Если не равен, возвр. в enter_lock.

Реализация 1 – сначала просто обращаемся к переменной. Когда становится 0, переходим к TestAndSet. В цикле, т.к. кто-то ещё может захватить.

int bLock = 0; // глобальная

. . . do

{

while (bLock)

/* пережидание */ ;

}

while (TestAndSet(&bLock));

// критический раздел

bLock = 0;

Реализация 2 – то же, со сложным условием.

int bLock = 0; // глобальная

// . . .

while (bLock || TestAndSet(&bLock))

/* пережидание */ ;

// критический раздел

bLock = 0;


Аппаратные инструкции для поддержки взаимных исключений

Обмен

Атомарно меняет местами значения

Выход из крит. раздела чуть сложнее.

^ Алгоритм атомарного обмена

входные данные: r // регистр

m; // память

вспомогательные данные: t

начало

t <- m;

m <- r ;

r <- t;

^ Код процесса i

int bLock = 0; // глобальная

// . . .

int bKeyI = 1; // локальная

while (bKeyI)

Exchange(bKeyI, bLock);

// критический раздел

Exchange(bKeyI, bLock);



Соотношение:



Связь между проверкой-установкой и обменом

^ Алгоритм атомарной проверки и установки

входные данные: i // по ссылке

начало

t <- i ;

i <- 1 ;

вернуть (t = 0) ;

входные данные: i// по ссылке

начало

t <- 1 ;

обмен(i , t); // атомарная

вернуть (t = 0) ;

Особенности аппаратной реализации критических секций

Преимущества

- Простота.

- Применимость к любому количеству процессов и процессоров с общей

памятью.

- Поддержка нескольких критических разделов.

Недостатки

- Использование пережидания.

- Возможность голодания.

- Возможность взаимной блокировки (процессы с разными приоритетами).
Оправдано, когда низкие пережидания. Это примитивная реализация. Решение этих проблем – семафоры.

В параллельной среде некоторые действия должны выполняться атомарно, то есть без какой-либо возможности прерывания.

Семафоры (сильные/слабые)

Семафор — это способ управления доступом к ресурсу.

Семафор – объект ядра, он имеет доступ к планировщику и его можно интегрировать.

Если FIFO – семафор сильный (будет соотв. порядку).

Если нет – семафор наз. слабым.

Слабое место – неатомарность. Для этого можно установить блок, например, проверка и установка.

Алгоритм попытки захвата семафора

входные данные: s // переменная-семафор

начало

s:count <- s:count - 1 ;

если s:count < 0, то

Поместить текущий процесс в s:queue ;

Заблокировать текущий процесс ;
Алгоритм освобождения семафора

входные данные: s // переменная-семафор

начало

s:count <- s:count + 1 ;

если s:queue не пуста, то

Удалить процесс P из s:queue;

Поместить процесс P в список активных;

Реализация семафоров в однопроцессорной среде

Алгоритм попытки захвата семафора

входные данные: s // переменная-семафор

начало

Запретить прерывания;

Остальная реализация;

Разрешить прерывания;

^ Алгоритм освобождения семафора

входные данные: s // переменная-семафор

начало

Запретить прерывания;

Остальная реализация;

Разрешить прерывания;
Реализация семафоров при помощи атомарной операции

Алгоритм попытки захвата семафора

Алгоритм освобождения семафора

(одинаково?)

входные данные: s // переменная-семафор

начало

пока ПУ(s.flag), выполнять

Пережидание;

Остальная реализация;

s.flag <- 0;

Задача о читателях и писателях

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

- Чтение данных возможно одновременно любым количеством читателей.

- Запись данных возможна одновременно только одним писателем.

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

Решение с приоритетным чтением (чтение)

^ Алгоритм попытки захвата чтения

вспомогательные данные: // глобальные

nr = 0 // # читающих

snr = 1 // для защиты nr

sw = 1 // для записи

начало

ждать snr

nr <- nr + 1;

если nr = 1, то

Ждать(sw);

отпустить

Алгоритм освобождения чтения

начало

ждать snr

nr <- nr - 1;

если nr = 0, то

Отпустить(sw);

отпустить


Решение с приоритетным чтением (запись)

Алгоритм попытки захвата записи

начало

Ждать(sw);

^ Алгоритм освобождения записи

начало

Отпустить(sw);

Задача о читателях и писателях (приоритетная запись)

Дополнение к условию

- Чтение данных невозможно, если хотя бы один писатель изъявил о намерении записи.

^ Дополнительные переменные

sr : запрещает вход первого читателя при запросе на запись.

nw: обеспечивает корректную установку sr.

snw: гарантирует корректность изменения nw.

srr : запрещает вход остальных читателей при запросе на запись.
1   2   3   4   5

Похожие:

Алгоритм 2 iconАлгоритм
Ш 55 Разгром Японии и самурайская угроза. — М.: Изд-во Алгоритм; Изд-во Эксмо, 2005. — 512 с, ил
Алгоритм 2 iconРазрешение записи
Для уменьшения объема хранимой видеоинформации в видеорегистраторах применяются различные алгоритмы ее компрессии. В сетевых видеорегистраторах...
Алгоритм 2 iconАннотация Слово «алгоритм»
Слово «алгоритм» не случайно введено в название книги: мне представляется, что есть возможность «разложить по полочкам» самые сложные...
Алгоритм 2 iconСтатья «Алгоритм решения изобретательских задач» в Википедии Это...
Алгоритм решения изобретательских задач[1][2][3][4][5][6][7][8][9][10] раздел теории решения изобретательских задач (триз), разработаной...
Алгоритм 2 iconПрограмма упорядоченное множество ко­манд, реализу­ющих алгоритм решения задачи
Алгоритм упорядоченное множе­ство фор­ма­ль­ных предписаний, выпол­нение которых приводит к решению задачи. Команда элементарная...
Алгоритм 2 iconАлгоритм работы системы

Алгоритм 2 icon6. задача о рюкзаке
Циклический алгоритм целочисленного программирования
Алгоритм 2 iconУкрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12
Алгоритм 2 iconЗаконодательное обоснование
Алгоритм действий граждан в случае обнаружения несанкционированных раскопок – с. 6
Алгоритм 2 iconПризрак толпы / Карл Ясперс, Жан Бодрийар. М.: Алгоритм, 2007. 272 с. Философский
Призрак толпы / Карл Ясперс, Жан Бодрийар. — М.: Алгоритм, 2007. — 272 с. — Философский
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница