Состояния потока
ОС выполняет планирование потоков, принимая во внимание их состояние. В мультипрограммной системе поток может находиться в одном из трех основных состояний:
выполнение — активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;
ожидание — пассивное состояние потока, находясь в котором, поток заблокирован по своим внутренним причинам (ждет осуществления некоторого события, например завершения операции ввода-вывода, получения сообщения от другого потока или освобождения какого-либо необходимого ему ресурса);
готовность — также пассивное состояние потока, но в этом случае поток заблокирован в связи с внешним по отношению к нему обстоятельством (имеет все требуемые для него ресурсы, готов выполняться, однако процессор занят выполнением другого потока).
ПРИМЕЧАНИЕ
Состояния выполнения и ожидания могут быть отнесены и к задачам, выполняющимся в однопрограммном режиме, а вот состояние готовности характерно только для режима мультипрограммирования.
В течение своей жизни каждый поток переходит из одного состояния в другое в соответствии с алгоритмом планирования потоков, принятым в данной операционной системе.
Рассмотрим типичный граф состояния потока (рис. 4.3). Только что созданный поток находится в состоянии готовности, он готов к выполнению и. стоит в очереди к процессору. Когда в результате планирования подсистема управления потоками принимает решение об активизации данного потока, он переходит в состояние выполнения и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ожидания какого-нибудь события, либо будет принудительно «вытеснен» из процессора, например вследствие исчерпания отведенного данному потоку кванта процессорного времени. В последнем случае поток возвращается в состояние готовности. В это же состояние поток переходит из состояния ожидания, после того как ожидаемое событие произойдет.
Рис. 4.3. Граф состояний потока в многозадачной среде
В состоянии выполнения в однопроцессорной системе может находиться не более одного потока, а в каждом из состояний ожидания и готовности — несколько потоков. Эти потоки образуют очереди соответственно ожидающих и готовых потоков. Очереди потоков организуются путем объединения в списки описателей отдельных потоков. Таким образом, каждый описатель потока, кроме всего прочего, содержит по крайней мере один указатель на другой описатель, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать потоки, переводить потоки из одного состояния в другое. Если предположить, что на рис. 4.4 показана очередь готовых потоков, то запланированный порядок выполнения выглядит так: А, В, Е, D, С.
Рис. 4.4. Очередь потоков
Вытесняющие и невытесняющие алгоритмы планирования
С самых общих позиций все множество алгоритмов планирования можно разделить на два класса: вытесняющие и невытесняющие алгоритмы планирования.
Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению поток.
Вытесняющие (preemptive) алгоритмы — это такие способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается операционной системой, а не активной задачей.
Основным различием между вытесняющими и невытесняющими алгоритмами является степень централизации механизма планирования потоков. При вытесняющем мультипрограммировании функции планирования потоков целиком сосредоточены в операционной системе и программист пишет свое приложение, не заботясь о том, что оно будет выполняться одновременно с другими задачами. При этом операционная система выполняет следующие функции: определяет момент снятия с выполнения активного потока, запоминает его контекст, выбирает из очереди готовых потоков следующий, запускает новый поток на выполнение, загружая его контекст.
При невытесняющем мультипрограммировании механизм планирования распределен между операционной системой и прикладными программами. Прикладная программа, получив управление от операционной системы, сама определяет момент завершения очередного цикла своего выполнения и только затем передает управление ОС с помощью какого-либо системного вызова. ОС формирует очереди потоков и выбирает в соответствии с некоторым правилом (например, с учетом приоритетов) следующий поток на выполнение. Такой механизм создает проблемы как для пользователей, так и для разработчиков приложений.
Для пользователей это означает, что управление системой теряется на произвольный период времени, который определяется приложением (а не пользователем). Если приложение тратит слишком много времени на выполнение какой-либо работы, например на форматирование диска, пользователь не может переключиться с этой задачи На другую задачу, например на текстовый редактор, в то время как форматирование продолжалось бы в фоновом режиме.
Поэтому разработчики приложений для операционной среды с невытесняющей многозадачностью вынуждены, возлагая на себя часть функций планировщика, создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Например, программа форматирования может отформатировать одну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматирования, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить «дружественное» отношение своей программы к другим выполняемым одновременно с ней программам. Для этого в программе должны быть предусмотрены частые передачи управления операционной системе. Крайним проявлением «не дружественности» приложения является его зависание, которое приводит к общему краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм имеет возможность снять зависшую задачу с выполнения.
Однако распределение функций планирования потоков между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент возвращения управления, то при этом исключаются нерациональные прерывания программ в «неудобные» для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждого цикла выполнения использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит данные. Существенным преимуществом невытесняющего планирования является более высокая скорость переключения с потока на поток.
ПРИМЕЧАНИЕ
Понятия вытесняющих и невытесняющих алгоритмов планирования иногда отождествляют с понятиями приоритетных и бесприоритетных дисциплин, что, возможно, связано со звучанием соответствующих англоязычных терминов «preemptive» и «non-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 — функция отдачи управления, отличается от Thread-Switch тем, что поток просит поместить его в очередь готовых к выполнению, но низкоприоритетных потоков.
Планировщик NetWare использует несколько очередей готовых потоков (рис. 4.5). Только что созданный поток попадает в конец очереди RunHst, которая содержит готовые к выполнению потоки. После отказа от процессора поток попадает в ту или иную очередь в зависимости от того, какой из системных вызовов был использован при передаче управления. Поток поступает в конец очереди RunHst при вызове ThreadSwitch, в конец очереди DelayedWorkToDoHst при вызовах ThreadSwitchWithDelay или Del ay или же в конец очереди LowPrlorityRunList при вызове ThreadSwl tchLowPrlority.
После того как выполнявшийся процессором поток завершит свой очередной цикл выполнения, отдав управление с помощью одного из вызовов передачи управления (или вызова ожидания на семафоре), планировщик выбирает для выполнения стоящий первым в очереди RunList поток и запускает его. Потоки, находящиеся в очереди DelayedWorkToDoList, после завершения условия ожидания перемещаются в конец очереди RunList.
Потоки, находящиеся в очереди LowPriorltyRunList, запускаются на выполнение только в том случае, если очередь RunHst пуста. Обычно в эту очередь назначаются потоки, выполняющие несрочную фоновую работу.
Очередь WorkToDoList является в системе самой приоритетной. В эту очередь попадают так называемые рабочие потоки. В NetWare, как и в некоторых других ОС, вместо создания нового потока для выполнения определенной работы может быть использован уже существующий системный поток. Пул рабочих потоков создается при старте системы для системных целей и выполнения срочных работ. Рабочие потоки ОС обладают наивысшим приоритетом, то есть попадают на выполнение перед потоками из очереди RunList. Планировщик разрешает выполниться подряд только определенному количеству потоков из очереди Work -ToDoList, а затем запускает поток из очереди RunList.
Рис. 4.5. Схема планирования потоков в NetWare
Описанный невытесняющий механизм организации многопоточной работы в ОС NetWare v3.x и NetWare 4.x потенциально очень производителен, так как отличается небольшими накладными расходами ОС на диспетчеризацию потоков за счет простых алгоритмов планирования и иерархии контекстов. Но для достижения высокой производительности к разработчикам приложений для ОС NetWare предъявляются высокие требования, так как распределение процессорного времени между различными приложениями зависит в конечном счете от искусства программиста.