1.3.4. Потоки ввода/вывода

В заключение обсудим функциональное представление интерактивных систем. Взаимодействующие (интерактивные) программы могут также пониматься как функции на потоках входных значений, которые в каче­стве результата порождают потоки выходных значений. Это делает воз­можным функциональное моделирование распределенных, взаимодейст­вующих систем. Такое толкование подходит как для моделирования программ, которые в интерактивном режиме обмениваются данными с человеком-пользователем, так и для коммуникации между программами.

Поток данных (англ. stream) над заданным множеством данных D есть конечная или бесконечная последовательность элементов из D. Итак, определим, как и в разделе о трассах:

D® = D* u D^x. Для потоков будем использовать следующие функции:

first: D^w -+ D¹,

rest: D^w -> D^(!\

, & . : D¹ x D^M -> D^w,

причем для непустого потока s вызов функции first(s) дает первый эле­мент потока. Если s есть пустая последовательность, то first(s) дает зна­чение 1.

Вызов функции rest(s) дает последовательность s без первого элемен­та. Если s пустая последовательность, то rest(s) дает пустую последова­тельность е. Для d е D дает d & s последовательность, которая начинает­ся с d и затем продолжается с s. Выражение 1 & s дает всегда пустую по­следовательность. Итак, для d е D\ s е D"' справедливо: first (d & s) = d,

( г если d = 1,

rest(d & s) = j

I s иначе,

f e если d = 1,

d & s = \

I <d>° s иначе.

С помощью этих основных функций на потоках могут быть определены функции, которые берут конечные или бесконечные потоки в качестве входа и вырабатывают конечные или бесконечные потоки в качестве вы­хода. В нотации языков программирования пишут

stream m

в качестве обозначения типа потока с множеством данных (M\{_L})^W, где М обозначает множество данных типа т.

Пример (функции, обрабатывающие потоки).

1. Следующая функция берет поток чисел в качестве входа, проверяет, являются ли числа четными, и вырабатывает соответствующий поток булевских значений (булевская функция even дает true, если се аргу­мент является четным, и false в противном случае; если аргумент есть 1, то функция even также выдает _L, так как even предполагается строгой):

fct test = ( stream nat s ) stream bool:

if even(first(s)) then true & test(rest(s)) else false & test(rest(s))

fi.

Аналогичную функцию получим через:

fct test = ( stream nat s ) stream bool: even(first(s)) & test(rest(s)).

2. Поэлементное умножение двух потоков

fct smult = ( stream nat si, s2 ) stream nat:

(first (si) * first (s2)) & smult (rest (si), rest(s2)).

(3) Бесконечный поток всех натуральных числе > п можно сгенерировать с помощью вызова функции enum(n), где enum определена следую­щим образом:

fct enum = ( nat n ) stream nat: n & enum(n + 1).

Обратим внимание, что функции test и smult в качестве входных данных могут обрабатывать как конечные, так и бесконечные потоки. □

Бесконечные потоки могут быть определены и рекурсивно, что становит­ся возможным благодаря использованию нестрогих функции для по­строения последовательностей. Функция & яатяется нестрогой справа. Например, для потока

1 & 1 & е

в качестве результата получается не пустой поток, а поток 1 & е. Функ­ция & является строгой слева в следующем смысле: если только в потоке

d[ & d₂ & d₃ & d₄ &...

одно из dj имеет значение 1 (и тем самым представляется расходящееся вычисление), поток в этом месте обрывается с е. Это моделирует поэле­ментное порождение и переработку потока слева направо.

Множество потоков частично упорядочено через префиксный поря­док с, который определяется с помощью конкатенации ° следующим об­разом:

si с s2 <=> 3 s3 е D^m: s2 = si ° s3.

Имеет место Si с s₂, если si является началом s₂. При таком порядке г. есть наименьший элемент. Рассмотренные до сих пор функции на пото­ках в этом порядке являются монотонными и непрерывными.

С помощью функций, обрабатывающих потоки, потоки элементов данных могут обрабатываться слева направо, пока эти элементы хорошо определены (т. е. * 1), и выдаваться элементы данных в качестве резуль­татов, пока эти результаты хорошо определены. Как только в одном из потоком встречается элемент со значением 1, поток обрывается.

Пустой ноток s представляет наименьший элемент в префиксном по­рядке и соответствует неопределенному потоку (аналог J. для других ти­пов). Так как функция & относительно этого наименьшего элемент?- префиксного порядка является нестрогой, мы можем задать также нетри­виальные рекурсивные объявления для потоков. В рекурсивном объявле­нии

stream nat s = 1 & s наименьшей неподвижной точкой в упомянутом выше порядке был бы е, если бы функция & была строгой, и тем самым имело бы место 1 & е = е. Но, поскольку это равенство несправедливо, в качестве наименьшей и единственной неподвижной точки получаем бесконечную последователь­ность I^х, с

first(I^х) = 1, rest(I^х) = I^х.

Конечно, вычисление потока s не может быть завершено в конечное время, так как s яатяется бесконечным потоком. Однако поток s в неза­вершающемся вычислении может аппроксимироваться все лучше и луч­ше за счет того, что вычисляется все больше и больше его элементов. В частности, завершается каждый из вызовов

first (rest (... rest (х)...)),

если умело организовать вычисление его значения (см. строгие и нестро­гие функции и их вычисление в части I).

Обратим внимание, что дтя рекурсивного объяатения потока s

stream nat s = first (s) & s

поток e яатяется неподвижной точкой, и как наименьший элемент яатя­ется также и наименьшей неподвижной точкой.

Пример (производитель/потребитель с потоками). С помощью обеих объ- яатенных ниже функций может быть описана задача производи­тель/потребитель:

fct produce = ( product х ) stream product:

if last_product(x)then x & s

else x & produce (next_product(x))

fi

fct consume = ( stream product y, m z ) m:

if ~-last_producl(first(y)) then consume (rest (y), put_in_box(first(y), z)) else put_injx>x(first(y), z)

fi.

При этом пусть put_in_box и next_product - заранее заданные функции, a last_product - заданный предикат. Мы используем также объяатения

stream product у = produce(xo), m b = consume(y, emptybox).

Оба эти равенства для взаимно рекурсивных объявлений потока у и ре­зультата b моделируют ситуацию производитель/потребитель. Поток у содержит последовательность элементов типа product, порождаемых вы­зовом produce^). О

Гибкость функций обработки потоков для моделирования интерактивных систем иллюстрируется следующим примером.

Пример (решето Эратосфена). Бесконечный поток всех простых чисел можно получить с помощью потока eratosthenes, который имеет следую­щее рекурсивное объявление (функция enum была определена выше):

stream nat eratosthenes = sieb(enum(2)).

Функция sieb (решето) задается следующим объявлением:

fct sieb = (stream nat s) stream nat:

first(s) & sieb(filter(first(s), s)).

Вспомогательная функция filter задается следующим объявлением (объявление функции divides было дано в части I, разд. 4.5.3):

fct filter = (nat ti, stream nat s) stream nat.

if divides(n, first(s)) then filter(n, rest(s))

else first(s) & filter(n, rest(s)) fi. Li

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

Функции обработки потоков могут также быть использованы для мо­делирования распределенных систем и их компонент. Проиллюстрируем это не одном маленьком примере.

1
Пользователь
Пользовательский ввод	1
Система
Системный ввод

Рис. 1.36. Диаграмма течения данных при взаимодействии пользоватая и систе.чы

Потоки и обрабатывающие их функции могут применяться для моде­лирования взаимодействия пользователя и системы. Пользователь поро­ждает поток заданий к системе, а система производит поток системных выводов как "заданий" для пользователя. Поведения пользователя сис­темой и самой системы соответствуют следующим функциям (предпола­гается, что функции enough, ready, newinput, newuserstate, newoutput и newsystemstate, а также типы userstate, systemstate, input и output опре­делены подходящим образом):

fct user = (stream output s, userstate t) stream input:

if enough(first(s), t) then f.

else ne\vinput(first(s), t) & user(rest(s), ne\vuserstate(first(s), t))

fi

fct system = (stream input s, systemstate t) stream output:

if ready(first(s), t) then к

elsene\voutput(first(s), t) & system(rest(s), newsyste instate (first (s), t))

fi.

Взаимодействие пользователя и системы определим через взаимно- ре курс и вные раве нства

stream output systemoutput = system(userinput, initial_system_state),

stream input userinput = initial_input & user(systemoutput,

initial_user_state).

Это взаимодействие можно тогда изобразить графически, как это демон­стрируется на рис. 1.36, в виде диаграммы потока данных.

Принцип наименьшей относительно префиксного порядка непод­вижной точки очень удобен для моделирования обратной связи и взаи­модействия между компонентами системы. Наименьшая неподвижная точка представляет самый короткий поток, который удовлетворяет урав­нению неподвижной точки. Путем выбора наименьшей неподвижной точки выражается простое требование: никакое значение не может быть принято до того, как оно будет послано. Тем самым адекватно моделиру­ется обратная связь. Если возникает ситуация взаимного ожидания (тупик), поток обрывается.

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

.2. Операционные системы и системное программирование

Под вычиыительной машиной (ЭВМ) понимается совокупность техниче­ских устройств (аппаратура, "жесткое оборудование", "hardware"), таких как процессоры, память, шина и периферийные устройства, т. е. техни­ческая система для переработки информации. Как мы видели в части II, программирование на языке машины утомительно и чревато ошибками. Поэтому ЭВМ без специальной системы программ, которая поддержива­ет функционирование машины, для пользователя практически бесполез­на. Программирование на чисто машинном уровне, без использования вспомогательных, весьма дорогостоящих программ, для пользователя бы­ло бы почти невозможно. Только наличие специальной поддерживающей программной системы, которая дает возможность пользователю проще организовать и реализовать свои индивидуальные применения, делает вычислительную машину работоспособным, непосредственно примени­мым инструментом. Семейство упомянутых системных программ называ­ется операционной системой (ОС). Вычислительная машина, снабженная операционной системой, называется вычислительной системой (ВС). Ко­нечно, даже для одной и той же ЭВМ можно создать и предоставить i распоряжение пользователей различные ОС.

Под ОС (в широком смысле) понимается комплекс программ, функ­ции которых определяют ВС с точки зрения пользователя. Работая н; машине с ОС, пользователь не обращается непосредственно к машинным операциям. Скорее он дает запросы (задания) программам ОС, которые затем уже используют машинные операции. ОС, как правило, содержат ь себе большое семейство программ. Объем ядра достаточно простой 0< составляет примерно 100-500 Кбайт программного кода. Новейшие 0< могут иметь значительно больший объем.

ОС реализует, в частности, интерфейс с пользователем. С точки зре ния пользователя, который не различает, да и не должен различать апп;¹ ратную и программную реализацию функций ВС, с помощью ОС вознг кает новая, "виртуальная" (воображаемая) машина. И чем точнее пользо­вательский интерфейс удовлетворяет потребности пользователя, те t проще и удобнее становится для него применение ЭВМ. Такол "дружественный" интерфейс является особенно важной предпосылка широкого применения ЭВМ пользователями, которые не имеют спей; - альных знаний в области информатики.

Таким образом, при проектировании ОС очень важно точно опреде­лить требования к ОС и преимущественные пели для предстоящих при­менений ВС, чтобы затем на этой основе позаботиться о возможно более оптимальном поведении системы для пользователя. При этом, естест­венно, некоторые из поставленных целей, например дружественность по отношению к пользователю и эффективность, вступают в конфликт меж­ду собой. Здесь относительно поведения ОС для нахождения компро­мисса должны быть заданы определенные приоритеты, которые и дают решение при наличии противоречивых точек зрения. Этого можно также достичь с помощью параметров, которые позволяют приспособить ОС к желаниям пользователей.

Предлагаемый пользователю интерфейс должен через ОС опираться на заранее заданные машинные функции. Здесь мы также говорим об ин­терфейсе - машинном интерфейсе. При этом ОС выполняет функцию моста между двумя интерфейсами - пользователя и аппаратуры. Характе­ристика аппаратуры, так же как и требования интерфейса с пользовате­лем, определяет внутреннюю структуру и специальные задачи ОС. И чем дальше расходятся функции пользовательского и машинного интерфей­сов, тем сложнее и дороже будет реализация ОС.

Проектирование и реализация ОС принадлежат к классическим зада­чам системного программирования. Другими задачами системного про­граммирования являются реализации языков программирования - реали­зация компиляторов, интерпретаторов и общего окружения программи­рования, т. е. вспомогательных служебных программ, таких, как программы для конвертирования, форматирования, переноса, редактиро­вания и т. д. В системном программировании используется ряд специ­фичных принципов и методик, с которыми мы кратко познакомимся в конце этой главы.