Основные теоретические положения. Программа реализации алгоритма взаимоисключения

Программа реализации алгоритма взаимоисключения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.5.1. Работа процессов с разделяемыми данными.

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

· Считать из файла базы данных в буфер запись о клиенте с заданным идентификатором;

· Внести новое значение в поле заказ (для потока A) или оплата (для потока B);

· Вернуть модифицированную запись в файл базы данных.

Обозначим соответствующие шаги для потока A как A₁, A₂, A₃, а для потока B – B₁, B₂, B₃. Предположим, что тому и другому потоку потребовалось изменить сведения о заказе и оплате одного и того же клиента N. В некоторый момент времени поток A считывает соответствующую клиенту запись в буфер и модифицирует значение поля заказ (шаги A₁, A₂), но внести эту запись в базу (выполнить шаг A₃) не успевает, т.к. его выполнение прерывается, например, вследствие завершения отведенного ему кванта времени. Когда подходит очередь потока B, он тоже успевает только считать запись в буфер и произвести изменения в поле оплата (шаги B₁, B₂), а внести измененную запись (шаг B₃) в базу не успевает.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задание

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

Создать и реализовать модель алгоритма взаимного исключения. Необходимо визуализировать с помощью сетей Петри фрагмент управления доступом к критическим секциям двух процессов, функционирующим таким образом, что оба процесса не могут одновременно выполнять свои критические секции. Модель такой системы приведена на рис.5.2. Позиция m представляет собой разрешение для входа в критическую секцию. Для того чтобы какой-либо процесс вошел в критическую секцию, он должен иметь фишку в p1 или p2 соответственно, свидетельствующую о желании попасть в критическую секцию, а также должна существовать фишка в m, дающая разрешение на вход. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск t1 запретит переход t2, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию m.

Рис.5.2. Модель взаимного исключения.

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

1. Используйте Вашу среду исследования функционирования операционной системы.

2. Для моделирования используйте 2 процесса.

3. Создайте критическую секцию, используя соответствующие API функции.

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

5. Запустите все процессы с визуализацией происходящего в соответствии с рис.5.2.

Контрольные вопросы

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

2. Взаимодействие процессов и потоков в мультипрограммной системе, понятие критической секции. Пример эффекта гонок.

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

Р а з д е л VI

Дата добавления: 2014-12-07