Практическая работа 4. Синхронное и асинхронное исполнение
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) после возврата из операции посылки сообщения процесс имеет информацию о том, было доставлено сообщение или нет.
Можно разбить возможные отказы на две группы:
1) отказы средств связи – сообщения либо искажаются, либо доставляются, либо дублируются, сами процессы функциональны;
2) отказы процессов – процесс либо перестает выполняться, либо процесс перестает правильно исполнять алгоритм, возможно умышленно искажая информацию.
Достарыңызбен бөлісу: |