Процессам часто нужно взаимодействовать друг с другом. Например, один процесс может передавать данные другому процессу или несколько процессов могут обрабатывать данные из общего файла. Во всех этих случаях возникает проблема синхронизации процессов, которая может решаться приостановкой и активизацией процессов, организацией очередей, блокированием и освобождением ресурсов.
Пренебрежение вопросами синхронизации процессов, выполняю-щихся в режиме мультипрограммирования, может привести к их неправильной работе или даже к сбою работы ОС. Рассмотрим, например, программу печати заданий (рис. 2.2). Эта программа печатает по очереди все задания, имена которых последовательно в порядке поступления записываются в очередь заданий.
Особая переменная N, также доступная всем процессам-клиентам, содержит номер первой свободной позиции для задания в очереди. Процессы-клиенты читают эту переменную, записывают в соответствующую позицию очереди имя своего задания и наращивают значение N на единицу. Предположим, что в некоторый момент процесс A решил распечатать свой файл, для этого он прочитал значение переменной N, значение которой для определен-ности предположим равным 4. Процесс запомнил это значение, но поместить задание не успел, так как его выполнение было прервано (например, вследствие исчерпания кванта). Очередной процесс B, желающий послать задание на печать, прочитал то же самое значение переменной N, поместил в четвертую позицию свое задание и нарастил значение переменной на единицу.
Урок 23. Процесс в операционной системе
Когда в очередной раз управление будет передано процессу A, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итера-ции, запишет задание также в позицию 4, поверх задания процесса B.
Таким образом, процесс A никогда не увидит свое задание распечатанным. Сложность проблемы синхронизации состоит в нерегулярности возникающих ситуаций. В предыдущем примере можно представить и другое развитие событий: были потеряны задания
 |
Рис. 2.2. Пример необходимости синхронизации
нескольких процессов или, напротив, не было потеряно ни одного задания. В данном случае все определяется взаимными скоростями процессов и моментами их прерывания. Поэтому отладка взаимодей-ствующих процессов является сложной задачей. Ситуации подобные той, когда два или более процессов обрабатывают разделяемые данные, и конечный результат зависит от соотношения скоростей процессов, называются гонками.
Контрольный пример
Необходимо разработать программу, осуществляющую моделирова-ние режима работы с разделением времени между независимыми процессами.
#define dX 14 //ширина окна процесса
#define dY 4 //высота окна процесса
#define ID_COUNT 20 //количество процессов
#define TIME 0.01 //время выполнения процесса
Урок 33. Процессы и потоки в операционной системе
#define DELAY –6000 //задержка в тыс.операций для отключ.
/* массив координат окон для процессов */
/* массив статуса процессов: 0 – свободен, 1 – на выполнении */
typedef unsigned char BYTE ;
void ShowMenu(); //главное меню
void ShowCursor(); //показать курсор
void HideCursor(); //спрятать курсор
/* описание класса процесса */
int id; //номер процесса
BYTE x,y; //координаты окна процесса
long CountOperations; //кол-во операций процесса
TProcess *next; //указатель на следующий процесс
TProcess *prev; //указатель на предыд. процесс
int GetID(); //получить номер процесса
long GetTime(); //получить кол-во невыполн.операц.
void GetParams(); //задать параметры процесса
void ShowWND(); //показать окно процесса
void HideWND(); //спрятать окно процесса
void ActiveWND(); //активизировать окно процесса
int Time(); //выполнение процесса
/*метод получения количества невыполненных операций*/
/*метод выполнения процесса в течении кванта времени*/
cprintf(«%2d:%02d:%02d.%02d»,t.ti_hour, t.ti_min, t.ti_sec, t.ti_hund);
/*метод активизации окна выполнения процесса*/
/*метод удаления окна выполнения процесса с экрана*/
/*метод вывода окна выполнения процесса на экран*/
/*метод получения номера текущего процесса*/
/*метод создания нового процесса*/
cprintf(«Создание нового процесса # %d.»,id);
cprintf(» Количество операций (в тысячах) = «);
/*прототип функции задания процесса для удаления */
/*прототип функции очистки командеой строки*/
class TProcess * ptr1=NULL;
class TProcess * ptr2=NULL;
class TProcess * BPtr=NULL; //указатель на начало списка процессов
class TProcess * EPtr=NULL; //указатель на конец списка процессов
/* обработка процессов,пока не нажата любая клавиша */
if (!BPtr) continue;
if (ptr1==BPtr) BPtr=ptr1–>next;
if (ptr1==EPtr) EPtr=ptr1–>prev;
> // ожидание нажатия клавиши
/* обработка нажатия клавиши */
if (!key) key = getch();
case INS: //создание нового процесса
cprintf(«nnНевозможно создать новый процесс.Уже создано 20 процессов.»);
ptr1 = new TProcess;
cprintf(«nnОшибка выделения памяти для нового процесса.»);
if (!BPtr) BPtr=ptr1;
case DEL: //удаление процесса
if (ptr1==BPtr) BPtr=ptr1–>next;
if (ptr1==EPtr) EPtr=ptr1–>prev;
while(key!=ESC); //выход по нажатию Esc
//удаление всех процессов
/*функция получения номера процесса для удаления*/
TProcess * GetDelProcess(TProcess * BPtr)
TProcess *ptr, *ptrf=NULL;
cprintf(«Введите номер процесса для удаления : «);
cprintf(«Ощибка. Процесс #%d не найден.»,id);
/*вывод рабочего меню на экран*/
textcolor(4); cprintf(» INS»);
textcolor(0); cprintf(» – создать новый процесс «);
textcolor(4); cprintf(» DEL»);
textcolor(0); cprintf(» – удалить процесс «);
textcolor(4); cprintf(» ESC»);
textcolor(0); cprintf(» – выход из программы «);
/*функция гашения курсора*/
/*функция восстановления курсора*/
Разработанная программа позволяет пользователю создавать до двадцати выполняемых процессов (количество процессов ограничено в связи с использованием текстового режима 80*25 и невозможностью вместить большое число выполняемых процессов).
Программа реализована на языке Си и одинаково корректно работает в DOS и в DOS-сессии Windows [6].
Для создания процесса необходимо нажать клавишу INS, затем внизу экрана в командной строке (строка запроса) ввести количество операций в тысячах для процесса с указанным номером (рис. 2.3). После чего на экране возникнет новое окно – окно выполнения процесса, в котором выводится значение текущего времени и текущее количество операций для выполнения (рис. 2.4). Далее процесс автоматически заносится в список процессов для выполнения, имеющий кольцевидную (замкнутую) структуру.
Моделирование режима разделения времени заключается в том, что каждый процесс работает в течение короткого промежутка времени, затем управление передается следующему из списка процессу. Под работой процесса понимается вывод на экран в окне рабочего процесса значения текущего времени и текущего количества операций для выполнения.
Если процесс выполнил требуемое количество операций, то на эк-ране возникает надпись о его завершении «Complete …» и через малый промежуток времени окно процесса исчезает с экрана (рис. 2.4 и 2.5). При этом сам процесс удаляется из списка заданий. Для удаления процесса в произвольный момент времени необходимо нажать клавишу DEL и в строке запроса ввести номер процесса для удаления.
Если процесс с указанным номером будет найден, то он исчезнет с экрана и удалится из списка обрабатываемых процессов (рис. 2.6). Для выхода из программы необходимо воспользоваться клавишей ESC. После этого все процессы удаляются, и осуществляется завершение работы программы.
Рис. 2.3. Создание нового процесса
Рис. 2.4. Работа и завершение процессов
Рис. 2.5. Активные и завершенные процессы
Рис. 2.6. Запрос на удаление процесса
Лабораторная работа № 2
Цель работы: разработать программу, осуществляющую моделирование режима работы с разделение времени.
Результат: отчет о лабораторной работе и программа, моделирующая режим работы с разделением времени.
| Вариант 1 | Создание хаотичного режима передачи сообщений. Каждый процесс может отправлять сообщение любому из своих соседей и самому себе. Случайный способ выбора следующего |
| Вариант 2 | Одновременная работа нескольких внешних программ под управлением менеджера. Пользователь может запускать, закрывать, приостанавливать любой активный процесс |
| Вариант 3 | Одновременный опрос выбранных портов ПК. Синхронизация в режиме реального времени |
| Вариант 4 | Параллельная сортировка массивов. Передача управления осуществляется после перестановки значений. Первым завершается процесс, с меньшим количеством перестановок |
| Вариант 5 | Одновременный расчет результатов нескольких математических уравнений. При решении используются общие области оперативной памяти (переменные) |
| Вариант 6 | Вывод нескольких графических объектов. Скорость вращения объектов зависит от приоритета. Приоритет и положение объекта на экране должны задаваться пользователем |
| Вариант 7 | Работа с двумя и более одновременными независимыми операциями умножения матриц. Пользователь должен менять приоритет процессов во время работы |
| Вариант 8 | Работа нескольких параллельных процессов с одной внешней базой. Приоритет и ключи поиска у разных процессов – различны. База доступна только для чтения |
| Вариант 9 | Одновременный отсчет. Синхронизация по таймеру. От величины приоритета зависит уменьшение числа в течение одного интервала |
| Вариант 10 | Генерация нескольких движущихся объектов в пределах одного окна. При движении необходимо учитывать операции столкновения и отражения управляемых объектов |
3. РАБОТА С РАЗДЕЛЕННЫМИ ФАЙЛАМИ
НА УРОВНЕ ПРОЦЕССОВ
Важным понятием синхронизации процессов является понятие «критическая секция» программы. Критическая секция – это часть программы, в которой осуществляется доступ к разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением [12].
Системы, состоящие из нескольких процессов, часто легче программировать, используя так называемые критические секции. Когда процессу нужно читать или модифицировать некоторые разделяемые структуры данных, он прежде всего входит в критическую секцию для того, чтобы обеспечить себе исключительное право использования этих данных.
При этом он уверен, что никакой процесс не будет иметь доступа к этому ресурсу одновременно с ним. Это называется взаимным исключением. В однопроцессорных системах критические секции защищаются семафорами, мониторами и другими аналогичными конструкциями. Рассмотрим, какие алгоритмы могут быть использованы в распределенных системах.
Наиболее очевидный и простой путь реализации взаимного исключения в распределенных системах – это применение тех же методов, которые используются в однопроцессорных системах. Один из процессов выбирается в качестве координатора (например, процесс, выполняющийся на машине, имеющей наибольшее значение сетевого адреса).
Когда какой-либо процесс хочет войти в критическую секцию, он посылает сообщение с запросом к координатору, оповещая его о том, в какую критическую секцию он хочет войти, и ждет от координатора разрешение. Если в этот момент ни один из процессов не находится в критической секции, то координатор посылает ответ с разрешением. Если же некоторый процесс уже выполняет критическую секцию, связанную с данным ресурсом, то никакой ответ не посылается. Запрашивавший процесс ставится в очередь, и после освобождения критической секции ему отправляется ответ-разрешение. Этот алгоритм гарантирует взаимное исключение одновременного доступа в критическую секцию, но вследствие своей централизованной природы обладает низкой отказоустойчивостью.
Когда процесс хочет войти в критическую секцию, он формирует сообщение, содержащее имя нужной ему критической секции, номер процесса и текущее значение времени. Затем он посылает это сообщение всем другим процессам. Предполагается, что передача сообщения надежна, то есть получение каждого сообщения сопровождается подтверждением. Когда процесс получает сообщение такого рода, его действия зависят от того, в каком состоянии по отношению к указанной в сообщении критической секции он находится. Имеют место три ситуации:
1. Если получатель не находится и не собирается входить в критическую секцию в данный момент, то он отсылает назад процессу-отправителю сообщение с разрешением.
2. Если получатель уже находится в критической секции, то он не отправляет никакого ответа, а ставит запрос в очередь.
3. Если получатель хочет войти в критическую секцию, но еще не сделал этого, то он сравнивает временную отметку поступившего сообщения со значением времени, которое содержится в его собственном сообщении, разосланном всем другим процессам. Если время в поступившем к нему сообщении меньше, то есть его собственный запрос возник позже, то он посылает сообщение-разрешение, в обратном случае он не посылает ничего и ставит поступившее сообщение-запрос в очередь.
Процесс может войти в критическую секцию только в том случае, если он получил ответные сообщения-разрешения от всех остальных процессов. Когда процесс покидает критическую секцию, он посылает разрешение всем процессам из своей очереди и исключает их из очереди.
Контрольный пример
В ходе выполнения работы должна быть разработана программа, осуществляющая работу с разделенными файлами на уровне процессов.
Совместный доступ реализован следующим образом: осуществля-ется доступ к одному файлу несколькими процессами при их создании, а считанные данные записываются в другой файл при закрытии процессов.
При запуске программы происходит автоматическое создание текстового файла «RichEdit.txt», в который помещается общая для всех процессов информация для вывода. Далее при создании каждого нового процесса к данному файлу будет осуществляться обращение.
Каждый из процессов представляет собой независимое от других окно ввода данных, в котором изначально пишется номер процесса. При помощи кнопок-иконок в каждом окне можно задавать выравнивание текста, жирность и наклон шрифта, осуществлять работу с буфером обмена.
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Источник: studopedia.net
Критическая секция
Важным понятием синхронизации процессов является понятие «критическая секция» программы. Критическая секция — это часть программы, в которой осуществляется доступ к разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением.
Простейший способ обеспечить взаимное исключение — позволить процессу, находящемуся в критической секции, запрещать все прерывания. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены.
Рис. 2.4. Реализация критических секций с использованием блокирующих переменных
Другим способом является использование блокирующих переменных. С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На рисунке 2.4 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к разделяемому ресурсу D блокирующую переменную F(D). Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной F(D) устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.
Если все процессы написаны с использованием вышеописанных соглашений, то взаимное исключение гарантируется. Следует заметить, что операция проверки и установки блокирующей переменной должна быть неделимой. Поясним это. Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван.
За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом был нарушен принцип взаимного исключения, что потенциально может привести к нежелаемым последствиям. Во избежание таких ситуаций в системе команд машины желательно иметь единую команду «проверка-установка», или же реализовывать системными средствами соответствующие программные примитивы, которые бы запрещали прерывания на протяжении всей операции проверки и установки.
Реализация критических секций с использованием блокирующих переменных имеет существенный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время. Для устранения таких ситуаций может быть использован так называемый аппарат событий.
С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x — идентификатор некоторого события. На рисунке 2.5 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.
Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:
V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.
P(S): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.
Рис. 2.5. Реализация критической секции с использованием системных
функций WAIT(D) и POST(D)
В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).
Нити
Многозадачность является важнейшим свойством ОС. Для поддержки этого свойства ОС определяет и оформляет для себя те внутренние единицы работы, между которыми и будет разделяться процессор и другие ресурсы компьютера. Эти внутренние единицы работы в разных ОС носят разные названия — задача, задание, процесс, нить. В некоторых случаях сущности, обозначаемые этими понятиями, принципиально отличаются друг от друга.
Говоря о процессах, мы отмечали, что операционная система поддерживает их обособленность: у каждого процесса имеется свое виртуальное адресное пространство, каждому процессу назначаются свои ресурсы — файлы, окна, семафоры и т.д. Такая обособленность нужна для того, чтобы защитить один процесс от другого, поскольку они, совместно используя все ресурсы машины, конкурируют с друг другом. В общем случае процессы принадлежат разным пользователям, разделяющим один компьютер, и ОС берет на себя роль арбитра в спорах процессов за ресурсы.
При мультипрограммировании повышается пропускная способность системы, но отдельный процесс никогда не может быть выполнен быстрее, чем если бы он выполнялся в однопрограммном режиме (всякое разделение ресурсов замедляет работу одного из участников за счет дополнительных затрат времени на ожидание освобождения ресурса). Однако задача, решаемая в рамках одного процесса, может обладать внутренним параллелизмом, который в принципе позволяет ускорить ее решение. Например, в ходе выполнения задачи происходит обращение к внешнему устройству, и на время этой операции можно не блокировать полностью выполнение процесса, а продолжить вычисления по другой «ветви» процесса.
Для этих целей современные ОС предлагают использовать сравнительно новый механизм многонитевой обработки (multithreading). При этом вводится новое понятие «нить» (thread), а понятие «процесс» в значительной степени меняет смысл.
Мультипрограммирование теперь реализуется на уровне нитей, и задача, оформленная в виде нескольких нитей в рамках одного процесса, может быть выполнена быстрее за счет псевдопараллельного (или параллельного в мультипроцессорной системе) выполнения ее отдельных частей. Например, если электронная таблица была разработана с учетом возможностей многонитевой обработки, то пользователь может запросить пересчет своего рабочего листа и одновременно продолжать заполнять таблицу. Особенно эффективно можно использовать многонитевость для выполнения распределенных приложений, например, многонитевый сервер может параллельно выполнять запросы сразу нескольких клиентов.
Нити, относящиеся к одному процессу, не настолько изолированы друг от друга, как процессы в традиционной многозадачной системе, между ними легко организовать тесное взаимодействие. Действительно, в отличие от процессов, которые принадлежат разным, вообще говоря, конкурирующим приложениям, все нити одного процесса всегда принадлежат одному приложению, поэтому программист, пишущий это приложение, может заранее продумать работу множества нитей процесса таким образом, чтобы они могли взаимодействовать, а не бороться за ресурсы.
В традиционных ОС понятие «нить» тождественно понятию «процесс». В действительности часто бывает желательно иметь несколько нитей, разделяющих единое адресное пространство, но выполняющихся квазипараллельно, благодаря чему нити становятся подобными процессам (за исключением разделяемого адресного пространства).
Нити иногда называют облегченными процессами или мини-процессами. Действительно, нити во многих отношениях подобны процессам. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние.
Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находится в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования.
Однако различные нити в рамках одного процесса не настолько независимы, как отдельные процессы. Все такие нити имеют одно и то же адресное пространство. Это означает, что они разделяют одни и те же глобальные переменные. Поскольку каждая нить может иметь доступ к каждому виртуальному адресу, одна нить может использовать стек другой нити.
Между нитями нет полной защиты, потому что, во-первых, это невозможно, а во-вторых, не нужно. Все нити одного процесса всегда решают общую задачу одного пользователя, и аппарат нитей используется здесь для более быстрого решения задачи путем ее распараллеливания. При этом программисту очень важно получить в свое распоряжения удобные средства организации взаимодействия частей одной задачи. Кроме разделения адресного пространства, все нити разделяют также набор открытых файлов, таймеров, сигналов и т.п.
Итак, нити имеют собственные:
- программный счетчик,
- стек,
- регистры,
- нити-потомки,
- состояние.
- адресное пространство,
- глобальные переменные,
- открытые файлы,
- таймеры,
- семафоры,
- статистическую информацию.
Многонитевая обработка повышает эффективность работы системы по сравнению с многозадачной обработкой. Например, в многозадачной среде Windows можно одновременно работать с электронной таблицей и текстовым редактором. Однако, если пользователь запрашивает пересчет своего рабочего листа, электронная таблица блокируется до тех пор, пока эта операция не завершится, что может потребовать значительного времени. В многонитевой среде в случае, если электронная таблица была разработана с учетом возможностей многонитевой обработки, предоставляемых программисту, этой проблемы не возникает, и пользователь всегда имеет доступ к электронной таблице.
Широкое применение находит многонитевая обработка в распределенных системах. Смотрите об этом в разделе «Процессы и нити в распределенных системах».
Некоторые прикладные задачи легче программировать, используя параллелизм, например задачи типа «писатель-читатель», в которых одна нить выполняет запись в буфер, а другая считывает записи из него. Поскольку они разделяют общий буфер, не стоит их делать отдельными процессами.
Другой пример использования нитей — это управление сигналами, такими как прерывание с клавиатуры (del или break). Вместо обработки сигнала прерывания, одна нить назначается для постоянного ожидания поступления сигналов. Таким образом, использование нитей может сократить необходимость в прерываниях пользовательского уровня. В этих примерах не столь важно параллельное выполнение, сколь важна ясность программы.
Наконец, в мультипроцессорных системах для нитей из одного адресного пространства имеется возможность выполняться параллельно на разных процессорах. Это действительно один из главных путей реализации разделения ресурсов в таких системах. С другой стороны, правильно сконструированные программы, которые используют нити, должны работать одинаково хорошо как на однопроцессорной машине в режиме разделения времени между нитями, так и на настоящем мультипроцессоре.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник: studopedia.ru
Синхронизация процессов в ОС
Процессам часто нужно взаимодействовать друг с другом с целью совместного использования аппаратных и информационных ресурсов вычислительной системы, например, один процесс может передавать данные другому процессу, или несколько процессов могут обрабатывать данные из общего файла.
Процессы в общем случае протекают независимо, асинхронно друг другу.Одной из функций ОС явялется обеспечение санкционированного взаимодействия процессов.
Взаимодействие процессв в вычислительной системе напоминает жизнь в коммунальной квартире. Постоянное ожидание в очереде к местам общего пользования (процессору) и ежедневная борьба за ресуосы (кто опять занял все конфорки на плите?)
Для нормального функционирования процессов ОС старается максимально обособить их друг от друга. Каждый процесс имеет собственное адресное пространство (каждая семья должна жить в отдельной комнате), нарушение которого, как правило, приводит к аварийной остановке процесса(вызов милиции). Каждому процессу по возможности предоставляются свои дополнительные ресурсы (каждая семья предпочитает иметь собственный холодильник). Тем не менее для решения некотопых задач (приготовление праздничного стола на всю кваритиру) процессы могут объединять свои усилия.
Существуют в основном две проблемы взаимодействия процессов, это:
— «конкуренция» процессов в борьбе за ресурсы;
— «сотрудничество» с использованием разделяемых переменных, совместно используемых данных или баз данных.
Для исключения проблем при обмене данными между процессами, разделении данных, при доступе к процессору и устройствам ввода-вывода необходима синхронизация.
Любое взаимодействие процессов связано с их синхронизацией, которая заключается в согласовании их скоростей путем приостановки процесса до наступления некоторого события и последующей его активизации при наступлении этого события.
Синхронизация лежит в основе любого взаимодействия процессов, связано ли это взаимодействие с разделением ресурсов или с обменом данными. Например(синхронизация по информации), поток-получатель должен обращаться за данными только после того, как они помещены в буфер потоком-отправителем. Если же поток-получатель обратился к данным до момента их поступления в буфер, то он должен быть приостановлен.
Например(синхронизация при совместном использовании аппаратных ресурсов), активному потоку требуется доступ к последовательному порту, а с этим портом в монопольном режиме работает другой поток, находящийся в данный момент в состоянии ожидания, то ОС приостанавливает активный поток и не активизирует его до тех пор, пока нужный ему порт не освободится.
Часто нужна также синхронизация с событиями, внешними по отношению к вычислительной системе, например реакции на нажатие комбинации клавиш .
Ежесекундно в ВС происходит сотни событий, связанных с распределением и освобождение ресурсов. Поэтому ОС должна иметь надежные и производительные средства, позволяющие ей синхронизировать процессы с происходящими в системе событиями.
Во многих ОС эти средства называются средствами межпроцессного взаимодействия — Inter Process Communication (IРС). Обычно к средствам IРС относят не только средства межпроцессной синхронизации, но и средства межпроцессного обмена данными.
Выполнение процесса в мультипрограммной среде всегда имеет асинхронный характер. Очень сложно с полной определенностью сказать, на каком этапе выполнения будет находиться процесс в определенный момент времени. Даже в однопрограммном режиме не всегда можно точно оценить время выполнения задачи. Так как исходные данные в разные моменты запуска задачи могут быть разными, то и время выполнения отдельных этапов и задачи в целом является весьма неопределенной величиной.
Еще более неопределенным является время выполнения программы в мультипрограммной системе. Моменты прерывания потоков, время нахождения их в очередях к разделяемым ресурсам, порядок выбора потоков для выполнения — все эти события являются результатом стечения многих обстоятельств и могут быть интерпретированы как случайные. В лучшем случае можно оценить вероятностные
Возникновение гонок при доступе к разделяемым данным
характеристики вычислительного процесса, например вероятность его завершения за данный период времени.
Пренебрежение вопросами синхронизации процессов, выполняющихся в режиме мультипрограммирования, может привести к их неправильной работе или даже к краху системы: гонки и блокировки(тупики).
Ситуации, когда два или более процесса обрабатывают разделяемые данные и конечный результат зависит от соотношения скоростей процессов, называются гонками.
 |
Рассмотрим, например, задачу ведения базы данных клиентов некоторого предприятия.
Каждому клиенту в базе данных отводится отдельная запись, в которой среди прочих полей имеются поля Заказ и Оплата. Программа, ведущая базу данных, оформлена как единый процесс, имеющий несколько потоков, в том числе:
-поток А заносит в базу данных информацию о заказах, поступивших от клиентов, и
-поток В фиксирует в базе данных сведения об оплате клиентами выставленных счетов.
Оба эти потока совместно работают над общим файлом базы данных, используя однотипные алгоритмы, включающие три шага:
1. Считать из файла базы данных в буфер запись о клиенте с заданным иденти-фикатором.
2. Внести новое значение в поле Заказ (для потока А) или Оплата (для потока В).
3. Вернуть модифицированную запись в файл базы данных.
Обозначим соответствующие шаги для потока А как А1, А2 и А3, а для потока В как В1, В2 и В3.
Предположим, что в некоторый момент поток А обновляет поле Заказ записи о клиенте N. Для этого он считывает эту запись в свой буфер (шаг А1), модифицирует значение поля Заказ (шаг А2), но внести запись в базу данных (шаг А3) не успевает, так как его выполнение прерывается, например, вследствие завершения кванта времени.
Предположим также, что потоку В потребовалось внести сведения об оплате относительно того же клиента N. Когда подходит очередь потока В, он успевает считать запись в свой буфер (шаг В1) и выполнить обновление поля Оплата (шаг В2), а затем прерывается. В буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение.
Когда в очередной раз управление будет передано потоку А, то он, продолжая свою работу, сохранит запись о клиенте N с модифицированным полем Заказ в базу данных (шаг А3). После прерывания потока А и активизации потока В последний запишет в базу данных поверх только что обновленной записи о клиенте N свой вариант записи, в которой обновлено значение поля Оплата. Таким образом, в базе данных будут зафиксированы сведения о том, что клиент N произвел оплату, но информация о его заказе окажется потерянной.
Сложность проблемы синхронизации состоит в нерегулярности возникающих ситуаций.
В предыдущем примере можно представить и другое развитие событий: могла быть потеряна информация не о заказе, а об оплате, или, напротив, все исправления были успешно внесены. В данном случае все определяется взаимными скоростями процессов и моментами их прерывания. Поэтому отладка взаимодействующих процессов является сложной задачей.
Проблема гонок может решаться:
1) приостановкой и активизацией процессов,
2) организацией очередей,
3) блокированием и освобождением ресурсов.
Предположим, что несколько процессов конкурируют за обладание конечным числом ресурсов. Если запрашиваемый процессом ресурс недоступен, ОС переводит данный процесс в состояние ожидания. В случае, когда требуемый ресурс удерживается другим ожидающим процессом, первый процесс не сможет сменить свое состояние. Такая ситуация называется тупиком (deadlock).
Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация, или «зависание системы», является следствием того, что один или более процессов находятся в состоянии тупика. Иногда подобные ситуации называют взаимоблокировками.
Пусть например, имеются два процесса Р1 и Р2 и два ресурса- R1, R2. Предположим, что каждому процессу для выполнения части своих функций требуется доступ к общим ресурсам. Тогда возможно возникновение следующей ситуации:ОС выделяет ресурс R1 процессу Р2, а ресурс R2 – процессу Р1. В результате каждый процесс ожидает получения одного из двух ресурсов.
При этом ни один из них не освобождает уже имеющийся ресурс, ожидая получения второго ресурса для выполнения функций, требующих наличия двух ресурсов. В результате процессы оказываются взаимно заблокированными.
Очень удобно моделировать условия возникновения ткпиков, используя напрвленные графы. Графы имеют 2 вида узлов:процессы – кружочки, ресурсы – квадратики.
Ребро, направленное от квадрата (ресурса) к кружку (процессу), означает, что ресурс был запрошен, получен и используется. В нашем примере будем иметь
Исходное распределение ресурсов
Ребро, направленное от процесса (кружка) к ресурсу (квадрату), означает, что процесс в данный момент заблокирован и находится в состоянии ожидания доступа к этому ресурсу.
В нашем случае получим следующий граф
Цикл в графе означает наличие взаимной блокировки процессов.
В общем случае проблема тупиков эффективного решения не имеет.
Рассмотрим пример аппаратного тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, диск и последовательный порт. На следующем рисунке показаны фрагменты соответствующих программ.
Возникновение взаимных блокировок при выполнении программы
Процесс А запрашивает сначала порт, а затем диск, а процесс В запрашивает эти устройства в обратном порядке. И пусть после того, как процесс А занял порт, он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как порт оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован, т.к. диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.
В зависимости от соотношения скоростей процессов, они могут либо взаимно блокировать друг друга (б), либо образовывать очереди к разделяемым ресурсам (в), либо совершенно независимо использовать разделяемые ресурсы (г).
Тупиковые ситуации отличаются от простых очередей, хотя и те и другие возникают при совместном использовании ресурсов и внешне выглядят похоже: процесс приостанавливается и ждет освобождения ресурса.
Очередь — это нормальное явление, неотъемлемый признак высокого коэффициента использования ресурсов при случайном поступлении запросов. Она возникает тогда, когда ресурс недоступен в данный момент, но через некоторое время он освободится, и процесс продолжает свое выполнение. Тупик же является в некотором роде неразрешимой ситуацией.
В рассмотренных примерах тупик был образован двумя процессами, но взаимно блокировать друг друга могут и большее число процессов.
Определение. Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое может вызвать только другой процесс данного множества.
Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.
1. Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.
2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.
3. Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобожден он может только процессом, который их удерживает.
4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.
Для образования тупика необходимым и достаточным является выполнение всех четырех условий.
Основные направления борьбы с тупиками:
— игнорирование данной проблемы;
— распознавание тупиков и восстановление системы после тупиков.
Важным понятием синхронизации процессов является понятие «критической секции«программы.
Критическая секция — это часть программы, в которой осуществляется доступ к разделяемым ресурсам. Критическая секция всегда определяется по отношению к определенным критическим данным, при несогласованном изменении которых могут возникнуть нежелательные эффекты. В нашем примере такими критическими данными являлись записи файла базы данных.
Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находилось не более одного процесса. Этот прием называют взаимным исключением. Простейший способ обеспечить взаимное исключение — позволить процессу, находящемуся в критической секции, запрещать все прерывания на время его нахождения в критической секции. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены.ОС использует разные способы взаимного исключения:
— антидедлоки и т.д.
Вопрос 18.
Критическая секция — это часть программы, в которой осуществляется доступ к разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением.
Простейший способ обеспечить взаимное исключение — позволить процессу, находящемуся в критической секции, запрещать все прерывания. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены.
Вопрос 20.
Алгоритм Петерсона
Первое решение проблемы, удовлетворяющее всем требованиям и использующее идеи ранее рассмотренных алгоритмов, было предложено датским математиком Деккером (Dekker). В 1981 году Петерсон (Peterson) предложил более изящное решение. Пусть оба процесса имеют доступ к массиву флагов готовности и к переменной очередности.
shared int ready[2] = ;
shared int turn;
while (some condition)
При исполнении пролога критической секции процесс Pi заявляет о своей готовности выполнить критический участок и одновременно предлагает другому процессу приступить к его выполнению. Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу. При этом одно из предложений всегда следует после другого. Тем самым работу в критическом участке продолжит процесс, которому было сделано последнее предложение.
Давайте докажем, что все пять наших требований к алгоритму действительно удовлетворяются.
Удовлетворение требований 1 и 2 очевидно.
Докажем выполнение условия взаимоисключения методом от противного. Пусть оба процесса одновременно оказались внутри своих критических секций.
Заметим, что процесс Pi может войти в критическую секцию, только если ready[1-i] == 0 или turn == i. Заметим также, что если оба процесса выполняют свои критические секции одновременно, то значения флагов готовности для обоих процессов совпадают и равны 1. Могли ли оба процесса войти в критические секции из состояния, когда они оба одновременно находились в процессе выполнения цикла while? Нет, так как в этом случае переменная turn должна была бы одновременно иметь значения 0 и 1 (когда оба процесса выполняют цикл, значения переменных измениться не могут).
Пусть процесс P0 первым вошел в критический участок, тогда процесс P1 должен был выполнить перед вхождением в цикл while по крайней мере один предваряющий оператор (turn = 0;). Однако после этого он не может выйти из цикла до окончания критического участка процесса P0, так как при входе в цикл ready[0] == 1 и turn == 0, и эти значения не могут измениться до тех пор, пока процесс P0 не покинет свой критический участок. Мы пришли к противоречию. Следовательно, имеет место взаимоисключение.
Докажем выполнение условия прогресса. Возьмем, без ограничения общности, процесс P0. Заметим, что он не может войти в свою критическую секцию только при совместном выполнении условий ready[1] == 1 и turn == 1. Если процесс P1 не готов к выполнению критического участка, то ready[1] == 0, и процесс P0 может осуществить вход.
Если процесс P1готов к выполнению критического участка, то ready[1] == 1 и переменная turn имеет значение 0 либо 1, позволяя процессу P0 либо процессу P1 начать выполнение критической секции. Если процесс P1 завершил выполнение критического участка, то он сбросит свой флаг готовности ready[1] == 0, разрешая процессу P0 приступить к выполнению критической работы. Таким образом, условие прогресса выполняется.
Отсюда же вытекает выполнение условия ограниченного ожидания. Так как в процессе ожидания разрешения на вход процесс P0 не изменяет значения переменных, он сможет начать исполнение своего критического участка после не более чем одного прохода по критической секции процесса P1.
Источник: infopedia.su