Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 56
Текст из файла (страница 56)
Основной причиной возникновен ^этих ошибок является то, что процессы в мультипрограммных операционных стемах развиваются с различными скоростями и относительные скорости развитиякаждого из взаимодействующих процессов не подвластны и не известны ни одному из них. Более того, на их скорости могут влиять решения планировщиков, касающиеся других процессов, с которыми ни одна из этих программ не взаимодействует. Кроме того, содержание и скорость исполнения одного из них обычно неизвестны другому процессу. Поэтому влияние, которое оказывают друг на другавзаимодействующие процессы, не всегда предсказуемо и воспроизводимо.Взаимодействовать могут либо конкурирующие процессы, либо процессы, обрабатывающие информацию совместно.
Конкурирующие процессы действуют относительно независимо друг от друга, однако они имеют доступ к некоторым общимпеременным. Их независимость заключается в том, что они могут работать другбез друга, поодиночке. Но при своем выполнении они могут работать и параллельно, и тогда они иногда начинают конкурировать при обращении к этим общим переменным.
Таким образом, их независимость относительна.Приведем несколько наиболее известных примеров конкурирующих процессов ипродемонстрируем появление ошибок. В качестве первого примера рассмотримработу двух процессов Р1 и Р2 с общей переменной X. Пусть оба процесса асинхронно, независимо один от другого, изменяют (например, увеличивают) значение переменной X, считывая ее значение в локальную область памяти Ri1, при этомкаждый процесс выполняет во времени некоторые последовательности операций(табл. 7.1). Здесь мы рассмотрим не все операторы каждого из процессов, а толькоте, в которых осуществляется работа с общей переменной X. Каждому из операторов мы присвоили некоторый условный номер.Таблица 7 . 1 .
Пример конкурирующих процессовНомер оператораПроцесс Р1Номер оператораПроцесс Р21R1 :=Х4R2:=X2R1 :=R1 + 15R2:=R2 + 13X:=R16X:=R2Поскольку при мультипрограммировании процессы могут иметь различные скорости исполнения, то может иметь место любая последовательность выполненияопераций во времени. Например, если сначала будут выполнены все операции процесса Р1, а уже потом — все операции процесса Р2 (рис. 7.1) или, наоборот, сначала — операции 4-6, а затем — операции 1-3, то в итоге переменная X получит значение, равное X + 2.Р1: (1) R1:=X; (2) R1:=R1+1; (3) X:=R1;Р2:(4) R2:=X; (5) R2:=R2+1; (6)X:=R2;,•ВремяРис.
7 . 1 . Первый вариант развития событий при выполнении процессовэто просто имя переменной для процесса с номером i.Глава 7. Организация параллельных взаимодействующих вычислений212Однако если в промежуток времени между выполнением операций 1 и 3 буд е твыполнена хотя бы одна из операций 4-6 (рис. 7.2), то значение переменной X после выполнения всех операций будет не (X + 2),а(Х + 1).P1:(1)R1:=X;Р2:(4)R2:=X;(2)R1:=R1+1;(3)X:=R1;(5)R2:=R2+1;(6)X:=R2;•ВремяРис. 7.2. Второй вариант развития событий при выполнении процессовПонятно, что это очень серьезная ошибка. Например, если бы процессы Р1 и Р2осуществляли продажу билетов и переменная X фиксировала количество уже проданных, то в результате некорректного взаимодействия было бы продано несколько билетов на одно и то же место.
К сожалению, такого рода ошибки трудноуловимы, поскольку они иногда возникают, иногда нет.В качестве второго примера рассмотрим ситуацию, которая еще совсем недавнобыла достаточно актуальной для первых персональных компьютеров. Пусть наперсональном компьютере с простейшей однопрограммной операционной системой (типа MS DOS) установлена некоторая резидентная программа с условнымназванием TIME, которая по нажатию комбинации клавиш (например, Ctrl+T) воспроизводит на экране дисплея время в виде 18:20:59, и допустим, что значенияпеременных, обозначающих час, минуты и секунды, равны 18,20 и 59 соответственно, причем вывод на дисплей осуществляется справа налево (сначала секунды, затем минуты и, наконец, часы).
Пусть сразу же после передачи программой TIMEна дисплей информации «59 секунд» генерируется прерывание от таймера, и значение времени обновляется: 18:21:00.После этого программа TIME, прерванная таймером, продолжит свое выполнение, и на дисплей будут выданы значения: минуты (21), часы (18). В итоге на экране мы увидим: 18:21:59.Рассмотрим теперь несколько иной случай развития событий обновления значений времени по сигналу таймера. Если программа ведения системных часов послевычислений количества секунд 59 + 1 = 60 и замены его на 00 прерывается от нажатия клавиш Ctrl+T, то есть программа не успевает осуществить пересчет количества минут, то время, индицируемое на дисплее, станет равным 18:20:00. И в этомслучае мы получим неверное значение времени.Наконец, в качестве третьего примера приведем пару процессов, которые изменяют различные поля записей служащих какого-либо предприятия [17].
Пусть процесс АДРЕС изменяет домашний адрес служащего, а процесс СТАТУС — его должность и зарплату. Пусть каждый процесс для выполнения своей функции копиру^всю запись СЛУЖАЩИЙ в свою рабочую область. Предположим, что каждыйпроцесс должен обработать некоторую запись ИВАНОВ. Предположим также, чтопосле того как процесс АДРЕС скопировал запись ИВАНОВ в свою рабочую область, но до того как он записал скорректированную запись обратно, процесс СТУС скопировал первоначальную запись ИВАНОВ в свою рабочую область.цазависимые и взаимодействующие вычислительные процессы213Изменения, выполненные тем из процессов, который первым запишет скорректированную запись назад в файл СЛУЖАЩИЕ, будут утеряны, и, возможно, никто0 б этом не узнает.Чтобы предотвратить некорректное исполнение конкурирующих процессов вследствие нерегламентированного доступа к разделяемым переменным, необходимоввести понятие взаимного исключения, согласно которому два процесса не должныодновременно обращаться к разделяемым переменным.Процессы, выполняющие общую совместную работу таким образом, что результаты вычислений одного процесса в явном виде передаются другому, то есть ониобмениваются данными и именно на этом построена их работа, называются сотрудничающими.
Взаимодействие сотрудничающих процессов удобнее всего рассматривать в схеме производитель-потребитель (produces-consumer), или, как часто говорят, поставщик-потребитель.Кроме реализации в операционной системе средств, организующих взаимное исключение и, тем самым, регулирующих доступ процессов к критическим ресурсам, в ней должны быть предусмотрены средства, синхронизирующие работу взаимодействующих процессов.
Другими словами, процессы должны обращаться другк другу не только ради синхронизации с целью взаимного исключения при обращении к критическим ресурсам, но и ради обмена данными.Допустим, что «поставщик» — это процесс, который отправляет порции информации (сообщения) другому процессу, имя которого — «потребитель». Например,некоторая задача пользователя, порождающая данные для вывода их на печать,может выступать как поставщик, а системный процесс, который выводит эти строки на устройство печати, — как потребитель. Один из методов, применяемых припередаче сообщений, состоит в том, что заводится пул (pool) 1 свободных буферов,каждый из которых может содержать одно сообщение. Заметим, что длина сообщения может быть произвольной, но ограниченной размером буфера.В этом случае между процессами «поставщик» и «потребитель» будем иметь очередь заполненных буферов, содержащих сообщения.
Когда поставщик хочет послать очередное сообщение, он добавляет в конец этой очереди еще один буфер.Потребитель, чтобы получить сообщение, забирает из очереди буфер, который стоитвее начале. Такое решение, хотя и кажется тривиальным, требует, чтобы поставщик и потребитель синхронизировали свои действия. Например, они должны следить за количеством свободных и заполненных буферов. Поставщик может передавать сообщения только до тех пор, пока имеются свободные буферы.
Аналогично,потребитель может получать сообщения, только если очередь не пуста. Ясно, чтоДля учета заполненных и свободных буферов нужны разделяемые переменные,поэтому, так же как и для конкурирующих процессов, для сотрудничающих процессов тоже возникает необходимость во взаимном исключении.аки м образом, до окончания обращения одной задачи к общим переменным слеУет исключить возможность обращения к ним другой задачи. Эта ситуация и на°вокупность однородных динамически распределяемых объектов, например блоков памяти одинаковой длины.214Глава 7.
Организация параллельных взаимодействующих вычисленийзывается взаимным исключением. Другими словами, при организации различного рода взаимодействующих процессов приходится организовывать взаимное исключение и решать проблему корректного доступа к общим переменным (критическим ресурсам). Те места в программах, в которых происходит обращениекритическим ресурсам, называются критическими секциями (Critical Section, CS)Решение проблемы заключается в организации такого доступа к критическомуресурсу, при котором только одному процессу разрешается входить в критическую секцию.
Данная задача только на первый взгляд кажется простой, ибо критическая секция, вообще говоря, не является последовательностью операторов программы, а является процессом, то есть последовательностью действий, которыевыполняются этими операторами. Другими словами, несколько процессов могутвыполнять критические секции, использующие одну и ту же последовательностьоператоров программы.Когда какой-либо процесс находится в своей критической секции, другие процессы могут, конечно, продолжать свое исполнение, но без входа в их критическиесекции.
Взаимное исключение необходимо только в том случае, когда процессыобращаются к разделяемым (общим) данным. Если же они выполняют операции,которые не ведут к конфликтным ситуациям, процессы должны иметь возможность работать параллельно. Когда процесс выходит из своей критической секции,то одному из остальных процессов, ожидающих входа в свои критические секции,должно быть разрешено продолжить работу (если в этот момент действительноесть процесс в состоянии ожидания входа в свою критическую секцию).Обеспечение взаимного исключения является одной из ключевых проблем параллельного программирования. При этом можно перечислить требования к критическим секциям [17, 54].Q В любой момент времени только один процесс должен находиться в своей критической секции.•Ни один процесс не должен бесконечно долго находиться в своей критическойсекции.•Ни один процесс не должен бесконечно долго ожидать разрешение на вход всвою критическую секцию. В частности:••никакой процесс, бесконечно долго находящийся вне своей критическойсекции (что допустимо), не должен задерживать выполнение других процессов, ожидающих входа в свои критические секции (другими словами,процесс, работающий вне своей критической секции, не должен блокировать критическую секцию другого процесса);если два процесса хотят войти в свои критические секции, то принятие ршения о том, кто первым войдет в критическую секцию, не должно обесконечно долгим.Q Если процесс, находящийся в своей критической секции, завершается естеств ^ным или аварийным путем, то режим взаимного исключения должен быть ^менен, с тем чтобы другие процессы получили возможность входить в свои Щтические секции.Иьедства синхронизации и связи взаимодействующих процессов215было предложено несколько способов решения этой проблемы: программных ия паратных; локальных низкоуровневых и глобальных высокоуровневых; предусматривающих свободное взаимодействие между процессами и требующих строгоV- то соблюдения протоколов.Средства синхронизациии связи взаимодействующихвычислительных процессовgee известные средства решения проблемы взаимного исключения основаны наиспользовании специально введенных аппаратных возможностей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
