Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 61
Текст из файла (страница 61)
Если пул буферов заполнится и к нему обратится процесс«поставщик», то он будет заблокирован на семафоре 5_свободно в результате выполнения операции Р(Б_свободно).о решении задачи о поставщике и потребителе общие семафоры применены дляучета свободных и заполненных буферов. Их можно также применить и для распределения иных ресурсов.Синхронизация взаимодействующих процессовспомощью семафоровожно использовать семафорные операции для решения таких задач, в которыхУ пешное завершение одного процесса связано с ожиданием завершения другого.Редположим, что существуют два процесса ПР1 и ПР2. Необходимо, чтобы просе IIP l запускал процесс ПР2 с ожиданием его выполнения, то есть ПР1 не бупродолжать свое выполнение до тех пор, пока процесс ПР2 до конца не выполсвою работу.
Программа, реализующая такое взаимодействие, представлена влистинге 7.12.232Глава 7. Организация параллельных взаимодействующих вычисленийЛистинг 7.12. Пример синхронизации процессовvar S : Semaphore;beginInitSem(S.O):ПР1: beginПРИ; { первая часть ПР1 }ON ( ПР2 ); { поставить на выполнение ПР2 }P(S);ПР12; { оставшаяся часть ПР1 }STOPend;ПР2:beginПР2; { вся работа программы ПР2 }VCS):STOPendendНачальное значение семафора S равно нулю. Если процесс ПР1 начал выполняться первым, то через некоторое время он поставит на выполнение процесс ПР2, послечего выполнит операцию P(S) и «заснет» на семафоре, перейдя в состояние пассивного ожидания.
Процесс ПР2, осуществив все необходимые действия, выполнитпримитив V(S) и откроет семафор, после чего процесс ПР1 будет готов к дальнейшему выполнению.Задача «читатели-писатели»Другой важной и часто встречающейся задачей, решение которой также требует синхронизации, является задача «читатели-писатели». Эта задача имеет много вариантов. Наиболее характерная область ее использования — построение систем управления файлами и базами данных, информационно-справочных систем. Два классапроцессов имеют доступ к некоторому ресурсу (области памяти, файлам). «Читатели» — это процессы, которые могут параллельно считывать информацию из некоторой общей области памяти, являющейся критическим ресурсом.
«Писатели» — этопроцессы, записывающие информацию в эту область памяти, исключая друг друга.а также процессы «читатели». Имеются различные варианты взаимодействия междуписателями и читателями. Наиболее широко распространены следующие условия.Устанавливается приоритет в использование критического ресурса процессам «читатели». Это означает, что если хотя бы один читатель пользуется ресурсом, то онзакрыт для всех писателей и доступен для всех читателей. Во втором варианте,наоборот, больший приоритет у процессов «писатели». При появлении запросаписателя необходимо закрыть дальнейший доступ всем тем читателям, которызапросят критический ресурс после него.Помимо системы управления файлами другим типичным примером решениядачи «читатели-писатели» может служить система автоматизированной продабилетов. Процессы «читатели» обеспечивают нас справочной информацией оличии свободных билетов на тот или иной рейс.
Процессы «писатели» запуска!гпр п р т в а с и н х р о н и з а ц и и и связи взаимодействующих процессов<сооа с пульта кассира, когда он оформляет для нас тот или иной билет. Имеется больше количество как читателей, так и писателей.Пример программы, реализующей решение данной задачи в первой постановке,дставлен в л и с т и н г е 7.13. Процессы «читатели» и «писатели» описаны в видесоответствующих процедур.Листинг 7.13. Решение задачи «читатели-писатели» с приоритетом в доступек критическому ресурсу читателейR. W : semaphore:varN_R : integer:procedure ЧИТАТЕЛЬ;beginP(R):Inc(NR):{ NR:=NR +1 }if NR = 1 then P(W):V(R):Read_0ata; { критическая секция }P(R);Dec(NR);if N_R = 0 then V(W);V(R)end;procedure ПИСАТЕЛЬ;beginP(W);Write_Data; { критическая секция }V(W)end1beginNR:=0:InitSem(S.l): InitSem(W,l);parbeginwhile true do ЧИТАТЕЛЬandwhile true do ЧИТАТЕЛЬandwhile true do ЧИТАТЕЛЬandwhile true do ПИСАТЕЛЬandwhile true do ПИСАТЕЛЬandwhile true do ПИСАТЕЛЬpa rendend.РИ решении данной задачи используются два семафора R и W, а также переменNR, предназначенная для подсчета текущего числа процессов типа «читатели»,Годящихся в критической секции.
Доступ к разделяемой области памяти осузд234Глава 7. Организация параллельных взаимодействующих вычисл^нн"ществляется через семафор W. Семафор R требуется для взаимного исключенапроцессов типа «читатели».Если критический ресурс не используется, то первый появившийся процесс поивходе в критическую секцию выполнит операцию P(W) и закроет семафор. Еслипроцесс является читателем, то переменная NR увеличится на единицу, и последующие читатели будут обращаться к ресурсу, не проверяя значения семафора Wчто обеспечит параллельность их доступа к памяти. Последний читатель, покидающий критическую секцию, является единственным, кто выполнит операцию V(W)и откроет семафор W. Семафор R предохраняет от некорректного изменения значения NR, а также от выполнения читателями операций P(W) и V(W).
Если в критической секции находится писатель, то на семафоре W может быть заблокирован только один читатель, все остальные будут блокироваться на семафоре R. Другиеписатели блокируются на семафоре W.Когда писатель выполняет операцию V(W), неясно, какого типа процесс войдет вкритическую секцию. Чтобы гарантировать получение читателями наиболее свежей информации, необходимо при постановке в очередь готовности использоватьдисциплину обслуживания, учитывающую более высокий приоритет писателей.Однако этого оказывается недостаточно, ибо если в критической секции продолжает находиться по крайней мере один читатель, то он не даст обновить данные, нои не воспрепятствует вновь приходящим процессам «читателям» войти в своюкритическую секцию.
Необходим дополнительный семафор. Пример правильногорешения этой задачи приведен в листинге 7.14.Листинг 7.14. Решение задачи «читатели-писатели» с приоритетом в доступек критическому ресурсу писателейvar S, W, R : semaphore;NR : integer:procedure ЧИТАТЕЛЬ;beginPCS): PCR):Inc(NR);if NR = 1 then P(W):VCS): VCR):Read_Data; { критическая секция }PCR):Dec(NR);if NR = 0 then VCW);VCR)end;procedure ПИСАТЕЛЬ;beginPCS): P(W);Write_Oata: { критическая секция }VCS): VCW)end;beginNR:=0;InitSem(S.l): InitSem(W.l); InitSem(R.l);parbeginwhile true do ЧИТАТЕЛЬandwhile true do ЧИТАТЕЛЬandwhile true do ЧИТАТЕЛЬandwhile true do ПИСАТЕЛЬandwhile true do ПИСАТЕЛЬandwhile true do ПИСАТЕЛЬparendend.Как можно заметить, семафор S блокирует приход новых читателей, если появился хотя бы один писатель.
Обратите внимание, что в процедуре ЧИТАТЕЛЬ использование семафора S имеет место только при входе в критическую секцию. Послевыполнения чтения уже категорически нельзя использовать этот семафор, ибо онтут же заблокирует первого же читателя, если хотя бы один писатель захочет войти в свою критическую секцию. И получится так называемая тупиковая ситуация,ибо писатель не сможет войти в критическую секцию, поскольку в ней уже находится читатель. А читатель не сможет покинуть критическую секцию, потому чтописатель желает войти в свою критическую секцию.Обычно программы, решающие проблему «читатели-писатели», используют каксемафоры, так и мониторные схемы с взаимным исключением, то есть такие, которые блокируют доступ к критическим ресурсам для всех остальных процессов, еслиодин из них модифицирует значения общих переменных.
Взаимное исключениетребует, чтобы писатель ждал завершения всех текущих операций чтения. Приусловии, что писатель имеет более высокий приоритет, чем читатель, такое ожидание в ряде случаев весьма нежелательно. Кроме того, реализация принципа взаимного исключения в многопроцессорных системах может вызвать определеннуюизбыточность.
Поэтому схема, представленная в листинге 7.15 и применяемаяиногда для решения задачи «читатели-писатели», в случае одного писателя допускает одновременное выполнение операций чтения и записи. После чтения данныхпроцесс «читатель» проверяет, мог ли он получить неправильное значение, некорректные данные (вследствие того, что параллельно с ним процесс «писатель» мог ихизменить), и если обнаруживает, что это именно так, то операция чтения повторяется.Листинг 7.15. Синхронизация процессов «читатели» и «писатель» без взаимного исключенияvar VI, V2 : integer:Procedure ПИСАТЕЛЬ;BeginInc(Vl);Write DataV2:=V1End:продолжениеё>236Глава 7 , О р г а н и з а ц и я параллельных в з а и м о д е й с т в у ю щ и х в ы ч и с л е н ^Листинг 7.15 (продолжение)Procedure ЧИТАТЕЛЬ;Var V: i n t e g e rBeginRepeatV:= V2;Read_DataU n t i l VI = VEnd;BeginVI := 0:V2 := 0:Parbeginw h i l e t r u e do ЧИТАТЕЛЬandw h i l e t r u e do ЧИТАТЕЛЬandw h i l e t r u e do ЧИТАТЕЛЬandw h i l e t r u e do ПИСАТЕЛЬpa rendend.Этот алгоритм использует для данных два номера версий, которым соответствуютпеременные VI и V2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
