Обоснование корректности:
- 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 : запрещает вход остальных читателей при запросе на запись.
Решение с приоритетным записи (глобальные данные)
Инициализация глобальных данных при приоритете записи
вспомогательные данные: // глобальные
nr = 0 // количество читающих
snr = 1 // для защиты nr
sw = 1 // для записи
sr = 1 // блокировка одного читателя при запросе на запись
nw = 0 // количество пишущих
snw = 1 // для защиты nw
srr = 1 // блокировка остальных читателей при запросе на запись
алгоритм попытки захвата чтения начало ждать srr ждать sr ждать snr nr <- nr + 1; если nr = 1, то Ждать(sw); отпустить отпустить отпустить |
алгоритм освобождения чтения начало ждать snr nr <- nr - 1; если nr = 0, то Отпустить(sw); отпустить
|
Решение с приоритетной записью (запись)
алгоритм попытки захвата записи начало ждать snw nw <- nw + 1; если nw = 1, то Ждать(sr ); отпустить Ждать(sw); |
алгоритм освобождения записи начало Отпустить(sw); ждать snw nw <- nw - 1; если nw = 0, то Отпустить(sr ); отпустить |
Возможные сценарии исполнения алгоритма
Сценарии
Имеются только читатели
1 Устанавливается sw.
2 Нет очередей.
Имеются только писатели
1 Устанавливаются sw и sr .
2 Есть очередь писателей на sw.
Есть читатели и писатели, первым выполняется чтение
1 Читателем устанавливается sw.
2 Писателем устанавливается sr .
3 Все писатели становятся в очередь на sw.
4 Один читатель становится в очередь на sr .
5 Остальные читатели становятся в очередь на srr .
Есть читатели и писатели, первым выполняется запись
1 Писателем устанавливается sw.
2 Писателем устанавливается sr .
3 Все писатели становятся в очередь на sw.
4 Один читатель становится в очередь на sr .
5 Остальные читатели становятся в очередь на srr .