Д. Кнут - Искусство программирования том 1 (1119450), страница 61
Текст из файла (страница 61)
Составьте схему расположения буферных областей и объясните, какие команды необходимо (если необходимо вообще) использовать в начале и в конце программы, чтобы первый и последний блоки наверняка были записаны правильно. В случае необходимости последний блок следует заполнить нулями. 4. [М20] Покажите, что если программа использует единственное устройство В/В, то при благоприятных обстоятельствах можно сократить время ее выполнении наполовину путем буферизации В/В.
Но нельзя более чем в два раза сократить время выполнения по сравнению с небуферизированным В/В. 5. [М21] Обобщите решение предыдущего упражнения для случая, когда программа работает не с одним, а с и устройствами В/В. 6. [12] Какие команды нужно поместить в начале программы, чтобы подпрограмма ЧОМО1М (4) начала правильно работать? (Например, в индексном регистре 6 должно что-шо содержаться.
) 7. [22] напишите подпрограмму с именем 90301м, которая, в основном, аналогична (4), за исключением того, что в ней не используется маркер конца блока. 6. [11] В тексте раздела описывается гипотетический сценарий ввода, начало которого показано на рис. 23, а продолжение — на рис. 24, (а), (Ь) и (с). Дайте интерпретацию такому же сценарию, но при условии, что выполняется вывод на АЦПУ, а не ввод с перфокарт. (Например, что происходит в момент, показанный на рис. 23?) 9. [21] Программу, в результате выполнения которой содержимое буферов выглядит, как показано на рис.
27, можно охарактеризовать с помощью следующего списка промежутков времени: А, 1000, В, 1000, А, 1000, В, 1000, А, 1000, В, 1000, А, 1000, В, 1000, А, 7000, В, 5000, А, 7000, В, 5000, А, 7000, В, 5000, А, 7000, В, 5000, А, 1000, В, 1000, А, 2000, В, 1000. Этот список расшифровывается так: "Назначить, вычислять в течение 1000и, освободить, вычислять в течение 1000и, назначить, ..., вычислять в течение 2000и, освободить, вычислять в течение 1000и". Приведенные промежутки времени вычислений не включают о о о Устройство вывода Компью- '~Д(А+НА. „~~ ккк к А А к к.
к В а Я И. й З оЕо о 3 ю В оо оч оо оо ' ' о Время — + Зеленый Об буфер чення Желтый уфер стройстве тивво :устройство 'свободно Красный бУфеР Красный буфер содержимое которого выводится А Назначить Освободить Инициировать вывод Рнс. 27.
Вывод с использованием трех буферов (см. упр. 9). какие-либо периоды, когда компьютер ожидает устройство вывода, чтобы занять его (как в случае четвертой операции "назначить" на рис, 27). Выходное устройство затрачивает на вывод каждого блока по 7500и времени. В следующей таблице перечислены действия, которые соответствуют промежуткам времени, показанным на рис. 27.
Время 0 1000 2000 3000 4000 5000 6000 8500 9500 10500 16000 23000 23500 28000 31000 35000 Действие АЯБИМ(ВОР1) ВИ.ЕАЯЕ, СОТ ВОР1 АЯБТСМ(ВОР2) ВИ.ЕАБЕ АБЯ1СМ(ВОРЗ) ВИ.ЕАЯЕ АЯБ1СМ (ждать) ВОР1 назначен, ООТ ВОР2 ВИ.ЕАЯЕ АББИМ (ждать) ВОР2 назначен, СОТ ВОРЗ ЕИ,ЕАЯЕ СОТ ВОР1 АЯБТСМ(ВОРЗ) ООТ ВОР2 ВЕЬЕАБЕ Время 38500 40000 46000 47000 52000 54500 59000 64000 65000 66000 66500 68000 69000 74000 81500 Действие ООТ ВОРЗ АБЯХСМ(ВОР1) Вывод остановлен. ВЕ1.ЕАБЕ, ООТ ВОР1 АЯБ1СМ(ВОР2) Вывод остановлен. ВЕАЕАБЕ, ООТ ВОР2 АББ1СМ(ВОРЗ) ВЕЬЕАЯЕ АББ1СМ(ВОР1) СОТ ВОРЗ ВЕАЕАБЕ Вычисления прекращены.
ООТ ВОР1 Вывод остановлен. Таким образом, всего потребнвалось 81500и; компьютер простаивал в промежутках 6000- 8500, 10500-16000 и 69000-81500, т. е. всего 20500и; устройство вывода было свободно в промежутках 0 — 1000, 46000 — 4?000 и 54500-59000, т. е, всего 6500и. Для этой же программы создайте таблицу типа "время — действие", аналогичную приведенной выше, но при условии, что используются только деа буфера. 10. [21] Выполните упр. 9, но только для четырех буферов. 11. [ВХ] Выполните упр. 9, но только для одного буфера.
12. [24] Предположим, что алгоритм множественной буферизации, приведенный в тексте, используется для ввода с перфокарт. И пусть ввод должен быть прекращен сразу же, как только будет считана перфокарта, в колонке 80 которой содержится ".". Покажите, как следует модифицировать сопрограмму СОМТНОЬ [алгоритм В и программу В), чтобы ввод прекращался указанным образом. 13. [20] Пусть вывод выполняется с помощью алгоритмов буферизации.
Какие команды нужно вставить в конце сопрограммы СОМРОТБ, приведенной в тексте раздела, чтобы гарантировать вывод всей информации из буферов? ь 14. [80] Предположим, в вычислительной программе нет чередования действий НАЗНАЧИТЬ и ОСВОБОДИТЬ, а есть только последовательность действий ... НАЗНАЧИТЬ ... НАЗНАЧИТЬ ... ОСВОБОДИТЬ... ОСВОБОДИТЬ. Какое влияние зто окажет на алгоритмы, описанные в тексте раздела? Может ли это оказаться полезным? ь 15. [ВВ] Напишите законченную программу для М1Х, которая копирует 100 блоков с накопителя на магнитной ленте под номером 0 на аналогичное устройство номер 1, используя только три буфера. Программа должна работать настолько быстро, насколько зто возможно. 16.
[80] Сформулируйте алгоритм для зеленого-желтого-красного-фиолетового буферов, которые предложены на рис. 26, аналогичный алгоритмам множественной буферизации, приведенным в тексте раздела. Используйте три сопрограммы (одну для управления устройством ввода, другую — устройством вывода и тре~ью — для вычислений). 17. [40] Переделайте алгоритм множественной буферизации для пула буферов; предусмотрите встроенные методы, которые не допускают замедления процесса из-за слишком большого объема опережающего ввода.
Постарайтесь, по возможности, придать алгоРитму красоту и изящество. Сравните свой метод с методами, в которых не используется пул, применяя их к реальным задачам. ь 18. [00] Предлагаемое расширение машины М1Х позволяет прерывать вычисления, как будет описано ниже. Ваша задача в этом упражнении — модифицировать приведенные в тексте раздела алгоритмы и программы А, В и В, чтобы вместо команд ХББО в них использовались эти средства прерывания. Новые возможности М1Х включают 3 999 дополнительных ячеек памяти с адресами от †39 до †00. У этой машины есть два внутренних "состояния" — норлгальнае и Нпраеллюи1ее. В нормальном состоянии ячейки с †39 по †00 недоступны и машина М1Х работает,как обычно. Когда происходит "прерывание", вызванное условиями, о которых речь пойдет позже, в ячейки с †00 по †00 заносится содержимое регистров машины М1Х: гА — в -0009; гП-г16 — в — 0008 — 0003; гХ вЂ” в — 0002, а г1, состояние флага переполнения, флага сравнения и адрес следующей команды сохраняются в ячейке — 0001 в следующем виде: Когда машина входит в управляющее состояние, ячейка, которой передается управление, выбирается в зависимости от типа прерывания.
Ячейка — 0010 игрлет роль часов: через каждые 1000и единиц времени число, содержащееся в этой ячейке, уменьшается на единицу; если в результате получается нуль, то происходит прерывания и управление передается в ячейку — 0011. Новая команда ИТХ "1Ит" (С = 5, Р = 9) работает следующим образом, (а) В нормальном состоянии при прерывании управление передается ячейке -0012. (Таким образом, программист может вызвать прерывание, чтобы установить связь с управляющей программой; адрес 1ИТ значения не имеет, хотя управляющая программа может использовать его в информационном смысле, чтобы отличать один тип прерывания от другого.) (Ь) В управляющем состоянии все регистры Н1Х загружаются информацией из ячеек с -0009 по -0001, затем компьютер возвращается в нормальное состояние и возобновляет выполнение.
Времн выполнения команды 1ИТ в обоих случаях составляет 2ш Команда 1И, ООТ или 100, выданная в упраеллющем состоянии, вызовет прерывание сразу же по окончании операции В/В. В этом случае управление будет передано в ячейку -(0020ч-номер устройства). В управляющем состоянии прерывания никогда ие происходят. Любые условия, вызывающие прерывания, "сохраняются" до появления следующей операции 1ИТ, и прерывание происходит после выполнения одной команды в нормальном состоянии программы. ь 19.
(М88] Ввод-вывод небольших блоков данных с вращающегося устройства, например с магнитного диска, необходимо рассматривать особо. Предположим, программа работает с и > 2 последовательными блоками информации следующим образом. Блок й начинает вводиться в момент йм где !1 = О. Он назначается для обработки в момент иь > Гл + Т и освобождает буфер в момент ел — — ил + С. Диск совершает один оборот через каждые Р единиц времени, и его считывающая головка пересекает начало нового блока через каждые б единиц времени; поэтому мы имеем гл ш (!г — 1)5 (по модулю Р).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
