LXF94:Mono

Версия 14:32, 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), и каждый поток будет считывать первый элемент из списка, удалять его и затем возводить в квадрат. Нам не нужна ситуация, когда все четыре потока прочитают первый элемент, затем поток 0 удалит его, поток 1 примется удалять следующий элемент, поток 2 – еще один, а поток 3 – еще один, и выйдет, что мы сосчитали квадрат для первого числа 4 раза, уничтожили 2-й, 3-й и 4-й элементы, сосчитали квадрат для 5-го элемента… и так далее.

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

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

Так как мы будем использовать коллекцию List, надо добавить новое выражение в секцию using:

using System.Collections.Generic;

Удалите все ранее определенные переменные и вставьте следующее:

static List<int> Numbers = new List<int>();

Метод Main() должен подготовить 2000 чисел для Списка. Так как мы удалили все переменные, число потоков будет зашито в программу в виде константы. Вот новый код Main():

public static void Main(string[] args) {
 for (int i = 0; i < 2000; ++i) {
  Numbers.Add(i);
 }
 for (int i = 0; i < 4; ++i) {
  Thread thread = new Thread(DoFunk);
  thread.Name = Convert.ToString(i);
  thread.Start();
 }
}

Серьезная работа возложена на метод DoFunk(): ему надо вытащить число из списка и возвести его в квадрат, блокировав при этом список Numbers, чтоб не вмешались другие потоки. Вот как выглядит код DoFunk():

while (Numbers.Count > 0) {
 lock (Numbers) {
  int Num = Numbers[0];
  Numbers.RemoveAt(0);
  Console.WriteLine(“Thread #{0} says: {1} squared is {2}”,
  Thread.CurrentThread.Name, Num, Num * Num);
 }
}

Цикл будет выполняться, пока в Numbers остаются числа. Но первым делом надо заблокировать список – lock(Numbers). Первый поток, который доберется до этого кода, обнаружит, что Numbers свободен, и заблокирует его. Другие потоки обнаружат, что Numbers заблокирован первым потоком, и не пойдут дальше, пока первый поток не снимет блокировку. Первый поток прочтет первое число, удалит его из списка, возведет в квадрат и выведет на экран, затем, достигнув конца блока lock, освободит Numbers. Второй поток обнаружит, что Numbers свободен, заблокирует его, выполнит свою работу, и так далее. Попробуйте запустить и посмотреть, что случится.

Все выглядит замечательно до тех пор, пока вы не дойдете до конца, когда вы увидите следующее:

Unhandled Exception: System.ArgumentOutOfRangeException:
Argument is out of range.
Parameter name: index
at System.Collections.Generic.List`1[System.Int32].get_Item
(Int32) [0x00000]
at hackaday.MainClass.DoFunk () [0x00000]
at (wrapper delegate-invoke) System.MulticastDelegate:invoke_
void ()

Китайская грамота, да? Что ж, так нам пытаются сообщить, что возникло «состояние гонки». То есть два потока (или более) параллельно пытаются достичь одного результата, и мы из-за непредсказуемой работы планировщика виртуальной машины получаем неожиданные результаты. Взгляните на код – в частности, на метод DoFunk(). Проблема находится в строке int Num = Numbers[0] – там, где вызывается внутренний метод Mono get_item(). Посмотрим, что здесь может вызвать проблему.

Нашли? Если нет, давайте я покажу, что происходит в случае двух потоков исполнения:

• 1 Поток 1: Numbers > 0.
• 2 Поток 1: Numbers свободен. Блокируем его.
• 3 Поток 2: Numbers > 0.
• 4 Поток 2: Numbers блокирован. Ждем.
• 5 Поток 1: Взять первое число, удалить, возвести в квадрат и вывести на экран.
• 6 Поток 1: разблокировать Numbers.
• 7 Поток 2: Numbers свободен. Блокировать его.
• 8 Поток 1: Numbers > 0.
• 9 Поток 1: Numbers блокирован. Ждем.
• 10 Поток 2: Взять первое число, удалить, возвести в квадрат и вывести на экран.
• 11 Поток 2: Разблокировать Numbers.

... и так далее. Но в конечном счете произойдет следующее:

• 1 Поток 1: Numbers свободен. Блокируем его.
• 2 Поток 2: Numbers > 0.
• 3 Поток 2: Numbers блокирован. Ждем.
• 4 Поток 1: Взять первое число, удалить, возвести в квадрат и вывести на экран.
• 5 Поток 1: Разблокировать Numbers.
• 6 Поток 2: Numbers свободен. Блокируем его.
• 7 Поток 1: Numbers не больше 0. Закончили.
• 8 Поток 2: Взять первое число... БАЦ!

В этой последовательности, Numbers начинает с ровно одним оставшимся элементом, и поток 1 его блокирует. В то же время поток 2 проверяет Numbers на наличие элементов, и его ждет успех – так как Numbers все еще содержит число. Но заблокировать Numbers он не может, поэтому ждет. Поток 1 продолжает работу, удаляет первый элемент и возводит его в квадрат, затем разблокирует Numbers. Поток 2 теперь блокирует Numbers, думая, что там еще остались числа, и пытается считать оттуда, затем отбрасывается исключение ‘System.ArgumentOutOfRangeException’, так как Numbers[0] не существует.

Если запустить программу несколько тысяч раз, обнаружится, что она не всегда завершается аварийно. Полный произвол: поток 1 может заблокировать Numbers и удалить последнее значение до того, как поток 2 сможет прочитать оставшееся число элементов. Вот почему это зовется ситуацией гонки: потоки забегают один за другой, и между проверкой значения и его использованием может случиться все что угодно.

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

if (Numbers.Count == 0) break;

Теперь запуск программы увенчается успехом, так как мы устранили ситуацию гонки.

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

Пришла пора для главного проекта месяца: взлома SHA1 методом грубой силы. Породим 26 потоков (по одному на каждую букву алфа- вита), затем заставим их считать SHA1-хэш для всех возможных слов, начинающихся с этой буквы. Программа прочтет из командной строки максимальный размер слова и хэш SHA1, и остановится, как только найдет слово, соответствующее хэшу. Максимальный размер слова будет использоваться для ограничения пробных входов: например, если максимум установить на 4, то поток проверит сначала ‘aa’, ‘aaa’, ‘aaaa’, ‘aaab’, ‘aaac’... ‘aaay’, ‘aaaz’, ‘aaba’ и так далее до ‘azzz’.

Здесь не хватит места для всей программы, потому что она занимает около 90 строк (вы найдете ее на диске). Но прежде чем браться за дело, обсудим несколько важных моментов:

• 1 Программа ожидает на входе 2 параметра: максимальный размер создаваемого слова и хэш, которому оно должно соответствовать. Если параметры не предоставлены, программа завершается. Заметим, что метод DoFunk() – точнее, любой метод, который поток выполняет при своем запуске – должен не иметь параметров, либо принимать только один параметр. Если надо передать несколько параметров, следует создать класс, содержащий все необходимые данные, а затем передать объект этого класса в поток.
• 2 Main() создает 26 потоков, по одному на каждую букву алфавита. Это делается следующим образом: буква ‘a’ преобразуется к целому значению в кодировке ASCII, затем добавляется число i и опять преобразуется в букву. I находится в диапазоне от 0 до 25, что дает нам ‘a’,’b’,’c’ и т.д. Затем оно передается в thread.Start().
• 3 Созданные потоки помещаются в список с незатейливым именем Threads.
• 4 Причина, по которой мы отслеживаем потоки – мы хотим, чтобы программа дождалась всех потоков, а потом уж продолжила свою работу. Для этого и метод thread.Join(): он ждет завершения потока.
• 5 Это, в свою очередь, сделано ради подсчета, сколько времени потребуется для завершения работы всех потоков. Если мы не сделаем Join() для каждого потока, Main() продолжит выполнение и спутает нам хронометраж.
• 6 Подсчет хэша SHA1() на .NET – штука мучительная, и я решил эту проблему, написав вам в помощь небольшой метод. Чтобы посчитать SHA1-хэш любого слова, просто отправьте ее в метод Sha1().

Откинув все это в сторону, вы увидите, что метод DoFunk() поразительно мал. На самом деле он только принимает параметр (начальную букву), а затем вызывает другой метод. Но обратите внимание на то, как он принимает параметр типа object, затем преобразует его (char) в символ. Это неизбежность в .NET, но ее легко обойти.

DoFunk() вызывает NextLetter(), передает ей начальную букву и номер 2. Второй параметр – это уровень, то есть размер слова.

Если мы велим программе искать слова максимальной длины 6, то цикл пойдет, обнаружит, что уровень (2) меньше или равен максимуму (6) и войдет в цикл от 0 до 25, а затем перезапустит себя. Вот как будет выглядеть поток вычислений после вызова NextLetter(“a”,2):

if (2 <= 6) {
 for each alphabet letter {
  string = “a” + letter;
  hash = Sha1(string);
  if (hash is what we’re looking for) {
   print happy message
  } else {
     print sad message
    }
 NextLetter(string, 3);
}

О да, рекурсивная функция может здорово надсадить мозги, но самый простой способ понять ее работу – рассовать повсюду выводы сообщений Console.WriteLine(), чтобы проследить внутреннюю логику.

Если вы поняли, как генерируются входные слова, дальше все просто. Программа использует потоки, и так как потоков 26, она будет плавно рассредотачиваться при добавлении процессоров – даже четырехъядерную машинку обеспечит работой под завязку! Вы можете видеть результат на экранном снимке внизу. Заметьте, как другие 24 потока выводят сообщения, найдя соответствие. Это в чистом виде гонка.

Короче, многопоточность не так уж сложна – по крайней мере, если вы разобрались с блокировками, гонками, присоединениями и фоновыми потоками. Верно? Согласны?

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

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

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

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

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