Многоур-ые очереди с обратной свзью

Многоуровневые очереди.

Multilevel Queue.

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

К этим очередям приписыв-ся фиксир-ые приоритеты. Внутри этих очередей для планир-ия м. примен-ся самые разн. алг-мы. Н-р, для больш. счётных проц-ов, не требующих взаимод-ия с польз-ем(фоновые проц-сы) м. использ-ся алг-м FCFS. Для интерактивных проц-ов – алг-м RR. Подобный подход, получивший назв-ие многоуровневых очередей, повышает гибкость планир-ия: для проц-ов с разл. Хар-ми примен-ся наиболее подходящий алг-м.

Multilevel Feedback Queue.

Дальнейшем развитием алг-ма многоур-ых очередей явл-ся добавл-ие к нему механизма обратной связи. Здесь проц-с не постоянно приписан к опред. Очереди, а м. мигрировать из одной очереди в др. в зависимости от своего повед-ия. Пусть проц-сы в сост. готовность организованы в 4 очереди. Планир-ие проц-са между очередями осуществл-ся на основе вытесняющего приоритетного мезанизма. Чем выше располаг-ся очередь, тем выше её приоритет. Проц-сы в очереди 1 не м. исполн-ся, если в очереди 0 есть хотя бы один проц-с. Проц-сы в очереди 2 не будут выбраны для исполн-ия, пока есть хоть один проц-с в очередях 0и 1. Если при работе проц-са появл-ся др. проц-с к-л. более приоритетноц очереди, исполняющийся проц-с вытесн-ся новым. Родившийся проц-с поступает в очередь 0. При выборе на исполн-ие он получает в своё распоряжение квант вр. размером 8 единиц.

Если продолжительность его времени непрерывного выполнения меньше этого кванта времени, процесс остаётся в очереди 0, в противном случае он переходит в очередь 1.

Для процессов из очереди 1 квант времени имеет величину 16, если процесс не укладывается в это время, то он переходит в очередь 2, если укладывается, то остаётся в очереди 1 В очереди 2 величина кванта времени = 32 ед. Если для неправильной работы проц-са и этого мало процесс поступает в очередь 3, и для которых квантование времени не применяется. Чем больше значение продолжительности времени непрерывной работы проц-са, тем в менее приоритетную очередь он попадет, но тем на большее проц-ое время он может рассчитывать. Т.о. ч/з некоторое время все проц-сы, требующие мало вр. и работы процессора окажутся разными в высоко приоритетных очередях, а все процессы требующие большого счёта – низкого приоритета.

Миграция процессов в обратном направлении может осуществляться по разл. принципам. Например, после завершения ожидания ввода с клавиатуры процессы из очередей 1-2 и 3 могут перемещаться в очередь 0. После завершения дисковых операций, процессы из оч 2 и3 могут перемещаться в очередь 1, а после завершения ожидания всех других событий из очереди 3 в очередь 2.

Перемещение процессов из очереди с низким приоритетом в оч с высоким приор.позволяет более полно учитывать изменение поведения процессов с течением времени.

Многоуровневые очереди с обратной связью представляют собой наиболее общий подход планирования процесса. Они наиболее трудны в реализации, но обладают наибольшей гибкостью. Существует много других разновидностей такого способа планирования Для полного описания их конкретной реализации необходимо указать:

1. Количество очередей для процесса находящихся в состоянии готовности;

2. Алгоритм планирования действий между очередями;

3. Алгоритм планирования, действующие внутри очередей;

4. Правило помещения родив-ся процесса в одну из очередей

5. Правило перевода проц. из одной оч в др.

Заключение.

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

Простейшим алгоритмом планирования является не вытесняющий алгоритм FCFS, который, однако, может существенно задержать короткие процессы, перешедшие в состояние готовности. В системах разделения времени широко применяется вытесняющая версия этого алгоритма (RR).

Среди всех, не вытесняющих алгоритма оптимален с т. зр. среднего времени ожидания процессов является алгоритм. SJF. Существует и вытесняющий вариант этого алгоритма. В интерактивных системах часто используется алгоритм гарантированного планирования, обеспечивающий пользователю равные части проц. времени.

Алгоритм SJF и алгоритм гарантированного планирования является частными случаями планирования с использованием приоритетов. В более общих методах приоритетного планирования применяется многоуровневые очереди процессов готовых к исполнению и многоуровневые очереди с обратной связью. Будучи наиболее сложными, в реализации эти способы планирования обеспечивают гибкое поведение вычислительных систем и их адаптивность к решению задач различных классов.

Дата добавления: 2014-01-13