Windows и C++

Статья
07/03/2015

Облегченная кооперативная многозадачность на основе C++

Kenny Kerr Если вы работаете в компании, где есть такие документы со стандартами кодирования, которые — будь они однажды напечатаны — потребовали бы вырубить целый участок джунглей, вам лучше не читать эту статью. Скорее всего то, о чем я собираюсь рассказать, разрушит многие догмы, изложенные в этих документах. А я намерен показать вам одну методику, которую изначально придумал я сам и которая позволила мне эффективно писать полностью асинхронный код, обходясь без сложных конечных автоматов.

Если только вы не Дональд Кнут, любой код, написанный вами, вероятно, напоминает что-то, что уже было сделано. Действительно, самое старое высказывание, которое мне удалось найти, по поводу описываемой здесь методики принадлежит лично Кнуту, а самое недавнее — одному джентльмену из Англии, Саймону Тэтэму (Simon Tatham), известному своей популярной разработкой — эмулятором терминалов PuTTY. Однако на недавнем процессе Oracle против Google судья заявил примерно так: «нельзя патентовать цикл for». Тем не менее, мы все так или иначе опираемся на достижения своих коллег в области программирования, когда делаем что-то новое.

Прежде чем углубляться в описание моей методики и рассказывать, как она работает, я сделаю небольшое отступление в надежде, что это немного прояснит то, о чем пойдет речь. В книге Алфреда В. Эйхоу (Alfred V. Aho), Моники С. Лэм (Monica S. Lam), Рави Сети (Ravi Sethi) и Джефри Д. Уллмена (Jeffrey D. Ullman) «Compilers: Principles, Techniques and Tools, Second Edition» (Prentice Hall, 2006), более известной под названием «Dragon Book», авторы суммируют суть компилятора как программы, способной читать некую программу на одном языке и транслировать ее в эквивалентную программу на другом языке. Если бы вам довелось спросить Бьёрна Страуструпа (Bjarne Stroustrup), разработчика C++, о том, каким языком он пользовался при создании C++, он ответил бы вам, что это был C++. То есть он написал препроцессор, читающий C++ и выдающий текст на C, который стандартный компилятор C мог бы потом транслировать в какой-нибудь машинный язык. Если вы подумаете, то, возможно, вспомните, что видели вариации этой идеи во многих местах. Компилятор C#, например, транслирует кажущееся волшебным ключевое слово yield в регулярный класс, реализующий итератор. В конце прошлого года я заметил, что компилятор Visual C++ сначала транслирует части с синтаксисом C++/CX в стандартный C++ и только потом продолжает компиляцию. С тех пор это могло измениться, но суть в том, что компиляторы в основном занимаются трансляцией.

Иногда, используя конкретный язык, можно счесть, что была бы желательна некая функциональность, которую этот язык по самой своей природе не дает реализовать. Такое редко бывает в C++, поскольку этот язык по своей архитектуре — благодаря его богатому синтаксису и средствам метапрограммирования — подходит для выражения различных методологий. И все же я столкнулся именно с этой ситуацией.

Большую часть времени я сейчас работаю над встраиваемой ОС, которую сам создал с нуля. Она не использует на внутреннем уровне ни Linux, ни Windows, ни какую-либо другую ОС. Я не опираюсь ни на какие проекты с открытым исходным кодом, и на самом деле это все равно невозможно по причинам, которые станут ясны позже. В связи с этим мне открылся целый мир программирования на C и C++, совершенно отличный от привычного мира разработки программного обеспечения для ПК. В большинстве встраиваемых систем существуют ограничения, сильно отличающие их от «обычных» программ. Они должны быть чрезвычайно надежными. Любой сбой может обойтись очень дорого. «Перезапустить» программу, в которой произошел сбой, как правило, некому. Такие системы могут бесперебойно работать годами без вмешательства человека. Вообразите мир без Windows Update или подобных механизмов. Кроме того, в распоряжении этих систем может быть крайне мало вычислительных ресурсов. Корректность, надежность и параллельная обработка играют центральные роли в проектировании таких систем.

Ввиду этого роскошный мир Visual C++ с его мощными библиотеками редко подходит для разработок такого рода. Даже если бы Visual C++ был рассчитан на мой встраиваемый микроконтроллер, вспомогательные библиотеки не особо годятся для систем с такими малыми вычислительными ресурсами и зачастую с жесткими требованиями к выполнению в реальном времени. Один из микроконтроллеров, который я сейчас использую, имеет всего 32 Кб памяти и тактовую частоту менее 50 МГц, и это еще роскошь для некоторых представителей встраиваемых устройств. Так что вам должно быть ясно, что под «встраиваемым» я вовсе не имею в виду средний смартфон с половиной гигабайта памяти и процессором на 1 ГГц.

В книге «Programming: Principles and Practice Using C++» (Addison-Wesley Professional, 2008) Страуструп упоминает операции выделения свободной памяти (free-store allocations) (например, new и delete), исключения и dynamic_cast в краткой списке средств, которых следует избегать в большинстве встраиваемых систем, так как эти средства непредсказуемы. Увы, это делает невозможным использование большинства стандартных и предоставляемых поставщиком библиотек C++, а также библиотек C++ с открытым исходным кодом, доступных в настоящее время.

Результат в том, что при программировании встраиваемых устройств — и если на то пошло, то и при программировании для Windows в режиме ядра — по-прежнему применяют в основном C, а не C++. Учитывая, что C — это фактически подмножество C++, я чаще пользуюсь компилятором C++, но придерживаюсь строгого подмножества этого языка, которое является предсказуемым, портируемым и хорошо работает во встраиваемых системах.

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

Представьте себе драйвер хранилища. В нем может быть функция storage_read для чтения страницы памяти из постоянной флеш-памяти устройства. Эта функция могла бы сначала проверять, занято ли периферийное устройство или шина, и, если да, просто ставить запрос на чтение в очередь перед возвратом управления. В некий момент периферийное устройство или шина освобождается, и запрос может быть обработан. При этом отключается приемопередатчик, команда форматируется соответственно требованиям шины, подготавливаются буферы для прямого доступа к памяти, приемопередатчик снова включается, а затем управление передается вызвавшему коду, чтобы он мог сделать что-то еще, пока аппаратное обеспечение выполняет передачу данных. В конечном счете шина сигнализирует об окончании передачи данных, вызвавший уведомляется об этом через какой-то механизм обратного вызова, и продолжается обработка любых других запросов, находящихся в очереди. Очевидно, что управление очередями, обратными вызовами и конечными автоматами может оказаться весьма сложным. Еще труднее проверять, что все корректно. Я даже не стал говорить о том, как можно было бы реализовать неблокирующую файловую систему поверх этой абстракции или как веб-сервер мог бы использовать эту файловую систему для обслуживания запросов, — и все это без блокирования. Здесь явно нужен другой подход, чтобы уменьшить неизбежно растущую сложность.

Теперь вообразите, будто в C++ есть несколько ключевых слов, которые позволяли бы вам переключать процессор между стеками вызовов в промежуточной функции (mid-function). Представьте себе следующий гипотетический код на C++:

void storage_read(storage_args & args) async
{
  wait while (busy);
  busy = true;
  begin_transfer(args);
  yield until (done_transmitting());
  busy = false;
}

Обратите внимание на контекстно-зависимое ключевое слово async за списком параметров. Я также использую два воображаемых ключевых словосочетаний: wait while и yield until. Рассмотрим, что означало бы для C++ наличие таких ключевых слов. Компилятор должен был бы каким-то образом выражать эту концепцию, если хотите, вставки (interlude). Кнут назвал это сопрограммой (coroutine). Ключевое слово async должно появляться вместе с объявлением функции, чтобы компилятор знал, что эта функция может выполняться асинхронно, а значит, ее нужно вызывать соответствующим образом. Гипотетические ключевые слова wait и yield — точки, в которых функция прекращает синхронное выполнение и потенциально может вернуть управление вызвавшему коду только для того, чтобы возобновить свое выполнение после возврата управления, но на более позднем этапе. Вы также могли бы вообразить условное ключевое слово «wait until», равно как и безусловное выражение yield.

Я видел альтернативы этой кооперативной форме параллельной обработки — особенно Asynchronous Agents Library, поставляемую с Visual C++, — но все решения, которые я находил, полагались на какой-либо механизм планирования в исполняющей среде. В этой статье я предлагаю и вскоре продемонстрирую вполне реальную возможность добиться того, чтобы компилятор C++ предоставлял кооперативную параллельную обработку безо всяких издержек, связанных с исполняющими средами. Учтите, что я не говорю о том, будто это решит задачу масштабируемости на несколько ядре процессора. Я имею в виду лишь то, что у нас должна быть возможность писать быстрые и отзывчивые программы, управляемые событиями, без использования какого-либо планировщика. И в существующих на данный момент языках C и C++ ничто не должно помешать применению этих методик совместно с потоками ОС или другими механизмами параллельной обработки.

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

task_begin(storage_read, storage_args & args)
{
  task_wait_while(busy);
  busy = true;
  begin_transfer(args);
  task_yield_until(done_transmitting());
  busy = false;
}
task_end

Понятно, что здесь я опираюсь на макросы. Ясно также, что это противоречит пункту 16 в C++ Coding Standards (bit.ly/8boiZ0), но альтернативы еще хуже. Идеальное решение — прямая языковая поддержка. К другим вариантам относится, например, применение longjmp, но, как я убедился, этот вариант хуже и в нем много своих подвохов. Другим подходом могло бы стать использование языка ассемблера, но тогда я потерял бы все возможности портирования. Весьма спорный вопрос, что такое вообще можно сделать столь же эффективно, как на языке ассемблера, поскольку наиболее вероятно, что этот подход приведет к решению, которое использует больше памяти из-за потери контекстно-зависимой информации и неизбежной реализации «по одному стеку на каждую задачу». Так что будьте снисходительны ко мне, когда я буду показывать вам, насколько просто и эффективно это решение и как оно работает.

Чтобы не усложнять картину, с этого момента я буду называть эти асинхронные функции задачами (tasks). Если взять задачу, описанную ранее, то ее можно планировать простым вызовом как функции:

storage_args = { ... };
storage_read(args);

Как только задача решает, что она не может продолжать дальше, она просто возвращает управление вызвавшему коду. Задачи используют возвращаемый тип bool, который сообщает вызвавшему коду, завершена ли данная задача. Таким образом, вы могли бы постоянно планировать задачу до тех пор, пока она не завершится:

while (storage_read(args));

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

task_wait_for(storage_read, args);

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

task_declare(имя, параметр) — объявляет задачу, обычно в заголовочном файле;
task_begin(имя, параметр) — начинает определение задачи, обычно в файле исходного кода на C++;
task_end — завершает определение задачи;
task_return() — завершает выполнение задачи и возвращает управление вызвавшему коду;
task_wait_until(выражение) — ожидает, пока выражение не станет true, а затем продолжает работу;
task_wait_while(выражение) — ждет, пока выражение равно true, а затем продолжает работу;
task_wait_for(имя, параметр) — запускает задачу и ожидает ее завершения перед тем, как продолжить работу;
task_yield() — безусловно возвращает управление, продолжая, когда задача планируется заново;
task_yield_until(выражение) — возвращает управление минимум раз, продолжая, когда выражение отлично от 0.

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

Рис. 1. Задача average

struct average_args
{
  int * source;
  int sum;
  int count;
  int average;
  int task_;
};
task_begin(average, average_args & args)
{
  args.sum = 0;
  args.count = 0;
  args.average = 0;
  while (true)
  {
    args.sum += *args.source;
    ++args.count;
    args.average = args.sum / args.count;
    task_yield();
  }
}
task_end

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

Сама по себе эта задача интересна тем, что содержит бесконечный цикл while с вызовом task_yield в теле цикла. Перед вхождением в этот цикл задача инициализирует некое состояние. Затем обновляет его агрегатные величины (aggregates) и возвращает управление, давая возможность выполняться другим задачам перед повторением цикла.

Теперь перейдем к задаче input, показанной на рис. 2.

Рис. 2. Задача input

struct input_args
{
  int * target;
  int task_;
};
task_begin(input, input_args & args)
{
  while (true)
  {
    printf("number: ");
    if (!scanf_s("%d", args.target))
    {
      task_return();
    }
    task_yield();
  }
}
task_end

Эта задача интересна тем, что иллюстрирует, как задачи могут на самом деле блокироваться, поскольку функция scanf_s крутится в цикле while, ожидая ввода. Однако это далеко не идеально для системы, управляемой событиями. Эта задача также демонстрирует использование вызова task_return call для завершения задачи в промежуточной функции вместо применения условного выражения в while. Задача завершается либо вызовом task_return, либо, так сказать, выходом за конец функции. В любом случае вызвавший увидит это, когда задача будет завершаться, и сможет возобновить свое выполнение.

Чтобы «оживить» эти задачи, вам нужна лишь простая функция main, выступающая в роли планировщика:

int main()
{
  int share = -1;
  average_args aa = { &share };
  input_args ia = { &share };
  while (input(ia))
  {
    average(aa);
    printf("sum=%d count=%d average=%d\n",
      aa.sum, aa.count, aa.average);
  }
}

Возможности безграничны. Вы могли бы написать задачи, представляющие таймеры, источники данных и их потребителей, обработчики TCP-соединений и многое другое.

Как же все это работает? Сначала еще раз напомню, что в идеале это должно было бы быть реализовано в компиляторе, и тогда он мог бы применять все виды хитрых оптимизаций, а то, что я собираюсь описать, никак не будет столь же изощренным или сложным.

Насколько мне известно, здесь все сводится к открытию, которое сделал программист Том Дафф (Tom Duff); он обнаружил, что с выражением switch можно выделывать весьма хитрые фокусы. Пока вы соблюдаете синтаксис, вы можете вкладывать в выражение switch различные выражения выбора или итерации, что в позволяет эффективно переходить в любую функцию или выходить из нее. Дафф опубликовал эту методику для ручной раскрутки цикла (manual loop unrolling), а Тэтэму (Tatham) потом пришло в голову мысль, как это можно было бы использовать для имитации сопрограмм. Я взял на вооружение эти идеи и реализовал задачи следующим образом.

Макросы task_begin и task_end определяют окружающее выражение switch:

#define task_begin(name, parameter) \
                                    \
  bool name(parameter)              \
  {                                 \
    bool yield_ = false;            \
    switch (args.task_)             \
    {                               \
      case 0:
#define task_end                    \
                                    \
    }                               \
    args.task_ = 0;                 \
    return false;                   \
  }

Теперь должно быть очевидно, для чего предназначена единственная переменная task_ и как все это работает. Инициализация task_ нулевым значением гарантирует, что поток выполнения перейдет в начало задачи. Когда задача завершается, этой переменной вновь присваивается 0 для удобства — чтобы задачу можно было легко запустить снова. Учитывая это, макрос task_wait_until предоставляет необходимый адрес перехода и механизм кооперативного возврата (cooperative return facility):

#define task_wait_until(expression)      \
                                         \
  args.task_ = __LINE__; case __LINE__:  \
  if (!(expression))                     \
  {                                      \
    return true;                         \
  }

Переменной task_ присваивается макрос с предопределенным номером строки (predefined line number macro), и выражение case получает тот же номер строки, тем самым гарантируя, что, если задача вернет управление, то в следующий раз поток выполнения возобновится прямо там, откуда он «ушел». Остальные макросы показаны на рис. 3..

Рис. 3. Остальные макросы

#define task_return()                    \
                                         \
  args.task_ = 0;                        \
  return false;
#define task_wait_while(expression)      \
                                         \
  task_wait_until(!(expression))
#define task_wait_for(name, parameter)   \
                                         \
  task_wait_while(name(parameter))
#define task_yield_until(expression)     \
                                         \
  yield_ = true;                         \
  args.task_ = __LINE__; case __LINE__:  \
  if (yield_ || !(expression))           \
  {                                      \
    return true;                         \
  }
#define task_yield()                     \
                                         \
  task_yield_until(true)

Они должны быть совершенно очевидными. Возможно, стоит упомянуть лишь об одной тонкости, связанной с task_yield_until, так как он аналогичен task_wait_until, но на самом деле всегда возвращает управление минимум раз. Макрос task_yield в свою очередь всегда возвращает управление только раз, и я уверен, что любой приличный компилятор оптимизирует мою писанину. Должен упомянуть, что task_wait_until также является отличным способом справляться с ситуациями нехватки памяти. Вместо провала где-то в глубоко вложенной операции с сомнительными шансами на успешное восстановление вы можете просто возвращать управление до тех пор, пока операция выделения памяти не закончится успешно, давая возможность другим задачам завершиться и освободить какое-то количество столь необходимой памяти. И вновь, это крайне важно для встраиваемых систем, где выдача ошибки неприемлема.

В связи с тем, что я эмулирую сопрограммы, вас поджидают некоторые подводные камни. Внутри задач нельзя использовать локальные переменные, и любой код, нарушающий соответствие синтаксису скрытого выражения switch, обязательно создаст проблемы. Тем не менее, учитывая, что я могу определить свой task_args, и тот факт, насколько проще мой код благодаря этой методике, я радуюсь уже тому, что он вообще работает.

Я обнаружил, что полезно отключить следующие предупреждения компилятора Visual C++:

// Условное выражение является константой
#pragma warning(disable: 4127)
// Локальная переменная инициализирована, но на нее нет ссылок
#pragma warning(disable: 4189)
// Присваивание внутри условного выражения
#pragma warning(disable: 4706)

Наконец, если вы используете Visual C++ IDE, обязательно отключите функцию «edit and continue debugging», указав /Zi вместо /ZI.

В заключение отмечу, что я прошелся по Интернету в поисках любых аналогичных инициатив и нашел новые ключевые слова async и await, введенные в компилятор C# из состава Visual Studio 2012. Во многих отношениях это попытка решить сходную проблему. Полагаю, что сообщество C++ последует этому примеру. Вопрос в том, появятся ли эти решения в C и C++ в таком виде, чтобы можно было получать предсказуемый код, пригодный для встраиваемых систем, или они будут опираться на исполняющую среду параллельной обработки, как это делают текущие версии библиотек Visual C++. Надеюсь, что однажды я смогу отбросить все эти макросы, но до тех пор я буду использовать эту облегченную кооперативную многозадачность.

В следующем выпуске этой рубрики я покажу некоторые новые методики, над которыми работали Никлас Густафссон (Niklas Gustafsson) и Артур Лаксберг (Artur Laksberg) из группы Visual C++, чтобы ввести в C++ возобновляемые функции.

Кенни Керр (Kenny Kerr) — высококвалифицированный специалист в области разработки ПО для Windows. С ним можно связаться через kennykerr.ca.

Выражаю благодарность за рецензирование статьи эксперту Артуру Лаксбергу (Artur Laksberg).

Windows и C++

Облегченная кооперативная многозадачность на основе C++

Дополнительные ресурсы