Shortest Job First(SLF)

Round Robin(RR).

Алгоритмы планир-ия.

First Come First Served(первый пришёл первого обслужил).

Пусть проц-ы, находящ-ся в сост. готовность выстроены в очередь. Когда проц-с переходит в сост. готовность, ссылка на его РСВ, помещ-ся в конец этой очереди. Выбор нового проц-са для исполн-ия осуществл-ся из начала очереди с удалением оттуда ссылки на его РСВ. Очередь подобного типа имеет в программ-ии спец. назв-ие – First In First Out(FIFO). Такой алг-м выбора проц-са осущ-т невытесн-ее планир-ие. Проц-с, получивший в своё распоряж-ие ЦП занимает его до истечении текущего времени непрерывного использ-ия(CPU burst). После этого для выполне-ия выбирается нов. проц-с из начала очереди. Преимуществом алг-ма FCFS явл-ся лёгкость его реализ-ии. Недостатком явл-ся то, что среднее время ожидания и ср. полное вр. Выполнения для этого алг-ма существенно зависят от пор-ка расположения проц-са в очереди. Если есть проц-с с длит. временем непрер-го выполн-ия, то короткие проц-сы будут долго ждать начала выполн-ия, поэтому этот алг-м практически не применим для систем разделения времени, т.к. сред. время отклика в интерактивных проц-х получается слишком большим.

Модификацией алг-ма FCFS явл-ся алг-м RR. По стуи это тот же самый алг-м, только реализ-ый в режиме вытесняющего планир-ия. Всё множ-во готовых проц-ов организовано циклически – ЦП сидят на карусели. Карусель вращ-ся так, что кажд. проц-с находящийся около ЦП – небольшой фиксированный квант времени, обычно 10-100мсек. Пока проц-с нах-ся рядом с ЦП, он получет ЦП в своё распоряж-ие и м. исполн-ся.

Реализ-ся этот алг-м так же, как и предыдущий, организацией проц-ов, находящихся в сост. готовность в очередь FIFO. Планировщик выбирает для очередного исполн-ия проц-с, располож-ый в начале очереди и устанавливает таймер для генерации прерывания по истечении определ-го кванта врем-и. При больших вел-ах кванта времени, когда кажд. проц-с успевает завершить свой интервал вр. непрерывного выполн-ия до возникновения прерывания по вр-и, алг-м RR вырожд-ся в алг-м FCFS. При очень мал-х величинах создаётся иллюзия того, кажд. из n проц-ов работает на собственном виртуальном ЦП с производительностью 1/N. В реальных условиях при слишком малых величинах времени и, соответ-но, слишком частом переключении контекста, накладные расходы на переключения редко снижают производительность сист-ы.

В алг-ме FSFC и RR существенным явл-ся порядок расположения ЦП в очередб проц-ов, готовых к исполн-ию. Если короткие задачи, расположенные в очереди ближе к её началу, то общая производит-ть этих алг-ов значит-но возрастает. При известных длительностях выполн-ия проц-са, находящ-ся в сост. готовность, м. выбрать для исполн-ия не проц-с из начала очереди, а проц-с с мин. длительностью выполн-ия. Если таких проц-ов 2 или больше, то для выбора одного из них м. использ-ть алг-м FSFC, квантование времени при этом не примен-ся. Описанный алг-м получил назв-ие “кратчайший выполн-ся первым”. SJF – это алг-м краткосрочного планир-ия. Оно м.б.вытесняющим и невытесняющим. При невытесняющем SJF планир-ии ЦП предоставл-ся избранному проц-су на все необходимое ему вр., независимо от событий, происходящих в выч. сист. При вытесняющих SFJ планир-ях учитыв-ся появление нов. проц-ов во вр. работы выбран-го проц-са. Если вр. непр-го выполн-ия нов. проц-са меньше, чем у исполняющегося, то исполн-ся проц-с вытесняющийся новым. Осн. cложность при реализ-ии алг-ма SJF: невозможность точного знания вр., очередного промежутка вр. непрерывной работы для исполняющегося проц-са. В пакетных сист. кол-во проц-го вр., необходимое задание указ-т польз-ль при формировании заданий. М. брать эту вел-ну для осуществления долгосрочного SJF-планир-ия. При краткоср-ом планир-ии м. делать только прогноз длительности след. промежутка вр. непр-ой работы, исходя из предысторий работы проц-ов. Для подсчёта нов. оценки нужно взять старую оценку, сложить с измеренным временем текущего промежутка вр. непр-ой работы и получен. сумму: на 2. Полученная оценка примен-ся как продолж-ть очередных промежутков вр. непр-го использ-ия ЦП для краткосрочного SJF-планир-ия.

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