1.7.2. Буферизация последовательностей
Когда данные пересылаются со внешнего устройства хранения или на него, от%
дельные биты передаются потоком. Обычно устройство налагает строгие времен%
ные ограничения на пересылку данных. Например, если данные записываются на ленту, лента движется с фиксированной скоростью, и нужно, чтобы данные пере%
давались ей тоже с фиксированной скоростью. Когда источник данных исчерпан,
Файлы или последовательности
Фундаментальные структуры данных
42
движение ленты прекращается, и ее скорость падает быстро, но не мгновенно.
Поэтому на ленте остается промежуток между уже записанными данными и дан%
ными, которые поступят позже. Чтобы добиться высокой плотности данных, нуж%
но, чтобы число промежутков было мало, и для этого данные передают относи%
тельно большими блоками, чтобы не прерывать движения ленты. Похожие требования имеют место при работе с магнитными дисками, где данные размеща%
ются на дорожках с фиксированным числом блоков фиксированного размера. На самом деле диск следует рассматривать как массив блоков, причем каждый блок читается или записывается целиком и обычно содержит
2
k байтов с k = 8, 9, … 12
Однако в наших программах не соблюдается никаких временных ограничений.
Чтобы обеспечить такую возможность, передаваемые данные буферизуются. Они накапливаются в переменной%буфере (в оперативной памяти) и пересылаются, ког%
да накапливается достаточно данных, чтобы собрать блок нужного размера. Клиент буфера имеет к нему доступ только посредством двух процедур deposit и fetch
:
DEFINITION Buffer;
PROCEDURE deposit (x: CHAR);
PROCEDURE fetch (VAR x: CHAR);
END Buffer.
Буферизация
обладает тем дополнительным преимуществом, что она позволя%
ет процессу, который порождает/получает данные, выполняться одновременно с устройством, которое пишет/читает данные в/из буфера. На самом деле удобно рассматривать само устройство как процесс, который просто копирует потоки данных. Назначение буфера – в какой%то степени ослабить связь между двумя процессами, которые будем называть
производителем (producer) и
потребителем(consumer). Например, если потребитель в какой%то момент замедляет работу, он может нагнать производителя позднее. Без такой развязки часто нельзя обеспе%
чить полноценное использование внешних устройств, но она работает, только если скорость работы производителя и потребителя примерно равны в среднем,
хотя иногда и флуктуируют. Степень развязки растет с ростом размера буфера.
Обратимся теперь к вопросу представле%
ния буфера и для простоты предположим по%
ка, что элементы данных записываются в него
(deposited) и считываются из него (fetched)
индивидуально, а не поблочно. В сущности,
буфер представляет собой очередь, организо%
ванную по принципу «первым пришел – пер%
вым ушел» (first%in%first%out, или fifo). Если он объявлен как массив, то две индексные пере%
менные (скажем, in и out
) отмечают те пози%
ции, куда должны писаться и откуда должны считываться данные. В идеале такой массив должен быть бесконечным. Однако вполне до%
Рис. 1.8. Кольцевой буфер с индексами in и out
43
статочно иметь конечный массив, учитывая, что прочитанные элементы больше не нужны. Занимаемое ими место может быть использовано повторно. Это приво%
дит к идее
кольцевого буфера.
Операции записи и считывания элемента реализуются в следующем модуле,
который экспортирует эти операции как процедуры, но скрывает буфер и его ин%
дексные переменные – и тем самым механизм буферизации – от процесса%потреби%
теля. В таком механизме еще нужна переменная n
для подсчета количества элемен%
тов в буфере в данный момент. Если
N
обозначает размер буфера, то очевидным инвариантом является условие
0
≤
n
≤
N
. Поэтому операция считывания (проце%
дура fetch
) должна охраняться условием n
>
0
(буфер не пуст), а операция записи
(процедура deposit
) – условием n
<
N
(буфер не полон). Невыполнение первого условия должно считаться ошибкой программирования, а нарушение второго –
недостатком предложенной реализации (буфер слишком мал).
MODULE Buffer; (* ! *)
CONST N = 1024; (* ! *)
VAR n, in, out: INTEGER;
buf: ARRAY N OF CHAR;
PROCEDURE deposit deposit deposit deposit deposit (x: CHAR);
BEGIN
IF n = N THEN HALT END;
INC(n); buf[in] := x; in := (in + 1) MOD N
END deposit;
PROCEDURE fetch fetch fetch fetch fetch (VAR x: CHAR);
BEGIN
IF n = 0 THEN HALT END;
DEC(n); x := buf[out]; out := (out + 1) MOD N
END fetch;
BEGIN n := 0; in := 0; out := 0
END Buffer.
Столь простая реализация буфера приемлема, только если процедуры deposit и fetch вызываются единственным агентом (действующим то как производитель, то как потребитель). Но если они вызываются независимыми процессами, работаю%
щими одновременно, то такая схема оказывается слишком примитивной. Ведь тог%
да попытку записи в полный буфер или попытку чтения из пустого буфера следует рассматривать как вполне законные. Просто выполнение таких действий должно быть отложено до того момента, когда снова будут выполнены соответствующие
охраны (guarding conditions). В сущности, такие задержки и представляют собой необходимый механизм синхронизации между параллельными (concurrent) про%
цессами. Можно представить эти задержки следующими операторами:
REPEAT UNTIL n < N
REPEAT UNTIL n > 0
которые нужно подставить вместо соответствующих двух условных операторов,
содержащих оператор
HALT
Файлы или последовательности
Фундаментальные структуры данных
44
1.7.3. Буферизация обмена между
параллельными процессами
Однако представленное решение нельзя рекомендовать, даже если известно, что два процесса исполняются двумя независимыми агентами. Причина в том, что два процесса должны обращаться к одной и той же переменной n
и, следовательно,
к одной области оперативной памяти. Ожидающий процесс, постоянно проверяя значение n
, мешает своему партнеру, так как в любой момент времени к памяти может обратиться только один процесс. Такого рода ожиданий следует избегать, и поэтому мы постулируем наличие средства, которое, в сущности, скрывает в себе механизм синхронизации. Будем называть это средство сигналом (signal) и при%
мем, что оно предоставляется в служебном модуле
Signals вместе с набором при%
митивных операций для сигналов.
Каждый сигнал s
связан с охраной (условием)
P
s
. Если процесс нужно приостановить, пока не будет обеспечена истинность
P
s
(другим процессом), то он должен, прежде чем продолжить свою работу, дождаться сигнала s
. Это выража%
ется оператором
Wait(s)
. С другой стороны, если процесс обеспечивает истинность
P
s
, то после этого он сигнализирует об этом оператором
Send(s)
. Если для каждого оператора
Send(s)
обеспечивается истинность предусловия
P
s
, то
P
s можно рас%
сматривать как постусловие для
Wait(s)
DEFINITION Signals;
TYPE Signal;
PROCEDURE Wait (VAR s: Signal);
PROCEDURE Send (VAR s: Signal);
PROCEDURE Init (VAR s: Signal);
END Signals.
Теперь мы можем реализовать буфер в виде следующего модуля, который дол%
жен правильно работать, когда он используется независимыми параллельными процессами:
MODULE Buffer;
IMPORT Signals;
CONST N = 1024; (* ! *)
VAR n, in, out: INTEGER;
nonfull: Signals.Signal; (*n < N*)
nonempty: Signals.Signal; (*n > 0*)
buf: ARRAY N OF CHAR;
PROCEDURE deposit deposit deposit deposit deposit (x: CHAR);
BEGIN
IF n = N THEN Signals.Wait(nonfull) END;
INC(n); buf[in] := x; in := (in + 1) MOD N;
IF n = 1 THEN Signals.Send(nonempty) END
END deposit;
45
PROCEDURE fetch fetch fetch fetch fetch (VAR x: CHAR);
BEGIN
IF n = 0 THEN Signals.Wait(nonempty) END;
DEC(n); x := buf[out]; out := (out + 1) MOD N;
IF n = N–1 THEN Signals.Send(nonfull) END
END fetch;
BEGIN n := 0; in := 0; out := 0; Signals.Init(nonfull); Signals.Init(nonempty)
END Buffer.
Однако нужно сделать еще одну оговорку. Данная схема разрушается, если по случайному совпадению как производитель, так и потребитель (или два произво%
дителя либо два потребителя) одновременно обращаются к переменной n
, чтобы изменить ее значение. Непредсказуемым образом получится либо значение n+1
,
либо n–1
, но не n
. Так что нужно защищать процессы от опасных взаимных помех.
Вообще говоря, все операции, которые изменяют значения общих (shared) пере%
менных, представляют собой потенциальные ловушки.
Достаточным (но не всегда необходимым) условием является требование, что%
бы все общие переменные объявлялись локальными в таком модуле, для проце%
дур
которого гарантируется, что они
взаимно исключают исполнение друг друга.
Такой модуль называют
монитором (monitor) [1.7]. Условие взаимного исключе%
ния (mutual exclusion) гарантирует, что в любой момент времени только один про%
цесс сможет активно выполнять какую%либо процедуру монитора. Если другой процесс попытается вызвать некую процедуру того же монитора, его выполнение будет автоматически задержано до того момента, когда первый процесс завершит выполнение своей процедуры.
Замечание. Слова «активно выполнять» означают, что процесс выполняет лю%
бой оператор, кроме оператора ожидания.
Наконец, вернемся к задаче, в которой производитель или потребитель (или оба) требует, чтобы данные к ним поступали блоками определенного размера.
Показанный ниже модуль является вариантом предыдущего, причем предполага%
ется, что размер блоков данных равен
N
p элементов для производителя и
N
c эле%
ментов для потребителя. В этом случае обычно выбирают размер буфера
N
так,
чтобы он делился на
N
p и
N
c
. Чтобы подчеркнуть симметрию между операциями записи и считывания данных, вместо единственного счетчика n
теперь исполь%
зуются два счетчика, ne и nf
. Они показывают соответственно число пустых и за%
полненных ячеек буфера. Когда потребитель находится в состоянии ожидания, nf показывает число элементов, нужных для продолжения работы потребителя; а когда производитель находится в состоянии ожидания, то ne показывает число элементов, необходимых для продолжения работы производителя. (Поэтому ус%
ловие ne + nf = N
выполняется не всегда.)
MODULE Buffer;
IMPORT Signals;
CONST Np = 16; (* *)
Nc = 128; (* *)
Файлы или последовательности
Фундаментальные структуры данных
46
N = 1024; (* ! , Np Nc*)
VAR ne, nf: INTEGER;
in, out: INTEGER;
nonfull: Signals.Signal; (*ne >= 0*)
nonempty: Signals.Signal; (*nf >= 0*)
buf: ARRAY N OF CHAR;
PROCEDURE deposit deposit deposit deposit deposit (VAR x: ARRAY OF CHAR);
BEGIN
ne := ne – Np;
IF ne < 0 THEN Signals.Wait(nonfull) END;
FOR i := 0 TO Np–1 DO buf[in] := x[i]; INC(in) END;
IF in = N THEN in := 0 END;
nf := nf + Np;
IF nf >= 0 THEN Signals.Send(nonempty) END
END deposit;
PROCEDURE fetch fetch fetch fetch fetch (VAR x: ARRAY OF CHAR);
BEGIN
nf := nf – Nc;
IF nf < 0 THEN Signals.Wait(nonempty) END;
FOR i := 0 TO Nc–1 DO x[i] := buf[out]; INC(out) END;
IF out = N THEN out := 0 END;
ne := ne + Nc;
IF ne >= 0 THEN Signals.Send(nonfull) END
END fetch;
BEGIN
ne := N; nf := 0; in := 0; out := 0;
Signals.Init(nonfull); Signals.Init(nonempty)
END Buffer.
1.7.4. Ввод и вывод текстаПод стандартным вводом и выводом мы понимаем передачу данных в ту или иную сторону между вычислительной системой и внешними агентами, например чело%
веком%оператором. Достаточно типично, что
ввод производится с клавиатуры,
а вывод – на экран дисплея. Для таких ситуаций характерно, что информация представляется в форме, понятной человеку, и обычно состоит из последователь%
ности литер. То есть речь идет о тексте. Отсюда еще одно усложнение, характерное для реальных операций ввода и вывода. Кроме передачи данных, в них выполняет%
ся еще и преобразование представления. Например, числа, обычно рассматривае%
мые как неделимые сущности и представленные в двоичном виде, должны быть преобразованы в удобную для чтения десятичную форму. Структуры должны представляться так, чтобы их элементы располагались определенным образом, то есть форматироваться.
Независимо от того, что это за преобразование, задача заметно упрощается,
если снова привлечь понятие последовательности. Решающим является наблюде%
47
ние, что если набор данных можно рассматривать как последовательность литер,
то преобразование последовательности может быть реализовано как последова%
тельность (одинаковых) преобразований элементов:
T(0
, s
1
, ... , s n–1
>) = 0
), T(s
1
), ... , T(s n–1
)>
Исследуем вкратце действия, необходимые для преобразования представле%
ний натуральных чисел для ввода и вывода. Математическим основанием послу%
жит тот факт, что число x
, представленное последовательностью десятичных цифр d = , ... , d1, d0>
, имеет значение x = S
S
S
S
Si: i = 0 .. n–1: d i
* 10
i x = d n–1
× 10
n–1
+ d n–2
× 10
n–2
+ … + d
1
× 10 + d
0
x = (… (d n–1
× 10 + d n–2
)
× 10 + … + d
1
)
× 10 + d
0
Пусть теперь нужно прочесть и преобразовать последовательность d
,
а получившееся числовое значение присвоить переменной x
. Следующий простой алгоритм останавливается при считывании первой литеры, не являющейся циф%
рой (арифметическое переполнение не рассматривается):
x := 0; Read(ch);
(* ADruS174.% '- *)
WHILE ("0" <= ch) & (ch <= "9") DO
x := 10*x + (ORD(ch) – ORD("0")); Read(ch)
END
В случае вывода преобразование усложняется тем, что разложение значения x
в набор десятичных цифр дает их в обратном порядке. Младшая значащая цифра порождается первой при вычислении x MOD 10
. Поэтому требуется промежуточ%
ный буфер в виде очереди типа «первым пришел – последним вышел» (то есть стека). Будем представлять ее массивом d
с индексом i
и получим следующую программу:
i := 0;
(* ADruS174.-'% *)
REPEAT d[i] := x MOD 10; x := x DIV 10; INC(i)
UNTIL x = 0;
REPEAT DEC(i); Write(CHR(d[i] + ORD("0")))
UNTIL i = 0
Замечание. Систематическая замена константы 10 в этих алгоритмах на поло%
жительное целое B даст процедуры преобразования для представления по основа%
нию B. Часто используется случай B = 16 (шестнадцатеричное представление),
тогда соответствующие умножения и деления можно реализовать простыми сдвигами двоичных цифр.
Очевидно, было бы неразумным детально описывать в каждой программе та%
кие часто встречающиеся операции. Поэтому постулируем наличие вспомога%
тельного модуля, который обеспечивает чаще всего встречающиеся, стандартные операции ввода и вывода для чисел и цепочек литер. Этот модуль используется в большинстве программ в этой книге, и мы назовем его
Texts
. В нем определен
Файлы или последовательности
Фундаментальные структуры данных
48
тип
Text
, а также типы объектов%бегунков для чтения (
Reader)
и записи (
Writer
)
в переменные типа
Text
, а
также процедуры для чтения и записи литеры, целого числа и цепочки литер.
Прежде чем дать определение модуля
Texts
, подчеркнем существенную асим%
метрию между вводом и выводом текстов. Хотя текст порождается последова%
тельностью вызовов процедур вывода целых и вещественных чисел, цепочек ли%
тер и т. д., ввод текста посредством вызова процедур чтения представляется сомнительной практикой. Дело здесь в том, что хотелось бы читать следующий элемент, не зная его типа, и определять его тип
после чтения. Это приводит к поня%
тию
сканера (scanner), который после каждой попытки чтения позволяет прове%
рить тип и значение прочитанного элемента. Сканер играет роль бегунка для фай%
лов. Однако тогда нужно наложить ограничения на синтаксическую структуру считываемых текстов. Мы определим сканер для текстов, состоящих из последо%
вательности целых и вещественных чисел, цепочек литер, имен, а также специаль%
ных литер. Синтаксис этих элементов задается следующими правилами так назы%
ваемой расширенной нотации Бэкуса–Наура (EBNF, Extended Backus Naur Form;
чтобы точнее отразить вклад авторов нотации в ее создание, аббревиатуру еще раскрывают как Extended Backus Normal Form, то есть «расширенная нормальная нотация Бэкуса» –
прим. перев.):
item =
integer | RealNumber | identifier | string | SpecialChar.
integer =
[
“–”] digit {digit}.
RealNumber = [
“–”] digit {digit} “.” digit {digit} [(“E” | “D”)[“+” |
“–” digit {digit}].
identifier =
letter {letter | digit}.
string =
‘”’ {any character except quote} ‘”’.
SpecialChar =
“!” | “?” | “@” | “#” | “$” | “%” | “^” | “&” | “+” | “–” |
“*” | “/” | “\” | “|” | “(” | “)” | “[” | “]” | “{” | “}” |
“<” | “>” | “.” | “,” | “:” | “;” | “”.
Элементы разделяются пробелами и/или символами конца строк.
DEFINITION Texts;
(* ADruS174_Texts *)
CONST Int = 1; Real = 2; Name = 3; Char = 4;
TYPE Text, Writer;
Reader = RECORD eot: BOOLEAN END;
Scanner = RECORD class: INTEGER;
i: INTEGER;
x: REAL;
s: ARRAY 32 OF CHAR;
ch: CHAR;
nextCh: CHAR
END;
PROCEDURE OpenReader (VAR r: Reader; t: Text; pos: INTEGER);
PROCEDURE OpenWriter (VAR w: Writer; t: Text; pos: INTEGER);
PROCEDURE OpenScanner (VAR s: Scanner; t: Text; pos: INTEGER);
PROCEDURE Read (VAR r: Reader; VAR ch: CHAR);
49
PROCEDURE ReadInt (VAR r: Reader; VAR n: INTEGER);
PROCEDURE Scan (VAR s: Scanner);
PROCEDURE Write (VAR w: Writer; ch: CHAR);
PROCEDURE WriteLn (VAR w: Writer); (* v *)
PROCEDURE WriteString (VAR w: Writer; s: ARRAY OF CHAR);
PROCEDURE WriteInt (VAR w: Writer; x, n: INTEGER); (* x
n . n v , ,
*)
PROCEDURE WriteReal (VAR w: Writer; x: REAL);
PROCEDURE Close (VAR w: Writer);
END Texts.
(Выше добавлена отсутствующая в английском оригинале процедура ReadInt, ис%
пользуемая в примерах программ
– прим. перев.)
Мы требуем, чтобы после вызова процедуры
Scan(S)
для полей записи
S
выпол%
нялось следующее:
S.class = Int означает, что прочитано целое число, его значение содержится в
S.i
;
S.class = Real означает, что прочитано вещественное число, его значение со%
держится в
S.x
;
S.class = Name означает, что прочитана цепочка литер, она содержится в
S.s
;
S.class = Char означает, что прочитана специальная литера, она содержится в
S.ch
;
S.nextCh содержит литеру, непосредственно следующую за прочитан%
ным элементом, которая может быть пробелом.
Скачать 2.67 Mb.