гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
Сегментное распределение При страничной организации виртуальное адресное пространство процесса делится механически на равные части. Это не позволяет дифференцировать способы доступа к разным частям программы (сегмен- там), а это свойство часто бывает очень полезным. Например, можно запретить обращаться с операциями записи и чтения в кодовый сегмент программы, а для сегмента данных разрешить только чтение. Кроме то- го, разбиение программы на "осмысленные" части делает принципиально возможным разделение одного 64 сегмента несколькими процессами. Например, если два процесса используют одну и ту же математическую подпрограмму, то в оперативную память может быть загружена только одна копия этой подпрограммы. Рис. 2.13. Механизм преобразования виртуального адреса в физический при страничной организации памяти Рассмотрим, каким образом сегментное распределение памяти реализует эти возможности (рисунок 2.14). Виртуальное адресное пространство процесса делится на сегменты, размер которых определяется про- граммистом с учетом смыслового значения содержащейся в них информации. Отдельный сегмент может представлять собой подпрограмму, массив данных и т.п. Иногда сегментация программы выполняется по умолчанию компилятором. При загрузке процесса часть сегментов помещается в оперативную память (при этом для каждого из этих сегментов операционная система подыскивает подходящий участок свободной памяти), а часть сегмен- тов размещается в дисковой памяти. Сегменты одной программы могут занимать в оперативной памяти не- смежные участки. Во время загрузки система создает таблицу сегментов процесса (аналогичную таблице страниц), в которой для каждого сегмента указывается начальный физический адрес сегмента в оперативной памяти, размер сегмента, правила доступа, признак модификации, признак обращения к данному сегменту за последний интервал времени и некоторая другая информация. Если виртуальные адресные пространства нескольких процессов включают один и тот же сегмент, то в таблицах сегментов этих процессов делаются ссылки на один и тот же участок оперативной памяти, в который данный сегмент загружается в единствен- ном экземпляре. Система с сегментной организацией функционирует аналогично системе со страничной организаци- ей: время от времени происходят прерывания, связанные с отсутствием нужных сегментов в памяти, при необходимости освобождения памяти некоторые сегменты выгружаются, при каждом обращении к опера- тивной памяти выполняется преобразование виртуального адреса в физический. Кроме того, при обращении к памяти проверяется, разрешен ли доступ требуемого типа к данному сегменту. Виртуальный адрес при сегментной организации памяти может быть представлен парой (g, s), где g - номер сегмента, а s - смещение в сегменте. Физический адрес получается путем сложения начального физи- ческого адреса сегмента, найденного в таблице сегментов по номеру g, и смещения s. 65 Недостатком данного метода распределения памяти является фрагментация на уровне сегментов и более медленное по сравнению со страничной организацией преобразование адреса. Рис. 2.14. Распределение памяти сегментами Странично-сегментное распределение Как видно из названия, данный метод представляет собой комбинацию страничного и сегментного распределения памяти и, вследствие этого, сочетает в себе достоинства обоих подходов. Виртуальное про- странство процесса делится на сегменты, а каждый сегмент в свою очередь делится на виртуальные страни- цы, которые нумеруются в пределах сегмента. Оперативная память делится на физические страницы. За- грузка процесса выполняется операционной системой постранично, при этом часть страниц размещается в оперативной памяти, а часть на диске. Для каждого сегмента создается своя таблица страниц, структура ко- торой полностью совпадает со структурой таблицы страниц, используемой при страничном распределении. Для каждого процесса создается таблица сегментов, в которой указываются адреса таблиц страниц для всех сегментов данного процесса. Адрес таблицы сегментов загружается в специальный регистр процессора, ко- гда активизируется соответствующий процесс. На рисунке 2.15 показана схема преобразования виртуально- го адреса в физический для данного метода. 66 Рис. 2.15. Схема преобразования виртуального адреса в физический для сегментно-страничной организации памяти Свопинг Разновидностью виртуальной памяти является свопинг. На рисунке 2.16 показан график зависимости коэффициента загрузки процессора в зависимости от числа одновременно выполняемых процессов и доли времени, проводимого этими процессами в состоянии ожидания ввода-вывода. Рис. 2.16. Зависимость загрузки процессора от числа задач и интенсивности ввода-вывода 67 Из рисунка видно, что для загрузки процессора на 90% достаточно всего трех счетных задач. Однако для того, чтобы обеспечить такую же загрузку интерактивными задачами, выполняющими интенсивный ввод-вывод, потребуются десятки таких задач. Необходимым условием для выполнения задачи является за- грузка ее в оперативную память, объем которой ограничен. В этих условиях был предложен метод органи- зации вычислительного процесса, называемый свопингом. В соответствии с этим методом некоторые про- цессы (обычно находящиеся в состоянии ожидания) временно выгружаются на диск. Планировщик опера- ционной системы не исключает их из своего рассмотрения, и при наступлении условий активизации некото- рого процесса, находящегося в области свопинга на диске, этот процесс перемещается в оперативную па- мять. Если свободного места в оперативной памяти не хватает, то выгружается другой процесс. При свопинге, в отличие от рассмотренных ранее методов реализации виртуальной памяти, процесс перемещается между памятью и диском целиком, то есть в течение некоторого времени процесс может пол- ностью отсутствовать в оперативной памяти. Существуют различные алгоритмы выбора процессов на за- грузку и выгрузку, а также различные способы выделения оперативной и дисковой памяти загружаемому процессу. 9. Иерархия запоминающих устройств. Принцип кэширования данных Память вычислительной машины представляет собой иерархию запоминающих устройств (внутрен- ние регистры процессора, различные типы сверхоперативной и оперативной памяти, диски, ленты), отли- чающихся средним временем доступа и стоимостью хранения данных в расчете на один бит (рисунок 2.17). Пользователю хотелось бы иметь и недорогую и быструю память. Кэш-память представляет некоторое ком- промиссное решение этой проблемы. Рис. 2.17. Иерархия ЗУ Кэш-память - это способ организации совместного функционирования двух типов запоминающих устройств, отличающихся временем доступа и стоимостью хранения данных, который позволяет уменьшить среднее время доступа к данным за счет динамического копирования в "быстрое" ЗУ наиболее часто ис- пользуемой информации из "медленного" ЗУ. Кэш-памятью часто называют не только способ организации работы двух типов запоминающих уст- ройств, но и одно из устройств - "быстрое" ЗУ. Оно стоит дороже и, как правило, имеет сравнительно не- большой объем. Важно, что механизм кэш-памяти является прозрачным для пользователя, который не дол- жен сообщать никакой информации об интенсивности использования данных и не должен никак участво- вать в перемещении данных из ЗУ одного типа в ЗУ другого типа, все это делается автоматически систем- ными средствами. Рассмотрим частный случай использования кэш-памяти для уменьшения среднего времени доступа к данным, хранящимся в оперативной памяти. Для этого между процессором и оперативной памятью поме- щается быстрое ЗУ, называемое просто кэш-памятью (рисунок 2.18). В качестве такового может быть использована, например, ассоциативная память. Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных. Каждая запись об элементе данных включает в себя адрес, который этот элемент данных имеет в оперативной памяти, и управляющую информацию: признак модификации и признак обращения к данным за некоторый последний период времени. 68 В системах, оснащенных кэш-памятью, каждый запрос к оперативной памяти выполняется в соответ- ствии со следующим алгоритмом: 1. Просматривается содержимое кэш-памяти с целью определения, не находятся ли нужные данные в кэш-памяти; кэш-память не является адресуемой, поэтому поиск нужных данных осуществляется по содержимому - значению поля "адрес в оперативной памяти", взятому из запроса. 2. Если данные обнаруживаются в кэш-памяти, то они считываются из нее, и результат переда- ется в процессор. 3. Если нужных данных нет, то они вместе со своим адресом копируются из оперативной памя- ти в кэш-память, и результат выполнения запроса передается в процессор. При копировании данных может оказаться, что в кэш-памяти нет свободного места, тогда выбираются данные, к которым в последний пери- од было меньше всего обращений, для вытеснения из кэш-памяти. Если вытесняемые данные были модифи- цированы за время нахождения в кэш-памяти, то они переписываются в оперативную память. Если же эти данные не были модифицированы, то их место в кэш-памяти объявляется свободным. На практике в кэш-память считывается не один элемент данных, к которому произошло обращение, а целый блок данных, это увеличивает вероятность так называемого "попадания в кэш", то есть нахождения нужных данных в кэш-памяти. Рис. 2.18. Кэш-память Покажем, как среднее время доступа к данным зависит от вероятности попадания в кэш. Пусть име- ется основное запоминающие устройство со средним временем доступа к данным t1 и кэш-память, имеющая время доступа t2, очевидно, что t2 69 70 В реальных системах вероятность попадания в кэш составляет примерно 0,9. Высокое значение веро- ятности нахождения данных в кэш-памяти связано с наличием у данных объективных свойств: пространст- венной и временной локальности. • Пространственная локальность. Если произошло обращение по некоторому адресу, то с вы- сокой степенью вероятности в ближайшее время произойдет обращение к соседним адресам. • Временная локальность. Если произошло обращение по некоторому адресу, то следующее обращение по этому же адресу с большой вероятностью произойдет в ближайшее время. Все предыдущие рассуждения справедливы и для других пар запоминающих устройств, например, для оперативной памяти и внешней памяти. В этом случае уменьшается среднее время доступа к данным, расположенным на диске, и роль кэш-памяти выполняет буфер в оперативной памяти. Аппаратно-независимый уровень управления виртуальной памятью Обычно ОС опирается на некоторое собственное представление организации виртуальной памяти, ко- торое используется в аппаратно-независимой части подсистемы управления виртуальной памятью и связывается с конкретной аппаратной реализацией с помощью аппаратно-зависимой части. Как же достигается возможность наличия виртуальной памяти с размером, существенно превышающим размер оперативной памяти? В элементе таблицы страниц может быть установлен специальный флаг (означающий отсутствие страницы), наличие которого заставляет аппаратуру вместо нормального ото- бражения виртуального адреса в физический прервать выполнение команды и передать управление со- ответствующему компоненту операционной системы. Когда программа обращается к виртуальной стра- нице, отсутствующей в основной памяти, т.е. "требует" доступа к данным или программному коду, операционная система удовлетворяет это требование путем выделения страницы основной памяти, пе- ремещения в нее копии страницы, находящейся во внешней памяти, и соответствующей модификации элемента таблицы страниц. Здесь мы имеем дело с частным случаем исключительной ситуации (exception) при работе с памятью, так называемым страничным нарушением (page fault). Исключительные ситуации при работе с памятью. Из материала предыдущей главы следует, что ключевая информация о характере отображения адреса хранится в таблице страниц. Помимо сведений о присутствии или отсутствии нужной страницы в опе- ративной памяти, атрибуты страницы могут разрешать или запрещать конкретные операции обращения к памяти. Что же происходит, когда операция запрещена, или нужной страницы в памяти нет? Естественно, что операционная система должна быть как-то оповещена о происшедшем. Обычно для этого используется механизм исключительных ситуаций (exceptions). При попытке выполнить опера- цию такого рода, возникает исключительная ситуация страничное нарушение (page fault), приводящая к вызову специальной программы - обработчика (handler) этой исключительной ситуации, который уже и решает, что же нужно предпринять, чтобы обработать конкретный вид страничного нарушения. Стра- ничное нарушение обычно происходит в самых разных случаях, например: при попытке записи в стра- ницу с атрибутом "только чтение" или при попытке чтения или записи страницы с атрибутом "только выполнение". В любом из этих случаев вызывается обработчик страничного нарушения, обычно яв- ляющийся частью операционной системы, которому обычно передается причина возникновения исклю- чительной ситуации и соответствующий виртуальный адрес. Нас будет интересовать вариант обращения к не присутствующей странице, поскольку его обработка во многом определяет производительность страничной системы. Оптимизация может происходить по пути уменьшения частоты страничных нарушений, а также увеличения скорости их обработки. Время эф- фективного доступа к не присутствующей странице складывается из: • времени обслуживания исключительной ситуации (page fault) • времени чтения (подкачки) страницы из вторичной памяти (иногда, при недостатке места в ос- новной памяти, необходимо вытолкнуть одну из страниц из основной памяти во вторичную, то есть осуществить замещение страницы). 71 • времени рестарта процесса, вызвавшего данный page fault Первое и третье времена могут быть уменьшены за счет тщательного кодирования нескольких сотен инструкций и составлять десятки микросекунд каждое. Время подкачки страницы с диска будет вероят- но близким к нескольким десяткам миллисекунд. Оценки (Silberschatz) показывают, что если удастся снизить вероятность page fault'а до 5*10**-7, то производительность страничной системы будет сниже- на всего на 10%. Таким образом, снижение частоты page fault'ов является одной из ключевых задач сис- темы управления памятью. Ее решение обычно связано с правильным выбором алгоритма замещения страниц. Алгоритмы замещения страниц Итак, наиболее ответственным действием страничной системы является выделение страницы основной памяти для удовлетворения требования доступа к отсутствующей в основной памяти виртуальной стра- нице. Напомним, что мы рассматриваем ситуацию, когда размер каждой виртуальной памяти может существенно превосходить размер основной памяти. Это означает, что при выделении страницы основ- ной памяти с большой вероятностью не удастся найти свободную (не приписанную к какой-либо вирту- альной памяти) страницу. В этом случае операционная система должна в соответствии с заложенными в нее критериями найти некоторую занятую страницу основной памяти, переместить в случае надобности ее содержимое во внешнюю память, должным образом модифицировать соответствующий элемент со- ответствующей таблицы страниц и после этого продолжить процесс удовлетворения доступа к страни- це. Заметим, что при замещении приходится дважды передавать страницу между основной и вторичной памятью. Процесс замещения может быть оптимизирован за счет использования бита модификации (один из атрибутов страницы). Бит модификации устанавливается компьютером, если хотя бы один байт записан на страницу. При выборе кандидата на замещение, проверяется бит модификации. Если бит не установлен, нет необходимости переписывать данную страницу на диск, она уже там. Эта техни- ка также применяется к read-only страницам, они никогда не модифицируются. Эта схема уменьшает время обработки fault'а. Существует большое количество разнообразных алгоритмов замещения страниц. Все они делятся на локальные и глобальные. Локальные алгоритмы, в отличие от глобальных, распределяют фиксирован- ное или динамически настраиваемое число страниц для каждого процесса. Когда процесс израсходует все предназначенные ему страницы, система будет удалять из физической памяти одну из его страниц, а не из страниц других процессов. Глобальный же алгоритм замещения в случае возникновения исключи- тельной ситуации удовлетворится освобождением любой физической страницы, независимо от того, какому процессу она принадлежала. Глобальные алгоритмы имеют несколько недостатков. Во-первых, они делают одни процессы чувстви- тельными к поведению других процессов. Например, если один процесс в системе использует большое количество памяти, то все остальные приложения будут в результате ощущать сильное замедление из-за недостатка памяти. Во-вторых, некорректно работающее приложение может подорвать работу всей сис- темы (если конечно в системе не предусмотрено ограничение на размер памяти, выделяемой процессу), пытаясь захватить все больше памяти. Поэтому в многозадачной системе лучше использовать более сложные, но эффективные локальные алгоритмы. Такой подход требует, чтобы система хранила список физических страниц каждого процесса. Этот список страниц иногда называют рабочим множеством процесса. Рабочее множество и реализация алгоритма подкачки, основанного на понятиях локальности и рабочего множества описаны в последующих разделах. Алгоритм обычно оценивается на конкретной последовательности ссылок к памяти, для которой под- считывается число fault'ов. Эта последовательность называется reference string. Мы можем генерировать reference string искусственным образом при помощи датчика случайных чисел или трассируя конкрет- ную систему. Последний метод дает слишком много ссылок, для уменьшения числа которых можно сделать две вещи: • Для конкретного размера страниц можно запоминать только их номера, а не адреса, на которые идет ссылка. • Если имеется ссылка на страницу p ближайшие последующие ссылки на данную страницу мож- но не фиксировать. Как уже говорилось, большинство процессоров имеют простейшие аппаратные средства, позволяющие собирать некоторую статистику обращений к памяти. Эти средства включают два специальных флага на каждый элемент таблицы страниц. Один флаг (флаг обращения, reference бит) автоматически устанав- ливается, когда происходит любое обращение к этой странице, а второй флаг (флаг изменения, modify бит) устанавливается, если производится запись в эту страницу. Чтобы использовать эти возможности, операционная система должна периодически сбрасывать эти флаги. |