Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 62
Текст из файла (страница 62)
Перед записью порции новых данных процесс «писатель» увеличивает на 1 значение переменной VI, а после записи — переменной V2. Читательобращается к V2 перед чтением данных, а к VI — после. Если при этом переменныеVI и V2 равны, то очевидно, что получена правильная версия данных. Если же данные обновлялись за время чтения, то операция повторяется.
Этот алгоритм можетбыть использован в случае, если нежелательно заставлять процесс «писатель»ждать, пока читатели закончат операцию чтения, или если вероятность повторения операции чтения достаточно мала и обусловленное повторными операциямиснижение эффективности системы меньше потерь, связанных с избыточностьюрешения с помощью взаимного исключения.
Однако необходимо иметь в виду ненулевую вероятность зацикливания чтения при высокой интенсивности операциизаписи. Наконец, если само чтение представляет собой достаточно длительнуюоперацию, то оператор V := V2 для процесса «читатель» может быть заменен следующим оператором:Repeat V := V2 Until VI = VЭто предотвратит выполнение читателем операции чтения, если писатель уже начал запись.Мониторы ХоараАнализ рассмотренных задач показывает, что, несмотря на очевидные достоинст(простота, независимость от количества процессов, отсутствие активного ожйДния), семафорные механизмы имеют и ряд недостатков. Эти механизмы являютслишком примитивными, так как семафор не указывает непосредственно на син(^тниторы Хоара*±Lонизирующее условие, с которым он связан, или на критический ресурс.
Поэтому при построении сложных схем синхронизации алгоритмы решения задач пооой получаются весьма непростыми, ненаглядными и трудными для доказательства их правильности.Необходимо иметь очевидные решения, которые позволят прикладным программистам без лишних усилий, связанных с доказательством правильности алгоритмов и отслеживанием большого числа взаимосвязанных объектов, создавать параллельные взаимодействующие программы.
К таким решениям можно отнеститак называемые мониторы, предложенные Хоаром [52].В параллельном программировании монитор — это пассивный набор разделяемыхпеременных и повторно входимых процедур доступа к ним, которым процессыпользуются в режиме разделения, причем в каждый момент им может пользоваться только один процесс.Рассмотрим, например, некоторый ресурс, который разделяется между процессами каким-либо планировщиком [17]. Каждый раз, когда процесс желает получитьв свое распоряжение какие-то ресурсы, он должен обратиться к программе-планировщику.
Этот планировщик должен иметь переменные, с помощью которых можноотслеживать, занят ресурс или свободен. Процедуру планировщика разделяют всепроцессы, и каждый процесс может в любой момент захотеть обратиться к планировщику. Но планировщик не в состоянии обслуживать более одного процессаодновременно. Такая процедура-планировщик и представляет собой пример монитора.Таким образом, монитор — это механизм организации параллелизма, который содержит как данные, так и процедуры, необходимые для динамического распределения конкретного общего ресурса или группы общих ресурсов.
Процесс, желающий получить доступ к разделяемым переменным, должен обратиться к монитору,который либо предоставит доступ, либо откажет в нем. Необходимость входав монитор с обращением к какой-либо его процедуре (например, с запросом навыделение требуемого ресурса) может возникать у многих процессов. Однако входв монитор находится под жестким контролем — здесь осуществляется взаимноеисключение процессов, так что в каждый момент времени только одному процессуразрешается войти в монитор. Процессам, которые хотят войти в монитор, когдаон уже занят, приходится ждать, причем режимом ожидания автоматически управляет сам монитор.
При отказе в доступе монитор блокирует обратившийся к немупроцесс и определяет условие ожидания. Проверка условия выполняется самиммонитором, который и деблокирует ожидающий процесс. Поскольку механизммонитора гарантирует взаимное исключение процессов, исключаются серьезныепроблемы, связанные с организацией параллельных взаимодействующих процессов.нутренние данные монитора могут быть либо глобальными (относящимися копроцедурам монитора), либо локальными (относящимися только к однойонкретной процедуре). Ко всем этим данным можно обращаться только изнутри°нитора; процессы, находящиеся вне монитора и, по существу, только вызывающие его процедуры, просто не могут получить доступ к данным монитора. ПриВ с е м238Глава 7 . Организация параллельных взаимодействующих вычислениепервом обращении монитор присваивает своим переменным начальные значенияПри каждом последующем обращении используются те значения переменныхкоторые остались от предыдущего обращения.Если процесс обращаете^ к некоторой процедуре монитора, а соответствующийресурс уже занят, эта процедура выдает команду ожидания WAIT с указанием условия ожидания.
Процесс мог бы оставаться внутри монитора, однако, если в монитор затем войдет другой процесс, это будет противоречить принципу взаимногоисключения. Поэтому процесс, переводящийся в режим ожидания, должен внемонитора ждать того момента, когда необходимый ему ресурс освободится.Со временем процесс, который занимал данный ресурс, обратится к монитору, чтобы возвратить ресурс системе.
Соответствующая процедура монитора при этомможет просто принять уведомление о возвращении ресурса, а затем ждать, пока непоступит запрос от другого процесса, которому потребуется этот ресурс. Однакоможет оказаться, что уже имеются процессы, ожидающие освобождения данногоресурса. В этом случае монитор выполняет команду извещения (сигнализации)SIGNAL, чтобы один из ожидающих процессов мог получить данный ресурс и покинуть монитор. Если процесс сигнализирует о возвращении (иногда называемомосвобождением) ресурса и в это время нет процессов, ожидающих данного ресурса, то подобное оповещение не вызывает никаких других последствий, кроме того,что монитор, естественно, вновь внесет ресурс в список свободных.
Очевидно, чтопроцесс, ожидающий освобождения некоторого ресурса, должен находиться внемонитора, чтобы другой процесс имел возможность войти в монитор и возвратитьему этот ресурс.Чтобы гарантировать, что процесс, находящийся в ожидании некоторого ресурса,со временем получит этот ресурс, считается, что ожидающий процесс имеет болеевысокий приоритет, чем новый процесс, пытающийся войти в монитор. В противном случае новый процесс мог бы перехватить ожидаемый ресурс до того, как ожидающий процесс вновь войдет в монитор. Если допустить многократное повторениеподобной нежелательной ситуации, то ожидающий процесс мог бы откладыватьсябесконечно.
Для систем реального времени можно допустить использование дисциплины обслуживания на основе абсолютных или динамически изменяемых приоритетов.В качестве примера рассмотрим простейший монитор для выделения одного ресурса (листинг 7.16).Листинг 7.16. Пример монитора Хоараmonitor Resourse;condition free: { условие - свободный }var busy : boolean: { занят }procedure REQUEST: { запрос }beginif busy then WAIT ( free ):busy :=t rue:TakeOff: { выдать ресурс }end:fi/jnHMjopbi Xoapa<£.з»procedure RELEASE:beginTakeOn; { взять ресурс }busy:=fa1se;SIGNAL ( free )end;beginbusy:=false;endЕдинственный ресурс динамически запрашивается и освобождается процессами,которые обращаются к процедурам REQUEST (запрос) и RELEASE (освободить). Еслипроцесс обращается к процедуре REQUEST в тот момент, когда ресурс используется,значение переменной busy (занято) будет равно true, и процедура REQUEST выполнит операцию монитора WAIT(free).
Эта операция блокирует не процедуру REQUEST,а обратившийся к ней процесс, который помещается в конец очереди процессов,ожидающих, пока не будет выполнено условие free (свободно).Когда процесс, использующий ресурс, обращается к процедуре RELEASE, операциямонитора SIGNAL деблокирует процесс, находящийся в начале очереди, не позволяя исполняться никакой другой процедуре внутри того же монитора. Этот деблокированный процесс будет готов возобновить исполнение процедуры REQUEST сразуже после операции WAIT (free), которая его и блокировала. Если операция SIGNAL(free)выполняется в то время, когда нет процесса, ожидающего условия free, то никакихдействий не выполняется.Использование монитора в качестве основного средства синхронизации и связиосвобождает процессы от необходимости явно разделять между собой информацию.
Напротив, доступ к разделяемым переменным всегда ограничен телом монитора, и, поскольку мониторы входят в состав ядра операционной системы, разделяемыепеременные становятся системными переменными. Это автоматически исключает необходимость в критических секциях (так как в каждый момент мониторомможет пользоваться только один процесс, то два процесса никогда не смогут получить доступ к разделяемым переменным одновременно).Монитор является пассивным объектом в том смысле, что это не процесс; его процедуры выполняются только по требованию процесса.Хотя по сравнению с семафорами мониторы не представляют собой существенноболее мощного инструмента для организации параллельных взаимодействующихвычислительных процессов, у них есть некоторые преимущества перед более примитивными синхронизирующими средствами. Во-первых, мониторы очень гибки.В форме мониторов можно реализовать не только семафоры, но и многие другиесинхронизирующие операции.
Например, разобранный в разделе «Средства синхронизации и связи взаимодействующих вычислительных процессов» механизмРешения задачи «поставщик-потребитель» легко запрограммировать в виде монитора. Во-вторых, локализация всех разделяемых переменных внутри тела монитора позволяет избавиться от малопонятных конструкций в синхронизируемыхпроцессах — сложные взаимодействия процессов можно синхронизировать наглядным образом. В-третьих, мониторы дают процессам возможность совместно не-240Глава 7. Организация параллельных взаимодействующих вычисленийпользовать программные модули, представляющие собой критические секции. Еслинесколько процессов совместно используют ресурс и работают с ним совершенноодинаково, то в мониторе достаточно только одной процедуры, тогда как решениес семафорами требует, чтобы в каждом процессе имелся собственный экземпляркритической секции. Таким образом, мониторы по сравнению с семафорами позволяют значительно упростить организацию взаимодействующих вычислительных процессов и дают большую наглядность при совсем незначительной потерев эффективности.Почтовые ящикиТесное взаимодействие между процессами предполагает не только синхронизацию — обмен временными сигналами, но также передачу и получение произвольных данных, то есть обмен сообщениями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
