Форум программистов, компьютерный форум CyberForum.ru

Многопоточная сортировка: синхронизация - C++

Восстановить пароль Регистрация
 
mishula
0 / 0 / 0
Регистрация: 01.10.2014
Сообщений: 81
27.03.2016, 15:22     Многопоточная сортировка: синхронизация #1
Добрый день, только начал изучать параллельное программирование и решил написать параллельную битоническую сортировку. Суть её в том, что за одну итерацию мы проходим по массиву 2 раза, первый раз переставляя 1 и 2, 3 и 4 и т.д., а второй раз переставляем 2 и 3, 4 и 5 и т.д.
Как я понимаю, нужно использовать n/2 потоков, если всего в массиве n элементов. После прохождения в первый раз массива нужно все подождать все потоки, чтобы вывести промежуточные результаты и затем сортировать со второго элемента. Но с этой синхронизацией у меня и возникли проблемы, несмотря на то, что разделяемых объектов нет и мьютексы использовать не нужно. Вот мой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <thread>
#include <vector>
#include <iostream>
 
 
void compareAndSwap(std::vector<int> &v, int i) {
    if (v[i] > v[i + 1])//если 10 элементов сортирую, то пишет standart c++ libraries out of range
    {
        int t = v[i];
        v[i] = v[i + 1];
        v[i + 1] = t;
    }
}
class Storage {
 
    std::mutex _mu1;
public:
    Storage() {
        std::cout << "I'm created!" << std::endl;
    }
    ~Storage() {
        data.clear();
        std::cout << "I'm die!" << std::endl;
    }
    int Size() {
        return data.size();
    }
    void sort() {
        
        std::vector<std::thread>th;
        for (int k = 0; k < data.size(); ++k)
        {
 
            for (int i = 0, j = 0; i < th.size() - 1; i += 2, j++)
            {
                th.push_back(std::thread(compareAndSwap, std::ref(data), i));
                if (th[j].joinable())
                    th[j].join();
            }
                
            th.clear();
            std::cout << *this;//почему-то если написать cout<<data, то пишет, что нет оператора вывода, соотв двум операндам
            //Print(x, l);
            for (int j = 1, i = 0; j < data.size(); j += 2, i++)
            {
                th.push_back(std::thread(compareAndSwap, std::ref(data), j));
                if (th[i].joinable())
                    th[i].join();
            }
            th.clear();
            std::cout << *this;//почему-то если написать cout<<data, то пишет, что нет оператора вывода, соотв двум операндам
        }
    }
    void pushToData(int num) {
        data.push_back(num);
    }
    friend std::ostream& operator<<(std::ostream &os, Storage &st) {
        for (int i = 0; i < st.data.size(); i++){
             os<< st.data[i]<<" ";
        }
        return std::cout << std::endl;
    }
private:
    std::vector<int>data;
 
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int x;
    Storage st;
    while (std::cin >> x) {
        st.pushToData(x);
    }
    const int size = st.Size();
    st.sort();
    std::cout << st;
    system("pause");
    
    return 0;
}
Если элементов меньше 10, то сортировка просто идет неправильно, однако если 10 и более, то выводит ошибку expression subscript out of range. Помогите, пожалуйста, решить с этим проблему и по возможности покажите, как можно бы было в моем примере один и тот же поток использовать несколько раз, так как если написать
C++
1
th[i](compareAndSwap, std::ref(data), i);
, то пишет term doesn't evaluate to a function, taking 3 arguments.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.03.2016, 15:22     Многопоточная сортировка: синхронизация
Посмотрите здесь:

многопоточная программа C++
C++ Синхронизация
Синхронизация доступа C++
C++ Синхронизация потоков в c++
Синхронизация мьютекс C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
cordfield
33 / 33 / 13
Регистрация: 04.05.2014
Сообщений: 148
27.03.2016, 16:21     Многопоточная сортировка: синхронизация #2
Как я понимаю, нужно использовать n/2 потоков, если всего в массиве n элементов
Это точно неправильный подход. А если элементов миллион, создавать 500 000 потоков?
Обычно создают столько потоков, сколько ядер у процессора. Большее количество потоков компьютер одновременно выполнять не сможет (будет происходить переключение процессора с выполнения одного потока на выполнение другого потока).

Зачем создавать поток и сразу после этого ожидать, когда он завершится (выполнять join)? У вас всё равно одновременно не больше 1 потока будет выполняться.

Попробуйте сначала написать однопоточную программу, выполняющую вашу задачу.
mishula
0 / 0 / 0
Регистрация: 01.10.2014
Сообщений: 81
27.03.2016, 16:38  [ТС]     Многопоточная сортировка: синхронизация #3
cordfield, вот я не понимаю, если я в начале объявил объект-поток
C++
1
(std::thread th;
), а потом хочу запустить в этом потоке функцию(
C++
1
th(compareAndSwap, std::ref(data), i);
), то у меня подчеркивает строчку и выводит ошибку call of an object of a class without appropriate function () or conversation to poiter-to-function type.
cordfield
33 / 33 / 13
Регистрация: 04.05.2014
Сообщений: 148
27.03.2016, 16:54     Многопоточная сортировка: синхронизация #4
mishula, стандартные потоки не такие умные. Им можно сказать только при их создании, какую функцию выполнять. Как только произойдёт выход из этой функции, поток завершится.

Можно создать так называемый "thread pool". Он состоит из N потоков и очереди задач. Каждый поток, когда свободен, ждёт появление задачи в очереди. Когда задача появляется, поток берёт её из очереди и выполняет. Когда задач нет, завершения потока не происходит, а вызывается функция ожидания появления задач в очереди.
Yandex
Объявления
27.03.2016, 16:54     Многопоточная сортировка: синхронизация
Ответ Создать тему
Опции темы

Текущее время: 18:05. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru