Ликбез по программированию & Популярно об ИИ

Данный материал носит объединенный характер и подпадает сразу под две серии вашего покорного слуги. Причиной тому послужило несколько писем. Изначально я просто хотел ответить на вопрос:

«Кристофер, помоги разобраться с потоками для С++ —> Windows Application. Все книги в основном описывают MFC, а на лекциях дали вывод в консоли; для Windows Application это не работает, приложение виснет,… интересует, как расставлять приоритеты, это тоже непонятная тема. Или напиши, пожалуйста, материал по потокам… С уважением, Вячеслав».

Потом встретился с небольшими нападками, в которых говорилось конкретно о серии «Популярно об ИИ». Отметили, что там хорошо представлен начальный уровень, популяризируется тема, но… показываются узкоспециализированные решения, многие из которых «не применимы для крупных проектов». Автор такого письма так распалился, что предложил мне «перед тем как писать, консультироваться со специалистами в данной области». Тут, как говорится, без комментариев. Укажу на одну очевидную вещь: как называется серия материалов? «ПОПУЛЯРНО(!) об ИИ». Методологий масса, некоторые книги вообще невозможно читать, да и многие постулаты дисциплины выглядят спорно. Это во-первых. Во-вторых, если бы ваш покорный слуга начал серию с описания PROLOG или LISP, то, бесспорно, выглядел бы в глазах читателей умным, но они бы ничего не поняли.

Переходим к делу…

О потоках (С++, Windows Application)

Тема долгая, поэтому попытаемся изложить кратко. Итак, лично я воспринимаю потоки в большинстве случаев как асинхронно работающие функции, скажем так. Если речь конкретно не заходит о симметричной многопроцессорной обработке. Внутренние механизмы Windows позволяют представлять потоки как одновременно и синхронно выполняющиеся процессы. Это может быть действительно так, если используется симметричная многопроцессорная обработка, либо создается видимость синхронно выполняющихся процессов. Потоки делятся по приоритетам (см. справку MSVS или книги). При этом можно сказать о существовании очереди выполнения. Все это делается с помощью специального компонента операционной системы, называемого планировщиком потоков (Thread Scheduler).

В рамках нашего случая можно привести пример: одна функция отвечает за вывод окна на экран, другая что-то считает и т.п. В классическом программировании под MFC (!), если вы правильную информацию нашли, используется два вида потоков: потоки пользовательского интерфейса (UI threads) и рабочие потоки (worker threads). Первые отвечают за вывод интерфейсных окон и элементов, они обладают циклом сообщений (message loop), то есть можно обрабатывать сообщения, посылаемые этим окнам и так далее. Рабочие потоки в основном предназначены для фоновых вычислений, хотя их можно использовать по-разному.

Я понимаю проблему, с которой столкнулся автор вопроса, когда рабочие потоки, написанные им, начали «ссориться» с потоками пользовательских интерфейсов. Как результат — окно просто зависает. Но… компьютер ведет себя правильно. Почему так происходит? Фактически, выполнение рабочего потока поместилось внутрь UI-потока, либо он вовсе не был образован и ассоциировался с простой активизацией функции. А если там используется бесконечный цикл или серьезная рекурсия?
Я покажу самый простой вариант нормального решения проблемы, так чтобы вам было понятно.
Перед Main() указываем:
DWORD WINAPI KakayaToFunkzia(LPVOID);
Допустим, тело потока у нас будет таким:
DWORD WINAPI
KakayaToFunkzia(LPVOID vThreadParm)
{
while(1)
{
//что-то делаем
}
}
Я намеренно встроил бесконечный цикл для того, чтобы вы могли наблюдать, как именно работают потоки. Тем более что бесконечные циклы часто используются, особенно при программировании сокетов и т.п. То есть в любых случаях, связанных с постоянным обменом сообщениями и данными. Потом из функции Main() либо по нажатии какой-либо кнопки активизируем этот поток:
HANDLE myNewThread;
DWORD dwThreadID;
myNewThread = CreateThread(
NULL, 0, KakayaToFunkzia,
&threadParm, 0,
&dwThreadID);

Запускайте приложение, оно будет работать без сбоев. Самое главное в данном случае следить за областями видимости для обмена данными между потоками. В нашем случае это может быть, например, вывод полученных из потока сообщений в каком-нибудь элементе графического интерфейса (textbox, listbox, combobox и т.п.) с постоянным обновлением данных и так далее.

В простейшем варианте все делается с помощью глобальных переменных. Например, в потоке в бесконечном цикле из бинарного файла считывается некий параметр. Как его прочитать и отобразить в каком-нибудь элементе графического Windows-интерфейса? Решение простое, поэтому опишу не кодом, а словами. На форму ставите таймер, который обновляет, например, наполнение TextBox с частотой раз в 1 секунду (интервал 1000). Создаем некую глобальную переменную, значение которой переписывается в нашем потоке, а таймер ее считывает и переносит на TextBox. То есть эта переменная должна быть видна везде.

Это только один из вариантов реализации, показанный для того, чтобы вы поняли структуру работы. На самом деле такая реализация не очень удобна для некоторых случаев, но эту тему нужно рассматривать отдельно. То есть, опять же все зависит от конкретной задачи. Например, нередко вы можете столкнуться со специальным проектированием программ, в которых есть отдельные интерфейсы/программные модули и т.п. Общение между ними могут реализовываться как напрямую (например, те же сокеты — я встречал и такие варианты решений), либо же через текстовые или бинарные файлы.

Переключение темы

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

Отдельно стоит сказать о «семафоринге», то есть способности переключения между потоками, а также возможности одного потока управлять действиями другого. Это вызывает ряд сложностей в освоении, поэтому я опишу несколько другую ситуацию.

Эмулируем многопоточность

Допустим, у вас есть задача реализовать многопоточность в рамках среды, которая ее не поддерживает. То есть нам нужно самостоятельно создать планировщик потоков. Буквально перед этим Новым годом мне позвонили друзья с очень веселой проблемой, а именно, они решили сделать свое решение кросс-платформенным, при этом исходный код у них был написан под Windows с использованием потоков на базе стандартных решений. Немногие ОС это поддерживают, а во многих случаях и поддерживают по-другому. Попросили придумать и реализовать решение. Я сразу сказал, что наиболее оптимальный вариант — перенести расчеты в процедурный язык Lua, сценарии которого легко встраиваемы в исполняемый С/С++/С# и т.п. код, а потоки преобразовать в асинхронные вызовы. Звучало сложно, пока не увидели результат.

Пример для вас? Специально сделал простой вариант, отображенный в листинге (см. листинг). Поскольку Lua знают немногие, я написал пример на C#. Главное — чтобы вы поняли суть.

У нас есть две функции, которые мы хотим «запустить синхронно». Условно мы их обозначили AFunction() и BFunction(). Для простоты сделали так, что одна выводит в консольном окне строку «Hello», а другая - «, World!». При этом все сделано в циклах. Зачем? Допустим, у вас AFunction() будет не просто выводить строку, а заполнять массив, производить чтение из файла, делать какую-нибудь циклическую работу. Функция BFunction() производит то же самое, но с другими файлами и данными. Нам нужна та самая пресловутая «синхронизация», а вернее, реализация переключателя между работой двух функций. Мы его и сделали в рамках SelectorFunc().
Что вообще делает эта программа?:))) Сначала наш селектор вызывает одну функцию, но при этом потом переключает вызов на другую, потом опять на первую (простые качели true-false, если функций больше, используем конструкцию switch-case). Шаг вызовов — это не что иное, как приоритет. Допустим, мы сделали для AFunction() значение selector_step равным трем, а для BFunction() — единице, и можем сказать, что приоритетным является процесс выполнения функции AFunction(). Как видите, все просто, понятно и работает. Можно сказать, что мы заменили конструкцию потоков асинхронными вызовами.

Проблема многих студентов состоит в том, что их сразу загружают высокоуровневым программированием, классами и т.п. На самом деле, за всем стоят очевидные вещи.
Также обратите внимание на то, что мы можем из одной функции блокировать вызовы другой. В нашем случае это проще всего делать с помощью более тонкой настройки переключений на базе переменной selector (возможно несколько вариантов).

Причем здесь ИИ?

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

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

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

«Эмуляция многопоточности»

using System;

namespace ConsoleApplication2
{
class Program
{
//главная функция
static void Main(string[] args)
{
//вызываем из Main() функцию "селектора потоков"
//SelectorFunc(). в C# это лучше делать так...
Program anInstanceofProgram = new Program();
anInstanceofProgram.SelectorFunc();
//консольное окно должно остаться открытым
Console.ReadLine();
}

//функция переключения потоков
void SelectorFunc()
{
//счетчик вызовов
int counter = 0;
//шаг вызовов
int counter_step;
//переключатель между двумя функциями selector
//ВНИМАНИЕ!!! Если функций много (не две, как в нашем
// примере), то эта переменная будет как int, и вместо
//if в цикле далее используем switch-case
bool selector = true;
//запускаем цикл
for (counter = 0; counter < 100; counter += counter_step)
{
//"качели"... если selector == true, то вызываем
//функцию AFunction(), которой сообщаем номер вызова
//и шаг, потом переводим selector в false, чтобы вызвать
//BFunction().
if (selector)
{
//"эмулируем" приоритетность потоков
counter_step=3;
//запускаем AFunction()
AFunction(counter, counter_step);
selector = false;
}
else
{
//"эмулируем" приоритетность потоков
counter_step = 1;
//запускаем BFunction()
BFunction(counter, counter_step);
selector = true;
}

}
}

//функция AFunction() принимает текущее значение счетчика
//и шаг, выводит порядковый номер вызова и строку "Hello"
void AFunction(int a, int b)
{
for (int i = a; i < 100; i++)
{ //обратите внимание на то, как
//функционирует цикл, то есть он
//стартует с текущей позиции до варианта
//позиция + шаг
if (i == a+b) break;
Console.Write(i.ToString()+" ");
Console.WriteLine("Hello");

}

}

//идентично BFunction()... выводит строку ", World!"
void BFunction(int a, int b)
{
for (int i = a; i < 100; i++)
{ if (i == a + b) break;
Console.Write(i.ToString() + " ");
Console.WriteLine(", World!");

Кристофер christopher@tut.by