назначить

освободить

Al. Ждать условия n<N

текущий •(- следз

A3. Продвинуть следз

R1. Увеличить п

управление буферами

/ В1. Вычис-\ ление .

I В4. Вычис-V ление

Рис. 25. Алгоритмы множественной буферизации.

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

7V - общее число буферов; п - текущее число красных буферов.

В приведенном ниже алгоритме переменная п используется для того, чтобы СЛЕДЗ и СЛЕДК не мешали один другому.

Алгоритм А (НАЗНАЧИТЬ). Этот алгоритм (рис. 25) состоит из шагов, которые определяются операцией НАЗНАЧИТЬ в вычислительной программе, как описано выше.

а1. [Ждать условия п < N.] Если п = N, остановить программу, пока не будет выполнено условие п < N. (Если п = N, следовательно, ни один буфер не готов к тому, чтобы быть назначенным. Но приведенньп ниже алгоритм В, работающий параллельно с данным алгоритмом в конце концов достигнет успеха в получении зеленого буфера.)

а2. [ТЕКУЩИЙ f- СЛЕДЗ.] Присвоить CURRENT <- NEXTG (назначая, таким образом, текущий буфер).

A3. [Продвинуть СЛЕДЗ.] Продвинуть СЛЕДЗ к следующему буферу по часовой стрелке. I

Алгоритм R (ОСВОБОДИТЬ). Этот алгоритм состоит из шагов, которые определяются операцией ОСВОБОДИТЬ в вычислительной программе, как описано выше.

r1. [Увеличить п.] Увеличить п на единицу.

Алгоритм В [Управление буферами). Этот алгоритм осуществляет реальную инициацию операторов В/В в машине; он должен выполняться одновременно с главной программой, в то.м смысле, как описано ниже.

в1. [Вычисление.] Позволить главной программе в течение короткого времени проводить вычисления. Шаг В2 вьшолняется после некоторой задержки, когда устройство В/В готово для следующей операции.

82. [n = О?] Если п = О, перейти к В1. (Таким образом, если нет ни одного красного буфера, нельзя выполнить ни одну операцию В/В.)

83. [Инициировать Ц/В.] Инициировать передачу данных между буферной областью, на которую указывает СЛЕДК, и устройством В/В.

84. [Вычисление.] Позволить главной программе работать в течение некоторого времени; затем, когда операция В/В будет завершена, перейти к шагу В5.

85. [Продвинуть СЛЕДК.] Продвинуть СЛЕДК к следующему буферу по часовой стрелке.

86. [Уменьшить п.] Уменьшить п на единицу и перейти к шагу В2.

В этих алгоритмах присутствуют два независимых процесса, выполняющихся "одновременно", - программа управления буферизацией и вычислительная программа. Фактически эти процессы являются сопрограммами, которые мы назовем CONTROL и COMPUTE*. Сопрограмма CONTROL вызывает COMPUTE на шагах В1 и В4; сопрограмма COMPUTE вызывает CONTROL с помощью команд "перехода при готовности", которые разбросаны в программе через случайные промежутки.

Запрограммировать этот алгоритм для MIX чрезвычайно просто. Для удобства будем считать, что буфера связаны таким образом, что слово, предшествующее каждому из них, - это адрес следующего буфера. Например, при 7V = 3 имеем CONTENTSCBUFl-1) = BUF2, CONTENTS(BUF2 - 1) = BUF3 и CONTENTS(BUF3 - 1) = BUFl.

Программа А (НАЗНАЧИТЬ,- подпрограмма в сопрограмме COMPUTE). rI4 = ТЕКУЩИЙ; rI6 = n; последовательность вызова: JMP ASSIGN; на выходе в гХ содержится СЛЕДЗ. НАЗНАЧИТЬ STJ 9F

1Н JRED CONTROL(U) Al. Ожидать усповия п < N.

СМР6 =N= JE IB

LD4 СЛЕДЗ А2. ТЕКУЩИЙ 4- СЛЕДЗ.

LDX -1,4 A3. Продвинуть СЛЕДЗ.

STX СЛЕДЗ 9Н JMP * Выход. I

Программа R (ОСВОБОДИТЬ,- используется в сопрограмме COMPUTE). rI6 = п. Этот маленький фрагмент следует вставлять везде, где нужно выполнить операцию RELEASE.

INC6 1 R1. Увеличить п.

JRED CONTROL (U) Возможен переход к сопрограмме CONTROL.

Программа В {Сопрограмма CONTROL). rI6 = n, rI5 = СЛЕДК.

CONTl JMP COMPUTE Bl. Вычисление.

IH J6Z *-l B2. n = 0?

IN 0,5(U) B3. Инициация B/B.

JMP COMPUTE B4. Вычисление.

LD5 -1,5 B5. Продвинуть СЛЕДК.

DEC6 1 Вб. Уменьшить п. JMP IB I

* "Управление" и "вычисление". - Прим. перев.

Помимо приведенного выше кода, имеем также обычные команды связи сопрограмм:

CONTROL STJ COMPUTEX COMPUTE STJ CONTROLX

CONTROLX JMP CONTl COMPUTEX JMP COMPI

Кроме того, команду "JRED CONTROL (U)" следует помещать внутри программы

COMPUTE примерно через каждые 50 команд.

Таким образом, программы множественной буферизации состоят, в сущности,

только из семи команд для CONTROL, восьми - для НАЗНАЧИТЬ и двух - для

ОСВОБОДИТЬ.

Здесь есть один замечательный факт: один и тот же алгоритм можно применять и для ввода, и для вывода. Но в чем же отличие между этими двумя процессами? Как программа управления определяет, что нужно делать - опережать (в случае ввода) или запаздывать (в случае вывода)? Ответ на этот вопрос кроется в начальных условиях. При вводе мы начинаем сп = N (все буфера красные), а при выводе-СП = О (все буфера зеленые). И после того как программа запустится при соответствующих начальных условиях, она уже будет себя вести либо как процесс ввода, либо как процесс вывода. Другим начальным условием является NEXTR = NEXTG, т. е. обе стрелки должны указывать на один из буферов.

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

Здесь возникает важный вопрос: "Какое значение 7V является оптимальным?". Конечно, по мере увеличения 7V скорость работы программы не уменьшится, но и не будет неограниченно расти, поэтому рано или поздно скорость роста снизится. Давайте снова обратимся к величинам С и Т, которые представляют время вычислений между операторами В/В и само время В/В. Точнее, пусть С - это промежуток времени между последовательными операциями НАЗНАЧИТЬ, а Т - промежуток времени, за которое передается один блок. Если С всегда больше Т, то вполне достаточно будет значения N = 2, так как нетрудно показать, что с двумя буферами компьютер будет постоянно занят. Если С всегда меньше Т, то и в такой ситуации достаточно значения N = 2, поскольку устройство В/В будет постоянно занято (за исключением случая, когда устройство имеет особые ограничения на время использования, как в упр. 19). Следовательно, большие значения 7V полезны, главным образом, тогда, когда С принимает то малые, то большие значения. При этом, если большие значения С существенно превосходят Т, подходящим значением iV является среднее число последовательных малых величин С плюс 1. (Нужно заметить, однако, что преимущества буферизации фактически сводятся на нет, если ввод полностью выполняется в начале программы, а вывод - полностью в конце.) Если промежуток времени между операциями НАЗНАЧИТЬ и ОСВОБОДИТЬ всегда достаточно мал, то во всех описанных выше случаях значение 7V можно уменьшить на 1, что почти не окажет влияния на время вьшолнения.

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