Н.В. Вдовикина, И.В. Машечкин, А.Н. Терехин, А.Н. Томилин - Операционные системы - взаимодействие процессов (2008) (1114653), страница 4
Текст из файла (страница 4)
с моментапредыдущей записи в файл другой процесс мог ужедобавить свои сообщения, тем самым расширив файл);2. запись нового сообщения.Отметим, что в описанном случае файл является разделяемымресурсом.Представим теперь ситуацию, изображенную на Рис. 2:1Процесс Апозиционирование;Процесс Впозиционирование;запись;2запись;3Рис. 2 Конкуренция процессов за ресурс.1.
Процесс А осуществляет позиционирование в конецфайла, однако в тот момент, когда новая позиция вфайле уже была получена, но до того, как былаосуществлена запись в файл, выполнение процессапрерывается и на выполнение загружается процесс В.2. Процесс В осуществляет позиционирование в конецфайла. Затем он производит запись в конец файла13своего сообщения, тем самым изменив размер файлаи новое смещение его конца.3. Процесс А возобновляет свою работу в той точке, вкоторой он был прерван, и производит запись своихданных по старому смещению, тем самым затеревсообщение от процесса B.Результат выполнения процессов здесь зависит от того, вкакой момент осуществляется переключение процессов, и от того,какой конкретно процесс будетвыбран для выполненияследующим.
Такие ситуации называются гонками (в англоязычнойлитературе - race conditions) между процессами, а процессы –конкурирующими. Единственный способ избежать гонок прииспользовании разделяемых ресурсов – контролировать доступ клюбым разделяемым ресурсам в системе. При этом необходимоорганизовать взаимное исключение – т.е. такой способ работы сразделяемым ресурсом, при котором постулируется, что в тотмомент, когда один из процессов работает с разделяемым ресурсом,все остальные процессы не могут иметь к нему доступ.Проблему организации взаимного исключения можносформулировать в более общем виде. Часть программы (фактическинабор операций), в которой осуществляется работа с критическимресурсом, называется критической секцией, или критическиминтервалом. Задача взаимного исключения в этом случае сводитсяк тому, чтобы не допускать ситуации, когда два процессаодновременно находятся в критических секциях, связанных с одними тем же ресурсом.Заметим, что вопрос организации взаимного исключенияактуален не только для взаимосвязанных процессов, совместноиспользующих определенные ресурсы для обмена информацией.Выше отмечалось, что возможна ситуация, когда процессы, неподозревающие о существовании друг друга, используютглобальные ресурсы системы, такие как, например, устройстваввода/вывода.
В с этом случае имеет место конкуренция за ресурсы,доступ к которым также должен быть организован по принципувзаимного исключения.Важно отметить, что при организации взаимного исключениямогут возникнуть две неприятные проблемы:1. Возникновение так называемых тупиков (deadlocks).Тупиком можно назвать такую ситуацию, когда ни один извзаимодействующих процессов не может продолжать своюработу, т.к. ожидает совершения определенных действий14другим взаимодействующим процессом. Рассмотрим дляпримера следующую ситуацию (см. Рис. 3): имеютсяпроцессы А и В, каждому из которых в некоторый моменттребуется иметь доступ к двум ресурсам R1 и R2.
ПроцессА получил доступ к ресурсу R1, и следовательно, никакойдругой процесс не может иметь к нему доступ, покапроцесс А не закончит с ним работать. Одновременнопроцесс В завладел ресурсом R2. В этой ситуации каждыйиз процессов ожидает освобождения недостающегоресурса, но оба ресурса никогда не будут освобождены, ипроцессы никогда не смогут выполнить необходимыедействия.Процесс АПроцесс ВR1R2Рис. 3 Возникновение тупиковой ситуации.2. Ситуация блокирования (дискриминации) одного изпроцессов, когда один из процессов будет бесконечнонаходиться в ожидании доступа к разделяемому ресурсу, вто время как каждый раз при его освобождении доступ кнему получает какой-то другой процесс.Таким образом, любые средства организации взаимногоисключения должны обеспечивать разрешение этих двух проблем.Помимо этого, к организации взаимного исключения выдвигаютсяследующие требования:1.
Не должно возникать ситуации, при которой процесс,находящийся вне своей критической секции, блокируетисполнение другого процесса.2. Недолжноделатьсяникакихпредположенийотносительновзаимныхскоростейисполненияпроцессов, а также относительноколичества искоростей работы процессоров в системе.Далее мы рассмотрим различные механизмы организациивзаимного исключения для синхронизации доступа к разделяемымресурсам и обсудим достоинства, недостатки и области примененияэтих подходов.152.1 Способы реализации взаимного исключения2.1.1 Запрещение прерываний и специальные инструкцииПростейшее умозаключение, которое, на первый взгляд,решает проблему синхронизации доступа к критическим ресурсам,заключается в следующем: некорректная работа с разделяемымиресурсами возникает в том случае, если переключение процессовпроисходит в тот момент, когда выполняющийся процесс началработу с разделяемым ресурсом, но не закончил ее, т.е.
находится всвоей критической секции. Чтобы этого не происходило, процессдолжен запретить все прерывания непосредственно после входа вкритическую секцию и разрешить их перед самым выходом из нее.Если прерывания запрещены, то переключения процессов непроисходит, так как передача управления планировщику может бытьреализована только с использованием прерываний (это может бытькак прерывание по таймеру, так и другие прерывания, например, призаказе обмена). Таким образом, запрещение прерываний гарантируетпроцессу, что никакой другой процесс не обратится к разделяемомуресурсу, пока прерывания не будут разрешены.Этот подход, однако, имеет ряд существенных недостатков.Первым из них является снижение общей производительностисистемы вследствие ограничения возможности переключенияпроцессов для оптимальной загрузки процессора.
Другая проблемазаключается в том, что нет никаких гарантий, что процесс,запретивший прерывания, не зациклится в своей критическойсекции, тем самым приведя систему в полностью неработоспособноесостояние. Цена программной ошибки здесь становится слишкомвысокой. Кроме всего прочего, для многопроцессорной системызапрещение прерываний не гарантирует даже взаимногоисключения, так как запрещение прерываний на одном изпроцессоров никак не влияет на исполнение процессов на другихпроцессорах ВС, и эти процессы по-прежнему имеют доступ кразделяемому ресурсу, например, ячейке общей памяти.Дляорганизациивзаимногоисключениянамногопроцессорной системе с общей памятью могут использоватьсяспециальные машинные инструкции.
Примером такой инструкцииможет служить TSL – test and set lock, реализующая чтениеячейки памяти и запись нового значения в ту же ячейку как единуюоперацию. При этом гарантируется, что совокупность операцийчтения и записи ячейки памяти является неделимой, т.е.
доступ кячейке памяти со стороны других процессоров блокируется на всевремя исполнения инструкции. Вариацией этой идеи является16специальная инструкция exchange, которая меняет местамисодержимое регистра и ячейки памяти. Здесь опять гарантируется,что на все время выполнения инструкции доступ к ячейке памятиблокируется.Используя эти инструкции и дополнительную разделяемуюпеременную, значение которой говорит о том, можно ли в данныймомент войти в критическую секцию, процессы могутсинхронизировать свою работу. Возможность считывать староезначение и записывать новое за одну операцию позволяет избежатьситуации, когда процесс, считав значение переменной, говорящееему о том, что он может войти в свою критическую секцию, неуспеет изменить ее значение на «занято» и будет в этот моментпрерван; другой же процесс, получивший управление, считаетнеизмененное значение переменной, которое позволит и ему войти вкритическую секцию, в результате чего два процесса одновременноокажутся в критических секциях.2.1.2 Алгоритм ПетерсонаДругим подходом к решению задачи организации взаимногоисключения является изобретение различных алгоритмов,позволяющихпроцессамсинхронизироватьсвоюработупрограммно.
Одним из первых программных решений являетсяалгоритм Петерсона.Алгоритм Петерсона для случая 2х процессов представлен наРис. 4.int first_process() {for(;;) {flag[0] = 1;turn = 1;while (flag[1] && turn) {/* waiting */};/* critical section */flag[0] = 0;}}int second_process() {for(;;) {flag[1] = 1;turn = 0;while (flag[0] && (!turn)){/* waiting */};/* critical section */flag[1] = 0;}}Рис. 4 Алгоритм ПетерсонаЭлементы массива flag символизируют собой желаниесоответствующего процесса попасть в критическую секцию.17Каждый из процессов видит все элементы массива flag, номодифицирует только «свой» элемент. Переменная turnустанавливает очередность прохождения критической секции приобоюдном желании процессов вступить в нее.
Благодаря тому, чтокаждый из процессов прежде всего устанавливает флаг очередностив пользу другого процесса, исключается ситуация «монополизации»ресурса одним из процессов и вечного блокирования второго.2.1.3 Активное ожиданиеОбщим недостатком рассмотренных выше решений являетсято, что процесс, желающий получить доступ к занятому ресурсу,блокируется в состоянии так называемого активного ожидания (ванглоязычной литературе – busy waiting), т.е.
в цикле постояннопроверяет, не наступило ли условие, при котором он сможет войти вкритическую секцию. Использование активного ожидания приводитк бесполезному расходованию процессорного времени и, какследствие, снижению общей производительности системы. Крометого, при некоторых стратегиях планирования времени ЦП в целомкорректный алгоритм с активным ожиданием может привести ктупику. Примером может служить стратегия планирования сприоритетами, когда процесс, имеющий больший приоритет,загружается на выполнение и переходит в состояние активногоожидания, в то время как процесс с меньшим приоритетом захватилнеобходимый ресурс, но был выгружен до того, как освободил его.Поскольку процесс с большим приоритетом не блокирован, а готов кпродолжению выполнения, переключение процессов не происходит,и процесс, владеющий ресурсом, никогда не сможет его освободить.Далее мы рассмотрим ряд подходов, которые позволяютреализовать взаимное исключение без использования активногоожидания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
