Мультипрограммирование
§ Задачи и упражнения
Важнейшей функцией операционной системы является организация рационального использования всех ее аппаратных и информационных ресурсов. К основным ресурсам могут быть отнесены процессоры, память, внешние устройства, данные и программы. Располагающая одними и теми же аппаратными ресурсами, но управляемая различными ОС, вычислительная система может работать с разной степенью эффективности. Поэтому знание внутренних механизмов операционной системы позволяет косвенно судить о ее эксплуатационных возможностях и характеристиках. Хотя и в однопрограммной ОС необходимо решать задачи управления ресурсами (например, распределение памяти между приложением и ОС), главные сложности на этом пути возникают в мультипрограммных ОС, в которых за ресурсы конкурируют сразу несколько приложений. Именно поэтому большая часть всех проблем, рассматриваемых в этой главе, относится к мультипрограммным системам.
Мультипрограммирование
Мультипрограммирование, или многозадачность (multitasking), — это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются сразу несколько программ. Эти программы совместно используют не только процессор, но и другие ресурсы компьютера: оперативную и внешнюю память, устройства ввода-вывода, данные. Мультипрограммирование призвано повысить эффективность использования вычислительной системы, однако эффективность может пониматься по-разному. Наиболее характерными критериями эффективности вычислительных систем являются:
§ пропускная способность — количество задач, выполняемых вычислительной системой в единицу времени;
§ удобство работы пользователей, заключающееся, в частности, в том, что они имеют возможность интерактивно работать одновременно с несколькими приложениями на одной машине;
§ реактивность системы — способность системы выдерживать заранее заданные (возможно, очень короткие) интервалы времени между запуском программы и получением результата.
В зависимости от выбранного критерия эффективности ОС делятся на системы пакетной обработки, системы разделения времени и системы реального времени. Каждый тип ОС имеет специфические внутренние механизмы и особые области применения. Некоторые операционные системы могут поддерживать одновременно несколько режимов, например часть задач может выполняться в режиме пакетной обработки, а часть — в режиме реального времени или в режиме разделения времени.
Мультипроцессорная обработка
Мультипроцессорная обработка — это способ организации вычислительного процесса в системах с несколькими процессорами, при котором несколько задач (процессов, потоков) могут одновременно выполняться на разных процессорах системы.
Концепция мультипроцессирования ненова, она известна с 70-х годов, но до середины 80-х доступных многопроцессорных систем не существовало. Однако к настоящему времени стало обычным включение нескольких процессоров в архитектуру даже персонального компьютера. Более того, многопроцессорность теперь является одним из необходимых требований, которые предъявляются к компьютерам, используемым в качестве центрального сервера более-менее крупной сети.
Не следует путать мультипроцессорную обработку с мультипрограммной обработкой. В мультипрограммных системах параллельная работа разных устройств позволяет одновременно вести обработку нескольких программ, но при этом в процессоре в каждый момент времени выполняется только одна программа. То есть в этом случае несколько задач выполняются попеременно на одном процессоре, создавая лишь видимость параллельного выполнения. А в мультипроцессорных системах несколько задач выполняются действительно одновременно, так как имеется несколько обрабатывающих устройств — процессоров. Конечно, мульипроцессирование вовсе не исключает мультипрограммирования: на каждом из процессоров может попеременно выполняться некоторый закрепленный за данным процессором набор задач.
Мультипроцессорная организация системы приводит к усложнению всех алгоритмов управления ресурсами, например требуется планировать процессы не для одного, а для нескольких процессоров, что гораздо сложнее. Сложности заключаются и в возрастании числа конфликтов по обращению к устройствам ввода-вывода, данным, общей памяти и совместно используемым программам. Необходимо предусмотреть эффективные средства блокировки при доступе к разделяемым информационным структурам ядра. Все эти проблемы должна решать операционная система путем синхронизации процессов, ведения очередей и планирования ресурсов. Более того, сама операционная система должна быть спроектирована так, чтобы уменьшить существующие взаимозависимости между собственными компонентами.
В наши дни становится общепринятым введение в ОС, функций поддержки мультипроцессорной обработки данных. Такие функции имеются во всех популярных ОС, таких как Sun Solaris 2.x, Santa Crus Operations Open Server 3.x, 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.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 предъявляются высокие требования, так как распределение процессорного времени между различными приложениями зависит в конечном счете от искусства программиста.
Алгоритмы планирования, основанные на квантовании
В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени — квант. Смена активного потока происходит, если:
§ поток завершился и покинул систему;
§ произошла ошибка;
§ поток перешел в состояние ожидания;
§ исчерпан квант процессорного времени, отведенный данному потоку.
Поток, который исчерпал свой квант, переводится в состояние готовности и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых. Граф состояний потока, изображенный на рис. 4.6, соответствует алгоритму планирования, основанному на квантовании.
Рис. 4.6.Граф состояний потока в системе с квантованием
Кванты, выделяемые потокам, могут быть одинаковыми для всех потоков или различными. Рассмотрим, например, случай, когда всем потокам предоставляются кванты одинаковой длины q (рис. 4.7). Если в системе имеется п потоков, то время, которое поток проводит в ожидании следующего кванта, можно грубо оценить как q(n-l). Чем больше потоков в системе, тем больше время ожидания, тем меньше возможности вести одновременную интерактивную работу нескольким пользователям. Но если величина кванта выбрана очень небольшой, то значение произведения q(n-l) все равно будет достаточно мало для того, чтобы пользователь не ощущал дискомфорта от присутствия в системе других пользователей. Типичное значение кванта в системах разделения времени составляет десятки миллисекунд.
Рис. 4.7. Иллюстрация расчета времени ожидания в очереди
Если квант короткий, то суммарное время, которое проводит поток в ожидании процессора, прямо пропорционально времени, требуемому для его выполнения (то есть времени, которое потребовалось бы для выполнения этого потока при монопольном использовании вычислительной системы). Действительно, поскольку время ожидания между двумя циклами выполнения равно q(n-l), а количество циклов B/q, где В — требуемое время выполнения, то W*B(n-l). Заметим, что эти соотношения представляют собой весьма грубые оценки, основанные на предположении, что В значительно превышает q. При этом не учитывается, что потоки могут использовать кванты не полностью, что часть времени они могут тратить на ввод-вывод, что количество потоков в системе может динамически меняться и т. д.
Чем больше квант, тем выше вероятность того, что потоки завершатся в результате первого же цикла выполнения, и тем менее явной становится зависимость времени ожидания потоков от их времени выполнения. При достаточно большом кванте алгоритм квантования вырождается в алгоритм последовательной обработки, присущий однопрограммным системам, при котором время ожидания задачи в очереди вообще никак не зависит от ее длительности.
Кванты, выделяемые одному потоку, могут быть фиксированной величины, а могут и изменяться в разные периоды жизни потока. Пусть, например, первоначально каждому потоку назначается достаточно большой квант, а величина каждого следующего кванта уменьшается до некоторой заранее заданной величины. В таком случае преимущество получают короткие задачи, которые успевают выполняться в течение первого кванта, а длительные вычисления будут проводиться в фоновом режиме. Можно представить себе алгоритм планирования, в котором каждый следующий квант, выделяемый определенному потоку, больше предыдущего. Такой подход позволяет уменьшить накладные расходы на переключение задач в том случае, когда сразу несколько задач выполняют длительные вычисления.
Потоки получают для выполнения квант времени, но некоторые из них используют его не полностью, например из-за необходимости выполнить ввод или вывод данных. В результате возникает ситуация, когда потоки с интенсивными обращениями к вводу-выводу используют только небольшую часть выделенного им процессорного времени. Алгоритм планирования может исправить эту «несправедливость». В качестве компенсации за неиспользованные полностью кванты потоки получают привилегии при последующем обслуживании. Для этого планировщик создает две очереди готовых потоков (рис. 4.8). Очередь 1 образована потоками, которые пришли в состояние готовности в результате исчерпания кванта времени, а очередь 2 — потоками, у которых завершилась операция ввода-вывода. При выборе потока для выполнения прежде всего просматривается вторая очередь, и только если она пуста, квант выделяется потоку из первой очереди.
Многозадачные ОС теряют некоторое количество процессорного времени для выполнения вспомогательных работ во время переключения контекстов задач. При этом запоминаются и восстанавливаются регистры, флаги и указатели стека, а также проверяется статус задач для передачи управления. Затраты на эти вспомогательные действия не зависят от величины кванта времени, поэтому чем больше квант, тем меньше суммарные накладные расходы, связанные с переключением потоков.
Рис. 4.8.Квантование с предпочтением потоков, интенсивно обращающихся к вводу-выводу
ПРИМЕЧАНИЕ
В алгоритмах, основанных на квантовании, какую бы цель они не преследовали (предпочтение коротких или длинных задач, компенсация недоиспользованного кванта или минимизация накладных расходов, связанных с переключениями), не используется никакой предварительной информации о задачах. При поступлении задачи на обработку ОС не имеет никаких сведений о том, является ли она короткой или длинной, насколько интенсивными будут ее запросы к устройствам ввода-вывода, насколько важно ее быстрое выполнение и т. д. Дифференциация обслуживания при квантовании базируется на «истории существования» потока в системе.
Алгоритмы планирования, основанные на приоритетах
Другой важной концепцией, лежащей в основе многих вытесняющих алгоритмов планирования, является приоритетное обслуживание. Приоритетное обслуживание предполагает наличие у потоков некоторой изначально известной характеристики — приоритета, на основании которой определяется порядок их выполнения. Приоритет — это число, характеризующее степень привилегированности потока при использовании ресурсов вычислительной машины, в частности процессорного времени: чем выше приоритет, тем выше привилегии, тем меньше времени будет проводить поток в очередях.
Приоритет может выражаться целым или дробным, положительным или отрицательным значением. В некоторых ОС принято, что приоритет потока тем выше, чем больше (в арифметическом смысле) число, обозначающее приоритет. В других системах, наоборот, чем меньше число, тем выше приоритет.
В большинстве операционных систем, поддерживающих потоки, приоритет потока непосредственно связан с приоритетом процесса, в рамках которого выполняется данный поток. Приоритет процесса назначается операционной системой при его создании. Значение приоритета включается в описатель процесса и используется при назначении приоритета потокам этого процесса. При назначении приоритета вновь созданному процессу ОС учитывает, является этот процесс системным или прикладным, каков статус пользователя, запустившего процесс, было ли явное указание пользователя на присвоение процессу определенного уровня приоритета. Поток может быть инициирован не только по команде пользователя, но и в результате выполнения системного вызова другим потоком. В этом случае при назначении приоритета новому потоку ОС должна принимать во внимание значение параметров системного вызова.
Во многих ОС предусматривается возможность изменения приоритетов в течение жизни потока. Изменение приоритета могут происходить по инициативе самого потока, когда он обращается с соответствующим вызовом к операционной системе, или по инициативе пользователя, когда он выполняет соответствующую команду. Кроме того, ОС сама может изменять приоритеты потоков в зависимости от ситуации, складывающейся в системе. В последнем случае приоритеты называются динамическими в отличие от неизменяемых, фиксированных, приоритетов.
От того, какие приоритеты назначены потокам, существенно зависит эффективность работы всей вычислительной системы. В современных ОС во избежание разбалансировки системы, которая может возникнуть при неправильном назначении приоритетов, возможности пользователей влиять на приоритеты процессов и потоков стараются ограничивать. При этом обычные пользователи, как правило, не имеют права повышать приоритеты своим потокам, это разрешено делать (да и то в определенных пределах) только администраторам. В большинстве же случаев ОС присваивает приоритеты потокам по умолчанию.
В качестве примера рассмотрим схему назначения приоритетов потокам, принятую в операционной системе Windows NT (рис. 4.9). В системе определено 32 уровня приоритетов и два класса потоков — потоки реального времени и потоки с переменными приоритетами. Диапазон от 1 до 15 включительно отведен для потоков с переменными приоритетами, а от 16 до 31 — для более критичных ко времени потоков реального времени (приоритет 0 зарезервирован для системных целей).
Рис. 4.9. Схема назначения приоритетов в Windows NT
При создании процесса он в зависимости от класса получает по умолчанию базовый приоритет в верхней5 или нижней части диапазона. Базовый приоритет процесса в дальнейшем может быть повышен или понижен операционной системой. Первоначально Поток получает значение базового приоритета из диапазона базового приоритета процесса, в котором он был создан. Пусть, например, значение базового приоритета некоторого процесса равно К. Тогда все потоки данного процесса получат базовые приоритеты из диапазона [К-2, К+2]. Отсюда видно, что, изменяя базовый приоритет процесса, ОС может влиять на базовые приоритеты его потоков.
В Windows NT с течением времени приоритет потока, относящегося к классу потоков с переменными приоритетами, может отклоняться от базового приоритета потока, причем эти изменения могут быть не связаны с изменениями базового приоритета процесса. ОС может повышать приоритет потока (который в этом случае называется динамическим) в тех случаях, когда поток не полностью использовал отведенный ему квант, или понижать приоритет, если квант был использован полностью. ОС наращивает приоритет дифференцирование в зависимости от того, какого типа событие не дало потоку полностью использовать квант. В частности, ОС повышает приоритет в большей степени потокам, которые ожидают ввода с клавиатуры (интерактивным приложениям) и в меньшей степени — потокам, выполняющим дисковые операции. Именно на основе динамических приоритетов осуществляется планирование потоков. Начальной точкой отсчета для динамического приоритета является значение базового приоритета потока. Значение динамического приоритета потока ограничено снизу его базовым приоритетом, верхней же границей является нижняя граница диапазона приоритетов реального времени.
Существуют две разновидности приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами.
В обоих случаях выбор потока на выполнение из очереди готовых осуществляется одинаково: выбирается поток, имеющий наивысший приоритет. Однако проблема определения момента смены активного потока решается по-разному. В системах с относительными приоритетами активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или же произойдет ошибка, или поток завершится). На рис. 4.10, а показан граф состояний потока в системе с относительными приоритетами.
В системах с абсолютными приоритетами выполнение активного потока прерывается кроме указанных выше причин, еще при одном условии: если в очереди готовых потоков появился поток, приоритет которого выше приоритета активного потока. В этом случае прерванный поток переходит в состояние готовности (рис. 4.10, б).
В системах, в которых планирование осуществляется на основе относительных приоритетов, минимизируются затраты на переключения процессора с одной работы на другую. С другой стороны, здесь могут возникать ситуации, когда одна задача занимает процессор долгое время. Ясно, что для систем разделения времени и реального времени такая дисциплина обслуживания не подходит: интерактивное приложение может ждать своей очереди часами, пока вычислительной задаче не потребуется ввод-вывод. А вот в системах пакетной обработки (в том числе известной ОС OS/360) относительные приоритеты используются широко.
Рис. 4.10.Графы состояний потоков в системах с относительными и абсолютными приоритетами
В системах с абсолютными приоритетами время ожидания потока в очередях может быть сведено к минимуму, если ему назначить самый высокий приоритет. Такой поток будет вытеснять из процессора все остальные потоки (кроме потоков, имеющих такой же наивысший приоритет). Это делает
Смешанные алгоритмы планирования
Во многих операционных системах алгоритмы планирования построены с использованием как концепции квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора потока из очереди готовых определяется приоритетами потоков. Именно так реализовано планирование в системе Windows NT, в которой квантование сочетается с динамическими абсолютными приоритетами. На выполнение выбирается готовый поток с наивысшим приоритетом. Ему выделяется квант времени. Если во время выполнения в очереди готовых появляется поток с более высоким приоритетом, то он вытесняет выполняемый поток. Вытесненный поток возвращается в очередь готовых, причем он становится впереди всех остальных потоков имеющих такой же приоритет.
Рассмотрим более подробно алгоритм планирования в операционной системе UNIX System V Release 4. В этой ОС понятие «поток» отсутствует, и планирование осуществляется на уровне процессов. В системе UNIX System V Release 4 реализована вытесняющая многозадачность, основанная на использовании приоритетов и квантования.
Каждый процесс в зависимости от задачи, которую он решает, относится к одному из трех определенных в системе приоритетных классов: классу реального времени, классу системных процессов или классу процессов разделения времени. Назначение и обработка приоритетов выполняются для разных классов по-разному. Процессы системного класса, зарезервированные для ядра, используют стратегию фиксированных приоритетов. Уровень приоритета процессу назначается ядром и никогда не изменяется.
Процессы реального времени также используют стратегию фиксированных приоритетов, но пользователь может их изменять. Так как при наличии готовых к выполнению процессов реального времени другие процессы не рассматриваются, то процессы реального времени надо тщательно проектировать, чтобы они не захватывали процессор на слишком долгое время. Характеристики планирования процессов реального времени включают две величины: уровень глобального приоритета и квант времени. Для каждого уровня приоритета по умолчанию имеется своя величина кванта времени. Процессу разрешается захватывать процессор на указанный квант времени, а по его истечении планировщик снимает процесс с выполнения.
Процессы разделения времени были до появления UNIX System V Release 4 единственным классом процессов, и по умолчанию UNIX System V Release 4 назначает новому процессу именно этот класс. Состав класса процессов разделения времени наиболее неопределенный и часто меняющийся в отличие от системных процессов и процессов реального времени. Для справедливого распределения времени процессора между процессами в этом классе используется стратегия динамических приоритетов. Величина приоритета, назначаемого процессам разделения времени, вычисляется пропорционально значениям двух составляющих: пользовательской части и системной части. Пользовательская часть приоритета может быть изменена администратором и владельцем процесса, но в последнем случае только в сторону его снижения.
Системная составляющая позволяет планировщику управлять процессами в зависимости от того, как долго они занимают процессор, не уходя в состояние ожидания. У тех процессов, которые потребляют большие периоды процессорного времени без ухода в состояние ожидания, приоритет снижается, а у тех процессов, которые часто уходят в состояние ожидания после короткого периода ' использования процессора, приоритет повышается. Таким образом, процессам, ведущим себя не «по-джентльменски», дается низкий приоритет. Это означает, что они реже выбираются для выполнения. Это ущемление в правах компенсируется тем, что процессам с низким приоритетом даются большие кванты времени, чем процессам с высокими приоритетами. Таким образом, хотя низкоприоритетный процесс и не работает так часто, как высокоприоритетный, но зато, когда он наконец выбирается для выполнения, ему отводится больше времени.
Другой пример относится к операционной системе OS/2. Планирование здесь основано на использовании квантования и абсолютных динамических приоритетов. На множестве потоков определены приоритетные классы — критический (time critical), серверный (server), стандартный (regular) и остаточный (idle), в каждом из которых имеется 32 приоритетных уровня. Потоки критического класса имеют наивысший приоритет. В этот класс могут быть отнесены, например, системные потоки, выполняющие задачи управления сетью. Следующий по приоритетности класс предназначен, как это следует из его названия, для потоков, обслуживающих серверные приложения. К стандартному классу могут быть отнесены потоки обычных приложений. Потоки, входящие в остаточный класс, имеют самый низкий приоритет. К этому классу относится, например, поток, выводящий на экран заставку, когда в системе не выполняется никакой работы.
Поток из менее приоритетного класса не может быть выбран для выполнения, пока в очереди более приоритетного класса имеется хотя бы один поток. Внутри каждого класса потоки выбираются также по приоритетам. Потоки, имеющие одинаковое значение приоритета, обслуживаются в циклическом порядке.
Приоритеты могут изменяться планировщиком в следующих случаях:
§ Если поток находится в ожидании процессорного времени дольше, чем это задано системной переменной MAXWAIT, то его уровень приоритета будет автоматически увеличен операционной системой. При этом результирующее значение приоритета не должно превышать нижней границы диапазона приоритетов критического класса.
§ Если поток ушел на выполнение операции ввода-вывода, то после ее завершения он получит наивысшее значение приоритета своего класса.
§ Приоритет потока автоматически повышается, когда он поступает на выполнение.
ОС динамически устанавливает величину кванта, отводимого потоку для выполнения. Величина кванта зависит от загрузки системы и интенсивности подкачки. Параметры настройки системы позволяют явно задать границы изменения кванта. В любом случае он не может быть меньше 32 мс и больше 65 536 мс. Если поток был прерван до истечения кванта, то следующий выделенный ему интервал выполнения будет увеличен на время, равное одному периоду таймера (около 32 мс), и так до тех пор, пока квант не достигнет заранее заданного при настройке ОС предела.
Благодаря такому алгоритму планирования в OS/2 ни один поток не будет «забыт» системой и получит достаточно процессорного времени.
Управление памятью
Типы адресов
Символьные имена присваивает пользователь при написании программы на алгоритмическом языке или ассемблере. Виртуальные адреса вырабатывает транслятор, переводящий программу на машинный…Многослойная модель подсистемы ввода – вывода
Нижние слои подсистемы ввода – вывода должны включать индивидуальные драйвера конкретных физических устройств, а верхние слои должны обобщать…Управление вводом-выводом
Одной из главных функций ОС является управление всеми устройствами ввода-вывода компьютера. ОС должна передавать устройствам команды, перехватывать прерывания и обрабатывать ошибки; она также должна обеспечивать интерфейс между устройствами и остальной частью системы. В целях развития интерфейс должен быть одинаковым для всех типов устройств (независимость от устройств).
Физическая организация устройств ввода-вывода
Внешнее устройство обычно состоит из механического и электронного компонента. Электронный компонент называется контроллером устройства или… Операционная система обычно имеет дело не с устройством, а с контроллером.… ОС выполняет ввод-вывод, записывая команды в регистры контроллера. Например, контроллер гибкого диска IBM PC принимает…Организация программного обеспечения ввода-вывода
Ключевым принципом является независимость от устройств. Вид программы не должен зависеть от того, читает ли она данные с гибкого диска или с… Очень близкой к идее независимости от устройств является идея единообразного… Другим важным вопросом для программного обеспечения ввода-вывода является обработка ошибок. Вообще говоря, ошибки…Обработка прерываний
Драйверы устройств
В операционной системе только драйвер устройства знает о конкретных особенностях какого-либо устройства. Например, только драйвер диска имеет дело с… Драйвер устройства принимает запрос от устройств программного слоя и решает,… Первый шаг в реализации запроса ввода-вывода, например, для диска, состоит в преобразовании его из абстрактной формы в…Независимый от устройств слой операционной системы
Типичными функциями для независимого от устройств слоя являются: обеспечение общего интерфейса к драйверам устройств, именование устройств, … Остановимся на некоторых функциях данного перечня. Верхним слоям программного… При создании файла или заполнении его новыми данными необходимо выделить ему новые блоки. Для этого ОС должна вести…Пользовательский слой программного обеспечения
то библиотечная процедура write будет связана с программой. Набор подобных процедур является частью системы ввода-вывода. В частности,… Другой категорией программного обеспечения ввода-вывода является подсистема… Логическая организация файловой системыMicrosoft Windows
Microsoft Windows (/ˈwɪndoʊz/) — семейство проприетарных операционных систем компании Майкрософт (Microsoft). Операционные системы Windows работают на платформах x86, x86-64, IA-64, ARM. Существовали также версии для DEC Alpha, MIPS и PowerPC.
Версии Microsoft Windows
1. Windows 1.0 (1985) 2. Windows 2.0 (1987) 3. Windows 3.0 (1990)Windows 1.x
В отличие от последующих версий, Windows 1.0 предоставляла лишь ограниченную поддержку многозадачности для существующих программ MS-DOS,… Windows 1.0 часто считают «оболочкой» для операционной системы MS-DOS (это… Определение Windows 1.0 как «оболочки для DOS» исходит из того факта, что она была создана лишь как графическая среда…Windows 2.x
Вместо мозаичного размещения окон, который был в в Windows 1.x , в Windows 2.x реализована система перекрывающихся окон. Кроме того, используются…Windows 3.x
Windows 3.0 была выпущена 22 мая 1990 года и имела значительно обновлённый пользовательский интерфейс, а также технические усовершенствования,… Средство MS-DOS Executive, использовавшееся ранее для запуска программ и… Windows 3.0 была последней версией Windows, которая, по заявлениям Microsoft, поддерживала полную совместимость со…Windows NT
Windows NT была разработана «с нуля», развивалась отдельно от других ОС семейства Windows (Windows 3.x и Windows 9x) и, в отличие от них,… Разработка Windows NT под рабочим названием NT OS/2 была начата в ноябре 1988… Нужно отметить, что в качестве программных интерфейсов ОС NT изначально планировались API OS/2 и затем POSIX,…Windows 95
Это первая система семейства Windows, интерфейс которой используется во всех последующих версиях Windows: именно в ней появились такие элементы… Windows 95 — результат объединения продуктов MS-DOS и Windows, которые ранее… Основным нововведением в Windows 95 стала возможность выполнять 32-разрядные приложения на основе API Win32. Впервые…Windows 98
По сути, данная операционная система — это обновлённая версия Windows 95, по-прежнему являющаяся гибридным 16/32-разрядным продуктом, основанном на… Внутренний номер «первой редакции» Windows 98 — 4.10.1998, SE - 4.10.2222. Системные требования для Windows 98: процессор 486DX/66 MHz или лучше, 16 Мб ОЗУ и по крайней мере 195 Мб свободного…Windows 2000
Первая бета-версия системы была выпущена 27 сентября 1997 года. Изначально система носила название Windows NT 5.0, поскольку была следующей крупной… Windows 2000 выпускается в четырёх изданиях: Professional (издание для рабочих… Некоторыми из наиболее существенных улучшений в Windows 2000 по сравнению с Windows NT 4.0 являются: Поддержка службы…Windows ME
От своих предшественниц — Windows 95 и Windows 98 — отличается относительно небольшими обновлениями, такими как новый Internet Explorer 5.5 и… Одно из наиболее заметных изменений в Windows ME — в стандартной конфигурации…Windows XP
В отличие от предыдущей системы Windows 2000, которая поставлялась как в серверном, так и в клиентском вариантах, Windows XP является исключительно… Microsoft с 14 апреля 2009 года прекратила бесплатную поддержку операционной… Кроме этого, прекратилась бесплатная поддержка офисного пакета Office 2003, а также Windows Server 2003.Windows Server 2003
Windows Server 2003 является развитием Windows 2000 Server и серверным вариантом операционной системы Windows XP. Изначально Microsoft планировала… Windows Server 2008 — следующая серверная версия Windows NT, которая должна… Windows Server 2003 в основном развивает функции, заложенные в предыдущей версии системы — Windows 2000 Server. На это…Windows Fundamentals for Legacy PCs
Windows FLP или Windows Fundamentals for Legасу PCs (Code Name: Eiger) — версия Microsoft Windows, вышедшая 8 июля 2006 года. — Компактная ОС от Microsoft для устаревших PC, на базе Microsoft Windows XP Embedded Service Pack 2. Предполагает использование вместе с терминальными серверами (Microsoft, Citrix). Также возможен запуск небольшого количества локальных приложений.
Windows Vista
В линейке продуктов Windows NT Windows Vista носит номер версии 6.0 (Windows 2000 — 5.0, Windows XP — 5.1, Windows Server 2003 — 5.2). Для… Windows Vista, как и Windows XP, — исключительно клиентская система. Microsoft… 30 ноября 2006 года Microsoft официально выпустила Windows Vista и Office 2007 для корпоративных клиентов. 30 января…Windows Home Server
Windows Home Server — это серверная операционная система компании Microsoft, которая построена на основе Windows Server 2003 SP2 и ориентирована на домашних пользователей (что видно из названия — англ. home — дом) для использования в домашних сетях.
Продукт был анонсирован Биллом Гейтсом 7 января 2007 года и вышел 16 июля 2007 года.
Windows Server 2008
Windows Server 2008 включает вариант установки называемый Server Core (русск. Установка ядра сервера). Server Core — это существенно облегченная… В Windows Server 2008 произошло значительное обновление Служб Терминалов… Другая важная особенность, добавленная в Службы Терминалов — Terminal Services Gateway и Terminal Services Web Access…Windows 7
Microsoft сделала заявление о том, что операционная система поступит в продажу 22 октября 2009 года, меньше, чем через три года после выпуска… В состав Windows 7 вошли как некоторые разработки, исключенные из Windows… В Windows 7 будет функция отключения или включения браузера Internet Explorer.Ссылки
http://www.windxp.com.ru/win7/winfag.htm