Критическая секция. Взаимоисключение

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

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

Рассмотрим примеры.

1. Пусть два потока p₁ и p₂ асинхронно увеличивают значение общей целочисленной переменной x, которая представляет количество общих единиц ресурса:

p₁:...; x:=x+1;...;...

p₂:...; x:=x+1;...;...

Если потоки выполняются на разных процессорах C₁ и C₂, имеющих внутренние регистры R₁ и R₂ и разделяемую основную память, то может возникнуть любая из следующих двух последовательностей:

(1) p₁: R₁:=x; R₁:=R₁+1; x:=R₁;...

p₂:...; R₂:=x; R₂:=R₂+1; x:=R₂;...

t₀ t₁
(2) p₁: R₁:=x; R₁:=R₁+1; x:=R₁;...

p₂:...; R₂:=x; R₂:=R₂+1; x:=R₂;...

Пусть x содержит значение V в момент времени t₀. Тогда, если выполнение потоков p₁ и p₂ происходит, как в последовательности (1), то в момент t₁ переменная x содержит значение V+1, если же – как в последовательности (2), то переменная x содержит значение V+2. Точно такие же результаты были бы получены, если бы потоки p₁ и p₁ разделяли во времени единственный процессор с переключением управления между потоками посредством прерываний. В этом примере проиллюстрирован эффект гонок.

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

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

§ Внести новое значение в поле заказ (для потока 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) Программа может останавливаться вне критической секции (КС).

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

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

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

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

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