Параллельные процессы, работа с временными интервалами

1. Вызов подпрограммы (subroutine).

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

2. Следующим по сложности является вызов процедуры. В дополнение к действиям по вызову подпрограммы добавляется захват области памяти при входе в процедуру и освобождение памяти при выходе (возврате) из процедуры. Память используется в стековом режиме – последняя занятая память первой освобождается.

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

· Захват секции памяти.

· Установка динамической цепочки (адрес начала секции памяти вызывающей процедуры).

· Сохранение регистров.

· Сохранение адреса возврата.

· Передача параметров.

· Передача управления.

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

3. Сопрограмма (coroutine). В дополнение к действиям «создать» и «уничтожить» сопрограмму вводится оператор transfer (p) – прервать исполнение текущей сопрограммы и передать управление в сопрограмму р (точнее – возобновить её исполнение). При приостановке сопрограммы её память не освобождается, поэтому когда-то управление может в неё вернуться (опять-таки оператором transfer). Такая структура управления полностью детерминирована и очень удобна при моделировании различных процессов

4. Ппроцессы. Процесс – это практически независимый объект, он имеет свой исполняемый код, свою область памяти, его состояние определяется содержимым этой памяти и адресом исполняемой в данный момент команды. Одна копия кода может разделяться многими параллельно исполняющимися процессами (reenterable), но рабочая память у каждого процесса должна быть своя. Процессы могут исполняться реально параллельно, например, на разных процессорах. Если приложение состоит из нескольких параллельных процессов, они должны иногда взаимодействовать. Синхронизации действий параллельных процессов. Было придумано несколько чисто программных решений

- ожидающий процесс «висит» на процессоре в пустом цикле

- Э.Дейкстра семафор. Семафор – это структура с одним целым полем, но имя поля не известно, поэтому обычными способами ни прочитать, ни изменить это поле нельзя. Семафор допускает только три операции – установить значение семафора (level), увеличить (up) значение на 1 и уменьшить (down) на. down <=0 текущий процесс приостанавливается (suspend)

Up =0 один из процессов, приостановленных из-за этого семафора, возобновляется (resume). Считается, Принципиально новой идеей в семафорах является их неделимость. В операции down между вычитанием единицы и проверкой на неотрицательность невозможно никакое прерывание процесса. В наше время любая память ЭВМ обеспечивает кроме обычных операций чтения и записи специальную операцию «семафорное чтение», в которой в одном такте выдаётся значение байта, а в байт пишется 1. Нетрудно сообразить, как, используя эту операцию, корректно реализовать операции up и down.

- Т.Хоар - более безопасную конструкцию – монитор. В языки программирования ввели оператор seize m

(схватить ресурс m). Если ресурс занят, процесс зависает прямо на этом операторе seize, никакого «парного» оператора не надо. Вроде бы пустяк, но оказалось, что этот оператор значительно технологичнее.

- В нашем коллективе принято пользоваться механизмом сообщений. Параллельные процессы могут

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

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

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

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

В системах реального времени часто возникает ситуация, когда текущий процесс должен быть задержан на определенный период времени. Чаще всего такая ситуация возникает, когда процесс должен дождаться окончания работы какого-то внешнего устройства Задержку на определенное время осуществляет оператор delay m, где m – количество каких-то единиц времени, например, миллисекунд.

Реализацию оператора delay. Процесс, в котором исполнился этот оператор, приостанавливается и ставится в очередь задержанных процессов. Эта очередь упорядочена по времени ожидания

Есть аппаратный таймер, который каждые 10 мс выдаёт прерывание. К нему очередь процессов, которые надо "разбудить". Очередь упорядочена по возрастанию.

Классическое решение (псевдопараллелизм):

Есть работающий процесс.

Его прервали.

Управление передаётся диспетчеру, который даёт поработать P1, P2 (они такие, что отработают быстро), потом поработают P3, P4, P5, потом снова P1, P2.

Что плохо:

редко какой процесс работает долго;

прерывание процесса (сворачивание) – занимает очень много команд (200-300).

Лучше процесс не прерывать (+600 команд), а дать ему доработать (20-30 команд).

Правильное решение (очередь временных событий):

пусть имеется три процесса. Пусть их надо будить через 10, 30, 100 мс соответственно. Образуется очередь:

Уменьшаем на единицу только первое значение (вычитание происходит аппаратно). Когда доходит до нуля, значит подаём сигнал этому процессу, смещаем указатель в очереди.