Как определить, где данные теряются при использовании многопоточности

Question

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

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

// Inserts a key-value pair into the table 
void insert(int key, int val) { 
    pthread_mutex_lock(&lock); 
    int i = key % NUM_BUCKETS; 
    bucket_entry *e = (bucket_entry *) malloc(sizeof(bucket_entry)); 
    if (!e) panic("No memory to allocate bucket!"); 
    e->next = table[i]; 
    e->key = key; 
    e->val = val; 
    table[i] = e; 
    pthread_mutex_unlock(&lock); 
    pthread_exit(NULL); 
} 

// Retrieves an entry from the hash table by key 
// Returns NULL if the key isn't found in the table 
bucket_entry * retrieve(int key) { 
    pthread_mutex_lock(&lock); 
    bucket_entry *b; 
    for (b = table[key % NUM_BUCKETS]; b != NULL; b = b->next) { 
     if (b->key == key) return b; 
    } 
    pthread_mutex_unlock(&lock); 
    pthread_exit(NULL); 
    return NULL; 
} 

Так основные проблемы здесь:

1. Как сказать, где данные теряются между каждой операцией резьбы

2. Что может ли программа зависать, когда ключи извлекаются из хеш-таблицы?

Answer 1

Во-первых, вы должны узнать больше о pthreads. Читайте также pthreads(7). Обратите внимание, в частности, что каждый замок вызов как pthread_mutex_lock должен всегда быть позже с последующим вызовом pthread_mutex_unlock на же мьютекс (и условно вы должны принять дисциплину что каждый замок и разблокировка происходит в же блок). Поэтому ваш return в for цикл вашего retrieve неправильно, вы должны написать:

bucket_entry * 
retrieve(int key) { 
    bucket_entry *res = NULL; 
    pthread_mutex_lock(&lock); 
    for (bucket_entry *b = table[key % NUM_BUCKETS]; 
     b != NULL; b = b->next) { 
    if (b->key == key) 
     { res = b; break; }; 
    } 
    pthread_mutex_unlock(&lock); 
    return res; 
} 

Тогда вы могли бы использовать valgrind и использовать недавнийGCC компилятор (например, 5.2 в ноябре 2015 года). Скомпилируйте все предупреждения & отладочная информация (gcc -Wall -Wextra -g -pthread). Читайте о дезинфицирующих debugging options, в частности, рассмотреть вопрос об использовании -fsanitize=thread

Есть несколько причин, чтобы назвать pthread_exit (также, вы редко вызова exit в программе). Когда вы это сделаете, весь текущий поток будет прекращен.