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

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

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

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

Адресация в 32-разрядных микропроцессорах i80x86______________________ 111

Рис. 4.7. Дескриптор страницы

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

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

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

Каждая из таблиц (PDE и РТЕ) состоит из 1024 элементов (2 Ш = 1024). В свою очередь, каждый элемент (дескриптор страницы) имеет длину 4 байт (32 бит), по­этому размер этих таблиц как раз соответствует размеру страницы.

Оценим теперь эту схему трансляции с позиций расхода памяти. Каждый дескрип­тор описывает страницу размером 4 Кбайт. Следовательно, одна таблица страниц, содержащая 1024 дескриптора, описывает пространство памяти в 4 Мбайт. Если за­дача пользуется виртуальным адресным пространством, например, в 55 Мбайт (пред­положим, что речь идет о некотором графическом редакторе, который обрабатывает изображение, состоящее из большого количества пикселов 1 ), то для описания этой памяти необходимо иметь 14 страниц (14×4 Мбайт = 56 Мбайт), содержащих таб­лицы РТЕ. Кроме того, нам потребуется для этой задачи еще одна таблица PDE (тоже размером в одну страницу), в которой 14 дескрипторов будут указывать на место-

‘ Напомним, что термин «пиксел» происходит от английского Picture Element — графический эле­мент. Множество пикселов образуют изображение.

112________________ Глава 4. Особенности архитектуры микропроцессоров i80x86

нахождение упомянутых таблиц РТЕ. Остальные дескрипторы PDE не требуются. Итого, для описания 55 Мбайт адресного пространства задачи потребуется всего 15 страниц, то есть 60 Кбайт памяти, что можно считать приемлемым.

Рис. 4.8. Трансляция линейного адреса в микропроцессорах i80x86

Адресация в 32-разрядных микропроцессорах j80x86_________________________ 113

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

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

Дата добавления: 2016-09-20 ; просмотров: 576 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Источник

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

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

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

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

94_____________________ Глава 3. Управление памятью в операционных системах

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

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

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

— чтение и запись;

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

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

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

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

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

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

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

96_____________________ Глава 3. Управление памятью в операционных системах

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

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

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

1 В системе Windows NT файл с выгруженными виртуальными страницами носит название PageFile.sys. Таких файлов может быть несколько. Их совокупный размер должен быть не менее, чем объем физи­ческой памяти компьютера плюс 11 Мбайт, необходимых для самой Windows NT. В системах Windows 2000 размер файла PageFile.sys намного превышает объем установленной физической па­мяти и часто достигает многих сотен мегабайтов.

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

микропроцессорах равен 4 Кбайт, возможно быстрое обращение к памяти разме­ром 128 Кбайт.

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

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

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

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

Источник