45440

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

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-11-17

611 KB

54 чел.

Управление задачами

Понятия процесса (process) и потока выполнения (thread) нам уже известны. Мы теперь знаем, в чем здесь имеется сходство, а в чем — существенное различие. Однако в данной главе при рассмотрении вопросов распределения процессорного времени мы не всегда будем разделять эти понятия. Дело в том, что по отношению к этому ресурсу — процессорному времени — оба этих понятия практически эквиваленты. Они выступают просто как некоторая работа, для выполнения которой необходимо предоставить центральный процессор. Поэтому мы будем в основном использовать термин задача (task), который является как бы обобщающим. Ведь каждый поток выполнения на самом деле получает статус задачи, и для него создается соответствующий дескриптор. Но мы должны помнить о различиях между дескриптором процесса и дескриптором задачи. Даже если процесс состоит из единственного потока, мы говорим о дескрипторе процесса, содержащем информацию, с помощью которой операционная система отслеживает все ресурсы, необходимые процессу для его выполнения. Один из основных модулей супервизора операционной системы — диспетчер задач — переводит процессы в одно из состояний в зависимости от того, доступен тот или иной ресурс или не доступен. И поскольку в мультизадачной системе любой процесс содержит хотя бы один поток, то потоку (то есть задаче) ставится в соответствие дескриптор задачи, в котором сохраняется контекст этих вычислений. Сказанное справедливо для мультипрограммных систем, поддерживающих мультизадачный режим. В мультипрограммных системах, не поддерживающих мультизадачность, контекст прерванного процесса хранится в дескрипторе этого процесса. Заметим, что повсеместно распространенные системы Windows 9x/NT/2000/XP являются и мультипрограммными, и мультизадачными. Не случайно начиная с Windows NT и Windows 95 компания Microsoft отказалась от термина «задача» и стала использовать понятия процесса и потока выполнения (треда, нити). Правда, для изложения вопросов диспетчеризации это становится неудобным, ибо здесь чаще используется обобщающее понятие.

Еще одним доводом в пользу термина «задача» при рассмотрении вопросов организации распределения процессорного времени между выполняющимися вычислениями является аналогичный выбор этой сущности разработчиками процессоров. Именно для отображения этой ситуации и обеспечения дополнительными возможностями системных программистов в решении вопросов распределения процессорного времени они вводят специальные информационные структуры и аппаратную поддержку для работы с ними. Во многих современных микропроцессорах, предназначенных для построения на их основе мощных мультипрограммных и мультизадачных систем, имеются дескрипторы задач. Примером, подтверждающим этот тезис, являются микропроцессоры, совместимые с архитектурой ia32, то есть с 32-разрядными процессорами фирмы Intel. Основные архитектурные особенности этих микропроцессоров, специально проработанные для организации мультизадачных операционных систем, рассматриваются достаточно подробно в главе 4. Здесь мы лишь отметим тот факт, что в этих процессорах имеется специальная аппаратная поддержка организации мультизадачного (и мультипрограммного) режима. Речь идет о сегменте состояния задачи (Task State Segment, TSS), который предназначен, прежде всего, для сохранения контекста потока или процесса и который легко позволяет организовать и мультипрограммный, и мультизадачный режимы. Не случайно был введен термин «задача», ибо он здесь применим и по отношению к полноценному вычислительному процессу, и по отношению к легковесному процессу (потоку выполнения, треду, нити). На самом деле этот аппаратный механизм применяется гораздо реже, чем об этом думали разработчики архитектуры ia32. На практике оказалось, что для сохранения контекста потоков эффективнее использовать программные механизмы, хотя они и не обеспечивают такой же надежности, как аппаратные.

Итак, операционная система выполняет следующие основные функции, связанные с управлением процессами и задачами:

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

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

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

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

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

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

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

Когда говорят о диспетчеризации, то всегда в явном или неявном виде подразумевают понятие задачи (потока выполнения). Если операционная система не поддерживает механизм потоковых вычислений, то можно заменять понятие задачи понятием процесса. Ко всему прочему, часто понятие задачи используется в таком контексте, что для его трактовки приходится использовать термин «процесс».

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

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

Задача планирования процессов возникла очень давно — в первых пакетных операционных системах при планировании пакетов задач, которые должны были выполняться на компьютере и по возможности бесконфликтно и оптимально использовать его ресурсы. В настоящее время актуальность этой задачи стала меньше. На первый план уже очень давно вышли задачи динамического (или краткосрочного) планирования, то есть текущего наиболее эффективного распределения ресурсов, возникающего практически по каждому событию. Задачи динамического планирования стали называть диспетчеризацией1. Очевидно, что планирование процессов осуществляется гораздо реже, чем текущее распределение ресурсов между уже выполняющимися задачами. Основное различие между долгосрочным и краткосрочным планировщиками заключается в частоте их запуска, например: краткосрочный планировщик может запускаться каждые 30 или 100 мс, долгосрочный — один раз в несколько минут (или чаще; тут многое зависит от общей длительности решения заданий пользователей).

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

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

Планирование вычислительных процессов и стратегии планирования

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

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

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

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

На сегодняшний день абсолютное большинство компьютеров — это персональные IBM-совместимые компьютеры, работающие на платформах Windows компании Microsoft. Это однопользовательские диалоговые мультипрограммные и мультизадачные системы. При создании операционных систем для персональных компьютеров разработчики, прежде всего, стараются обеспечить комфортную работу с системой, то есть основные усилия уходят на проработку пользовательского интерфейса. Что касается эффективности организации вычислений, то она, видимо, тоже должна оцениваться с этих позиций. Если же считать системы Windows операционными системами общего назначения, что тоже возможно, ибо эти системы повсеместно используют для решения самых разнообразных задач автоматизации, то также следует признать, что принятые в системах Windows стратегии обслуживания приводят к достаточно высокой эффективности вычислений. Некоторым даже удается использовать системы Windows NT/2000 для решения задач реального времени. Однако выбор этих операционных систем для таких задач скорее всего делается либо вследствие некомпетентности, либо из-за невысоких требований ко времени отклика и гарантиям обслуживания со стороны самих систем реального времени, которые реализуются на Windows NT/2000.

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

Например, в Windows 2000 можно открыть окно Свойства системы, перейти на вкладку Дополнительно, щелчком на кнопке Параметры быстродействия открыть одноименное окно и с помощью переключателя в разделе Отклик приложений установить режим Оптимизировать быстродействие приложений. Это будет соответствовать выбору такой стратегии диспетчеризации задач, в соответствии с которой приоритет на получение процессорного времени будут иметь задачи пользователя, а не фоновые служебные вычисления. В предыдущей версии ОС — Windows NT 4.0 — для выбора нужной ему стратегии пользователь должен был на вкладке Быстродействие окна Свойства системы установить желаемое значение в поле Ускорение приложения переднего плана. Это ускорение можно сделать максимальным (по умолчанию), а можно его свести к нулю. Последний вариант означал бы, что все запущенные пользователем приложения будут иметь одинаковый приоритет. Последнее важно, если пользователь часто запускает сразу по нескольку задач, каждая из которых требует длительных вычислений, причем эти приложения часто используют операции ввода-вывода. Например, если нужно обработать несколько десятков музыкальных или графических файлов, причем каждый файл имеет большие размеры, то выполнение всей этой работы как множества параллельно исполняющихся задач будет завершено за меньшее время, если указать стратегию равенства обслуживания. Должно быть очевидным, что любой другой вариант решения этой задачи потребует больше времени. Например, последовательное выполнение задач обработки каждого файла (то есть обработка следующего файла может начинаться только по окончании обработки предыдущего) приведет к самому длительному варианту. Стратегия предоставления процессорного времени в первую очередь текущей задаче пользователя, которая установлена в системах Windows по умолчанию, приведет нас к промежуточному (по затратам времени) результату.

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

Дисциплины диспетчеризации

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

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

В концепции приоритетов имеем следующие варианты:

  •  приоритет, присвоенный задаче, является величиной постоянной;
  •  приоритет изменяется в течение времени решения задачи (динамический приоритет). 

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

Рассмотрим некоторые основные (наиболее часто используемые) дисциплины диспетчеризации.

Самой простой в реализации является дисциплина FCFS(First Come First Served — первым пришел, первым обслужен), согласно которой задачи обслуживаются «в порядке очереди», то есть в порядке их появления. Те задачи, которые были заблокированы в процессе работы (попали в какое-либо из состояний ожидания, например из-за операций ввода-вывода), после перехода в состояние готовности вновь ставятся в эту очередь готовности. При этом возможны два варианта. Первый (са-•;ый простой) — это ставить разблокированную задачу в конец очереди готовых : выполнению задач. Этот вариант применяется чаще всего. Второй вариант заключается в том, что диспетчер помещает разблокированную задачу перед теми задачами, которые еще не выполнялись. Другими словами, в этом случае образу-тся две очереди (рис. 2.2): одна очередь образуется из новых задач, а вторая очередь — из ранее выполнявшихся, но попавших в состояние ожидания. Такой подход позволяет реализовать стратегию обслуживания «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина обслуживания не требует внешнего вмешательства в ход вычислений, при ней не происходит перераспределения процессорного времени. Про нее можно сказать, что она относится к не вытесняющим дисциплинам2.

К достоинствам этой дисциплины прежде всего можно отнести простоту реализации и малые расходы системных ресурсов на формирование очереди задач.

Однако эта дисциплина приводит к тому, что при увеличении загрузки вычислительной системы растет и среднее время ожидания обслуживания, причем короткие задания (требующие небольших затрат машинного времени) вынуждены ожидать столько же, сколько трудоемкие задания. Избежать этого недостатка позволяют дисциплины SJN и SRT. Правило FCFS применяется и в более сложных дисциплинах диспетчеризации. Например, в приоритетных дисциплинах диспетчеризации, если имеется несколько задач с одинаковым приоритетом, которые стоят в очереди готовых к выполнению задач, то попадают они в эту очередь с учетом времени.

Дисциплина обслуживания SJN( Shortest Job Next — следующим выполняется самое короткое задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Необходимость сообщать операционной системе характеристики задач с описанием потребностей в ресурсах вычислительной системы привела к тому, что были разработаны соответствующие языковые средства. В частности, ныне уже забытый язык JCL (Job Control Language — язык управления заданиями) был одним из наиболее известных. Пользователи вынуждены были указывать предполагаемое время выполнения задачи и для того, чтобы они не злоупотребляли возможностью указать заведомо меньшее время выполнения (с целью возможности получить результаты раньше других), ввели подсчет реальных потребностей. Диспетчер задач сравнивал заказанное время и время выполнения и в случае превышения указанной оценки потребности в данном ресурсе ставил данное задание не в начало, а в конец очереди. Еще в некоторых операционных системах в таких случаях использовалась система штрафов, при которой в случае превышения заказанного машинного времени оплата вычислительных ресурсов осуществлялась уже по другим расценкам.

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

Для устранения этого недостатка и была предложена дисциплина SRT (Shortest Remaining Time) — следующим будет выполняться задание, которому осталось меньше всего выполняться на процессоре.

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

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

Для решения перечисленных проблем используется дисциплина обслуживания, называемая карусельной (Round Robin, RR), и приоритетные методы обслуживания.

Дисциплина обслуживания RR предполагает, что каждая задача получает процессорное время порциями или, как говорят, квантами времени (time slice) q. После окончания кванта времени q задача снимается с процессора, и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению. Эту дисциплину обслуживания иллюстрирует рис. 2.3. Для оптимальной работы системы необходимо правильно выбрать закон, по которому кванты времени выделяются задачам.

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

В некоторых операционных системах есть возможность указывать в явном виде величину кванта времени или диапазон возможных значений, тогда система будет стараться выбирать оптимальное значение сама. Например, в операционной системе OS/2 в файле CONFIG.SYS есть возможность с помощью оператора TIMESLICE указать минимальное и максимальное значения для кванта q. Так, например, строка TIMESLICE=32,256 указывает, что минимальное значение равно 32 мс, а максимальное — 256. Если некоторая задача прервана, поскольку израсходован выделенный ей квант времени q, то следующий выделенный ей интервал будет увеличен на время, равное одному периоду таймера (около 32 мс), и так до тех пор, пока квант времени не станет равным максимальному значению, указанному в операторе TIMESLICE. Этот метод позволяет OS/2 уменьшить накладные расходы на переключение задач в том случае, если несколько задач параллельно выполняют длительные вычисления. Следует заметить, что диспетчеризация задач в этой операционной системе реализована, пожалуй, наилучшим образом с точки зрения реакции системы и эффективности использования процессорного времени.

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

Дисциплина диспетчеризации RR — это одна из самых распространенных дисциплин. Однако бывают ситуации, когда операционная система не поддерживает в явном виде дисциплину карусельной диспетчеризации. Например, в некоторых операционных системах реального времени используется диспетчер задач, работающий по принципу абсолютных приоритетов (процессор предоставляется задаче с максимальным приоритетом, а при равенстве приоритетов он действует по принципу очередности) [7, 11]. Другими словами, причиной снятия задачи с выполнения может быть только появление задачи с более высоким приоритетом. Поэтому если нужно организовать обслуживание задач таким образом, чтобы все они получали процессорное время равномерно и равноправно, то системный оператор может сам организовать эту дисциплину. Для этого достаточно всем пользовательским задачам присвоить одинаковые приоритеты и создать одну высокоприоритетную задачу, которая не должна ничего делать, но которая, тем не менее, будет по таймеру (через указанные интервалы времени) планироваться на выполнение. Благодаря высокому приоритету этой задачи текущее приложение будет сниматься с выполнения и ставиться в конец очереди, а поскольку этой высокоприоритетной задаче на самом деле ничего делать не надо, то она тут же освободит процессор, и из очереди готовности будет взята следующая задача.

В своей простейшей реализации дисциплина карусельной диспетчеризации предполагает, что все задачи имеют одинаковый приоритет. Если же необходимо ввести механизм приоритетного обслуживания, то это, как правило, делается за счет организации нескольких очередей. Процессорное время предоставляется в первую очередь тем задачам, которые стоят в самой привилегированной очереди. Если она пустая, то диспетчер задач начинает просматривать остальные очереди. Именно по такому алгоритму действует диспетчер задач в операционных системах OS/2, Windows 9x, Windows NT/2000/XP и многих других. Отличия в основном заключаются в количестве очередей и в правилах, касающихся перемещения задач из одной очереди в другую.

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

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

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

Итак, диспетчеризация без перераспределения процессорного времени, то есть не вытесняющая (non-preemptive multitasking), или кооперативная, многозадачность (cooperative multitasking), — это такой способ диспетчеризации задач, при котором активная задача выполняется до тех пор, пока она сама, что называется «по собственной инициативе», не отдаст управление диспетчеру задач для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс или поток. Дисциплины обслуживания FCFS, SJN, SRT относятся к не вытесняющим.

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

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

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

Например, в ныне уже забытой операционной среде Windows 3.x нативные 16-разрядные приложения этой системы разделяли между собой процессорное время именно таким образом. И именно программисты должны были обеспечивать «дружественное» отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая управление ядру системы. Крайним проявлением «недружественности» приложения является его зависание, приводящее к общему краху системы — прекращению всех вычислений. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный механизм диспетчеризации, во-первых, обеспечивает все задачи процессорным временем, во-вторых, дает возможность иметь надежные механизмы мониторинга вычислений и, в-третьих, позволяет снять зависшую задачу с выполнения.

Однако распределение функций диспетчеризации между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и достоинством, потому что дает возможность разработчику приложений самому планировать распределение процессорного времени наиболее подходящим для данного фиксированного набора задач образом [27, 44, 46]. Так как разработчик -м определяет в программе момент времени передачи управления, то при этом исключаются нерациональные прерывания программ в «неудобные» для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена, что на протяжении этого периода никто другой их не изменит. Примером эффективного применения не вытесняющей многозадачности является сетевая операционная система Novell NetWare, в которой в значительной степени благо-ларя этому достигнута высокая скорость выполнения файловых операций. Менее удачным оказалось использование не вытесняющей многозадачности в операционной среде Windows 3.x. К счастью, на сегодня эта операционная система уже нигде не применяется, ее с успехом заменила сначала Windows 95, а затем и Windows 98. Правда, следует заметить, что при выполнении в этих операционных системах старых 16-разрядных приложений, разработанных в свое время для операционной среды Win 16 API, создается виртуальная машина, работающая по принципам не вытесняющей многозадачности.

Качество диспетчеризации и гарантии обслуживания

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

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

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

Гарантировать обслуживание можно, например, следующими тремя способами.

  •  Выделять минимальную долю процессорного времени некоторому классу процессов, если по крайней мере один из них готов к исполнению. Например, можно отводить 20 % от каждых 10 мс процессам реального времени, 40 % от каждых 2 с — интерактивным процессам и 10 % от каждых 5 мин — пакетным (фоновым) процессам.
  •  Выделять минимальную долю процессорного времени некоторому конкретному процессу, если он готов к выполнению.
  •  Выделять столько процессорного времени некоторому процессу, чтобы он мог выполнить свои вычисления к сроку.

Для сравнения алгоритмов диспетчеризации обычно используются некоторые критерии.

  •  Загрузка центрального процессора (CPU utilization). В большинстве персональных систем средняя загрузка процессора не превышает 2-3 %, доходя в моменты выполнения сложных вычислений и до 100 %. В реальных системах, где компьютеры (например, серверы) выполняют очень много работы, загрузка процессора колеблется в пределах от 15-40 % (для легко загруженного процессора) до 90-100 % (для тяжело загруженного процессора).
  •  Пропускная способность центрального процессора (CPU throughput). Пропускная способность процессора может измеряться количеством процессов, которые выполняются в единицу времени.
  •  Время оборота (turnaround time). Для некоторых процессов важным критерием является полное время выполнения, то есть интервал от момента появления процесса во входной очереди до момента его завершения. Это время названо временем оборота и включает время ожидания во входной очереди, время ожидания в очереди готовых процессов, время ожидания в очередях к оборудованию, время выполнения в процессоре и время ввода-вывода.
  •  Время ожидания (waiting time). Под временем ожидания понимается суммарное время нахождения процесса в очереди готовых процессов.
  •  Время отклика (response time). Для интерактивных программ важным показателем является время отклика, или время, прошедшее от момента попадания процесса во входную очередь до момента первого обращения к терминалу.

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

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

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

В случае мультипроцессорных систем применяются следующие методы повышения производительности системы:

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

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

Диспетчеризация задач с использованием динамических приоритетов

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

Рассмотрим, например, как реализован механизм динамических приоритетов в операционной системе UNIX, которая, как известно, не относится к ОС РВ. Операцией- ные системы класса UNIX относятся к мультитерминальным диалоговым системам. Основная стратегия обслуживания, применяемая в UNIX-системах, — это равенство в обслуживании и обеспечение приемлемого времени реакции системы. Реализуется эта стратегия за счет дисциплины диспетчеризации RR с несколькими очередями и механизма динамических приоритетов. Приоритет процесса вычисляется следующим образом [39]. Во-первых, в вычислении участвуют значения двух полей дескриптора процесса — p_nice и р_сpu. Первое из них назначается пользователем явно или формируется по умолчанию с помощью системы программирования. Второе поле формируется диспетчером задач (планировщиком разделения времени) и называется системной составляющей или текущим приоритетом. Другими словами, каждый процесс имеет два атрибута приоритета. С учетом этого приоритета и распределяется между исполняющимися задачами процессорное время: текущий приоритет, на основании которого происходит планирование, и заказанный относительный приоритет (называемый nice number, или просто nice).

Схема нумерации текущих приоритетов различна для различных версий UNIX. Например, более высокому значению текущего приоритета может соответствовать более низкий фактический приоритет планирования. Разделение между приоритетами режима ядра и задачи также зависит от версии. Рассмотрим частный случай, когда текущий приоритет процесса варьируется в диапазоне от 0 (низкий приоритет) до 127 (наивысший приоритет), Процессы, выполняющиеся в режиме задачи, имеют более низкий приоритет, чем в режиме ядра. Для режима задачи приоритет меняется в диапазоне 0-65, для режима ядра — 66-95 (системный диапазон). Процессы, приоритеты которых лежат в диапазоне 96-127, являются процессами с фиксированным приоритетом, не изменяемым операционной системой, и предназначены для поддержки приложений реального времени.

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

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

Текущий приоритет процесса в режиме задачи p_priuser, как мы только что отмечали, зависит от значения относительного приоритета p_nice и степени использования вычислительных ресурсов р_сpu:

p_priuser = а * p_nice - b * p_cpu

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

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

Возможно использование следующей формулы:

p_cpup_cpu/2

В этом правиле проявляется недостаток нивелирования приоритетов при повышении загрузки системы. Происходит это потому, что в таком случае каждый процесс получает незначительный объем вычислительных ресурсов и, следовательно, имеет малую составляющую р_срu, которая еще более уменьшается благодаря формуле пересчета величины р_срu. В результате загрузка процессора перестает оказывать заметное влияние на приоритет, и низкоприоритетные процессы (то есть процессы с высоким значением nice number) практически «отлучаются» от вычислительных ресурсов системы.

В некоторых версиях UNIX для пересчета значения р_срu используется другая формула:

p_cpu = p_cpu * (2 * load)/(2 * load + 1)

Здесь параметр load равен среднему числу процессов, находившихся в очереди на выполнение за последнюю секунду, и характеризует среднюю загрузку системы за этот период времени. Этот алгоритм позволяет частично избавиться от недостатка планирования по формуле p_cpu = p_cpu/2, поскольку при значительной загрузке системы уменьшение р_срu при пересчете будет происходить медленнее.

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

Аналогичные механизмы имеют место и в таких операционных системах, как OS/2 или Windows NT/2000/XP. Правда, алгоритмы изменения приоритета задач в этих системах иные. Например, в Windows NT/2000/XP каждый поток выполнения имеет базовый уровень приоритета, который лежит в диапазоне от двух уровней ниже базового приоритета процесса, его породившего, до двух уровней выше этого приоритета, как показано на рис. 2.4. Базовый приоритет процесса определяет, сколь сильно могут различаться приоритеты потоков этого процесса и как они соотносятся с приоритетами потоков других процессов. Поток наследует этот базовый приоритет и может изменять его так, чтобы он стал немного больше или немного меньше. В результате получается приоритет планирования, с которым поток и начинает исполняться. В процессе исполнения потока его приоритет может отклоняться от базового.

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

Для определения порядка выполнения потоков диспетчер задач использует систему приоритетов, направляя на выполнение задачи с высоким приоритетом раньше задач с низким приоритетом. Система прекращает исполнение, или вытесняет (preempts), текущий поток, если становится готовым к выполнению другой поток с более высоким приоритетом.

Имеется группа очередей — по одной для каждого приоритета. В операционных системах Windows NT/2000/XP используется один и тот же диспетчер задач. Он поддерживает 32 уровня приоритета. Задачи делятся на два класса: реального времени и переменного приоритета. Задачи реального времени, имеющие приоритеты от 16 до 31, — это высокоприоритетные потоки, используемые программами, критическими по времени выполнения, то есть требующими немедленного внимания системы (по терминологии Microsoft).

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

Большинство задач в системе относятся к классу переменного приоритета с уров-1И приоритета (номером очереди) от 1 до 15. Эти очереди используются зада-ами с переменным приоритетом (variable priority), так как диспетчер задач для оптимизации отклика системы корректирует их приоритеты по мере выполнения. Диспетчер приостанавливает исполнение текущей задачи, после того как та израсходует свой квант времени. При этом если прерванная задача — это поток временного приоритета, то диспетчер задач понижает приоритет этого потока выполнения на единицу и перемещает в другую очередь. Таким образом, приоритет задачи, выполняющей много вычислений, постепенно понижается (до значения его базового приоритета). С другой стороны, диспетчер повышает приоритет задачи после ее освобождения из состояния ожидания. Обычно добавка ; приоритету задачи определяется кодом исполнительной системы, находя-мся вне ядра операционной системы, однако величина этой добавки зависит !т типа события, которого ожидала заблокированная задача. Так, например, поток, ожидавший ввода очередного байта с клавиатуры, получает большую добавку к значению своего приоритета, чем поток ввода-вывода, работавший с дисковым накопителем. Однако в любом случае значение приоритета не может достигнуть 16.

В операционной системе OS/2 схема динамической приоритетной диспетчеризации несколько иная, хоть и похожа3. В OS/2 также имеется четыре класса задач. II для каждого класса задач имеется своя группа приоритетов с интервалом значений от 0 до 31. Итого, 128 различных уровней и, соответственно, 128 возможных очередей готовых к выполнению задач (потоков).

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

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

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

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

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

OS/2 самостоятельно изменяет приоритет выполняющихся программ независимо от уровня, установленного самим приложением. Этот механизм называется повышением приоритета (priority boost). Операционная система изменяет приоритет задачи в трех случаях [26].

  •  Повышение приоритета активной задачи (foreground boost). Приоритет задачи автоматически повышается, когда она становится активной. Это снижает время реакции активного приложения на действия пользователя по сравнению с фоновыми программами.
  •  Повышение приоритета ввода-вывода (Input/Output boost). По завершении операции ввода-вывода задача получает самый высокий уровень приоритета ее класса. Таким образом обеспечивается завершение всех незаконченных операций ввода-вывода.
  •  Повышение приоритета «забытой» задачи (starvation boost). Если задача не получает управление в течение достаточно долгого времени (этот промежуток времени задает оператор MAXWAIT в файле CONFIG.SYS4), диспетчер задач OS/2 временно присваивает ей уровень приоритета, не превышающий критический. В результате переключение на такую «забытую» программу происходит быстрее. После выполнения приложения в течение одного кванта времени его приоритет вновь снижается до остаточного. В сильно загруженных системах этот механизм позволяет программам с остаточным приоритетом работать хотя бы в краткие интервалы времени. В противном случае они вообще никогда бы не получили управление.

Если нет необходимости использовать метод динамического изменения приоритета, то с помощью оператора PRIORITY = ABSOLUTE в файле CONFIG.SYS можно ввести дисциплину абсолютных приоритетов; по умолчанию оператор PRIORITY имеет значение DYNAMIC.

Управление памятью в операционных системах

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

Память и отображения, виртуальное адресное пространство

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

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

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

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

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

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

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

  •  объем виртуального адресного пространства программы Vv меньше объема физической памяти Vp (Vv < Vp);
  •  объем виртуального адресного пространства программы Vv равен объему физической памяти Vp (Vv = Vp); 
  •  объем виртуального адресного пространства программы Vv больше объема физической памяти Vp (Vv > Vp).

Первая ситуация (Vv < Vp) ныне практически не встречается, но, тем не менее, это реальное соотношение. Скажем, не так давно 16-разрядные мини-ЭВМ имели систему команд, в которых пользователи-программисты могли адресовать до 216 = 64 Кбайт адресов (обычно в качестве адресуемой единицы выступала ячейка памяти размером с байт). А физически старшие модели этих мини-ЭВМ могли иметь объем оперативной памяти в несколько мегабайтов. Обращение к памяти столь большого объема осуществлялось с помощью специальных регистров, содержимое которых складывалось с адресом операнда (или команды), извлекаемым из поля операнда или указателя команды (и/или определяемым по значению поля операнда или указателя команды). Соответствующие значения в эти специальные регистры, выступающие как базовое смещение в памяти, заносила операционная система. Для одной задачи в регистр заносилось одно значение, а для второй (третьей, четвертой и т. д.) задачи, размещаемой одновременно с первой, но в другой области памяти, заносилось, соответственно, другое значение. Вся физическая память таким образом разбивалась на разделы объемом по 64 Кбайт, и на каждый такой раздел осуществлялось отображение своего виртуального адресного пространства.

Вторая ситуация (Vv = Vp) встречается очень часто, особенно характерна она была для недорогих вычислительных комплексов. Для этого случая имеется большое количество методов распределения оперативной памяти.

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

Простое непрерывное распределение и распределение с перекрытием

Общие принципы управления памятью в однопрограммных операционных системах

Простое непрерывное распределение — это самая простая схема, согласно которой вся память условно может быть разделена на три области:

  •  область, занимаемая операционной системой;
  •  область, в которой размещается исполняемая задача;
  •  незанятая ничем (свободная) область памяти.

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

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

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

Если есть необходимость создать программу, логическое адресное пространство которой должно быть больше, чем свободная область памяти, или даже больше, чем весь возможный объем оперативной памяти, то используется распределение с перекрытием — так называемые оверлейные структуры (от overlayперекрытие, расположение поверх чего-то). Этот метод распределения предполагает, что вся программа может быть разбита на части — сегменты. Каждая оверлейная программа имеет одну главную (main) часть и несколько сегментов (segments), причем в памяти машины одновременно могут находиться только ее главная часть и один или несколько не перекрывающихся сегментов.

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

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

Распределение оперативной памяти в MS DOS

Как известно, MS DOS1 — это однопрограммная операционная система для персонального компьютера типа IBM PC. В ней, конечно, можно организовать запуск резидентных, или TSR-задач2, в результате которого в памяти будет находиться не одна программа, но в целом система MS DOS предназначена для выполнения только одного вычислительного процесса. Поэтому распределение памяти в ней построено по схеме простого непрерывного распределения. Система поддерживает механизм распределения памяти с перекрытием (оверлейные структуры).

Как известно, в IBM PC использовался 16-разрядный микропроцессор 18088, который за счет введения сегментного способа адресации позволял указывать адрес ячейки памяти в пространстве объемом до 1 Мбайт. В последующих персональных компьютерах (IBM PC AT, AT386 и др.) было принято решение поддерживать совместимость с первыми, поэтому при работе в DOS прежде всего рассматривают первый мегабайт. Вся эта память разделялась на несколько областей, что иллюстрирует рис. 3.2. На этом рисунке показано, что памяти может быть и больше, чем 1 Мбайт, но более подробное рассмотрение этого вопроса мы здесь опустим, отослав желающих изучить данную тему глубже к монографии [2].

0000-003FF 1 Кбайт 

Таблица векторов прерываний 

00400-005FF 51 2 байт 

Глобальные переменные BIOS; глобальные переменные DOS 

В ранних версиях здесь располагались глобальные переменные интерпретатора Бейсик 

00600-ОАООО 35-60 Кбайт 

Модуль Ю. SYS; Модуль MSDOS. SYS: - обслуживающие функции; - буферы, рабочие и управляющие области; - устанавливаемые драйверы; Резидентная часть COMMAND. COM: - обработка программных прерываний; - системная программа загрузки; - программа загрузки транзитной части COMMAND. COM 

Размер этой области зависит от версии MSDOS и, главное, от конфигурационного файла CONFIG. SYS 

580 Кбайт 

Область памяти для выполнения программ пользователя и утилит MS DOS. В эту область попадают программы типа *.СОМ и *.ЕХЕ 

Объем этой области очень зависит от объема, занимаемого ядром ОС. Программа может перекрывать транзитную область COMMAND. COM 

Область расположения стека исполняющейся программы 

Стек «растет» снизу вверх 

18 Кбайт 

Транзитная часть командного процессора COMMAND. COM 

Собственно командный интерпретатор 

AOOOO-C7FFF 160 Кбайт 

Видеопамять. Область и размер используемого видеобуфера зависят от текущего режима 

При работе в текстовом режиме область памяти АОООО-ВОООО свободна и может быть использована в программе 

С8000-ЕОООО 96 Кбайт 

Зарезервировано для расширения BIOS 

FOOOO-FFFF 64 Кбайт 

Область ROM BIOS (System BIOS) 

Обычно объем этой области равен 32 Кбайт, но может достигать и 128 Кбайт, занимая младшие адреса 

Более 100000 

High Memory Area.

При наличии драйвера HIMEM. SYS здесь можно расположить основные системные файлы MS DOS, освобождая тем самым область основной памяти в первом мегабайте 

Может использоваться при наличии специальных драйверов. Используются спецификации XMS и EMS 

Если не вдаваться в детали, можно сказать, что в состав MS DOS входят следующие основные компоненты.

  •  Подсистема BIOS (Base Input-Output System — базовая подсистема ввода-вывода), включающая в себя помимо программы POST (Power On Self Test — самотестирование при включении компьютера)3 программные модули обработки прерываний, с помощью которых можно управлять основными контроллерами на материнской плате компьютера и устройствами ввода-вывода. Эти модули часто называют обработчиками прерываний. По своей функциональной сути они представляют собой драйверы. BIOS располагается в постоянном запоминающем устройстве компьютера. В конечном итоге почти все остальные модули MS DOS обращаются к BIOS. Если и не напрямую, то через модули более высокого уровня иерархии.
  •  Модуль расширения BIOS — файл IO.SYS (в других DOS-системах он может называться иначе, например _ВЮ.СОМ).
  •  Основной, или базовый, модуль обработки прерываний DOS — файл MSDOS.SYS. Именно этот модуль в основном реализует работу с файловой системой.
  •  Командный процессор (интерпретатор команд) — файл COMMAND.COM.
  •  Утилиты и драйверы, расширяющие возможности системы.
  •  Программа загрузки MS DOS — загрузочная запись (Boot Record, BR), расположенная на дискете или на жестком диске (подробнее о загрузочной записи и о других загрузчиках см. главу 6).

Вся память в соответствии с архитектурой IBM PC условно может быть разбита на следующие три части.

  •  В самых младших адресах памяти (первые 1024 ячейки) размещается таблица векторов прерывания (см. раздел «Система прерываний 32-разрядных микропроцессоров i80x86» в главе 4). Это связано с аппаратной реализацией процессора i8088. В последующих процессорах (начиная с i80286) адрес таблицы прерываний определяется через содержимое соответствующего регистра, но для обеспечения полной совместимости с первым процессором при включении или аппаратном сбросе в этот регистр заносятся нули. При желании, однако, в случае использования современных микропроцессоров i80x86 вектора прерываний можно размещать и в других областях.
  •  Вторая часть памяти отводится для программных модулей самой системы MS DOS и для программ пользователя. Эту область памяти мы рассмотрим чуть позже, здесь только заметим, что она называется основной, или стандартной, памятью (conventional memory).
  •  Наконец, третья часть адресного пространства отведена для постоянных запоминающих устройств и функционирования некоторых устройств ввода-вывода. Эта область памяти получила название UMA (Upper Memory Area — область памяти, адрес которой выше основной).

В младших адресах основной памяти размещается то, что можно условно назвать ядром этой операционной системы — системные переменные, основные программные модули, блоки данных для буферизации операций ввода-вывода. Для управления устройствами, драйверы которых не входят в базовую подсистему ввода-вывода, загружаются так называемые загружаемые, или устанавливаемые, драйверы. Перечень устанавливаемых драйверов определяется специальным конфигурационным файлом CONFIG.SYS. После загрузки расширения BIOS — файла IO.SYS -последний (загрузив модуль MSDOS.SYS) считывает файл CONFIG.SYS и уже в соответствии с ним подгружает в память необходимые драйверы. Кстати, в конфигурационном файле CONFIG.SYS могут иметься операторы, указывающие на количество буферов, отводимых для ускорения операций ввода-вывода, и на количество файлов, которые могут обрабатываться (для работы с файлами необходимо зарезервировать место в памяти для хранения управляющих структур, с помощью которых выполняются операции с записями файла). В случае использования микропроцессоров i80x86 и наличия в памяти драйвера HIMEM.SYS модули IO.SYS и MSDOS.SYS могут быть размещены за пределами первого мегабайта в области, которая получила название НМA (High Memory Area — область памяти с большими адресами).

Память с адресами, большими чем lOFFFFh, может быть использована в DOS-программах при выполнении их на микропроцессорах, имеющих такую возможность (например, микропроцессор i80286 имел 24-разрядную шину адреса, а i80386 -уже 32-разрядную). Но для этого с помощью специальных драйверов необходимо переключать процессор в другой режим работы, при котором он сможет использовать адреса выше lOFFFFh. Широкое распространение получили две основные спецификации: XMS (Extended Memory Specification) и EMS (Expanded Memory Specification). Последние годы система MS DOS практически перестала применяться. Теперь ее используют в основном для запуска некоторых утилит, с помощью которых подготавливают дисковые устройства, или для установки других операционных систем. И поскольку основным утилитам, необходимым для обслуживания персонального компьютера, спецификации EMS и XMS, как правило, не нужны, мы не будем здесь их рассматривать.

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

Для того чтобы предоставить больше памяти программам пользователя, в MS DOS применено то же решение, что и во многих других простейших операционных системах, — командный процессор COMMAND.COM состоит из двух частей. Первая часть является резидентной и размещается в области ядра, вторая часть транзитная и размещается в области старших адресов раздела памяти, выделяемой для программ пользователя. И если программа пользователя перекрывает собой область, в которой была расположена транзитная часть командного процессора, то последний при необходимости восстанавливает в памяти свою транзитную часть, поскольку после выполнения программы она возвращает управление резидентной части COMMAND.COM.

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

Распределение памяти статическими и динамическими разделами

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

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

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

Разделы с фиксированными границами

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

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

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

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

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

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

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

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

Разделы с подвижными границами

Чтобы избавиться от фрагментации, можно попробовать размещать в оперативной памяти задачи плотно, одну за другой, выделяя ровно столько памяти, сколько задача требует. Одной из первых операционных систем, в которой был реализован такой способ распределения памяти, была OS MVT5 (Multiprogramming with a Variable number of Tasks — мультипрограммирование с переменным числом задач). В этой операционной системе специальный планировщик (диспетчер памяти) ведет список адресов свободной оперативной памяти. При появлении новой задачи диспетчер памяти просматривает этот список и выделяет для задачи раздел, объем которой либо равен необходимому, либо чуть больше, если память выделяется не ячейками, а некими дискретными единицами. При этом модифицируется список свободных областей памяти. При освобождении раздела диспетчер памяти пытается объединить освобождающийся раздел с одним из свободных участков, если таковой является смежным.

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

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

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

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

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

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

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

Сегментная, страничная и сегментно-страничная организация памяти

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

Сегментный способ организации виртуальной памяти

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

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

Таким образом, виртуальный адрес для этого способа будет состоять из двух полей — номера сегмента и смещения относительно начала сегмента. Соответствующая иллюстрация приведена на рис. 3.4 для случая обращения к ячейке, виртуальный адрес которой равен сегменту с номером 11 со смещением от начала этого сегмента, равным 612. Как мы видим, операционная система разместила данный сегмент в памяти, начиная с ячейки с номером 19700.

Итак, каждый сегмент, размещаемый в памяти, имеет соответствующую информационную структуру, часто называемую дескриптором сегмента. Именно операционная система строит для каждого исполняемого процесса соответствующую таблицу дескрипторов сегментов, и при размещении каждого из сегментов в оперативной или внешней памяти отмечает в дескрипторе текущее местоположение сегмента. Если сегмент задачи в данный момент находится в оперативной памяти, то об этом делается пометка в дескрипторе. Как правило, для этого используется бит присутствия Р (от слова «present»). В этом случае в поле адреса диспетчер памяти записывает адрес физической памяти, с которого сегмент начинается, а в поле длины сегмента (limit) указывается количество адресуемых ячеек памяти. Это поле используется не только для того, чтобы размещать сегменты без наложения друг на друга, но и для того, чтобы контролировать, не обращается ли код исполняющейся задачи за пределы текущего сегмента. В случае превышения длины сегмента вследствие ошибок программирования мы можем говорить о нарушении адресации и с помощью введения специальных аппаратных средств генерировать сигналы прерывания, которые позволят фиксировать (обнаруживать) такого рода ошибки.

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

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

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

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

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

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

Для решения проблемы замещения (определения того сегмента, который должен быть либо перемещен во внешнюю память, либо просто замещен новым) используются следующие дисциплины6:

  •  правило FIFO (First In First Out — первый пришедший первым и выбывает);
  •  правило LRU (Least Recently Used — дольше других неиспользуемый);
  •  правило LFU (Least Frequently Used — реже других используемый);
  •  случайный (random) выбор сегмента.

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

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

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

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

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

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

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

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

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

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

Примером использования сегментного способа организации виртуальной памяти является операционная система OS/2 первого поколения7, которая была создана для персональных компьютеров на базе процессора i80286. В этой операционной системе в полной мере использованы аппаратные средства микропроцессора, который специально проектировался для поддержки сегментного способа распределения памяти.

OS/2 v.l поддерживала распределение памяти, при котором выделялись сегменты программы и сегменты данных. Система позволяла работать как с именованными, так и с неименованными сегментами. Имена разделяемых сегментов данных имели ту же форму, что и имена файлов. Процессы получали доступ к именованным разделяемым сегментам, используя их имена в специальных системных вызовах. Операционная система OS/2 v.l допускала разделение программных сегментов приложений и подсистем, а также глобальных сегментов данных подсистем. Вообще, вся концепция системы OS/2 была построена на понятии разделения памяти: процессы почти всегда разделяют сегменты с другими процессами. В этом состояло существенное отличие системы OS/2 от систем типа UNIX, которые обычно разделяют только реентерабельные программные модули между процессами.

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

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

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

Было организовано в OS/2 и динамическое присоединение обслуживающих программ. Программы OS/2 используют команды удаленного вызова. Ссылки, генерируемые этими вызовами, определяются в момент загрузки самой программы или ее сегментов. Такое отсроченное определение ссылок называется динамическим присоединением. Загрузочный формат модуля OS/2 представляет собой расширение формата загрузочного модуля DOS. Он был расширен, чтобы поддерживать необходимое окружение для свопинга сегментов с динамическим присоединением. Динамическое присоединение уменьшает объем памяти для программ в OS/2, одновременно делая возможными перемещения подсистем и обслуживающих программ без необходимости повторного редактирования адресных ссылок к прикладным программам.

Страничный способ организации виртуальной памяти

Как уже упоминалось, при страничном способе организации виртуальной памяти все фрагменты программы, на которые она разбивается (за исключением последней ее части), получаются одинаковыми. Одинаковыми полагаются и единицы памяти, которые предоставляются для размещения фрагментов программы. Эти одинаковые части называют страницами и говорят, что оперативная память разбивается на физические страницы, а программа — на виртуальные страницы. Часть виртуальных страниц задачи размещается в оперативной памяти, а часть — во внешней. Обычно место во внешней памяти, в качестве которой в абсолютном большинстве случаев выступают накопители на магнитных дисках (поскольку они относятся к быстродействующим устройствам с прямым доступом), называют файлом подкачки, или страничным файлом (paging file). Иногда этот файл называют swap-файлом, тем самым подчеркивая, что записи этого файла — страницы — замещают друг друга в оперативной памяти. В некоторых операционных системах выгруженные страницы располагаются не в файле, а в специальном разделе дискового пространства8.

Разбиение всей оперативной памяти на страницы одинаковой величины, причем кратной степени двойки, приводит к тому, что вместо одномерного адресного пространства памяти можно говорить о двухмерном. Первая координата адресного пространства — это номер страницы, вторая координата — номер ячейки внутри выбранной страницы (его называют индексом). Таким образом, физический адрес определяется парой (Рp, i), а виртуальный адрес — парой (Pv, i), где Pv — номер виртуальной страницы, Рр — номер физической страницы, i — индекс ячейки внутри страницы. Количество битов, отводимое под индекс, определяет размер страницы, а количество битов, отводимое под номер виртуальной страницы, — объем потенциально доступной для программы виртуальной памяти. Отображение, осуществляемое системой во время исполнения, сводится к отображению Pv в Рр и приписыванию к полученному значению битов адреса, задаваемых величиной i. При этом нет необходимости ограничивать число виртуальных страниц числом физических, то есть не поместившиеся страницы можно размещать во внешней памяти, которая в данном случае служит расширением оперативной.

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

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

  •  только чтение;
  •  чтение и запись;
  •  только выполнение.

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

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

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

Для использования дисциплин LRU и LFU в процессоре должны быть соответствующие аппаратные средства. В дескрипторе страницы размещается бит обращения (на рис. 3.5 подразумевается, что этот бит расположен в последнем поле), который становится единичным при обращении к дескриптору. 

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

Для абсолютного большинства современных операционных систем характерна дисциплина замещения страниц LRU как самая эффективная. Так, именно эта дисциплина используется в OS/2 и в Linux. Однако в операционных системах Windows NT/2000/XP разработчики, желая сделать их максимально независимыми от аппаратных возможностей процессора, отказались от этой дисциплины и применили правило FIFO. А для того чтобы хоть как-то компенсировать неэффективность правила FIFO, была введена «буферизация» тех страниц, которые должны быть записаны в файл подкачки на диск9 или просто расформированы. Принцип буферизации прост. Прежде чем замещаемая страница действительно окажется во внешней памяти или просто расформированной, она помечается как кандидат на выгрузку. Если в следующий раз произойдет обращение к странице, находящейся в таком «буфере», то страница никуда не выгружается и уходит в конец списка FIFO. В противном случае страница действительно выгружается, а на ее место в «буфер» попадает следующий «кандидат». Величина такого «буфера» не может быть большой, поэтому эффективность страничной реализации памяти в Windows NT/2000/XP намного ниже, чем в других операционных системах, и явление пробуксовки начинается даже при существенно большем объеме оперативной памяти.

В ряде операционных систем с пакетным режимом работы для борьбы с пробуксовкой используется метод «рабочего множества». Рабочее множество — это множество «активных» страниц задачи за некоторый интервал Т, то есть тех страниц, к которым было обращение за этот интервал времени. Реально количество активных страниц задачи (за интервал Т) все время изменяется, и это естественно, но, тем не менее, для каждой задачи можно определить среднее количество ее активных страниц. Это количество и есть рабочее множество задачи. Наблюдения за исполнением множества различных программ показали [11, 17, 22], что даже если интервал Т равен времени выполнения всей работы, то размер рабочего множества часто существенно меньше, чем общее число страниц программы. Таким образом, если операционная система может определить рабочие множества исполняющихся задач, то для предотвращения пробуксовки достаточно планировать на выполнение только такое количество задач, чтобы сумма их рабочих множеств не превышала возможности системы.

Как и в случае с сегментным способом организации виртуальной памяти, страничный механизм приводит к тому, что без специальных аппаратных средств он существенно замедляет работу вычислительной системы. Поэтому обычно используется кэширование страничных дескрипторов. Наиболее эффективным механизмом кэширования является ассоциативный кэш. Именно такой ассоциативный кэш и создан в 32-разрядных микропроцессорах i80x86. Начиная с i80386, который поддерживает страничный способ распределения памяти, в этих микропроцессорах имеется кэш на 32 страничных дескриптора. Поскольку размер страницы в этих микропроцессорах равен 4 Кбайт, возможно быстрое обращение к памяти размером 128 Кбайт.

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

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

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

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

Сегментно-страничный способ организации виртуальной памяти

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

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

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

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

Особенности архитектуры

микропроцессоров i80x86 для организации мультипрограммных операционных систем

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

Реальный и защищенный режимы работы процессора

Широко известно, что первым микропроцессором, на базе которого был создан персональный компьютер IBM PC, был Intel 8088. Этот микропроцессор отличался от первого 16-разрядного микропроцессора фирмы Intel (микропроцессора 8086), прежде всего, тем, что у него была 8-разрядная шина данных, а не 16-разрядная (как у 8086). Оба этих микропроцессора предназначались для создания вы- числительных устройств, работающих в однозадачном режиме, то есть специальных аппаратных средств для поддержки надежных и эффективных мультипрограммных операционных систем в них не было.

Однако к тому времени, когда разработчики осознали необходимость включения специальной аппаратной поддержки мультипрограммных вычислений, уже было создано очень много программных продуктов. Поэтому для совместимости с первыми компьютерами в последующих версиях микропроцессоров была реализована возможность использовать их в двух режимах: реальном (real mode) — так назвали режим работы первых 16-разрядных микропроцессоров — и защищенном (protected mode), означающем, что параллельные вычисления могут быть защищены аппаратно-программными механизмами.

Подробно рассматривать архитектуру первых 16-разрядных микропроцессоров i8086/i8088 мы не будем, поскольку этот материал должен изучаться в других дисциплинах. Итак, мы исходим из того, что читатель знаком с архитектурой процессора i8086/i8088 и с программированием на ассемблере для этих 16-разрядных процессоров Intel. Для тех же, кто с ней незнаком, можно рекомендовать, например, такие книги, как [12, 24, 40] и многие другие. Однако мы напомним, что в этих микропроцессорах (а значит, и в остальных микропроцессорах семейства i80x86 при работе их в реальном режиме) обращение к памяти с возможным адресным пространством в 1 Мбайт осуществляется посредством механизма сегментной адресации (рис. 4.1). Этот механизм был использован для того, чтобы увеличить с 16 до 20 количество разрядов, участвующих в формировании адреса ячейки памяти, по которому идет обращение, и тем самым увеличить доступный объем памяти.

Для конкретности будем рассматривать определение адреса команд, хотя для адресации операндов используется аналогичный механизм, только участвуют в этом случае другие сегментные регистры. Напомним, что для определения физического адреса команды содержимое регистра сегмента кода (Code Segment, CS) умножается на 16 за счет добавления справа (к младшим битам) четырех нулей, после чего к полученному значению прибавляется содержимое регистра указателя ко- манд (Instruction Pointer, IP). Получается 20-разрядное значение1, которое и позволяет указать любой байт из 2020.

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

Для изучения этих возможностей рассмотрим сначала новые архитектурные возможности микропроцессоров i80x86.

Новые системные регистры микропроцессоров i80x86

Основные регистры микропроцессора i80x86, знание которых необходимо для понимания защищенного режима работы, приведены на рис. 4.2. На этом рисунке следует обратить внимание на следующее:

  •  указатель команды (EIP) — это 32-разрядный регистр, младшие 16 разрядов которого представляют регистр IP;
  •  регистр флагов (EFLAGS) — это 32-разрядный регистр, младшие 16 разрядов которого представляют регистр FLAGS;
  •  регистры общего назначения ЕАХ, ЕВХ, ЕСХ, EDX, а также регистры ESP, EBP, ESI, EDI 32-разрядные, однако их младшие 16 разрядов представляют собой известные регистры АХ, ВХ, CX,DX, SP, BP, SI, DI;
  •  сегментные регистры CS, SS, DS, ES, FS, GS 16-разрядные, при каждом из них пунктиром изображены скрытые от программистов (недоступные никому, кроме собственно микропроцессора) 64-разрядные регистры, в которые загружаются дескрипторы соответствующих сегментов;
  •  при 16-разрядном регистре-указателе на локальную таблицу дескрипторов (Local Descriptor Table Register, LDTR) также имеется «теневой» (скрытый от программиста) 64-разрядный регистр, в который микропроцессор заносит дескриптор, указывающий на таблицу дескрипторов сегментов задачи, описывающих ее локальное виртуальное адресное пространство;
  •  16-разрядный регистр задачи (Task Register, TR) указывает на дескриптор в глобальной таблице дескрипторов, который позволяет получить доступ к дескриптору сегмента состояния задачи (Task State Segment, TSS) — информационной структуре, которую поддерживает микропроцессор для управления задачами;
  •  48-разрядный регистр GDTR (Global Descriptor Table Register) глобальной таблицы дескрипторов (Global Descriptor Table, GDT) содержит как дескрипторы общих сегментов, так и специальные системные дескрипторы, в частности, в GDT находятся дескрипторы, с помощью которых можно получить доступ к сегментам TSS;
  •  48-разрядный регистр таблицы дескрипторов прерываний (IDTR) содержит информацию, необходимую для доступа к таблице прерываний (IDT);
  •  32-разрядные регистры CRO-CR3 являются управляющими.

Помимо перечисленных имеются и некоторые другие регистры.

Управляющий регистр CRO содержит целый ряд флагов, которые определяют режимы работы микропроцессора. Подробности об этих флагах можно найти, например, в [1, 8, 20]. Мы же просто ограничимся тем фактом, что самый младший бит РЕ (Protect Enable) этого регистра определяет режим работы процессора. При РЕ = 0 процессор функционирует в реальном режиме работы, а при единичном значении микропроцессор переключается в защищенный режим. Самый старший бит регистра CRO — бит PG (PaGing) — определяет, включен (PG =1) или нет (PG = 0) режим страничного преобразования адресов.

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

Регистр CR3 содержит номер физической страницы, в которой располагается таблица каталога таблиц страниц текущей задачи. Очевидно, что, приписав к этому номеру нули, мы попадем на начало этой страницы.

Адресация в 32-разрядных микропроцессорах i80x86 при работе в защищенном режиме

Поддержка сегментного способа организации виртуальной памяти

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

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

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

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

Локальное адресное пространство задачи определяется через таблицу LOT (Local Descriptor Table). У каждой задачи может быть свое локальное адресное пространство. Общее, или глобальное, адресное пространство определяется через таблицу GDT (Global Descriptor Table). Само собой, что работу с этими таблицами (их заполнение и последующую модификацию) должна осуществлять операционная система. Доступ к таблицам LDT и GDT со стороны прикладных задач должен быть исключен.

При переключении микропроцессора в защищенный режим он начинает совершенно другим образом, чем в реальном режиме, вычислять физические адреса команд и операндов. Прежде всего, содержимое сегментных регистров начинает интерпретироваться иначе: считается, что там содержится не адрес начала, а номер соответствующего сегмента. Для того чтобы подчеркнуть этот факт, сегментные регистры CS, SS, DS, ES, FS, GS начинают даже называть иначе — селекторами сегментов. При этом каждый селекторный регистр разбивается на три поля (рис. 4.4).

  •  Поле индекса (Index) — старшие 13 битов (3-15) определяет собственно номер сегмента (его индекс в соответствующей таблице дескрипторов).
  •  Поле индикатора таблицы сегментов (Table Index, TI) — бит с номером 2 определяет часть виртуального адресного пространства (общее или принадлежащее только данной задаче). Если TI = 0, то поле индекса указывает на элемент в глобальной таблице дескрипторов (GDT), то есть идет обращение к общей памяти. Если TI = 1, то идет обращение к локальной области памяти текущей задачи; это пространство описывается локальной таблицей дескрипторов (LDT).
  •  Поле уровня привилегий идентифицирует запрашиваемый уровень привилегий (Requested Privilege Level, RPL).

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

Для манипулирования задачами операционные системы поддерживают информационную структуру, которую мы уже раньше называли как дескриптор задачи (см. главу 1). Микропроцессоры с архитектурой IA32 поддерживают работу с наиболее важной частью дескриптора задачи, которая меньше всего зависит от операционной системы. Эта инвариантная часть дескриптора, с которой и работает микропроцессор, названа сегментом состояния задачи (Task State Segment, TSS). Перечень полей TSS показан на рис. 4.5. Видно, что этот сегмент содержит в основном контекст задачи. Процессор получает доступ к этой структуре с помощью регистра задачи (Task Register, TR).

Регистр TR содержит индекс (селектор) элемента в GDT. Этот элемент представляет собой дескриптор сегмента TSS. Дескриптор заносится в теневую часть регистра (см. рис. 4.2). К рассмотрению TSS мы еще вернемся, а сейчас заметим, что в одном из полей TSS содержится указатель (селектор) на локальную таблицу дескрипторов данной задачи. При переходе процессора с одной задачи на другую содержимое поля LDTR заносится микропроцессором в одноименный регистр. Инициализировать регистр TR можно и явным образом.

Итак, регистр LDTR содержит селектор, указывающий на один из дескрипторов таблицы GDT. Этот дескриптор заносится микропроцессором в теневую часть регистра LDTR и описывает таблицу LDT для текущей задачи. Теперь, когда у нас определены как глобальная, так и локальная таблица дескрипторов, можно рассмотреть процесс определения линейного адреса3. Для примера рассмотрим процесс получения адреса команды. Адреса операндов определяются по аналогии, но задействованы будут другие регистры.

Микропроцессор анализирует бит TI селектора кода и, в зависимости от его значения, извлекает из таблицы GDT или LDT дескриптор сегмента кода с номером (индексом), который равен полю индекса (биты 3-15 селектора на рис. 4.4). Этот дескриптор заносится в теневую (скрытую) часть регистра CS. Далее микропроцессор сравнивает значение регистра EIP (Extended Instruction Pointer — расширенный указатель команды) с полем размера сегмента, содержащегося в извлеченном дескрипторе, и если смещение относительно начала сегмента не превышает размера предела, то значение EIP прибавляется к значению поля начала сегмента, и мы получаем искомый линейный адрес команды. Линейный адрес — это одна из форм виртуального адреса. Исходный двоичный виртуальный адрес, вычисляемый в соответствии с используемой схемой адресации, преобразуется в линейный. В свою очередь, линейный адрес будет либо равен физическому (если страничное преобразование отключено), либо путем страничной трансляции преобразуется в физический адрес. Если же смещение из регистра EIP превышает размер сегмента кода, то эта аварийная ситуация вызывает прерывание, и управление должно передаваться супервизору операционной системы.

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

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

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

При создании микропроцессора i80386 разработчики столкнулись с очень серьезной проблемой в реализации страничного механизма. Дело в том, что микропроцессор имел широкую шину адреса (32 бит), и возник вопрос о разбиении всего адреса на поле страницы и поле индекса. Если большое количество битов адреса отвести под индекс, то страницы станут очень большими, что повлечет значительные потери и на фрагментацию, и на операции ввода-вывода, связанные с замещением страниц. Хотя количество страниц стало бы при этом меньше, и накладные расходы на их поддержание тоже уменьшились бы. Если же размер страницы уменьшить, то большое поле номера страницы привело бы к потенциально громадному количеству страниц, и пришлось бы либо вводить какие-то механизмы контроля за номерами страниц (с тем, чтобы они не выходили за размеры таблицы страниц), либо создавать эти таблицы максимального размера. Разработчики пошли по пути, при котором размер страницы выбран небольшим (212 = 4096 = 4 Кбайт), а поле номера страницы величиной в 20 бит, в свою очередь, разбивается на два поля и осуществляется двухэтапная страничная трансляция.

Для описания каждой страницы создается соответствующий дескриптор. Длина дескриптора выбрана равной 32 бит: 20 бит линейного адреса определяют номер страницы (по существу — ее адрес, поскольку добавление к нему 12 нулей приводит к определению начального адреса страницы), а остальные биты разбиты на поля, показанные на рис. 4.7. Как видно, три бита дескриптора зарезервировано для использования системными программистами при разработке подсистемы организации виртуальной памяти. С этими битами микропроцессор сам не работает. 

Прежде всего, микропроцессор анализирует самый младший бит дескриптора — бит присутствия, если он равен нулю, то это означает отсутствие данной страницы в оперативной памяти, и такая ситуация влечет прерывание в работе процессора с передачей управления на соответствующую программу, которая должна будет загрузить затребованную страницу. Бит, называемый «грязным» (dirty), показывает, что данную страницу модифицировали, и при замещении этого страничного кадра следующим ее необходимо сохранить во внешней памяти. Бит обращения (access) свидетельствует о том, что к данной таблице или странице осуществлялся доступ. Он анализируется для определения страницы, которая будет участвовать в замещении при использовании дисциплины LRU или LFU. Наконец, первый и второй биты требуются для защиты памяти.

Старшие 10 бит линейного адреса определяют номер таблицы страниц (Page Table Entry, РТЕ), из которой посредством вторых 10 бит линейного адреса выбирается соответствующий дескриптор виртуальной страницы. И уже из этого дескриптора выбирается номер физической страницы, если данная виртуальная страница отображена на оперативную память. Эта схема определения физического адреса из линейного изображена на рис. 4.8.

Первая таблица, которую мы индексируем первыми (старшими) десятью битами линейного адреса, названа таблицей каталога таблиц страниц (Page Directory Entry, PDE). Ее адрес в оперативной памяти определяется старшими двадцатью битами управляющего регистра CRO.

Каждая из таблиц (PDE и РТЕ) состоит из 1024 элементов (2'°= 1024). В свою очередь, каждый элемент (дескриптор страницы) имеет длину 4 байт (32 бит), поэтому размер этих таблиц как раз соответствует размеру страницы. Оценим теперь эту схему трансляции с позиций расхода памяти. Каждый дескриптор описывает страницу размером 4 Кбайт. Следовательно, одна таблица страниц, содержащая 1024 дескриптора, описывает пространство памяти в 4 Мбайт. Если задача пользуется виртуальным адресным пространством, например, в 55 Мбайт (предположим, что речь идет о некотором графическом редакторе, который обрабатывает изображение, состоящее из большого количества пикселов4), то для описания этой памяти необходимо иметь 14 страниц (14 х 4 Мбайт = 56 Мбайт), содержащих таблицы РТЕ. Кроме того, нам потребуется для этой задачи еще одна таблица PDE (тоже размером в одну страницу), в которой 14 дескрипторов будут указывать на местонахождение упомянутых таблиц РТЕ. Остальные дескрипторы PDE не требуются. Итого, для описания 55 Мбайт адресного пространства задачи потребуется всего 15 страниц, то есть 60 Кбайт памяти, что можно считать приемлемым.

Если бы не был использован такой двухэтапный механизм трансляции, то потери памяти на описание адресного пространства могли бы составить 4 Кбайт х 210 = 4 Мбайт! Очевидно, что это уже неприемлемое решение.

Итак, микропроцессор для каждой задачи, для которой у него есть TSS, позволяет иметь таблицу PDE и некоторое количество таблиц РТЕ. Поскольку это дает возможность адресоваться к любому байту из 232, а шина адреса как раз и позволяет использовать физическую память с таким объемом, то можно как бы отказаться от сегментного способа адресации. Другими словами, если считать, что задача состоит из одного единственного сегмента кода и одного сегмента данных, которые, в свою очередь, разбиты на страницы, то фактически мы получаем только один страничный механизм работы с виртуальной памятью. Этот подход получил название плоской модели памяти. При использовании плоской модели памяти упрощается создание и операционных систем, и систем программирования, кроме того, уменьшаются расходы памяти на поддержку системных информационных структур. Поэтому в абсолютном большинстве современных 32-разрядных операционных систем, создаваемых для микропроцессоров i80x86, используется плоская модель памяти. Более того, появление новых 64-разрядных микропроцессоров во многом определено желанием получить большее адресное пространство, чем его имеют 32-разрядные процессоры, при сохранении возможности работать только с плоской моделью памяти.

Режим виртуальных машин для исполнения приложений реального режима

Разработчики рассматриваемого семейства микропроцессоров в своем стремлении обеспечить максимально возможную совместимость архитектуры пошли не только на то, чтобы за счет введения реального режима работы обеспечить возможность программам, созданным для первых 16-разрядных персональных компьютеров, без проблем выполняться на компьютерах с более поздними моделями микропроцессоров. Они обеспечили возможность выполнения 16-разрядных приложений реального режима при условии, что сам процессор функционирует в защищенном режиме работы, и операционная система, используя соответствующие аппаратные средства микропроцессора, организует мультипрограммный (мультизадачный) режим. Другими словами, микропроцессоры i80x86 поддерживают возможность создания операционных сред реального режима при работе микропроцессора в защищенном режиме. Если условно назвать 16-разрядные приложения DOS-приложениями (поскольку в абсолютном большинстве случаев это именно так), то можно сказать, что введена поддержка виртуальных DOS-машин, работающих вместе с обычными 32-разрядными приложениями защищенного режима. Это нашло отражение в названии такого режима работы микропроцессоров i80x86 (его называют режимом виртуального процессора i8086, иногда для краткости —режимом V86, или просто виртуальным режимом), когда в защищенном режиме работы может исполняться код DOS-приложения. Мультизадачное^ при выполнении нескольких программ реального режима поддерживается аппаратными средствами защищенного режима. Переход в виртуальный режим осуществляется посредством изменения бита VM (Virtual Mode) в регистре EFLAGS. Когда процессор находится в виртуальном режиме, для адресации памяти используется схема реального режима работы (сегмент плюс смещение) с размером сегментов до 64 Кбайт, которые могут располагаться в адресном пространстве размером в 1 Мбайт, однако полученные адреса считаются не физическими, а линейными. В результате страничной трансляции осуществляется отображение виртуального адресного пространства 16-разрядного приложения на физическое адресное пространство. Это позволяет организовать параллельное выполнение нескольких задач, разработанных для реального режима, да еще совместно с обычными 32-разрядными приложениями, требующими защищенного режима работы.

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

Вопрос, связанный с операциями ввода-вывода, которые недоступны для обычных приложений (см. следующий раздел), решается аналогично. При попытке выполнить недопустимые команды (ввода-вывода) возникают прерывания, и необходимые операции выполняются операционной системой, хотя задача об этом и «не подозревает». При выполнении команд IN, OUT, INS, OUTS, CLI, STI процессор, находящийся в виртуальном режиме и исполняющий код на уровне привилегий третьего (самого нижнего) кольца защиты, за счет возникающих вследствие этого прерываний переводится на выполнение высоко привилегированного кода операционной системы.

Таким образом, операционная система может полностью виртуализировать аппаратные5 и программные ресурсы компьютера, создавая полноценную операционную среду, отличную от себя самой, ибо существуют так называемые нативные приложения, создаваемые по собственным спецификациям данной операционной системы. Очень важным моментом для организации полноценной виртуальной машины является виртуализация не только программных, но и аппаратных ресурсов. Так, например, в Windows NT эта задача выполнена явно неудачно, тогда как в OS/2 имеется полноценная виртуальная машина как для DOS-приложений, так и для приложений, работающих в среде спецификаций Win 16. Правда, в последнее время это перестало быть актуальным, поскольку появилось большое количество приложений, работающих по спецификациям Win32 API.

Защита адресного пространства задач

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

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

Уровни привилегий для защиты адресного пространства задач

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

В микропроцессорах i80x86 режим супервизора и режим пользователя непосредственно связаны с так называемыми уровнями привилегий, причем имеется не два, а четыре уровня привилегий. Для указания уровня привилегий используются два бита, поэтому код 0 обозначает самый высший уровень, а код 3 — самый низший. Самый высший уровень привилегий предназначен для операционной системы (прежде всего для ядра ОС), самый низший — для прикладных задач пользователя. Промежуточные уровни привилегий введены для большей свободы системных программистов в организации надежных вычислений при создании операционной системы и иного системного программного обеспечения. Предполагалось, что уровень с номером (кодом) 1 может быть использован, например, для системного сервиса — программ обслуживания аппаратуры, драйверов, работающих с портами ввода-вывода. Уровень привилегий с кодом 2 может быть использован для создания пользовательских интерфейсов, систем управления базами данных и прочими, то есть для реализации специальных системных функций, которые по отношению к супервизору операционной системы ведут себя как обычные приложения. Так, например, в системе OS/2 доступны три уровня привилегий: с нулевым уровнем привилегий исполняется код супервизорной части операционной системы, на втором уровне исполняются системные процедуры подсистемы ввода-вывода, на третьем уровне исполняются прикладные задачи пользователей. Однако на практике чаще всего задействуются только два уровня — нулевой и третий. Таким образом, упомянутый режим супервизора для микропроцессоров i80x86 соответствует выполнению кода с уровнем привилегий 0, обозначаемый как PLO (Privilege Level 0 — уровень привилегий 0). Подводя итог, можно констатировать, что именно уровень привилегий задач определяет, какие команды в них можно использовать и какое подмножество сегментов и/или страниц в их адресном пространстве они могут обрабатывать.

Основными системными объектами, которыми манипулирует процессор при работе в защищенном режиме, являются дескрипторы. Именно дескрипторы сегментов содержат информацию об уровне привилегий соответствующего сегмента кода или данных. Уровень привилегий исполняющейся задачи определяется значением поля привилегий, находящегося в дескрипторе ее текущего кодового сегмента. Напомним (см. рис. 4.3), что в байте прав доступа каждого дескриптора сегмента имеется поле DPL (Descriptor Privilege Level — уровень привилегий сегмента, определяемый его дескриптором), которое и определяет уровень привилегий связанного с ним сегмента. Таким образом, поле DPL текущего сегмента кода становится полем текущего уровня привилегий (Current Privilege Level, CPL), или уровня привилегий задачи. При обращении к какому-нибудь сегменту в соответствующем селекторе указывается (см. рис. 4.4) запрашиваемый уровень привилегий (Requested Privilege Level, RPL)6.

В пределах одной задачи используются сегменты с различными уровнями привилегий, и в определенные моменты времени выполняются или обрабатываются сегменты с соответствующими им уровнями привилегий. Механизм проверки привилегий работает в ситуациях, которые можно назвать межсегментными переходами (обращениями). К этим ситуациям относятся доступ к сегменту данных или стековому сегменту, межсегментные передачи управления в случае прерываний (и особых ситуаций), использование команд CALL, JMP, INT, IRET, RET. В таких межсегментных обращениях участвуют два сегмента: целевой сегмент (к которому мы обращаемся) и текущий сегмент кода, из которого идет обращение.

Процессор сравнивает упомянутые значения CPL, RPL, DPL и на основе понятия эффективного уровня привилегий (Effective Privilege Level, EPL)7 ограничивает возможности доступа к сегментам по следующим правилам, в зависимости от того, идет ли речь об обращении к коду или к данным.

При доступе к сегментам данных проверяется условие CPL < EPL. Нарушение этого условия вызывает так называемую особую ситуацию ошибки защиты, ведущую к прерыванию. Уровень привилегий сегмента данных, к которому осуществляется обращение, должен быть таким же, как и текущий уровень, или меньше его. Обращение к сегменту с более высоким уровнем привилегий воспринимается как ошибка, так как существует опасность изменения данных с высоким уровнем привилегий программой с низким уровнем привилегий. Доступ к данным с меньшим уровнем привилегий разрешается.

Если целевой сегмент является сегментом стека, то правило проверки имеет вид:

CPL = DPL = RPL

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

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

Механизм шлюзов для передачи управления на сегменты кода с другими уровнями привилегий

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

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

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

В этом дескрипторе вместо адреса сегмента указываются селектор, позволяющий найти дескриптор искомого сегмента кода, и адрес (смещение назначения), с которого будет выполняться подчиненный сегмент, то есть полный 32-разрядный адрес. Формат дескриптора шлюза приведен на рис. 4.11. Адресовать шлюз вызова можно с помощью команды CALL или FAR CALL (межсегментный вызов процедуры). По существу, дескрипторы шлюзов вызова не являются дескрипторами сегментов, но могут располагаться среди обычных дескрипторов (в дескриптор-ных таблицах) процесса. Смещение, указываемое в команде перехода на другой сегмент (FAR CALL), игнорируется, и фактически осуществляется переход на команду, адрес которой определяется через смещение из шлюза вызова. Этим гарантируется попадание только на разрешенные точки входа в подчиненные сегменты. 

Введены следующие правила использования шлюзов:

  •  значение DPL шлюза вызова должно быть больше или равно значению текущего уровня привилегий С PL;
  •  значение DPL шлюза вызова должно быть больше или равно значению поля RPL селектора шлюза;
  •  значение DPL шлюза вызова должно быть больше или равно значению DPL целевого сегмента кода;
  •  значение DPL целевого сегмента кода должно быть меньше или равно значению текущего уровня привилегий CPL

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

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

Изложенный вкратце аппаратный механизм защиты по привилегиям оказывается довольно сложным и жестким. Однако поскольку все практические ситуации учесть в схемах микропроцессора невозможно, то при разработке процедур операционных систем и иного привилегированного кода следует придерживаться приведенных ниже рекомендаций, заимствованных из [8].

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

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

  •  Следует проверять счетчики циклов и повторений на минимальные и максимальные значения.
  •  Необходимо проверить 8- и 16-разрядные параметры, передаваемые в 32-разрядных регистрах. Когда процедуре передается короткий параметр, его следует расширить знаковым разрядом или нулем для заполнения всего 32-разрядного регистра.
  •  Следует стремиться свести к минимуму время работы процессора с запрещенными прерываниями. Если процедуре требуется запрещать прерывания, необходимо, чтобы вызывающая программа не могла влиять на время нахождения процессора с запрещенными прерываниями (флаг IF = 0).
  •  Процедура никогда не должна воспринимать как параметр код или указатель на код.
  •  В операциях процессора следует явно задавать состояние флага направления DF для цепочечных команд.
  •  Заключительная команда RET или RET n в процедуре должна точно соответствовать полю WC (Word Counter — счетчик слов) шлюза вызова; при этом n = 4 х WC, так как счетчик задает число двойных слов, а п соответствует байтам.
  •  Не следует применять шлюзы вызовов для функций, которым передается переменное число параметров (см. предыдущую рекомендацию). При необходимости нужно воспользоваться счетчиком и указателем параметров.
  •  Функции не могут возвращать значения в стеке (см. предыдущую рекомендацию), так как после возврата стеки процедуры и вызывающей программы находятся точно в таком состоянии, в каком они были до вызова.
  •  В процедуре следует сохранять и восстанавливать все сегментные регистры. Без этого, если какой-либо сегментный регистр привлекался для адресации данных, недоступных вызывающей программе, процессор автоматически загрузит в него пустой селектор. Рекомендуется контролировать все обращения к памяти.

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

Система прерываний 32-разрядных микропроцессоров i80x86

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

Работа системы прерываний в реальном режиме

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

Итак, каждый вектор прерывания состоит из четырех байтов, или двух слов: первые два содержат новое значение для регистра IP, а следующие два — новое значение для регистра CS. Таблица векторов прерывания занимает 1024 байт. Таким образом, в ней может быть задано 256 векторов прерываний. В процессоре i8086 эта таблица располагается на адресах OOOOOH-003FFH. Расположение этой таблицы в процессорах i80286 и в более поздних определяется значением регистра IDTR (Interrupt Descriptor Table Register — регистр таблицы дескрипторов прерываний). При включении или сбросе процессора i80x86 этот регистр обнуляется. Однако при необходимости можно в регистре IDTR указать смещение и таким образом перейти на новую таблицу векторов прерываний.

Таблица векторов прерываний заполняется (инициализируется) при запуске системы, но, в принципе, может быть изменена или перемещена.

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

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

В IBM PC, как и в других вычислительных системах, прерывания бывают двух видов: внутренние и внешние.

Внутренние прерывания, как мы уже знаем, возникают в результате работы процессора в ситуациях, которые нуждаются в специальном обслуживании, или при выполнении специальных команд (INT, INTO). Это следующие прерывания:

  •  прерывание при делении на ноль (номер прерывания 0);
  •  прерывание по флагу TF (Trap Flag — флаг трассировки)9 обычно используется специальными программами отладки типа DEBUG (номер прерывания 1);
  •  прерывания, возникающие при выполнении команд INT (Interrupt — прерывание) и INTO (Interrupt if Overflow — прерывание по переполнению), называются программными.

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

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

Маскируемые прерывания генерируются контроллером прерываний по заявке определенных периферийных устройств10. Контроллер прерываний (его обозначение 18259А) поддерживает восемь уровней (линий) приоритета; к каждому уровню «привязано» одно периферийное устройство11. Маскируемые прерывания часто называют аппаратными прерываниями.

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

  1.  В стек помещается регистр флагов PSW.
  2.  Флаг включения-выключения прерываний IF и флаг трассировки TF, находящиеся в регистре PSW, обнуляются для блокировки других маскируемых прерываний и исключения пошагового режима исполнения команд.
  3.  Значения регистров CS и IP сохраняются в стеке вслед за PSW.
  4.  Вычисляется адрес вектора прерывания и из вектора, соответствующего номеру прерывания, загружаются новые значения IP и CS.

Когда системная подпрограмма принимает управление, она может разрешить снова маскируемые прерывания командой STI (Set Interrupt Flag — установить флаг прерываний), которая переводит флаг IF в состояние 1, что разрешает микропроцессору вновь реагировать на прерывания, инициируемые внешними устройствами, поскольку стековая организация допускает вложение прерываний друг в друга.

Закончив работу, подпрограмма обработки прерывания должна выполнить команду IRET (Interrupt Return), которая извлекает из стека три 16-разрядных значения и загружает их в указатель команд IP, регистр сегмента команд CS и регистр PSW соответственно. Таким образом, процессор сможет продолжить работу с того места, где он был прерван.

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

  1.  Контроллер прерываний получает заявку от определенного периферийного устройства и, соблюдая схему приоритетов, генерирует сигнал INTR (запрос на прерывание), который является входным для микропроцессора.
  2.  Микропроцессор проверяет флаг IF в регистре PSW. Если он установлен в 1, то переходим к шагу 3. В противном случае работа процессора не прерывается. Часто говорят, что прерывания замаскированы, хотя правильнее говорить, что они отключены. Маскируются (запрещаются) отдельные линии запроса на прерывания посредством программирования контроллера прерываний.
  3.  Микропроцессор генерирует сигнал INTA (подтверждение прерывания). В ответ на этот сигнал контроллер прерываний посылает по шипе данных номер прерывания. После этого выполняется описанная ранее процедура передачи управления соответствующей программе обработки прерывания.

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

Работа системы прерываний в защищенном режиме

В защищенном режиме работы система прерываний микропроцессора i80x86 работает совершенно иначе. Прежде всего, вместо таблицы векторов, о которой мы говорили выше, она имеет дело с таблицей дескрипторов прерываний (Interrupt Descriptor Table, IDT). Дело здесь не столько в названии таблицы, сколько в том, что таблица IDT представляет собой не таблицу с адресами обработчиков прерываний, а таблицу со специальными системными структурами данных (дескрипторами), доступ к которой со стороны пользовательских (прикладных) программ невозможен. Только сам микропроцессор (его система прерываний) и код операционной системы могут получить доступ к этой таблице, представляющей собой специальный сегмент, адрес и длина которого содержатся в регистре IDTR (см. рис. 4.2). Этот регистр аналогичен регистру GDTR в том отношении, что он инициализируется один раз при загрузке системы. Интересно заметить, что в реальном режиме работы регистр IDTR также указывает на адрес таблицы прерываний, но при этом, как и в процессоре i8086, каждый элемент таблицы прерываний (вектор) занимает всего 4 байт и содержит 32-разрядный адрес в формате селектор-.смещение (CS:IP). Начальное значение этого регистра равно нулю, но в него можно занести и другое значение. В этом случае таблица векторов прерываний будет находиться в другом месте оперативной памяти. Естественно, что перед тем, как занести в регистр IDTR новое значение, необходимо подготовить саму таблицу векторов. В защищенном режиме работы загрузку регистра IDTR может произвести только код с максимальным уровнем привилегий.

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

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

Дескриптор прерываний может относиться к одному из трех типов:

  •  коммутатор прерывания (interrupt gate);
  •  коммутатор перехвата (trap gate);
  •  коммутатор задачи (task gate).

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

Обработка прерываний в контексте текущей задачи

Обработку прерывания в контексте текущей задачи поясняет рис. 4.12.

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

  1.  В стек на уровне привилегий текущего сегмента кода помещаются:
    - значения
    SS и SP, если уровень привилегий в коммутаторе выше уровня привилегий ранее исполнявшегося кода;
    - регистр флагов
    EFLAGS;
    - регистры
    CS и IP.
  2.  Если рассматриваемому прерыванию соответствовал коммутатор прерывания, то запрещаются прерывания (устанавливается флаг IF = 0 в регистре EFLAGS). В случае коммутатора перехвата флаг прерываний не сбрасывается, и обработка новых прерываний на период обработки текущего прерывания тем самым не запрещается. 
  3.  Поле селектора из дескриптора прерывания используется для индексирования таблицы дескрипторов задачи. Дескриптор сегмента заносится в теневой регистр, а смещение относительно начала нового сегмента кода определяется полем смещения из дескриптора прерывания.

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

Обработка прерываний с переключением на новую задачу

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

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

  1.  Сохраняются все рабочие регистры процессора в текущем сегменте TSS, базовый адрес этого сегмента берется в регистре TR (см. раздел «Адресация в 32-разрядных микропроцессорах i80x86 при работе в защищенном режиме»).
  2.  Текущая задача отмечается как занятая.
  3.  По селектору из коммутатора задачи выбирается новый сегмент TSS (поле селектора помещается в регистр TR) и загружается состояние новой задачи. Напомним, что загружаются значения регистров LDTR, EFLAGS, восьми регистров общего назначения, регистра EIP и шести сегментных регистров.
  4.  Устанавливается бит NT (Next Task).
  5.  В поле обратной связи TSS помещается селектор прерванной задачи.
  6.  С помощью значений CS.iP, взятых из нового сегмента TSS, обнаруживается и выполняется первая команда обработчика прерывания.

Таким образом, коммутатор задачи дает указание процессору произвести переключение задачи, и обработка прерывания осуществляется под контролем отдельной внешней задачи. В каждом сегменте TSS имеется селектор локальной таблицы деск- рипторов (LDT), поэтому при переключении задачи процессор загружает в регистр LDTR новое значение. Это позволяет обратиться к сегментам кода, которые абсолютно не пересекаются с сегментами кода любых других задач, поскольку именно локальные таблицы дескрипторов обеспечивают эффективную изоляцию виртуальных адресных пространств. Новая задача начинает свое выполнение на уровне привилегий, определяемом полем RPL нового содержимого регистра CS, которое загружается из сегмента TSS. Достоинством этого коммутатора является то, что он позволяет сохранить все регистры процессора с помощью механизма переключения задач, тогда как коммутаторы перехвата и прерываний сохраняют только содержимое регистров IFLAGS, CS и IP, а сохранение других регистров возлагается на программиста, разрабатывающего соответствующую программу обработки прерывания.

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

Управление вводом-выводом

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

Физическая организация устройств ввода-вывода

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

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

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

ОС выполняет ввод-вывод, записывая команды в регистры контроллера. Например, контроллер гибкого диска IBM PC принимает 15 команд, таких как READ, WRITE, SEEK, FORMAT и т.д. Когда команда принята, процессор оставляет контроллер и занимается другой работой. При завершении команды контроллер организует прерывание для того, чтобы передать управление процессором операционной системе, которая должна проверить результаты операции. Процессор получает результаты и статус устройства, читая информацию из регистров контроллера.

Организация программного обеспечения ввода-вывода

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

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

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

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

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

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

Для решения поставленных проблем целесообразно разделить программное обеспечение ввода-вывода на четыре слоя (рисунок 2.30):

  •  Обработка прерываний,
  •  Драйверы устройств,
  •  Независимый от устройств слой операционной системы,
  •  Пользовательский слой программного обеспечения.

Рис. 2.30. Многоуровневая организация подсистемы ввода-вывода 

Обработка прерываний

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

Драйверы устройств

Весь зависимый от устройства код помещается в драйвер устройства. Каждый драйвер управляет устройствами одного типа или, может быть, одного класса.

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

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

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

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

Независимый от устройств слой операционной системы

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

Типичными функциями для независимого от устройств слоя являются:

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

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

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

Пользовательский слой программного обеспечения

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

count = write (fd, buffer, nbytes),

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

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

Файловая система

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

В широком смысле понятие "файловая система" включает:

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

Имена файлов

Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при этом учитываются ограничения ОС как на используемые символы, так и на длину имени. До недавнего времени эти границы были весьма узкими. Так в популярной файловой системе FAT длина имен ограничивается известной схемой 8.3 (8 символов - собственно имя, 3 символа - расширение имени), а в ОС UNIX System V имя не может содержать более 14 символов. Однако пользователю гораздо удобнее работать с длинными именами, поскольку они позволяют дать файлу действительно мнемоническое название, по которому даже через достаточно большой промежуток времени можно будет вспомнить, что содержит этот файл. Поэтому современные файловые системы, как правило, поддерживают длинные символьные имена файлов. Например, Windows NT в своей новой файловой системе NTFS устанавливает, что имя файла может содержать до 255 символов, не считая завершающего нулевого символа.

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

Длинные имена поддерживаются не только новыми файловыми системами, но и новыми версиями хорошо известных файловых систем. Например, в ОС Windows 95 используется файловая система VFAT, представляющая собой существенно измененный вариант FAT. Среди многих других усовершенствований одним из главных достоинств VFAT является поддержка длинных имен. Кроме проблемы генерации эквивалентных коротких имен, при реализации нового варианта FAT важной задачей была задача хранения длинных имен при условии, что принципиально метод хранения и структура данных на диске не должны были измениться.

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

Типы файлов

Файлы бывают разных типов: обычные файлы, специальные файлы, файлы-каталоги.

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

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

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

В разных файловых системах могут использоваться в качестве атрибутов разные характеристики, например:

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

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

Рис. 2.31. Структура каталогов: а - структура записи каталога MS-DOS (32 байта);
б - структура записи каталога ОС UNIX
 

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

Рис. 2.32. Логическая организация файловой системы
а - одноуровневая; б - иерархическая (дерево); в - иерархическая (сеть)
 

Логическая организация файла

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

Рис. 2.33. Способы логической организации файлов 

Физическая организация и адрес файла

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

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

Рис. 2.34. Физическая организация файла
а - непрерывное размещение; б - связанный список блоков;
в - связанный список индексов; г - перечень номеров блоков
 

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

В заключение рассмотрим задание физического расположения файла путем простого перечисления номеров блоков, занимаемых этим файлом. ОС UNIX использует вариант данного способа, позволяющий обеспечить фиксированную длину адреса, независимо от размера файла. Для хранения адреса файла выделено 13 полей. Если размер файла меньше или равен 10 блокам, то номера этих блоков непосредственно перечислены в первых десяти полях адреса. Если размер файла больше 10 блоков, то следующее 11-е поле содержит адрес блока, в котором могут быть расположены еще 128 номеров следующих блоков файла. Если файл больше, чем 10+128 блоков, то используется 12-е поле, в котором находится номер блока, содержащего 128 номеров блоков, которые содержат по 128 номеров блоков данного файла. И, наконец, если файл больше 10+128+128(128, то используется последнее 13-е поле для тройной косвенной адресации, что позволяет задать адрес файла, имеющего размер максимум 10+ 128 + 128(128 + 128(128(128.

Права доступа к файлу

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

  •  создание файла,
  •  уничтожение файла,
  •  открытие файла,
  •  закрытие файла,
  •  чтение файла,
  •  запись в файл,
  •  дополнение файла,
  •  поиск в файле,
  •  получение атрибутов файла,
  •  установление новых значений атрибутов,
  •  переименование,
  •  выполнение файла,
  •  чтение каталога,

и другие операции с файлами и каталогами.

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

Рис. 2.35. Матрица прав доступа 

Различают два основных подхода к определению прав доступа:

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

Кэширование диска

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

Общая модель файловой системы

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

Рис. 2.36. Общая модель файловой системы 

Задачей символьного уровня является определение по символьному имени файла его уникального имени. В файловых системах, в которых каждый файл может иметь только одно символьное имя (например, MS-DOS), этот уровень отсутствует, так как символьное имя, присвоенное файлу пользователем, является одновременно уникальным и может быть использовано операционной системой. В других файловых системах, в которых один и тот же файл может иметь несколько символьных имен, на данном уровне просматривается цепочка каталогов для определения уникального имени файла. В файловой системе UNIX, например, уникальным именем является номер индексного дескриптора файла (i-node).

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

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

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

Рис. 2.37. Функции физического уровня файловой системы 

Исходные данные:
V - размер блока
N - номер первого блока файла
S - смещение логической записи в файле

Требуется определить на физическом уровне: 

n - номер блока, содержащего требуемую логическую запись

s - смещение логической записи в пределах блока

n = N + [S/V], где [S/V] - целая часть числа S/V
s = R [S/V] - дробная часть числа S/V

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

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

Отображаемые в память файлы

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

Предположим, например, что файл f имеет длину 64 К и отображается на область виртуального адресного пространства с начальным адресом 512 К. После этого любая машинная команда, которая читает содержимое байта по адресу 512 К, получает 0-ой байт этого файла и т.д. Очевидно, что запись по адресу 512 К + 1100 изменяет 1100 байт файла. При завершении процесса на диске остается модифицированная версия файла, как если бы он был изменен комбинацией вызовов SEEK и WRITE.

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

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

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

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

Рис. 2.38. (а) Сегменты процесса перед отображением файлов в адресное пространство; (б) Процесс
после отображения существующего файла abc в один сегмент и создания нового сегмента для файла ddd
 

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

Третья проблема состоит в том, что файл может быть больше, чем сегмент, и даже больше, чем все виртуальное адресное пространство. Единственный способ ее решения состоит в реализации вызова MAP таким образом, чтобы он мог отображать не весь файл, а его часть. Хотя такая работа, очевидно, менее удобна, чем отображение целого файла.

Современные архитектуры файловых систем

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

Новая файловая система имеет многоуровневую структуру (рисунок 2.39), на верхнем уровне которой располагается так называемый переключатель файловых систем (в Windows 95, например, такой переключатель называется устанавливаемым диспетчером файловой системы - installable filesystem manager, IFS). Он обеспечивает интерфейс между запросами приложения и конкретной файловой системой, к которой обращается это приложение. Переключатель файловых систем преобразует запросы в формат, воспринимаемый следующим уровнем - уровнем файловых систем.

Рис. 2.39. Архитектура современной файловой системы 

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

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

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

76850. Артерии голени 182.91 KB
  Они являются конечными ветвями подколенной артерии и начинаются от нее на уровне нижнего края подколенной мышцы. Передний пучок состоит из передней большеберцовой артерии 23 сопровождающих глубоких вен и глубокой ветви малоберцового нерва боковой пучок из малоберцовой артерии 23 сопровождающих глубоких вен и поверхностной ветви малоберцового нерва. Мелкие ветви задней большеберцовой артерии: Ветвь огибающая головку фибулы участвует в образовании сети коленного сустава и кровоснабжении малоберцовых мышц.
76851. Артерии стопы 180.84 KB
  Дуга проецируется на уровне оснований плюсневых костей и заканчивается соединением с глубокой ветвью тыльной артерии стопы проходящей в первом межплюсневом промежутке. От дуги начинаются четыре плюсневые артерии . Прободающие артерии через межкостные промежутки соединяются с тыльными плюсневыми артериями.
76853. Плечеголовные вены 184.63 KB
  Обе плечеголовные вены: правая и левая (vv. brachiocephlicae dextra et sinistra) начинаются при слиянии подключичных и внутренних яремных вен правой и левой стороны на уровне и позади грудино-ключичных суставов, а заканчиваются образованием верхней полой вены на уровне прикрепления к грудине
76856. Вены головы 186.78 KB
  Кровь из вен головы поступает в яремные вены шеи и внутреннее позвоночное сплетение. Поверхностные вены головного мозга впадают в венозные синусы твердой мозговой оболочки. cerebri superiores имеющих восходящее направление: вены пре и постцентральной извилин предлобные лобные теменные и затылочные которые впадают в верхний сагиттальный синус.
76857. Вены верхней конечности 179.85 KB
  В области надплечья и плеча они вливаются в глубокие вены. Вторые проходят вместе с артериями собирая кровь от костей мышц суставов и вливаясь в подключичные вены. Вены верхней конечности клапанные начинаясь от пальцев они формируют на кисти тыльные венозные сети и ладонные дуги с перфорантными ветвями на предплечье и плече поверхностные и глубокие вены с анастомозами между ними.