Теория распараллеливания и синхронизация. Демьянович Ю.К - 54 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

7) < next = next + 1; >
8) [некритическая секция];
9) }
10) }
Недостатки алгоритма. 1) Общий недостаток для алгоритмов
с неограниченно увеличивающимися счетчиками: увеличение счет-
чиков может привести к переполнению (к счастью, на практике
это бывает ре дко). 2) Первое из фигурирующих в этой программе
неделимых действий — чтение числа number и его увеличение —
реализовать трудно.
В некоторых вычислительных системах имеются инструкции,
возвращающие одновременно и старое зн ачение переменной и уве-
личенное (или уменьшенное) на 1 ее значение.
Пусть у нас имеет инструкция FA (Fetch and Add — извлечь и
сложить):
FA (var, incr) :
< int tmp = var; var = var + 1; return(tmp); >
Тогда можно предложить мелкомодульное решение алгоритма би-
лета.
АЛГОРИТМ БИЛЕТА: МЕЛКОМОДУЛЬНОЕ РЕШЕНИЕ
1) int number = 1, next = 1, turn[1 : n] = ([n]0);
2) process CS[i = 1 to n] {
3) while (true) {
4) turn[i] = FA (number, 1); # протокол входа
5) while (turn[i]! = next) skip;
6) [критическая секция];
7) next = next + 1; # протокол выхода
8) [некритическая секция];
9) }
10) }
55

Страницы