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

Это мой первый раз, когда я использую мьютексы, поэтому я не совсем уверен в том, что я делаю, но я думаю, что у меня ошибка с безопасностью потоков функции push_back с использованием векторного контейнера (у меня есть несколько потоков, записывающих в него одновременно time и получаю эту ошибку): * glibc обнаружен * ./quicksort: двойное освобождение или повреждение (out): 0x00007f2638000980 *

Чтобы решить эту проблему, я добавил мьютекс, но, похоже, он ничего не сделал, код здесь:

void parallel_quicksort(vector<int>& input)
{
    boost::mutex mutex;
    queue<pr_pair> partitions, temp_partitions;
    vector<pr_pair> jobs;
    parallel_partition(input, partitions, 0, input.size());
    pr_pair temp;
    while(1)
    {
        boost::thread_group threadpool;

        while(!partitions.empty())
        {
            temp = partitions.front();
            partitions.pop();
            jobs.push_back(temp);

            if (jobs.size() == NUM_THREADS)
            {
                for (int i = 0; i < NUM_THREADS; i++)
                {
                    temp = jobs.back();
                    jobs.pop_back();
                    threadpool.create_thread(boost::bind(&parallel_partition, boost::ref(input), boost::ref(temp_partitions), temp.p, temp.r));
                }
                threadpool.join_all();
            }
        }

        while(!jobs.empty())
        {
            temp = jobs.back();
            jobs.pop_back();
            threadpool.create_thread(boost::bind(&parallel_partition, boost::ref(input), boost::ref(temp_partitions), temp.p, temp.r));
        }
        threadpool.join_all();

        while(!temp_partitions.empty())
        {   
            temp = temp_partitions.front();
            partitions.push(temp);
            temp_partitions.pop();
        }   

        if(partitions.empty())
        {   
            break;
        }   
    }   

    return;
}

void parallel_partition(vector<int>& input, queue<pr_pair>& partitions, int p, int r)
{
    int p_store = p;
    int r_store = r;
    int pivot = input[r];

    while (p<r)
    {
        while (input[p] < pivot)
            p++;
        while (input[r] > pivot)
            r--;
        if (input[p] == input[r])
            p++;
        else if (p<r)
        {
            int tmp = input[p];
            input[p] = input[r];
            input[r] = tmp; }
    }
    pr_pair temp;
    if (r-1 > p_store)
    {
        boost::mutex::scoped_lock scoped_lock(mutex);
        temp.p = p_store;
        temp.r = r-1;
        partitions.push(temp);
    }
    if (r_store > r+1)
    {
        boost::mutex::scoped_lock scoped_lock(mutex);
        temp.p = r+1;
        temp.r = r_store;
        partitions.push(temp);
    }
    return;
}

person Dan    schedule 08.05.2014    source источник


Ответы (1)


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

person Martijn Wijns    schedule 28.05.2014