Порядок выполнения работы. 1. Ознакомление с теоретической частью индивидуальной работы.

1. Ознакомление с теоретической частью индивидуальной работы.

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

Теоретическая часть работы описана в ЭУМКД по курсу (Стр. 37-41).

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

Для реализации очередей можно использовать функцию currenttime, которая возвращает текущее машинное время с целью вычисления временных интервалов, отводимых системой процессам. Обычно эти интервалы измеряются в микросекундах. Очереди с приоритетом часто создаются на основе связанных списков. Если список отсортирован, то нахождение минимального элемента – это выбор первого элемента списка. Однако при этом вставка нового элемента в отсортированный список требует просмотра в среднем половины элементов списка. Если оставить список неупорядоченным, упрощается вставка нового элемента и затрудняется поиск минимального элемента.

Дата добавления: 2015-07-16