Параллельные процессы

Вообще-то, про параллельные процессы принято рассказывать в других курсах, чаще всего в курсе "Операционные системы" [23]. Но поскольку мы хотим изложить придуманную в нашем коллективе эффективную организацию вычислительного процесса во встроенных системах реального времени, нужно, чтобы читатель понимал "что почем" в мире параллельных процессов.

Можно предложить следующую иерархию разбиения сложной системы на взаимодействующие куски:

1. Самым простым является вызов подпрограммы ( subroutine ). Часто встречающийся кусок кода оформляется как подпрограмма. В том месте программы, где необходимо использовать эту подпрограмму, ставится команда "переход с возвратом" ( branch and link ), которая запоминает адрес следующей команды в регистре, а затем передает управление в начало подпрограммы. В конце подпрограммы ставится команда перехода по адресу, записанному в регистре. Разумеется, должны соблюдаться определенные соглашения о связях, например, возврат из подпрограммы должен всегда осуществляться по одному и тому же номеру регистра. Каждая подпрограмма должна сохранить значение этого регистра в какой-то памяти, если внутри нее есть вызовы других подпрограмм. В любом случае, накладные расходы на вызов подпрограммы небольшие (2-4 команды).
2. Следующим по сложности является вызов процедуры. К действиям по вызову подпрограммы добавляется захват области памяти для локальных переменных процедуры и различных рабочих данных при входе в процедуру и освобождение памяти при выходе (возврате) из процедуры. Память используется в стековом режиме – последняя занятая память освобождается первой.

   Примерный перечень действий при вызове процедуры:

   • Захват секции памяти.
   • Установка динамической цепочки (адрес начала секции памяти вызывающей процедуры).
   • Сохранение регистров.
   • Сохранение адреса возврата.
   • Передача параметров.
   • Передача управления.

   При возврате нужно восстановить регистры, освободить память и восстановить контекст вызывающей процедуры. Для ЭВМ без аппаратной поддержки вызов процедуры может потребовать от 30 до 150 команд. Когда-то мы очень гордились, что сумели для архитектуры IBM/360 придумать реализацию вызова процедуры за 11 команд.

   Заметим, что описанная реализация вызова допускает рекурсию, когда процедура вызывает саму себя, а основное направление оптимизации вызовов – сведение вызова процедуры к вызову подпрограммы.
3. Еще более сложным является вызов сопрограммы ( coroutine ). В дополнение к действиям "создать" и "уничтожить" сопрограмму вводится оператор transfer(p) – прервать исполнение текущей сопрограммы и передать управление в сопрограмму р (точнее, возобновить ее исполнение). При приостановке сопрограммы ее память не освобождается, поэтому когда-то управление может в нее вернуться (опять-таки оператором transfer ). Такая структура управления полностью детерминирована и очень удобна при моделировании различных процессов. Наиболее известным языком, использующим сопрограммы, является Модула 2 [24]. По времени исполнения вызов сопрограммы мало чем отличается от вызова процедуры, но по объему используемой памяти, разумеется, он обходится дороже.
4. Самым общим, мощным и дорогим средством организации взаимодействия различных фрагментов большой программы являются параллельные процессы. Процесс – это практически независимый объект, он имеет свой исполняемый код, свою область памяти, его состояние определяется содержимым этой памяти и адресом исполняемой в данный момент команды. Если программный код устроен таким образом, что в него никто не пишет, одна копия кода может разделяться многими параллельно исполняющимися процессами ( reenterable ), но рабочая память у каждого процесса должна быть своя. Процессы могут исполняться параллельно, например, на разных процессорах. Во многих операционных системах задача – это процесс, к которому приписаны различные ресурсы (максимально доступные объемы памяти и процессорного времени, объемы дискового пространства и т.д.). Если приложение состоит из нескольких параллельных процессов, они должны иногда взаимодействовать. Это очень непростая задача. Рассмотрим пример.

Пусть два процесса р1 и р2 используют общую переменную S вида struct (int a,b), т.е. S является структурой с двумя целыми полями. Предположим, процесс р1 решил прочитать значение структуры S, успел прочитать первое поле a, но был по какой-то причине прерван. Процесс р2 записал в структуру S новое значение, потом процесс р1 был возобновлен и продолжил чтение со второго поля b. В результате р1 получит значения полей а и b из разных фаз обработки.

Таким образом, мы приходим к идее монополизации ресурсов или, другими словами, синхронизации действий параллельных процессов. Было придумано несколько чисто программных решений, но все они обладают одним общим недостатком – какое–то время ожидающий процесс "висит" на процессоре в пустом цикле, бесполезно растрачивая самый драгоценный ресурс – время процессора.

Еще в конце 50-х годов ХХ века известный ученый Э. Дейкстра придумал принципиально новую конструкцию – семафор [5]. Семафор – это структура с одним целым полем, но имя поля неизвестно, поэтому обычными способами ни прочитать, ни изменить это поле нельзя. Семафор допускает только три операции – установить значение семафора ( level ), увеличить ( up ) значение на 1 и уменьшить ( down ) на 1. Если во время исполнения операции down значение семафора стало отрицательным, текущий процесс приостанавливается ( suspend ), если при выполнении операции up значение семафора из отрицательного становится нулем, один из процессов, приостановленных из-за этого семафора, возобновляется ( resume ). Считается, что в операционной системе есть очередь готовых к исполнению процессов и очередь процессов, ожидающих неотрицательного значения какого-то семафора, но никакого определенного порядка исполнения не подразумевается. Принципиально новой идеей в семафорах является их неделимость. В операции down между вычитанием единицы и проверкой на неотрицательность никакое прерывание процесса невозможно. В наше время любая память ЭВМ обеспечивает, кроме обычных операций чтения и записи, специальную операцию "семафорное чтение", в которой в одном такте выдается значение байта, а в байт пишется 1. Нетрудно сообразить, как, используя эту операцию, корректно реализовать операции up и down.

Рассмотрим пример:

sema s = level 1;
par  begin 
    do НАЧАЛО1;
      down s; ДЕЙСТВИЯ1; up s;
      КОНЕЦ1
    od ,
    do НАЧАЛО2;
      down s; ДЕЙСТВИЯ2; up s;
    КОНЕЦ2
    od
  end

Здесь два параллельных процесса представлены бесконечными циклами. Каждый процесс включает в себя последовательность операторов, ограниченную операторами down и up. Начальное значение семафора равно 1.

Действия НАЧАЛО1 и НАЧАЛО2 выполняются параллельно, допустим, второй процесс раньше достигает своего оператора down s. Тогда s получит значение 0, начнется выполнение последовательности ДЕЙСТВИЯ2. Пусть теперь и первый процесс достигнет оператора down s. Так как текущее значение s равно 0, первый процесс приостановится и будет ждать, пока второй процесс не выполнит оператор up s. Кстати, никто не гарантирует, что после этого возобновится первый процесс – если второй процесс выполняется быстрее первого, то вполне возможно, что раньше снова сработает оператор down s второго процесса.

Я хотел показать на этом примере, что ДЕЙСТВИЯ1 никогда не будут выполняться параллельно последовательности ДЕЙСТВИЯ2 – или ДЕЙСТВИЯ1, или ДЕЙСТВИЯ2, но не вместе. Такие фрагменты параллельных процессов называются критическими интервалами.

На практике столь простая и фундаментальная конструкция, как семафор, оказалась очень опасной. Два семантически связанных действия разнесены по тексту. Кто-то забудет открыть семафор, а кто-то – закрыть.

Позже Т. Хоар предложил более безопасную конструкцию для синхронизации параллельных процессоров – монитор[26]. Представьте себе дверь в комнату, в замок которой вставлен ключ. Вы открываете дверь, вынимаете ключ, входите в комнату и закрываетесь в ней. Следующий, кто захочет войти в комнату, не найдет ключа и вынужден будет ждать, пока вы не выйдете. В языки программирования ввели оператор seize m (схватить ресурс m ). Если ресурс занят, процесс зависает прямо на этом операторе seize – никакого "парного" оператора не надо. Вроде бы пустяк, но оказалось, что этот оператор значительно технологичнее.

Значительно позже появились почтовые ящики, "рандеву" и многие другие средства. Математически они все эквивалентны, т.е. выражаются друг через друга, но с точки зрения технологичности, выразительности, эффективности реализации — существенно различаются.

В нашем коллективе принято пользоваться механизмом сообщений. Параллельные процессы могут использовать операторы send m (послать сообщение) и receive m (получить сообщение). После оператора send процесс ничего не ждет, а работает дальше, сообщение "заплетается" в очередь входных сообщений того процесса, которому оно предназначено (обычно адресат указывается либо отдельным параметром, либо просто включается в сообщение).

По оператору receive процесс просматривает свою очередь входных сообщений. Если она пуста, то процесс "зависает", иначе берется очередное сообщение и обрабатывается.

Нам нравится, что сообщения не только играют роль синхронизации, но и несут семантическую нагрузку – обмен данными.

Иногда требуется более жесткая схема синхронизации, тогда вместо send используется оператор ask m, после которого процесс приостанавливается и ждет ответа.