Билеты (Graur) (1114774), страница 15
Текст из файла (страница 15)
Кроме того, процессы могут выполняться в разных узлах сети. Этиобстоятельства влияют на способ их взаимодействия, а именно – на возможностьсовместно использовать ресурсы, обмениваться информацией, оповещать другдруга о наступлении некоторых событий, а также определяют возможность одногопроцесса влиять на выполнение другого.Таким образом, необходимо уметь решать две важнейшие задачи:1. Распределение ресурсов между процессами.2. Организация защиты ресурсов, выделенных определенному процессу,от неконтролируемого доступа со стороны других процессов.Важнейшим требованием мультипрограммирования с точки зренияраспределения ресурсов является следующее: результат выполнения процессов недолжен зависеть от порядка переключения выполнения между процессами, т.е.
отсоотношения скорости выполнения данного процесса со скоростями выполнениядругих процессов.В качестве примера ситуации, когда это правило нарушается, рассмотримследующую. Пусть имеется некоторая простая функция, которая считываетсимвол, введенный с клавиатуры, и выводит его на экран:void echo(){char in;input(in);output(in);}В данном примере мы используем некоторые условные функции input() иoutput(), так как в данный момент для нас неважно, какконкретно реализован ввод/вывод в данной системе.
Посколькутакой кусок кода будет использоваться практически в любойпрограмме, его удобно сделать разделяемым, когда ОСзагружает в некоторую область памяти, доступную всемпроцессам, одну-единственную копию данной программы, и всепроцессы используют эту копию совместно. Заметим, что вэтом случае переменная in является разделяемой. Представимтеперь ситуацию, изображенную на Рис. 4:XYПроцесс Аinput(in);Процесс ВYinput(in);output(in);output(in);YРис. 4 Конкуренция процессов за ресурс.1. Процесс А вызывает функцию echo(), однако в тот момент, когдавходной символ был считан в переменную in, но до того, как онбыл выведен на экран, выполнение процесса прерывается и навыполнение загружается процесс В.2. Процесс В тоже вызывает функцию echo().
После выполненияфункции echo() переменная in содержит уж новое значение,считанное с клавиатуры.3. Процесс А возобновляет свою работу в той точке, в которой он былпрерван, и выводит на экран символ, находящийся в переменнойin.В рассмотренном случае символ, считанный процессом А, был потерян, а символ,считанный процессом В, был выведен дважды. Результат выполнения процессовздесь зависит от того, в какой момент осуществляется переключение процессов, иот того, какой конкретно процесс будет выбран для выполнения следующим.Такие ситуации называются гонками (в англоязычной литературе - raceconditions) между процессами, а процессы – конкурирующими. Единственныйспособ избежать гонок при использовании разделяемых ресурсов – контролироватьдоступ к любым разделяемым ресурсам в системе.
При этом необходимоорганизовать взаимное исключение – т.е. такой способ работы с разделяемымресурсом, при котором постулируется, что в тот момент, когда один из процессовработает с разделяемым ресурсом, все остальные процессы не могут иметь к немудоступ.Проблему организации взаимного исключения можно сформулировать в болееобщем виде. Часть программы (фактически набор операций), в которойосуществляется работа с критическим ресурсом, называется критическойсекцией, или критическим интервалом. Задача взаимного исключения в этомслучае сводится к тому, чтобы не допускать ситуации, когда два процессаодновременно находятся в критических секциях, связанных с одним и тем жересурсом.Заметим, что вопрос организации взаимного исключения актуален не толькодля взаимосвязанных процессов, совместно использующих определенные ресурсыдля обмена информацией. Выше отмечалось, что возможна ситуация, когдапроцессы, не подозревающие о существовании друг друга, используют глобальныересурсы системы, такие как, например, устройства ввода/вывода.
В с этом случаеимеет место конкуренция за ресурсы, доступ к которым также должен бытьорганизован по принципу взаимного исключения.Важно отметить, что при организации взаимного исключения могутвозникнуть две неприятные проблемы:1. Возникновение так называемых тупиков (deadlocks). Рассмотримследующую ситуацию (см. Рис.
5): имеются процессы А и В, каждомуиз которых в некоторый момент требуется иметь доступ к двумресурсам R1 и R2. Процесс А получил доступ к ресурсу R1, иследовательно, никакой другой процесс не может иметь к немудоступ, пока процесс А не закончит с ним работать. Одновременнопроцесс В завладел ресурсом R2. В этой ситуации каждый изпроцессов ожидает освобождения недостающего ресурса, но обаресурса никогда не будут освобождены, и процессы никогда не смогутвыполнить необходимые действия.Процесс АПроцесс ВR1R2Рис.
5 Возникновение тупиковой ситуации.2. Ситуация блокирования (дискриминации) одного из процессов, когдаодин из процессов будет бесконечно находиться в ожидании доступа кразделяемому ресурсу, в то время как каждый раз при егоосвобождении доступ к нему получает какой-то другой процесс.Таким образом, любые средства организации взаимного исключения должныобеспечивать разрешение этих двух проблем. Помимо этого, к организациивзаимного исключения выдвигаются следующие требования:1. Не должно возникать ситуации, при которой процесс, находящийсявне своей критической секции, блокирует исполнение другогопроцесса.2. Не должно делаться никаких предположений относительно взаимныхскоростей исполнения процессов, а также относительно количества искоростей работы процессоров в системе.Далее мы рассмотрим различные механизмы организации взаимного исключениядля синхронизации доступа к разделяемым ресурсам и обсудим достоинства,недостатки и области применения этих подходов.БИЛЕТ 26 Некоторые способы реализации взаимногоисключения: семафоры Дейкстры, мониторы, обменсообщениями.Семафоры.Первый из таких подходов был предложен Дейкстрой в 1965 г.
Дейкстрапредложил новый тип данных, именуемый семафором. Семафор представляетсобой переменную целого типа, над которой определены две операции: down(P) иup(V). Операция down проверяет значение семафора, и если оно больше нуля, тоуменьшает его на 1. Если же это не так, процесс блокируется, причем операцияdown считается незавершенной. Важно отметить, что вся операция являетсянеделимой, т.е. проверка значения, его уменьшение и, возможно, блокированиепроцесса производятся как одно атомарное действие, которое не может бытьпрервано. Операция up увеличивает значение семафора на 1. При этом, если всистеме присутствуют процессы, блокированные ранее при выполнении down наэтом семафоре, ОС разблокирует один из них с тем, чтобы он завершилвыполнение операции down, т.е.
вновь уменьшил значение семафора. При этомтакже постулируется, что увеличение значения семафора и, возможно,разблокирование одного из процессов и уменьшение значения являются атомарнойнеделимой операцией.Чтобы прояснить смысл использования семафоров для синхронизации, можнопривести простую аналогию из повседневной жизни. Представим себесупермаркет, посетители которого, прежде чем войти в торговый зал, должныобязательно взять себе инвентарную тележку.
В момент открытия магазина навходе имеется N свободных тележек – это начальное значение семафора. Каждыйпосетитель забирает одну из тележек (уменьшая тем самым количество оставшихсяна 1) и проходит в торговый зал – это аналог операции down. При выходепосетитель возвращает тележку на место, увеличивая количество тележек на 1 –это аналог операции up. Теперь представим себе, что очередной посетительобнаруживает, что свободных тележек нет – он вынужден блокироваться на входев ожидании появления тележки. Когда один из посетителей, находящихся вторговом зале, покидает его, посетитель, ожидающий тележку, разблокируется,забирает тележку и проходит в зал. Таким образом, наш семафор в виде тележекпозволяет находиться в торговом зале (аналоге критической секции) не более чемN посетителям одновременно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
