Таким образом, всего потребавалось 81500и; компьютер простаивал в промежутках 6000-8500, 10500-16000 и 69000-81500, т. е. всего 20500и; устройство вывода было свободно в промежутках 0-1000, 46000-47000 и 54500-59000, т. е. всего 6500и.

Для этой же программы создайте таблицу типа "время-действие", аналогичную приведенной выше, но при условии, что используются только два буфера.

10. [21] Выполните упр. 9, но только для четырех буферов.

11. [21] Выполните упр. 9, но только для одного буфера.

12. [24] Предположим, что алгоритм множественной буферизации, приведенный в тексте, используется для ввода с перфокарт. И пусть ввод должен быть прекращен сразу же, как только будет считана перфокарта, в колонке 80 которой содержится ".". Покажите, как следует модифицировать сопрограмму CONTROL (алгоритм В и программу В), чтобы ввод прекращался указанным образом.

13. [20] Пусть вывод выполняется с помощью алгоритмов буферизации. Какие команды нужно вставить в конце сопрограммы COMPUTE, приведенной в тексте раздела, чтобы гарантировать вывод всей информации из буферов?

► 14. [20] Предположим, в вычислительной программе нет чередования действий НАЗНАЧИТЬ и ОСВОБОДИТЬ, а есть только последовательность действий ...НАЗНАЧИТЬ... НАЗНАЧИТЬ... ОСВОБОДИТЬ ... ОСВОБОДИТЬ. Какое влияние это окажет на алгоритмы, описанные в тексте раздела? Может ли это оказаться полезным?

► 15. [22] Напишите законченную программу для MIX, которая копирует 100 блоков с накопителя на магнитной ленте под номером О на аналогичное устройство номер 1, используя только три буфера. Программа должна работать насто.11ько быстро, насколько это возможно.

16. [29] Сформулируйте алгоритм для зеленого-желтого-красного-фиолетового буферов, которые предложены на рис. 26, аналогичный алгоритмам множественной буферизации, приведенным в тексте раздела. Используйте три сопрограммы (одну для управления устройством ввода, другую - устройством вывода и третью-для вычислений).

17. [40] Переделайте алгоритм множественной буферизации для пула буферов; предусмотрите встроенные методы, которые не допускают замедления процесса из-за слишком большого объема опережающего ввода. Постарайтесь, по возможности, придать алгоритму красоту и изящество. Сравните свой метод с методами, в которых не используется пул, применяя их к реальным задачам.

► 18. [30] Предлагаемое расширение машины MIX позволяет прерывать вычисления, как будет описано ниже. Ваша задача в этом упражнении - модифицировать приведенные в тексте раздела алгоритмы и программы А, R и В, чтобы вместо команд JRED в них использовались эти средства прерывания.

Новые возможности MIX включают 3 999 дополнительных ячеек памяти с адресами от -3999 до -0001. У этой машины есть два внутренних "состояния"-нормальное и управляющее. В нормальном состоянии ячейки с -3999 по -0001 недоступны и машина MIX работает, как обычно. Когда происходит "прерывание", вызванное условиями, о которых речь пойдет позже, в ячейки с -0009 по -0001 заносится содержимое регистров машины MIX: гА - в -0009; г11-г16 -в -0008-0003; гХ -в -0002, а rJ, состояние флага переполнения, флага сравнения и адрес следующей команды сохраняются в ячейке -0001 в следующем виде:

Когда машина входит в управляющее состояние, ячейка, которой передается управление, выбирается в зависимости от типа прерывания.

Ячейка -0010 играет роль часов: через каждые lOOOu единиц времени число, содержащееся в этой ячейке, уменьшается на единиху; если в результате получается нуль, то происходит прерывани и управление передается в ячейку -ООН.

Новая команда MIX "INT" (С = 5, F = 9) работает следующим образом, (а) В нормальном состоянии при прерывании управление передается ячейке -0012. (Таким образом, программист может вызвать прерывание, чтобы установить связь с управляющей программой; адрес INT значения не имеет, хотя управляющая программа может использовать его в информационном смысле, чтобы отличать один тип прерывания от другого.) (Ь) В управляющем состоянии все регистры MIX загружаются информацией из ячеек с -0009 по -0001, затем компьютер возвращается в нормальное состояние и возобновляет выполнение. Время выполнения команды INT в обоих случаях составляет 2и.

Команда IN, OUT или ЮС, выданная в управляющем состоянии, вызовет прерывание сразу же по окончании операции В/В. В этом случае управление будет передано в ячейку -(0020+ номер устройства).

В управляющем состоянии прерывания никогда не происходят. Любые условия, вызывающие прерывания, "сохраняются" до появления следующей операции INT, и прерывание происходит после выполнения одной команды в нормальном состоянии программы.

► 19. [М28] Ввод-вывод небольших блоков данных с вращающегося устройства, например с магнитного диска, необходимо рассматривать особо. Предположим, программа работает с гг > 2 последовательными блоками информации следующим образом. Блок к начинает вводиться в момент tk, где ti = 0. Он назначается для обработки в момент Uk > tk + Т и освобождает буфер в момент Vk = Uk + С. Диск совершает один оборот через каждые Р единиц времени, и его считывающая головка пересекает начало нового блока через каждые L единиц времени; поэтому мы имеем tk = (А; - 1)L (по модулю Р). Так как обработка выполняется последовательно, имеем также Uk > Vk-i при 1 < А; < п. Всего у нас N буферов; следовательно, tk > Vk-N при N < к < п.

Насколько большим датжно быть N, чтобы время Vn завершения операции было минимальным из возможных, Т + С + (п - 1) max(L, С)? Сформулируйте общее правило определения наименьшего такого N. Проиллюстрируйте свое правило для L = 1, Р = 100, Т = .5,п = 100 и (а) С = .5; (Ь) С = 1.0; (с) С = 1.01; (d) С = 1.5; (е) С = 2.0; (f) С = 2.5; (g) С = 10.0; (h) С = 50.0; (i) С = 200.0.

Поэтому в нашем примере имеем (а) N = 1; (Ь) N = 2; (с) N = 3, cn = 2.5; (d) Л = 35, cn = 51.5; (е) N = 51, cn = 101.5; (f) = 41, cn == 102; (g) N = 11, cn = 109.5; (h) iV = 3, cn = 149.5; (i) N = 2, cn = 298.5.

1.4.5. История и библиография

Большинство фундаментальных методов, описанных в разделе 1.4, было независимо разработано разными программистами, и подробная история возникновения их идей, видимо, никогда не будет достоверно известна. Поэтому сейчас мы просто попытаемся перечислить и оценить наиболее важные работы, которые внесли вклад в развитие этих идей.

Подпрограммы были первым средством экономии сил программистов. Еще в 19 веке Чарльз Бэббидж (Charles Babbage) предвидел возможность создания библиотеки программ для своей аналитической машины [см. Charles Babbage and His Calculating Engines, под редакцией Филиппа (Philip) и Эмили (Emily) Моррисон (Morrison) (Dover, 1961), 56]. И теперь можно сказать, что его мечта сбылась в 1944 году, когда Грэйс М. Хоппер (Grace М. Hopper) написала подпрограмму вычисления функции sin X для счетно-решающего устройства Mark I, установленного

в Гарвардском университете [см. Mechanization of Thought Processes (London: Nat. Phys. Lab., 1959), 164]. Ho это еще были, в сущности, "открытые подпрограммы", т. е. такие подпрограммы,которые нужно вставлять в программу, а не связывать динамически. Управление машиной Бэббиджа, как и ткацким станком Жаккарда, осуществлялось с помощью набора перфокарт, а счетно-решающим устройством Mark I - с помощью бумажных перфолент. Таким образом, эти устройства существенно отличались от современных компьютеров с их хранящимися в памяти программами.

Связь с подпрограммами, реализуемая на машинах с хранящимися в памяти программами, где адрес, по которому нужно вернуть управление, передается в качестве параметра, была рассмотрена Германом Г. Голдстайном (Herman Н. Goldstine) и Джоном фон Нейманом (John von Neumann) в их широкоизвестной монографии по программированию, написанной между 1946 и 1947 годами [см. работу фон Неймана Collected Works 5 (New York: Macmillan, 1963), 215-235]. В их программах главная программа отвечала за передачу параметров в тело подпрограммы, а не за передачу необходимой информации в регистры. В Англии А. М. Тьюринг (А. М. Turing) уже в 1945 году разработал аппаратное и программное обеспечение связи с подпрограммами [см. работу Proceedings of а Second Symposium on Large-Scale Digital Calculating Machinery (Cambridge, Mass.: Harvard University, 1949), 87-90; B. E. Carpenter, R. W. Doran, editors, A. M. Turings ACE Report of 1946 and Other Papers (Cambridge, Mass.: MIT Press, 1986), 35, 36, 76, 78, 79]. Способы применения и строение универсальной библиотеки подпрограмм - это главная тема первого учебника по компьютерному программированию М. V. Wilkes, D. J. Wheeler, S. Gill, Tiie Preparation of Programs for an Electronic Digital Computer, 1st ed. (Reading, Mass.: Addison-Wesley, 1951) (Уилкс M., Уилер Д. и Гилл С. Составление программ для электронных счетных машин. - М.: Изд-во иностр. лит., 1953).

Слово "сопрограмма" придумал М. Э. Конвей (М. Е. Conway) в 1958 году, после того как он разработал это понятие и впервые применил его при построении программы на языке ассемблера. Почти в то же время сопрограммы независимо изучали Дж. Эрдвинн (J. Erdwinn) и Дж. Мернер (J. Merner). Они написали статью "Bilateral Linkage"*, которую посчитали недостаточно интересной, чтобы быть достойной опубликования. К сожалению, до сегодняшнего дня ни один экземпляр этой статьи, похоже, не сохранился. Первое опубликованное объяснение понятия сопрограммы появилось значительно позже в статье Конвея "Design of а Separable Transition-Diagram Compiler", САСМ 6 (1963), 396-408. На самом деле о примитивной форме связи сопрограмм уже кратко упоминалось в "советах по программированию" в первых публикациях, посвященных машине UNIVAC [The Programmer 1,2 (February, 1954), 4]. Удобное обозначение для сопрограмм в алголоподобных языках было введено в работе Dahl, Nygaard SIMULA I [САСМ 9 (1966), 671-678]. Несколько прекрасных примеров сопрограмм (включая сопрограммы репликации) появилось в книге 0.-J. Dahl, Е. W. Dijkstra, С. А. R. Ноаге Structured Programming, Chapter 3 (Дал У., Дейкстра Э., Хоор К. Структурное программирование / Пер. с англ. - М.: Мир, 1975 (сер. "Математическое обеспечение ЭВМ")). Первой программой-интерпретатором можно считать "универсальную машину Тьюринга", способную имитировать любые другие машины Тьюринга. Машины Тьюринга -

* "Двусторонняя связь". - Прим. перев.