Организация виртуальной памяти

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

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

Схемы управления памятью – страничная, сегментная и сегментно-страничная.

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

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

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

 

13. Стратегии замещения и размещения страниц. Принцип локальности.

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

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

Стратегия размещения (placement policy) - в какой участок первичной памяти поместить поступающую страницу. В системах со страничной организацией все просто - в любой свободный страничный кадр.

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

Стратегия размещения. В системах со страничной организацией виртуальной памяти решение о размещении вновь загружаемых страниц принимается достаточно просто: новая страница может быть помещена в любой свободный страничный кадр. Для систем с сегментной организацией виртуальной памяти применяются стратегии размещения: 1)размещение с выбором первого подходящего (стратегия "первый подходящий");2)размещение с выбором наиболее подходящего (стратегия "самый подходящий"); 3) алгоритм с выбором наименее подходящего (стратегия "самый неподходящий"). Стратегия "первый подходящий" состоит в выполнении следующих шагов: 1) упорядочить таблицу свободных областей в порядке возрастания адресов; 2) поместить информацию в первый встретившийся участок основной памяти размером не менее требуемого. Стратегия "самый подходящий" реализует следующую последовательность действий:1) упорядочить таблицу свободных областей в порядке возрастания размеров свободных областей; 2) поместить информацию в первый встретившийся участок свободной памяти размером не менее требуемого. Стратегия "самый неподходящий" выполняет следующие действия: 1) упорядочить таблицу свободных областей в порядке убывания размеров областей; 2) поместить информацию в первый встретившийся участок свободной памяти размером не менее требуемого.

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

Рассмотрим ряд алгоритмов замещения страниц.

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

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

Алгоритм LRU-Выталкивание дольше всего не использовавшейся страницы. Ключевое отличие между FIFO и оптимальным алгоритмом заключается в том, что один смотрит назад, а другой вперед. Если использовать прошлое для аппроксимации будущего, имеет смысл замещать страницу, которая не использовалась в течение самого долгого времени. Такой подход называется least recently used алгоритм (LRU). LRU - хороший, но труднореализуемый алгоритм. Необходимо иметь связанный список всех страниц в памяти, в начале которого будут хранится недавно использованные страницы. Причем этот список должен обновляться при каждом обращении к памяти. Много времени нужно и на поиск страниц в таком списке. В 2002 году был рассмотрен вариант реализации алгоритма LRU со специальным 64-битным указателем, который автоматически увеличивается на единицу после выполнения каждой инструкции, а в таблице страниц имеется соответствующее поле, в которое заносится значение указателя при каждой ссылке на страницу. При возникновении страничного нарушения выгружается страница с наименьшим значением этого поля.

Алгоритм NFU- Выталкивание редко используемой страницы. Поскольку большинство современных процессоров не предоставляют соответствующей аппаратной поддержки для реализации алгоритма LRU, хотелось бы иметь алгоритм, достаточно близкий к LRU, но не требующий специальной поддержки. Это алгоритм NFU. Для него требуются программные счетчики, по одному на каждую страницу, которые сначала равны нулю. При каждом прерывании по времени (а не после каждой инструкции) операционная система сканирует все страницы в памяти и у каждой страницы с установленным флагом обращения увеличивает на единицу значение счетчика, а флаг обращения сбрасывает. Таким образом, кандидатом на освобождение оказывается страница с наименьшим значением счетчика, как страница, к которой реже всего обращались. Главный недостаток алгоритма NFU состоит в том, что он ничего не забывает. Например, страница, к которой очень часто обращались в течение некоторого времени, а потом обращаться перестали, все равно не будет удалена из памяти, потому что ее счетчик содержит большую величину. Например, в многопроходных компиляторах страницы, которые активно использовались во время первого прохода, могут надолго сохранить большие значения счетчика, мешая загрузке полезных в дальнейшем страниц. К счастью, возможна небольшая модификация алгоритма, которая позволяет ему "забывать". Достаточно, чтобы при каждом прерывании по времени содержимое счетчика сдвигалось вправо на 1 бит, а уже затем производилось бы его увеличение для страниц с установленным флагом обращения. Другим, уже более устойчивым недостатком алгоритма является длительность процесса сканирования таблиц страниц.

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

 

14. Этапы загрузки операционных систем (Unix, Windows NT).

Этапы загрузки операционной системы Unix. Рассмотрим загрузку операционной системы UNIX как следующую последовательность этапов

Досистемный загрузчик. Как правило, сразу после включения питания программа ПЗУ BIOS проводит тестирование оборудования, затем запускается досистемный загрузчик. Задача этого этапа — определить (возможно, с помощью пользователя), с какого устройства будет идти загрузка, загрузить оттуда специальную программу-загрузчик и запустить её. Например, выяснить, что устройство для загрузки — жесткий диск, считать самый первый сектор этого диска и передать управление программе, которая находится в считанной области.

Загрузчик первого уровня. З анимает обычно не более одного сектора в самом начале диска — в его загрузочной записи. Загрузочная запись диска (Master Boot Record) — первый сектор диска, в котором хранится таблица разделов и код системного загрузчика. Ядро операционной системы имеет довольно сложную структуру — а значит, и непростой способ загрузки; оно может быть довольно большим и может располагаться в произвольной област диска, подчиняясь законам файловой системы (например, состоять из нескольких частей, разбросанных по диску). Учесть все это первичный загрузчик не в состоянии, поэтому его задача — определить, где на диске находится загрузчик второго уровня, загрузить его в память и передать ему управление.

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

Инициализация ядра операционной системы. Ядро — очень сложная программа, взаимодействующая с различным оборудованием, поэтому прежде чем начать работу с системой, ядро необходимо проинициализировать. Этот этап специфичен для различных операционных систем. В UNIX-подобных системах при этом обычно выводится информация отладочного характера о ходе загрузке ядра. Первым делом ядро занимается определением параметров вычислительной подсистемы компьютера: выясняет тип и быстродействие центрального процессора, объем оперативной памяти, объем и структуру кэш-памяти; делает предположение об архитектуре компьютера в целом и многое другое. На следующем шаге ядро определяет состав и архитектуру всего аппаратного наполнения компьютера: тип и параметры шин передачи данных и устройств управления ими (контроллеров), список внешних устройств, доступных по шинам, настройки этих устройств — диапазон портов ввода-вывода, адрес ПЗУ, занимаемое аппаратное прерывание, номер канала прямого доступа к памяти и т. п. Ядро на основании параметра, переданного ему загрузчиком, выбирает корневой раздел — файловую систему, содержащую будущий каталог / и его подкаталоги (для системной начальной загрузки важны каталоги /etc, /bin, и /sbin). Корневой раздел монтируется в качестве /. После этого ядро запускает первый процесс — init (по умолчанию, /sbin/init).

процесс init. С этого момента операционная система обеспечивает полноценную функциональность всем исполняющимся процессам. В UNIX первым запускаемым процессом является init. Процесс init является обычным процессом операционной системы, однако он имеет некоторые особенности: его PID всегда равен 1, и процесс этот выполняется всё время, пока работает система. В UNIX-системах init играет две важные роли: 1) производит инициализацию системы — как правило, для работы запущенного ядра не достаточно, нужно смонтировать все файловые системы, загрузить дополнительные драйверы устройств, запустить демоны и т. п.; 2) является родительским для всех процессов в системе — это является гарантией того, что в UNIX для любого процесса в любой момент времени будет существовать родительский процесс.

Как правило, процесс init запускается из исполняемого файла /sbin/init и работает с некоторыми специфическими особенностями в различных UNIX-системах. Рассмотрим классификацию современных версий UNIX с точки зрения инициализации системы.

Этапы загрузки операционной системы Windows NT. Mинимальный набор файлов, который необходим для успешного запуска системы, вот они: 1)Boot.ini 2) Bootsect.dos (необходим только при использовании мультизагрузки) 3) NTLDR 4) Ntdetect.com 5) Ntbootdd.sys (необходим только для загрузки с SCSI-винчестера) 6) Ntoskrnl.exe 7) Hal.dll 8) Необходимые драйверы и разделы реестра.

При включении ПК ход загрузки операционной системы проходит в несколько этапов:

1) Код, выполняющий POST, зашит в БИОСе каждого компьютера, и именно ему передается управление при включении питания. Если в процессе тестирования обнаруживаются какие-либо ошибки, то БИОСом генерируются коды ошибок (POST codes), которые отличаются для БИОСа разных производителей. Если же процедура POST завершается успешно, то BIOS компьютера считывает и загружает в оперативную память главную загрузочную запись Master Boot Record (MBR), в которой находится таблица разделов диска и небольшая программа - эта программа находит начальный адрес системного раздела на диске и загружает в память копию его загрузочного сектора (сектор 0), а затем, если раздел помечен как "активный" в таблице разделов, передает управление другой программе - загрузчику WinNT из только что перенесенного в память загрузочного сектора.

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

3)После этого уже начинается выполнение обычных программ из файлов, находящихся на диске, что и приводит к полной загрузке всей операционной системы и к возможности запускать прикладные программы.(на процессорах RISC программа osloader.exe выполняет функции ntldr, ntdetect.com и bootsect.dos).

Работу загрузчика ntldr можно разбить на несколько этапов: 1) ntldr переключает процессор в режим 32-разрядной модели памяти с прямой адресацией;

2) запускает минифайловую систему для доступа к томам FAT, FAT32 и NTFS;

3)считывает файл boot.ini, также расположенный в корневом каталоге системного диска;

4)отображает меню выбора операционной системы (если выбирается ОС, отличная от WinNT, то считывается файл bootsect.dos с копией загрузочного сектора предыдущей ОС и управление передается ему);

5)запускает файл ntdetect.com, собирающий информацию о физических устройствах, подключенных к компьютеру в момент загрузки;

6) загружает и запускает ядро ОС - файл ntoskrnl.exe и передает ему информацию, собранную ntdetect.com.

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

7)После выбора операционной системы загрузчик запускает Ntdetect.com. Этот компонент считывает из CMOS-памяти системную дату и время, после чего производит поиск и распознавание аппаратных средств, подключенных в данный момент к компьютеру. Завершив работу, Ntdetect возвращает управление и аккуратно собранную им информацию обратно в NTLDR. Если существует несколько профилей оборудования, загрузчик предложит выбрать один из них, после чего приступит к загрузке ядра Ntoskrnl.exe. На этой стадии ядро только загружается в память, но ему не передается управление. В первую очередь в память загружается само ядро и уровень аппаратных абстракций. В этот момент на экране появляется надпись Starting Windows и индикатор завершенности процесса. Затем сканируется реестр (ищется куст, находящийся в \ Winnt\ System32\ Config\ System) и составляется список драйверов устройств, необходимых для запуска. Из реестра извлекаются настройки, касающиеся организации памяти, которые могут задаваться как самим пользователем, так и специальными утилитами. Здесь же создается набор управляющих параметров (Control Set), который в дальнейшем играет очень важную роль в работе системы.

Определившись с используемым набором, загрузчик делает его активным, ищет драйверы устройств, у которых переменная Start имеет значение 0х0, что означает, что они должны загружаться без инициализации. В свою очередь, параметр Group определяет, какие устройства в каком порядке будут загружаться. После окончания загрузки ядра операционная система практически готова к работе, осталось только проинициализировать драйверы и подготовить службы - индикатор полностью заполняется, и происходит переключение из текстового режима в графический. На этом шаге управление передается ядру Ntoskrnl, которое получает ссылки на объекты, созданные при помощи NTLDR, таким образом, ядру передается вся информация, собранная другими модулями, а в конце передается и управление. При своей инициализации ядро производит ряд действий в следующей последовательности: 1) окончательная подготовка к работе памяти и менеджера памяти; 2) инициализация диспетчера объектов; 3) установка системы безопасности; 4) инициализация менеджера Plug and Play; 5) установка базовых объектов и сервисов системы; 6) настройка драйвера файловой системы и сохранение начальных параметров в реестре (создается копия набора управляющих параметров Clone, в которой содержатся данные, идентичные Current ControlSet, инициализируются устройства согласно порядку инициализации, затем создается ключ HKEY_LOCAL_MACHINE\ HARDWARE); 7) загрузка и инициализация диспетчера ввода-вывода (обычно - самая длительная фаза); 8) ядро "убирает за собой мусор", который остался после загрузки; 9) последняя стадия - загрузка системных сервисов, которые, собственно, и реализуют взаимодействие с пользователем.

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