Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
Новгородский государственный университет имени Ярослава Мудрого
Институт Электронных и Информационных систем
Кафедра «Информационных технологий и систем»
ОПЕРАЦИОННЫЕ СИСТЕМЫ
Дисциплина для специальности 230105 “Программное обеспечение вычислительной техники и автоматизированных систем”
Методические указания по курсовому проектированию
Принято на заседании кафедры ИТиС Зав. кафедрой ИТиС _____________А. Л. Гавриков «____» ____________ 2011г. |
Разработал: Доцент кафедры ИТиС __________ В. В.Дронов «____»_____________ 2011 г. |
Общие положения
Для выполнения курсовой работы студенту предлагаются (на выбор) три темы:
Разработка и реализация программы управления процессом имитационного моделирования информационно-вычислительной системы;
Разработка и программная реализация многопользовательских сетевых приложений;
Разработка и программная реализация параллельных игровых алгоритмов.
Студент может предложить свою тему и согласовать её с преподавателем.
1 Разработка и реализация программы управления процессом имитационного моделирования информационно-вычислительной системы
По описанию варианта задачи необходимо:
разработать концептуальную модель процессно-ориентированного алгоритма управления вычислительным процессом.
определить необходимые средства межпроцессного взаимодействия (разделяемая память, каналы, сообщения, сигналы).
определить необходимые средства синхронизации процессов.
разработать программу, реализующую алгоритм имитационного моделирования, на Shell-языке командной строки операционной системы Linux.
разработать программу на языке C++ обработки итогового журнала и определения результатов прогона имитационной модели.
выполнить прогон модели, интерпретировать полученные результаты, оформить отчёт.
Варианты заданий
Вариант 1
Система передачи данных обеспечивает передачу пакетов данных из пункта А в пункт С через транзитный пункт В. В пункт А пакеты поступают через (10+-5) мс. Здесь они буферизуются в накопителе емкостью 20 пакетов и передаются по любой из двух линий АВ1 - за время 20 мс или АВ2 - за время (20+-5) мс. В пункте В они снова буферизуются в накопителе емкостью 25 пакетов и далее передаются по линиям ВС1 за (25+-3) мс и ВС2 за 25 мс. Причем пакеты из АВ1 поступают в ВС1, а иэ АВ2 - в ВС2. Чтобы не было переполнения накопителя, в пункте В вводится пороговое значение его емкости - 20 пакетов. При достижении очередью порогового значения происходит подключение резервной аппаратуры и время передачи снижается для линий ВС1 и ВС2 до 15 мс. Смоделировать прохождение через систему передачи данных 500 пакетов. Определить вероятность подключения резервной аппаратуры и характеристики очереди пакетов в пункте В. В случае возможности его переполнения определить необходимое для нормальной работы пороговое значение емкости накопителя.
Вариант 2
Система обработки информации содержит мультиплексный канал и три миниЭВМ. Сигналы от датчиков поступают на вход канала через интервалы времени (10+-5) мкс. В канале они буферизуются и предварительно обрабатываются в течение (10+-3) мкс. Затем они поступают на обработку в ту миниЭВМ, где имеется наименьшая по длине входная очередь. Емкости входных накопителей во всех миниЭВМ рассчитаны на хранение величин 10 сигналов. Время обработки сигнала в любой миниЭВМ равно 33 мкс. Смоделировать процесс обработки 500 сигналов, поступающих с датчиков. Определить среднее время задержки сигналов в канале и миниЭВМ и вероятности переполнения входных накопителей. Обеспечить ускорение обработки сигнала в ЭВМ до 25 мкс при достижении суммарной очереди сигналов значения 25 единиц.
Вариант 3
Магистраль передачи данных состоит из двух каналов (основного и резервного) и общего накопителя. При нормальной работе сообщения передаются по основному каналу за (7+-3) с. В основном канале происходят сбои через интервалы времени (200+-35) с. Если сбой происходит во время передачи, то за 2 с запускается запасной канал, который передает прерванное сообщение с самого начала. Восстановление основного канала занимает (23+-7) с. После восстановления резервный канал выключается и основной канал продолжат работу с очередного сообщения. Сообщения поступают через (9+-4) с и остаются в накопителе до окончания передачи. В случае сбоя передаваемое сообщение передается повторно по запасному каналу. Смоделировать работу магистрали передачм данных в течение одного часа. Определить загрузку запасного канала, частоту отказов канала и число прерванных сообщений.
Вариант 4
В системе передачи данных осуществляется обмен пакетами данных между пунктами А и В по дуплексному каналу связи. Пакеты поступают в пункты системы от абонентов с интервалами времени между ними (10+-3) мс. В пунктах имеются буферные регистры, которые могут хранить два пакета (включая передаваемый). В случае прихода пакета в момент занятости регистров пунктам системы предоставляется выход на спутниковую полудуплексную линию спязи, которая осуществляет передачу пакетов данных за (10+-5) мс. При занятости спутниковой линии пакет получает отказ. Смоделировать обмен информацией в системе передачи данных в течение одной минуты. Определить частоту вызовов спутниковой линии и ее загрузку. В случае возможности отказов определить необходимый для безотказной работы системы объем буферных регистров.
Вариант 5
Специализированная вычислительная система состоит из трех процессоров и общей оперативной памяти. Задания, поступающие на обработку через интервалы времени (5+-2) мин, занимают объем оперативной памяти размером в страницу. После трансляции первым процессором в течение (5+-1) мин их объем увеличивается до двух страниц и они поступают в оперативную память. Затем после редактирования во втором процессоре, которое занимает (2,5+-0,5) мин на страницу, объем возрастает до трех страниц. Отредактированные задания через оперативную память поступают в третий процессор на решение, требующее (1,5+-0,4) мин на страницу, и покидают систему, минуя оперативную память. Смоделировать работу вычислительной системы в течение 50 ч. Определить характеристики занятия оперативной памяти по всем трем видам заданий.
Вариант 6
На вычислительном центре в обработку принимаются три типа заданий А, В и С. Исходя из наличия оперативной памяти ЭВМ задания классов А и В могут решаться одновременно, а задания класса С монополизируют ЭВМ. Задания класса А поступают через (20+-5) мин, класса В - через (20+-10) мин и С - через (30+-10) мин и требуют для выполнения: класс А - (20+-5) мин, класс В - (21+-3) мин и класс С - (28+-5) мин. Задачи класса С загружаются в ЭВМ, если она полностью свободна. Задачи классов А и В могут дозагружаться к решающейся задаче. Смоделировать работу ЭВМ за 80 ч. Определить ее загрузку.
Вариант 7
В студенческом машиннам зале расположены две миниЭВМ и одно устройство подготовки данных (УПД). Студенты приходят с интервалом в (8+-2) мин и треть из них хочет использовать УПД и ЭВМ, а остальные только ЭВМ. Допустимая очередь в машинном зале составляет четыре человека, включая работающего на УПД. Работа на УПД занимает (8+-1) мин, а на ЭВМ - - 17 мин. Кроме того, 20% работавших на ЭВМ возвращается для повторного использования УПД и ЭВМ. Смоделировать работу машинного зала в течение 60 ч. Определить загрузку УПД, ЭВМ и вероятности отказа в обслуживании вследствие переполнения очереди. Определить соотношение желающих работать на ЭВМ и на УПД в очереди.
Вариант 8
К миниЭВМ подключено четыре терминала, с которых осуществляется решение задач. По команде с терминала выполняют операции редактирования, трансляции, планирования и решения. Причем, если хоть один терминал выполняет планирование, остальные вынуждены простаивать из-за нехватки оперативной памяти. Если два терминала выдают требование на решение, то оставшиеся два простаивают, и если работают три терминала, выдающих задания на трансляцию, то оставшийся терминал блокируется. Интенсивности поступления задач различных типов равны. Задачи одного типа от одного терминала поступают через экспоненциально расположенные интервалы времени со средним значением 160 с. Выполнение одной операции длиться 10 с. Смоделировать работу миниЭВМ в течение 4 ч. Определить загрузку процессора, вероятности простоя терминалов и частоту одновременного выполнения трансляции с трех терминалов.
Вариант 9
В системе передачи цифровой информации передается речь в цифровом виде. Речевые пакеты передаются через два транзитных канала, буферируясь в накопителях перед каждым каналом. Время передачи пакета по каналу составляет 5 мс. Пакеты поступают через (6+-3) мс. Пакеты, передававшиеся более 10 мс, на выходе системы уничтожаются, так как их появление в декодере значительно снизит качество передаваемой речи. Уничтожение более 30% пакетов недопустимо. При достижении такого уровня система за счет ресурсов ускоряет передачу до 4 мс на канал. При снижении уровня до приемлемого происходит отключение ресурсов. Смоделировать 10 с работы системы. Определить частоту уничтожения пакетов и частоту подключения ресурса.
Вариант 10
ЭВМ обслуживает три терминала по круговому циклическому алгоритму, предоставляя каждому терминалу 30 с. Если в течение этого времени задание обрабатывается, то обслуживание завершается; если нет, то остаток задачи становится в специальную очередь, которая использует свободные циклы терминалов, т. е. задача обслуживается, если на каком-либо терминале нет заявок. Заявки на терминалы поступают через (30+-5) с и имеют длину (300+-50) знаков. Скорость обработки заданий ЭВМ равна 10 знаков/с. Смоделировать 5 ч работы ЭВМ. Определить загрузку ЭВМ, параметры очереди неоконченных заданий.
Вариант 11
В узел коммутации сообщений, состоящий из входного буфера, процессора, двух исходящих буферов и двух выходных линий, поступают сообщения с двух направлений. Сообщения с одного направления поступают во входной буфер, обрабатываются в процессоре, буферизуются в выходном буфере первой линии и передаются по выходной линии. Сообщения со второго направления обрабатываются аналогично, но передаются по второй выходной линии. Применяемый метод контроля потоков требует одновременного присутствия в системе не более трех сообщений на каждом направлении. Сообщения поступают через интервалы (15+-7) мс. Время обработки в процессоре равно 7 мс на сообщение, время передачи по выходной линии равно (15+-5) мс. Если сообщение поступает при наличии трех сообщений в направлении, то оно получает отказ. Смоделировать работу узла коммутации в течение 10 с. Определить загрузки устройств и вероятность отказа в обслуживании из-за переполнения буфера направления.
Вариант 12
Распределенный банк данных системы сбора информации организован на базе двух ЭВМ, соединенных дуплексным каналом связи. Поступающий запрос обрабатывается на первой ЭВМ и с вероятностью 50% необходимая информация обнаруживается на месте. В противном случае необходима посылка запроса во вторую ЭВМ. Запросы поступают через (10+-3) с, первичная обработка запроса занимает 2 с, выдача ответа требует (18+-2) с, передача по каналу связи занимает 3 с. Временные характеристики второй ЭВМ аналогичны первой. Смоделировать прохождение 400 запросов. Определить необходимую емкость накопителей перед ЭВМ, обеспечивающую безотказную работу системы.
Вариант 13
На вычислительный центр через (300+-100)с поступают задания длиной (500+-200) байт. Скорость ввода, вывода и обработки заданий - 100 байт/мин. Задания проходят последовательно ввод, обработку и вывод, буферируясь перед каждой операцией. После вывода 5% заданий оказываются выполненными неправильно вследствие сбоев и возвращаются на ввод. Для ускорения обработки задания в очередях располагаются по возрастанию их длины, т. е. короткие сообщения обслуживают в первую очередь. Задания, выполненные неверно, возвращаются на ввод и во всех очередях обслуживаются первыми. Смоделировать работу вычислительного центра в течение 30 ч. Определить необходимую емкость буферов
Вариант 14
Вычислительная система включает три ЭВМ. В систему в среднем через 30 с поступают задания, которые попадают в очередь на обработку к первой ЭВМ, где они обрабатываются около 30 с. После этого задания поступают одновременно во вторую и третью ЭВМ. Вторая ЭВМ может обработать задания за (14+-5) с, а третья - за (16+-1) с. Окончание обработки задания на любой ЭВМ означает снятие ее с решения с той и другой машины. В свободное время вторая и третья ЭВМ заняты обработкой фоновых задач. Смоделировать 4 ч работы системы. Определить необходимую емкость накопителей перед всеми ЭВМ.
Рекомендуемая литература
Е., А. Введение в операционные системы.
http://cs. mipt. ru/docs/courses/osstud/oc. html
Брюс Моли UNIX/LINUX. Теория и практика программирования.
http://bookwebmaster. narod. ru/unix. html
Мендель Купер Искусство программирования на языке сценариев командной
оболочки.
http://www. opennet. ru/docs/RUS/bash_scripting_guide/
Г., Ю. Теория вычислительных процессов и структур.
Учебно-методическое пособие.
http://bsur-helper. ru.
Стасышин В М Управление ресурсами в ОС UNIX.
http://www. ict. edu. ru/ft/002355/Method1.HTM
Пример концептуальной схемы для варианта 3
|
|
2 Разработка и программная реализация многопользовательских сетевых приложений
Цель работы
Получение практических навыков разработки и реализации многопользовательских сетевых приложений под управлением операционной системы семейства Unix/Linux.
Общее описание задачи
В общем случае необходимо разработать 2 приложения: приложение-сервер (далее Сервер) и приложение-клиент (далее Клиент). В зависимости от варианта набор различных приложений может меняться.
Сервер предоставляет программный интерфейс (набор функций сервера) Клиенту. Если разработчиков несколько, то начать разработку лучше с интерфейса.
Приложения взаимодействуют друг с другом посредством протокола – набора правил, по которому Клиент вызывает функции программного интерфейса Сервера.
Пример взаимодействия Клиента с Сервером:
Сервер может одновременно обслуживать более одного Клиента (в несколько потоков). Максимальное количество Клиентов одновременно взаимодействующих с Сервером определяется конкретной задачей.
Основные отличия процессов Клиента и Сервера применительно к удаленному взаимодействию:
– Сервер работает постоянно, на всем протяжении жизни приложения, а Клиенты могут работать эпизодически.
– Сервер ждет запроса от Клиентов, инициатором же взаимодействия выступает Клиент.
– Клиент обращается к одному Серверу за раз, в то время как к Серверу могут одновременно поступить запросы от нескольких Клиентов.
– Клиент должен знать полный адрес Сервера перед началом организации запроса (до начала общения), в то время как Сервер может получить информацию о полном адресе Клиента из пришедшего запроса (после начала общения).
– И Клиент, и Сервер должны использовать один и тот же протокол транспортного уровня OSI модели.
Неравноправность процессов в модели клиент-сервер, накладывает свой отпечаток на программный интерфейс, используемый между уровнем приложений/процессов и транспортным уровнем.
Поступающие запросы Сервер может обрабатывать последовательно – запрос за запросом – или параллельно, запуская для обработки каждого из них свой процесс или thread. Как правило, Серверы, ориентированные на связь клиент-сервер с помощью установки логического соединения (TCP-протокол), ведут обработку запросов параллельно, а серверы, ориентированные на связь клиент-сервер без установления соединения (UDP-протокол), обрабатывают запросы последовательно.
Более подробно об организации взаимодействия между Клиентом и Сервером с помощью протоколов TCP, UDP необходимо прочитать:
http://www. intuit. ru/department/os/osintropractice/10/1.html (можно с 4-ой страницы)
Там же можно посмотреть примеры реализации Клиента и Сервера.
Требования к реализации
Оба приложения должны выполняться в Unix/Linux-подобной ОС
Компилятор GCC/G++
Язык программирования C/C++
Параметры (аргументы) приложений передаются через командную строку при запуске (например, при запуске Клиента передать IP-адрес Сервера)
Любые изменения в требованиях к реализации обязательно согласовываются с преподавателем (другой язык программирования, другой компилятор и т. д.).
Требования к отчёту
Отчёт по курсовой работе оформляется в соответствии со стандартами оформления документации НовГУ.
Отчёт должен иметь следующие разделы:
Цель работы
Задание
Разработка проекта
Описание методов решения задачи. Обязательно описать протокол взаимодействия Клиента и Сервера. Объяснить выбор протокола транспортного уровня OSI-модели (TCP/UDP). Привести UML-диаграмму взаимодействия потоков. Описать основной алгоритм решения задачи.
Реализация проекта
Описать структуру Клиента и Сервера. Описать программный интерфейс Сервера. Привести описание основных функций Клиента и Сервера (возможно с помощью хорошо прокомментированных вставок кода). Для каждой выбранной функции описать входные данные и результат выполнения.
Привести список системных вызовов операционной системы, используемых при реализации.
Описать пример работы приложений. Привести команды для запуска приложений. Можно привести screenshot'ы нескольких этапов выполнения программ.
Результат работы
Описать результаты выполнения курсовой работы (и положительные, и отрицательные). Если какую-то часть задания реализовать не удалось – описать причины.
Вывод
Сделать вывод по результатам работы. Насколько полно выполнено задание? Всем ли требованиям соответствует решение?
Приложения
Привести исходный код всех приложений и код скриптов для сборки.
Примечание: при выполнении задания не требуется написание сложного графического интерфейса, достаточно использовать консоль. В некоторых задачах удобно использовать символы псевдографики.
Варианты
Номер варианта | Задание | Литература |
1 | Многопользовательская сетевая игра «крестики-нолики». Возможность играть с компьютером | Скотт Граннеман «Linux. Карманный справочник»; Брюс Моли «Unix/Linux. Теория и практика программирования»; http://ru. wikipedia. org/wiki/Крестики-нолики; http://www. osp. ru/nets/1997/06/142618/; http://citforum. ru/programming/unix/sockets/; http://www. /alan/tutorials/tcpip/TCP-IP-complete. pdf |
2 | Многопользовательская сетевая игра «морской бой». Возможность играть с компьютером | Скотт Граннеман «Linux. Карманный справочник»; Брюс Моли «Unix/Linux. Теория и практика программирования»; http://ru. wikipedia. org/wiki/Морской_бой; http://www. osp. ru/nets/1997/06/142618/; http://citforum. ru/programming/unix/sockets/; http://www. /alan/tutorials/tcpip/TCP-IP-complete. pdf |
3 | Другая многопользовательская сетевая игра. Возможность играть с компьютером. Задание обязательно согласовывается с преподавателем | Скотт Граннеман «Linux. Карманный справочник»; Брюс Моли «Unix/Linux. Теория и практика программирования»; http://www. osp. ru/nets/1997/06/142618/; http://citforum. ru/programming/unix/sockets/; http://www. /alan/tutorials/tcpip/TCP-IP-complete. pdf |
4 | Сетевой чат. Число одновременно подключённых клиентов больше 3-х. Хранение истории сообщений. Возможность отправлять приватные сообщения (только конкретному собеседнику) | Скотт Граннеман «Linux. Карманный справочник»; Брюс Моли «Unix/Linux. Теория и практика программирования»; http://www. osp. ru/nets/1997/06/142618/; http://citforum. ru/programming/unix/sockets/; http://www. /alan/tutorials/tcpip/TCP-IP-complete. pdf |
5 | Другое многопользовательское сетевое приложение. Возможно использование нескольких серверов. Задание обязательно согласовывается с преподавателем | Скотт Граннеман «Linux. Карманный справочник»; Брюс Моли «Unix/Linux. Теория и практика программирования»; http://www. osp. ru/nets/1997/06/142618/; http://citforum. ru/programming/unix/sockets/; http://www. /alan/tutorials/tcpip/TCP-IP-complete. pdf |
3 Разработка и программная реализация параллельных игровых алгоритмов
Все курсовые работы выполняются под ОС Linux.
Предполагается, что будет использован язык C++.
Задание 1 Курсовая работа «Крестики-нолики»
Интерфейс – консольный или графический на выбор студента.
Должна присутствовать возможность играть вдвоем или против компьютера.
Ход каждого игрока просчитывается в отдельном потоке.
(При работе в паре: первый делает игру против компьютера, второй – против человека).
Подробное описание.
Требуется реализовать программу на языке C или C++ под OS Linux. Интерфейс с пользователем можно осуществлять через консоль.
Пример интерфейса:
...
.x.
o..
Т. е. в начале каждого хода достаточно выводить 3 строки по 3 символа, которые отображают текущее состояние клетки поля - пустая, установлен нолик, установлен крестик.
(Аналогичный консольный интерфейс допустим и для всех остальных курсовых работ).
В игре участвуют два игрока.
Для их обработки требуется создать 2 дополнительных потока (threads).
За весь вывод на экран в любом случае должен отвечать только один основной поток. (Это относится ко всем курсовым работам).
Пример последовательности взаимодействия потоков показан на следующей диаграмме:
Задание 2 Курсовая работа «Игра "3 пальца"»
Интерфейс – консольный.
Количество игроков = 2. Управлять каждым может как человек, так и компьютер.
Ход каждого игрока просчитывается в отдельном потоке.
Требуется организовать взаимодействие нескольких процессов: 2 игрока и 1 ведущий (т. е. подсчет суммы).
Вывод результата на экран производится в основном потоке.
Суть задачи: игроки одновременно показывают 1, 2 или 3 пальца. Далее ведущий подсчитывает сумму очков S (по общему количеству показанных пальцев). Если сумма четная, то выигрывает второй игрок, иначе выигрывает первый игрок. Выигравший игрок добавляет эту сумму S к своим очкам, проигравший вычитает S из своих очков. Изначально у каждого игрока ноль очков.
Количество раундов задается в параметрах командной строки при запуске приложения. После окончания игры требуется вывести финальное количество очков каждого игрока.
(При работе в паре: первый делает игру против компьютера, второй – против человека).
Задание 3 Курсовая работа «Гонки»
Интерфейс – консольный или графический на выбор студента.
Игроки только компьютерные.
Суть задачи: на экране постепенно заполняется несколько (от 2 до 10) полосок (progress bar). Каждый ход каждая полоска получает случайное приращение.
За обработку хода каждой полоски отвечает отдельный поток.
Вывод результатов гонки на экран производятся в основном потоке.
Задание 4 Курсовая работа «Морской бой»
Интерфейс – консольный или графический на выбор студента.
Количество игроков = 2. Управлять каждым может как человек, так и компьютер.
Суть задачи:
В начале игры задается расположение кораблей каждого игрока – чтением координат кораблей из файла или случайным образом. В процессе расстановки кораблей программа должна проверить то, что их количество верное: 1 из 4 клеток, 2 из 3 клеток, 3 из 2х, 4 корабля по 1 клетке. Корабли не могут соприкасаться краями и углами. Корабли не могут быть изогнуты или установлены по диагонали, т. е. все клетки корабля располагаются либо горизонтально, либо вертикально.
В начале каждого хода экран очищается и выводится 2 поля 10x10 клеток.
На поле игрока, который сейчас должен ходить, отмечены пораженные клетки и корабли. На втором поле отмечены только пораженные клетки. Если в пораженной клетке был корабль, то это должно быть также указано (цветом или особым символом).
Ход игрока состоит в указании координат клетки поля соперника, которая далее будет считаться пораженной. В случае нахождении корабля в пораженной клетке, ход остается у того же игрока, в противном случае ход переходит противнику.
За обработку хода каждого игрока отвечает отдельный поток.
(При работе в паре: первый делает игру против компьютера, второй – против человека для 2 игроков).
Обязательное дополнение для реализации параллельных процессов:
Компьютерный игрок в процессе ожидания завершения хода другого игрока (неважно, компьютерного или нет) должен составить для себя список последовательности клеток, по которому он собирается поражать клетки другого игрока. Таким образом, к началу своего хода, компьютер уже должен быть готов ходить без дополнительных размышлений. В случае обнаружения корабля противника, компьютерный игрок должен начать построение списка с нуля, с учетом выясненной информации. Но построение нового списка должно начаться только когда ход перейдет к противнику, текущий ход будет производиться без использования списка, непосредственным выбором координат стрельбы.
Задание 5 Курсовая работа «Червяки»
Интерфейс – консольный или графический на выбор студента.
Игроки могут быть как люди, так и компьютерные.
На экране от 2 до 8 червяков.
Суть задачи: Игровое поле – пустое пространство, на котором нанесены цифры. Каждый игрок управляет червяком. Червяк состоит из головы, занимающей одну клетку и хвоста, который изначально занимает еще 3 клетки.
Каждый ход все червяки на экране сдвигаются на 1 ход в одном из доступных направлений (вперед, влево или вправо от текущего направления головы). В выбранную новую доступную клетку сдвигается голова червя, все остальные клетки червя сдвигаются вслед за предыдущей клеткой.
Если голова червя оказывается на клетке с цифрой, то она съедается, т. е. удаляется с поля. Хвост червя увеличивается на количество клеток, равное съеденной цифре. Удлинение червя происходит за счет отсутствия перемещения кончика хвоста, в то время как голова и остальной хвост продолжают перемещаться дальше.
На следующий ход вместо съеденных цифр на поле помещаются новые. Количество цифр должно оставаться неизменным, но значения добавляемых цифр могут быть другими.
Доступной для перемещения считается пустая клетка или клетка с цифрой. Если голова червя сделала ход в недопустимую клетку, то червяк погибает и убирается с поля. Игра продолжается, пока жив хотя бы 1 червяк. В конце выводится сумма цифр, съеденных каждым червяком.
Каждый червяк управляется индивидуальным потоком.
Если сразу за нескольких игроков играют люди, то ходы делаются пошагово. На экране отображается номер текущего игрока, который должен указать направление следующего перемещения своего червяка. Если игрок только один, то перемещение может осуществляться либо в пошаговом режиме, либо динамически без задержек, по выбору студента. Все червяки на игровом поле двигаются с одинаковой скоростью.
(Чтобы просмотреть пример реализации игровой модели, можно ввести в консоли gnibbles).
(При работе в паре: первый делает игру против компьютера, второй – против человека).
Задание 6 Курсовая работа «Пакман»
Интерфейс – консольный или графический на выбор студента.
Суть задачи: игровое поле – лабиринт. Каждая клетка лабиринта может иметь от 1 до 4 стенок. На игровом поле присутствуют от 2 до 4 Пакманов.
Каждым Пакманом управляет игрок или компьютер.
Каждый ход производится перемещение каждого Пакмана в соседнюю клетку. Перемещаться сквозь стены нельзя.
Цель – посетить первым максимальное число клеток лабиринта.
Непосещенные никем клетки должны быть помечены на экране точкой.
За посещение каждой новой клетки (т. е. за взятие точки) тому Пакману, который это сделал, добавляется 1 очко.
Игра заканчивается, когда все клетки оказываются посещенными (т. е. все точки собраны).
После завершения игры требуется вывести количество очков, набранных каждым игроком.
Каждый Пакман управляется индивидуальным потоком.
Если сразу за несколько игроков играют люди, то ходы делаются пошагово. На экране отображается номер текущего игрока, который должен указать направление следующего перемещения. Если игрок только один, то перемещение может осуществляться либо в пошаговом режиме, либо динамически без задержек, по выбору студента. Все пакманы на игровом поле двигаются с одинаковой скоростью.
(Пример игровой модели можно посмотреть по адресу http://www. /pacman/)
(При работе в паре: первый делает игру против компьютера, второй – против человека).
Задание 7 Курсовая работа «Параллельный волновой алгоритм»
Интерфейс – консольный или графический на выбор студента.
Требуется реализовать волновой алгоритм с использованием параллельных потоков.
Описание идеи волнового алгоритма: http://algolist. manual. ru/maths/graphs/shortpath/wave. php
Задача: дан лабиринт MxN клеток. Каждая клетка лабиринта может иметь от 1 до 4 стенок. Дана стартовая клетка. Все эти характеристики и структура лабиринта читаются из входного файла. Количество рабочих потоков также должно читаться из входного файла.
Требуется определить длину пути из стартовой клетки во все остальные клетки лабиринта. Если клетка недостижима (или еще не исследована), то расстояние должно быть установлено равным -1.
Для повышения эффективности использования параллельных потоков следует использовать обход в глубину.
Основной алгоритм: При обнаружении нескольких возможных путей продолжения обхода – требуется направить текущий поток в последний найденных путь. А в пути, найденные ранее, нужно направить новые потоки, если еще не все рабочие потоки (указанные на входе) были задействованы.
Для каждой клетки нужно хранить ее расстояние от стартовой клетки и номер потока, который записал это расстояние.
Чтение и запись данных в структуру лабиринта (в матрицу MxN) должно быть синхронизовано между всеми потоками.
В результате работы программы требуется вывести на экран, в выходной поток или в файл следующую информацию:
Клетки лабиринта, пройденные первым потоком и записанная в них длина пути;
Клетки лабиринта, пройденные 2 потоком и записанная в них длина пути;
...
Клетки лабиринта, пройденные n потоком и записанная в них длина пути;
Итоговый лабиринт, в котором отображены расстояния от начальной клетки и номера потоков, которые последними записывали информацию в данную клетку.
(Допускается работе в паре и сдача одного отчета на двоих).
Задание 8
Можно придумать собственное задание на курсовую работу.
Основное условие: параллельные потоки должны реально параллельно работать для решения одной задачи, а не быть простым разделением независимых задач (как в курсовой №1). Т. е. требуется придумать задание, в котором алгоритм работы будет не таким: «отдать задачу первому потоку, дождаться результата, отдать задачу второму потому, дождаться его результата, и после этого продолжать самому». И не таким: «в первом потоке рисуем GUI, а во втором параллельно делаем вычисления и периодически посылаем сигналы первому на обновление GUI с учетом результатов промежуточных вычислений».
Требуется придумать задание, в котором одна большая задача будет разделена на множество подзадач, которые будут работать максимально независимо и реально параллельно.
Пример: Параллельный многопоточный поиск максимума в массиве.
(Когда n/2 потоков могут одновременно вычислить максимумы половины элементов массива, потом еще n/4 потоков могут вычислить максимумы оставшихся элементов и т. п.)
Основные порталы (построено редакторами)