Разработайте класс, который обеспечивает блокировку, только если нет возможных тупиков - PullRequest
9 голосов
/ 02 марта 2011

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

Разработка класса, который обеспечивает блокировку, только если нет возможных тупиков.

Никакой другой информации не предоставлено. Я не совсем уверен, как это интерпретировать. Предполагая модель pthreads, ищет ли интервьюер класс менеджера блокировки? Любые идеи помогут.

Ответы [ 3 ]

8 голосов
/ 03 марта 2011

тупик будет возникать с замком, только если замки можно удерживать по кругу; то есть, если вы определяете порядок <для блокировок таким образом, что A <B только в том случае, если блокировка A может удерживаться и при блокировке B, то <не является строгим частичным упорядочением. Например, если поток 1 пытается получить блокировку A, а затем блокировать B, тогда как поток 2 пытается получить блокировку B, а затем блокировать A, тогда A <B и B <A, поэтому <не является строгим частичным упорядочением. Действительно, тупик может возникнуть, если каждый из потоков 1 и 2 получает блокировки A и B соответственно, а затем пытается получить другую блокировку. </p>

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

РЕДАКТИРОВАТЬ: Вот эскиз простой схемы реализации. Я предполагаю, что в качестве примитива у вас есть наивная блокировка мьютекса, которая не предотвращает взаимоблокировку, а также возможность хранить некоторые данные для каждого потока.

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

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

Когда поток фактически получает блокировку, добавьте эту блокировку к набору собственных блокировок потока.

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

Надеюсь, это поможет!

4 голосов
/ 03 марта 2011

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

0 голосов
/ 13 января 2016

На самом деле тот же самый вопрос появляется в «Взломе кодирования». Вот ответ: enter image description here

...