Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

93
тистическую информацию об обращениях к сегментам. В результате можно соста- вить список, упорядоченный либо по длительности не использования (для дисцип- лины LRU), либо по частоте использования (для дисциплины LFU).
Важнейшей проблемой, которая возникает при организации мультипро-
граммного режима, является защита памяти. Для того чтобы выполняющиеся приложения не смогли испортить саму ОС и другие вычислительные процессы, не- обходимо, чтобы доступ к таблицам сегментов с целью их модификации был обес- печен только для кода самой ОС. Для этого код ОС должен выполняться в некото- ром привилегированном режиме, из которого можно осуществлять манипуляции с дескрипторами сегментов, тогда как выход за пределы сегмента в обычной при- кладной программе должен вызывать прерывание по защите памяти. Каждая при- кладная задача должна иметь возможность обращаться только к своим собст- венным сегментам.
При использовании сегментного способа организации виртуальной памяти по- является несколько интересных возможностей. Во-первых, появляется возмож- ность при загрузке программы на исполнение размещать её в памяти не целиком, а
«по мере необходимости». Действительно, поскольку в подавляющем большинстве случаев алгоритм, по которому работает код программы, является разветвлённым,
а не линейным, то в зависимости от исходных данных некоторые части программы,
расположенные в самостоятельных сегментах, могут быть и не задействованы; зна- чит, их можно и не загружать в оперативную память. Во-вторых, некоторые про- граммные модули могут быть разделяемыми. Эти программные модули являются сегментами, и в этом случае относительно легко организовать доступ к таким сег- ментам. Сегмент с разделяемым кодом располагается в памяти в единственном эк- земпляре, а в нескольких таблицах дескрипторов сегментов исполняющихся задач будут находиться указатели на такие разделяемые сегменты.
Однако у сегментного способа распределения памяти есть и недостатки. Пре- жде всего, из рис. 2.7 видно, что для получения доступа к искомой ячейке памяти необходимо потратить намного больше времени. Мы должны сначала найти и про- читать дескриптор сегмента, а уже потом, используя данные из него о местонахож-

94
дении нужного нам сегмента, можем вычислить и конечный физический адрес. Для того чтобы уменьшить эти потери, используется кэширование – то есть те дескрип- торы, с которыми мы имеем дело в данный момент, могут быть размещены в сверхоперативной памяти (специальных регистрах, размещаемых в процессоре).
Несмотря на то, что этот способ распределения памяти приводит к существен- но меньшей фрагментации памяти, нежели способы с неразрывным распределени- ем, фрагментация остается. Кроме этого, мы имеем большие потери памяти и про- цессорного времени на размещение и обработку дескрипторных таблиц. Ведь на каждую задачу необходимо иметь свою таблицу дескрипторов сегментов. А при определении физических адресов необходимо выполнять операции сложения.
Поэтому следующим способом разрывного размещения задач в памяти стал способ, при котором все фрагменты задачи одинакового размера и длины, кратной степени двойки, чтобы операции сложения можно было заменить операциями кон- катенации (слияния). Это – страничный способ организации виртуальной памяти.
Примером использования сегментного способа организации виртуальной па- мяти является операционная система для ПК OS/2 первого поколения
1
, которая бы- ла создана для процессора i80286. В этой ОС в полной мере использованы ап- паратные средства микропроцессора, который специально проектировался для поддержки сегментного способа распределения памяти.
OS/2 v.l поддерживала распределение памяти, при котором выделялись сег- менты программы и сегменты данных. Система позволяла работать как с имено- ванными, так и неименованными сегментами. Имена разделяемых сегментов дан- ных имели ту же форму, что и имена файлов. Процессы получали доступ к имено- ванным разделяемым сегментам, используя их имена в специальных системных вызовах. OS/2 v.l допускала разделение программных сегментов приложений и подсистем, а также глобальных сегментов данных подсистем. Вообще, вся кон- цепция системы OS/2 была построена на понятии разделения памяти: процессы почти всегда разделяют сегменты с другими процессами. В этом состояло суще-
1
OS/2 v.l начала создаваться в 1984 г. и вышла в продажу в 1987 г.

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

96
динением. Динамическое присоединение уменьшает объём памяти для программ в
OS/2, одновременно делая возможным перемещения подсистем и обслуживающих программ без необходимости повторного редактирования адресных ссылок к при- кладным программам.
Страничный способ организации виртуальной памяти
Как мы уже сказали, при таком способе все фрагменты программы, на которые она разбивается (за исключением последней её части), получаются одинаковыми.
Одинаковыми полагаются и единицы памяти, которые мы предоставляем для раз- мещения фрагментов программы. Эти одинаковые части называют страницами и говорят, что память разбивается на физические страницы, а программа – на вирту- альные страницы. Часть виртуальных страниц задачи размещается в оперативной памяти, а часть – во внешней. Обычно место во внешней памяти, в качестве кото- рой в абсолютном большинстве случаев выступают накопители на магнитных дис- ках (поскольку они относятся к быстродействующим устройствам с прямым досту- пом), называют файлом подкачки или страничным файлом (paging file). Иногда этот файл называют swap-файлом, тем самым подчеркивая, что записи этого файла
– страницы – замещают друг друга в оперативной памяти. В некоторых ОС выгру- женные страницы располагаются не в файле, а в специальном разделе дискового пространства. В UNIX-системах для этих целей выделяется специальный раздел,
но кроме него могут быть использованы и файлы, выполняющие те же функции,
если объёма раздела недостаточно.
Разбиение всей оперативной памяти на страницы одинаковой величины, при- чем величина каждой страницы выбирается кратной степени двойки, приводит к тому, что вместо одномерного адресного пространства памяти можно говорить о двумерном. Первая координата адресного пространства – это номер страницы, а вторая координата – номер ячейки внутри выбранной страницы (его называют ин- дексом). Таким образом, физический адрес определяется парой (P
p
, i), а вир- туальный адрес – парой (P
v
, i), где P
v
– это номер виртуальной страницы, P
p
– это номер физической страницы и i – это индекс ячейки внутри страницы. Количество

97
битов, отводимое под индекс, определяет размер страницы, а количество битов, от- водимое под номер виртуальной страницы, – объём возможной виртуальной памя- ти, которой может пользоваться программа. Отображение, осуществляемое систе- мой во время исполнения, сводится к отображению P
v в P
p и приписывании к по- лученному значению битов адреса, задаваемых величиной i. При этом нет необхо- димости ограничивать число виртуальных страниц числом физических, то есть не поместившиеся страницы можно размещать во внешней памяти, которая в данном случае служит расширением оперативной.
Для отображения виртуального адресного пространства задачи на физическую память, как и в случае с сегментным способом организации, для каждой задачи не- обходимо иметь таблицу страниц для трансляции адресных пространств. Для опи- сания каждой страницы диспетчер памяти ОС заводит соответствующий де- скриптор, который отличается от дескриптора сегмента прежде всего тем, что в нем нет необходимости иметь поле длины – ведь все страницы имеют одинаковый размер. По номеру виртуальной страницы в таблице дескрипторов страниц теку- щей задачи находится соответствующий элемент (дескриптор). Если бит присутст- вия имеет единичное значение, значит, данная страница сейчас размещена в опера- тивной, а не во внешней памяти и мы в дескрипторе имеем номер физической страницы, отведенной под данную виртуальную. Если же бит присутствия равен нулю, то в дескрипторе мы будем иметь адрес виртуальной страницы, расположен- ной сейчас во внешней памяти. Таким образом и осуществляется трансляция вир- туального адресного пространства на физическую память. Этот механизм трансля- ции проиллюстрирован на рис. 2.8.
Защита страничной памяти, как и в случае с сегментным механизмом, основа- на на контроле уровня доступа к каждой странице. Как правило, возможны сле- дующие уровни доступа: только чтение; чтение и запись; только выполнение. В
этом случае каждая страница снабжается соответствующим кодом уровня доступа.
При трансформации логического адреса в физический сравнивается значение кода разрешенного уровня доступа с фактически требуемым. При их несовпадении ра- бота программы прерывается.

98

99
ращения (подразумевается, что на рис. 2.8 этот бит расположен в последнем поле),
и этот бит становится единичным при обращении к дескриптору.
Если объём физической памяти небольшой и даже часто требуемые страницы не удается разместить в оперативной памяти, то возникает так называемая «про- буксовка». Другими словами, пробуксовка – это ситуация, при которой загрузка нужной нам страницы вызывает перемещение во внешнюю память той страницы, с которой мы тоже активно работаем. Очевидно, что это очень плохое явление. Что- бы его не допускать, желательно увеличить объём оперативной памяти (сейчас это стало самым простым решением), уменьшить количество параллельно выполняе- мых задач либо попробовать использовать более эффективные дисциплины заме- щения. В абсолютном большинстве современных ОС используется дисциплина за- мещения страниц LRU как самая эффективная. Так, именно эта дисциплина ис- пользуется в OS/2 и Linux. Однако в такой ОС, как Windows NT, разработчики, же- лая сделать систему максимально независимой от аппаратных возможностей про- цессора, пошли на отказ от этой дисциплины и применили правило FIFO. А для то- го, чтобы хоть как-нибудь сгладить её неэффективность, была введена «буфериза- ция» тех страниц, которые должны быть записаны в файл подкачки на диск
1
или просто расформированы. Принцип буферирования прост. Прежде чем замещаемая страница действительно будет перемещена во внешнюю память или просто рас- формирована, она помечается как кандидат на выгрузку. Если в следующий раз произойдет обращение к странице, находящейся в таком «буфере», то страница ни- куда не выгружается и уходит в конец списка FIFO. В противном случае страница действительно выгружается, а на её место в «буфере» попадает следующий «кан- дидат». Величина такого «буфера» не может быть большой, поэтому эффектив- ность страничной реализации памяти в Windows NT намного ниже, чем у вышена- званных ОС, и явление пробуксовки начинается даже при существенно большем объёме оперативной памяти.
1
В системе Windows NT файл с выгруженными виртуальными страницами носит название PageFile.sys. Таких фай- лов может быть несколько. Их совокупная длина должна быть не меньше, чем объём физической памяти компьюте- ра плюс 11 Мб, необходимые для самой Windows NT. В системах Windows 2000 размер файла PageFile.sys намного превышает объём установленной физической памяти и часто достигает многих сотен мегабайт.

100
В ряде ОС с пакетным режимом работы для борьбы с пробуксовкой использу- ется метод «рабочего множества». Рабочее множество – это множество «актив- ных» страниц задачи за некоторой интервал То есть тех страниц, к которым было обращение за этот интервал времени. Реально количество активных страниц задачи
(за интервал Т) все время изменяется, и это естественно, но, тем не менее, для каж- дой задачи можно определить среднее количество её активных страниц. Это сред- нее число активных страниц и есть рабочее множество задачи. Наблюдения за ис- полнением множества различных программ показали [28, 37, 49], что даже если Т
равно времени выполнения всей работы, то размер рабочего множества часто су- щественно меньше, чем общее число страниц программы. Таким образом, если ОС
может определить рабочие множества исполняющихся задач, то для предотвраще- ния пробуксовки достаточно планировать на выполнение только такое количество задач, чтобы сумма их рабочих множеств не превышала возможности системы.
Как и в случае с сегментным способом организации виртуальной памяти, стра- ничный механизм приводит к тому, что без специальных аппаратных средств он будет существенно замедлять работу вычислительной системы. Поэтому обычно используется кэширование страничных дескрипторов. Наиболее эффективным способом кэширования является использование ассоциативного кэша. Именно та- кой ассоциативный кэш и создан в 32-разрядных микропроцессорах i80x86. Начи- ная с i80386, который поддерживает страничный способ распределения памяти, в этих микропроцессорах имеется кэш на 32 страничных дескриптора. Поскольку размер страницы в этих микропроцессорах равен 4 Кбайт, возможно быстрое об- ращение к 128 Кбайт памяти.
Итак, основным достоинством страничного способа распределения памяти яв- ляется минимально возможная фрагментация. Поскольку на каждую задачу может приходиться по одной незаполненной странице, то становится очевидно, что па- мять можно использовать достаточно эффективно; этот метод организации вир- туальной памяти был бы одним из самых лучших, если бы не два следующих об- стоятельства.

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