Билет 37. Задача поставщик-потребитель и ее решение.

Синхронизация сотрудничающих потоков
(поставщик – потребитель)

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

Const N=100;

Var S, SS, SN: semaphore;

Begin

S:=1; SS:=0; SN:=N;

Parbegin

Поставщик: while true do begin

… { генерация собщения}

P(SN); P(S);

… {запись сообщения}

V(SS); V(S);

End;

And

Потребитель: while true do begin

P(SS); P(S);

…{ чтение сообщения}

V(SN); V(S);

… {обработка сообщения}

End;

Parend

End.

Здесь N – число буферов в пуле, S – двоичный семафор, используемый для регулирования доступа к пулу буферов как при записи так и при считывании, SS и SN – числовые семафоры, используемые как сч¨тчики числа занятых и свободных буферов в пуле соответственно.

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

Пусть пул буферов частично занят (числовые поля SS и SN имеют целые положительные значения), и управление получает Поставщик. Он создаст новое сообщение, последовательно выполнит P(SN) и P(S), и начнёт запись. Если в этот момент управление получит Потребитель, то он выполнит P(SS), затем P(S), и здесь заблокируется по семафору S. Потребитель сможет деблокироваться только после того, как Поставщик закончит запись и выполнит операцию V(S). Другими словами, пока очередная запись в пул не закончена чтение из пула невозможно, и наоборот.

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

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

Билет 38. Задача обедающих философов.

Пять безмолвных философов сидят вокруг круглого стола, перед каждым философом стоит тарелка спагетти. Вилки лежат на столе между каждой парой ближайших философов.

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

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

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

Официант

Относительно простое решение задачи достигается путём добавления официанта возле стола. Философы должны дожидаться разрешения официанта перед тем, как взять вилку. Поскольку официант знает, сколько вилок используется в данный момент, он может принимать решения относительно распределения вилок и тем самым предотвратить взаимную блокировку философов. Если четыре вилки из пяти уже используются, то следующий философ, запросивший вилку, вынужден будет ждать разрешения официанта — которое не будет получено, пока вилка не будет освобождена. Предполагается, что философ всегда пытается сначала взять левую вилку, а потом — правую (или наоборот), что упрощает логику. Официант работает, как семафор — понятие, введённое Дейкстрой в 1965 году.^[

Чтобы показать, как это решение работает, предположим, что философы обозначены от А до Д по часовой стрелке. Если философы А и В едят, то заняты четыре вилки. Философ Б сидит между А и В, так что ему недоступна ни одна из вилок. В то же время, философы Г и Д имеют доступ к одной неиспользуемой вилке между ними. Предположим, что философ Г хочет есть. Если он тут же берёт свободную вилку, то становится возможна взаимная блокировка философов. Если вместо этого он спрашивает разрешения у официанта, то тот просит его подождать — и можно быть уверенным в том, что как только пара вилок освободится, то по крайней мере один философ сможет взять две вилки. Таким образом, взаимная блокировка становится невозможной.

Иерархия ресурсов

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

Пусть ресурсы (вилки) будут пронумерованы от 1 до 5, и каждая рабочая единица (философ) всегда берёт сначала вилку с наименьшим номером, а потом вилку с наибольшим номером из двух доступных. Далее, философ кладёт сначала вилку с бо́льшим номером, потом — с меньшим. В этом случае, если четыре из пяти философов одновременно возьмут вилку с наименьшим номером, на столе останется вилка с наибольшим возможным номером. Таким образом, пятый философ не сможет взять ни одной вилки. Более того, только один философ будет иметь доступ к вилке с наибольшим номером, так что он сможет есть двумя вилками. Когда он закончит использовать вилки, он в первую очередь положит на стол вилку с бо́льшим номером, потом — с меньшим, тем самым позволив другому философу взять недостающую вилку и приступить к еде.

Данное решение было предложено Дейкстрой.

В то время, как иерархия ресурсов позволяет избежать взаимных блокировок, данное решение не всегда является практичным, в особенности когда список необходимых ресурсов неизвестен заранее. Например, если рабочая единица удерживает ресурс 3 и 5 и решает, что ей необходим ресурс 2, то она должна выпустить ресурс 5, затем 3, после этого завладеть ресурсом 2 и снова взять ресурс 3 и 5. Компьютерные программы, которые работают с большим количеством записей в базе данных, не смогут работать эффективно, если им потребуется выпускать все записи с верхними индексами прежде, чем завладеть новой записью. Это делает данный метод непрактичным.

Решение на основе монитора

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

В отсутствии блокировок, связанных с вилками, философы должны обеспечивать то, что начало принятия пищи не основывается на старой информации о состоянии соседей. Например: Если философ B видит, что A не ест в данный момент времени, а потом поворачивается и смотрит на C, A мог начать есть, пока философ B смотрит на C. Используя одну взаимоисключающую блокировку, можно избежать этой проблемы. Эта блокировка не связана с вилками, но она связана с решением процедур, которые могут изменить состояние философов. Это обеспечивается монитором.

Алгоритм монитора реализует схему «проверить, взять и положить» и разделяет взаимоисключающую блокировку. Заметьте, что философы, желающие есть, не будут иметь вилок.

Если монитор разрешает философу, желающему есть, действовать, то философ снова завладевает первой вилкой, прежде чем взять уже свободную вторую.

По окончании текущего приёма пищи философ оповещает монитора о том, что обе вилки свободны.

Стоит заметить, что этот алгоритм монитора не решает проблемы голодания. Например, философ B может бесконечно ждать своей очереди, если у философов A и C периоды приёма пищи всё время пересекаются. Чтобы гарантировать также, что ни один философ не будет голодать, можно отслеживать, сколько раз голодный философ не ел, когда его соседи положили вилки на стол. Если количество раз превысит некий предел, такой философ перейдёт в состояние Голодания и алгоритм монитора форсирует процедуру завладения вилками, выполняя условие недопущения голодания ни одного из соседей.

Философ, не имеющий возможности взять вилки из-за того, что его сосед голодает, находится в режиме полезного ожидания окончания приёма пищи соседом его соседа. Эта дополнительная зависимость снижает параллелизм. Увеличение значения порога перехода в состояние Голодание уменьшает этот эффект.

Билет 39. Взаимные блокировки, клинчи или тупики. Причины возникновения, проявление, последствия. Пример тупика двух потоков. Средства распознавания тупиков.

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

На рис. 4.22, а показаны фрагменты соответствующих программ. Поток А запрашивает сначала принтер; а затем порт, а поток В запрашивает устройства в обратном порядке. Предположим, что после того, как ОС назначила принтер потоку А и установила связанную с этим ресурсом блокирующую переменную, поток А был прерван. Управление получил поток В, который сначала выполнил запрос на получение СОМ- порта, затем при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым потоком А. Управление снова получил поток А, который в соответствии со своей программой сделал попытку занять порт и был заблокирован, поскольку порт уже выделен потоку В. В таком положении потоки А и В могут находиться сколь угодно долго.

В зависимости от Соотношения скоростей потоков они могут либо взаимно блокировать друг друга (рис. 4.22, б), либо образовывать очереди к разделяемым ресурсам (рис. 4.22, в), либо совершенно независимо использовать разделяемые ресурсы (рис. 4.22, г).

Рис. 4.22. Возникновение взаимных блокировок при выполнении программы

ПРИМЕЧАНИЕ

Тупиковые ситуации надо отличать от простых очередей* хотя те и другие возникают при совместном использовании ресурсов и внешне выглядят похоже: поте* приостанавливается и ждет освобождения ресурса. Однако очередь — это нормальное явление, неотъемлемый признак высокого коэффициента использования ресурсов при случайном поступлении запросов. Очередь появляется тогда, когда ресурс недоступен в данный момент, но освободится через некоторое время, позволив потоку продолжить выполнение. Тупик же, что видно из его названия, является в некотором роде неразрешимой ситуацией. Необходимым условием возникновения тупика является потребность потока сразу в нескольких ресурсах.Невозможность потоков завершить начатую работу из-за возникновения взаимных блокировок снижает производительность вычислительной системы. Поэтому проблеме предотвращения тупиков уделяется большое внимание. На тот случай, когда взаимная блокировка все же возникает, система должна предоставить администратору-оператору средства, с помощью которых он смог бы распознать тупик, отличить его от обычной блокировки из-за временной недоступности ресурсов. И наконец, если тупик диагностирован, то нужны средства для снятия взаимных блокировок и восстановления нормального вычислительного процесса.

Рис. 4.23. Взаимная блокировка нескольких потоков

Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть при любом соотношении взаимных скоростей потоков. Так, если бы в примере, показанном на рис. 4.22, поток А и поток В запрашивали ресурсы в одинаковой последовательности, то тупик был бы>в принципе невозможен. Другой, более гибкий подход к предотвращению тупиков заключается в том, что ОС каждый раз при запуске задач анализирует их потребности в ресурсах и определяет, может ли в данной мультипрограммной смеси возникнуть тупик. Если да, то запуск новой задачи временно откладывается. ОС может также использовать определенные правила при назначении ресурсов потокам, например, ресурсы могут выделяться операционной системой в определенной последовательности, общей для всех потоков.

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

Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные потоки/Можно снять только часть из них, освободив ресурсы, ожидаемые остальными потоками, можно вернуть некоторые потоки в область подкачки, можно совершить -«откат» некоторых потоков до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в тех местах, после которых возможно возникновение тупика.