Различие между racearound условием и мертвой блокировкой

Каково различие между тупиком и гонкой вокруг условия в программировании условий?

46
задан kmp 15 October 2013 в 06:44
поделиться

3 ответа

Подумайте о состоянии гонки на традиционном примере. Допустим, у вас и у вашего друга есть банкоматные карты для одного и того же банковского счета. Теперь предположим, что на счету есть 100 долларов. Подумайте, что происходит, когда вы пытаетесь вывести 10 долларов, а ваш друг пытается вывести 50 долларов в одно и то же время.

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

Отметьте обе свои транзакции T1 (вы снимаете 10 долларов) и T2 (ваш друг снимает 50 долларов). Теперь числа ниже, слева, представляют временные шаги.

       T1                        T2
       ----------------          ------------------------
 1.    Read Acct ($100)          
 2.                              Read Acct ($100)
 3.    Write New Amt ($90)
 4.                              Write New Amt ($50)
 5.                              End
 6.    End

После завершения обеих транзакций с использованием этой временной шкалы, что возможно, если вы не используете какой-либо механизм блокировки, на счету будет 50 долларов. Это на 10 долларов больше, чем следовало бы (ваша транзакция потеряна навсегда, но у вас все еще есть деньги).

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

Тупик возникает при конфликте разделяемого ресурса. Это что-то вроде «Уловки-22».

   T1            T2
   -------       --------
1.  Lock(x)
2.               Lock(y)
3.  Write x=1
4.               Write y=19
5.  Lock(y)
6.  Write y=x+1
7.               Lock(x)
8.               Write x=y+2
9.  Unlock(x)
10.              Unlock(x)
11. Unlock(y)
12.              Unlock(y)

Вы можете видеть, что тупик возникает в момент 7, потому что T2 пытается получить блокировку на x , но T1 уже удерживает блокировку на x , но ожидает блокировки для y , что соответствует T2.

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

Один из способов предотвращения такого рода проблемы взаимоблокировки с несколькими объектами (ресурсами) блокировки - это ввести порядок. Как видите, в предыдущем примере T1 заблокировал x , а затем y , но T2 заблокировал y , а затем x . Если обе транзакции здесь придерживаются некоторого правила упорядочивания, которое гласит: « x всегда должен быть заблокирован до y », то эта проблема не возникнет. (Вы можете изменить предыдущий пример с учетом этого правила и увидеть, что взаимоблокировки не возникает).

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

Надеюсь, это немного поможет. Как всегда, используйте Википедию в качестве отправной точки для концепций CS:

http://en.wikipedia.org/wiki/Deadlock

http://en.wikipedia.org/wiki/Race_condition

64
ответ дан 26 November 2019 в 20:25
поделиться

Тупик - это когда два (или более) потока блокируют друг друга. Обычно это как-то связано с потоками, пытающимися получить общие ресурсы. Например, если потокам T1 и T2 необходимо получить ресурсы A и B для выполнения своей работы. Если T1 получает ресурс A, то T2 получает ресурс B, тогда T1 может ждать ресурса B, в то время как T2 ожидает ресурса A. В этом случае оба потока будут ждать неограниченное время ресурса, удерживаемого другим потоком. Эти потоки считаются заблокированными.

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

14
ответ дан 26 November 2019 в 20:25
поделиться

Я предполагаю, что вы имеете в виду «условия гонки», а не «гонку вокруг условий» (я слышал этот термин ...)

По сути, мертвая блокировка - это состояние, при котором поток A ожидает ресурса X, удерживая блокировку ресурса Y, а поток B ожидает ресурса Y, удерживая блокировку ресурса X. Потоки блокируют друг друга, ожидая освобождения своих блокировок.

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

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

newNode->next = listHead;
listHead = newNode;

Но если два потока делают это одновременно, то может возникнуть ситуация, когда они будут работать как итак:

Thread A                       Thread B
newNode1->next = listHead
                               newNode2->next = listHead
                               listHead = newNode2
listHead = newNode1

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

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

5
ответ дан 26 November 2019 в 20:25
поделиться
Другие вопросы по тегам:

Похожие вопросы: