C++ Многопоточность Mutex блокирует ошибку сегментации

** Это для курса колледжа, на самом деле я не пытаюсь взломать пароли ** Ниже приведен мой исходный код, но, по сути, я хочу, чтобы родительский процесс помещал пароли в очередь в std::list‹> tryList. Затем дочерние потоки захватывают начало очереди и в настоящее время просто распечатывают значение.

Как вы можете видеть из приведенного ниже кода, я пытаюсь использовать std::mutex, чтобы заблокировать tryList, когда фронт выталкивается, но оба потока проходят мимо блокировки одновременно и читают спереди. Затем один из них дает сбой сегментации, и программа падает.

Конкретный раздел кода, который вызывает ошибку seg,...

mutex.lock();
password = attemptList.front();
attemptList.pop_front();
size = attemptList.size();
std::cout << password << std::endl;
            mutex.unlock();
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <chrono>
#include <shared_mutex>
#include <unistd.h>
#include <sys/ipc.h>
#include <mutex>
#include <sys/shm.h>
#include <sys/wait.h>
#include <thread>
#include <vector>
#include <algorithm>
#include <list>

#define MAX_LENGTH 4
#define MAX_QUEUE_SIZE 1000
#define CHARACTER_LIST "abcdefghijklmnopqrstuvwxyz"

void enqueue_passwords(const std::string& charList);
void bruteforce();
void do_join(std::thread& t);
void join_all(std::vector<std::thread>& v);

std::list<std::string> attemptList;
std::mutex mutex;
bool conclude = false;

int main(int argc, char* argv[]) {
    auto start = std::chrono::high_resolution_clock::now();

    int index;
    std::vector<std::thread> threads;
    for (index = 0; index < 2; index++) {
        threads.emplace_back(std::thread(bruteforce));
    }

    enqueue_passwords(CHARACTER_LIST);

    join_all(threads);

    auto stop = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
    std::cout << duration.count() << " milliseconds" << std::endl;

    return 0;
}

void bruteforce() {
    double size = 0;
    std::string password;

    while (!conclude) {
        do {
            mutex.lock();
            size = attemptList.size();
            mutex.unlock();

            if (size == 0) {
                usleep(300);
            }
        } while (size == 0);

        while(size != 0) {
            mutex.lock();
            password = attemptList.front();
            attemptList.pop_front();
            size = attemptList.size();

            std::cout << password << std::endl;
            mutex.unlock();
        }
    }
}

void enqueue_passwords(const std::string& charList) {
    const int maxLength = MAX_LENGTH;
    const int charListLength = charList.length();

    char password[MAX_LENGTH + 1];
    memset(password, '\0', MAX_LENGTH + 1);

    int index;
    int number;

    double permutations = 0;

    double count = 0;
    double passPosition = 0;
    double size = 0;

    // Calculate number of permutations possible
    for (index = 0; index < maxLength; index++) {
        permutations += charListLength * powl(charList.length(), maxLength - index - 1);
    }

    std::cout << "Permutations:  " << permutations << std::endl << std::endl;

    password[0] = charList[0];
    while (count < permutations) {
        do {
            mutex.lock();
            size = attemptList.size();
            mutex.unlock();

            if (size > MAX_QUEUE_SIZE) {
                usleep(250);
            }
        } while (size > MAX_QUEUE_SIZE);

        // Loop over current set of characters ,changing the last one
        for (index = 0; index < charListLength; index++) {
            password[int(passPosition)] = charList[index];

            // ENQUEUE HERE //
            mutex.lock();
            attemptList.push_back(std::string(password));
            mutex.unlock();
            // ENQUEUE HERE //

            if (count > permutations) {
                break;
            }
            count++;
        }

        // Iterate over remaining indexes, except for the last one
        for (number = int(passPosition); number >= 0; number--) {
            if (password[number] != charList[charListLength - 1]) {
                password[number]++;
                break;
            } else {
                if (number == 0) {
                    passPosition++;
                    for (index = 0; index < passPosition + 1; index++) {
                        password[index] = charList[0];
                    }
                    break;
                }
                password[number] = charList[0];
            }
        }
    }

    conclude = true;
}

void do_join(std::thread& t) {
    t.join();
}

void join_all(std::vector<std::thread>& v) {
    std::for_each(v.begin(), v.end(), do_join);
}

person gofish    schedule 19.04.2019    source источник
comment
Извините, я недостаточно ясно выразился в вопросе. Это один из дочерних потоков, который вызывает ошибку seg, когда он пытается прочитать передний элемент, но возвращает null.   -  person gofish    schedule 19.04.2019
comment
Вы должны использовать только одну блокировку для получения значения из очереди, это устранит состояние гонки и сделает его более эффективным, и вам лучше использовать std::condition_variable для синхронизации   -  person Slava    schedule 19.04.2019
comment
Является ли условная переменная похожей на сефафор в c?   -  person gofish    schedule 19.04.2019
comment
Не совсем, семафор более общий и может использоваться как мьютекс и/или условная переменная. Переменная условия специально предназначена для этой конкретной цели - синхронизировать доступ к общему ресурсу и сигнализировать, когда ресурс доступен.   -  person Slava    schedule 19.04.2019


Ответы (2)


   do {
        mutex.lock();
        size = attemptList.size();
        mutex.unlock();

        if (size == 0) {
            usleep(300);
        }
    } while (size == 0);

Оставляя в стороне проблему эффективности, этот код блокирует мьютекс, получает размер списка и разблокирует мьютекс.

Допустим, поток пришел к выводу, что размер списка равен 1, и, следовательно, поток выходит из этого цикла. size равно 1. На данный момент список имеет только одно значение. Цикл while завершается.

Но прежде чем продолжить, один из ваших других потоков, который делает точно то же самое, в этот момент, одновременно: он блокирует мьютекс, получает размер списка, разблокирует мьютекс, определяет, что размер списка 1, и также выходит из цикла while, как и первый поток. Давайте посмотрим, что произойдет дальше, с обоими нашими потоками сейчас:

    while(size != 0) {
        mutex.lock();
        password = attemptList.front();
        attemptList.pop_front();

Итак, первый поток теперь просыпается, входит в цикл while, блокирует мьютекс, захватывает единственную запись в списке, удаляет ее из списка, и теперь список пуст.

Ваш второй поток теперь делает то же самое и блокирует свой вызов mutex.lock(), потому что первый поток заблокировал его.

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

Неопределенное поведение.

Это причина твоего сбоя.

person Sam Varshavchik    schedule 19.04.2019

Как уже объяснил Сэм, двойная блокировка мьютекса делает ваш код менее эффективным и в то же время создает состояние гонки. Возможным решением может быть (внутренний цикл для извлечения данных):

while( !conclude ) {
    std::string password;
    {
        std::lock_guard<std::mutex> lock( mutex );
        if( attemptList.size() ) {
           password = std::move( attemptList.front() );
           attemptList.pop_front();
        }
    }
    if( password.empty() ) {
        usleep(300);
        continue;
    }
    // work with password here
}

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

Этот код должен работать, но спящий режим — не лучший способ синхронизации потоков в этом случае, вместо этого вы должны использовать std::condition_variable. И ваша переменная conclude должна быть проверена под блокировкой мьютекса или должна быть как минимум std::atomic<bool>.

person Slava    schedule 19.04.2019