Автор этой статьи: Ду Юян
Didi | Старший эксперт-инженер ядра Linux
Введение. Взаимоблокировка — распространенная серьезная проблема в многопоточных и распределенных программах. Взаимная блокировка является деструктивной. После ее возникновения восстановить систему будет трудно или почти невозможно. Взаимная блокировка носит случайный характер и возникает только при соблюдении определенных условий. , это очень сложно.. Воспроизведите и отладьте. Взаимоблокировки, вызванные использованием блокировок, являются обычным случаем взаимоблокировок. Ядро Linux использует инструмент Lockdep для обнаружения и, в частности, прогнозирования сценариев взаимной блокировки блокировки. Однако в настоящее время Lockdep поддерживает только обработку блокировок мьютексов и не поддерживает более сложные блокировки чтения-записи, особенно рекурсивные блокировки чтения. Таким образом, Lockdep страдает как от ложноположительных ошибок прогнозирования, вызванных блокировками чтения-записи, так и от ложноотрицательных ошибок прогнозирования. В этой работе сначала расшифровывается инструмент Lockdep, а затем предлагается разработка и реализация общего алгоритма прогнозирования взаимоблокировок блокировок (мьютексные блокировки можно рассматривать только как использующие блокировки записи в блокировках чтения-записи), и в то же время доказывается, что алгоритм правильный и комплексный план решения.
В начале этого года мы последовательно устранили три ошибки ядра, которые серьезно повлияли на масштабный серверный кластер базовой платформы Didi.Решая эти проблемы, мы потратили много времени и сил на то, чтобы выяснить, кто и где создал тупик. , Задержка времени устранения неполадок, поэтому я задался вопросом, есть ли какой-либо общий способ помочь нам справиться с проблемами взаимоблокировки. Однако из-за неотложности времени мы можем только целенаправленно исследовать и решать эти конкретные вопросы. После, наконец, успешного исправления этих нескольких ошибок ядра у меня наконец-то появилось время, чтобы успокоиться и глубоко подумать о причинах взаимоблокировок и о том, как обнаруживать и прогнозировать взаимоблокировки. В ходе глубокого изучения этой проблемы я последовательно реализовал некоторые алгоритмы оптимизации и разработки алгоритмов для прогнозирования взаимоблокировок ядра, некоторые из которых были приняты ядром Linux, а другие все еще находятся на стадии проверки. Здесь я делюсь с вами одной из наиболее важных работ: общим алгоритмом прогнозирования взаимоблокировок блокировки чтения-записи. В этой работе предлагается общий алгоритм прогнозирования взаимоблокировок блокировок, который поддерживает все блокировки чтения-записи ядра Linux, при этом доказывая, что этот алгоритм является правильным и всеобъемлющим решением. Основная проблема, решаемая этим алгоритмом, существует уже более 10 лет (в настоящее время находится на стадии рассмотрения сообществом). Прежде чем представить эту работу, я сначала кратко расскажу о проблеме взаимоблокировки и инструменте взаимоблокировки ядра Linux Lockdep.
1. Тупик
Тупики не редкость в повседневной жизни. Люди, живущие в больших городах, более или менее пережили сцену, показанную на картинке ниже. Эта ситуация на кольцевой развязке или на перекрестке является тупиковой. Возможно, некоторые из них сломаны, но подавляющее большинство из них исправны. Но поскольку каждая машина должна дождаться движения впереди идущей машины, прежде чем она сможет двигаться, все машины не могут двигаться, или, в более общем смысле, они не могут продвигаться вперед (Действовать вперед). Причина, по которой это происходит, заключается в том, что ожидание транспортных средств представляет собой цикл, в котором каждое состояние транспортного средства ожидает предшествующее транспортное средство, поэтому ни одно из транспортных средств не может ждать того, чего оно ожидает. Это состояние тупиковой ситуации будет усугубляться и иметь серьезные последствия: во-первых, это приведет к возникновению пробок на перекрестках, а в случае дальнейшего расширения заторов приведет к масштабному параличу движения. Блокировка транспортного средства с трудом поддается самоизлечению.Выйти из состояния блокировки самостоятельно очень сложно или занимает много времени.Как правило, это можно решить только ручным вмешательством (например, ГАИ).
Взаимоблокировки также могут возникать в многопоточных или распределенных системных программах. Суть его та же, что и в упомянутой выше пробке на перекрестке, потому что участники составляют круговое ожидание, так что все участники не могут дождаться желаемого результата и, следовательно, никогда не смогут там продвинуться. Конечно, ядро Linux также будет заблокировано.Если основная часть (ядро), такая как планировщик и управление памятью, или подсистема, такая как файловая система, заблокирована, вся система будет недоступна.
Взаимоблокировки происходят случайным образом. Как и в случае с кольцевой развязкой на картинке выше, кольцевая развязка есть, и тупик не всегда случается. Однако сама кольцевая развязка представляет собой потенциальный риск тупиковой ситуации, особенно на перекрестках с интенсивным движением, кольцевая развязка будет более склонна к тупиковой ситуации. И если такой перекресток оформить как светофор, то будет намного лучше, а если оформить как эстакаду, то будет намного лучше. В программе мы называем сценарии, которые могут вызвать тупик, потенциальным тупиком (сценарий потенциального тупика), а неизбежный или продолжающийся тупик называется экземпляром тупика (конкретный тупик).
Как справиться с взаимоблокировкой, всегда было проблемой активного исследования и решения в академических кругах и в прикладных областях. Мы можем грубо разделить решения для взаимоблокировок: обнаружение взаимоблокировок (обнаружение), предотвращение взаимоблокировок (предотвращение) и прогнозирование взаимоблокировок (предсказание). Обнаружение взаимоблокировки относится к обнаружению экземпляров взаимоблокировки во время работы программы; предотвращение взаимоблокировки заключается в дальнейшем предотвращении экземпляра взаимоблокировки, когда обнаруживается, что он вот-вот будет создан; а прогнозирование взаимоблокировки заключается в выявлении потенциала в программе с помощью статического или динамического Тупик, тем самым принципиально устраняя потенциальный тупик заранее.
2. Блокировка тупика и Lockdep
В тупиковой ситуации тупиковая ситуация, вызванная неправильным использованием блокировки (Lock), является важным источником тупиковой ситуации. Блокировки являются основным средством синхронизации, и использование блокировок неизбежно. Для сложных отношений синхронизации использование блокировок будет более сложным. При неправильном использовании легко вызвать взаимоблокировку замков. С точки зрения ожидания взаимоблокировка блокировки возникает из-за того, что участвующие потоки ожидают освобождения блокировки, и это ожидание представляет собой цикл ожидания, такой как взаимоблокировка ABBA:
Среди них черная стрелка в потоке представляет текущий оператор выполнения потока, а красная стрелка представляет отношение ожидания между операторами потока. Как видите, красные стрелки образуют круг (или петлю). Оглядываясь назад на потенциальные взаимоблокировки и экземпляры взаимоблокировок, можно сказать, что если время выполнения этих двух потоков немного изменится, то очень вероятно, что экземпляры взаимоблокировок не возникнут.Например, если Thread1 завершает выполнение этого фрагмента кода, Thread2 начинает выполняться. Но такое поведение блокировки (Locking Behavior), несомненно, является потенциальным тупиком.
Кроме того, можно увидеть, что если мы можем отслеживать и анализировать поведение блокировки программы, можно предсказывать взаимоблокировки или находить потенциальные взаимоблокировки, а не ждать, пока взаимоблокировки обнаружат экземпляры взаимоблокировки. Инструмент Lockdep ядра Linux должен характеризовать поведение блокировки ядра, чтобы предсказывать потенциальные взаимоблокировки и сообщать о них.
Lockdep может описывать поведение класса блокировок (Lock Class), в основном записывая порядок блокировок (Locking Order) всех экземпляров блокировок в классе блокировок, то есть если поток удерживает блокировку A, он возьмет ее снова прежде чем он будет выпущен Блокировка B, затем блокировка A и блокировка B имеют последовательность блокировки A-> B. В Lockdep эта последовательность блокировки называется: Зависимость блокировки. Аналогично, для взаимоблокировки типа ABBA нам не нужно, чтобы Thread1 и Thread2 генерировали ровно один экземпляр взаимоблокировки, пока один поток генерирует поведение последовательности блокировки A->B, а другой поток генерирует последовательность B->A плюс блокировка. поведение, то это представляет собой потенциальную взаимоблокировку, как показано на следующем рисунке:
Исходя из этого обобщения, мы можем записать и сохранить все последовательности блокировки (то есть зависимости блокировки), чтобы сформировать граф последовательности блокировки (Graph). Среди них, если есть зависимость блокировки A->B и зависимость блокировки B->C , то, поскольку отношение зависимости блокировки (Relation) является транзитивным (Transitive), мы также можем получить зависимость блокировки A->C . A->B и B->C называются прямой зависимостью, а A->C называется косвенной зависимостью. Для каждой новой прямой зависимости блокировки мы проверяем, образует ли зависимость цикл с существующими зависимостями блокировки в графе, и если это так, мы можем предсказать потенциальную взаимоблокировку.
3. Блокировка чтения-записи
Блокировки, которые мы только что упомянули, являются эксклюзивными блокировками. Блокировка чтения-записи является более сложной блокировкой или общей блокировкой Мы можем думать о мьютексе как о блокировке чтения-записи, которая использует только блокировки записи. Пока нет блокировки записи или конкуренции за блокировку записи, блокировки чтения позволяют читателям (Readers) удерживать их одновременно. В ядре Linux существует множество блокировок чтения-записи, в основном в том числе: rwsem, rwlock и qrwlock и т. д. Проблема в том, что блокировки чтения-записи чрезвычайно усложняют прогнозирование взаимоблокировок, а Lockdep не может поддерживать такие виды блокировок чтения-записи, поэтому Lockdep будет генерировать некоторые связанные ложноположительные (ложноположительные) предсказания взаимоблокировок и ошибки во время использования. . Эта проблема существует уже более 10 лет.Мы предлагаем общий алгоритм прогнозирования взаимоблокировок для блокировок и доказываем, что этот алгоритм решает проблему прогнозирования взаимоблокировок для блокировок чтения-записи.
4. Общее прогнозирование взаимоблокировок для блокировок
При описании этого алгоритма мы объясняем или демонстрируем правильность предложенного нами предсказания взаимоблокировок, предлагая несколько лемм (лемма).
▍Лемма 1: после введения блокировок на чтение-запись цикл последовательности блокировок является необходимым условием потенциальной взаимоблокировки, но не достаточным условием. Кроме того, потенциальную взаимоблокировку можно и можно предсказать как можно раньше, когда последняя последовательность блокировки (или зависимость блокировки) вот-вот сгенерирует цикл взаимоблокировки.
Основываясь на лемме 1, решение проблемы прогнозирования взаимоблокировки состоит в том, чтобы вычислить, представляет ли кольцо ожидания потенциальную взаимоблокировку, каким-либо методом, когда последний порядок взятия блокировки (то есть зависимость блокировки) образует кольцо ожидания (цикл), и наша Задача состоит в том, чтобы найти этот метод (алгоритм).
▍Лемма 2: Два виртуальных потока T1 и T2 могут использоваться для представления всех сценариев взаимоблокировок.
Для любого экземпляра взаимоблокировки, предполагая, что в экземпляре взаимоблокировки участвует n потоков, n потоков представлены как:
T1,T2,…,Tn
Рассмотрим случай n:
Если n=1: этот тип взаимоблокировки заключается в том, что поток ожидает самого себя, что в Lockdep называется рекурсивной взаимоблокировкой. Так как такую взаимоблокировку проще проверить, этот частный случай игнорируется в приведенном ниже алгоритме. Если n>1: Этот тип взаимоблокировки называется Inversion Deadlock в Lockdep. Для этого случая мы делим n потоков на две группы, а именно T1,T2,…,Tn-1 и Tn, затем объединяем все зависимости блокировок из предыдущей группы вместе и предполагаем, что все эти зависимости существуют в виртуальном , тогда получаем два виртуальные потоки T1 и T2.
Это два виртуальных потока, описанные в лемме 2. Основываясь на лемме 2, мы предлагаем двухпотоковую модель проверки взаимоблокировок для представления поведения блокировки ядра:
T1 : Все зависимости блокировки перед текущей зависимостью проверки блокировки, которые формируют граф зависимостей блокировки. T2 : Текущая ожидающая зависимость прямой блокировки.
На основании леммы 2 и двухпоточной модели проверки взаимоблокировок можно получить следующую лемму:
▍Лемма 3: Любой тупик можно преобразовать в ABBA-тип.
Основываясь на приведенных выше 3 леммах, мы можем дополнительно описать проблему прогнозирования взаимоблокировок, поскольку, когда мы получаем новую прямую зависимость блокировки B-> A, мы представляем эту новую зависимость как T2, в то время как все предыдущие зависимости блокировки существуют. В сгенерированном графе зависимостей блокировок по воображаемому T1 прогноз взаимоблокировки заключается в проверке наличия зависимости блокировки A->B в T1, если взаимоблокировка есть, в противном случае взаимоблокировки нет и T2 объединяется с T1. Как показано ниже:
После введения блокировок чтения-записи зависимость блокировки зависит и от типа блокировки в ней, то есть типа чтения или записи. В соответствии с конструктивными характеристиками взаимоисключающих блокировок и блокировок чтения-записи в ядре Linux мы вводим таблицу мьютексов блокировок для представления отношений взаимного исключения между блокировками:
Среди них блокировка рекурсивного чтения (Recursive-read Lock) — это особый вид блокировки чтения, который может быть получен рекурсивно одним и тем же потоком. Ниже мы сначала предлагаем простой алгоритм (Simple Algorithm). На основе двухпоточной модели с заданными T1 и T2 и блокировками ABBA:
Шаги простого алгоритма следующие:
Если X1.A и X1.B являются взаимоисключающими, а X2.A и X2.B взаимно исключающими, то T1 и T2 представляют собой потенциальную тупиковую ситуацию.
В противном случае T1 и T2 не представляют собой потенциальную тупиковую ситуацию.
Из простого алгоритма видно, что тип блокировки определяет отношение взаимного исключения между блокировками, а отношение взаимного исключения является ключевой информацией для проверки взаимоблокировок. Для блокировок чтения-записи тип блокировки может измениться во время выполнения программы, так как же записать все типы блокировки? На основе взаимного исключения типов блокировки, то есть взаимного исключения типов блокировки от низкого к высокому: рекурсивная блокировка чтения
Среди них RRn представляет блокировку рекурсивного чтения n (блокировка рекурсивного чтения n), Rn представляет блокировку чтения n (блокировка чтения n), а Wn представляет блокировку записи или мьютекс n (блокировка записи n). Ниже Xn представляет любую блокировку n (т. е. блокировку рекурсивного чтения, чтения или записи).
Однако приведенный выше простой алгоритм не может справиться со всеми ситуациями прогнозирования взаимоблокировок.Например, следующий случай позволяет избежать простого алгоритма, но на самом деле это потенциальная взаимоблокировка:
В этом случае X1 и X3 являются взаимоисключающими, и этот случай представляет собой потенциальную тупиковую ситуацию. Однако, когда простой алгоритм проверяет RR2->X1 (то есть, T2 есть RR2->X1), он может найти X1->RR2 в T1 в соответствии с простым алгоритмом, но поскольку RR и RR не исключают друг друга, ошибочно определили, что этот случай не является тупиковым. Причина, по которой при анализе этого случая делается неправильный вывод, заключается в том, что X3->X1 в реальном тупике X1X3X3X1 является косвенной блокировочной зависимостью, а косвенная зависимость упускается простым алгоритмом.
Более глубокая причина этой проблемы заключается в том, что между мьютексами существует только взаимное исключение, поэтому, пока существует ABBA, это потенциальная взаимоблокировка, и нет необходимости проверять зависимость косвенной блокировки T2. В случае блокировки чтения это условие больше не существует, поэтому необходимо учитывать косвенные зависимости блокировки в T2.
▍Лемма 4: Для косвенной зависимости блокировки, представленной прямой зависимостью блокировки, если косвенная зависимость блокировки представляет собой взаимоблокировку, то прямая зависимость блокировки по-прежнему имеет решающее значение.
Лемма 4 является расширением леммы 1. Согласно лемме 1, эта прямая зависимость блокировки должна быть последней зависимостью блокировки, формирующей цикл блокировки, а лемма 4 показывает, что с помощью этой зависимости блокировки должна быть возможность определить, является ли цикл блокировки определенным образом является потенциальным тупиком. Другими словами, модифицируя и улучшая предложенный ранее простой алгоритм, новый алгоритм должен уметь решать эту задачу. Но проблема в том, что прямая зависимость от блокировок в оригинальном T2 может в дальнейшем генерировать много косвенных зависимостей от блокировок Как мы можем найти косвенную зависимость от блокировок, которая в конечном итоге приводит к потенциальной взаимоблокировке? Далее нам нужно сначала переопределить T2, а потом найти все непрямые зависимости блокировок в этом T2, тогда какова граница T2? Если T2 распространить на весь граф зависимостей блокировок, сложность алгоритма увеличится настолько, что может даже превысить вычислительную мощность Lockdep, что сделает Lockdep практически недоступным.
▍Лемма 5: T2 нужно расширить только до стека блокировки текущего потока.
В соответствии с леммой 5 мы сначала модифицируем ранее предложенную двухпотоковую модель следующим образом:
T1: в настоящее время проверяет все зависимости блокировки перед прямыми зависимостями блокировки, которые формируют граф. T2: Текущий стек блокировки проверяемого потока.
Согласно лемме 5 и новой двухпоточной модели мы предлагаем следующий окончательный алгоритм (Final Algorithm), основанный на простом алгоритме:
Продолжайте поиск графа зависимостей блокировки, т. е. T1 находит новый цикл зависимости блокировки. В этом новом цикле, если в T2 есть другие блокировки, то эта блокировка и прямая зависимость блокировки в T2 составляют косвенную зависимость блокировки, проверьте, представляет ли эта косвенная зависимость блокировки потенциальную взаимоблокировку. Если обнаружена потенциальная взаимоблокировка, алгоритм завершает работу, если нет, алгоритм переходит к 1 до тех пор, пока не будет просмотрен весь граф зависимостей блокировок.
Устранит ли этот окончательный алгоритм предыдущие случаи, когда возникала уязвимость? Ответ положительный, конкретный процесс проверки показан на рисунке:
Однако для всех остальных случаев верна ли лемма 5? Почему последний алгоритм работает? Мы доказываем, что непрямая блокировочная зависимость в окончательном алгоритме необходима и достаточна с помощью следующих двух лемм.
▍Лемма 6: Необходимо проверять непрямые блокировки в T2, иначе простой алгоритм решил все проблемы.
Лемма 6 утверждает, что из-за существования блокировок чтения-записи невозможно проверить только прямые зависимости блокировок.
▍Лемма 7: границей T2 является стек блокировок текущего потока, что достаточно.
Согласно лемме 2 и лемме 3 любой тупик может быть преобразован в двухпоточный тупик ABBA, причем T1 может вносить только AB, а T2 должен вносить BA. Здесь T2 — это не только виртуальный поток, но и фактический физический поток, поэтому T2 нужно и нужно только проверять текущий поток.
На данный момент описание общего алгоритма прогнозирования взаимоблокировок блокировки чтения-записи официально не подтверждено. Этот алгоритм был реализован в Lockdep и отправлен на проверку сообществу памяти Linux (см. https://lkml.org/lkml/2019/8/29/167 для получения последней версии). Ввиду актуальности и ограничений по объему некоторые ключевые детали алгоритма здесь показаны не все. Заинтересованные читатели могут перейти по ссылке выше, чтобы найти их. Комментарии и предложения приветствуются.
Обзор от начальной обработки нескольких серьезных системных сбоев, которые произошли в больших кластерах базовой платформы Didi, до изучения и исследования инструментов прогнозирования взаимоблокировок ядра, до разработки и реализации нового общего алгоритма прогнозирования взаимоблокировок блокировки чтения-записи. Это было полно неопределенности и даже драмы, но весь процесс и конечный результат были для меня очень полезными. Я думаю, что этот опыт похож на бег Форреста Гампа в фильме «Форрест Гамп»: когда вы достигаете пункта назначения, вы просто хотите пробежать еще немного, а когда вы достигнете следующего пункта назначения, установите новую и более далекую цель. Я также думаю, что разница между обычной работой и работой мирового уровня заключается не в отправной точке, а в конечной точке, забежали ли вы еще на несколько более отдаленных целей.
В то же время, вы также можете обратить внимание на официальный аккаунт Didi Technology, мы своевременно опубликуем самую последнюю информацию из открытых источников и техническую информацию!