Всем привет.
В общем я решил серьезно подойти к вопросу многопоточности и начать скрупулезно ее изучать.(Без нее нынче никак)
Сейчас дочитываю последние главы книги CLR via C# Рихтера. Но мне маловато. Хочу больше информации о многопоточности, попрактиковаться в задачах, мб узнать идиомы.
Задачи, идиомы, полезные моменты при изучении.
Сейчас у меня в основном теоретические знания.

Здравствуйте, -n1l-, Вы писали:

http://www.rsdn.ru/forum/dotnet/5167296.flat#5167296

Автор: Sharov
Дата: 13.05.13

Здравствуйте, -n1l-, Вы писали:

N>Всем привет.
N>В общем я решил серьезно подойти к вопросу многопоточности и начать скрупулезно ее изучать.(Без нее нынче никак)
N>Сейчас дочитываю последние главы книги CLR via C# Рихтера. Но мне маловато. Хочу больше информации о многопоточности, попрактиковаться в задачах, мб узнать идиомы.
N>Задачи, идиомы, полезные моменты при изучении.
N>Сейчас у меня в основном теоретические знания.

Напиши сортировку пузырьком многопоточную

Здравствуйте, -n1l-, Вы писали:

N>Всем привет.
N>В общем я решил серьезно подойти к вопросу многопоточности и начать скрупулезно ее изучать.(Без нее нынче никак).

Хороших книг не попадалось, практические нюансы есть в pfx team blog, но найти там что либо — задача нетривиальная.

Здравствуйте, Tom, Вы писали:

Tom>Здравствуйте, -n1l-, Вы писали:

N>>Всем привет.
N>>В общем я решил серьезно подойти к вопросу многопоточности и начать скрупулезно ее изучать.(Без нее нынче никак)
N>>Сейчас дочитываю последние главы книги CLR via C# Рихтера. Но мне маловато. Хочу больше информации о многопоточности, попрактиковаться в задачах, мб узнать идиомы.
N>>Задачи, идиомы, полезные моменты при изучении.
N>>Сейчас у меня в основном теоретические знания.

Tom>Напиши сортировку пузырьком многопоточную

А чем она должна отличаться от однопоточной? Тем, что должна сортировать одну коллекцию в несколько потоков?

Здравствуйте, -n1l-, Вы писали:

N>Сейчас дочитываю последние главы книги CLR via C# Рихтера. Но мне маловато.

Попробуйте заменить "многопоточность" на "Кунг-фу" и даже вам станет очевидной смехотворность вашего "пути". Думаете, если начитаетесь "умных книжек", то всё, останется только сесть за ПК? Ха-ха! >:] *это такой злорадный смех*
Если вы не написали ничего по своей задаче, даже Introduction для вас должно быть много! Без практики ваша теория — потерянное время и ложное ощущение профессионализма. Работаем так:

1. Читаем, слегка въезжаем в тему
2. Пробуем, понимаем окончательно
3. Находим новые аспекты и к п.1

N>Задачи, идиомы, полезные моменты при изучении.

Вряд ли вы найдёте какие-то дотошные объяснения по конкретным приёмам или примерам. Обычно как: есть теория, которую знают все. Потом каждый садится писать своё детище. Получает граблями, бежит на форумы, там спрашивает один небольшой аспект и опять возвращается к своей большой задаче. Так что пока вы не начнёте писать, вы даже не поймёте того, чего ещё не знаете.

Вот интересная задача: возьмите арифметическое выражение и сделайте распределённый калькулятор. Причём каждый узел должен уметь получать задания параллельно работе. А потом центральный узел всё собирает.

Здравствуйте, matumba, Вы писали:

N>>Задачи, идиомы, полезные моменты при изучении.
M>Вряд ли вы найдёте какие-то дотошные объяснения по конкретным приёмам или примерам. Обычно как: есть теория, которую знают все. Потом каждый садится писать своё детище. Получает граблями, бежит на форумы, там спрашивает один небольшой аспект и опять возвращается к своей большой задаче. Так что пока вы не начнёте писать, вы даже не поймёте того, чего ещё не знаете.

Ну, вообще есть книги. Например, вот эта — ссылка на PDF. Но без "своей большой задачи" ее читать оооочень муторно

Здравствуйте, Ilinichev, Вы писали:

I>Ну, вообще есть книги.

Вообще есть даже Единая Рассея. Как это поможет человеку изучить предмет, если он ни черта его не применяет? Практика! Все на поля!

Не могу открыть.

Здравствуйте, -n1l-, Вы писали:

N>Не могу открыть.

Pattern-Oriented Software Architecture, Patterns for Concurrent and
Networked Objects, Volume 2
by Douglas Schmidt, Michael Stal, Hans Rohnert and Frank Buschmann
ISBN: 0471606952
John Wiley & Sons © 2000 (633 pages)
An examination of 17 essential design patterns used to build modern objectoriented middleware systems.

Спасибо.

Здравствуйте, Tom, Вы писали:
Tom>Напиши сортировку пузырьком многопоточную

Написал. Хочу спросить, какие недостатки есть?
И еще, можно ли как-то свап сделать без приведения к объекту?

    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new[] { 2, 4, 7, 3, 6, 9, 10, 14, 17, 21 };

            ThreadPool.QueueUserWorkItem(BubbleSort, arr);
            string result = string.Join(",",arr.Select(x=>x.ToString()).ToArray());
            Console.WriteLine(result);
            Console.ReadLine();

        }

        static void BubbleSort(object context)
        {
            bool sorted;
            int[] array = (int[]) context;

            do
            {
                sorted = true;

                for (int i = 0; i < array.Length-1; i++)
                {
                    if (array[i] > array[i + 1])
                    {
                        Swap(ref array[i], ref array[i+1]);
                        sorted = false;
                    }
                }
                
            } while (!sorted);
            
        }

        static void Swap(ref int a, ref int b)
        {
            a ^= b;
            b ^= a;
            a ^= b;
        }

    }

Здравствуйте, -n1l-, Вы писали:

N>И еще, можно ли как-то свап сделать без приведения к объекту?
Не так выразился. Хочу операцию свапа выполнять тоже в отдельном потоке, как это лучше сделать взяв поток из пула?
или новый создать? Или может еще какие варианты?
Вообще вижу, что ThreadPool не очень подходит для таких задач и вообще для небольших проектов.

Здравствуйте, -n1l-, Вы писали:

Tom>>Напиши сортировку пузырьком многопоточную
N>Написал. Хочу спросить, какие недостатки есть?

Один маленький недостаток: это НЕ многопоточная сортировка. Тупо вызов плоской сортировки вставлен в трэд.
Многопоточная — когда несколько процессов обрабатывают данные. Например, пока идёт первый прогон поиска минимального элемента, второй уже может начинать работу, "бежа" за первым (и надо следить, чтоб не обогнал! ).

Здравствуйте, Tom, Вы писали:

Tom>Напиши сортировку пузырьком многопоточную

Зачетно троллишь! Многопоточный пузырек... Там на синхронизацию расходы будут выше крыши. Если ТС хочет написать многопоточную сортировку — пусть реализует любую из них, построенную на принипе разделения, например, сортировку слиянием.

Здравствуйте, matumba, Вы писали:

M>Один маленький недостаток: это НЕ многопоточная сортировка. Тупо вызов плоской сортировки вставлен в трэд.
M>Многопоточная — когда несколько процессов обрабатывают данные. Например, пока идёт первый прогон поиска минимального элемента, второй уже может начинать работу, "бежа" за первым (и надо следить, чтоб не обогнал! ).

Именно. Как я уже выше указал, хочу выполнять swap в отдельном потоке. Но создавать каждый раз новый поток не хочу. Хочу пользоваться пулом потоков.
Подскажите пожалуйста мне как мне это воплотить в реальность?

Здравствуйте, -n1l-, Вы писали:

N>Здравствуйте, Tom, Вы писали:
Tom>>Напиши сортировку пузырьком многопоточную

ИМХО, совет был правильным, но судя по ответу топик-стартера, нужно было дать его в более развернутым виде

Совет, видимо, должен был быть таким:
"Напиши сортировку пузырьком многопоточную и сравни ее с однопоточной с точки зрения эффективности и сложности".
(И еще, а насколько пузырьковая сортировка параллелится? Мне кажется, что это сверх сложная задача для параллелизма; та же быстрая или вставками, ИМХО, будут более подходящими для распараллеливания).

Многопоточность — это же не сферический конь, нужный сам по себе; это штука, которая за счет увеличения сложности кода (а значит и его сопровождаемости) дает возможность полноценно использовать возможности современных многоядерных процессоров.

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

— Concurrency — несколько "процессов" исполняются в один момент времени. Это наиболее общий термин, который даже не предполагает наличие нескольких вычислительных устройств; например, я работаю на двух работах — это concurrency, при этом я не работаю на двух работах в один момент времени, а просто переключаюсь с одной работы на другую раз в два дня.

— Параллелизм (parallel computing) — одновременное выполнение нескольких задач за счет наличия более одного вычислительного устройства (процессора, ядра процессора и т.д.). Это более строгое понятие, чем concurrency, поскольку говорит не просто о выполнении двух и более задач, а о выполнении двух и более задач непосредственно в один момент времени.

— Многопоточность (multithreading) — наличие нескольких логических потоков исполнения; это один из способов обеспечения конкурентности за счет использования потоков — как примитивов операционной системы. Многопоточность не связана напрямую с параллелизмом, хотя и может быть одним из средством его обеспечения. Так, за счет многопоточности на однопроцессорной машине мы сможем обеспечить concurrency, но не сможем обеспечить параллелизм (даже на однопроцессорном компьютере у нас может быть куча запущенных процессов, и concurrency обеспечивается операционной системой за счет высокой частоты переключения контекста исполнения между разными потоками, при этом никакого "параллельного" исполнения не происходит).

— Асинхронность (asynchrony) — это возможность продолжить основной поток испольнения, когда некоторая второстепенная задача выполняется в фоне. При этом под фоном может пониматься другой поток или выполнение операций ввода-вывода, которые вообще не требуют вычислительных ресурсов.

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

Изучение этой непростой темы я бы советовал начать со статьи Герба Саттера "The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software", которая даст понять, почему "мир изменился" и все начали так интенсивно интересоваться этой темой.

А для продолжения, можно посмотреть чего-то из списка ниже:

Книги
Joe Duffy — Concurrent Programming on Windows — одна из лучших книг по этой теме.
Patterns for Parallel Programming: Understanding and Applying Parallel Patterns with the .NET Framework 4 by Stephen Toub
Parallel Programming with Microsoft .NET by Colin Campbell et al
Windows via C/C++ by Jeffrey Richter — это если нужно с более низкоуровневой привязкой к винде.
Хороший раздел по многопоточности есть в книге "C# in the Nutshell" Джо Албахари, перевод которого можно найти и на rsdn в 3-х частях (1

Автор(ы): Joseph Albahari
Дата: 24.03.2007
Подробно рассматривается работа с потоками — запуск, завершение, прерывание, блокировки, синхронизация, контексты синхронизации, особенности взаимодействия с апартаментами, а также потоковые возможности .NET — потоковые таймеры, пулы потоков, BackgroundWorker, асинхронные методы и делегаты.
В статье использован материал из книги Joseph Albahari, Ben Albahari "C# 3.0 in a Nutshell" — http://www.oreilly.com/catalog/9780596527570/

, 2

Автор(ы): Joseph Albahari
Дата: 27.06.2007
Окончание статьи, опубликованной в RSDN Magazine #1-2007. Рассматриваются особенности взаимодействия с апартаментами, потоковые таймеры, пулы потоков, BackgroundWorker, асинхронные методы и делегаты.
В статье использован материал из книги Joseph Albahari, Ben Albahari "C# 3.0 in a Nutshell" — http://www.oreilly.com/catalog/9780596527570/

, 3

Автор(ы): Joseph Albahari
Дата: 28.07.2011
В третьей части статьи рассматривается Parallel LINQ, класс Parallel, конструкции параллелизма задач, параллельные коллекции, а также структуры SpinLock и SpinWait. В статье использован материал из книги Joseph Albahari, Ben Albahari "C# 4.0 in a Nutshell" —  http://oreilly.com/catalog/9780596800963

).

Блоги/статьи
Вся серия Саттера "Effective Concurrency"
Избранные сообщения камрада remark-а
Его же сайтецкий 1024 cores
Блог pfxteam-а

По идее должно хватить на первое время

N>Написал. Хочу спросить, какие недостатки есть?

Исходня из описания выше, ты должен сам ответить на свой вопрос: к какому из приведенных четырех типов параллелизма относится твое решение? Я вижу, что оно асинхронное, но явно не "параллельное". При этом ты добавил кучу проблем, не решив ни одной исходной. Главной бедой (ладно, одной из главных) многопоточности и параллелизма является гонки или борьба за разделяемые ресурсы, которая у тебя проявляется во всей красе!

Видимо, ты либо ни разу не запускал свою программу, либо не внимательно смотрел на результат (поскольку входные даные твои "почти" отсортированы), либо у тебя одноядерная машинка, на которой проблема не воспроизводится (вспоминаем о разнице между многопоточностью и параллелизмом). Я, например, при запуске вижу следующее: "2,4,7,3,6,9,10,14,17,21", что сложно рассматривать, как корректный результат.

N>И еще, можно ли как-то свап сделать без приведения к объекту?

Ты точно за свап говоришь, а не за свой метод BubleSort, который кастит контекст?

Я бы, подходя к этому решению постарался бы сразу сделать вменяемый API сортирвки (глянув на тот же LINQ-овский OrderBy), а затем сравнил бы эффективность своего решения со "стандартным" — с PLINQ-овским OrderBy.

Здравствуйте, -n1l-, Вы писали:

N>Именно. Как я уже выше указал, хочу выполнять swap в отдельном потоке.

У тебя ЭТО что ли самая сложная операция?? Подумай над задачей в целом и чего ради делается многопоточность. Подсказка: точно не для swap

Здравствуйте, matumba, Вы писали:

M>У тебя ЭТО что ли самая сложная операция?? Подумай над задачей в целом и чего ради делается многопоточность. Подсказка: точно не для swap

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

Здравствуйте, SergeyT., Вы писали:

ST>Совет, видимо, должен был быть таким:
ST>"Напиши сортировку пузырьком многопоточную и сравни ее с однопоточной с точки зрения эффективности и сложности".
Однопоточная сортировка пузырьком проще пишется, но медленнее выполняется. У меня нет в коде разделения задачи на потоки, я как бы разделил вычисления и пользовательский интерфейс, так что у меня асинхронное выполнение программы.

ST>(И еще, а насколько пузырьковая сортировка параллелится? Мне кажется, что это сверх сложная задача для параллелизма;
Я, пока что, еще не знаю что конкретно от меня хотят видеть в качестве многопоточной сортировки пузырьком. Но исходя из сообщений выше, думаю это будет архисложно и жутко запутанно.


ST>При этом ты добавил кучу проблем, не решив ни одной исходной. Главной бедой (ладно, одной из главных) многопоточности и параллелизма является гонки или борьба за разделяемые ресурсы, которая у тебя проявляется во всей красе!
ST>Видимо, ты либо ни разу не запускал свою программу, либо не внимательно смотрел на результат (поскольку входные даные твои "почти" отсортированы), либо у тебя одноядерная машинка, на которой проблема не воспроизводится (вспоминаем о разнице между многопоточностью и параллелизмом). Я, например, при запуске вижу следующее: "2,4,7,3,6,9,10,14,17,21", что сложно рассматривать, как корректный результат.

Да, уверен, что вывод результата попросту выполнился перед сортировкой.
Быстронаписанный код, что бы привлечь в тему больше людей.

ST>Ты точно за свап говоришь, а не за свой метод BubleSort, который кастит контекст?
Он тоже далек от нормы.

ST>Я бы, подходя к этому решению постарался бы сразу сделать вменяемый API сортирвки (глянув на тот же LINQ-овский OrderBy), а затем сравнил бы эффективность своего решения со "стандартным" — с PLINQ-овским OrderBy.
Что вы понимаете под "api сортировки"? Метод расширения с linq подобным синтаксисом. Быть может. Первое, что я делаю, это решение в лоб.