16.Принципы планирования процессов и потоков. Классификация алгоритмов планирования.

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

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

1) определение момента времени для смены текущего активного потока;

2) выбор для выполнения потока из очереди готовых потоков.

В большинстве операционных систем универсального назначения планирование осуществляется динамически (on-line), то есть решения принимаются во время работы системы на основе анализа текущей ситуации. ОС работает в условиях неопределенности – потоки и процессы появляются в случайные моменты времени и также непредсказуемо завершаются. Динамические планировщики могут гибко приспосабливаться к изменяющейся ситуации и не используют никаких предположений о мультипрограммной смеси. Для того чтобы оперативно найти в условиях такой неопределенности оптимальный в некотором смысле порядок выполнения задач, ОС должна затрачиваться значительные ресурсы.

Другой тип планирования – статический (off-line) – может быть использован в специализированных системах, в которых весь набор одновременно выполняемых задач определен заранее, например, в системах реального времени. Планировщик называется статическим (или предварительным планировщиком), если он принимает решения о планировании не во время работы системы, а заранее.

Классификация алгоритмов планирования (вытесняющие и невытесняющие, бесприоритетные и приоритетные алгоритмы)

17.Вытесняющие и невытесняющие алгоритмы планирования ос. Приоритетные и бесприоритетные алгоритмы планирования

С самых общих позиций все множество алгоритмов планирования можно разделить на два класса: вытесняющие и невытесняющие алгоритмы планирования

Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению поток.

Вытесняющие (preemptive) алгоритмы – это такие способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается ОС, а не активной задачей.

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

Далее среди множества алгоритмов планирования выделяются два больших класса – бесприоритетные и приоритетные алгоритмы (рис.3.1) /7,8,12/.

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

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