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

Состояние системы определяется действиями, производимыми процессами, которые могут затребовать, захватить и освободить ресурсы. Под ресурсом системы в общем случае понимается и ЦП (центральный процессор). При минимальном аппаратном параллелизме часто полезной абстракцией является рассмотрение процессов как процессов, протекающих параллельно. Тогда, если система имеет одну конечную точку, то типы отношения предшествования, которые возможны между процессами, можно представить следующим образом(рис. 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 -операций используют и другие операции над семафорами. Такие операции в силу своей неделимости позволяют блокировать или активизировать процессы при освобождении или запросах ресурсов любого типа (памяти, процессоров, устройств ввода-вывода и т.д.).

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