Контрольная работа

Задание
1.) Написать последовательную программу по заданию варианта.
2.) Реализовать версию программы с использованием многопочности или MPI. Для вариантов 3, 4, 5, 6 один процесс моделируемой системы имитируется одним потоком или с использованием MPI один процесс моделируемой системы имитируется одним MPI процессом/рэнком. Для планировщиков предусмотреть наличие нескольких вычислителей, каждый из которых имитируется отдельным потоком или MPI процессом. Для варианта 1 имитируется некоторое расширение сетей Петри, в которых все переходы могут срабатывать одновременно. Каждый переход моделируется отдельным потоком или MPI процессом. При этом, используя средства синхронизации в потоках или MPI, нужно исключить одновременный доступ разных переходов к одним и тем же позициям.

Темы контрольных работ:
№ варианта Задание
1 Имитатор работы сети Петри. Описание графа и начальное состояние считывается из текстового файла. Синтаксис описания выбирается произвольно. Промежуточные шаги (номера срабатывающих переходов) и конечное состояние сохраняются в файл.
2 Реализация планировщика для дисциплины “короткие задачи вперед”. Исходные данные задают последовательность поступающих задач с указанием времени их поступления и оценки времени счета для каждой задачи. Переключение между задачами происходит либо при завершении задачи, либо при поступлении новой задачи. В результате работы планировщика формируется отчет, хранящий описание событий: 1) поступление задачи, 2) запуск задачи, 3) завершение задачи (с указанием всех существенных ассоциированных с этими событиями параметров (время, номер задачи, оставшееся время счета и т.д.)
3 Программа, имитирующая работу снэпшот алгоритма для системы с двумя процессами
4 Программа, имитирующая работу алгоритма выбора лидера Чанга и Робертс. Входная конфигурация описывает число процессов и UID каждого из них, порядок их следования в кольце и номер процесса/процессов, запустивших алгоритм. В результате формируется отчет о всех сообщениях от момента старта алгоритма до момента его завершения
5 Программа, имитирующая работу алгоритма выбора лидера Bully. Входная конфигурация описывает число процессов и UID каждого из них и номер процесса/процессов, запустивших алгоритм. В результате формируется отчет о всех сообщениях от момента старта алгоритма до момента его завершения
6 Программа, имитирующая работу Итай/Родэ. Результат работы – отчет с информацией о каждом промежуточном состоянии
7 Реализация планировщика для дисциплины “Robin Round”. Исходные данные задают последовательность поступающих задач с указанием времени их поступления. Переключение между задачами происходит по истечении одной единицы модельного времени, либо при завершении задачи, либо при поступлении новой задачи. В результате работы планировщика формируется отчет, хранящий описание событий: 1) поступление задачи, 2) запуск задачи, 3) завершение задачи, переключение между задачами (с указанием всех существенных ассоциированных с этими событиями параметров (время, номер задачи, оставшееся время счета и т.д.)
8 Реализация имитатора алгоритма распределенной блокировки для случая с тремя распределенными процессами
9 Реализация имитатора работы асинхронной программы
10 Реализация задачи читатели-писатели

=============================================

Вопросы для самоконтроля
1. Виды прозрачности в распределенных системах.
2. Свойства масштабируемости, открытости и неоднородности системы.
3. Отличия распределенных систем от параллельных ВС.
4. Какие есть способы измерения производительности отдельных узлов распределенной ВС? Показатели производительности.
5. Производительность распределенной системы. Ускорение. Эффективность распараллеливания.
6. Понятия мультимножества, двудольных и многодольных графов.
7. Понятие сетей Петри. Алгоритм функционирования.
8. Какие бывают интерпретации сетей Петри?
9. Безопасная сеть Петри.
10. Понятие графа достижимости.
11. Понятие семафора
12. Дедлоки. Необходимые условия их возникновения.
13. Способы борьбы с дедлоками.
14. Задача производитель/потребитель.
15. Задача читатель-писатель.
16. Понятие критического интервала.
17. Понятие асинхронной программы.
18. Алгоритм Кристиана. Назначение и функционирование.
19. Основные свойства отношения частичного порядка в часах Лэмпорта для распределенной системы
20. Часы Лампорта и пример их реализации.
21. На каких правилах построена реализация часов Лэмпорта?
22. Определение частичного порядка событий в часах Лэмпорта. Отношение “случилось до”.
23. Как можно ввести отношение полного порядка в часах Лэмпорта?
24. Как формулируется проблема синхронизации стрелков? Опишите один из алгоритмов ее решения.
25. Алгоритмы выбора лидера. Задачи, решаемые ими, и свойства корректного алгоритма.
26. Какие существуют основные алгоритмы выбора лидера, в чем отличия между ними?
27. Алгоритм Чанга и Робертс.
28. Алгоритм Bully.
29. Алгоритм Итай/Родэ
30. Алгоритмы взаимного исключения в распределенных системах. Назначение. Условия, которым должных удовлетворять алгоритмы взаимного исключения.
31. Снэпшот алгоритмы.
32. Пример работы снэпшот алгоритма.
33. Алгоритмы поиска минимального остовного дерева.
34. Алгоритм Прима.
35. Дисциплины обслуживания. Основные характеристики. Достоинства и недостатки.
36. Задачи, решаемые алгоритмами балансировки. Виды этих алгоритмов.