Классические ДРР

Вначале рассмотрим простейшие одноочередные ДРР [10], когда организуется единственная очередь запросов на ресурс от процессов (рис.11).

1. Дисциплина обслуживания в порядке поступления или First In – First Out (FIFO) (рис.2.7,а).

2. Дисциплина обслуживания в порядке, обратном порядку поступления, Last In – First Out (LIFO), по сути представляющая стек (рис.2.7,б).

В принципе возможна и очередь с двумя концами, имеющая название «дек» – от слов d ouble e nded que ue (deque).

3. Круговой циклический алгоритм (КЦА) (рис.2.7, в) [10] или карусельная (Round Robin) дисциплина [1]. Здесь: НЗ – новый запрос, ОЗ – обслуженный запрос, t_k – квант обслуживания. Алгоритм основан на дисциплине FIFO и используется при реализации режима РДВ.

Рис.2.7. Дисциплины обслуживания FIFO, LIFO и КЦА

В КЦА возможны две ситуации, когда могут быть:

· короткий НЗ, имеющий длительность облуживания t₁≤ t_k. Он обслуживается очень быстро;

· длинный НЗ, его длительность облуживания t₂ > t_k. Если измерять условную длину (l) запроса числом использованных t_k и обозначить n_ср – среднюю длину очереди, а t^ср_ожид – среднее время ожидания, то

откуда

Время обслуживания зависит от t_k, длины запроса (l), длины очереди (n_ср).

4. Дисциплина обслуживания вида «следующим будет выполняться самый короткий запрос» [1].

5. Дисциплина обслуживания вида «следующим будет выполняться запрос, которому осталось меньше всех выполняться на процессоре» [1].

Далее рассмотрим более сложные многоочередные ДРР [10].

1. Неприоритетная многоочередная ДРР (рис.2.8) основана на КЦА:

· организуется N очередей;

· все новые запросы поступают в конец очереди 1;

· первый запрос очереди i (1≤i≤N) поступает на обслуживание, если очереди 1, 2,…, (i-1) – пусты;

· на обслуживание выделяется квант времени t_k;

· не до конца обслуженный запрос возвращается в конец очереди (i+1), что похоже на неявное снижение приоритета длинного запроса.

Рис.2.8. Схема неприоритетной многоочередной ДРР

Ее особенности: наиболее быстро обслуживаются короткие запросы; возникают непроизводительные затраты времени на перемещение запросов из одной очереди в другую; длинные запросы обслуживаются еще медленнее, чем в КЦА.

2. Приоритетная многоочередная ДРР (рис.2.9) также основана КЦА и является модификацией предыдущей дисциплины. Она отличается от предыдущей дисциплины тем, что каждый новый запрос имеет приоритет p=1÷N и попадает в очередь с номером j=N-p+1.

Рис.2.9. Схема приоритетной многоочередной ДРР

По отношению к новым запросам с приоритетами возможны две следующие стратегии поведения системы.

3. Обслуживание с абсолютным приоритетом. Если во время обслуживания запроса из очереди i поступает запрос в очередь j < i, то обслуживание i-го уровня прерывается, система начинает обслуживать более приоритетный запрос в течение t_k. После окончания его обслуживания продолжается обслуживание прерванного запроса i-го уровня. Особенности: дискриминация низкоприоритетных запросов, время ожидания высокоприоритетных уменьшается, усложняется логика работы системы и ее реализация, появляется проблема прерывания обслуживания, и понадобятся дополнительные средства и ресурсы для ее реализации. Дисциплина подходит для систем управления объектами, в которых важна быстрая реакция на событие. Но при таком подходе возникают и сложные организационные проблемы:

· найти удачное правило продолжения обслуживания прерванного запроса:

Ø когда ему вновь выделять ресурс (если сразу – новые затраты);

Ø учитывать, что ресурс уже использовался до прерывания, или нет;

· выбрать, в какую очередь помещать прерванный запрос (i+1, i, i-1);

· что делать, если во время прерывания обслуживания появится еще запрос уровня q < I (проблема маскирования)?

4. Обслуживание с относительным приоритетом. Новый запрос не вызывает прерывания обслуживания запроса, даже если обслуживается менее приоритетный запрос. Только после окончания обслуживания текущего (менее приоритетного) запроса начнется обслуживание нового (более приоритетного). Особенности: минимизируются затраты на переключения процессора, но допускается его монополизация. Дисциплина не подходит для систем РДВ и РВ.

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

· взаимосвязи процессов;

· стратегий распределения других ресурсов;

· тупиковых ситуаций, когда возникает циклический конфликт занятости ресурсов [1, 2]. Пример подобной ситуации приведен на рис.2.10, где Процессу 1 требуются Ресурсы 1 и 2, но выделяется только Ресурс 1, так как Ресурс 2 ранее уже был выделен Процессу 2, которому требовался еще Ресурс 1. Но Ресурс 1 также занят и не может быть выделен Процессу 2;

· прав процесса использовать разделяемый ресурс;

· специфики самого ресурса.

Рис.2.10. Пример тупиковой ситуации

Кроме рассмотренных ДРР, существуют и другие, ориентированные на специфику самого распределяемого ресурса. Например, при распределении ОП используется:

· разная техника распределения ОП:

Ø статическое распределение – до порождения процесса (заранее создаются разделы ОП определенного размера, и каждая программа привязывается к своему разделу; уменьшается гибкость, так как нет гарантии того, что программа поместится в данный раздел);

Ø динамическое распределение – в момент порождения процесса (требуется ожидание освобождения ОП, поэтому возможны задержки, простои);

Ø комбинированное распределение – частично статически, частично динамически;

· разная структура ресурса (как простой ресурс – распределение непрерывными областями, или как составной – несмежными частями).

При распределении непрерывными областями может возникать явление фрагментации [1-4, 10]. Его суть состоит в том, что после многократного выделения и освобождения областей ОП остаются незаполненные области (НО) все более малого размера – такие, что размера каждой из них уже будет недостаточно для загрузки программы, а суммарный размер свободной ОП будет достаточно большим. Пример фрагментации приведен на рис.2.11,а–д, где показано распределение ОП для задач разного объема (в условных единицах в скобках) по состоянию в разные моменты времени t₁, t₂, …, t₅. Из рис.2.11 видно, что в момент времени t₅ в ОП не может быть загружена задача объемом 3 единицы в то время, когда суммарный объем НО составляет 20 единиц из общего числа 27 единиц. Ограничение объема загружаемых задач ужесточается с течением времени, что отражено в табл.2.2.

Поэтому при таком распределении ОП необходимы программные средства объединения всех малых НО ОП в единственную непрерывную область на основе различных известных алгоритмов устранения «дыр» в ОП.

а) t₁ б) t₂ в) t₃ г) t₄ д) t₅

Задача 1 (12)     Задача 2 (10) Задача 3 (1)   НО-1 (4)

Задача 4 (8)   НО-2 (4)   Задача 5 (8)   НО-3 (2) Задача 3 (1)   НО-1 (4)

Задача 7 (6) НО-5 (2) Задача 6 (2) НО-4 (2)     Задача 8 (6) НО-6 (2) НО-3 (2) Задача 3 (1)   НО-1 (4)

Задача 7 Задача 9 (2) Задача 6 Задача 10 (2)   Задача 8 (3) Задача 11 (2) НО-7 (1) НО-6 (2) НО-3 (2) НО-8 (1) Задача 12 (2) НО-1 (2)

Задача 13 (4) НО-9 (2) НО-10 (2) НО-11 (2) НО-12 (2)   Задача 8 (3) НО-13 (2) НО-7 (1) НО-6 (2) НО-3 (2) НО-8 (1) НО-14 (2) НО-1 (2)

Рис.2.11. Распределение ОП для задач разного объема по состоянию моменты времени t₁, t₂, …, t₅.

Таблица 2.2

Момент времени:	t0=0	t1	t2	t3	t4	t5
Предел объема загружаемой задачи (усл.ед.) в момент ti
Предел объема загружаемой задачи (усл.ед.) после ti и завершения других задач

Кроме того, многоочередная ДРР может строиться на основе еще более сложных в организации динамических приоритетных циклических (карусельных) схем, сочетающих элементы режимов РВ и РДВ. На рис.2.12 показана двухступенчатая схема подобного варианта, где в виде большого кольца изображена главная карусель (циклическая очередь задач к процессору). С ней связано еще несколько локальных каруселей (малых колец). Каждая задача, условно изображенная в виде квадрата, попадает в основную карусель из своей локальной, куда и возвращается при появлении в данной локальной карусели более приоритетной задачи.

Смена «представителя» в главной карусели организуется за счет динамического временного повышения или понижения приоритета задач в локальной карусели. В главной карусели предоставление процессора может осуществляться по аналогичному или иному правилу.

Рис.2.12. Двухступенчатая карусельная схема

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

Рис.2.13. Многоступенчатая карусельная схема