|
Страница 22 из 60
Циклическая очередь
spos 2
1 Queue ---T--T--T--T--T--T--T--T--T--T--¬
at Start-up ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+---
rpos 3
spos 2
4 Qstore('A') ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+---
rpos 3
spos 2
4 Qstore('B') ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦B ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+---
rpos 3
spos 2
5 Qreirieve ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦B ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+---
rpos 3
spos 2
5 Qreirieve ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦B ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+---
rpos 3
spos 2
4 Qstore('C') ---T--T--T--T--T--T--T--T--T--T--¬
¦A ¦B ¦C ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
L--+--+--+--+--+--+--+--+--+--+---
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" делает обращение к программе операци-
онной системы, которая возвращает значение "истина", если была
нажата какая-либо клавиша, или значение "ложь", если клавиатура
не использовалась.
|