Главная Промышленная автоматика.

Последний массив - это массив сегментов для хеш-таблицы. Код процедуры ASSIGN приведен в листинге 4.10. Написание процедур для операторов MAKENULL и COMPUTE оставляем для упражнения.

Листинг 4.10. Процедура ASSIGN для открытой хеш-таблицы

procedure ASSIGN ( var А: MAPPING; d: domaintype; г: rangetype ) ; var

bucket: integer; current: tcelltype; begin

buckethid); current: Albucket]; while current <> nil do

if current. domainelement = d then begin curren tt. range -. = r;

{ замена старого значения для d } return

end else

current: currentt.next; { d не найден в списке } current:= Albucket] ;

{использование current для запоминания первой ячейки} new(A[bucket]); A[bucket]t .domainelement:= d; A[bucket]t .range:= r; A[bucket]t .next:= current; end; { ASSIGN }

Подобным образом для реализации отображений можно использовать закрытое хеширование. Ячейки хеш-таблицы будут содержать поля для элементов областей определения и значений, а АТД MAPPING можно определить как массив таких ячеек. Как и в случае открытого хеширования, хеш-функция применяется к элементам области определения, а не к элементам области значений. Мы оставляем читателю в качестве упражнения реализацию соответствуюших операторов для закрытых хеш-таблиц.

4.10. Очереди с приоритетами

Очередь с приоритетами - это АТД, основанный на модели множеств с операторами INSERT и DELETEMIN, а также с оператором MAKENULL для инициализации структуры данных. Перед определением нового оператора DELETEMIN сначала объясним, что такое "очередь с приоритетами". Этот термин подразумевает, что на множестве элементов задана функция приоритета (priority), т.е. для каждого элемента а множества можно вычислить функцию р(а), приоритет элемента а, которая обычно принимает значения из множества действительньпс чисел, или, в более обшем случае, из некоторого линейно упорядоченного множества. Оператор INSERT для очередей с приоритетами понимается в обычном смысле, тогда как DELETEMIN является функцией, которая возврашает элемент с наименьшим приоритетом и в качестве побочного эффекта удаляет его из множества. Таким образом, оправдывая свое название, DELETEMIN является комбинацией операторов DELETE и MIN, которые были описаны выше в этой главе.

Пример 4.9. Название "очередь с приоритетами" происходит от того вида упорядочивания (сортировки), которому подвергаются данные этого АТД. Слово "очередь" предполагает, что люди (или входные элементы) ожидают некоторого обслуживания,

4.10. ОЧЕРЕДИ С ПРИОРИТЕТАМИ 129



а слова "с приоритетом" обозначают, что обслуживание будет производиться не по принципу "первый пришел - первым получил обслуживание", как происходит с АТД QUEUE (Очередь), а на основе приоритетов всех персон, стояших в очереди. Например, в приемном отделении больницы сначала принимают пациентов с потенциально фатальными диагнозами, независимо от того, как долго они или другие пациенты находились в очереди.

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

Один возможный путь удовлетворить короткие процессы и не заблокировать большие состоит в задании процессу Р приоритета, который вычисляется по формуле 100<„cп(*) - *нач(-Р)- Здбсь Параметр «„с равен времени, израсходованному процессом Р ранее, а <„ач - время, прошедшее от начала инициализации процесса, отсчитываемое от некоего "нулевого времени". Отметим, что в обшем случае приоритеты будут большими отрицательными целыми числами, если, конечно, „ач не отсчитывается от "нулевого времени" в будушем. Число 100 в приведенной формуле является "магическим числом" (т.е. не поддается четкому логическому обоснованию, а пришедшему из практики) и должно быть несколько больше числа ожидаемых активных процессов. Читатель может легко увидеть, что если всегда сначала выполняется процесс с наименьшим приоритетным числом и если в очереди немного коротких процессов, то в течение некоторого (достаточно продолжительного) времени процессу, который не закончился за один квант машинного времени, будет выделено не менее 1% машинного времени. Если этот процент надо увеличить или уменьшить, следует заменить константу 100 в формуле вычисления приоритета.

Представим процесс в виде записи, содержашей поле id идентификатора процесса и поле priority со значением приоритета, т.е. тип процесса processtype определим следуюшим образом:

type

processtype = record id: integer; priority: integer

end;

Значение приоритета мы определили как целое число. Функцию определения приоритета (но не его вычисления) можно определить так:

function р ( а: processtype ) : integer; begin

return {a .priority)

end;

Для того чтобы для выбранных процессов зарезервировать определенное количество квантов машинного времени, компьютерная система поддерживает очередь с приоритетом WAITING (Ожидание), состояшую из элементов типа processtype и ис-пользуюшую две процедуры: initial (инициализация) и select (выбирать). Очередь WAITING управляется с помошью операторов INSERT и DELETEMIN. При инициа-



лизации нового процесса вызывается процедура initial, которая указывает записи, соответствующей новому процессу, место в очереди WAITING. Процедура select вызывается тогда, когда система хочет "одарить" квантом машинного времени какой-либо нроцесс. Запись для выбранного процесса удаляется из очереди WAITING, но сохраняется посредством select для повторного ввода в очередь (если процесс не закончился за выделенное время) с новым приоритетом - приоритет увеличивается на 100 при пересчете времени *„сп (когда <„спувеличивается на единицу).

Можно использовать функцию currenttime (которая возвращает текущее машинное время) для вычисления временных интервалов, отводимых системой процессам; обычно эти интервалы измеряются в микросекундах. Будем также использовать процедуру еxecute(P) а,ля вызова процесса с идентификатором Р на иснолнение в течение одного кванта времени. В листинге 4.11 приведены коды процедур initial и select. □

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

procedure initial ( Р: integer ) ;

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

process: processtype; begin

process.id: = P;

process.priority: = - currenttime; insert (process, WAITING) end; { initial }

procedure select;

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

begintime, endtime: integer; process: processtype; begin

process: = Ideletemin ( waiting ) ;

{deletemin возвращает указатель на удаленный элемент} beglntime:= currenttime; execute (process.id) ; endtime:- currenttime;

process, priority: process.prioricy+100* (endtime-begintime) ;

{ пересчет приоритета } INSERT (process,WAITING)

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

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

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

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 [39] 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0036