4. Многопоточные приложения

Ю.В. Земсков. Вычислительные сети. Версия 0.20. — Санкт-Петербургский гос. университет гражданской авиации, 2012

При запуске программы в командной строке указываются имена файлов, для каждого файла создаётся свой поток (тред); он подсчитывает количество пробелов в файле и выводит на консоль соответствующее сообщение.

В Visual C требуется использовать потокобезопасную библиотеку libcmt.lib, чтобы сообщения, выводимые разными потоками на экран, не перепутывались (иначе оказывается, что один из потоков начиначет выводить своё сообщение, не дожидаясь, пока завершится вывод сообщения другого потока).

4.2. Методы синхронизации потоков

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

— 25 —

Ю.В. Земсков. Вычислительные сети. Версия 0.20. — Санкт-Петербургский гос. университет гражданской авиации, 2012

4.3.Варианты заданий

1.Модифицировать программу (см. листинг ??, ?? или 1) так, чтобы каждый поток осуществлял вывод на консоль, только если работа других потоков с консолью уже закончена или ещё не начата. Для синхронизации использовать:

1.1.критические секции;

1.2.мьютексы;

1.3.семафоры.

2.Модифицировать программу (см. листинг ??, ?? или 1) так, чтобы каждому потоку передавался в качестве входного параметра кроме имени файла ещё и адрес элемента массива целых чисел, в который поток должен поместить результат своей работы — количество пробелов в своём файле. Главная программа должна распечатать значения элементов этого массива вместе с именами файлов, после того как все потоки завершат свою работу. Для реализации ожидания в главной программе необходимо использовать:

2.1.проверку всех элементов массива в цикле;

2.2.ожидание с помощью вызова WaitForMultipleObjects;

3.Задача “читатели–писатели”. Два класса процессов имеют доступ

кнекоторому разделяемому ресурсу (области памяти, файлу, порту устройства ввода–вывода). “Читатели” — это процессы, которые могут параллельно считывать информацию из ресурса, а “писатели” — процессы, записывающие информацию в этот ресурс. Провести моделирование данной ситуации с выводом результатов в наглядном виде на экран. Варианты:

3.1.приоритет выше у “читателей”: если хотя бы один “читающий” процесс получил доступ к ресурсу, то он закрывается для “писателей”;

3.2.приоритет выше у “писателей”: если хотя бы один “пишущий” процесс запросил доступ к ресурсу, то он закрывается для “читателей”, запросивших доступ к этому ресурсу после этого;

3.3.в каждый момент времени только один пишущий процесс может получить доступ к ресурсу, в это время читать информацию могут одновременно несколько, но не более процессов.

4.Задача о пяти обедающих философах (классическая задача параллельного программирования, предложена Эдсгером Дейкстрой). В давние

—26 —

Ю.В. Земсков. Вычислительные сети. Версия 0.20. — Санкт-Петербургский гос. университет гражданской авиации, 2012

времена один богатый филантроп пожертвовал свой капитал на учреждение некоего пансиона, чтобы дать пристанище пяти знаменитым философам. У каждого философа была своя комната, где он мог предаваться размышлениям. Была у них и общая столовая с круглым столом, вокруг которого стояло пять стульев, каждый помеченный именем того философа, которому он предназначался. Звали философов Phil1, Phil2, Phil3, Phil4 и Phil5, и за столом они располагались в этом же порядке против часовой стрелки. Слева от каждого философа лежала золотая вилка, а в центре стола стояла большая миска спагетти, содержимое которой постоянно пополнялось. Предполагалось, что большую часть времени философ проводил в размышлениях, но, почувствовав голод, шёл в столовую, садился на свой стул, брал слева от себя вилку и приступал к еде. Но такова уж сложная природа спагетти, что их не донести до рта без помощи второй вилки. Поэтому философу приходилось брать вилку и справа от себя. Закончив трапезу, он клал на место обе вилки, выходил из-за стола и возвращался к своим размышлениям. Разумеется, одной вилкой философы могли пользоваться только по очереди. Если же вилка требовалась другому философу, ему приходилось ждать, пока она освободится. Таким образом, жизнь каждого философа представляет собой повторение цикла из семи последовательно сменяющих друг друга состояний: 1) размышляет; 2) хочет кушать; 3) садится; 4) берёт левую вилку (если она занята, то ждёт её освобождения); 5) берёт правую вилку (если она занята, то ждёт её освобождения); 6) ест; 7) кладёт обе вилки.

4.1.Необходимо создать приложение, моделирующее поведение пяти философов с выводом результатов моделирования в наглядном виде на экран. В результате работы программы необходимо увидеть ситуацию статического дедлока (все пять философов проголодались, взяли вилку слева от себя, а вилки справа уже нет), приводящего

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

4.2.Попытка “наивного” решения данной задачи: каждый философ может держать вилку не дольше определённого времени, после чего он устаёт и кладёт её обратно (независимо от того, владел ли он обеими вилками или ожидал освобождения второй). Создать приложение, моделирующее поведение пяти философов в этом случае. Необходимо наблюдать ситуацию динамического дедлока (все пять философов устали одновременно, положили вилки слева от себя, а после отдыха взяли их опять).

4.3.Другое решение задачи — появление слуги (решение предложено Карелом С. Шолтеном). В обязанности слуги входит сопровожде-

—27 —

Ю.В. Земсков. Вычислительные сети. Версия 0.20. — Санкт-Петербургский гос. университет гражданской авиации, 2012

ние каждого философа за стол и из-за стола. Слуге даётся секретное указание следить за тем, чтобы за столом никогда не оказывалось более четырёх философов одновременно. Поскольку вилок в этой ситуации всегда больше, то опасности дедлока нет. Хотя появляется другая опасность. Предположим, что левая рука у сидящего философа весьма медлительна, в то время как его левый сосед в высшей степени проворен. Прежде чем философ дотянется до своей левой вилки, его левый сосед быстро вступает в дело, садится, хватает обе вилки и долго ест. Рано или поздно наевшись, он кладёт обе вилки на стол и покидает своё место. Но стоит ему встать, как он снова ощущает голод, возвращается к столу, садится, мгновенно хватает обе вилки — и всё это прежде, чем его медлительный, долгосидящий и изнывающий от голода правый сосед дотянется до их общей вилки. Поскольку такого рода цикл может повторяться неограниченно долго, может оказаться, что сидящий философ никогда не приступит к еде. Похоже, что при строгом подходе эта проблема неразрешима, поскольку если каждый философ столь жаден и проворен, как было описано, то неизбежно кто-нибудь (или он, или его сосед) очень долгое время будет оставаться голодным. В такой ситуации не видно эффективного решения к достижению общего удовлетворения, кроме как приобрести достаточное количество вилок (по условию задачи проблем с поставками спагетти не имеется). Однако, чтобы все-таки гарантировать доступ к спагетти для каждого сидящего философа, нужно изменить поведение слуги: проводив философа до его места, слуга должен ждать, пока философ не возьмёт обе вилки и только после этого может позволить сесть его соседям. Однако, остаётся более философская проблема. Предположим, что слуга испытывает иррациональную неприязнь к одному из философов и постоянно затягивает исполнение своей обязанности проводить его к столу, даже если философ к этому готов. Это ситуация, которую мы не можем описать формально, поскольку она неотличима от той, когда философу требуется бесконечно длительное время, чтобы проголодаться. Заметим, что слуга может быть реализован в виде семафора, максимальное значение счётчика которого должно быть на 1 меньше числа философов.

4.4.Условия те же, что и в пункте 4а, но правила упрощены: философ может брать вилки в произвольном порядке.

4.5.Условия те же, что и в пункте 4б, но правила упрощены: философ может брать вилки в произвольном порядке.

4.6.Условия те же, что и в пункте 4в, но правила упрощены: философ может брать вилки в произвольном порядке.

—28 —