Параллельные процессы
Вообще-то, про параллельные процессы принято рассказывать в других курсах, чаще всего в курсе "Операционные системы" [23]. Но поскольку мы хотим изложить придуманную в нашем коллективе эффективную организацию вычислительного процесса во встроенных системах реального времени, нужно, чтобы читатель понимал "что почем" в мире параллельных процессов.
Можно предложить следующую иерархию разбиения сложной системы на взаимодействующие куски:
- Самым простым является вызов подпрограммы (subroutine). Часто встречающийся кусок кода оформляется как подпрограмма. В том месте программы, где необходимо использовать эту подпрограмму, ставится команда "переход с возвратом" (branch and link), которая запоминает адрес следующей команды в регистре, а затем передает управление в начало подпрограммы. В конце подпрограммы ставится команда перехода по адресу, записанному в регистре. Разумеется, должны соблюдаться определенные соглашения о связях, например, возврат из подпрограммы должен всегда осуществляться по одному и тому же номеру регистра. Каждая подпрограмма должна сохранить значение этого регистра в какой-то памяти, если внутри нее есть вызовы других подпрограмм. В любом случае, накладные расходы на вызов подпрограммы небольшие (2-4 команды).
- Следующим по сложности является вызов процедуры. К действиям по вызову подпрограммы добавляется захват области памяти для локальных переменных процедуры и различных рабочих данных при входе в процедуру и освобождение памяти при выходе (возврате) из процедуры. Память используется в стековом режиме – последняя занятая память освобождается первой.
Примерный перечень действий при вызове процедуры:
- Захват секции памяти.
- Установка динамической цепочки (адрес начала секции памяти вызывающей процедуры).
- Сохранение регистров.
- Сохранение адреса возврата.
- Передача параметров.
- Передача управления.
При возврате нужно восстановить регистры, освободить память и восстановить контекст вызывающей процедуры. Для ЭВМ без аппаратной поддержки вызов процедуры может потребовать от 30 до 150 команд.
Когда- то мы очень гордились, что сумели для архитектуры IBM/360 придумать реализацию вызова процедуры за 11 команд.
Заметим, что описанная реализация вызова допускает рекурсию, когда процедура вызывает самое себя, а основное направление оптимизации вызовов – сведение вызова процедуры к вызову подпрограммы.
- Еще более сложным является вызов сопрограммы (coroutine). В дополнение к действиям "создать" и "уничтожить" сопрограмму вводится оператор transfer(p) – прервать исполнение текущей сопрограммы и передать управление в сопрограмму р (точнее, возобновить ее исполнение). При приостановке сопрограммы ее память не освобождается, поэтому когда-то управление может в нее вернуться (опять-таки оператором transfer). Такая структура управления полностью детерминирована и очень удобна при моделировании различных процессов. Наиболее известным языком, использующим сопрограммы, является Модула 2 [24]. По времени исполнения вызов сопрограммы мало чем отличается от вызова процедуры, но по объему используемой памяти, разумеется, он обходится дороже.
- Самым общим, мощным и дорогим средством организации взаимодействия различных фрагментов большой программы являются параллельные процессы. Процесс – это практически независимый объект, он имеет свой исполняемый код, свою область памяти, его состояние определяется содержимым этой памяти и адресом исполняемой в данный момент команды. Если программный код устроен таким образом, что в него никто не пишет, одна копия кода может разделяться многими параллельно исполняющимися процессами (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, после которого процесс приостанавливается и ждет ответа.
