В компьютерных системах множество ресурсов, которые одновременно могут использоваться только одним процессом. Если два процесса будут использовать один и тот же элемент таблицы файловой системы, то эта система непременно будет повреждена. Поэтому все операционные системы способны временно предоставлять процессу исключительные права доступа к конкретным ресурсам. При работе многих приложений процессу нужен исключительный доступ не к одному, а сразу к нескольким ресурсам. Предположим, к примеру, что каждый из двух процес- сов захотел записать отсканированный документ на Blu-ray-диск. Процесс A запрашивает разрешение на использование сканера и получает его. Процесс B запрограмми- рован по-другому: сначала он запрашивает разрешение на использование пишущего привода Blu-ray-дисков и также получает это разрешение. Теперь A запрашивает разре- шение на использование пишущего привода Blu-ray-дисков, но запрос отклоняется до тех пор, пока это устройство не будет освобождено процессом B. К сожалению, вместо того чтобы освободить привод, B запрашивает разрешение на использование сканера. И в этот момент оба процесса оказываются заблокированными навсегда. Такая ситуа- ция называется тупиковой ситуацией (тупиком), или взаимоблокировкой (deadlock). Взаимоблокировки могут возникать и при массе других обстоятельств. К примеру, в системах управления базами данных, во избежание попадания в состояние состяза- ния программе может понадобиться блокировка нескольких используемых ею запи- сей. Если процесс A блокирует запись R1, а процесс B блокирует запись R2, а затем каждый процесс пытается заблокировать запись другого процесса, то получается та же взаимоблокировка. Таким образом, взаимоблокировки могут появляться при работе как с аппаратными, так и с программными ресурсами. ## Ресурсы Основная часть взаимоблокировок связана с ресурсами, к которым некоторым про- цессам были предоставлены исключительные права доступа. К их числу относятся устройства, записи данных, файлы и т. д. Короче говоря, под ресурсом по- нимается все, что должно предоставляться, использоваться и через некоторое время высвобождаться, поскольку в один и тот же момент времени может использоваться только одним процессом. ### Выгружаемые и невыгружаемые ресурсы К выгружаемым отно- сятся такие ресурсы, которые могут быть безболезненно отобраны у процесса, который ими обладает. Примером такого ресурса может послужить память. Данные в памяти мы можем выгрузить на диск. А вот невыгружаемый ресурс нельзя отобрать у его текущего владельца, не вызвав потенциально сбоя в вычислениях. Как правило, во взаимоблокировках фигурируют невыгружаемые ресурсы. Обычно потенциальные взаимоблокировки с участием выгружаемых ресурсов могут быть устранены путем перераспределения ресурсов от одного процесса к другому. В наиболее общем виде при использовании ресурса происходит следующая последо- вательность событий: 1. Запрос ресурса. 2. Использование ресурса. 3. Высвобождение ресурса. Если во время запроса ресурс недоступен, запрашивающий процесс вынужден перейти к ожиданию. В некоторых операционных системах при отказе в выделении запрошенного ресурса процесс автоматически блокируется, а когда ресурс становится доступен — возобновляется. В других системах отказ в выделении запрашиваемого ресурса сопровождается кодом ошибки, и принятие решения о том, что следует делать, немного подождать или попытаться снова получить ресурс, возлагается на вызывающий процесс. Процесс, чей запрос на выделение ресурса был только что отклонен, обычно входит в короткий цикл: запрос ресурса, затем приостановка, — после чего повторяет попытку. Хотя этот процесс не заблокирован, но по всем показателям он является фактически заблокированным, поскольку не может выполнять никакой полезной работы. При дальнейшем рассмотрении вопроса мы будем предполагать, что при отказе в выделении запрошенного ресурса процесс впадает в спячку. В Linux единственными ресурсами, о которых знает операционная система, являются специальные файлы, которые в конкретный момент времени могут быть открыты только одним процессом. Они открываются с использованием обычного вызова open. Если файл уже используется, вызывающий процесс блокируется до тех пор, пока файл не будет закрыт текущим владельцем. 1. Получение ресурса Один из способов, позволяющих ввести пользовательское управление ресурсами, заключа- ется в присоединении семафора к каждому из ресурсов. Все эти семафоры получают исходное значение, равное 1. С таким же успехом могут использоваться и мьютексы. Перечисленные ранее три этапа затем воплощаются в применение к семафору вызова down для получения ресурса, использование ресурса и, в завершение, применение вызова up при высвобождении ресурса Семафоры Ситуация изменилась в 1965 году, когда Дейкстра предложил использовать целочис- ленную переменную для подсчета количества активизаций, отложенных на будущее. Он предложил учредить новый тип переменной — семафор (semaphore). Значение семафора может быть равно 0, что будет свидетельствовать об отсутствии сохраненных активизаций, или иметь какое-нибудь положительное значение, если ожидается не менее одной активизации. Дейкстра предложил использовать две операции с семафорами, которые сейчас обычно называют down и up (обобщения sleep и wakeup соответственно). Операция down выясня- ет, отличается ли значение семафора от 0. Если отличается, она уменьшает это значение на 1 (то есть использует одну сохраненную активизацию) и продолжает свою работу. Если значение равно 0, процесс приостанавливается, не завершая в этот раз операцию down. И проверка значения, и его изменение, и, возможно, приостановка процесса осу- ществляются как единое и неделимое атомарное действие. Тем самым гарантируется, что с началом семафорной операции никакой другой процесс не может получить доступ к семафору до тех пор, пока операция не будет завершена или заблокирована. Атомар- ность является абсолютно необходимым условием для решения проблем синхронизации и исключения состязательных ситуаций. Атомарные действия, в которых группа взаи- мосвязанных операций либо выполняется без каких-либо прерываний, либо вообще не выполняется, приобрели особую важность и во многих других областях информатики. Мьютексы Мьютекс — это совместно используемая переменная, которая может находиться в од- ном из двух состояний: заблокированном или незаблокированном. Следовательно, для их представления нужен только один бит, но на практике зачастую используется целое число, при этом нуль означает незаблокированное, а все остальные значения — заблокированное состояние. Для работы с мьютексами используются две процедуры. Когда потоку (или процессу) необходим доступ к критической области, он вызывает процедуру mutex_lock. Если мьютекс находится в незаблокированном состоянии (означающем доступность входа в критическую область), вызов проходит удачно и вызывающий поток может свободно войти в критическую область. В то же время, если мьютекс уже заблокирован, вызывающий поток блокируется до тех пор, пока поток, находящийся в критической области, не завершит свою работу и не вызовет процедуру mutex_unlock. Если на мьютексе заблокировано несколько потоков, то произвольно выбирается один из них, которому разрешается воспользоваться за- блокированностью других потоков. ``` typedef int semaphore; semaphore resource_1; void process_A(void) { down(&resource_1); use_resource_1( ); up(&resource_1); } ``` Пока все идет хорошо. Пока речь идет только об одном процессе, все работает нор- мально. Конечно, когда используется только один процесс, нет нужды в формальном получении ресурсов, поскольку нет соперничества за обладание ими. Взаимоблокировка в группе процессов возникает в том случае, если каждый процесс из этой группы ожидает события, наступление которого зависит исключительно от другого процесса из этой же группы. ### Условия возникновения ресурсных взаимоблокировок 1. Условие взаимного исключения. Каждый ресурс либо выделен в данный момент только одному процессу, либо доступен. 2. Условие удержания и ожидания. Процессы, удерживающие в данный момент ранее выделенные им ресурсы, могут запрашивать новые ресурсы. 3. Условие невыгружаемости. Ранее выделенные ресурсы не могут быть принуди- тельно отобраны у процесса. Они должны быть явным образом высвобождены тем процессом, который их удерживает. 4. Условие циклического ожидания. Должна существовать кольцевая последовательность из двух и более процессов, каждый из которых ожидает высвобождения ресурса, удерживаемого следующим членом последовательности. Для возникновения ресурсной взаимоблокировки должны соблюдаться все четыре условия. Если одно из них не соблюдается, ресурсная взаимоблокировка невозможна. ### Обнаружение взаимоблокировки при использовании одного ресурса каждого типа Для такой системы можно построить ресурсный граф. Если этот граф содер- жит один и более циклов, значит, мы имеем дело с взаимоблокировкой. Любой процесс, являющийся частью цикла, заблокирован намертво. Если циклов нет, значит, система не находится в состоянии взаимоблокировки. Далее будет приведен простой алгоритм, проверяющий граф и прекращающий свою работу либо при обнаружении цикла, либо при обнаружении отсутствия циклов. В нем используется одна динамическая структура данных, L, пред- ставляющая собой список узлов, а также список ребер. В процессе работы алгоритма ребра будут помечаться для обозначения того, что они уже были проверены, чтобы предотвратить повторные проверки. Действие алгоритма основано на выполнении следующих шагов: 1. Для каждого узла N, имеющегося в графе, выполняются следующие пять шагов, использующих узел N в качестве начального. 2. Инициализируется (очищается) список L, а со всех ребер снимаются пометки. 3. Текущий узел добавляется к концу списка L, и проводится проверка, не появит- ся ли этот узел в списке L дважды. Если это произойдет, значит, граф содержит цикл (отображенный в списке L), и алгоритм прекращает работу. 4. Для заданного узла определяется, нет ли каких-нибудь отходящих от него непо- меченных ребер. Если такие ребра есть, осуществляется переход к шагу 5, если их нет, осуществляется переход к шагу 6. Произвольно выбирается и помечается непомеченное отходящее от узла ребро. Затем по нему осуществляется переход к новому текущему узлу, и алгоритм воз- вращается к шагу 3. 6. Если этот узел является первоначальным узлом, значит, граф не содержит никаких циклов, и алгоритм завершает свою работу. В противном случае алгоритм зашел в тупик. Этот узел удаляется, и алгоритм возвращается к предыдущему узлу, то есть к тому узлу, который был текущим перед только что удаленным узлом. Дан- ный узел делается текущим, и осуществляется переход к шагу 3. Этот алгоритм берет поочередно каждый узел в качестве корневого в надежде, что из этого получится дерево, и выполняет в дереве поиск в глубину. Если в процессе обхода алгоритм возвращается к уже встречавшемуся узлу, значит, он нашел цикл. Если алгоритм обходит все ребра из какого-нибудь заданного узла, то он возвращается к предыдущему узлу. Если он возвращается к корневому узлу и не может идти дальше, то подграф, доступный из текущего узла, не содержит циклов. Если данное свойство сохраняется для всех узлов, значит, полный граф не содержит циклов, а система не находится в состоянии взаимоблокировки. ### Обнаружение взаимоблокировки при использовании нескольких ресурсов каждого типа Сейчас будет представлен алгоритм, основанный на использовании матриц и предназначенный для обнаружения взаимоблокировки при работе n процессов, от P1 до Pn. Пусть m — это число классов ре- сурсов, Е1 — количество ресурсов класса 1, Е2 — количество ресурсов класса 2, а в общем Ei — количество ресурсов класса i (где 1 ≤ i ≤ m). E — это вектор существующих ресурсов. Он передает общее количество имеющихся в наличии экземпляров каждого ресурса. Например, если класс 1 представляет собой накопители на магнитных лентах, то E1 = 2 означает, что в системе есть два таких накопителя. В любой момент времени какие-то ресурсы могут быть выделены и недоступны. Пусть A будет вектором доступных ресурсов, где Ai дает количество экземпляров ресурса i, доступных на данный момент (то есть не выделенных). Если оба накопителя на маг- нитной ленте уже выделены, A1 будет равно 0. Теперь нам нужны два массива: C — матрица текущего распределения и R — матрица запросов. i-я строка в матрице C говорит о том, сколько экземпляров каждого класса ресурсов в данный момент удерживает процесс Pi. Таким образом, Cij — это количество экземпляров ресурса j, которое удерживается процессом i. По аналогии с этим Rij — это количество экземпляров ресурса j, которое хочет получить процесс Pi.