Циклическая очередь
spos 2
1 Queue +--------------------------------+
at Start-up ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+--------------------------------+
rpos 3
spos 2
4 Qstore('A') +--------------------------------+
¦A ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+--------------------------------+
rpos 3
spos 2
4 Qstore('B') +--------------------------------+
¦A ¦B ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+--------------------------------+
rpos 3
spos 2
5 Qreirieve +--------------------------------+
¦A ¦B ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+--------------------------------+
rpos 3
spos 2
5 Qreirieve +--------------------------------+
¦A ¦B ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+--------------------------------+
rpos 3
spos 2
4 Qstore('C') +--------------------------------+
¦A ¦B ¦C ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
+--------------------------------+
rpos 3
Рис.5. Указатель поиска преследует указатель свободного мес-
та в очереди:
1 - очередь в исходном положении;
2 - указатель свободного места в очереди;
3 - указатель следующего выбираемого элемента;
4 - процедура постановки в очередь;
5 - функция выборки из очереди.
{ простое планирование предписаниями }
procram MiniScheduler;
uses Grt;
const
MAX_EVENT = 100;
type
EvtType = string[80];
var
event: array[1..MAX_EVENT] of EvtType;
spos, rpos, t: integer;
ch:char;
done:boolean;
{ добавить в очередь }
procedure Qstore(q:EvtType);
begin
if spos=MAX_EVENT then
WriteLn('List full')
else
begin
event[spos] := q;
spos := spos+1;
end;
end; { конец процедуры постановки в очередь }
{ выборка объекта из очереди }
function Qretrieve:EvtType;
begin
if rpos=spos then
begin
WriteLn('No appointments scheduled.);
Qretrieve := '';
end else
begin
rpos := rpos+1;
Qretrieve := event[rpos-1];
end;
end; { конец функции выборки элемента из очереди }
{ ввести предписание в планировщик }
procedure Enter;
var
s: string[80];
begin
repeat
Write('Enter appointment',spos+1, ':');
ReadLn(s);
WriteLn;
if Length(s)<>0 then Qstore(s);
until Length(s)=0;
end; { конец процедуры ввода }
{ вывести предписание }
procedure Review;
var
t: integer;
begin
for t:=rpos to spos-1 do WriteLn(t+1,':',event[t]);
end; { конец процедуры вывода }
{ активизировать предписание }
procedure Periorm;
var
s:string[80];
begin
s:=Qretrieve; { получить следующее предписание }
if Length(s)<>0 then WriteLn(s);
end; { конец процедуры активизации предписаний }
begin { начало планировщика }
for t:= 1 to MAX_EVENT do event[t]:=''; { инициализация
событий}
spos:=0; rpos:=0; done:=FALSE;
repeat
Write('Enter,Review, Pertorm,Quit: ');
ch:= ReadKey;
WriteLn;
Case upcase(ch) of
'E':Enter;
'R':Review;
'P':Perform;
'Q':done:=TRUE;
end;
until done=TRUE;
end.
При чтении предыдущего раздела вы возможно подумали об улуч- шении программы планирования предписаниями. Вместо остановки программы по достижению предела массива, который используется под очередь, можно указатель постановки в очередь и указатель выборки из очереди вернуть на начало массива. В этом случае в очередь можно добавлять любое число элементов в то время как элементы бу- дут также выбираться из очереди. Такая очередь называется цикли- ческой, поскольку теперь массив используется не как линейный спи- сок, а как циклический список.
Для создания циклической очереди в программе планирования предписаний требуется изменить подпрограммы постановки в очередь и выборки из очереди следующим образом: procedure Qstore(q: EvtType);begin
{ убедитесь, что имеется свободное место в очереди }
if ((spos+1=rpos) or ((spos=MAX_EVENT) AND (rpos=0))then WriteLn('List full')
else
begin
event[spos] := q;
spos := spos+1;
if spos=MAX_EVENT then spos:=1; { возврат в начало }
end;
end; { конец процедуры постановки в очередь }
function Qretrieve:EvtType;
begin
if rpos=MAX_EVENT then rpos:=1; { возврат в начало }
else rpos:=rpos+1;
if rpos=spos then
begin
WriteLn('Queue empty'); Qretrieve:=';';
end else
Qretrieve:=event[rpos-1];
end; { конец функции выборки из очереди }
В действительности очередь становится заполненной только в том случае, когда указатель свободного места совпадает с указате- лем выборки следующего элемента. В противном случае очередь будет иметь свободное место для нового элемента. Однако, это значит, что в начале программы индекс выборки должен устанавливаться не в нулевое значение, а на значение максимального числа событий. В противном случае первое обращение к процедуре постановки в оче- редь приведет к появлению сообщения о заполнении списка. Следует помнить, что очередь может содержать только на один элемент мень- ше, чем значение максимального числа событий, поскольку указатели выборки и постановки в очередь всегда должны отличаться хотя бы на единицу (в противном случае нельзя будет понять заполнена ли очередь или она пустая).
Далее рассматривается циклический массив, который использу- ется в новой версии программы планирования. Наиболее широко цик- лические очереди применяются в операционных системах при буфери- зации информации, которая считывается или записывается на диско- вые файлы или консоль. Другое широкое применение эти очереди наш- ли в решении задач реального времени, когда, например, пользова- тель может продолжать делать ввод с клавиатуры во время выполне- ния другой задачи. Так работают многие текстовые процессоры, ког- да изменяется формат параграфа или выравнивается строка. Имеется короткий промежуток времени, когда набранная на клавиатуре инфор- мация не выводится на экран до окончания другого процесса. Для достижения такого эффекта в программе должна предусматриваться постоянная проверка ввода с клавиатуры в ходе выполнения другого процесса. При вводе некоторого символа его значение должно быстро ставиться в очередь и процесс должен продолжаться. После заверше- ния процесса набранные символы выбираются из очереди и обрабаты- ваются обычным образом.
Для того, чтобы понять, как это можно сделать с помощью цик- лической очереди, рассмотрим следующую простую программу, состоя- щую из двух процессов. Первый процесс выполняет подсчет до 32 000. Второй процесс устанавливает символы в циклическую очередь по мере того как они вводятся с клавиатуры. При этом вводимые символы не будут выводиться на экран до тех пор, пока не будет введена точка с запятой. Вводимые символы не будут выводиться на экран, поскольку первый процесс будет иметь более высокий приори- тет до тех пор, пока вы не введете точку с запятой или пока счет- чик не достигнет максимального значения. Затем из очереди будут выбраны введенные символы и выведены на экран.
{ программа, иллюстрирующая применение циклической очереди } program KeyBuffer;uses Crt, Dos;
const
MAX_EVENT = 10;
type
EvtType = char;
var
event: array[1..MAX_EVENT] of EvtType;
spos, rpos, t: integer;
ch: char;
{ поместить объект в очередь }
procedure Qstore(q:EvtType);
begin
2 { убедиться, что в очереди имеется свободное место} if ((spos+1=rpos) or ((spos=MAX_EVENT) AND (rpos=0))then WriteLn('List full')
else
begin
event[spos]:=q;
spos:=spos+1;
if spos=MAX_EVENT then spos:=1; { вернуться в начало очереди }
end;
end; { конец процедуры постановки в очередь }
{ выборка объекта из очереди }
function Qretrieve:EvtType;
begin
if rpos=MAX_EVENT then rpos:=1; { вернуться в начало очереди }
else rpos:=rpos+1;
if rpos=spos then
begin
WriteLn('Queue empty');
Qretrieve:=';';
end else
begin
Qretrieve:= event[rpos-1];
end;
end; { конец функции выборки объекта из очереди }
begin { буфер набранных с помощью клавиатуры символов }
spos := 0;
rpos := MAX_EVENT;
{ установить переменную "ch" на начальное значение,
отличное от точки с запятой }
ch:=' ';
t := 1;
repeat if KeyPressed then
begin
ch := ReadKey;
Qstore(ch);
end;
t:=t+1;
write(t); write(' ');
until (t=32000) or (ch=';');
{ вывести содержимое буфера введенных с клавиатуры символов }
repeat
ch:=Qretrieve;
if ch<>';' then Write(ch);
until ch = ';';
end.
Процедура "KeyPressed" делает обращение к программе операци- онной системы, которая возвращает значение "истина", если была нажата какая-либо клавиша, или значение "ложь", если клавиатура не использовалась.
