· Основные понятия и определения: операционная система (ОС), программное обеспечение (ПО), системное программное обеспечение.
· Состояние потока
· Вытесняющие и невытесняющие алгоритмы планирования.
10.2.1 Состояние потока— до 15 мин.
ОС планирует потоки, принимая во внимание их состояние. В мультипрограммной системе поток может находиться в одном из трех основных состояний:
- выполнение – активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;
- ожидание – пассивное состояние потока, в котором, поток заблокирован по своим внутренним причинам (ждет завершения операции ввода-вывода, получения сообщения от другого потока и т. д.);
- готовность – также пассивное состояние потока, но в этом случае он заблокирован в связи с внешним по отношению к нему обстоятельством (имеет все требуемые ресурсы, готов выполняться, однако процессор занят выполнением другого потока).
В течение своей жизни каждый поток переходит из одного состояния в другое в соответствии с алгоритмом планирования потоков, принятым в данной операционной системе.
Рассмотрим типичный граф состояния потока (рисунок 10.1). Только что созданный поток находится в состоянии готовности, он готов к выполнению и стоит в очереди к процессору. Когда в результате планирования подсистема управления потоками принимает решение об активизации данного потока, он переходит в состояние выполнения и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ожидания какого-нибудь события, либо будет принудительно «вытеснен» из процессора, например вследствие исчерпания отведенного ему кванта процессорного времени. В последнем случае поток возвращается в состояние готовности. В это же состояние поток переходит из состояния ожидания, после того как ожидаемое событие произойдет.
Рисунок 10.1 – Граф состояний потока в многозадачной среде
В состоянии выполнения в однопроцессорной системе может находиться не более одного потока, а в каждом из состояний ожидания и готовности – несколько потоков. Эти потоки образуют очереди соответственно ожидающих и готовых потоков. Очереди потоков организуются путем объединения в списки описателей отдельных потоков. Таким образом, каждый описатель потока, кроме всего прочего, содержит, по крайней мере, один указатель на другой описатель, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать потоки, переводить потоки из одного состояния в другое. Если предположить, что на рисунке 10.2 показана очередь готовых потоков, то запланированный порядок выполнения выглядит так: А, В, Е, D, С.
Рисунок 10.2 – Очередь потоков
Одним из примеров удачной организации многопоточной архитектуры можно привести ОС Solaris [2].
В этой системе реализован необычный многоуровневый подход к управлению потоками, способствующий значительной гибкости использования ресурсов.
Здесь используются четыре отдельные концепции, связанные с потоками:
- Процесс. Это обычный процесс Unix, который включает в себя пользовательское адресное пространство, стек и управляющий блок процесса.
- Поток на пользовательском уровне. Эти потоки реализуются с помощью библиотеки потоков в адресном пространстве процесса; они невидимы для операционной системы. Потоки на пользовательском уровне играют роль интерфейса для реализации параллелизма вычислений.
- Облегченные процессы. Их можно рассматривать, как отображение между потоками на пользовательском уровне и потоками ядра. Каждый из облегченных процессов поддерживает один или несколько потоков на пользовательском уровне и отображает их в один поток ядра. Планирование облегченных процессов производится ядром независимо.
Потоки ядра. Эти потоки являются фундаментальными элементами, планирование и выполнение которых может осуществляться на одном из системных процессоров.
10.2.2 Вытесняющие и невытесняющие алгоритмы планирования— до 15 мин.
Все множество алгоритмы планирования можно разделить на два принципиально различных класса: вытесняющие и невытесняющие.
- Невытесняющие (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 потенциально очень производителен, так как отличается небольшими накладными расходами ОС на диспетчеризацию потоков за счет простых алгоритмов планирования и иерархии контекстов. Но для достижения высокой производительности к разработчикам приложений для ОС NetWare предъявляются высокие требования, так как распределение процессорного времени между различными приложениями зависит, в конечном счете, от искусства программиста.
