Методы борьбы с тупиками

Понятие тупиковой ситуации при выполнении параллельных вычислительных процессов
При параллельном исполнении процессов могут возникать тупиковые ситуации, когда два или более процесса блокируют друг друга, вынуждая ожидать наступления события, связанного с освобождением ресурса.
Самый простой случай: каждый из двух процессов ожидает ресурс, занятый другим процессом, ни один из процессов не может продолжить исполнение и освободить ресурс, необходимый другому процессу.
Эта ситуация называется тупиком, дедлоком, или клинчем.
Ресурсы системы разделяют на два класса:
• повторно используемые (Reusable Resource, RR), или системные (System Resource, SR), ресурсы;
• потребляемые, или расходуемые, ресурсы (Consumable Resource, CR).
Системные ресурсы (SR) – конечное множество идентичных единиц некоторого вида ресурсов, обладающих свойствами:
• число единиц ресурса в системе неизменно;
• каждая единица ресурса либо доступна, либо выделена одному и только одному процессу;
• процесс может освободить единицу ресурса (сделать ее доступной), только если он ранее получил эту единицу.
? Особенности расходуемых ресурсов (CR):
• число доступных единиц некоторого ресурса типа CR изменяется по мере того, как выполняющимися процессами они расходуются (приобретаются) и освобождаются (производятся);
• процесс «потребитель» уменьшает число единиц ресурса, сначала запрашивая и затем приобретая (потребляя) одну или более единиц.

Для исследования параллельных процессов и проблемы тупиков было разработано несколько моделей. Одна из них – модель повторно используемых ресурсов Холта. Согласно этой модели система представляется как набор (множество) процессов и набор ресурсов, каждый из ресурсов состоит из фиксированного числа единиц. Любой процесс может изменять состояние системы путем выдачи запроса на получение или освобождение единицы ресурса. В графической форме процессы и ресурсы представляются квадратами и кружками соответственно. Каждый кружок содержит некоторое количество маркеров (фишек) в соответствии с существующим количеством единиц этого ресурса. Дуга из «процесса» на «ресурс» означает запрос одной единицы этого ресурса. Дуга из «ресурса» на «процесс» – выделение ресурса процессу. Т.к. каждая единица ресурса типа SR может быть выделена одновременно не более чем одному процессу, то число дуг из ресурса к различным процессам не может превышать общего числа единиц этого ресурса. Такая модель называется графом повторно используемых ресурсов. Удовлетворение запроса Пр1 приведет к тупиковой ситуации: Пр1 не сможет продолжиться до тех пор, пока Пр2 не освободит единицу ресурса R1, а процесс Пр2 не сможет продолжиться до тех пор, пока Пр1 не освободит единицу R2. Примеры тупиковых ситуаций и причины их возникновения Пример тупика на ресурсах типа CR ? Пусть имеется три процесса Пр1, Пр2 и ПрЗ, которые вырабатывают сообщения Ml, M2 и МЗ, соответственно. Эти сообщения представляют собой ресурсы типа CR. Пусть процесс Пр1 является потребителем сообщения МЗ, процесс Пр2 должен получить сообщение Ml, а ПрЗ – сообщение М2 от процесса Пр2. Таким образом, каждый из этих трех процессов является и поставщиком, и потребителем одновременно, и вместе они образуют кольцевую систему (рис. 7.2) передачи сообщений через почтовые ящики (ПЯ). Если связь с помощью этих сообщений со стороны каждого процесса устанавливается программным кодом в порядке, когда они сначала посылают сообщение следующему процессу, а затем ожидают от предыдущего, то никаких проблем не возникает. Но перестановка этих двух процедур (сначала – ожидают, затем – посылают свое) в каждом из процессов вызывает тупик. Пример тупика на ресурсах типа CR и SR
Пусть процесс Пр1 должен обменяться сообщениями с процессом Пр2 и каждый из них запрашивает ресурс R, причем Пр1 требует три единицы этого ресурса для своей работы, а Пр2 — две единицы и только на время обработки сообщения. Всего же имеется только четыре единицы ресурса R. Запрос и освобождение ресурса можно реализовать через соответствующий монитор с процедурами запроса N единиц ресурса R, и освобождения (возврата) N единиц ресурса R. Обмен сообщениями осуществляется через почтовый ящик MB. Эти два процесса всегда будут попадать в состояние тупика. Процесс Пр2, выполняясь первым, сначала будет ожидать сообщения от процесса Пр1, затем будет заблокирован при запросе ресурса R, часть которого уже отдана процессу Пр1. Процесс Пр1, завладев частью ресурса R, будет заблокирован ожиданием ответа от Пр2, которого никогда не получит, так как для этого Пр2 нужно получить ресурс R, находящийся в распоряжении Пр1.
Тупика можно избежать лишь при условии, что на время ожидания ответа от Пр2 процесс Пр1 отдаст хотя бы одну из единиц ресурса R, которыми он владеет.
В данном примере, как и в предыдущем, причиной тупика являются ошибки программирования. Пример тупика на ресурсах типа SR – не рассматриваем, но возможен.
Для возникновения тупиковой ситуации необходимо одновременное выполнение следующих четырех условий:
взаимного исключения, при котором процессы осуществляют монопольный доступ к ресурсаможидания, при котором процесс, запросивший ресурс, ждет до тех пор, пока запрос не будет удовлетворен, при этом удерживая ранее полученные ресурсы;
отсутствия перераспределения, при котором ресурсы нельзя отобрать у процесса, если они ему уже выделены;
кругового ожидания, при котором существует замкнутая цепь процессов, каждый из которых ждет ресурс, удерживаемый его предшественником в цепи. 38. Методы борьбы с тупиками Борьба с тупиковыми ситуациями основывается на одной из трех стратегий: предотвращение тупика; обход тупика ;распознавание тупика с последующим восстановлением. Предотвращение тупиков Предотвращение тупика основывается на предположении о чрезвычайно высокой его стоимости Этот подход используется в наиболее ответственных системах, обычно в системах реального времени. Предотвращение можно рассматривать как запрет существования опасных состояний. Поэтому подсистема распределения ресурсов, предотвращающая тупик, должна гарантировать, что ни одного из четырех условий, необходимых для его наступления, не возникнет. Условие взаимного исключения можно подавить путем разрешения неограниченного разделения ресурсов. Условие ожидания можно подавить, предварительно выделяя ресурсы. При этом процесс может начать исполнение, только получив все необходимые ресурсы заранее. Это может привести к снижению эффективности работы вычислительной системы в целом, часто невозможно. Условие отсутствия перераспределения можно исключить, позволяя ОС отнимать у процесса ресурсы. Для этого в ОС должен быть предусмотрен механизм запоминания состояния процесса с целью последующего восстановления хода вычислений.
Условие кругового ожидании можно исключить, предотвращая образование цепи запросов. Это можно обеспечить с помощью принципа иерархического выделения ресурсов. Все ресурсы образуют иерархию. Процесс, затребовавший ресурс на одном уровне, может затем потребовать ресурсы только на более высоком уровне. Он может освободить ресурсы на данном уровне, только после освобождения всех ресурсов на всех более высоких уровнях. После того как процесс получил, а потом освободил ресурсы данного уровня, он может запросить ресурсы на том же самом уровне.
Обход тупиков Обход тупика можно рассматривать как запрет входа в опасное состояние. Если ни одно из упомянутых четырех условии не исключено, то вход в опасное состояние можно предотвратить при наличии у системы информации о последовательности запросов, связанных с каждым параллельным процессом.
Доказано, что если вычисления находятся в любом неопасном состоянии, то существует, по крайней мере, одна последовательность состояний, которая обходит опасное состояние. Поэтому достаточно проверить, не приведет ли выделение затребованного ресурса сразу же к опасному состоянию. Если да, то запрос отклоняется, если нет, его можно выполнить. Определение того, является состояние опасным или нет, требует анализа последующих запросов от процессов.
Классическое решение этой задачи предложено Дейкстрой и известно как алгоритм банкира.
Каждый раз, когда что-то может быть выделено из числа остающихся незанятыми ресурсов, предполагается, что соответствующий процесс работает, пока не окончится, а затем его ресурсы освобождаются.
Если в итоге все ресурсы освобождаются, значит, все процессы могут завершиться, и система находится в безопасном состоянии. ? Т.е., согласно алгоритму банкира система удовлетворяет только те запросы, при которых ее состояние остается надежным. Новое состояние безопасно тогда и только тогда, когда каждый процесс может окончиться. Именно это условие и проверяется в алгоритме банкира. Обнаружение тупика
Чтобы распознать тупиковое состояние, необходимо для каждого процесса определить, сможет ли он когда-либо снова развиваться, то есть изменять свои состояния.
Обнаружение тупика посредством редукции графа повторно используемых ресурсов:
Граф повторно используемых ресурсов сокращается процессом Рi, который не является ни заблокированной, ни изолированной вершиной, путем удаления всех ребер, входящих в вершину Рi и выходящих из Рi.
Граф повторно используемых ресурсов несокращаем, если он не может быть сокращен ни одним процессом.
Граф ресурсов типа SR является полностью сокращаемым, если существует последовательность сокращений, которая удаляет все дуги графа. Лемма: для ресурсов типа SR порядок сокращений дуг графа повторно используемых ресурсов несуществен; все последовательности ведут к одному и тому же несокращаемому графу.
Теорема о тупике: Состояние S есть состояние тупика тогда и только тогда, когда граф повторно используемых ресурсов в состоянии S не является полностью сокращаемым. Первое следствие: процесс не находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором он не заблокирован. Второе следствие: если S есть состояние тупика (по ресурсам типа SR), то по крайней мере два процесса находятся в тупике в S.
Из теоремы о тупике следует и алгоритм обнаружения тупиков. Нужно попытаться сократить граф; если граф полностью не сокращается, то начальное состояние было состоянием тупика для тех процессов, вершины которых остались в несокращенном графе. Лемма позволяет предложить алгоритмы обнаружения тупика. Например, можно представить систему посредством графа повторно используемых ресурсов и попробовать выполнить его редукцию.
Методы обнаружения тупика по наличию замкнутой цепочки запросов
Первая теорема: цикл в графе повторно используемых ресурсов является необходимым условием тупика.
Вторая теорема: тупик может быть вызван только при запросе, который не удовлетворен немедленно. Т.е. проверка на тупиковое состояние может быть выполнена боле эффективно, если она проводится непрерывно (по мере развития процессов).
Состояние называется фиксированным, если каждый процесс, выдавший запрос, заблокирован.
Третья теорема: если состояние системы фиксированное (все процессы, имеющие запросы, удовлетворены), то наличие узла в соответствующем графе повторно используемых ресурсов – достаточное условие тупика.
Четвертая теорема: граф повторно используемых ресурсов с единичной емкостью указывает на состояние тупика тогда и только тогда, когда он содержит цикл.
Алгоритм обнаружения тупика по наличию замкнутой цепочки запросов ? Распознавание тупика может быть основано на анализе модели распределения ресурсов. Один из алгоритмов, основанный на методе обнаружения замкнутой цепи запросов, был разработан сотрудниками фирмы IBM. Он использует информацию о состоянии системы, содержащуюся в двух таблицах: таблице текущего распределения ресурсов и таблице заблокированных процессов. При каждом запросе на получение или освобождение ресурсов содержимое этих таблиц модифицируется, а запрос анализируется в соответствии с заданным алгоритмом.
Распознавание тупика требует дальнейшего восстановления вычислений. Восстановление можно интерпретировать как запрет постоянного пребывания в опасном состоянии. Методы восстановления:
принудительный перезапуск системы с потерей информации обо всех процессах, существовавших до перезапуска; принудительное завершение процессов, находящихся в тупике;
принудительное последовательное завершение процессов, находящихся в тупике, с последующим вызовом алгоритма распознавания после каждого завершения до исчезновения тупика;
перезапуск процессов, находящихся в тупике, с некоторой контрольной точки;
перераспределение ресурсов с последующим последовательным перезапуском процессов, находящихся в тупике.

Объекты ядра используются системой и нашими приложениями для управления множеством разных ресурсов: процессами, потоками, файлами и т.д. Система позволяет создавать и оперировать с несколькими типами таких объектов, в том числе: маркерами доступа (access token objects), файлами (file objects), проекциями файлов (file-mapping objects), портами завершения ввода вывода (I/O completion port objects), заданиями (jobs), почтовыми ящиками (mailslot objects), мьютексами (mutex objects), каналами (pipe objects), процессами (thread objects) и ожидаемыми таймерами (waitable timer objects). Эти объекты создаются Windows-функциями. Например, CreateFileMapping заставляет систему сформировать объект «проекция файла». Каждый объект ядра – на самом деле просто блок памяти, выделенный ядром и доступный только ему. Блок представляет собой структуру данных, в элементах которой содержится информация об объекте. Некоторые элементы (дескриптор защиты, счетчик числа пользователей и др.) присутствуют во всех объектах, но большая их часть специфична для объектов конкретного типа. Например, у объекта «процесс» есть идентификатор, базовый приоритет и код завершения, а у объекта «файл» — смещение в байтах, режим разделения и режим открытия. Приложение не может напрямую обращаться к объектам ядра читать и изменять их содержимое. Для взаимодействия с объектами ядра у Windows предусмотрен набор функций, обрабатывающих структуры объектов ядра по строго определенным правилам. Когда мы создаем объект ядра, функция возвращает описатель идентифицирующий созданный объект (HANDLE). Все операции с текущим объектом ядра возможны только при указании этого описателя управляющей функции. Для большей защиты, описатели уникальны только внутри конкретного процесса. Поэтому, передавая по межпроцессорной связи описатель объекта другому процессу, используя описатель в другом процессе мы получим ошибку. Это ограничение можно обойти – но об этом позже. Учет пользователей объектов ядра. Объекты ядра принадлежат ядру, а не процессу. Это говорит о том, что завершая работу с процессом, мы не обязательно разрушаем объект ядра. В большинстве случаев объект разрушается, но если созданный вами объект ядра используется другим процессом, ядро запретит разрушение объекта до тех пор, пока от него не откажется последний пользователь. В каждом объекте, как уже говорилось, есть счетчик пользователей объектом. В момент создания, счетчику присваивается значение 1. Соответственно, при обращении к нему другого процесса, счетчик увеличивается на 1. Когда пользовательский процесс завершается, счетчик уменьшается. Система удаляет объект ядра, когда счетчик обнуляется. Защита объектов ядра Почти во всех функциях, создающих объекты, есть параметр SECURITY_ATTRIBUTES. Он необходим для защиты объектов ядра от несанкционированного доступа. Чаще всего, это свойство используют в серверных приложениях, в клиентских приложениях этот объект можно игнорировать. Если вы пишите для win98 то там такое свойство отсутствует, но для корректной работы таких приложений в Win2000 и выше, стоит помнить о работе с соответствующими механизмами. При передаче в таком атрибуте NULL большинство объектов будут созданы со стандартными свойствами защиты, когда к объекту допускаются: создатель и администраторская группа. Остальные игнорируются.Наследуются только описатели объектов, существующие на момент создания дочернего процесса. Если родительский процесс создаст после этого новые объекты ядра с наследуемыми описателями, то эти описатели будут уже недоступны дочернему процессу. Для наследования описателей объектов характерно одно очень странное свойство: дочерний процесс не имеет ни малеЙшего понятия, что он унаследовал какие-то описатсли. Поэтому наследование описятелей объектов ядра полезно, только когда дочерний процесс сообщает, что при его создании родительским процессом он ожидает доступа к какому-нибудь объекту ядра. Тут надо заметить, что обычно родительское и дочернее приложения пишутся одной фирмой, но в принципе дочернее приложение может написать и сторонняя фирма, если в этой программе задокументировано, чего именно она ждет от родительского процесса. Для этого в дочерний процесс обычно передают значение ожидаемого им описателя объекта ядра как аргумент в командной строке. Инициализирующий код дочернего процесса анализирует командную строку (чаще всего вызовом sscanf), извлекает из нее значение описателя, и дочерний процесс получает неограниченный доступ к объекту. При этом механизм наследования срабатывает только потому, что значение описателя общего объекта ядра в родительском и дочернем процессах одинаково, — и именно по этой причине родительский процесс может передать значение описателя как аргумент в командной строке. Для наследственной передачи описателя объекта ядра от родительского процесса дочернему, конечно же, годятся и другие формы межпроцессной сяязи Один из приемов заключается в том, что родительский процесс дожидается окончания инициализации дочернего (через функцию WaitForInputIdle рассматриваемую в главе 9), а затем посылает (синхронно или асинхронно) сообщение окну, созданному потоком дочернего процесса. Еще один прием: родительский процесс добавляет в свой блок переменных окружения новую переменную Она должна быть узнаваема дочерним процессом и содержать значение наследуемого описятеля объекта ядра, Далее родительский процесс создает дочерний, тот наследует переменные окружения родительского процесса и, вызвав GetEnvironmentVariable, получает нужный описатель. Такой прием особенно хорош, когда дочерний процесс тоже порождает процессы, — ведь все переменные окружения вновь наследуются.

Многопото?чность — свойство платформы (например, операционной системы, виртуальной машины и т. д.) или приложения, состоящее в том, что процесс, порождённый в операционной системе, может состоять из нескольких потоков, выполняющихся «параллельно», то есть без предписанного порядка во времени. При выполнении некоторых задач такое разделение может достичь более эффективного использования ресурсов вычислительной машины. Такие потоки называют также потоками выполнения (от англ. thread of execution); иногда называют «нитями» (буквальный перевод англ. thread) или неформально «тредами». Сутью многопоточности является квазимногозадачность на уровне одного исполняемого процесса, то есть все потоки выполняются в адресном пространстве процесса. Кроме этого, все потоки процесса имеют не только общее адресное пространство, но и общие дескрипторы файлов. Выполняющийся процесс имеет как минимум один (главный) поток. Многопоточность (как доктрину программирования) не следует путать ни с многозадачностью, ни с многопроцессорностью, несмотря на то, что операционные системы, реализующиемногозадачность, как правило реализуют и многопоточность. К достоинствам многопоточности в программировании можно отнести следующее:

  • Упрощение программы в некоторых случаях за счет использования общего адресного пространства.
  • Меньшие относительно процесса временны?е затраты на создание потока.
  • Повышение производительности процесса за счет распараллеливания процессорных вычислений и операций ввода/вывода.

Эти объекты создаются Windows-функциями. Например, CreateFileMapping заставляет систему сформировать объект “проекция файла”. Каждый объект ядра — на самом деле просто блок памяти, выделенный ядром и доступный только ему. Этот блок представляет собой структуру данных, в элементах которой содержится информация об объекте. Некоторые элементы (дескриптор защиты, счетчик числа пользователей и др.) присутствуют во всех объектах, но большая их часть специфична для объектов конкретного типа. Например, у объекта “процесс” есть идентификатор, базовый приоритет и код завершения, а у объекта “файл” — смещение в байтах, режим разделения и режим открытия. Объекты ядра принадлежат ядру, а не процессу. Иначе говоря, если процесс вызывает функцию, создающую объект ядра, а затем завершается, объект ядра может быть не разрушен. В большинстве случаев такой объект все же разрушается; но если созданный объект ядра используется другим процессом, ядро запретит разрушение объекта до тех
пор, пока от него не откажется и тот процесс. Хотя механизмы синхронизации в пользовательском режиме обеспечивают высокое быстродействие, им свойствен ряд ограничений, и во многих приложениях они просто не будут работать. Например, Interlocked-функции оперируют только с отдельными переменными и никогда не переводят поток в состояние ожидания. Последнюю задачу можно решить с помощью критических секций, но они подходят лишь в тех случаях, когда требуется синхронизировать потоки в рамках одного процесса. Кроме того, при использовании критических секций легко попасть в ситуацию взаимной блокировки
потоков, потому что задать предельное время ожидания входа в критическую секцию нельзя. Объекты ядра предоставляют куда больше возможностей, чем механизмы синхронизации в пользовательском режиме. Тем не менее, у них есть один существенный недостаток — меньшее быстродействие. Дело в том, что при вызове любой из функций, использующей объект ядра, поток должен перейти из пользовательского режима в режим ядра. А такой переход обходится очень дорого — в тысячи процессорных тактов на платформе x86. К этому нужно прибавить еще и время, которое необходимо на выполнение кода этих функций в режиме ядра. Объект ядра “процесс” пребывает в занятом состоянии, пока выполняется сопоставленный с ним процесс, и переходит в свободное состояние, когда процесс завершается. Внутри этого объекта поддерживается булева переменная, которая при создании объекта инициализируется как FALSE (“занято”). По окончании работы процесса операционная система меняет значение этой переменной на TRUE, сообщая тем самым, что объект свободен.
Следующие объекты ядра бывают в свободном или занятом состоянии:

  • процессы
  • потоки
  • задания
  • файлы
  • консольный ввод
  • уведомления об изменении файлов
  • события
  • ожидаемые таймеры
  • семафоры
  • мьютексыт

Потоки могут засыпать и в таком состоянии ждать освобождения какого-либо объекта. Правила, по которым объект переходит в свободное или занятое состояние, зависят от типа этого объекта.

BROTHERS


Похожие статьи.

Понравилась статья? Поделиться с друзьями: