Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 57
Текст из файла (страница 57)
К этим аппаратным возможностям относятся: блокировка памяти, специальные команды типа«проверка и установка» и механизмы управления системой прерываний, которыепозволяют организовать такие средства, как семафорные операции, мониторы, почтовые ящики и др. С помощью перечисленных средств можно разрабатывать взаимодействующие процессы, при исполнении которых будут корректно решатьсявсе задачи, связанные с проблемой критических секций. Рассмотрим эти средствав следующем порядке по мере их усложнения, перехода к функциям операционной системы и увеличения предоставляемых ими удобств, опираясь на уже древнюю, но все же еще достаточно актуальную работу Дейкстры [10].
Заметим, чтоэтот материал позволяет в полной мере осознать проблемы, возникающие при организации параллельных взаимодействующих вычислений. Эта работа Дейкстры полезна, прежде всего, с методической точки зрения, поскольку она позволяет понять наиболее тонкие моменты в этой проблематике.Использование блокировки памятипри синхронизации параллельных процессовВсе вычислительные машины и системы (в том числе и с многопортовыми блоками оперативной памяти) имеют средство для организации взаимного исключения,называемое блокировкой памяти. Блокировка памяти запрещает одновременноеисполнение двух (и более) команд, которые обращаются к одной и той же ячейкепамяти. Блокировка памяти имеет место всегда, то есть это обязательное условиеФункционирования компьютера. Соответственно, поскольку в некоторой ячейкепамяти хранится значение разделяемой переменной, то получить доступ к нейМожет только один процесс, несмотря на возможное совмещение выполнения коМанд во времени на различных процессорах (или на одном процессоре, но с конВеиерной организацией параллельного выполнения команд)."Механизм блокировки памяти предотвращает одновременный доступ к разделяемой переменной, но не предотвращает чередование доступа.
Таким образом, есликРитические секции исчерпываются одной командой обращения к памяти, данноеРеДство может быть достаточным для непосредственной реализации взаимногосключенпя. Если же критические секции требуют более одного обращения к паЧти, то задача становится сложной, но алгоритмически разрешимой. Рассмотрим216Глава 7. Организация параллельных взаимодействующих вычисляйразличные попытки использования механизма блокировки памяти для организции взаимного исключения при выполнении критических секций и покажем нкоторые важные моменты, пренебрежение которыми приводит к неприемлемьаили даже к ошибочным решениям.Возможные проблемы при организациивзаимного исключения при условиииспользования только блокировки памятиПусть имеется два или более циклических процессов с абстрактными критическими секциями, то есть каждый процесс состоит из двух частей: некоторой критической секции и оставшейся части кода, которая не работает с общими (критическими)переменными.
Пусть эти два процесса асинхронно разделяют во времени единственный процессор либо выполняются на отдельных процессорах, то есть каждый изних имеет доступ к некоторой общей области памяти, с которой и работают критические секции. Проиллюстрируем эту ситуацию с помощью рис. 7.3.>'VCS1CS2(Критическая секцияпроцесса 1)(Критическая секцияпроцесса 2)PR1PR2(Оставшаяся частьпроцесса 1)(Оставшаяся частьпроцесса 2)Рис. 7.3. Модель взаимодействующих процессоввЗадача вроде бы легко решается, если потребовать, чтобы процессы ПР1 и ПР/дили в свои критические секции попеременно.
Для этого одна общая перемени'может хранить указатель на тот процесс, чья очередь войти в критическую секШТекст этого решения на языке, близком к Паскалю, приведен в листинге 7.1.Листинг 7 . 1 . Текст программы для первого решенияVar перекл : integer;Begin перекл := 1; {при перекл=1 в критической секции находится процесс ПР1}ParbeginйДСт в а синхронизации и связи взаимодействующих процессов217While true doBeginwhile перекл = 2 do begin end:CS1; { критическая секция процесса ПР1 }перекл := 2:PR1: { оставшаяся часть процесса ПР1 }EndAndWhile true doBeginwhile перекл = 1 do begin end:CS2; { критическая секция процесса ПР2 }перекл := 1:PR2; { оставшаяся часть процесса ПР2 }EndParendEnd.Здесь и далее языковая конструкция следующего типа означает параллельностьвыполнения К описываемых последовательных процессов:p a r b e g 1 n .
. . S l l ; S12: . . . : S1N1a n d . . . S21: S22: . . . : S2N2a n d . . . SKI: SK2: . . . : SKNlkparendКонструкция из операторов Sll; S12; ...; S1N1 выполняется последовательно (оператор за оператором), о чем свидетельствует наличие точки с запятой между ними.Следующая языковая конструкция означает, что каждый процесс может выполняться неопределенно долгое время фактически бесконечное количество раз:while t r u e dobegin S I : S2: SN endНаконец, конструкция типа begin end означает просто «пустой» оператор.Итак, решение, представленное в листинге 7.1, обеспечивает нам взаимное исключение в работе критических секций.
Однако если бы фрагмент программыPR1 был намного длиннее, чем фрагмент PR2, или если бы процесс ПР1 был заблокирован в секции PR1, или если бы процессор для ПР2 обладал более высоким быстродействием, то процесс ПР2 вскоре вынужден был бы ждать входав свою критическую секцию CS2, хотя процесс ПР1 и был бы вне CS1. Такое ожидание могло бы оказаться слишком долгим, то есть для этого решения один процесс вне своей критической секции может помешать другому войти в свою критическую секцию.топробуем устранить это блокирование с помощью двух общих переменных, корые будут использоваться как флаги, указывая, находится или нет соответствуши процесс в своей критической секции. То есть с каждым из процессов ПР1 ибудет связана переменная, которая принимает значение true, когда процессродится в своей критической секции, и false — в противном случае.
Прежде чем11в свою критическую секцию, процесс проверит значение флага другого проЭли э т о'значение равно true, процессу не разрешается входить в свою крив у ю секцию. В противном случае процесс установит собственный флаг и вой-218Глава 7, Организация параллельных взаимодействующих вычислены*дет в критическую секцию. Этот алгоритм взаимного исключения представлен влистинге 7.2.Листинг 7.2. Второй вариант реализации взаимного исключенияVar перекл1.перекл2.: boolean:begin nepemil:=false;перекл2:-false;parbeginwhile true dobeginwhile перекл2 dobeginend;nepeKJil:=true:CS1 { критическая секция процесса ПР1 }перекл1:-false:PR1 { процесс ПР1 после критической секции }endandwhile true dobeginwhile перекл! dobeginend:перекл2:Чгие:CS2 { Критическая секция процесса ПР2 }nepei<r2:=false;PR2 { процесс ПР2 после критической секции }endpa rendend.Данный алгоритм, увы, не гарантирует полного выполнения условия нахождениятолько одного процесса внутри критической секции.
Отсутствие гарантий связанос различными, в общем случае, скоростями развития процессов. Поэтому, например, между проверкой значения переменной перекл2 процессом ПР1 и последующей установкой им значения переменной перекл1 параллельно выполняющийсяпроцесс ПР2 может установить перекл2 в значение true, так как переменная перекл! еще не успела установиться в значение true. Отсюда следует, что оба процесса могут войти в свои критические секции одновременно.Следующий (третий) вариант решения этой задачи (листинг 7.3) усиливает взаимное исключение, так как в процессе ПР1 проверка значения переменной перекл^выполняется только после установки переменной перекл1 в значение true (аналогично для ПР2).Листинг 7.3. Третий вариант реализации взаимного исключенияvar перекл1, перекл2 : boolean;begin перекл!:=false; nepeKn2:=false; ,parbeginПР1: while true dobeginперекл!:=true:грндства синхронизации и связи взаимодействующих процессов219while перекл2 dobegin end;CS1 { критическая секция процесса ПР1 }перекл1:-false:PR1 { ПР1 после критической секции }endandПР2: while true dobeginnepewi2:=true;while перекл1 dobegin end;CS2 { критическая секция процесса ПР2 }перекл2:-false;PR2 { ПР2 после критической секции }endpa rendend.Алгоритм, приведенный в листинге 7.3, также имеет свои недостатки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
