Практическая работа Синхронное и асинхронное исполнение

1. Реализовать имитацию физического времени процессов.

2. Реализовать метки времени Лампорта в глобальном контексте.

3. Изучите теорию синхронного и асинхронного исполнения процессов в распределенных сетях и постройте схемы работы синхронизатора.

4. Имеется алгоритм, который инициализируется сообщением SYNC_INIT с аргументом в виде небольшого целого числа N. Процесс, получивший это сообщение, посылает соседям сообщение SYNC_RUN с этим аргументом. Обработчик сообщения SYNC_RUN должен принять аргумент K и затем послать соседям сообщение SYNC_RUN с аргументом K – 1, если K > 0, либо сообщение SYNC_DONE с результатом вычислений. Если четность номера шага совпадает с четностью аргумента SYNC_RUN, то передать соседям еще одно сообщение SYNC_RUN с аргументом K. Результат вычислений определяется как сумма всех полученных в сообщениях SYNC_RUN после SYNC_INIT чисел. Напишите рабочую функцию для симулятора асинхронного алгоритма, исполняющего данный синхронный алгоритм. Какие дополнительные функции придется реализовать в симуляторе? Дополните симулятор необходимыми функциями."

Теория.

• 
  имеется отношение «раньше». Прием сообщения всегда должен быть позже посылка;
  
• 
  логическое время должно быть дискретным, между двумя одновременными событиями должно быть не менее одного тика;
  
• 
  если А и В – события одного процесса (потока) и А случилось раньше В, то С(А)
• 
  если А есть событие отправления, а В есть событие приема, то С(А)
• 
  для всех различных взаимосвязанных событий С(А)≠ С(В).
  

В каждом сообщении, рассылаемом объектами распределенной системы, наряду с остальной информацией требуется теперь передавать в том числе и такую метку времени. Метка времени Лампорта может входить как в контекст алгоритма, так и в глобальный контекст процесса.

Переменная logicalClock – первый кандидат на помещение в контекст, связанный с распределенной системой в целом (контекст процесса). В данной модели имеется контекст, который принадлежит всем алгоритмам.

struct context_common_s

{

…

struct context_common_s context common;

Для помещения метки времени Лампорта в глобальный контекст процесса в рабочую функцию нужно внести следующие исправления:

1) из контекста алгоритма Кристиана убрать переменную logicalClock

2) в контекст contexc_commom_s добавить переменную logicalClock вместе с ее начальной инициализацией нулевым значением

3) в алгоритме ссылки на переменную из локального контекста алгоритма заменить ссылками на переную в глобальном контексте процесса.

Векторное время

Алгоритм определение предшествующего

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

Наиболее практичный сценарий применения данного алгоритма:

1) формируется группа процессов для выполнения какой-либо задачи, при решении которой важно точное определение отношения предшествования;

2) каждый из процессов этой группы создает в своем контексте вектор временных меток, отображающийся на процессы группы;

3) каждое из сообщений между процессами данной задачи содержит векторные метки времени;

4) при необходимости определение отношений предшествования процесс использует функцию happendBefore;

5) после завершения выполнения задачи вектора временных меток удаляются из контекста процессов.

Синхронность

Под «асинхронный» понимается:

1) что отправка сообщения есть неблокирующая операция и что отправивший сообщение процесс немедленно может продолжить полезную для него деятельность;

2) что отправленное сообщение попадает в новый слой взаимодействия, транспортную подсистему, и оно может быть доставлено, может быть не доставлено и может быть дублировано. Пославший сообщение процесс не может определить судьбу любого из посланных сообщений.

Системы с гарантированной доставкой сообщений называют надежными или системами без отказов. Существуют системы с отказами или ненадежные.

Синхронный режим обмена отличается от асинхронного:

1) отправка сообщения есть блокирующая операция и пославший сообщение процесс останавливает свое исполнение до получения результата запроса

2) после возврата из операции посылки сообщения процесс имеет информацию о том, было доставлено сообщение или нет.

Можно разбить возможные отказы на две группы: