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

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

Как уже упоминалось, при страничном способе организации виртуальной памяти все фрагменты программы, на которые она разбивается (за исключением после­дней ее части), получаются одинаковыми. Одинаковыми полагаются и единицы памяти, которые предоставляются для размещения фрагментов программы. Эти одинаковые части называют страницами и говорят, что оперативная память раз­бивается на физические страницы, а программа — на виртуальные страницы. Часть виртуальных страниц задачи размещается в оперативной памяти, а часть — во внеш­ней. Обычно место во внешней памяти, в качестве которой в абсолютном боль­шинстве случаев выступают накопители на магнитных дисках (поскольку они относятся к быстродействующим устройствам с прямым доступом), называют фай­лом подкачки, или страничным файлом (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 Кбайт.

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

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Статьи к прочтению:

Операционные системы, урок 7: Организация памяти. Виртуальная память.

Похожие статьи:

Рассмотрим пример физической памяти, в которой изначально содержится 5 сегментов. Посмотрим, что происходит, если сегмент 1 удаляется, а сегмент 7,…

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

Источник