Дейкстра предложил более сложную конструкцию для приема и передачи сообщений. Прием и передача сообщений может выполняться в соответсвии с заданными условиями. Процесс, которому адресуется сообщение, может быть не заинтересован в данный момент в приеме данного сообщения, то есть процесс может принять, а может проигнорировать это сообщение. Поэтому в процессе, который должен принять сообщение должно быть прописано соответсвующее условие. Дейкстра расширяет возможности процесса, то есть процессы могут выбирать принимать сообщение, реагировать на него или игнорировать.
Такой способ получил название у Дейкстры ОХРАНЯЕМОГО ОПЕРАТОРА или ОХРАНЯЕМОЙ КОМАНДЫ(или просто ОХРАНА)

<Охрана> -> <Список охраняемых операторов> Очевидно, охрана это какое-то логическое условие и список охраняемых операторов будет выполняться если <охрана> = истина.

Дейкстра ввел специальные операторные скобки IF … FI И ввел разделитель операторов. (по звуку не знаю что на доске написала)

if G1 -> S1               <- Gi - охрана, Si - список охраняемых операторов
	G2 -> S2
	…
	Gn -> Sn
fi

Развитие мысли Дейкстры об охраняемых операторах вышло в языке ADA (разработан для военных целей). Язык появился 1986 году. Очень мощный язык параллельного программирования.

Был разработан стандарт АНИС. В соответсвии с ним был разработан этот язык.

Нас интересует одно свойство этого языка. Язык ADA Поддерживает тип взаимодействия «Рандеву» - для нас это способ взаимодействия процессов.

Рассмотрим «Рандеву» как модель организации взаимодействия процессов. Модель Рандеву требует: в том случае, если процесс P1 желает передать данные процессу P2, то процесс P2 должен выразить свою готовность к установлению Рандеву (свидание/встреча) Модель Рандеву предложена Хоаром, при этом особенностью Рандеву является то, что если Рандеву принимается обеими сторонами (то есть они вступают в такое взаимодействие), то от имени обоих процессов выполняется одна и та же последовательность команд и взаимодействующие процессы получают результат выполнения этих команд одновременно. Таким образом исключается состояние ожидания при ответе. Этот способ исключает блокировки (не все конечно). Таким образом, взаимодействие выполняется быстрее и эффективнее Это очень важно, особенно для систем реального времени.

О языке ADA. В языке ADA работа с параллельными процессами осуществляется при помощи средств, которые называются task. Таски - специальный вид модуля, каждый из которых может работать независимо, но таски имеют средство связи друг с другом. Таск имеет спецификацию и тело. При этом задачи связываются друг с другом при помощи входов. Если одна задача выдала обращение ко входу и это обращение принимается другой задачей, то обе задачи теряют свою независимость и устанавливают Рандеву. Пока Рандеву действует задачи синхронизированы. В механизме Рандеву отсутствует симметрия, так как задача, к которой выполнено обращение, может принять вызов, а может его не принять. Обслуживающая задача, то есть к которой направлено обращение, имеет точки входа - entry. Это можно представить себе следующим образом.

task <имя> is 
	entry <идентификатор входа> (дискретный диапазон)
							(формальная часть);
	<другие объявления входов или фразы представления>
end <имя>;

Если в спецификации задачи имеется объявление входа, то тело задачи должно содержать по крайней мере один оператор приема accept В операторе приема accept указываются фактические условия, при которых наступает Рандеву. Формально accept записывает следующим образом:

accept: 
accept <идентификатор входа> (выражение) формальная часть
	do последовательность операторов end;

Рандеву начинается с согласования фактических и формальных параметров, затем оно продолжается выполнением операторов, расположенных между do и end, и когда мы доходим до точки с запятой, Рандеву заканчивается. Во время Рандеву задачи могут обмениваться информацией через список параметров и обе задачи синхронизированы, а именно последовательность операторов выполняется от имени обеих задач.

Кроме указанных операторов есть оператор select, при помощи которого может осуществляться выбор.

Рандеву - ЭТО ОСОБЫЙ ВИД ВЗАИМОДЕЙСТВИЯ, ПРИ КОТОРОМ ПОСЛЕДОВАТЕЛЬНОСТЬ ОПЕРАТОРОВ ВЫПОЛНЯЕТСЯ ОТ ИМЕНИ НЕСКОЛЬКИХ ПРОЦЕССОВ. ЭТО ЗНАЧИТ, ЧТО ОНИ ОДНОВРЕМЕННО ПОЛУЧАЮТ РЕЗУЛЬТАТ ВЫПОЛНЕНИЯ ДАННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАТОРОВ, ЧТО ИСКЛЮЧАЕТ ДОПОЛНИТЕЛЬНОЙ БЛОКИРОВКИ.

Рассмотрим работу программы make в UNIX.

Обычно в UNIX большие программы разбиваются на несколько файлов. Предполагается, что изменения, вносимые в один файл предполагают повторную компиляцию только этого файла. Программа make после ее запуска проверяет время последней модификации всех исходных файлов и всех объектных файлов программы. Соотвественно, если исходный файл имеет временную отметку больше, чем временная отметка последней модификации объектного файла, объектный файл будет перекомпилирован.

Например: <имя>.c - 1224 <имя>.o - 1223 Требуется перекомпиляция

Рассмотрим ситуацию в распределенной системе. Имеются два компьютера: на одном выполняется компиляция, на другом - редактирование.

Возникает следующая ситуация

Отметки по локальным часам:

			     1223	   	             1224	        	         1225                                     1226
_______________________________|______________________________|____________________________________|________________________________________|
							Создан <имя>.c
		

			     1222	   	             1223	        	         1224                                     1225
_______________________________|______________________________|____________________________________|________________________________________|
							Отредактирован <имя>.c

Считается, что тактовые генераторы работают со стабильной частотой, но имеют ограниченную точность. Возьмем, что точность кварцевых генераторов составляет 10^(-5). Если таймер генерирует 60 прерываний в секунду, то в час генерирует 216000 тиков. Учитывая точность, машина может выдать значения в диапазоне от 215998 до 216002 тиков в час.

Существует служба точного времени.

Интервал между двумя последовательными солнечными переходами называются солнечным днем. Солнечный переход - это момент подъема солнца на максимально возможную высоту. Была определена средняя солнечная секунда min solar second, но она нестабильна В 1848 были изобретены атомные часы, в результате была определена секунда как время, за которое атом Цезия 133 совершает ровно 9192631770 переходов. Около 50 лабораторий в мире имеют часы на цезии 133.

Соответсвенно, было создано международное бюро для усреднения этого времени, то есть 50 отсчетов усредняется и в результате определяется глобальное время по атомным часам - international atomic time(TAI) Полдень с использованием TAI наступает все раньше. Эта проблема решена с использованием потерянных секунд. Всякий раз, когда разница между солнечным временем и TAI достигает 800 миллисекунд, вводится потерянная секунда - время корректируется. В результате весь мир перешел на универсальное согласованное время - UTC Большинство электрических компаний положили в основу измерение времени для своих часов систему UTC. Когда международное бюро объявляет о потерянной секунде, то эти компании меняют частоту своих часов на 1 больше, чтобы подвести свои часы в той часовой зоне, в которой они работают. Но кроме этого им нужно постоянно иметь точное время. Для локальной сети это организуется следующим образом: один компьютер снабжается приемником сигналов точного времени (хотя сейчас может и у каждого компьютера) Существует подписка на сигналы точного времени.

В настоящее время в нашей стране появились оптические атомные часы на атомах Тулия. Эти часы более устойчивы к внешним воздействиями, также Тулий дает частоту колебаний больше, чем Цезий: более 230трлн/сек Основные алгоритмы для того, чтобы каждый компьютер имел возможность подсчета точного времени: алгоритм Кристиана, Беркли, усредняющие алгоритмы.

В распределенных система очень часто важно, чтобы обеспечивалось отношение случилось до / случилось после. Для того, чтобы быть уверенным, Лампортом был разработан алгоритм, который он назвал timestamps (Логические часы Лампорта)

Процесс 0 в какой-то момент времени решает послать процессу 1 сообщение. Понятно, что отправка сообщения не может производиться позже его получения. То есть отправка всегда выполняется во времени раньше чем получение.

6 -> 16 - A все хорошо 24 -> 40 - B все хорошо 60 -> 56 - C ошибка 64 -> 54 - D ошибка

То есть мы не можем обеспечить отношение случилось до/случилось после.

Лампорт предложил в сообщение добавить временную отметку о локальном времени отправителя. Получатель сравнивает свое время с тем временем, что пришло с сообщением. Если его время меньше, то он устанавливает собственное время равное пришедшему + 1

6 -> 16 - A все хорошо (корректировка не требуется) 24 -> 40 - B все хорошо (корректировка не требуется) 60 -> 56 - C ошибка (время корректируется и вместо 56 станоновится 60 + 1) 69 -> 54 - D ошибка (время корректируется и вместо 54 станоновится 69 + 1)

Это позволяет реализовать точное отношение случилось до/случилось после.

Это самая простая система. Существуют векторные.

Рассмотрим алгоритмы взаимного исключения в распределенных системах.

В распределенных системах часто решаются задачи, аналогичные задачам, которые решаются в mainfraime'ах. Нужны специальные подходы. Все эти подходы можно классифицироавть следующим образом:

1. Централизованные алгоритмы;
2. Распределенные алгоритмы;
3. Алгоритмы token-ring.

Централизованный алгоритм.

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

Координатор анализирует не находится ли какой-то процесс в данной критической секции, но также он должен посмотреть не желает ли какой-то процесс войти в данную критическую секцию, то есть у координатора может существовать очередь к соответствующим критическим секциям. Если какой-то другой процесс находится в этой критической секции или есть процесс, который раньше послал сообщение-запрос на вход в эту критическую секцию, то такой запрос ставится в очередь в данной критической секции, если нет, то координатор посылает сообщение-разрешение и отмечает, что данная критическая секция занята.

Возможно ситуация, когда на компьютере, на котором выполняется процесс-координатор, произошел какой-то сбой и координатор перестает существовать, значит система перестает функционировать. Что делать?

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

Проблема распределенных систем, заключается в том, что передача сообщений требует времеми и время этой передачи непредсказуемо.

Установка timeout позволяет определить существует ли процесс-координатор Если процесс ожидал какое-то время и время ожидания истекло, то он может считать, что координатор отсутсвует (здесь учитывается масса факторов, могут использоваться протоколы общения. То есть координатор, получив сообщение, не молча ставит его в очередь, а посылает сообщение-ответ "сообщение получено"). После истекания ожидания процесс может инициировать процесс выбора нового координатора. Для этого посылается соотвествующий запрос, то есть специальное сообщение-запрос, в котором процесс указывает свой номер. Если номер процесса, получившего такое сообщение больше чем номер, который пришел в сообщении, то он посылает сообщение-подтверждение приема и сам инициирует новые выборы, то есть рассылает сообщения со своим номером. В результате выполнения такой последовательности действий останется один процесс с самым большим номером. Он становится координатором.