Исследование алгоритмов (модель) взаимоисключения для двух процессов

Оглавление

Введение……………………………………………………………………...

Принцип взаимоисключения ……………………………………………….

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

Взаимодействие и взаимоисключение процессов…………………………

Варианты программного решения  проблемы взаимоисключения……….

Правильное решение проблемы  взаимоисключения……………………..

Алгоритм Деккера…………………………………………………………...

Доказательство правильности алгоритма Деккера......................................

Заключение…………………………………………………………………..

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

 

 

 

 

 

 

 

 

 

 

Введение.

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

Процессы  - выполнение пассивных инструкций компьютерной программы на процессоре ЭВМ. 

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

• При запуске ОС,
• При появлении запроса на создание процесса — происходит в случае, если работающий процесс создает новый процесс.

Завершение процесса происходит в минимум 2 этапа завершения: а)процесс удаляется из всех очередей планирования, т.е. ОС больше не планирует выделение каких-либо ресурсов процессу; б)сбор статистики о потреблённых процессом ресурсов с последующим удалением его из памяти.

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

• Обычный выход
• Выход по исключению или ошибке
• Недостаточный объем памяти
• Превышение лимита отведённого программе времени
• Выход за пределы отведённой области памяти
• Неверная команда (данные интерпретируются как команды)
• Ошибка защиты
• Завершение родительского процесса
• Ошибка ввода/вывода
• Вмешательство оператора

Процессы в информационной системе:

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

С учетом сферы применения выделяют: технические ИС, экономические  ИС, ИС в гуманитарных областях и  т.д.

рис.1, процессы в информационных сетях

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

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

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

Обратите внимание, что надо быть весьма осторожным при использовании  критического раздела в главном  потоке. Если вторичный поток проводит слишком много времени в его  собственном критическом разделе, то это может привести к "зависанию" главного потока на слишком большой  период времени.

 

 

 

 

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

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

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

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

обеспечивающих выполнение следующих условий:

     • при обращении  нескольких процессов к одному  разделяемому ресурсу только  одному из них разрешено воспользоваться

этим ресурсом;

     • в каждый  момент времени только один  процесс должен владеть критическим  ресурсом.

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

 

 

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

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

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

     1) примитив  вход_взаимоисключения – с его помощью фиксируется захват критического ресурса данным процессом и

устанавливается запрет на использование его другими процессами;

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

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

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

     В рассматриваемом  случае двух процессов эти  примитивы работают следующим  образом. Когда процесс П1 выполняет

примитив вход_взаимоисключения и если при этом процесс П2 находится вне своего критического участка, то П1 входит в свой критический участок, выполняет работу с критическим ресурсом, а затем выполняет примитив вы-

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

     Если процессы  П1 и П2 выполняют вход_взаимоисключения одновременно, то одному из них операционная система раз-

решает продолжить работу, а другой переводит в состояние ожидания.

 

 

 Взаимодействие  и взаимоисключение процессов

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

Многие современные микропроцессоры исполняют инструкции не по порядку. Алгоритм не будет работать на SMP-машинах, оборудованных такими CPU, если не использовать барьеры памяти.

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

-       определения доступности запрашиваемых ресурсов (ресурс свободен и может быть выделен для использования, ресурс уже занят одним из процессов программы и не может использоваться дополнительно каким-либо другим процессом);

-       выделения свободного ресурса одному из процессов, запросивших ресурс для использования;

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Первая попытка

Как упоминалось ранее, любая попытка  взаимного исключения должна опираться  на некий фундаментальный механизм исключений аппаратного обеспечения. Наиболее общим механизмом может  служить ограничение, согласно которому к некоторой ячейке памяти в определенный момент времени может осуществляться только одно обращение. Воспользовавшись этим ограничением, зарезервируем глобальную ячейку памяти, которую назовем turn. Процесс (Р0 или Р1), который намерен выполнить критический раздел, сначала проверяет содержимое ячейки памяти turn. Если значение turn равно номеру процесса, то процесс может войти в критический раздел; в противном случае он должен ждать, постоянно опрашивая значение turn до тех пор, пока оно не позволит процессу войти в критический раздел. Такая процедура известна как пережидание занятости (busy waiting), поскольку процесс вынужден, по сути, не делать ничего полезного до тех пор, пока не получит разрешение на вход в критический раздел. Более того, он

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

Говоря формально, имеется глобальная переменная

int turn = 0;

На рис. 5.1,а показана программа  для двух процессов. Это решение  гарантирует корректную работу взаимоисключения, однако имеет два недостатка. Во-первых, при входе в критический раздел процессы должны строго чередоваться; тем самым скорость работы диктуется более медленным из двух процессов. Если процессу Р0 вход в критический раздел требуется раз в час, а процессору Р1 — 1000 раз в час, то темп работы Р1 будет таким же, как и у процесса Р0. Во-вторых, гораздо более серьезная ситуация возникает в случае сбоя одного из процессов — при этом второй процесс оказывается заблокирован (при этом неважно, происходит ли сбой процесса в критическом разделе или нет). 
Описанная конструкция представляет собой сопрограмму (coroutine). Сопрограммы разрабатываются таким образом, чтобы быть способными передавать управление друг другу. Однако хотя эта технология структурирования и весьма полезна для отдельно взятого процесса, для поддержки параллельных вычислений она не подходит.

/* Процесс 0 */    while (turn != 0)  /* Ничего не делаем */;  /* Критический раздел */;  turn = 1;	/* Процесс 1 */      while (turn != 1)  /* Ничего не делаем */;  /* Критический раздел */;  turn = 0;
(а)         Первая попытка
/* Процесс 0 */    while (flag[l])   /* Ничего не делаем */;  flag[0] = true;   /* Критический раздел */;  flag[0] = false;	/* Процесс 1 */   while (flag[0])   /* Ничего не делаем */;  flag[1] = true;   /* Критический раздел */;  flag[0] = false;
(б)       Вторая попытка
/* Процесс 0 */  flag[0] = true;  while (flag[l])  /* Ничего не делаем */;  /* Критический раздел */;  flag[0] = false;	/* Процесс 1 */  flag[1] = true;   while (flag[0])   /* Ничего не делаем */;  /* Критический раздел */;  flag[1] = false;
(в)       Третья попытка
/* Процесс 0 */ * flag[0] = true;  while (flag[l])  {  flag[O] = false;  /* Задержка */  flag[O] = true;  }  /* Критический раздел */;  flag[O] = false;	/* Процесс 1 */ * flag[1] = true;  while (flag[0])  {  flag[1] = false;  /* Задержка */  flag[1] = true;  }  /* Критический раздел */;  flag[1] = false;
(г)       Четвертая попытка