Глава 7. Программирование с использованием мьютексов. Управление конкуренцией.

Содержание:

  • Пора позаботиться о стиле.
  • Тупик из-за упорядочения мьютексов.
  • Избавляемся от зацикливания потоков путем ожидания.
  • Избавляемся от зацикливания, устанавливая упорядочение захвата мьютексов.
  • Из огня да в полымя!
  • Избавляемся от зацикливания "ленивым способом", давая Win32 сделать это за нас.
  • Атомарность составных операций - управление конкуренцией оптимистическим и пессимистическим образом.
  • Оптимистическое управление.
  • Пессимистическое управление.
  • Избавляемся от недостатков в схеме блокировки.
  • Еще не все ясно? Можно и попроще!


Пора позаботиться о стиле?

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

Тупик из-за упорядочения мьютексов.

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

--Resize_Images_Alt_Text--

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

--Resize_Images_Alt_Text--

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

Избавляемся от зацикливания потоков путем ожидания.

Функции Win32, работающие с мьютексами, не требуют, чтобы поток вечно ждал воэможности захвата объекта мьютекса. Функция WaitForSingleObject позволяет определить время, в течение которого поток будет ждать. По его истечении поток будет разблокирован, и функция вернет код ошибки, показывающий, что время ожидания вышло. При использовании мьютексов для обеспечения доступа к критическому участку кода обычно не предполагается, что потоку придется ждать очень долго, так что установка периода ожидания (time-out) в пределах нескольких секунд вполне разумна. Если ваш поток использует этот метод, то он должен, конечно, правильно обрабатывать ошибки, например, повтором попытки или отказом от действия. При использовании критической секции такой возможности нет, так как функции ожидания критической секций ждут бесконечно.

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

Хотя возможность справиться с проблемами приобретения мьютекса и есть, лучше все-таки заранее гарантировать, чтобы тупиковые ситуации вообще не возникли. Поскольку такое зацикливание вызвано циклическими зависимостями, оно может быть устранено насильным упорядоченим приобретения мьютексов. Это упорядочение очень просто. Пусть у нас есть программа с мьютексами M1, M2, M3, ... Mn, где одним или несколькими мьютексами могут владеть потоки программы.

  • Зацикливание не произойдет, если потоки, которые пытаются захватить некоторый мьютекс Mx, в этот момент не владеют никакими мьютексами "более высокого приоритета", т.е., M(x+1) ... Mn.

Звучит несколько абстрактно? Рассмотрим простой конкретный пример. В этой части данной главы я упоминаю "блокировку" и "разблокирование" объектов. Эта терминология вполне уместна, когда мьютекс связан с куском данных, и требуется атомарный доступ к этим данным. Следует отметить, что это также означает, что каждый поток, получает доступ (захватывает) мьютекс до доступа к объекту, и освобождает мьютекс после операций с ним: такие действия уже обсуждались ранее, отличие только в терминах, которые более подходят в случае объектно-ориентированной (OO) модели. В этом смысле Object.Lock можно рассматривать как эквивалент EnterCriticalSection(Object.CriticalSection) или, возможно, WaitForSingleObject(Object.Mutex,INFINITE)

.

--Resize_Images_Alt_Text--

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

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

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

Выделить всёРазвернуть кодкод Pascal/Delphi
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
function Read(L: TList; Index: integer): integer;
begin
  if (Index > 0) and (L.Count > Index) then
  begin
    with L.Items[Index] do
    begin
      Lock;
      Result := Value;
      Unlock;
    end;
  end
  else
    raise ENotFound;
end;
 
procedure Write(L: TList; Index: integer; NewVal: integer);
begin
  if (Index > 0) and (L.Count > Index) then
  begin
    with L.Items[Index] do
    begin
      Lock;
      Value := NewVal;
      Unlock;
    end;
  end
  else
    raise ENotFound;
end;
 
function Compare(L: TList; Ind1, Ind2: integer): integer;
begin
  if (Ind1 > 0) and (Ind2 > 0) and (L.Count > Ind1) and (L.Count > Ind2) then
  begin
    L.Items[Ind1].Lock;
    L.Items[Ind2}.Lock;
    Result := L.Items[Ind2].Value - L.Items[Ind1].Value;
    L.Items[Ind2].Unlock;
    L.Items[Ind1].Unlock;
  end
  else
    raise ENotFound;
end;


Представим момент, в который потоку нужно сравнить элементы списка X и Y. Если поток всегда блокирует X, а потом Y, то может возникнуть зацикливание, если одному потоку нужно сравнивать элементы 1 и 2, а другому потоку - сравнивать 2 и 1. Одно из простых решений состоит в том, чтобы всегда блокировать сначала элемент с меньшим номером, или сортировать входные индексы, осуществлять блокировку, и правильно получать результаты сравнения. Однако более интересная ситуация создается, если объект содержит информацию о другом объекте, с которым требуется сравнение. В этом случае поток может блокировать первый объект, получить индекс второго объекта в списке, найти, что он располагается в списке ниже, блокировать его, и затем произвести сравнение. Все очень легко. Проблема возникает, когда второй объект находится в списке выше первого. Мы не можем блокировать его немедленно, так как это приведет к тупику. Теперь нам придется разблокировать первый объект, блокировать второй, и затем снова блокировать первый объект. Вот так удастся избежать тупика. Вот пример процедуры косвенного сравнения, представляющей данный подход

Выделить всёкод Pascal/Delphi
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
function CompareIndirect(L: TList; Ind1: integer): integer;
var
  Ind2: integer;
 
begin
  if (Ind1 > 0) and (L.Count > Ind1) then
  begin
    L.Items[Ind1].Lock;
    Ind2 := L.Items[Ind1];
    Assert(Ind2 <> Ind1); {I'm not even going to consider this nasty case in any more detail!}
    if Ind2 > Ind1 then
      L.Items[Ind2].Lock
    else
    begin
      L.Items[Ind1].Unlock;
      L.Items[Ind2].Lock;
      L.Items[Ind1].Lock;
    end;
    Result := L.Items[Ind2].Value - L.Items[Ind1].Value;
    L.Items[Ind1].Unlock;
    L.Items[Ind2].Unlock;
  end
  else
    raise ENotFound;
end;



Из огня да в полымя!

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

Избавляемся от зацикливания "ленивым способом", давая Win32 сделать это за нас.

Зная, что могут появиться такие проблемы, разработчики операционных систем Microsoft предусмотрели еще один путь их решения через другую функцию синхронизации Win32: WaitForMultipleObjects(Ex). Эта функция позволяет программисту ожидать и захватывать многочисленные объекты синхронизации (включая мьютексы) одновременно. В частности, она позволяет потоку ожидать, пока один или все из набора объектов не будут свободны (signalled) (в случае мьютексов - у них не будет владельцев), и тогда захватить объекты. Большое преимущество этого способа состоит в том, что если два потока ожидают мьютексы A и B, то не имеет значения порядок, в котором они идут в наборе объектов, подлежащих ожиданию, и либо ни один из объектов не будут захвачен, либо все они будут захвачены атомарно, так что зацикливание становится невозможным.
У этого метод также имеется несколько недостатков. Первый недостаток в том, что поскольку все объекты синхронизации должны быть свободны прежде, чем любой из них будет захвачен, то возможно, что поток, ждущий много объектов, долгое время не сможет захватить их, если другие потоки владеют какими-нибудь из этих же объектов синхронизации поодиночке. Например, самый левый поток на диаграмме мог бы ожидать мьютексы A, B и C, в то время как другие три потока захватывали каждый мьютекс отдельно. В самом неблагоприятном случае поток, ожидающий освобождения многочисленных объектов, вообще никогда не сможет их захватить.
Второй недостаток в том, что все-таки возможно попасть в тупик, но на этот раз не с отдельными мьютексами, а с набором из нескольких мьютексов сразу! Следующая диаграмма (прим.переводчика: диаграмма в оригинале отстутствует) иллюстрирует ситуацию, которая, несомненно, приведет к тупику, как и в примере, представленном в начале этой главы.
Третий недостаток этого метода, как и метода исключения тупика путем "ожидания" - невозможно использовать эти функции, если вы применяете критические секции; функция EnterCriticalSection не позволяет задать время ожидания, и не возвращает кода ошибки.

Атомарность составных операций - управление конкуренцией оптимистическим и пессимистическим образом.

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

Оптимистическое управление.

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

Выделить всёРазвернуть кодкод Pascal/Delphi
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
function CompareIndirect(L: TList; Ind1: integer): integer;
var
  Ind2: integer;
  TempValue: integer;
 
begin
  if (Ind1 > 0) and (L.Count > Ind1) then
  begin
    L.Items[Ind1].Lock;
    Ind2 := L.Items[Ind1];
    Assert(Ind2 <> Ind1); {I'm not even going to consider this nasty case in any more detail!}
    if Ind2 > Ind1 then
      L.Items[Ind2].Lock
    else
    begin
      TempValue := L.Items[Ind1].Value;
      L.Items[Ind1].Unlock;
      L.Items[Ind2].Lock;
      L.Items[Ind1].Lock;
    end;
    if TempValue := L.Items[Ind1].Value then
      Result := L.Items[Ind2].Value - L.Items[Ind1].Value
    else
      {Perhaps some retry mechanism?};
    L.Items[Ind1].Unlock;
    L.Items[Ind2].Unlock;
  end
  else
    raise ENotFound;
end;


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

Пессимистическое управление.

Мы можем использовать и … Продолжение »

Сделать бесплатный сайт с uCoz