Логический элемент

3.37. Управление процессорным временем. Вытесняющая и невитисняющая дисциплина планирования процессорного времени

3.37. КЕРУВАННЯ ПРОЦЕСОРНИМ ЧАСОМ. ВИТІСНЯЮЧІ ТА НЕВИТІСНЯЮЧІ ДИСЦИПЛІНИ ПЛАНУВАННЯ ПРОЦЕСОРНОГО ЧАСУ.
В общем случае планирование (на любом уровне) может быть представлена как система массового обслуживания (СМО). Применительно к планированию процессорного времени компоненты этой СМО могут быть интерпретированы следующим образом: заявкой является процесс, обслуживающим прибором - центральный процессор (ЦП), очередь заявок - это очередь готовых процессов. Процессы-заявки поступают в очередь, при освобождении ЦП один процесс выбирается из очереди и обслуживается на ЦП. Обслуживание может быть прервано по следующим причинам:
- выполнение процесса завершилось;
- процесс запросил выполнение операции, требующей ожидания какого-либо другого ресурса;
- выполнение прервано системой.
Первые два случая с точки зрения СМО одинаковы: в любом случае процесс выходит из данной СМО. Если процесс не завершился, то после получения запрошенного ресурса процесс вновь поступит во входную очередь. В случае прерывания процесса по инициативе системы прерванный (вытесненный) процесс поступает во входную очередь сразу же. Порядок обслуживания входной очереди, очередность выбора из нее заявок на обслуживания и составляет дисциплину или стратегию планирования.
С точки зрения реализации дисциплины планирования подразделяются прежде всего на дисциплины вытесняющие (preemptive) и невытесняющие (non-preemptive) или кооперативные (cooperative). Для первых возможно прерывание активного процесса и лишение его ресурса ЦП по инициативе планировщика, для вторых - нет. Дисциплины с вытеснением выполняют более частые переключения процессов, следовательно, имеют большие накладные расходы. Но в большинстве случаев только дисциплины с вытеснением могут обеспечить требуемые показатели справедливости обслуживания. Классификация дисциплин также определяется способом определения приоритетов процессов. Различают приоритеты:
- внешние - назначаемые администратором системы или пользователем в соответствии с классом пользователя и/или произведенной пользователем оплатой;
- статические - вычисляемые планировщиком при поступлении процесса в систему и не изменяемые впоследствии;
- динамические - перевычисляемые планировщиком периодически или/и при событиях, влияющих на планирование процессов;
- комплексные - динамически вычисляемые приоритеты, учитывающие внешний приоритет процесса, его статические характеристики, а также ход выполнения процесса, текущее состояние очереди готовых процессов и, возможно, состояние других системных ресурсов.
FCFS (first come - first serve - первым пришел - первым обслуживается) - простейшая дисциплина, работа которой понятна из ее названия. Это дисциплина без вытеснения, то есть, процесс, выбранный для выполнения на ЦП не прерывается, пока не завершится (или не перейдет в состояние ожидания по собственной инициативе).
RR (round robin - карусель) - простейшая дисциплина с вытеснением. Процесс получает в свое распоряжение ЦП на некоторый квант времени Q (в простейшем случае - размер кванта фиксирован). Если за время Q процесс не завершился, он вытесняется с ЦП и направляется в конец очереди готовых процессов, где ждет выделения ему следующего кванта, и т.д.
SJN (shortest job next - самая короткая работа - следующая) - невытесняющая дисциплина, в которой наивысший приоритет имеет самый короткий процесс.
PSJN (preemptive SJN - SJN с вытеснением) - текущий активный процесс прерывается, если его оставшееся время выполнения больше, чем у новоприбывшего процесса.
SRR (selfish RR - эгоистичный RR) - метод с вытеснением, дающий дополнительные преимущества выполняемым процессам, что позволяет повысить пропускную способность.
FB (foregroun-background - передний-задний планы) - очередь готовых процессов расщепляется на две подочереди - очередь переднего плана и очередь заднего плана.