LXF94:Mono

Версия 13:04, 12 марта 2008

Mono: Работаем с потоками

Два ядра позволяют сделать больше – по крайней мере, так уверяет отдел маркетинга Intel. Проверим это вместе с Полом Хадсоном.

Дивлюсь я на мою жену. Я при переходе улицы с трудом успеваю поглядеть в обе стороны, а она способна гладить, говорить по телефону и смотреть телевизор одновременно. Она правда думает обо всем сразу, или ее мозг мгновенно переключается с задачи на задачу?

Долгое время компьютеры были ограничены только последним вариантом. На вашей системе Linux одновременно работает около 100 программ. Вам видны лишь некоторые из них, вроде X или Nautilus, но есть еще и другие – апплет громкости, syslogd, Metacity, D-BUS, Cron и так далее. Большую часть времени они бездействуют в фоновом режиме, но когда два или более вступают в дело одновременно, ваш процессор начинает ими жонглировать. Обычный стандартный процессор без включенного Hyperthreading может выполнять только один процесс в заданный момент времени.

Чтобы избежать подвисания при запуске OpenOffice, каждый процесс получает период времени – доли секунды, обычно менее 100 мс – на выполнение кода. По истечении этого времени процесс приостанавливается, и свой квант времени получает другая программа. Если квант равен 100 мс, то за секунду успевают поработать десять различных программ; человеку за этим не уследить, и ему кажется, что все они работают одновременно.

Так продолжалось много лет; но на новых двух- и многоядерных чипах от AMD и Intel или любой старой SMP-системе с двумя физическими одноядерными процессорами все по-другому. Эти устройства могут действительно исполнять множество процессов сразу, благодаря наличию нескольких чипов: двухъядерный чип может выполнять два процесса одновременно, а четырехъядерный – четыре. Внутри процесса работают «потоки», которые представляют собой отдельные задачи внутри программы, способные работать параллельно с другими задачами. Однако даже самый красивый и изящный в мире код на C#, содержащий только один поток, использует всего четверть от четырехъядерной мощи.

На нашем уроке вы изучите, как создавать потоки в Mono, для запуска приложения одновременно на нескольких ядрах. Чтобы сделать тему более захватывающей, создадим «взломщика» хэшей SHA1. SHA1 – это алгоритм хэширования, спроектированный для создания 40- символьной уникальной последовательности битов из входного текста. Хэши обычно используются для проверки целостности информации – если вы скачаете 4-ГБ образ DVD, у которого искажен 1 КБ информации, то полученный хэш SHA1 будет совершенно отличаться от исходного. SHA1 и другие функции часто используются для хранения паролей, так как исходное значение пароля по хэшу не восстановить – хотя можно генерировать SHA1-ключи для всех возможных строк, чтобы увидеть совпадения. Но сначала займемся чем-нибудь попроще.

Попасть в квадрат

Первым нашим проектом этого урока будет возведение в квадрат 1000 чисел. Мы начали с такого примера, потому что его очень легко распараллелить: не требуется обмена данных между потоками. Создайте новое консольное C# приложение в MonoDevelop, назовите его Hackaday и поместите следующую строчку вверху его cs-файла:

using System.Threading;

Магическая строка using позволит нам использовать потоки. Нам также потребуется 4 переменных: одна будет отслеживать, сколько чисел надо создавать, другая будет отвечать за количество потоков, третья установит, сколько чисел генерировать на поток, а четвертая будет хранить генератор случайных чисел. Без первых трех переменных на самом деле можно обойтись, записав их как константы, но потом с ними уже не поиграешь!

Итак, добавьте четыре переменных до определения метода static void Main():

static int NumsToGenerate = 1000;
static int NumThreads = 4;
static int NumsPerThread;
static Random Rand = new Random();

Начинается настоящее дело: создание потоков. Каждый созданный поток будет выполнять метод, который определим мы. Метод может быть каким угодно, принимать любые параметры и даже вызывать другие методы. Но пока будем проще: пусть каждый поток пробегает в цикле от 0 до NumPerThread, генерирует число от 1 до 1000, затем возводит в квадрат и выдает результат.

Вот этот метод:

static void DoFunk() {
  for (int i = 0; i < NumsPerThread; ++i) {
   int num = Rand.Next(1, 1000);
   Console.WriteLine(“Thread #{0} says: {1} squared is {2}”,
   Thread.CurrentThread.Name, num, num * num);
  }
 }

DoFunk() – не очень конкретное имя, но так как мы будем использовать его во многих программах, сойдет и оно! Основная идея в том, что каждый их четырех потоков будет прокручивать 250 случайных чисел и выдавать квадрат каждого из них. Каждый поток будет ссылаться сам на себя с помощью Thread.CurrentThread, и в этом случае мы считываем Name – строку, назначаемую каждому потоку для упрощения отладки.

Синтаксис {0}, {1}, {2} – просто быстрый способ написать сложные вызовы WriteLine() за один раз: Mono автоматически подставляет параметры, то есть замещает {0} на Thread.CurrentThread.Name, {1} на num, {2} на результат num*num.

Остается только метод Main(), которому надо вычислить, сколько чисел должен обработать каждый поток, затем создать потоки и запустить их. При создании каждого потока в его конструктор передается имя метода, который мы хотим запустить. Вы все поймете, взглянув на код – вот он:

static void Main(string[] args) {
 NumsPerThread = NumsToGenerate / NumThreads;
 for (int i = 0; i < NumThreads; ++i) {
  Thread thread = new Thread(DoFunk);
  thread.Name = Convert.ToString(i);
  thread.Start();
  }
 }

Итак, считая от 0 до 4, создадим поток и велим ему запустить метод DoFunk(), а назовем его по номеру итерации, на которой он создается. Хотя все потоки будут созданы, ни один их них не запустится до тех пор, пока не будет вызван метод thread.Start(), после которого они начнут выполнять методы DoFunk(). Нажмите F5, чтобы собрать и запустить программу, и увидите вихрь чисел в окне вывода результатов.

Разделяй и… разделяй

Вы заметите четыре важных момента в работе программы:

• 1 Каждый поток имеет доступ к генератору случайных чисел Rand и NumThreads, потому что они помечены как ‘static’, то есть каждый поток может читать и писать их.
• 2 Каждый поток создает собственные случайные числа. Это потому, что переменная num объявлена локально в каждом потоке, поэтому у них есть по копии этой переменной, чтобы ей управлять.
• 3 При выводе программы вы заметите, что потоки не выводят каждый по строке, типа 012301230123. Более вероятно, что сначала поток 0 напечатает десять строк, затем поток 1 напечатает 10 строк, и так далее, то есть 0000000000111111111122222222223333333333.
• 4 Программа hackaday.exe ждет, пока все потоки не закончат свою работу.

Пункт 1 показывает, что потоки могут иметь общие переменные. В этом разница между процессами и потоками: порождаемые процессы независимы, а потоки разделяют большинство своих данных. Исключения составляют переменные, объявленные локально, как, например, num. Пункт 3 иллюстрирует то, что говорилось о квантах времени выше: каждый поток получает свой квант и исчерпывает его, чтобы передать работу следующему потоку.

Пункт 4 возник потому, что по умолчанию .NET создает не фоновые (foreground) потоки и не позволит завершить программу, пока они не отработают. Фоновые потоки, напротив, автоматически заканчивают работу, когда завершается родительский процесс. Попробуйте перед thread.Start() набрать thread.isBackground=true; затем перезапустите программу. На этот раз программа завершится быстрее: создав все потоки, Main() завершится, и потоки автоматически ликвидируются.

Сконцентрируемся на пункте 1, так как вопрос разделения данных – один из самых сложных. На техноязе то, чем мы занимаемся, называется потокобезопасность, и означает, что ваше приложение не сломается, если два потока попытаются сделать одно и то же в один момент. Что если два потока вдвоем примутся читать статическую переменную? Чтение переменных менее проблемно, но тоже небезопасно: легко нарваться на «состояние гонки» [race condition]. Не буду объяснять, что это такое, сейчас: из кода все станет ясно.

Для начала попробуем безопасным образом писать в переменные из потока. Наш старый код генерировал случайные числа для возведения в квадрат, но сейчас мы собираемся создать список из целых чисел (об этом см. [LXF92|LXF92]), и каждый поток будет считывать первый элемент из списка, удалять его и затем возводить в квадрат. Нам не нужна ситуация, когда все четыре потока прочитают первый элемент, затем поток 0 удалит его, поток 1 примется удалять следующий элемент, поток 2 – еще один, а поток 3 – еще один, и выйдет, что мы сосчитали квадрат для первого числа 4 раза, уничтожили 2-й, 3-й и 4-й элементы, сосчитали квадрат для 5-го элемента… и так далее.

C# позволяет легко разрешить эту проблему с помощью выражения lock, отмечающего критические секции кода. Внутри критического блока в заданный момент времени может находится только один поток. Любой другой поток, дойдя до lock-секции, будет ждать, пока первый поток не выйдет из нее. Отсюда следует, что нам надо блокировать любые общие переменные, прежде чем изменять их, чтобы предотвратить двойные изменения.

Блокировка потоков

В белых перчатках

Вот так параллельность!

Мы здесь обсуждаем так называемые «ошеломляюще параллельные» алгоритмы, которые хорошо распределяются по процессорам, так как каждая операция абсолютно не зависит от остальных. Как легко представить, не много задач попадает в эту категорию: физика частиц – да, фракталы – да, и несколько других классов. А вот со сжатием видео уже не все просто, потому что большинство кодеков кодируют изменения с предыдущего кадра, и вы не можете сжать кадр до того, как был обработан предыдущий. Использование ключевых кадров смягчает проблему, но есть задачи – в основном криптография, поблочное шифрование с обратной связью – которые нипочем не распараллелить.

И все-таки не беспокойтесь, если ваше приложение не может быть распараллелено на 100%. Если вы создали шахматную программу, которая выполняет в одном потоке все, кроме ИИ компьютера, который в фоновом потоке будет искать наилучший ход, это уже неплохо.

Представляем SHA2

SHA1 – не особенно сильный алгоритм хэширования, и он уже не рекомендуется экспертами по безопасности. Однако С# предлагает поддержку для более мощных хэш-функций, включая семейство SHA2 с невероятно сильным SHA512. Конечно, имейте в виду, что наша «лобовая атака» годится только для паролей, так как у большинства пользователей пароли короче 8 символов. На попытку найти совпадение для более длинного сообщения, например, электронного письма, потребовались бы годы.