Что такое блокировка реентера и концепция в целом?

Question 1

Я всегда путаюсь. Может ли кто-нибудь объяснить, что означает реентерабельность в разных контекстах? И почему вы хотите использовать реентерабельность и не реентерабельность?

Скажем, примитивы блокировки pthread (posix), являются ли они реентерабельными или нет? Каких подводных камней следует избегать при их использовании?

Повторяется ли мьютекс?

Question 2

Повторная блокировка

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

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

Если код полагается на общее состояние, которое может быть обновлено в середине его выполнения, он не является реентерабельным, по крайней мере, если это обновление могло его нарушить.

Пример использования повторной блокировки

Пример (несколько общий и надуманный) приложения для блокировки повторного входа может быть следующим:

У вас есть вычисления с использованием алгоритма, который проходит по графу (возможно, с циклами в нем). Обход может посещать один и тот же узел более одного раза из-за циклов или из-за нескольких путей к одному и тому же узлу.
Структура данных подлежит одновременному доступу и может быть обновлена по какой-то причине, возможно, другим потоком. Вы должны иметь возможность блокировать отдельные узлы, чтобы иметь дело с потенциальным повреждением данных из-за состояния гонки. По какой-то причине (возможно, из-за производительности) вы не хотите глобально блокировать всю структуру данных.
Ваше вычисление не может сохранить полную информацию о том, какие узлы вы посетили, или вы используете структуру данных, которая не позволяет быстро ответить на вопросы типа «был ли я здесь раньше».

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

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

Повторяющиеся мьютексы

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

IIRC API потоков POSIX предлагает возможность мьютексов с повторным входом и без него.

Question 3

Блокировка повторного входа позволяет вам написать метод, Mкоторый устанавливает блокировку ресурса, Aа затем вызывает его Mрекурсивно или из кода, который уже удерживает блокировку A.

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

Question 4

Повторная блокировка очень хорошо описана в этом руководстве .

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

Question 5

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

Я хотел бы записать свое понимание после некоторых поисков в сети.

Во-первых, вы должны понимать, что, говоря о мьютексах , определенно подразумевается и концепция многопоточности. (мьютекс используется для синхронизации. Мне не нужен мьютекс, если в моей программе только 1 поток)

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

Цитируется из APUE :

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

Ключевое отличие состоит в том, что в одном потоке повторная блокировка рекурсивной блокировки не приводит к тупиковой ситуации и не блокирует поток.

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

Давайте посмотрим на код в качестве доказательства.

нормальный мьютекс с тупиком

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lock;


void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

выход:

thread1
thread1 hey hey
thread2

общий пример тупика, нет проблем.

рекурсивный мьютекс с тупиком

Просто раскомментируйте эту строку
error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
и закомментируйте другую.

выход:

thread1
thread1 hey hey
thread2

Да, рекурсивный мьютекс тоже может вызвать тупик.

нормальный мьютекс, повторная блокировка в том же потоке

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

pthread_mutex_t lock;


void func3(){
    printf("func3\n");
    pthread_mutex_lock(&lock);
    printf("func3 hey hey\n");
}

void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    func3();
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    sleep(2); 
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

выход:

thread1
func3
thread2

Тупик в thread t1, в func3.
(Я использую, sleep(2)чтобы было легче увидеть, что тупик в первую очередь вызван повторной блокировкой func3)

рекурсивный мьютекс, повторная блокировка в том же потоке

Снова раскомментируйте строку рекурсивного мьютекса и закомментируйте другую строку.

выход:

thread1
func3
func3 hey hey
thread1 hey hey
thread2

Тупик в thread t2, в func2. Увидеть? func3завершается и завершается, повторная блокировка не блокирует поток и не приводит к тупиковой ситуации.

Итак, последний вопрос, зачем нам это нужно?

Для рекурсивной функции (вызываемой в многопоточных программах, и вы хотите защитить некоторые ресурсы / данные).

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

См. Пример из принятого ответа. Когда использовать рекурсивный мьютекс? .

Википедия очень хорошо объясняет рекурсивный мьютекс. Определенно стоит прочитать. Википедия: Reentrant_mutex

Answer 1

Я всегда путаюсь. Может ли кто-нибудь объяснить, что означает реентерабельность в разных контекстах? И почему вы хотите использовать реентерабельность и не реентерабельность?

Скажем, примитивы блокировки pthread (posix), являются ли они реентерабельными или нет? Каких подводных камней следует избегать при их использовании?

Повторяется ли мьютекс?

Answer 2

Повторная блокировка

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

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

Если код полагается на общее состояние, которое может быть обновлено в середине его выполнения, он не является реентерабельным, по крайней мере, если это обновление могло его нарушить.

Пример использования повторной блокировки

Пример (несколько общий и надуманный) приложения для блокировки повторного входа может быть следующим:

У вас есть вычисления с использованием алгоритма, который проходит по графу (возможно, с циклами в нем). Обход может посещать один и тот же узел более одного раза из-за циклов или из-за нескольких путей к одному и тому же узлу.
Структура данных подлежит одновременному доступу и может быть обновлена по какой-то причине, возможно, другим потоком. Вы должны иметь возможность блокировать отдельные узлы, чтобы иметь дело с потенциальным повреждением данных из-за состояния гонки. По какой-то причине (возможно, из-за производительности) вы не хотите глобально блокировать всю структуру данных.
Ваше вычисление не может сохранить полную информацию о том, какие узлы вы посетили, или вы используете структуру данных, которая не позволяет быстро ответить на вопросы типа «был ли я здесь раньше».

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

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

Повторяющиеся мьютексы

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

IIRC API потоков POSIX предлагает возможность мьютексов с повторным входом и без него.

Answer 3

2

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

Джон Скит,

Answer 4

+1, также рассмотрите случай, когда блокировка НЕ повторяется, вы можете заблокировать себя, если не будете осторожны. Кроме того, в C у вас нет тех же механизмов, которые есть в других языках, чтобы гарантировать, что блокировка снимается столько раз, сколько получено. Это может привести к большим проблемам.

user7116,

Answer 5

1

Именно это и произошло со мной вчера: я не принял во внимание вопрос повторного входа и закончил тем, что отлаживал тупик в течение 5 часов ...

vehomzzz

Answer 6

@Jon Skeet - Я думаю, что есть, вероятно, ситуации (см. Мой несколько надуманный пример выше), когда отслеживание блокировок нецелесообразно из-за производительности или других соображений.

ConcernedOfTunbridgeWells

Answer 7

21

Блокировка повторного входа позволяет вам написать метод, Mкоторый устанавливает блокировку ресурса, Aа затем вызывает его Mрекурсивно или из кода, который уже удерживает блокировку A.

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

Хенк Холтерман
источник

Означает ли это, что если у меня есть рекурсивные вызовы, получающие один и тот же объект блокировки более одного раза - скажем, xраз заданным потоком, я не могу чередовать выполнение, не освобождая все рекурсивно полученные блокировки (одна и та же блокировка, но xнесколько раз)? Если это правда, то это по существу делает эту реализацию последовательной. Я что-то упускаю?

DevdattaK

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

Хенк Холтерман

Answer 8

Означает ли это, что если у меня есть рекурсивные вызовы, получающие один и тот же объект блокировки более одного раза - скажем, xраз заданным потоком, я не могу чередовать выполнение, не освобождая все рекурсивно полученные блокировки (одна и та же блокировка, но xнесколько раз)? Если это правда, то это по существу делает эту реализацию последовательной. Я что-то упускаю?

DevdattaK

Answer 9

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

Хенк Холтерман

Answer 10

Повторная блокировка очень хорошо описана в этом руководстве .

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

Answer 11

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

Я хотел бы записать свое понимание после некоторых поисков в сети.

Во-первых, вы должны понимать, что, говоря о мьютексах , определенно подразумевается и концепция многопоточности. (мьютекс используется для синхронизации. Мне не нужен мьютекс, если в моей программе только 1 поток)

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

Цитируется из APUE :

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

Ключевое отличие состоит в том, что в одном потоке повторная блокировка рекурсивной блокировки не приводит к тупиковой ситуации и не блокирует поток.

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

Давайте посмотрим на код в качестве доказательства.

нормальный мьютекс с тупиком

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lock;


void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

выход:

thread1
thread1 hey hey
thread2

общий пример тупика, нет проблем.

рекурсивный мьютекс с тупиком

Просто раскомментируйте эту строку
error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
и закомментируйте другую.

выход:

thread1
thread1 hey hey
thread2

Да, рекурсивный мьютекс тоже может вызвать тупик.

нормальный мьютекс, повторная блокировка в том же потоке

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

pthread_mutex_t lock;


void func3(){
    printf("func3\n");
    pthread_mutex_lock(&lock);
    printf("func3 hey hey\n");
}

void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    func3();
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    sleep(2); 
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

выход:

thread1
func3
thread2

Тупик в thread t1, в func3.
(Я использую, sleep(2)чтобы было легче увидеть, что тупик в первую очередь вызван повторной блокировкой func3)

рекурсивный мьютекс, повторная блокировка в том же потоке

Снова раскомментируйте строку рекурсивного мьютекса и закомментируйте другую строку.

выход:

thread1
func3
func3 hey hey
thread1 hey hey
thread2

Тупик в thread t2, в func2. Увидеть? func3завершается и завершается, повторная блокировка не блокирует поток и не приводит к тупиковой ситуации.

Итак, последний вопрос, зачем нам это нужно?

Для рекурсивной функции (вызываемой в многопоточных программах, и вы хотите защитить некоторые ресурсы / данные).

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

См. Пример из принятого ответа. Когда использовать рекурсивный мьютекс? .

Википедия очень хорошо объясняет рекурсивный мьютекс. Определенно стоит прочитать. Википедия: Reentrant_mutex

Что такое блокировка реентера и концепция в целом?

Ответы: