Размещено на http://allbest.ru

Размещено на http://allbest.ru

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

Реферат

по дисциплине: «Системное программное обеспечение»

на тему:

«Независимые и взаимодействующие вычислительные процессы»

Выполнил: Студент Петров И.В.

Проверил: ст. преподаватель

Невиницин В.Ю.

Иваново 2015



Содержание

1. Независимые и взаимодействующие вычислительные процессы

2. Взаимодействие процессов

2.1 Параллельные процессы

2.2 Критическая секция. Взаимоисключение

2.3 Способы реализации взаимного исключения

2.4 Семафоры и их применение

2.5 Мьютексы

2.6 Мониторы Хоара

3. Платформенно-независимый интерфейс POSIX

4. Использование блокировки памяти при синхронизации параллельных процессов

4.1 Листинг 6.1: Первый вариант попытки реализации взаимного исключения

4.2 Листинг 6.2: Второй вариант попытки реализации взаимного исключения

4.3 Листинг 6.3: Третий вариант попытки реализации взаимного исключения

Список используемой литературы



1. Независимые и взаимодействующие вычислительные процессы

Основной особенностью мультипрограммных операционных систем является то, что в их среде параллельно развивается несколько (последовательных) вычислительных процессов. С точки зрения внешнего наблюдателя эти последовательные вычислительные процессы выполняются одновременно, мы будем использовать термин «параллельно».

При этом под параллельными понимаются не только процессы, одновременно развивающиеся на различных процессорах, каналах и устройствах ввода/вывода, но и те последовательные процессы, которые разделяют центральный процессор и хотя бы частично перекрываются во времени.

Любая мультипрограммная операционная система вместе с параллельно выполняющимися в ней задачами пользователей может быть логически описана как совокупность последовательных процессов, которые, с одной стороны, состязаются за использование ресурсов, переходя из одного состояния в другое, а с другой -- действуют почти независимо друг от друга, но образуют систему вследствие установления всевозможного рода связей между ними (путем пересылки сообщений и синхронизирующих сигналов).

Итак, параллельными мы будем называть такие последовательные вычислительные процессы, которые одновременно находятся в каком-либо активном состоянии. Два параллельных процесса могут быть независимыми (independing processes) либо взаимодействующими (cooperating processes).

Независимыми являются процессы, множества переменных которых не пересекаются. Под переменными в этом случае понимают файлы данных, а также области оперативной памяти, сопоставленные определенным в программе и промежуточным переменным. Независимые процессы не влияют на результаты работы друг друга, так как не могут изменить значения переменных другого независимого процесса. Они могут только явиться причиной задержек исполнения других процессов, так как вынуждены разделять ресурсы системы. Взаимодействующие процессы совместно используют некоторые (общие) переменные, и выполнение одного процесса может повлиять на выполнение другого.

Как мы уже говорили, при выполнении вычислительные процессы разделяют ресурсы системы. Подчеркнем, что при рассмотрении вопросов синхронизации вычислительных процессов из числа разделяемых ими ресурсов исключаются: центральный процессор и программы, реализующие эти процессы; то есть с логической точки зрения каждому процессу соответствуют свои процессор и программа, хотя в реальных системах обычно несколько процессов разделяют один процессор и одну или несколько программ. мультипрограммный интерфейс процесс

Многие ресурсы вычислительной системы могут совместно использоваться несколькими процессами, но в каждый момент времени к разделяемому ресурсу может иметь доступ только один процесс. Ресурсы, которые не допускают одновременного использования несколькими процессами, называются критическими.

Если нескольким вычислительным процессам необходимо пользоваться критическим ресурсом в режиме разделения, им следует синхронизировать свои действия таким образом, чтобы ресурс всегда находился в распоряжении не более чем одного из процессов. Если один процесс пользуется в данный момент критическим ресурсом, то все остальные процессы, которым нужен этот ресурс, должны получить отказ и ждать, пока он не освободится.

Если в операционной системе не предусмотрена защита от одновременного доступа процессов к критическим ресурсам, в ней могут возникать ошибки, которые трудно обнаружить и исправить. Основной причиной возникновения этих ошибок является то, что процессы в мультипрограммных операционных системах развиваются с различными скоростями, а относительные скорости развития каждого из взаимодействующих процессов не известны и не подвластны ни одному из них. Более того, на их скорости могут влиять решения планировщиков, касающиеся других процессов, с которыми ни одна из этих программ не взаимодействует. Кроме того, содержание одного процесса и скорость его исполнения обычно неизвестны другому процессу. Поэтому влияние, которое оказывают друг на друга взаимодействующие процессы, не всегда предсказуемо и воспроизводимо.

Взаимодействовать могут либо конкурирующие процессы, либо процессы, совместно выполняющие общую работу. Конкурирующие процессы, на первый взгляд, действуют относительно независимо, но они имеют доступ к общим переменным.

Процессы, выполняющие общую совместную работу таким образом, что результаты вычислений одного процесса в явном виде передаются другому, то есть их работа построена именно на обмене данными, называются сотрудничающими.

Взаимодействие сотрудничающих процессов удобно всего рассматривать в схеме «производитель -- потребитель» (produces -- consumer) или, как часто говорят -- «поставщик -- потребитель». В качестве первого примера рассмотрим работу двух процессов Р1 и Р2 с общей переменной X.

Пусть оба процесса асинхронно, независимо один от другого, изменяют (например, увеличивают) значение переменной X, считывая ее значение в локальную область памяти Rj, при этом каждый процесс выполняет некоторые последовательности операций во времени (рис. 6.1).

Процесс Р1	Процесс Р2
	R1:=X		R2:=X
	R1:=R1+X		R2:=R2+1
	X:=R1		X:=R2

Рис. 6.1 Пример конкурирующих процессов



Здесь мы рассмотрим не все операторы каждого из процессов, а только те, в которых осуществляется работа с общей переменной X. Каждому из операторов мы присвоили некоторый условный номер.

Поскольку при мультипрограммировании процессы могут иметь различные скорости исполнения, то может иметь место любая последовательность выполнения операций во времени. Если сначала будут выполнены все операции процесса Р1, а уже потом -- все операции процесса Р2 (или, наоборот, сначала операции 4-6, а затем -- операции 1-3), то в итоге переменная X получит значение, равное Х+2 .

Однако, если в промежуток времени между выполнением операций 1 и 3 будет выполнена хотя бы одна из операций 4-6, то значение переменной X после выполнения всех операций будет не (Х+2), а (Х+1).

Понятно, что это очень серьезная (и, к сожалению, неисправимая, так как ее нельзя проконтролировать) ошибка. Например, если бы процессы Р1 и Р2 осуществляли продажу билетов и переменная X фиксировала количество уже проданных, то в результате некорректного взаимодействия было бы продано несколько билетов на одно и то же место.

В качестве второго примера приведем пару процессов, которые изменяют различные поля записей служащих какого-либо предприятия. Пусть процесс АДРЕС изменяет домашний адрес служащего, а процесс СТАТУС -- его должность и зарплату. Пусть каждый процесс копирует всю запись СЛУЖАЩИЙ в свою рабочую область.

Предположим, что каждый процесс должен обработать некоторую запись ИВАНОВ. Предположим также, что после того, как процесс АДРЕС скопировал запись ИВАНОВ в свою рабочую область, но до того, как он записал скорректированную запись обратно, процесс СТАТУС скопировал первоначальную запись ИВАНОВ в свою рабочую область. Изменения, выполненные тем из процессов, который первым запишет скорректированную запись назад в файл СЛУЖАЩИЕ, будут утеряны и, возможно, никто не будет знать об этом.

Чтобы предотвратить некорректное исполнение конкурирующих процессов вследствие нерегламентированного доступа к разделяемым переменным, необходимо ввести механизм взаимного исключения, который не позволит двум процессам одновременно обращаться к разделяемым переменным.

Кроме реализации в операционной системе средств, организующих взаимное исключение и тем самым регулирующих доступ процессов к критическим ресурсам, в ней должны быть предусмотрены средства, синхронизирующие работу взаимодействующих процессов. Другими словами, процессы должны обращаться к неким средствам не только ради синхронизации с целью взаимного исключения, но и чтобы обмениваться данными.

Допустим, что «поставщик» -- это процесс, который отправляет порции информации (сообщения) другому процессу, имя которого «потребитель». Например, процесс пользователя, порождающий строки для вывода, может выступать как «поставщик», а процесс, который выводит эти строки на печать, -- как «потребитель». Один из методов, применяемых при реализации передачи сообщений, состоит в том, что заводится пул свободных буферов, каждый из которых может содержать одно сообщение (длина сообщения может быть произвольной, но ограниченной).

В этом случае между процессами «поставщик» и «потребитель» будем иметь очередь заполненных буферов, содержащих сообщения. Когда «поставщик» хочет послать очередное сообщение, он добавляет в конец этой очереди еще один буфер. «Потребитель», чтобы получить сообщение, забирает из очереди буфер, который стоит в ее начале.

Такое решение, хотя и кажется тривиальным, требует, чтобы «поставщик» и «потребитель» синхронизировали свои действия. Например, они должны следить за количеством свободных и заполненных буферов. «Поставщик» может передавать сообщения только до тех пор, пока имеются свободные буферы. Аналогично, «потребитель» может получать сообщения только если очередь не пуста. Ясно, что для учета заполненных и свободных буферов нужны разделяемые переменные, поэтому для сотрудничающих процессов, как и для конкурирующих, тоже возникает необходимость во взаимном исключении.

Таким образом, до окончания обращения одной задачи к общим переменным следует исключить возможность обращения к ним другой задачи. Эта ситуация и называется взаимным исключением. Другими словами, при организации различного рода взаимодействующих процессов приходится организовывать взаимное исключение и решать проблему корректного доступа к общим переменным (критическим ресурсам). Те места в программах, в которых происходит обращение к критическим ресурсам, называются критическими секциями или критическими интервалами (Critical Section -- CS).

Решение этой проблемы заключается в организации такого доступа к критическому ресурсу, когда только одному процессу разрешается входить в критическую секцию. Данная задача только на первый взгляд кажется простой, ибо критическая секция, вообще говоря, не является последовательностью операторов программы, а является процессом, то есть последовательностью действий, которые выполняются этими операторами. Другими словами, несколько процессов, которые выполняются по одной и той же программе, могут выполнять критические интервалы, базирующиеся на одной и той же последовательности операторов программы.

Когда какой-либо процесс находится в своем критическом интервале, другие процессы могут, конечно, продолжать свое исполнение, но без входа в их критические секции.

Взаимное исключение необходимо только в том случае, когда процессы обращаются к разделяемым, общим данным. Если же они выполняют операции, которые не приводят к конфликтным ситуациям, они должны иметь возможность работать параллельно. Когда процесс выходит из своего критического интервала, то одному из остальных процессов, ожидающих входа в свои критические секции, должно быть разрешено продолжить работу (если в этот момент действительно есть процесс в состоянии ожидания входа в свой критический интервал).

Обеспечение взаимоисключения является одной из ключевых проблем параллельного программирования. При этом можно перечислить следующие требования к критическим секциям:

· в любой момент времени только один процесс должен находиться в своей критической секции;

· ни один процесс не должен находиться в своей критической секции бесконечно долго;

· ни один процесс не должен ждать бесконечно долго входа в свой критический интервал. В частности:

1. никакой процесс, бесконечно долго находящийся вне своей критической секции (что допустимо), не должен задерживать выполнение других процессов, ожидающих входа в свои критические секции. Другими словами, процесс, работающий вне своей критической секции, не должен блокировать критическую секцию другого процесса;

2. если два процесса хотят войти в свои критические интервалы, то принятие решения о том, кто первым войдет в критическую секцию, не должно откладываться бесконечно долго;

· если процесс, находящийся в своем критическом интервале, завершается либо естественным, либо аварийным путем, то режим взаимоисключения должен быть отменен, с тем чтобы другие процессы получили возможность входить в свои критические секции.

Было предложено несколько способов решения этой проблемы -- программные и аппаратные; частные, низкоуровневые и глобальные, высокоуровневые; предусматривающие свободное взаимодействие между процессами и требующие строгого соблюдения жестких протоколов.



2. Взаимодействие процессов

Основной особенностью мультипрограммных вычислительных систем является то, что в их среде параллельно развивается несколько (последовательных) вычислительных процессов.

С точки зрения внешнего наблюдателя эти процессы выполняются одновременно, поэтому будем считать их работающими параллельно независимо от того, реально они используют в некоторый момент времени различные процессоры, каналы, устройства или разделяют одни и те же ресурсы во времени.

Любая мультипрограммная ОС вместе с параллельно выполняющимися в ней задачами пользователей может быть логически описана как совокупность последовательных процессов. Эти процессы, с одной стороны, состязаются за использование ресурсов, переходя из одного состояния в другое, а с другой - действуют почти независимо друг от друга, но образуют систему вследствие установления всевозможных связей между ними путем пересылки сообщений и синхронизирующих сигналов.

2.1 Параллельные процессы

Два параллельных процесса могут быть независимыми или взаимодействующими.

Независимыми являются процессы, множества переменных которых не пересекаются. Под переменными в этом случае понимают файлы данных, а также области оперативной памяти, сопоставленные определенным в программе переменным.

Независимые процессы не влияют на результаты работы друг друга, т.к. не могут изменить значение переменных другого независимого процесса. Они могут только являться причиной задержек исполнения других процессов, т.к. вынуждены разделять ресурсы системы.

Взаимодействующие процессы совместно используют некоторые общие переменные, и выполнение одного процесса может повлиять на выполнение другого.

Взаимодействовать могут либо конкурирующие процессы, либо совместно выполняющие общую работу.

Конкурирующие процессы на первый взгляд действуют относительно независимо, но имеют доступ к общим переменным. Процессы, работа которых построена на обмене данными (результат вычислений одного процесса в явном виде передается другому), называют сотрудничающими.

Многие ресурсы системы могут использоваться совместно несколькими процессами, но к разделяемым ресурсам в каждый момент времени может иметь доступ только один процесс. Ресурсы, которые не допускают одновременного использования несколькими процессами, называют критическими.

В системе должна быть предусмотрена защита от одновременного доступа процессов к критическим ресурсам, иначе в ней могут возникать непрогнозируемые и трудно обнаруживаемые ошибки.

В мультипрограммной системе потоки и процессы протекают асинхронно, с различными скоростями, на которые могут влиять еще и решения планировщиков относительно других процессов. Поэтому влияние взаимодействующих процессов друг на друга невозможно спрогнозировать. Чтобы предотвратить порчу общих данных и исключить взаимную блокировку, потокам необходимо синхронизировать свою работу.

Синхронизация заключается в согласовании скоростей потоков путем приостановки потока до наступления некоторого события и последующей его активизации, когда это событие произойдет.

Взаимодействие сотрудничающих потоков удобно рассматривать в схеме "производитель-потребитель": Поток-получатель должен обращаться за данными только после того, как они помещены в буфер потоком-отправителем. Если же поток-получатель обратился за данными раньше, то он должен быть приостановлен до момента поступления данных.

При отсутствии синхронизации возможны следующие проблемы:

Возникновение гонок. Гонками называется такая ситуация, когда два или более потоков обрабатывают разделяемые данные и конечный результат зависит от соотношения скоростей потоков.

Взаимные блокировки, или тупики (дедлоки, клинчи - разные термины для обозначения одного события).

Тупик - это состояние, когда несколько процессов ждут событий, которые могут быть вызваны только одним из этих процессов. Так как все процессы находятся в состоянии ожидания, то эти события не произойдут никогда, следовательно, без вмешательства системы ожидание будет бесконечным.

Существует ряд механизмов синхронизации потоков и процессов. Они могут образовывать иерархию, когда на основе более простых средств строятся более сложные, а также могут быть функционально специализированными, например, средства для синхронизации потоков одного процесса, средства для синхронизации потоков разных процессов при обмене данными и т.п.

Для синхронизации потоков прикладных программ программист может использовать как средства операционной системы, так и собственные приемы синхронизации.

Механизмы синхронизации различаются в зависимости от того, относятся они к потокам одного или разных процессов. Для синхронизации потоков одного процесса можно использовать глобальные блокирующие переменные, которые позволяют контролировать работу потоков в критической секции (мониторы, семафоры).

Для потоков разных процессов ОС использует системные семафоры, события, сигналы, таймеры и пр. В распределенных системах, состоящих из нескольких процессоров, синхронизация может быть реализована только посредством передачи сообщений. Рассмотрим несколько более подробно некоторые названные средства синхронизации и связанные с ними понятия.

2.2 Критическая секция. Взаимоисключение

Критическая секция - это часть программы, результат выполнения которой может непредсказуемо меняться, если переменные, относящиеся к этой части программы, изменяются другими потоками, когда выполнение этой части еще не завершено. Критическая секция всегда определяется по отношению к критическим данным, при несогласованном изменении которых могут возникнуть нежелательные эффекты.

Общие данные, разделяемые несколькими потоками, удобно описывать как ресурс, а обновление данных соответствует распределению или освобождению элементов ресурса.

В такой ситуации окончательный результат, занесенный в базу, будет зависеть от того, какой из потоков - A или B - первым получит возможность закончить свою работу. Но как в том, так и в другом случае часть информации окажется потерянной, хотя все исправления были успешно внесены. Сохранится только изменение, сделанное потоком, который последним занесет запись о клиенте в базу данных. Здесь также имеет место эффект гонок.

В данном примере критической секцией потока A являются A₁, A₂, A₃, а потока B - B₁, B₂, B₃.

Для исключения описанного эффекта по отношению к критическим данным необходимо обеспечить, чтобы в каждый момент времени в критической секции, связанной с этими данными, находился только один поток. При этом неважно, в активном или приостановленном состоянии он находится.

Этот прием называют взаимным исключением. Следует отметить, что вне критических секций потоки должны иметь возможность работать параллельно. Более точно проблема формулируется так.

Пусть имеется мультипрограммная система с общей памятью. Каждая из программ, выполняемых процессором, содержит критическую секцию, в которой организован доступ к общим данным. Программы выполняются циклически. Необходимо так запрограммировать доступ к общей памяти, чтобы в любой момент только одна из программ находилась в своей критической секции.

Относительно системы сделаны следующие предположения:

Считывание из общей памяти и запись в нее - неделимые операции. Одновременные обращения (на запись или на считывание) к одной и той же ячейке памяти более чем одного процесса приведут к последовательным обращениям в произвольном порядке.

Критические секции не могут иметь связанных с ними приоритетов.

Относительные скорости процессов неизвестны.

Программа может останавливаться вне критической секции (КС).

Требования к критическим секциям:

- в любой момент времени только один процесс может находиться в своей критической секции;

- ни один процесс не должен находиться в своей критической секции бесконечно долго;

- ни один процесс не должен ждать бесконечно долго входа в свой критический интервал;

- если процесс, находящийся в своем критическом интервале, завершается либо естественным, либо аварийным путем, то режим взаимоисключения должен быть отменен, с тем, чтобы другие процессы получили возможность входить в свои критические секции.



2.3 Способы реализации взаимного исключения

Самый простой и самый неэффективный способ обеспечения взаимного исключения состоит в том, что ОС позволяет потоку запрещать любые прерывания на время его нахождения в критической секции. Но доверять управление системой пользовательскому потоку опасно - он может надолго занять процессор, а при крахе потока в критической секции крах потерпит вся система, т.к. прерывания никогда не будут разрешены.

Будем предполагать, что система циклических потоков для проблемы критической секции имеет следующие программные формы:

parbegin

P1: while true do

Begin CS1; program_1; end;

P2: while true do

Begin CS2; program_2; end;

...

Pn: while true do

Begin CSn; program_n; end;

parend

Здесь управляющая конструкция parbegin ... parend используется для указания на то, что часть программы, заключенная между этими операторами, должна выполняться параллельно. Через идентификатор CS с номером обозначены критические секции каждого потока, program_1, program_2, …, program_n представляют собой те части потоков, которые не обращаются к общим данным и могут работать параллельно без каких бы то ни было ограничений.

Пусть проблема ограничена двумя потоками. Нашей целью является недопущение одновременного вхождения обоих потоков в их критические секции, т.е. взаимное исключение. В то же время должны быть устранены два возможных типа блокировки:

Поток, нормально работающий вне своей КС, не должен блокировать другой поток при вхождении последнего в свою КС.

Два потока, готовые войти в свои КС, не должны откладывать неопределенно долго решение вопроса о том, который из них войдет в свою КС первым.

Рассмотрим различные методы решения данной проблемы и покажем ловушки, которые при этом возникают.

Проблема решается легко, если потребовать, чтобы потоки входили в свои КС попеременно. Одна общая переменная может хранить указатель на то, чья очередь войти в КС.

Рассмотрим программную реализацию этого варианта (назовем его вариант 1).

Program Variant1;

Var turn : integer; {общая переменная}

Procedure process_1;

Begin

While true Do

Begin

While turn=2 Do; {активное ожидание}

CS1;

turn:=2;

program_1;

End;

End;

Procedure process_2;

Begin

While true Do

Begin

While turn=1 Do; {активное ожидание}

CS2;

turn:=1;

program_2;

End;

End;

Begin

turn:=1;

Parbegin

process_1; {процессы работают параллельно}

process_2;

Parend

End.

Здесь переменная turn указывает то, какой поток должен входить в критическую секцию.

Возможные неприятности: если первый из потоков гораздо медленнее другого, такое решение будет неэффективным. Может возникнуть ситуация, когда поток 2, выполнив работу в своей КС, передаст очередь первому потоку, затем выполнит действия вне своей КС и снова начнет на нее претендовать, а тот еще даже не соберется заходить в КС.

Тем самым он блокирует второй поток по первому типу, хотя программа и не может оказаться в состоянии полного тупика. Если же один из процессов завершится раньше другого, то второй вообще окажется не в состоянии продолжить выполнение. В рассмотренном примере мы имеем дело с жесткой синхронизацией.

Во второй версии программы делается попытка устранить указанные недостатки путем введения двух общих переменных CS1_in, CS2_in - флагов, которые будут указывать на то, находится ли каждый поток внутри своей критической секции. При такой организации более быстрый поток может несколько раз подряд войти в свой критический интервал, если другому потоку это пока не нужно

Пусть первый процесс проверил переменную CS2_in и обнаружил, что она имеет значение "ложь", но изменить значение своей переменной CS1_in не успел, в то время как второй процесс проделал то же самое. Тогда в результате выполненных проверок они оба одновременно войдут в свои критические интервалы, так что программа данной версии не гарантирует взаимного исключения.

Существует еще ряд вариантов взаимоисключения, но все они не свободны от недостатков.

Рассмотрим алгоритм реализации взаимоисключения, предложенный Деккером. Он не требует никаких специальных аппаратно-реализованных команд и позволяет избежать недостатков рассмотренных алгоритмов.

В этом алгоритме каждому из процессов соответствует логическая переменная, принимающая значение "истина", если этот процесс претендует на вход в критический интервал. Переменная turn принимает значения, соответствующие номеру выбранного на выполнение процесса.

2.4 Семафоры и их применение

Понятия, относящиеся к проблеме взаимоисключения, Дейкстра обобщил в своей концепции семафоров. Семафор - это переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: "закрытия" и "открытия", названных соответственно P- и V-операциями.

Значение семафора можно опрашивать и менять только при помощи примитивов P и V и операции инициализации. Семафоры могут быть двоичными (принимать значения только 0 или 1) или считающими (принимать целые неотрицательные значения).

Операции P и V неделимы в своем выполнении и взаимно исключают друг друга. Примитивы P и V значительно упростили синхронизацию процессов.

Семафорный механизм работает по схеме, в которой сначала исследуется состояние критического ресурса, идентифицируемое значением семафора, а затем уже осуществляется допуск к критическому ресурсу или отказ от него на некоторое время.

При отказе доступа к критическому ресурсу используется режим "пассивного ожидания". Поэтому в состав механизма включаются средства формирования и обслуживания очереди ожидающих процессов, которые реализуются супервизором операционной системы.

Находясь в списке заблокированных, процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо этого процессор занимается полезной работой, что повышает эффективность работы системы.

Пусть S - семафор. Операция V над семафором S записывается как V(S) и увеличивает переменную S на единицу одним неделимым действием, т.е. выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время операции V(S).

Операция P над семафором S записывается как P(S) и уменьшает переменную S на единицу, если это возможно. Если было S=0, то уменьшение S невозможно и процесс, вызвавший P-операцию, ждет, пока значение S не увеличится. Проверка и уменьшение значения S также являются одним неделимым действием.

Рассмотрим вариант реализации семафорных примитивов:

P(S): S:=S-1;

If S<0 Then {остановить процесс и поместить его в очередь ожидания к семафору S}

V(S): If S<0 Then {поместить один из ожидающих процессов очереди семафора S в очередь готовности};

S:=S+1;

Если несколько процессов одновременно запрашивают P- или V-операции над одним и тем же семафором, то эти операции будут выполняться последовательно в произвольном порядке. Аналогично, если несколько процессов ожидают выполнения P-операции и изменяемый семафор становится положительным, то процесс на продолжение выполнения может выбираться по произвольному закону. Участки взаимоисключения по семафору S в параллельных процессах обрамляются операциями P(S) и V(S).

Для работы с семафорными переменными необходимо еще иметь операцию инициализации самого семафора, т.е. операцию задания ему начального значения. Обычно эту операцию называют InitSem и она, как правило, имеет два параметра - имя семафорной переменной и ее начальное значение. Обращение к ней тогда будет иметь, например, следующий вид: InitSem(S,1).

В настоящее время используется много различных видов семафорных механизмов. Варьируемыми параметрами, которые отличают различные виды примитивов, являются начальное значение и диапазон изменения значений семафора, логика действий семафорных операций, количество семафоров, доступных для обработки при исполнении отдельного примитива. В некоторых реализациях семафорные переменные могут быть отрицательными, и величина отрицательного значения в таком случае указывает на длину очереди процессов, стоящих в состоянии ожидания открытия семафора.

Семафоры и операции над ними могут быть реализованы как программно, так и аппаратно. Программно они могут быть реализованы с использованием режима активного ожидания, однако это сопряжено с потерей эффективности. Как правило, они реализуются в ядре операционной системы, где осуществляется управление сменой состояния процессов.

Семафорные операции дают простое решение проблемы КС. Пусть S - семафор, используемый для защиты КС. Тогда примитив P(S) представляет собой вход взаимоисключения, а примитив V(S) - выход взаимоисключения. Рассмотрим пример программы, обеспечивающей взаимоисключение при помощи семафора.

Семафор имеет начальное значение, равное 1. Если первый и второй процессы попытаются одновременно выполнить примитив P(S), то это удастся успешно сделать только одному из них.

Предположим, что это сделал первый процесс. Он закрыл семафор, т.е. значение семафора стало S = 0, после чего данный процесс вошел в свой критический интервал. Второй процесс при этом оказывается заблокированным на семафоре - при попытке выполнения операции P(S) он "засыпает".

Взаимное исключение гарантировано, т.к. только один процесс может уменьшить значение S до нуля с помощью P-операции. Очевидным образом это решение распространяется на случай n процессов - тогда все другие процессы, пытающиеся войти в свои КС при S = 0, будут вынуждены ожидать по P(S). Взаимное блокирование невозможно, т.к. одновременные попытки войти в свои КС при S = 0 должны, по определению, преобразовываться в последовательные P-операции. После выхода из своей КС процесс выполняет V-операцию, тем самым открывая семафор и предоставляя возможность "пробуждения" блокированным процессам. Тогда один из блокированных процессов переводится в очередь готовности.

При реализации возможно одно из двух решений в отношении процессов, которые переводятся из очереди ожидания в очередь готовности при выполнении примитива V(S):

- процесс при его активизации вновь пытается выполнить примитив P, считая предыдущую попытку неуспешной;

- процесс при помещении его в очередь готовности отмечается как успешно выполнивший примитив P. Тогда при его активизации управление будет передано не на повторное выполнение примитива P, а на команду, следующую за ним.

При первом способе возможна следующая последовательность событий. Предположим, что начальное значение семафора было равно единице. Пусть процесс2 в какой-то момент времени выполнит операцию P(S), семафор S станет равным нулю, а процесс2 войдет в свою КС. Далее процесс1 тоже попытается выполнить операцию P(S) и "заснет" на семафоре, поскольку значение семафора теперь станет равным -1. После выхода из КС процесс2 выполнит V(S), при этом значение семафора станет равным 0, а процесс1 переведется в очередь готовности.

После активизации процесс1 снова выполнит P(S) и опять "уснет", то же самое произойдет с процессом2, если он пожелает войти в свою КС. "Пробуждать" процессы станет некому. Таким образом, возможно возникновение тупиковой ситуации.

При втором способе реализации тупиковой ситуации не будет. Действительно, при аналогичном варианте развития событий отличие начнется с момента активизации процесса1. Он сразу войдет в свою КС. При этом никакой другой процесс не попадет в критическую секцию, т.к. семафор остается закрытым (его значение равно 0).

После окончания работы процесса1 в КС в результате выполнения им операции V(S) значение семафора установится в единицу, если другие процессы не совершали попыток попасть в КС. Если процесс2, а также и другие процессы в случае их большего количества, во время работы процесса1 в КС также выполнят примитив P(S), то после выполнения процессом1 V-операции семафор установится в 0. Следовательно, он будет закрыт для всех процессов кроме того, который успел выполнить P-операцию, т.е. сделал заявку на КС. Таким образом, тупик не возникнет, а взаимоисключение гарантировано.

Возникновение тупиков возможно в случае несогласованного выбора механизма реактивации процессов из очереди, с одной стороны, и выбора алгоритмов семафорных операций - с другой (как мы видим в первом способе реализации).

2.5 Мьютексы

из вариантов семафорных механизмов для реализации взаимного исключения являются т.н. мьютексы (mutex). Мьютексы реализованы во многих ОС, их основное назначение - организация взаимного исключения для потоков одного или разных процессов. Они представляют собой простейшие двоичные семафоры, которые могут находиться в одном из двух состояний - в отмеченном или неотмеченном (открыт и закрыт соответственно). Если какой-то поток становится владельцем объекта mutex, тот переводится в неотмеченное состояние. Когда задача освобождает мьютекс, его состояние становится отмеченным. В каждый момент времени только одна задача может владеть мьютексом.

Для того, чтобы мьютекс был доступен потокам разных процессов, при создании ему необходимо присвоить имя, которое потом должно быть передано "по наследству" другим задачам для использования при их взаимодействии.

Для этого существуют специальные системные вызовы (CreateMutex), в которых указывается начальное значение мьютекса, его имя и, возможно, атрибуты защиты. Если начальное значение мьютекса равно true, то считается, что задача, создавшая этот объект, будет сразу им владеть. При начальном значении false мьютекс не принадлежит ни одной из задач и его состояние можно изменить только специальным обращением.

Для работы с мьютексом имеется ряд функций: создание (CreateMutex), открытие (OpenMutex), ожидание событий (WaitForSingleObject и WaitForMultipleObjects), освобождение (ReleaseMutex). Конкретные обращения к этим функциям и перечни их параметров приводятся в документации на соответствующую ОС.

2.6 Мониторы Хоара

Несмотря на очевидные достоинства (простота реализации, независимость от количества процессов, отсутствие активного ожидания), семафоры имеют ряд недостатков. Семафорные механизмы являются слишком примитивными, т.к. сам семафор не указывает непосредственно на синхронизирующее условие, с которым он связан, или на критический ресурс. Поэтому при построении сложных схем синхронизации алгоритмы решения задач получаются запутанными и ненаглядными.

Нужны понятные и очевидные решения, которые позволяли бы создавать параллельные взаимодействующие программы. Таким решением являются т.н. мониторы, предложенные Хоаром.

Монитор (в параллельном программировании) - это пассивный набор разделяемых переменных и повторно входимых процедур доступа к ним, которым процессы пользуются в режиме разделения, причем в каждый момент им может пользоваться только один процесс.



3. Платформенно-независимый интерфейс POSIX

POSIX (Portable Operating System Interface for Computer Environments) -- платформенно независимый системный интерфейс для компьютерного окружения. Это стандарт IEEE, описывающий системные интерфейсы для открытых операционных систем, в том числе оболочки, утилиты и инструментарии.

Помимо этого, согласно POSIX, стандартизированными являются задачи обеспечения безопасности, задачи реального времени, процессы администрирования, сетевые функции и обработка транзакций. Стандарт базируется на UNIX-системах, но допускает реализацию и в других ОС.

POSIX возник как попытка всемирно известной организации IEEE пропагандировать переносимость приложений в UNIX-средах путем разработки абстрактного, платформенно-независимого стандарта.

Однако POSIX не ограничивается только UNIX-системами; существуют различные реализации этого стандарта в системах, которые соответствуют требованиям, предъявляемым стандартом IEEE Standard 1003.1-1990 (POSIX.1).

Например, известная ОС реального времени QNX соответствует спецификациям этого стандарта, что облегчает перенос приложений в эту систему, но UNIX-системой не является ни в каком виде, ибо ее архитектура использует абсолютно иные принципы.

Этот стандарт подробно описывает VMS (virtual memory system, систему виртуальной памяти), многозадачность (МРЕ, multiprocess executing) и технологию переноса операционных систем (CTOS).

Таким образом, на самом деле POSIX представляет собой множество стандартов, именуемых POSIX.1 -- POSIX. 12.

Таким образом, программы, написанные с соблюдением данных стандартов, будут одинаково выполняться на всех POSIX-совместимых системах. Однако стандарт в некоторых случаях носит лишь рекомендательный характер.

Часть стандартов описана очень строго, тогда как другая часть только поверхностно раскрывает основные требования. Нередко программные системы заявляются как POSIX-совместимые, хотя таковыми их назвать нельзя. Причины кроются в формальности подхода к реализации POSIX-интерфейса в различных ОС. На рис. 54 изображена типовая схема реализации строго соответствующего POSIX приложения.

Из рис. 5.1 видно, что для взаимодействия с операционной системой программа использует только библиотеки POSIX.1 и стандартную библиотеку RTL языка С, в которой возможно использование лишь 110 различных функций, также описанных стандартом POSIX.1.

К сожалению, достаточно часто с целью увеличить производительность той или иной подсистемы либо из соображений введения фирменных технологий, которые ограничивают использование приложения соответствующей операционной средой, при программировании используются другие функции, не отвечающие стандарту POSIX.

Реализации POSIX API на уровне операционной системы различны. Если UNIX-системы в своем абсолютном большинстве изначально соответствуют спецификациям IEEE Standard 1003.1-1990, то WinAPI не является POSIX-совместимым.

Однако для поддержки данного стандарта в операционной системе MS Windows NT введен специальный модуль поддержки POSIX API, работающий на уровне привилегий пользовательских процессов. Данный модуль обеспечивает конвертацию и передачу вызовов из пользовательской программы к ядру системы и обратно, работая с ядром через WinAPI. Прочие приложения, написанные с использованием WinAPI, могут передавать информацию POSIX-приложениям через стандартные механизмы потоков ввода/вывода (stdin, stdout).



4. Использование блокировки памяти при синхронизации параллельных процессов

Все вычислительные машины и системы имеют такое средство для организации взаимного исключения, как блокировка памяти. Это средство запрещает одновременное исполнение двух (и более) команд, которые обращаются к одной и той же ячейке памяти. Поскольку в некоторой ячейке памяти хранится значение разделяемой переменной, то получить доступ к ней может только один процесс, несмотря на возможное совмещение выполнения команд во времени на различных процессорах (или на одном процессоре, но с конвейерной организацией параллельного выполнения команд).

Механизм блокировки памяти предотвращает одновременный доступ к разделяемой переменной, но не предотвращает чередование доступа. Таким образом, если критические интервалы исчерпываются одной командой обращения к памяти, данного средства может быть достаточно для непосредственной реализации взаимного исключения. Если же критические секции требуют более одного обращения к памяти, то задача становится сложной, но алгоритмически разрешимой. Рассмотрим различные попытки использования механизма блокировки памяти для организации взаимного исключения при выполнении критических интервалов и покажем некоторые важные моменты, пренебрежение которыми приводит к неприемлемым или даже ошибочным решениям.

Возможные проблемы при организации взаимного исключения посредством использования только блокировки памяти

Пусть имеются два (или более) циклических процесса, в которых есть абстрактные критические секции, то есть каждый из процессов состоит из двух частей: некоторого критического интервала и оставшейся части кода, в которой нет работы с общими (критическими) переменными. Пусть эти два процесса асинхронно разделяют во времени единственный процессор либо выполняются на отдельных процессорах, каждый из которых имеет доступ к некоторой общей области памяти, с которой и работают критические секции. Проиллюстрируем эту ситуацию с помощью рис. 6.4.

Рис. 6.4. Модель взаимодействующих процессов

Проблема кажется легко решаемой, если потребовать, чтобы процессы ПР1 и ПР2 входили в свои критические интервалы попеременно. Для этого одна общая переменная может хранить указатель того, чья очередь войти в критическую секцию. Текст такого решения на языке, близком к Pascal, приведен в листинге 6.1.

4.1 Листинг 6.1: Первый вариант попытки реализации взаимного исключения

var перекл : integer;

begin перекл := 1; {при перекл=1 в CS находится процесс ПР1 }

parbegin

while true do

begin

while перекл = 2 do begin end;

CS1; { Критическая секция процесса ПР1 }

перекл := 2;

PR1; { оставшаяся часть процесса ПР1 }

end

and

while true do

begin

while перекл = 1 do begin end;

CS2; { Критическая секция процесса ПР2 }

перекл := 1;

PR2; { оставшаяся часть процесса ПР2 }

end

parend

end.

Здесь и далее конструкция следующего типа

parbegin...S11;S12; ... ; S1N₁

and... S21; S22; ... ; S2N₂

and... SK1; SK2; ... ; SKN_k

parend

означает параллельность К описываемых последовательных процессов. Конструкция из операторов S11; S12; ... ; S1N₁ выполняется оператор за оператором, о чем свидетельствует наличие точки с запятой между операторами.

Конструкция

while true do

begin S1; S2;…SN end



означает, что каждый процесс может выполняться неопределенное время.

Конструкция типа begin end означает «пустой» оператор.

Итак, решение, представленное в листинге 6.1, обеспечивает взаимное исключение в работе критических интервалов.

Однако если бы часть программы PR1 была намного длиннее, чем программа PR2, или если бы процесс ПР1 был заблокирован в секции PR1, или если бы процессор для ПР2 был с большим быстродействием, то процесс ПР2 вскоре вынужден был бы ждать (и, может быть, чрезвычайно долго) входа в свою критическую секцию CS2, хотя процесс ПР1 и был бы вне CS1. То есть при таком решении один процесс вне своей критической секции может помешать вхождению другого в свою критическую секцию.

Попробуем устранить это блокирование с помощью использования двух общих переключателей, которые используются как флаги для указания, находится ли соответствующий процесс вне своей критической секции.

Пусть с каждым из процессов ПР1 и ПР2 будет связана переменная, по смыслу являющаяся переключателем, которая принимает значение true, когда процесс находится в своем критическом интервале, и false -- в противном случае.

Прежде чем войти в свой критический интервал, процесс проверяет значение переключателя другого процесса. Если это значение равно true, процессу не разрешается входить в свой критический интервал.

В противном случае процесс «включает» свой собственный переключатель и входит в критический интервал. Этот алгоритм взаимного исключения представлен в листинге 6.2.

Данный алгоритм не гарантирует полного выполнения условия нахождения только одного процесса внутри критического интервала. Отсутствие гарантий связано с различными, в общем случае, скоростями развития процессов.

Поэтому, например, между проверкой значения переменной перекл2 процессом ПР1 и последующей установкой им значения переменной перекл1 параллельно выполняющийся процесс ПР2 может установить перекл2 в значение true, так как перекл1 еще не успел установиться в значение true.

Отсюда следует, что оба процесса могут войти одновременно в свои критические интервалы.

4.2 Листинг 6.2: Второй вариант попытки реализации взаимного исключения

Var перекл1,перекл2: boolean;

begin перекл1:=false;

перекл2:=false;

parbegin

while true do

begin

while перекл2 do

begin end;

переклl:=true;

CS1; (* Критический интервал процесса ПР1 *)

nepeклl:=false:

PR1; (* процесс ПР1 после критического интервала *)

end

and

while true do

begin

while перекл1 do

begin end;

перекл2:=true;

CS2; (* Критический интервал процесса ПР2 *)

перекл2:=fa1se;

PR2; (* процесс ПР2 после критического интервала *)

end

parend

end.

Следующий (третий) вариант решения этой задачи (листинг 6.3) усиливает взаимное исключение, так как в процессе ПР1 проверка значения переменной перекл2 выполняется после установки переменной перекл1 в значение true (аналогично для ПР2).

4.3 Листинг 6.3: Третий вариант попытки реализации взаимного исключения

var перекл1,перекл2 : boolean;

begin перекл1:=false;

перекл2:=false;

parbegin

ПР1: while true do

begin

перекл1:=true:

while перекл2 do

begin end;

CS1;{ Критический интервал процесса ПР1 }

перекл1:=false;

PR1;{ ПР1 после критического интервала }

end

and

ПР2: while true do

begin

перекл2:=trueж

while перекл1 do

begin end;

CS2; { Критический интервал процесса ПР2 }

перекл2:=false;

PR2; { ПР2 после критического интервала }

end

parend

end.

Алгоритм, приведенный в листинге 6.3, также имеет свои недостатки. Действительно, возможна ситуация, когда оба процесса одновременно установят свои переключатели в значение true и войдут в бесконечный цикл. В этом случае будет нарушено требование отсутствия бесконечного ожидания входа в свой критический интервал. Предположив, что скорости исполнения процессов произвольны, мы получили такую последовательность событий, при которой процессы вообще перестанут нормально выполняться.

Рассмотренные попытки решить проблему критических интервалов иллюстрируют некоторые тонкости, лежащие в основе этой проблемы.

Последний вариант решения задачи взаимного исключения, использующий только блокировку памяти, который мы рассмотрим, -- это известный алгоритм, предложенный математиком Деккером.



Список используемой литературы

1) Фигурнов В.Э. IBM PC ДЛЯ ПОЛЬЗОВАТЕЛЯ.- М..: Финансы и статистика, 1997.-432 с.

2) В.А. Острейковский. Информатика.-М., «Высшая школа», 2000, 511 с.

3) Информатика. Практикум по технологии работы на компьютере. /Под ред. Н.В Макаровой - М.: «Финансы и статистика» 1997. -384 с.

4) С. Симонович, Г. Евсеев, А. Алексеев. Специальная информатика. Учебное пособие. М.: «АЕ-ПРЕСС», 1998.

5) В.Г. Долголаптев. Работа в Excel 7. для0 Windows 95 на примерах: М.: БИНОМ. 1995 г.

6) Гончаров А. Excel 97 в примерах. - Санкт-Петербург: Питер Пресс, 1997. -329 с.

7) Р.Е. Симонян, С.Л. Симонян. Компьютер для юриста. Практическое пособие для начинающих. Ростов -на - Дону. “Феникс”, 1998, 349 с.

8) Компьютерные технологии в юридической деятельности. Уч. и практическое пособие . /Под ред. проф. Н. Полевого, к.ю.н. В. Крылова. М.: БЕК, 1994.

Размещено на Allbest.ru