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

Все множество алгоритмы планирования можно разде­лить на два принципиально различных класса: вытесняющие и невытесняющие.

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

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

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

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

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

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

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

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

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

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

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

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

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

Планировщик NetWare использует несколько очередей готовых потоков (рисунок 10.3). Только что созданный поток попадает в конец очереди RunList, которая содержит готовые к выполнению потоки. После отказа от процессора поток попадает в ту или иную очередь в зависимости от того, какой из системных вызовов был ис­пользован при передаче управления. Поток поступает в конец очереди RunList при вызове ThreadSwitch, в конец очереди DelayedWorkToDoList при вызовах ThreadSwitchWithDelay или Delay или же в конец очереди LowPriorityRunList при вызове ThreadSwitchLowPriority.

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

Потоки, находящиеся в очереди DelayedWorkToDoList, после завершения условия ожидания перемещаются в конец очереди RunList.

Потоки, находящиеся в очереди LowPriorityRunList, запускаются на выполнение только в том случае, если очередь RunList пуста. Обычно в эту очередь назнача­ются потоки, выполняющие несрочную фоновую работу.

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

Рисунок 10.3 – Схема планирования потоков в NetWare

Описанный невытесняющий механизм организации многопоточной работы в ОС NetWare 3.x и NetWare 4.x потенциально очень производителен, так как от­личается небольшими накладными расходами ОС на диспетчеризацию потоков за счет простых алгоритмов планирования и иерархии контекстов. Но для дости­жения высокой производительности к разработчикам приложений для ОС Net­Ware предъявляются высокие требования, так как распределение процессорного времени между различными приложениями зависит, в конечном счете, от искус­ства программиста.

Дата добавления: 2014-11-25