3. WORDOUT STJ IF DECS 100

STA 0,5 JMP 2B

INC5 1 BUFMAX CON ENDBUFl

2H CMP5 BUFMAX » BUFFER AREAS

IH JNE » OUTBUFl ORIG *+100

OUT -100.5(V) ENDBUFl CON ENDBUF2

LD5 0,5 0UTBUF2 ORIG *+100

•ST5 BUFMAX ENDBUF2 CON ENDBUFl В начале программы используйте команду "ENT5 OUTBUFl", а в конце программы, скажем,

LDA BUFMAX INC5 1

DECA 100.5 СМР5 BUFMAX

JAZ »+6 JNE »-3

STZ 0,5 OUT -100.5(V)

4. Если время, затрачиваемое на вычисления, в точности равно времени В/В (это самая благоприятная ситуация), то одновременно работающие компьютер и периферийное устройство затрачивают в два раза меньше времени, чем в случае, когда они работают отдельно. Пусть С - время вычислений для всей программы, а Г - общее время, требуемое для В/В. Тогда минимальное из возможных время выполнения при использовании буферизации составит тах(С,Т), а время выполнения без буферизации - С + Т. И конечно, 5(С + Г) <тах(С7,Г) <С7 + Г.

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

5. Можно сократить время выполнения .максимум в {п + \) раз. g Г IN INBUFKU)"! Г IN INBUF2(U)1

IeNT6 INBUF2+99/ \eNT6 INBUFl+99/

(Этим командам может предшествовать команда ЮС 0(U), перематывающая ленту только в случае необходимости).

7. Один из способов -использование сопрограмм.

INBUF1 ORIG »+100 INC6 1

INBUF2 ORIG »+100 J6N 2В

1Н LDA INBUF2+100.6 IN INBUFl(U)

JMP MAIN . ENN6 100

INC6 1 JMP IB

J6N IB WORDIN STJ MAINX

WORDINl IN INBUF2(U) WORDINX JMP WORDINl

ENN6 100 MAIN STJ WORDINX

2H LDA INBUFl+100,6 MAINX JMP ♦

JMP MAIN

Если добавить еще несколько команд, чтобы извлечь преимущества из частных случаев, эта программа будет работать быстрее, чем (4).

8. К моменту, показанному на рис. 23, два красных буфера уже заполнены образами строк и выводится на печать содержимое того буфера, на который указывает стрелка СЛЕДК. В это же время программа проводит вычисления по командам, расположенным между операциями ОСВОБОДИТЬ и НАЗНАЧИТЬ. Когда программа выполняет операции НАЗНАЧИТЬ, зеленый буфер, на который указывает стрелка СЛЕДЗ, становится желтым; Стрелка СЛЕДЗ перемещается по часовой стрелке, и программа начинает заполнять желтый буфер. По окончании вывода стрелка СЛЕДК перемещается по часовой стрелке, буфер, содержимое которого только что было напечатано, становится зеленым и начинает печататься

содержимое оставшегося красного буфера. Наконец программа ОСВОБОЖДАЕТ желтый буфер

и теперь он также готов к печати своего содержимого.

9, 10,

Время О

1000 2000 3000 4000 5000 6000 7000 8000 8500 9500 10500 15500

Действие (N - 1) ASSIGN(BUF1) RELEASE, OUT BUFl ASSIGN (ожидать)

BUFl назначен, остаяовка вывода RELEASE, OUT BUFl ASSIGN (ожидать)

Действие (N = 2) ASSIGN(BUFl) RELEASE, OUT BUFl ASSIGN(BUF2) RELEASE

ASSIGN (ожидать)

BUFl назначен, OUT BUF2 RELEASE

ASSIGN (ожидать)

и т. д. Общее время при N = I равно llOOOOu, при N = 2 при N > 4 -76000U.

12. Замените последние три строки программы В следующими строками.

STA 2F LDA 3F СМРА 15,5(5:5) LDA 2F

-1.S 1

COMPUTE

.-1 (нли JMP COMPUTEX) О

Действие (N = 4)

ASSIGN(BUFl)

RELEASE, OUT BUFl

ASSIGN(BUF2)

RELEASE

ASSIGN(BUF3)

RELEASE

ASSIGN(BUF4)

RELEASE

ASSIGN (ожидать) BUFl назначен, OUT BUF2

RELEASE

89000U, при N = 3 -81500U и

LD5 DEC6 JNE JMP JMP 2H CON 3H ALF

13. JRED CONTROL(U) J6NZ .-1 I

14. Если ЛГ = 1, TO алгоритм нарушается (может произойти обращение к буферу во время выполнения В/В); в противном случае результатом этой конструкции будет наличие двух желтых буферов Это может оказаться полезным, если вычислительной программе понадобится обратиться к двум буферам одновременно, хотя это приводит к связыванию буферного пространства. В общем случае разность между количеством операций НАЗНАЧИТЬ и ОСВОБОДИТЬ должна быть неотрицательной и не превышать N.

15. и EQU О IN BUF3(U) V EQU 1 OUT BUF2(V) BUFl ORIG »+100 IN BUFl(U) BUF2 ORIG ♦+100 OUT BUF3(V) BUF3 ORIG *+100 DECl 3 TAPECPY IN BUFl(U) JIP IB

ENTl 99 OUT BUFl(V)

IH IN BUF2(U) HLT

OUT BUFl(V) END TAPECPY

Это частный случай алгоритма, показанного на рис. 26.

18. Частичное решение. В приведенных ниже алгоритмах t - это переменная, которая равна О, когда устройство В/В свободно, и 1, когда оно активно.

Алгоритм А (НАЗНАЧИТЬ,- подпрограмма для нормального состояния). Этот гилгоритм ничем не отличается от алгоритма 1.4.4А.

Алгоритм R (ОСВОБОДИТЬ; подпрограмма для нормального состояния). R1. Увеличить п на единицу.

R2. Есяи t = О, вызвать прерывание (с помощью команды INT) и в результате перейти к шагу ВЗ. I

Алгоритм В {Программа управления буферами, обрабатывающая прерывания).

81. Перезапустить главную программу.

82. Если п = О, присвоить t «- О и перейти к шагу В1.

83. Присвоить t i- 1 и инициировать В/В из буферной области, на которую указывает стрелка СЛЕДК.

84. Возобновить выполнение главной программы; выполнение условия "операция В/В завершена" приведет к прерыванию главной программы и переходу к шагу В5.

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

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

19. Есяи С < L, то tk = {к - 1)L, Uk = tk + Т и Vk = Uk + С тогда и только тогда, когда NL > Т+С- При С > L ситуация усложняется; имеем и/ь = {к - 1)С+Т и и*, = кС+Т тогда и только тогда, когда существуют целые щ < 02 < < Оп, такие, что tk = (к - 1)L + ПкР удовлетворяет неравенству Uk - Т >tk > Vk-N для N < к < п. Эквивалентным условием будет NC > Ьк при ЛГ < /; < п, где 6* = С + Г + ((/; - 1){С - L)) mod Р. Пусть cj = max{6(+i,... ,Ьп, 0}; тогда последовательность cj убывает и наименьшим значением N, при котором процесс остается стабильным, будет минимальное /. для которого ci/l < С Так как CJ < С + Г + Рис1 < L + r + п{С - L), это значение N никогда не превышает \mm{C + T + P,L + T + n{C-L)}IC]. [См. А. Itai, У. Raz, САСМ 31 (1988), 1339-1342.]

РАЗДЕЛ 2.1

1. (а) SUIT(NEXT(ТОР)) = SUIT(NEXT(242)) = SUIT(386) = 4. (b) Л.

2. Всегда, когда V является переменной связи, значение которой не равно Л (в противном случае выражение CONTENTS (V) не имеет смысла). Рекомендуется избегать использования LOC в таком контексте.

3. Пусть NEWCARD ч- ТОР, и если ТОР / Л, то ТОР <- NEXT (ТОР).

4. С1. Пусть X ч- LOC(TOP). (Для удобства можно сделать разумное предположение, что

ТОР = NEXT(LOC(ТОР)), а именно -что значение ТОР появляется в поле NEXT той ячейки, в которой оно хранится. Данное предположение относится и к программе (5); к тому же оно может избавить нас от необходимости создавать специальную процедуру для обработки случая, когда колода пуста.)

С2. Если NEXT(X) / Л, то X Ч- NEXT(X); затем повторить этот шаг.

СЗ. Пусть NEXT(X) ч- NEWCARD, NEXT(NEWCARD) Ч- Л, TAG(NEWCARD) Ч- 1

5. D1. Пусть X <г- LOC(TOP), Y ч- ТОР. (См. шаг С1. Согласно исходному предположению

Y / Л. Далее во всем алгоритме Y идет вслед за X в том смысле, что Y = NEXT(X).) D2. Если NEXT(Y) / Л, то X (- Y, Y (- NEXT(Y) Повторить этот шаг. D3. (Теперь NEXT(Y) = Л, поэтому Y указывает на последнюю (самую нижнюю) карту,

а X - на предпоследнюю.) Пусть NEXT(X) ч- Л, NEWCARD ч- Y.