Вытесняющие и невытесняющие алгоритмы

 Вытесняющие и невытесняющие алгоритмы

Существует два основных типа процедур планирования процессов – вытесняющие (preemptive) и невытесняющие (non-preemptive).

Non-preemptive multitasking – невытесняющая многозадачность – это способ планирования процессов, при котором активный процесс выпол- няется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику операционной системы для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.

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

Понятия preemptive и non-preemptive иногда отождествляются с по- нятиями приоритетных и бесприоритетных дисциплин, что совершенно неверно, а также с понятиями абсолютных и относительных приорите- тов, что неверно отчасти. Вытесняющая и невытесняющая многозадач- ность – это более широкие понятия, чем типы приоритетности. Приори- теты задач могут как использоваться, так и не использоваться и при вы- тесняющих, и при невытесняющих способах планирования. Так в случае использования приоритетов дисциплина относительных приоритетов может быть отнесена к классу систем с невытесняющей многозадачно- стью, а дисциплина абсолютных приоритетов – к классу систем с вытес- няющей многозадачностью. А бесприоритетная дисциплина планирова- ния, основанная на выделении равных квантов времени для всех задач, относится к вытесняющим алгоритмам.

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

реди готовых задач следующую и запускает ее на выполнение, загружая ее контекст.

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

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

Поэтому разработчики приложений для non-preemptive операцион- ной среды, возлагая на себя функции планировщика, должны создавать приложения так, чтобы они выполняли свои задачи небольшими частя- ми. Например, программа форматирования может отформатировать од- ну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматирова- ния, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно за- трудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить «дру- жественное» отношение своей программы к другим выполняемым одно- временно с ней программам, достаточно часто отдавая им управление. Крайним проявлением «недружественности» приложения является его зависание, которое приводит к общему краху системы. В системах с вы- тесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм снимет зависшую задачу с выполнения.

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

программ в «неудобные» для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит эти данные. Суще- ственным преимуществом non-preemptive систем является более высо- кая скорость переключения с задачи на задачу.

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

Однако почти во всех современных операционных системах, ориен- тированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, OS/2, VAX/VMS), реализована вытесняющая многозадач- ность. В последнее время дошла очередь и до ОС класса настольных систем, например, OS/2 Warp и Windows 95. Возможно в связи с этим вытесняющую многозадачность часто называют истинной многозадач- ностью.