Интервьюер: Что такое тупик? Как устранить взаимоблокировку? Как избежать тупика?

Операционная система

Я вдруг обнаружил, что в моей графической системе отсутствует содержимое "тупика", так что я это восполню.

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

На этот раз мы системно поговорим о проблеме взаимоблокировки.

  • концепция тупика;
  • Моделирование возникновения взаимоблокировок;
  • Используйте инструменты для устранения неполадок взаимоблокировки;
  • Избегайте проблем с взаимоблокировками;

концепция тупика

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

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

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

только тупикудовлетворить обоихБудут выполнены следующие четыре условия:

  • взаимоисключающие условия;
  • держите и ждите условий;
  • неотъемлемое состояние;
  • условие ожидания цикла;
взаимоисключающее условие

Взаимоисключающее условие означаетНесколько потоков не могут использовать один и тот же ресурс одновременно.

Например, на рисунке ниже, если ресурс, уже удерживаемый потоком A, не может одновременно удерживаться потоком B, если поток B запрашивает получение ресурса, уже занятого потоком A, тогда поток B может только ждать, пока поток A освобождает ресурс.

состояние удержания и ожидания

Условие удержания и ожидания означает, что когда поток A уже удерживает ресурс 1 и хочет подать заявку на ресурс 2, а ресурс 2 уже удерживается потоком C, поток A будет находиться в состоянии ожидания, ноПоток A не освобождает ресурс 1, который он уже удерживает, ожидая ресурса 2..

неотъемлемое условие

Неотъемлемое условие означает, что когда поток уже удерживает ресурс,Не может быть получен другими потоками, пока не будет использован сам по себе, если поток B также хочет использовать этот ресурс, он может получить его только после того, как поток A завершит его использование и освободит его.

условие ожидания цикла

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

Например, поток A уже содержит ресурс 2 и хочет запросить ресурс 1, в то время как поток B получил ресурс 1 и хочет запросить ресурс 2, что формирует кольцевую диаграмму ожидания запроса ресурса.

Моделирование генерации проблем взаимоблокировки

Talk is cheap. Show me the code.

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

Во-первых, мы сначала создаем два потока, поток A и поток B, а затем имеем две блокировки мьютекса, mutex_A и mutex_B, код выглядит следующим образом:

pthread_mutex_t mutex_A = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_B = PTHREAD_MUTEX_INITIALIZER;

int main()
{
    pthread_t tidA, tidB;
    
    //创建两个线程
    pthread_create(&tidA, NULL, threadA_proc, NULL);
    pthread_create(&tidB, NULL, threadB_proc, NULL);
    
    pthread_join(tidA, NULL);
    pthread_join(tidB, NULL);
    
    printf("exit\n");
    
    return 0;
}

Далее, давайте посмотрим, что делает функция потока A.

//线程函数 A
void *threadA_proc(void *data)
{
    printf("thread A waiting get ResourceA \n");
    pthread_mutex_lock(&mutex_A);
    printf("thread A got ResourceA \n");
    
    sleep(1);
    
    printf("thread A waiting get ResourceB \n");
    pthread_mutex_lock(&mutex_B);
    printf("thread A got ResourceB \n");

    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
    return (void *)0;
}

Как видите, процесс функции потока A:

  • Сначала захватите мьютекс A, затем засните на 1 секунду;
  • Затем установите блокировку мьютекса B, а затем снимите блокировку мьютекса B;
  • Наконец освободите мьютекс A;
//线程函数 B
void *threadB_proc(void *data)
{
    printf("thread B waiting get ResourceB \n");
    pthread_mutex_lock(&mutex_B);
    printf("thread B got ResourceB \n");
    
    sleep(1);
    
    printf("thread B waiting  get ResourceA \n");
    pthread_mutex_lock(&mutex_A);
    printf("thread B got ResourceA \n");
    
    pthread_mutex_unlock(&mutex_A);
    pthread_mutex_unlock(&mutex_B);
    return (void *)0;
}

Как видите, процесс функции потока B:

  • Сначала захватите мьютекс B, затем засните на 1 секунду;
  • Затем захватите мьютекс A, а затем освободите мьютекс A;
  • Наконец освободите мьютекс B;

Затем запускаем программу и получаем следующие результаты:

thread B waiting get ResourceB 
thread B got ResourceB 
thread A waiting get ResourceA 
thread A got ResourceA 
thread B waiting get ResourceA 
thread A waiting get ResourceB 
// 阻塞中。。。

Видно, что поток B ожидает освобождения мьютекса A, поток A ждет освобождения мьютекса B и обе стороны ждут освобождения ресурсов друг друга Очевидно, возникает проблема взаимоблокировки.

Устранение взаимоблокировок с помощью инструментов

Если вы хотите устранить неполадки, не заблокирована ли ваша программа Java, вы можете использоватьjstackинструмент, который представляет собой инструмент анализа стека потоков, который поставляется с jdk.

Поскольку пример кода взаимоблокировки Кобаяши написан на C, под Linux мы можем использоватьpstack + gdbИнструменты для обнаружения проблем взаимоблокировки.

Команда pstack может отображать информацию о трассировке стека (процесс вызова функции) каждого потока, и ее использование также очень просто, просто нужноpstack <pid>Вот и все.

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

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

$ pstack 87746
Thread 3 (Thread 0x7f60a610a700 (LWP 87747)):
#0  0x0000003720e0da1d in __lll_lock_wait () from /lib64/libpthread.so.0
#1  0x0000003720e093ca in _L_lock_829 () from /lib64/libpthread.so.0
#2  0x0000003720e09298 in pthread_mutex_lock () from /lib64/libpthread.so.0
#3  0x0000000000400725 in threadA_proc ()
#4  0x0000003720e07893 in start_thread () from /lib64/libpthread.so.0
#5  0x00000037206f4bfd in clone () from /lib64/libc.so.6
Thread 2 (Thread 0x7f60a5709700 (LWP 87748)):
#0  0x0000003720e0da1d in __lll_lock_wait () from /lib64/libpthread.so.0
#1  0x0000003720e093ca in _L_lock_829 () from /lib64/libpthread.so.0
#2  0x0000003720e09298 in pthread_mutex_lock () from /lib64/libpthread.so.0
#3  0x0000000000400792 in threadB_proc ()
#4  0x0000003720e07893 in start_thread () from /lib64/libpthread.so.0
#5  0x00000037206f4bfd in clone () from /lib64/libc.so.6
Thread 1 (Thread 0x7f60a610c700 (LWP 87746)):
#0  0x0000003720e080e5 in pthread_join () from /lib64/libpthread.so.0
#1  0x0000000000400806 in main ()

....

$ pstack 87746
Thread 3 (Thread 0x7f60a610a700 (LWP 87747)):
#0  0x0000003720e0da1d in __lll_lock_wait () from /lib64/libpthread.so.0
#1  0x0000003720e093ca in _L_lock_829 () from /lib64/libpthread.so.0
#2  0x0000003720e09298 in pthread_mutex_lock () from /lib64/libpthread.so.0
#3  0x0000000000400725 in threadA_proc ()
#4  0x0000003720e07893 in start_thread () from /lib64/libpthread.so.0
#5  0x00000037206f4bfd in clone () from /lib64/libc.so.6
Thread 2 (Thread 0x7f60a5709700 (LWP 87748)):
#0  0x0000003720e0da1d in __lll_lock_wait () from /lib64/libpthread.so.0
#1  0x0000003720e093ca in _L_lock_829 () from /lib64/libpthread.so.0
#2  0x0000003720e09298 in pthread_mutex_lock () from /lib64/libpthread.so.0
#3  0x0000000000400792 in threadB_proc ()
#4  0x0000003720e07893 in start_thread () from /lib64/libpthread.so.0
#5  0x00000037206f4bfd in clone () from /lib64/libc.so.6
Thread 1 (Thread 0x7f60a610c700 (LWP 87746)):
#0  0x0000003720e080e5 in pthread_join () from /lib64/libpthread.so.0
#1  0x0000000000400806 in main ()

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

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

Весь процесс отладки gdb выглядит следующим образом:

// gdb 命令
$ gdb -p 87746

// 打印所有的线程信息
(gdb) info thread
  3 Thread 0x7f60a610a700 (LWP 87747)  0x0000003720e0da1d in __lll_lock_wait () from /lib64/libpthread.so.0
  2 Thread 0x7f60a5709700 (LWP 87748)  0x0000003720e0da1d in __lll_lock_wait () from /lib64/libpthread.so.0
* 1 Thread 0x7f60a610c700 (LWP 87746)  0x0000003720e080e5 in pthread_join () from /lib64/libpthread.so.0
//最左边的 * 表示 gdb 锁定的线程，切换到第二个线程去查看

// 切换到第2个线程
(gdb) thread 2
[Switching to thread 2 (Thread 0x7f60a5709700 (LWP 87748))]#0  0x0000003720e0da1d in __lll_lock_wait () from /lib64/libpthread.so.0 

// bt 可以打印函数堆栈，却无法看到函数参数，跟 pstack 命令一样 
(gdb) bt
#0  0x0000003720e0da1d in __lll_lock_wait () from /lib64/libpthread.so.0
#1  0x0000003720e093ca in _L_lock_829 () from /lib64/libpthread.so.0
#2  0x0000003720e09298 in pthread_mutex_lock () from /lib64/libpthread.so.0
#3  0x0000000000400792 in threadB_proc (data=0x0) at dead_lock.c:25
#4  0x0000003720e07893 in start_thread () from /lib64/libpthread.so.0
#5  0x00000037206f4bfd in clone () from /lib64/libc.so.6

// 打印第三帧信息，每次函数调用都会有压栈的过程，而 frame 则记录栈中的帧信息
(gdb) frame 3
#3  0x0000000000400792 in threadB_proc (data=0x0) at dead_lock.c:25
27    printf("thread B waiting get ResourceA \n");
28    pthread_mutex_lock(&mutex_A);

// 打印mutex_A的值 ,  __owner表示gdb中标示线程的值，即LWP
(gdb) p mutex_A
$1 = {__data = {__lock = 2, __count = 0, __owner = 87747, __nusers = 1, __kind = 0, __spins = 0, __list = {__prev = 0x0, __next = 0x0}}, 
  __size = "\002\000\000\000\000\000\000\000\303V\001\000\001", '\000' <repeats 26 times>, __align = 2}

// 打印mutex_B的值 ,  __owner表示gdb中标示线程的值，即LWP
(gdb) p mutex_B
$2 = {__data = {__lock = 2, __count = 0, __owner = 87748, __nusers = 1, __kind = 0, __spins = 0, __list = {__prev = 0x0, __next = 0x0}}, 
  __size = "\002\000\000\000\000\000\000\000\304V\001\000\001", '\000' <repeats 26 times>, __align = 2}

Позвольте мне объяснить описанный выше процесс отладки:

  1. пройти черезinfo threadПосле вывода всей информации о потоке вы можете увидеть, что есть 3 потока, один из которых является основным (LWP 87746), а два других — потоками, созданными нами (LWP 87747 и 87748);
  2. пройти черезthread 2, переключится на поток 2 (LWP 87748);
  3. пройти черезbt, напечатайте информацию о стеке вызовов потока, вы можете видеть, что есть функция threadB_proc, указывающая, что это функция потока B, что означает, что LWP 87748 является потоком B;
  4. пройти черезframe 3, напечатайте информацию о третьем фрейме в стеке вызовов, вы можете видеть, что функция потока B заблокирована при захвате мьютекса A;
  5. пройти черезp mutex_A, напечатайте информацию об объекте мьютекса A, вы можете видеть, что он удерживается потоком, чей LWP равен 87747 (поток A);
  6. пройти черезp mutex_B, напечатайте информацию об объекте мьютекса A, вы можете видеть, что он удерживается потоком, чей LWP равен 87748 (поток B);

Поскольку поток B ожидает mutex_A, удерживаемый потоком A, и в то же время поток A ожидает mutex_B, принадлежащий потоку B, можно сделать вывод, что программа заблокирована.

Избегайте проблем с взаимоблокировками

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

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

Каково упорядоченное распределение ресурсов?

Порядок, в котором поток A и поток B получают ресурсы, должен быть одинаковым.Когда поток A сначала пытается получить ресурс A, а затем пытается получить ресурс B, поток B также сначала пытается получить ресурс A, а затем пытается получить ресурс B. . То есть поток A и поток B всегда запрашивают нужные им ресурсы в одном и том же порядке.

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

Сначала мы должны понять порядок, в котором поток A получает ресурсы: сначала он получает мьютекс A, а затем мьютекс B.

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

Улучшенный код функции потока B выглядит следующим образом:

//线程 B 函数，同线程 A 一样，先获取互斥锁 A，然后获取互斥锁 B
void *threadB_proc(void *data)
{
    printf("thread B waiting get ResourceA \n");
    pthread_mutex_lock(&mutex_A);
    printf("thread B got ResourceA \n");
    
    sleep(1);
    
    printf("thread B waiting  get ResourceB \n");
    pthread_mutex_lock(&mutex_B);
    printf("thread B got ResourceB \n");
    
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
    return (void *)0;
}

Результаты выполнения следующие: Как видите, взаимной блокировки не произошло.

thread B waiting get ResourceA 
thread B got ResourceA 
thread A waiting get ResourceA 
thread B waiting  get ResourceB 
thread B got ResourceB 
thread A got ResourceA 
thread A waiting get ResourceB 
thread A got ResourceB
exit

Суммировать

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

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

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

Категории