ОРГАНИЗАЦИЯ КОНКУРЕНЦИИ МЕЖДУ ПРОЦЕССАМИ.docx

ОРГАНИЗАЦИЯ КОНКУРЕНЦИИ МЕЖДУ ПРОЦЕССАМИ*

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

Семафоры. Представим себе операционную систему с разделением времени, управляющую работой машины с одним

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

Чтобы управлять доступом к принтеру, операционная система должна следить, занят ли принтер в данный момент или нет. Одним из возможных решений может быть использование флажка, который в данном контексте будет представлять со- бой бит памяти, состояние которого будет означать занят или свободен, а не просто 1 или 0. Если значение флажка "свобо- ден", то это означает, что принтер доступен, а если "занят", это указывает на то, что принтер уже предоставлен некоторому процессу. На первый взгляд использование такого подхода не должно вызывать каких-либо непредвиденных проблем. Опе- рационная система просто проверяет состояние флажка при каждом поступлении запроса на предоставление доступа к прин- теру. Если флажок находится в состоянии "свободен", то запрос удовлетворяется и операционная система изменяет значение флажка на "занят". Если текущее значение флажка "занят", то операционная система переводит процесс, направивший за- прос, в состояние ожидания. Каждый раз, когда очередной процесс заканчивает работу с принтером, операционная система или предоставляет принтер ожидающему процессу, или, если ожидающих процессов нет, просто изменяет значение флажка на "свободен".

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

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

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

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

Реализованный таким образом флажок называется семафором (semaphore). Это напоминает железнодорожное сигналь- ное устройство, используемое для управления доступом к определенному участку пути. Фактически в системах программно- го обеспечения семафоры используются почти так же, как и на железнодорожных линиях. Участку пути, на котором может находиться только один состав, соответствует последовательность команд, которая может выполняться одновременно толь- ко одним процессом. Такая последовательность команд называется критической областью (critical region). Требование о том, что в любой заданный момент только один процесс может выполнять команды критической области, называют взаим- ным исключением (mutual exclusion). Типичным способом реализации взаимного исключения для некоторой критической области является защита этой области с помощью семафора. Чтобы войти в критическую область, процесс должен удостове- риться, что семафор открыт, и затем изменить его значение на "закрыт" еще до того, как войдет в критическую область. При выходе из критической области процесс должен вновь открыть семафор.

Взаимная блокировка. Другой проблемой, которая может иметь место при распределении ресурсов, является взаимная блокировка (deadlock). Это состояние, при котором дальнейшая работа двух или нескольких процессов взаимно заблокиро- вана, так как каждый из них ожидает доступа к ресурсам, которые уже предоставлены другому. Например, один процесс мо- жет иметь доступ к принтеру, но ожидать доступа к накопителю на магнитных лентах, в то время как другой уже получил доступ к накопителю на магнитных лентах, но ожидает освобождения принтера. Другим примером является ситуация, когда процессы создают новые процессы, предназначенные для выполнения подзадач. Если у планировщика уже нет свободного места в таблице процессов, а каждому из процессов в системе для завершения своей задачи необходимо создать дополнитель- ный процесс, то ни один из процессов не сможет продолжить свою работу. Эта и подобные ситуации (рис. 3.9) могут серьезно нарушить работу системы.

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

1.  В системе имеет место конкуренция за использование неразделяемых ресурсов.

2.  Ресурсы запрашиваются частями – процесс, уже получив некоторые ресурсы, продолжает запрашивать другие.

3.  Предоставленный ресурс не может быть отобран принудительно.

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

Рис. 3.9. Взаимная блокировка, возникшая в результате конкуренции за использование неразделяемых пересечений железнодорожных путей

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

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

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

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

Вопросы для самопроверки

1.  Предположим, что процессы А и В функционируют в системе с разделением времени и что каждый из них нуждается в одном и том же неделимом ресурсе на короткий период времени. (Например, каждый процесс может печатать ряд незави- симых коротких сообщений.) В этой ситуации каждый процесс может многократно запрашивать доступ к ресурсу, освобож- дать его, а затем вновь запрашивать доступ. Какой недостаток существует в схеме контроля доступа к этому ресурсу, по- строенной по приведенному ниже принципу? Исходно флажку присваивается значение 0. Если процесс А запрашивает ре- сурс и значение флажка равно 0, следует удовлетворить этот запрос. В противном случае необходимо перевести процесс А в состояние ожидания. Если процесс В запрашивает ресурс и флажок имеет значение 1, следует удовлетворить этот запрос. В противном случае необходимо перевести процесс В в состояние ожидания. Каждый раз, когда процесс А заканчивает работу с ресурсом, значение флажка следует изменить на 1. Каждый раз, когда процесс В заканчивает работу с ресурсом, следует изменить значение флажка на 0.

2.  Предположим, что дорога имеет двустороннее движение, которое переходит в одностороннее при прохождении через туннель. Для координации использования туннеля была применена следующая система сигналов. Когда машина въезжает в туннель с любого его конца, над обоими входами загорается красный свет. Когда автомобиль выезжает, свет гаснет. Если при подъезде машины красный свет включен, она ожидает, пока он не будет выключен, и только после этого въезжает в тун- нель. Какой недостаток в этой системе?

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

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

4.   Предположим, что каждый процесс в системе с разделением времени будет представлен точкой; дополнительно ри- суется стрелка от одной точки к другой, если процесс, представленный первой точкой, ожидает освобождения ресурса, кото- рый используется вторым процессом. Математики называют этот чертеж ориентированным графом. Какая особенность в структуре ориентированного графа будет указывать на наличие в системе ситуации взаимной блокировки?