Критическая область и синхронизация

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

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

а) b) c) d)

Рис. 5.2. Типы отношения предшествования: a) − последовательное; b) − параллельное; c) − последовательно-параллельное; d)− общий случай (S − начало; F − конец)

Пусть S (a,b) обозначает последовательную связь процесса a) с процессом b), и пусть Р (a,b) обозначает параллельную связь процессов a) и b).Тогда граф развития процесса является правильно вложенным, если он может быть описан функциями S и Р или только композицией этих функций. Это свойство очень похоже на свойство «правильной вложенности» блочной структуры в языках программирования и скобок в выражениях. Первые три графа на рисунке могут быть описаны так:

S (P ₁, S (P ₂, S (P ₃, P ₄))),

P (P ₁, P (P ₂, P (P ₃, P ₄))),

S (P ₁, S (P (P ₂, P (S (P ₃, P (P ₄, P ₅)) P ₆)), P (P ₇, P ₈))).

Общий граф предшествования d на рисунке не является правильно вложенным. Покажем это: любое описание, сделанное с помощью функциональной композиции, должно включать на самом внутреннем уровне выражение или в форме S (P_i,P_j) или P (P_i,P_j) для P_i,P_j € { P_k/ k= 1 ,…, 8}. Связь P (P_i,P_j) не может появиться, поскольку граф d не содержит ни одного подграфа в этой форме. Все последовательно связанные P_i и P_j имеют, по крайней мере, еще один процесс P_k, который начинается или заканчивается в вершине ij, скажем между P_i и P_j, но ij становится недоступной для дальнейшего использования, если появляется S (P_i,P_j), т.к. тогда связь P_k не может быть описана. Следовательно, S (P_i,P_j) также не может быть использована, и описание правильно вложенного графа невозможно.

Последовательный процесс (иногда называемый «задача») есть работа, производимая последовательным процессором при выполнении программы с ее данными. С логической точки зрения каждый процесс имеет свой собственный процессор и программу. Два различных процесса могут разделять одну и ту же программу или один и тот же процессор. Развитие процесса можно описать как последовательность векторов состояния S ₀, S ₁,…, S_i, где каждый вектор состояния S_i содержит указатель на следующую программную команду, которую нужно выполнить, а также значения всех промежуточных и определяемых в программе переменных.

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

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

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

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

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

Рассмотрим два процесса Р 1 и Р 2, увеличивающих асинхронно значение общей переменной Х, представляющей число единиц ресурса:

Р 1:….. Х:≠ Х +1;…,

Р 1:….. Х:= Х +1;….

Пусть С 1 и С 2 – центральные процессоры с внутренними регистрами R 1 и R 2 соответственно и разделяемой общей памятью. Если бы Р 1 выполнялся на С 1, а Р 2 – на С 2, то могла бы возникнуть одна из двух последовательностей исполнения процессов во времени:

1) Р 1: R 1= Х; R 1= R 1+1; Х:= R 1; …

Р 2:……..; R 2= Х; R 2= R 2+1; Х:= R 2 …

……….. …………

t ₀ à time t_n

2) Р 1: R 1:= Х; R 1= R 1+1; Х:= R 1; …

Р 2:……..; R 2: Х; R 2:= R 2+1; Х = R 2 …

Предположим, что Х содержит значение δв момент t ₀. В момент t_n переменная Х содержала бы δ + 1, если бы исполнение на процессорах С 1 и С 2 следовало бы согласно 1) и содержала бы δ + 2 по 2). Оба значения Х могли быть реализованы также, если бы Р 1 и Р 2 разделяли во времени один процессор с переключением управления между процессами механизма прерывания. Правильность решения заключается в разрешении входить в любой момент времени в некоторую определенную область, называемую «критической» (critical section – CS), только одному процессу.

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

а) процесс, нормально работающий вне своей CS, не может блокировать другой процесс при вхождении этого (другого) в свою CS;

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

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

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

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

В 1965 г. Э. Дейкстра (Dijkstra E.W.) предложил механизм синхронизации, позволяющий выполнять над семафором Q следующие операции.

1). Операция Р (Q). Р -операция является операцией с одним аргументом-семафором, которая уменьшает его величину на 1, если Q> 0. Р -операция является неделимой, т.е. определение возможности уменьшения Q и последующее его уменьшение должны рассматриваться как неделимая операция. Р (Q) представляет собой операцию задержки, т.е. если процесс P₁ должен выполнить операцию Р(Q) над семафором Q =0, то операция Р (Q) не может завершиться до тех пор, пока какой-то процесс P_j не выполнит над QV операцию. Если некоторые процессы P ₁, P ₂ ,...,P_k одновременно начинают Р -операцию над Q,то Q изменит свое значение лишь тогда, когда завершится одна из начавшихся Р -операций.

2). Операция V(Q). V -операция является операцией с одним аргументом-семафором, которая увеличивает значение аргумента на 1. V -операция подобно Р -операции является неделимой.

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

Тупики

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

Рис. 5.3

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

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

а) процесс P 1 запрашивает ресурс типа R 1; стрелка от P 1 доходит только до большого кружка, что означает, что в текущий момент запрос от процесса на выделение данного ресурса находится в стадии рассмотрения; б) ресурс типа R 2 выделяется процессу P 2 (стрелка от маленького кружка, находящегося внутри большого кружка R 2, до квадрата P 2); в) процесс Р 3 запрашивает ресурс R 3, который выделен процессу P 4; ситуация приближается к потенциальному тупику; г) классическая тупиковая ситуация; процессу P 5 выделен ресурс R 5, необходимый процессу P 6, которому выделен ресурс R 4, необходимый процессу P 5 («круговое ожидание»).

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

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

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

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

Рис. 5.4. Редукция графа

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

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

Разработчиками операционных систем были сформулированы следующие необходимые условия наличия тупика:

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

− процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (условие ожидания ресурсов);

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

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

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

В проблеме тупиков можно выделить четыре основных направления:

− предотвращение тупиков;

− обход тупиков;

− обнаружение тупиков;

− восстановление после тупиков.

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

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

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

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

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

Для предотвращения тупиков в 1969 г. одним из сотрудников фирмы IBM J. W. Havender было предложено 3 стратегических принципа.

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

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

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

Сложность восстановления системы после тупиковой ситуации обусловливается рядом факторов:

- неочевидность того, что система попала в тупиковую ситуацию;

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

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

- вывод системы из тупиковой ситуации предполагает большой объем дополнительной работы.

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

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

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

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

1. Понятие архитектуры иерархической операционной системы.

2. Определение процесса в иерархической операционной системе.

3. Определение операции в операционной системе.

4. Понятие планирования в иерархии уровней ОС.

5. Структура планировщика.

6. Механизм планирования.

7. Основные блоки операционной системы.

8. Эффективность, показатель эффективности, определение оптимальной системы.

9. Понятие критической области.

10. Типы отношения предшествования.

11. Семафор, операции синхронизации.

12. Понятие тупика.

13. Необходимые условия наличия тупика.

14. Основные направления решения проблемы тупиков.