Сетевые операционные системы

Глава 4. Процессы и потоки

2004-10-04

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

Мультипрограммирование

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

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

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

Мультипрограммирование в системах пакетной обработки

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

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

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

Рассмотрим более детально совмещение во времени операции ввода-вывода и вычислений.

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

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

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

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

Общее время выполнения смеси задач часто оказывается меньше, чем их суммарное время последовательного выполнения. Однако вы-полнение отдельной задачи в мультипрограммном режиме может занять больше времени, чем при монопольном выделении процессора этой задаче. Действительно, при совместном использовании процессора в системе могут возникать ситуации, когда задача готова выполняться, но процессор занят выполнением другой задачи. В таких случаях задача, завершившая ввод-вывод, готова выполняться, но вынуждена ждать освобождения процессора, и это удлиняет срок ее выполнения. Так, из рис. 4.2 видно, что в однопро-граммном режиме задача А выполняется за 6 единиц времени, а в мультипро-граммном - за 7. Задача В также вместо 5 единиц времени выполняется за 6. Но зато время выполнения обеих задач в мультипрограммном режиме со-ставляет всего 8 единиц, что на 3 единицы меньше, чем при последователь-ном выполнении.

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

Мультипрограммирование в системах разделения времени

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

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

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

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

Мультипрограммирование в системах реального времени

Еще одна разновидность мультипрограммирования используется в системах реального времени, предназначенных для управления от компьюте-ра различными техническими объектами (например, станком, спутником, на-учной экспериментальной установкой и т.д.) или технологическими процес-сами (например, гальванической линией, доменным процессом и т.п.). Во всех этих случаях существует предельно допустимое время, в течение кото-рого должна быть выполнена та или иная управляющая объектом программа. В противном случае может произойти авария: спутник выйдет из зоны види-мости, экспериментальные данные, поступающие с датчиков, будут потеря-ны, толщина гальванического покрытия не будет соответствовать норме. Та-ким образом, критерием эффективности здесь является способность выдер-живать заранее заданные интервалы времени между запуском программы и получением результата (управляющего воздействия). Это время называется временем реакции системы, а соответствующее свойство системы - реактив-ностью. Требования ко времени реакции зависят от специфики управляемого процесса. Контроллер робота может требовать от встроенного компьютера ответ в течение менее 1 мс, в то время как при моделировании полета может быть приемлем ответ в 40 мс.

В системах реального времени мультипрограммная смесь представля-ет собой фиксированный набор заранее разработанных программ, а выбор программы на выполнение осуществляется по прерываниям (исходя из теку-щего состояния объекта) или в соответствии с расписанием плановых работ.

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

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

Мультипроцессорная обработка

Мультипроцессорная обработка - это способ организации вычисли-тельного процесса в системах с несколькими процессорами, при котором не-сколько задач (процессов, потоков) могут одновременно выполняться на раз-ных процессорах системы.

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

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

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

В наши дни становится общепринятым введение в ОС функций под-держки мультипроцессорной обработки данных. Такие функции имеются во всех популярных ОС, таких как Sun Solaris 2.x, Santa Crus Operations Open Server 3.х, IBM OS/2, Microsoft Windows NT и Novell NetWare, начиная с 4.1.

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

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

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

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

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

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

Масштабирование в асимметричной архитектуре реализуется иначе, чем в симметричной. Так как требование единого корпуса отсутствует, сис-тема может состоять из нескольких устройств, каждое из которых содержит один или несколько процессоров. Это масштабирование по горизонтали. Каждое такое устройство называется кластером, а вся мультипроцессорная система - кластерной.

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

Асимметричное мультипроцессирование является наиболее простым способом организации вычислительного процесса в системах с несколькими процессорами. Этот способ часто называют также "ведущий-ведомый".

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

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

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

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

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

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

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

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

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

Планирование процессов и потоков

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

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

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

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

Понятия "процесс" и "поток"

Чтобы поддерживать мультипрограммирование, ОС должна опреде-лить и оформить для себя те внутренние единицы работы, между которыми будет разделяться процессор и другие ресурсы компьютера. В настоящее время в большинстве операционных систем определены два типа единиц ра-боты. Более крупная единица работы, обычно носящая название процесса, или задачи, требует для своего выполнения нескольких более мелких работ, для обозначения которых используют термины "поток", или "нить".

ПРИМЕЧАНИЕ. При использовании этих терминов часто возникают сложности. Это происходит в силу нескольких причин. Во-первых, - специфика различных ОС, когда сов-падающие по сути понятия получили разные названия, например задача (task) в OS/2, OS/360 и процесс (process) в UNIX, Windows NT, NetWare. Во-вторых, по мере развития системного программирования и методов организации вычислении некоторые из этих терминов получили новое смысловое значение, особенно это касается понятия "процесс", который уступил многие свои свойства новому понятию "поток". В-третьих, терминоло-гические сложности порождаются наличием нескольких вариантов перевода англоязыч-ных терминов на русский язык. Например, термин "thread" переводится как "нить", "по-ток", "облегченный процесс", "минизадача" и др. Далее в качестве названия единиц рабо-ты ОС будут использоваться термины "процесс" и "поток". В тех же случаях, когда разли-чия между этими понятиями не будут играть существенной роли, они объединяются под обобщенным термином "задача".

Итак, в чем же состоят принципиальные отличия в понятиях "про-цесс" и "поток"?

Очевидно, что любая работа вычислительной системы заключается в выполнении некоторой программы. Поэтому и с процессом, и с потоком свя-зывается определенный программный код, который для этих целей оформля-ется в виде исполняемого модуля. Чтобы этот программный код мог быть выполнен, его необходимо загрузить в оперативную память, возможно, вы-делить некоторое место на диске для хранения данных, предоставить доступ к устройствам ввода-вывода, например к последовательному порту для полу-чения данных по подключенному к этому порту модему, и т.д. В ходе выпол-нения программе может также понадобиться доступ к информационным ре-сурсам, например файлам, портам TCP/UPD, семафорам. И, конечно же, не-возможно выполнение программы без предоставления ей процессорного времени, то есть времени, в течение которого процессор выполняет коды данной программы.

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

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

Для того чтобы процессы не могли вмешаться в распределение ресур-сов, а также не могли повредить коды и данные друг друга, важнейшей зада-чей ОС является изоляция одного процесса от другого. Для этого операцион-ная система обеспечивает каждый процесс отдельным виртуальным адрес-ным пространством, так что ни один процесс не может получить прямого доступа к командам и данным другого процесса.

ПРИМЕЧАНИЕ. Виртуальное адресное пространство процесса - это совокупность адре-сов, которыми может манипулировать программный модуль процесса. Операционная сис-тема отображает виртуальное адресное пространство процесса на отведенную процессу физическую память.

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

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

Потоки возникли в операционных системах как средство распаралле-ливания вычислений. Конечно, задача распараллеливания вычислений в рам-ках одного приложения может быть решена и традиционными способами.

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

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

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

ПРИМЕЧАНИЕ. Заметим, что в однопрограммных системах не возникает необходимо-сти введения понятия, обозначающего единицу работы, так как там не существует про-блемы разделения ресурсов.

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

Итак, мультипрограммирование более эффективно на уровне потоков, а не процессов. Каждый поток имеет собственный счетчик команд и стек. За-дача, оформленная в виде нескольких потоков в рамках одного процесса, может быть выполнена быстрее за счет псевдопараллельного (или парал-лельного в мультипроцессорной системе) выполнения ее отдельных частей. Например, если электронная таблица была разработана с учетом возможно-стей многопоточной обработки, то пользователь может запросить пересчет своего рабочего листа и одновременно продолжать заполнять таблицу. Осо-бенно эффективно можно использовать многопоточность для выполнения распределенных приложений, например многопоточный сервер может па-раллельно выполнять запросы сразу нескольких клиентов.

Использование потоков связано не только со стремлением повысить производительность системы за счет параллельных вычислений, но и с целью создания более читабельных, логичных программ. Введение нескольких по-токов выполнения упрощает программирование. Например, в задачах типа "писатель-читатель" один поток выполняет запись в буфер, а другой считы-вает записи из него. Поскольку они разделяют общий буфер, не стоит их де-лать отдельными процессами. Другой пример использования потоков - управление сигналами, такими как прерывание с клавиатуры (del или break). Вместо обработки сигнала прерывания один поток назначается для постоян-ного ожидания поступления сигналов. Таким образом, использование пото-ков может сократить необходимость в прерываниях пользовательского уров-ня. В этих примерах не столь важно параллельное выполнение, сколь важна ясность программы.

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

Создание процессов и потоков

Создать процесс - это прежде всего означает создать описатель процесса, в качестве которого выступает одна или несколько информационных структур, содержащих все сведения о процессе, необходимые операционной системе для управления им. В число таких сведений могут входить, например, идентификатор процесса, данные о расположении в памяти исполняемого модуля, степень привилегированности процесса (приоритет и права доступа) и т.п. Примерами описателей процесса являются блок управления задачей (ТСВ - Task Control Block) в OS/360, управляющий блок процесса (РСВ - Process Control Block) в OS/2, дескриптор процесса в UNIX, объект-процесс (object-process) в Windows NT.

Создание описателя процесса знаменует собой появление в системе еще одного претендента на вычислительные ресурсы. Начиная с этого мо-мента при распределении ресурсов ОС должна принимать во внимание по-требности нового процесса.

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

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

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

Рассмотрим в качестве примера создание процессов в популярной версии операционной системы UNIX System V Release 4. В этой системе по-токи не поддерживаются, в качестве единицы управления и единицы потреб-ления ресурсов выступает процесс.

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

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

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

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

После выполнения системного вызова fork оба процесса продолжают выполнение с одной и той же точки. Чтобы процесс мог опознать, является он родительским процессом или процессом-потомком, системный вызов fork возвращает в качестве своего значения в породивший процесс идентифика-тор порожденного процесса, а в порожденный процесс - NULL. Типичное разветвление на языке С записывается так:

if( fork () ) { действия родительского процесса } else { дейст-вия порожденного процесса }

Идентификатор потомка может быть присвоен переменной, входящей в контекст родительского процесса. Так как контекст процесса наследуется его потомками, то потомки могут узнать идентификаторы своих "старших братьев", таким образом сумма знаний наследуется при порождении и может быть распространена между родственными процессами. На независимости идентификатора процесса от выполняемой процессом программы построен механизм, позволяющий процессу перейти к выполнению другой программы с помощью системного вызова ехес.

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

Вновь созданному процессу операционная система присваивает цело-численный идентификатор, уникальный на весь период функционирования системы.

Планирование и диспетчеризация потоков

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

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

Планирование потоков, по существу, включает в себя решение двух задач:

• определение момента времени для смены текущего активного потока;
• выбор для выполнения потока из очереди готовых потоков.

Существует множество различных алгоритмов планирования потоков, по-своему решающих каждую из приведенных выше задач. Алгоритмы пла-нирования могут преследовать различные цели и обеспечивать разное каче-ство мультипрограммирования. Например, в одном случае выбирается такой алгоритм планирования, при котором гарантируется, что ни один по-ток/процесс не будет занимать процессор дольше определенного времени, в другом случае целью является максимально быстрое выполнение "коротких" задач, а в третьем случае - преимущественное право занять процессор полу-чают потоки интерактивных приложений. Именно особенности реализации планирования потоков в наибольшей степени определяют специфику опера-ционной системы, в частности, является ли она системой пакетной обработ-ки, системой разделения времени или системой реального времени.

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

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

Результатом работы статического планировщика является таблица, называемая расписанием, в которой указывается, какому потоку/процессу, когда и на какое время должен быть предоставлен процессор. Для построе-ния расписания планировщику нужны как можно более полные предвари-тельные знания о характеристиках набора задач, например о максимальном времени выполнения каждой задачи, ограничениях предшествования, огра-ничениях по взаимному исключению, предельным срокам и т.д.

После того как расписание готово, оно может использоваться опера-ционной системой для переключения потоков и процессов. При этом наклад-ные расходы ОС на исполнение расписания оказываются значительно мень-шими, чем при динамическом планировании, и сводятся лишь к диспетчери-зации потоков/процессов.

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

Диспетчеризация сводится к следующему:

• сохранение контекста текущего потока, который требуется сменить;
• загрузка контекста нового потока, выбранного в результате планирования;
• запуск нового потока на выполнение.

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

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

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

ПРИМЕЧАНИЕ. В различных ОС можно встретить компоненты ОС, имеющие названия планировщик (scheduler) или диспетчер (dispatcher). He следует однозначно судить о функциональном назначении этих компонентов по их названиям, то есть считать, что пла-нировщик выполняет планирование, а диспетчер - диспетчеризацию в том смысле, в ко-тором эти функции были определены выше. Чаще всего то и другое названия используют-ся для обозначения компонентов, которые занимаются планированием.

Состояния потока

ОС выполняет планирование потоков, принимая во внимание их состояние. В мультипрограммной системе поток может находиться в одном из трех основных состояний:

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

ПРИМЕЧАНИЕ. Состояния выполнения и ожидания могут быть отнесены и к задачам, выполняющимся в однопрограммном режиме, а вот состояние готовности характерно только для режима мультипрограммирования.

В течение своей жизни каждый поток переходит из одного состояния в другое в соответствии с алгоритмом планирования потоков, принятым в данной операционной системе.

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

В состоянии выполнения в однопроцессорной системе может нахо-диться не более одного потока, а в каждом из состояний ожидания и готовно-сти - несколько потоков. Эти потоки образуют очереди соответственно ожи-дающих и готовых потоков. Очереди потоков организуются путем объедине-ния в списки описателей отдельных потоков. Таким образом, каждый описа-тель потока, кроме всего прочего, содержит по крайней мере один указатель на другой описатель, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать по-токи, переводить потоки из одного состояния в другое. Если предположить, что на рис. 4.4 показана очередь готовых потоков, то запланированный поря-док выполнения выглядит так: А, В, Е, D, С.

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

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

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

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

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

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

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

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

ПРИМЕЧАНИЕ. Понятия вытесняющих и невытесняющих алгоритмов планирования иногда отождествляют с понятиями приоритетных и бесприоритетных дисциплин, что, возможно, связано со звучанием соответствующих англоязычных терминов "preemptive" и "non-preemptive". Однако это совершенно неверно, так как приоритеты в том и другом случаях могут как использоваться, так и не использоваться.

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

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

• ThreadSwitch- поток, вызвавший эту функцию, считает себя готовым к не-медленному выполнению, но отдает управление для того, чтобы могли вы-полняться и другие потоки;
• ThreadSwitchWithDelay - функция аналогична предыдущей, но поток счи-тает, что будет готов к выполнению только через определенное количество переключении с потока на поток;
• Delay - функция аналогична предыдущей, но задержка дается в миллисе-кундах;
• ThreadSwitchLowPriority - функция отдачи управления, отличается от ThreadSwitch тем, что поток просит поместить его в очередь готовых к вы-полнению, но низкоприоритетных потоков.

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

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

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

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

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

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

Продолжение следует...