Я всегда смущаюсь. Кто-нибудь объяснит, что Reentrant означает в разных контекстах? И почему вы хотите использовать реентерабельный или невозвратный?
Говорить pthread (posix) фиксирующие примитивы, являются ли они повторными или нет? Какие недостатки следует избегать при их использовании?
Является ли повторный вход mutex?
Блокировка повторного входа
Блокировка реентера такова, что процесс может требовать блокировку несколько раз, не блокируя сам по себе. Это полезно в ситуациях, когда нелегко отслеживать, захватили ли вы замок. Если блокировка не является повторной попыткой, вы можете захватить блокировку, а затем блокировать, когда вы идете, чтобы снова захватить ее, эффективно блокируя свой процесс.
Reentrancy в целом является свойством кода, в котором он не имеет центрального изменчивого состояния, которое может быть повреждено, если код был вызван во время его выполнения. Такой вызов может быть выполнен другим потоком, или он может быть рекурсивно реализован путем выполнения, исходящим из самого кода.
Если код зависит от общего состояния, которое может быть обновлено в середине его выполнения, оно не является повторным, по крайней мере, если это обновление может сломать его.
Вариант использования для блокировки повторного входа
A (несколько общий и надуманный) пример приложения для блокировки повторного входа может быть:
У вас есть некоторые вычисления с использованием алгоритма, который пересекает граф (возможно, с циклами в нем). Обход может посещать один и тот же node более одного раза из-за циклов или из-за нескольких путей к тому же node.
Структура данных подчиняется параллельному доступу и может быть обновлена по какой-либо причине, возможно, другим потоком. Вы должны иметь возможность блокировать отдельные узлы для борьбы с потенциальным повреждением данных из-за условий гонки. По какой-то причине (возможно, производительности) вы не хотите глобально блокировать всю структуру данных.
Вы не можете сохранить полную информацию о том, какие узлы вы посетили, или используете структуру данных, которая не позволяет мне "быть здесь раньше", чтобы быстро ответить.
>
Примером такой ситуации могла бы быть простая реализация алгоритма Дейкстры с приоритетной очередью, реализованной в виде двоичной кучи или поиска по ширине с использованием простого связанного списка в качестве очереди. В этих случаях проверка очереди для существующих вставок - O (N), и вы не можете делать это на каждой итерации.
В этой ситуации отслеживание того, какие замки вы уже приобрели, дорого. Предполагая, что вы хотите сделать блокировку на уровне node, механизм блокировки повторного входа облегчает необходимость выяснения того, посетил ли вы node раньше. Вы можете просто вслепую заблокировать node, возможно, разблокировать его после того, как вы вытащите его из очереди.
Метутесы повторного входа
Простой мьютекс не является повторным, поскольку только один поток может находиться в критическом разделе в данный момент времени. Если вы возьмете мьютекс, а затем попытайтесь снова захватить его, простой мьютекс не будет иметь достаточной информации, чтобы рассказать, кто его держал ранее. Чтобы сделать это рекурсивно, вам нужен механизм, в котором каждый поток имеет токен, чтобы вы могли узнать, кто захватил мьютекс. Это делает механизм мьютекса несколько более дорогим, поэтому вы не можете делать это во всех ситуациях.
IIRC API потоков POSIX предлагает возможность повторного входа и неперехватывать мьютексы.
Блокировка повторного входа позволяет вам написать метод M, который помещает блокировку в ресурс A, а затем вызывает M рекурсивно или из кода, который уже содержит блокировку на A.
С блокировкой без повторного входа вам понадобятся две версии M, одна из которых блокируется, а другая - нет, а дополнительная логика - правильная.
Реенторная блокировка очень хорошо описана в этом tutorial.
Пример в учебнике гораздо менее надуман, чем в ответе об обходе графика. Блокировка ретентата полезна в очень простых случаях.
Что и почему рекурсивного мьютекса не должно быть такой сложной вещью, описанной в принятом ответе.
Я хотел бы записать свое понимание после некоторых копаний в сети.
Во-первых, вы должны понимать, что когда речь идет о мьютексе, многопотоковые концепции также явно вовлечены. (мьютекс используется для синхронизации. Мне не нужен мьютекс, если в моей программе только 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