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

В общем  случае  планирование  (на  любом  уровне) может быть представлена как система массового обслуживания (СМО). Применительно к планированию процессорного времени компоненты этой СМО могут быть интерпретированы следующим  образом: заявкой является процесс,  обслуживающим  прибором - центральный процессор (ЦП), очередь заявок - это очередь готовых процессов. Процессы-заявки поступают  в очередь, при освобождении ЦП один процесс выбирается из очереди и обслуживается на ЦП.  Обслуживание может быть прервано по следующим причинам:

- выполнение процесса завершилось;
- процесс  запросил  выполнение операции,  требующей ожидания       какого-либо другого ресурса;
- выполнение прервано системой.

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

С точки зрения реализации дисциплины планирования подразделяются прежде  всего на дисциплины вытесняющие (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 - передний-задний планы)  -  очередь готовых процессов  расщепляется на две подочереди - очередь переднего плана и очередь заднего плана.