AOP_Tom1 (1021736), страница 64
Текст из файла (страница 64)
[МЗМ) Ввод-вывод небольших блоков данных с вращающегося устройства, например с магнитного диска, необходимо рассматривать особо. Предположим, программа работает с п > 2 последовательными блоками информации следующим образом. Блок й начинает ввОдИтЬСя В МОмЕнт Гю где 1~ = О. Он назначается для обработки в момент щ > Гв + Т и освобождает буфер в момент еэ = иь + С. Диск совершает один оборот через каждые Р единиц времени, и его считывающая головка пересекает начало нового блока через каждые 1 единиц времени; поэтому мы имеем гь ж (!с — 1)е (по модулю Р). так как обработка выполняется последовательно, имеем также пэ > щ ~ при 1 < к < п.
Всего у нас Х буферов; следовательно, !ь > щ я при л' < А < и. Насколько большим должно быть Х, чтобы время о завершения операции было минимальным из возможных, Т+ С + (и — 1) шах(Т., С)? Сформулируйте общее правило определения наименьшего такого Х. Проиллюстрируйте свое правило для 5 = 1, Р = 100, Т=.5, п = 100 и(а) С=.5; (Ь) С=1.0; (с) С=1.01; (4) С=1.5: (е) С=2.0; (1) С= 2.5; (М) С = 10.0; (Ь) С = 50.0; (!) С = 200.0. Поэтому в нашем примере имеем (а) Ю = 1; (Ь) М = 2; (с) Ф = 3, ск = 2.5; (с1) Ю = 35, ся = 51.5; (е) 5! = 51, сл = 101.5; (!) Х = 41, ся ж 102; (3) 5! = 11, ся = 109.5; (Ь) !М = 3 ск = 149.5; (!) !М = 2, сь = 298 5.
1.4.5. История и библиография Большинство фундаментальных методов, описанных в разделе 1.4, было независимо разработано разными программистами, и подробная история возникновения их идей, видимо, никогда не будет достоверно известна. Поэтому сейчас мы просто попытаемся перечислить и оценить наиболее важные работы, которые внесли вклад в развитие этих идей. Подпрограммы были первым средством экономии сил программистов. Еще в 19 веке Чарльз Бэббидж (СЬаг(еэ ВаЬЬаяе) предвидел возможность создания библиотеки программ для своей аналитической машины [см.
СЬаг!еэ ВаЬЬаае алд Н!э Са)си!абпя Епятеэ, под редакцией Филиппа (РЬН)р) и Эмили (Ет!!у) Моррисон (МогПэоп) (Ротег, 1961), 56). И теперь можно сказать, что его мечта сбылась в 1944 году, когда Грзйс М. Хоппер (Стасе М. Норрег) написала подпрограмму вычисления функции гбпх для счетно-решающего устройства МагЕ 1, установленного в Гарвардском университете [см. МесЛап!гаНоп оГ ТЬоикЬ! Ргосеяяея (1 оптов: Ха!.
РЬуя. 1 аЬ., 1959), 164). Но это еще были, в сущности, "открытые подпрограммы", т. е. такие подпрограммы, которые нужно вставлять в программу, а не связывать динамически. Управление машиной Бэббиджа, как и ткацким станком Жаккарда, осуществлялось с помощью набора перфокарт, а счетно-решающим устройством Магй 1 — с помощью бумажных перфолент. Таким образом, зти устройства существенно отличались от современных компьютеров с их хранящимися в памяти программами. Связь с подпрограммами, реализуемая на машинах с хранящимися в памяти программами, где адрес, по которому нужно вернуть управление, передается в качестве параметра, была рассмотрена Германом Г.
Голдстайном (Неппап Н. Со16яс!пе) и Джоном фон Нейманом (доЬп уоп Хешпапп) в их широкоизвестной монографии по программированию, написанной между 1946 и 1947 годами [см. работу фон Неймана Со!!есяес! И~от!ся 5 (Хезг Ъог1с Маспи!!ап, 1963), 215-235). В их программах главная программа отвечала за передачу параметров в тело подпрограммы, а не за передачу необходимой информации в регистры. В Англии А.
М. Тьюринг (А. М. Тиг1п8) уже в 1945 году разработал аппаратное и программное обеспечение связи с подпрограммами [см. работу Ргосеес!!п8я оу а 8есопс( Бутроя!ит оп Ьагйе-Вся!е Р!8!!а! Са!си!аг!п8 МасЫпегу (СашЬг!с!8е, Маяяс Нагьагд 11п!уегыту, 1949), 87 — 90; В. Е. Сагреп!ег, Н. %. Рогап, ес!!!огя, А.
М. Тиг!п8'я АСЕ Яерогг о!'1946 апс! 01Ьег Рарегя (СашЬг1с!ке, Маяяс М1Т Ргеяя, 1986), 35, 36, 76, 78, 79]. Способы применения и строение универсальной библиотеки подпрограмм — это главная тема первого учебника по компьютерному программированию М. У. ЪЧ1!!сея, Р. 1. %Ьее!ег, Б. 6111, ТЛе Ргерагабоп оГ Ргобгвтя Рог ап Е!ес!гоп!с Р!8!!а! Сотри!ег, 1я! ес1. (Влас!!п81 Маяяз АсЫ!яоп-Жея!еу, 1951) (Уилкс М., Уилер Д, и Гилл С.
Составление программ для электронных счетных машин.— Мс Изд-во иностр, лит., 1953). Слово "сопрограмма" придумал М. Э. Конвей (М. Е. Сопкау) в 1958 году, после тою как он разработал зто понятие и впервые применил его при построении программы на языке ассемблера. Почти в то же время сопрограммы независимо изучали Дж. Эрдвинн (1. Егс)кчпп) и Дж, Мернер (Л. Мегпег). Они написали статью вВ11а!ега1 Ып1са8еве, которую посчитали недостаточно интересной, чтобы быть достойной опубликования. К сожалению, до сегодняшнего дня ни один экземпляр этой статьи, похоже, не сохранился. Первое опубликованное объяснение понятия сопрограммы появилось значительно позже в статье Конвея "Рея!8п о( а ЯерагаЫе Тгапя!1!оп-Р!абгаш Сошр!!ег", САСМ 6 (1963), 396 — 408.
На самом деле о примитивной форме связи сопрограмм уже кратко упоминалось в "советах по программированиюв в первых публикациях, посвященных машине 1!Х1УАС [ТЬе Ргойгаглтег 1,2 (РеЬгиагу, 1954), 4[. Удобное обозначение для сопрограмм в алголоподобных языках было введено в работе РаЫ, Хубаагс! 81МН,А 1 [САСМ 9 (1966), 671 — 678!.
Несколько прекрасных примеров сопрограмм (включая сопрограммы репликации) появилось в книге 0.-3. РаЫ, Е. %. Р!1)ся!га, С. А. Н. Ноаге Яггиссигес( Ргодгатт1п8, СЬартег 3 (Дал У., Дейкстра Э., Хоор К. Структурное программирование / Пер. с англ. — Мс Мир, 1975 (сер. "Математическое обеспечение ЭВМв)). Первой программой-интерпретатором можно считать "универсальную машину Тьюринга", способную имитировать любые другие машины Тьюринга.
Машины Тьюринга— ь "двусторонняя связь". †Пр, верее. это не реальные компьютеры, а теоретические конструкции, использующиеся для доказательства того, что некоторые задачи нельзя решить с помощью алгоритмов. Программы-интерпретаторы в традиционном смысле упоминал в 1946 году Джон Мочли (доЬп МаисЫу) в своих лекциях, которые он читал в Школе Мура (Мооге ЯсЬоо1). Самыми известными из первых интерпретаторов, главным назначением которых было обеспечение удобных средств выполнения операций с плавающей точкой, были программы для машины ЖЬ!г!кй!пб 1 (разработанные Ч. В. Адамсом (С.
%. Абаспв) и др.) и для машины П!!ас 1 (разработанные Д. Дж. Уилером (В, Л. %Ьее!ег) и др.). Тьюринг также принимал участие в их разработке; интерпретирующие системы для компьютера Р11ос АСЕ были написаны под его руководством. Более подробно о положении дел с интерпретаторами в начале 50-х годов говорится в статье Л. М. Веппесс, Б. С. Рппа М.
1,. ИЪобв, "1пСегргесабие ЯиЬ-гоис!пав", Ргос. АСМ !УаС. СолЕ. (1952), 81 — 87 [см. также различные статьи в журнале Ргосеейпйв ог" сЬе Яутров!ит оп АисотаС!с Ргодгаттт8 Еог Р~8!са! Сотрисегв (1954), издаваемом Департаментом морских исследований (Вашингтон, федеральный округ Колумбия). Наиболее широкоиспользуемой программой-интерпретатором, вероятно, была "1ВМ 701 Яреес!соб!п8 вувСегп" Джона Бэкуса (ЗоЬп Вас!сив) [см.
7АСМ 1 (1954), 4 — 6]. Этот интерпретатор был несколько модифицирован и искусно переписан для 1ВМ 650 В. М. Волонтисом (У. М. 19о!опс!в) и другими из компании Ве1! Те!ерЬопе БаЬогасог!ев; их программа "Вей 1псегргебге Яувсегп" приобрела широкую популярность. Интерпретирующие системы 1Рс., которые были разработаны в начале 1956 года А.
Ньювеллом (А. 5!еве!!), Дж. К. Шоу (3. С. ЯЬак) и Г. А. Саймоном (Н. А. Яппоп) для совершенно других целей (см. раздел 2.6), широко использовались для обработки списков. Как уже упоминалось во введении к разделу 1.4.3, о современных способах применения интерпретаторов в компьютерной литературе, как правило, говорится "на ходу" [см. ссылки на статьи, перечисленные в этом разделе, в которых интерпретаторы обсуждаются более подробно].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
