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

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

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

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

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

- ThreadSwitch — поток, вызвавший эту функцию, считает себя готовым к немед­ленному выполнению, но отдает управление для того, чтобы могли выпол­няться и другие потоки;

- ThreadSwitchWithDelay — функция аналогична предыдущей, но поток считает, что будет готов к выполнению только через определенное количество пере­ключений с потока на поток;

- Del ay — функция аналогична предыдущей, но задержка дается в миллисекундах;

- ThreadSwItchLowPriority — функция отдачи управления, отличается от Thread-Switch тем, что поток просит поместить его в очередь готовых к выполнению, но низкоприоритетных потоков.