Многопоточное и распределенное программирование.

Список №1 задач для лабораторно-практических работ.

1. Обедающие философы. Стандартный вариант: k философов, k вилок, граф связей – кольцо (философ-вилка-философ-…).

2. Обедающие философы. Задан двудольный граф связей n философов и m вилок (для того, чтобы приступить к обеду, философ должен взять две вилки из тех, до которых может дотянуться согласно графу связей и которые еще не взяты другими философами).

3. Обедающие философы. Задан трехдольный граф связей n философов, m вилок, k ножей. (для того, чтобы приступить к обеду, философ должен взять одну вилку и один нож из тех, до которых может дотянуться согласно графу связей и которые еще не взяты другими философами)

4. Обедающие философы. Задан k-дольный (k больше 3) граф связей n философов и k видов столовых приборов (для того, чтобы приступить к обеду, философ должен взять по одному прибору из тех, до которых может дотянуться согласно графу связей и которые еще не взяты другими философами)

5. Производитель-потребитель. Производителей сообщений n, потребителей m, сообщения однотипны, и могут обрабатываться любым потребителем, очередь сообщений одна, ее емкость не ограничена.

6. Производитель-потребитель. Производителей сообщений n, потребителей m, сообщения однотипны, очередь сообщений имеет вид кольцевого буфера, производители и потребители подключены к буферу в разных точках, производитель может захватывать только свободную позицию буфера, потребитель не обязан забирать сообщение из первой же занятой позиции.

7. Производитель-потребитель. Производителей n, потребителей m, сообщения однотипны, очередей сообщений k, их емкости не ограничены, все производители и потребители связаны со всеми очередями, выбор очереди случаен.

8. Производитель-потребитель. Производителей сообщений n, потребителей m, сообщения однотипны, очередь сообщений имеет вид кольцевого буфера, производители и потребители подключены к буферу в разных точках, производитель может захватывать только свободную позицию буфера, потребитель обязан забирать сообщение из первой же занятой позиции.

9. Производитель-потребитель. Производителей n, потребителей m, сообщения адресованы конкретному потребителю, очередь сообщений одна, ее емкость не ограничена.

10. Производитель-потребитель. Производителей n, потребителей m, сообщения однотипны, очередей сообщений k, емкости очередей ограничены (не более z), все производители и потребители связаны со всеми очередями.

11. Производитель-потребитель. Производителей n, потребителей m, сообщения адресованы конкретному потребителю, очередей сообщений k, их емкости не ограничены, все производители и потребители связаны со всеми очередями, выбор очереди случаен.

12. Производитель-потребитель. Производителей n, потребителей m, сообщения однотипны, очередь сообщений одна, ее емкость k сообщений.

13. Производитель-потребитель. Производителей n, потребителей m, сообщения однотипны, очередей сообщений k, их емкости ограничены и фиксированы, все производители и потребители связаны со всеми очередями, выбор очереди случаен.

14. Производитель-потребитель. Производителей n, потребителей m, сообщения адресованы конкретному потребителю, очередь сообщений одна, ее емкость k сообщений.

15. Производитель-потребитель. Производителей n, потребителей m, сообщения адресованы конкретному потребителю, очередей сообщений k, их емкости ограничены и фиксированы, все производители и потребители связаны со всеми очередями, выбор очереди случаен.

16. Производитель -посредник-потребитель. Каждый из n производителей через случайные моменты времени формирует сообщение для одного конкретного потребителя (всего потребителей m) и размещает в общей очереди неограниченного объема. Каждый из k посредников выбирает сообщение из этой очереди и пытается записать его в очередь фиксированного размера для указанного потребителя. Если очередь заполнена, посредник ожидает возможности записать сообщение в нее, но не дольше, чем в течение заданного интервала времени, по истечении которого сообщение теряется.

17. Читатели и писатели. В библиотеке может находиться одновременно не более n писателей (всего писателей N) и ни одного читателя, либо m читателей (всего читателей M) и ни одного писателя. Продолжительность желаемого времени нахождения в библиотеке по отношению к общему времени деятельности для писателя 1:T, для читателя – 1: S.

18. Читатели и писатели. В библиотеке может находиться одновременно не более n писателей (всего писателей N) и не более m читателей (всего читателей M). Продолжительность желаемого времени нахождения в библиотеке по отношению к общему времени деятельности для писателя 1:T, для читателя – 1:S.

19. Из n входных каналов поступают сообщения, их могут получать m обработчиков, результаты обработки подсчитываются в k счетчиках (суть обработки – определение значения номера счетчика в диапазоне от 0 до k-1). Каждое сообщение должно быть обработано в точности одним обработчиком. Интервалы времени между появлением сообщений случайны в некотором диапазоне, затраты времени на обработку случайны в том же диапазоне.

20. Хозяева и воры. В одну квартиру n хозяев время от времени приносят вещи, характеризующиеся такими параметрами: количество, вес, стоимость. Есть m воров, у каждого из них есть рюкзак (вместимости рюкзаков ограничены сверху предельными весами). В квартире могут одновременно находиться несколько хозяев (но может и не быть ни одного) или не более одного вора. Каждый вор стремится забрать вещи максимальной ценности, но не больше, чем входит в его рюкзак. Продолжительность нахождения и хозяина и вора в квартире случайна и ограничена сверху.

21. Хозяева и воры. В несколько (n) квартир их хозяева время от времени приносят вещи, характеризующиеся такими параметрами: количество, вес, стоимость. Есть m воров, у каждого из них есть рюкзак (вместимости рюкзаков ограничены сверху предельными весами). В каждой квартире могут одновременно либо ее хозяин, либо вор, либо квартира пуста. Каждый вор стремится набрать как можно больше вещей по весу, но не больше, чем войдет в его рюкзак. Продолжительность нахождения и хозяина и вора в квартире случайна и ограничена сверху.

22. В подъезде многоэтажного дома работают n лифтов, грузоподъемность их может быть различной. На разных этажах в случайные моменты времени люди нажимают кнопки вызова (вверх/вниз) нужного лифта. Если на этаже нажата любая кнопка, другой лифт в том же направлении с этого этажа вызвать нельзя, пока не приедет и не уедет вызванный лифт.

23. В подъезде многоэтажного дома работают n лифтов, грузоподъемность их может быть различной. На разных этажах в случайные моменты времени люди нажимают одну или две кнопки (вверх/вниз) вызова любого лифта.

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

25. На сортировочную станцию железной дороги в случайные моменты времени приходят поезда с вагонами, которые должны быть отправлены в разные направления. Поезда, составляемые из них, должны содержать не менее n и не более m вагонов

26. В морском порту для погрузки/разгрузки контейнеровозов работает n причалов, каждый причал может обслуживать один корабль. К каждому причалу подходит один железнодорожный путь для перегрузки контейнеров между кораблем и поездом. На одном поезде могут находиться контейнеры для нескольких кораблей, аналогично с одного корабля может быть необходимо разгрузить контейнеры на разные поезда.

27. Через турникеты станций метро пассажиры в случайные моменты времени проходят по транспортным картам. Нужно сформировать сводную таблицу величины пассажиропотока между каждой парой станций за заданный интервал времени, например, за сутки.

28. Пункты A, B, C, … связаны автобусным сообщением в соответствии с заданным графом. Автобус имеют вместимость k пассажиров и отправляются, если в нем занято не менее к/2 мест. Пассажиры появляются в пунктах посадки случайно или для пересадки на другой автобус.

29. На склад в случайные моменты времени приходят фуры с товарами (разные виды товаров имеют разные объемы на единицу), которые должны примерно поровну отправляться в n магазинов. Для перевозки товаров между складом и магазинами используется k грузовиков с объемом кузова не более m. Грузовик отправляется только тогда, когда его загрузка составляет не менее 90%.

30. Через ущелье переброшено n веревочных мостиков, движение по которым может быть только в одну сторону, грузоподъемности их ограничены и могут быть различными. Если по мосту движется хотя бы один человек в одну сторону, заходить на него для прохода в противоположном направлении нельзя. Затраты времени на прохождение моста одним человеком известны. Люди подходят с обеих сторон ущелья через случайные промежутки времени.