Реализация структур управления

Реализация процедур read и write.

Идея буферизации.

Проблемы реализации ввода-вывода.

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

Кроме того, файлы имеют специфическую физическую организацию. Так, например, то, что с логической точки зрения является file of integer, физически может представлять последовательность блоков (физических записей), например, по 100 чисел в блоке.

Физическая организация. Помимо специфичных для каждого устройства особенностей, центральная проблемой ввода-вывода – существенно более низкая скорость обмена данными внешней памяти по сравнению с внутренней (оперативной). Пути решения этой проблемы за счёт распараллеливания обработки внутренних и внешних данных рассмотрим на примере стандартного Паскаля. В стандартном Паскале read и write – не операторы, но процедуры, реализованные с помощью операторов get и put. С каждым именем файла автоматически связывается переменная со стандартным именем f^, называемая буфером и имеющая для файла file of T тип T, для текстового – char. Оператор get(f) считывает очередную компоненту файла в переменную f^, put(f) записывает в файл содержимое буферной переменной.

get(f)~read(f,f^);

put(f)~write(f,f^);

read(f,x) ~ x:=f^; get(f);

write(f,e) ~ f^:=e; put(f);

Кроме того, с обработкой буфера связаны операторы: reset(f), который считывает первую компоненту файла (если есть), close(f) – выводит содержимое буфера в файл.

Суть идеи буферизации – распараллелить обмен со внешними носителями на два независимо выполняемые отдельные исполнителя:

1) Быстрый обмен в оперативной памяти;

2) Обмен между буфером и физическим файлом. То есть параллельно с основной программой работает копирование из файла в буфер. Так работают ввод и вывод.

Оставим в нашем мини-Паскале два оператора: оператор присваивания и бинарное присваивание вида y:=[yÅ]x, где Å - одна из базовых операций, к которым мы отнесём арифметические операции: +, *, -, div.

В реальности на ещё более низком уровне реализации (микропрограммирование) эти операции не базовые, но реализуются с помощью операций над битами (логические операции, операции сдвига и т.д.).

Принцип сведения содержательных операций для нас не нов (пример – сложение столбиком). Очевидно, такого присваивания достаточно для пошагового вычисления любых арифметических выражений.

Все структуры управления реализуются с помощью оператора условного перехода:

if B then goto M, где М – метка (адрес команды), а В – базовый предикат (= или ¹).

Упражнение. Выяснить, являются ли необходимыми операции сравнения. (нет).

if B then S₁ else S₂

if B then goto M;

S₂; goto M₂

M: S₁

M₂:

while B do S

S

N: if not B then goto M; S; goto N;

M:

M N:

+

Все остальные циклы и структуры выражаются через while.

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

Упражнение^*. Запрограммировать на мини-Паскале программу вычисления суммы 10 чисел.

Упражнение^*. Написать алгоритм построения по любой блок-схеме последовательности операторов в мини-Паскале.

Задача сложения 10-ти чисел:

var a:array[1..10] of integer;

begin

s:=0; i:=1;

while i<=10 do

begin

s:=s+a[i];

i:=succ(i);

end;

write(s);

end.

goto prog;

prog:

s:=0;

i:= 0;

p:=addr(A);

i:=1;

N: if i>10 then goto M;

s:=s+p^;

p:=p+cSizeOfInteger;

goto N;

M:

write(s);

Замечание: Потеря эффективности. В случае непроцедурного программирования на мини-Паскале мы могли бы сэкономить память (переменная i) и время выполнения за счёт трактовки p как счётчика цикла: if p<10*cSizeOfInteger.

Дата добавления: 2014-01-05