yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Листинг 4.11. Выделение процессам машинного времени

Алгоритмы и структуры данных

Листинг 4.11. Выделение процессам машинного времени

procedure initial ( Р: integer );

(initial указывает процессу с идентификатором Р место в очереди}

var

process: processtype;

begin

process.id: = P;

process.priority:= - currenttime;

INSERT(process, WAITING)

end; { initial }

 

procedure select;

{select выделяет квант времени процессу с наивысшим приоритетом}

var

begintime, endtime: integer;

process: processtype;

begin

process := ↑deletemin (waiting)

{DELETEMIN возвращает указатель на удаленный элемент}

begintime:= currenttime

execute (process, id) ;

endtime:= currenttiffle;

process.priority—process.priori ty+100*(endtime-begintime);

{ пересчет приоритета }

INSERT(process, WAITING)

{ занесение процесса в очередь с новым приоритетом }

end; { select }

4.11. Реализация очередей с приоритетами

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

При использовании связанных списков можно выбрать вид упорядочивания элементов списка или оставить его несортированным. Если список отсортирован, то нахождение минимального элемента просто — это первый элемент списка. Но вместе с тем вставка нового элемента в отсортированный список требует просмотра в среднем половины элементов списка.  Если оставить список неупорядоченным, упрощается вставка нового элемента и затрудняется поиск минимального элемента.

Пример 4.10. В листинге 4.12 показана реализация функции DELETEMIN для несортированного списка элементов, имеющих тип processtype, описанный в примере 4.9. В этом листинге также приведены объявления для типа ячеек списка и для АТД PRIORITYQUEUE (Очередь с приоритетами). Реализация операторов INSERT и MAKENULL (как для отсортированных, так и для несортированных списков) не вызывает затруднений, и мы оставляем ее в качестве упражнения для читателей.

Листинг 4.12. Реализация очереди с приоритетами посредством связанного списка

type

celltype = record

element: processtype;

next: ↑celltype

end;

PRIORITYQUEUE = ↑celltype;

{ ячейка указывает на заголовок списка }

function DELETEMIN ( var A: PRIORITYQUEUE ): ↑celltype;

var

current: ↑celltype;

{ указывает на ячейку, которая будет

проверена следующей }

lowpriority: integer;

{ содержит ранее найденный наименьший приоритет }

prewinner: ↑celltype;

{ указывает на ячейку, содержащую элемент

с наименьшим приоритетом }

begin

if A↑.next = nil then

error('Нельзя найти минимум в пустом списке')

else begin

lowpriority:= p (A↑.next↑.element);

{ функция р возвращает приоритет первого элемента.

Отметим, что А указывает на ячейку заголовка,

которая не содержит элемента }

prewinner:= А;

current:= A↑.next;

while current↑.next <> nil do begin

{ сравнение текущего наименьшего приоритета с

приоритетом следующего элемента }

if p(current↑. next↑. element) <lowpriority then begin

prewinner:= current;

lowpriority:= p(current↑.next↑. element)

end;

current:= current↑.next

end;

DELETEMIN:= prewinner↑. next ;

{ возвращает указатель на найденный элемент }

prewinner↑. next: = prewinner↑. Next↑. next

( удаляет найденный элемент из списка }

end

end; { DELETEMIN }

 

 

36