Два параллельных процесса могут быть

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

Пособие разработано в соответствии с государственными образовательными стандартами высшего профессионального образования по направлению подготовки дипломированного специалиста: 654600 — "Информатика и вычислительная техника"(специальность 220100 — "Вычислительные машины, комплексы, системы и сети") и направлению подготовки бакалавра 552800 — "Информатика и вычислительная техника". В пособии рассмотрены классификация и архитектура современных операционных систем, концепции управления процессами и потоками, а также механизмы управления виртуальной памятью. Учебное пособие предназначено для студентов, изучающих дисциплину "Операционные системы" в шестом семестре.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Более точно проблема формулируется так.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;

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

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

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

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

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

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