Программы и расположение в памяти

Мы уже реализовали многозадачную систему с мультипрограммированием, но столкнулись с проблемой при попытке запустить второй пользовательский процесс. Если вы помните, что при компиляции программ в Navy-apps мы линковали их все на адрес 0x3000000 или 0x83000000, вы сразу поймёте причину проблемы: при загрузке второго пользовательского процесса мы затираем содержимое первого!

Коренная причина возникшей выше проблемы в том, что нарушено условие «в памяти могут одновременно существовать несколько процессов». Очевидно, нам нужно управлять памятью, а не позволять множеству процессов использовать её как попало. Мы упоминали в PA3, что операционная система обязана управлять системными ресурсами, а в многозадачной операционной системе память как ресурс, естественно, тоже должна находиться под управлением. Операционная система должна отслеживать распределение памяти: когда нужно запустить новый процесс, она просто выделяет ему свободный участок памяти и загружает процесс туда.

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

Абсолютный код

Обычно расположение программы в памяти определяется на этапе компоновки (link time) (именно так обстоит дело с программами в Navy-apps); а некоторые программисты в прошлом даже напрямую использовали в программах абсолютные адреса для доступа к памяти. Оба этих вида кода называют абсолютным кодом (absolute code). Абсолютный код предполагает, что объекты программы (функции и данные) находятся по некоторому фиксированному адресу — например, после перемещения (relocation) на этапе компоновки программа считает, что переменная a находится по адресу 0x83001234. Если мы загрузим программу в другое место, фактическое расположение переменной a после загрузки изменится, но абсолютный код в программе всё равно будет считать, что переменная a по-прежнему находится по адресу 0x83001234, а обращение к 0x83001234 уже не даст доступа к настоящей переменной a. Очевидно, что абсолютный код может корректно работать только по фиксированному адресу в памяти.

Но свободный участок памяти, выделяемый операционной системой в момент загрузки, не всегда позволяет такой программе работать корректно. Поэтому одно из решений этой проблемы — заставить операционную систему отслеживать место загрузки программы: когда программа пытается загрузиться по адресу, уже занятому, загрузка завершится неудачей, и операционная система вернёт ошибку. Чтобы избежать неудачной загрузки, один из способов — поддерживать для каждой программы несколько версий с разными адресами загрузки в надежде, что хотя бы одна из них сможет успешно загрузиться.

Перемещаемый код

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

Поэтому некоторые программисты разработали особый класс программ — «самоперемещающиеся (self-relocation)». Такие программы при запуске сначала сами перемещают себя в другой участок памяти, а затем уже начинают настоящее выполнение. Такой тип перемещения называется «перемещением во время выполнения (run time)».

Мы упоминали в PA1 понятие BIOS; на самом деле программа в BIOS — это как раз такая самоперемещающаяся программа. Дело в том, что BIOS обычно прошита в ROM, а данные в ROM нельзя записывать. После включения компьютер начинает выполнять программу из BIOS, но эта программа BIOS сразу же копирует себя в другой участок памяти, выполняет некоторую работу по перемещению, и только после этого действительно начинает выполняться. К этому моменту данные уже находятся в записываемой RAM, и программа BIOS может производить над ними операции записи.

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

Раз только операционная система знает, свободна ли память, — почему бы просто не поручить перемещение загрузчику? Так появилось понятие «перемещения во время загрузки (load time)». А именно: загрузчик запрашивает свободный участок памяти, затем загружает программу по этому адресу, перемещает программу на этот адрес, и только после этого программа выполняется. Именно так сегодня GNU/Linux вставляет модули ядра.

Позиционно-независимый код

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

Нет ли способа сэкономить на затратах на перемещение или вообще избежать перемещения? Однако перемещение во время компоновки, в свою очередь, может привести к появлению абсолютного кода, а этого нам бы не хотелось. Если все обращения к адресам в программе выполняются относительно расположения самой программы, такую программу можно загрузить и выполнить в любом месте, не сталкиваясь с проблемами абсолютного кода —

и это как раз базовая идея PIC (position-independent code, позиционно-независимый код). Сегодня все динамические библиотеки представляют собой PIC, что позволяет загружать их в любой участок памяти. Кроме того, если исполняемый файл целиком состоит из PIC, у него есть отдельное название — PIE (position-independent executable, позиционно-независимый исполняемый файл). Компилятор может собрать PIE с помощью специальных опций. В отличие от обычных программ, PIE в определённой мере мешает и вредоносным атакующим программам: вредоносная программа тоже не может заранее предположить, по какому адресу будет выполняться PIE.

Именно благодаря этому свойству, связанному с безопасностью, во многих современных дистрибутивах GNU/Linux идущий в комплекте gcc по умолчанию собирает PIE. Впрочем, использование относительной адресации увеличивает объём кода программы и в некоторой степени сказывается на производительности; но для ранних компьютеров память была очень ценным ресурсом, и снижения производительности тоже никому не хотелось, поэтому к PIC и PIE относились достаточно осторожно.

Реализуйте загрузчик на основе PIE (рекомендуется обдумать при повторном прохождении)

Бесплатных обедов не бывает: то, что PIE достигает позиционной независимости, на самом деле опирается на структуру данных в программе под названием GOT (global offset table, глобальная таблица смещений). Чтобы PIE корректно работал, загрузчику при загрузке программы нужно заполнить GOT правильным содержимым.

Желающие могут добавить в загрузчик Nanos-lite поддержку PIE — конечно, для этого потребуется разобраться в некоторых деталях, связанных с ELF; конкретные подробности можно найти в руководстве ABI.

Если бы все программы в мире были перемещаемыми или представляли собой PIC, проблема перекрытия памяти отпала бы сама собой. Но всегда найдутся программы, содержащие абсолютный код, и с учётом вопросов совместимости их всё равно нужно как-то запускать. Нет ли более удачного, окончательного решения?

Магия переплетения виртуального и реального

Только что мы рассматривали проблему со стороны самой программы, и потому неизбежно упирались в вопрос абсолютного кода. Чтобы решить эту проблему, нужно взглянуть с другой стороны — со стороны памяти. Мы знаем, что программа проходит четыре этапа: компиляция, компоновка, загрузка, выполнение. После компиляции и компоновки абсолютного кода адрес памяти, который «видит» программа, оказывается зафиксирован; при загрузке и выполнении программа будет использовать именно этот адрес памяти, чтобы гарантировать корректную работу. Одна из попыток решения — отделить память, которую «видит» программа, от памяти, которую она на самом деле использует во время выполнения. Это и есть идея виртуальной памяти.

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

Так кто же, во время выполнения процесса, отображает виртуальный адрес в физический? Мы уже знакомы с жизненным циклом инструкции из PA1:

while (1) {
  Fetch the instruction from the memory location indicated by PC;
  Execute the instruction;
  Update PC;
}

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

Поэтому выполнять это отображение в аппаратуре — единственный выход: мы добавляем между процессором и памятью новый аппаратный модуль MMU (Memory Management Unit, блок управления памятью). Он — ядро механизма виртуальной памяти и берёт на себя важнейшую функцию этого механизма — отображение адресов. Стоит уточнить: упомянутое только что «MMU расположен между процессором и памятью» — лишь концептуальное описание. На самом деле механизм виртуальной памяти в современных компьютерах настолько важен, что MMU физически реализован прямо внутри чипа процессора.

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

Сегментация

Что касается того, как именно MMU выполняет отображение адресов, сейчас существует в основном два широко распространённых подхода. Самый простой способ таков: физический адрес = виртуальный адрес + смещение. Этот самый незамысловатый способ и есть сегментный механизм управления виртуальной памятью, сокращённо — сегментация (segmentation). Интуитивно это можно представить так: физическая память делится на несколько сегментов, разные процессы помещаются в разные сегменты для выполнения, при этом процессу не нужно заботиться о том, в каком именно сегменте он находится, — достаточно, чтобы операционная система использовала для разных процессов разные смещения, и процессы не будут мешать друг другу.

Аппаратная реализация механизма сегментации может быть очень простой — достаточно реализовать в MMU регистр базового адреса сегмента. Когда операционная система запускает разные процессы, она устанавливает разные значения в этот регистр базового адреса сегмента, а MMU прибавляет базовый адрес сегмента к виртуальному адресу, используемому процессом, чтобы получить настоящий физический адрес для обращения к памяти — так и достигается цель «использовать для разных процессов разные сегменты». Именно так работает учебная операционная система Minix, а некоторые простые встраиваемые системы и системы реального времени тоже управляют виртуальной памятью через механизм сегментации.

На самом деле механизм сегментации в процессорах может быть намного сложнее. Например, i386 по историческим причинам, ради совместимости со своим предшественником 8086, был вынужден ввести такие понятия, как дескриптор сегмента, селектор сегмента, глобальная таблица дескрипторов (GDT), регистр глобальной таблицы дескрипторов (GDTR) и так далее. В дескрипторе сегмента, помимо базового адреса сегмента, также описываются такие атрибуты, как длина, тип, гранулярность, права доступа сегмента и прочее. А чтобы компенсировать проблемы с производительностью из-за дескрипторов сегментов, добавили ещё и понятие кэша дескрипторов... Можно вживую полюбоваться на всё великолепие механизма сегментации i386:

           15              0    31                                   0
  LOGICAL +----------------+   +-------------------------------------+
  ADDRESS |    SELECTOR    |   |                OFFSET               |
          +---+---------+--+   +-------------------+-----------------+
       +------+         V                          |
       | DESCRIPTOR TABLE                          |
       |  +------------+                           |
       |  |            |                           |
       |  |            |                           |
       |  |            |                           |
       |  |            |                           |
       |  |------------|                           |
       |  |  SEGMENT   | BASE          +---+       |
       +->| DESCRIPTOR |-------------->| + |<------+
          |------------| ADDRESS       +-+-+
          |            |                 |
          +------------+                 |
                                         V
              LINEAR  +------------+-----------+--------------+
              ADDRESS |    DIR     |   PAGE    |    OFFSET    |
                      +------------+-----------+--------------+

На первый взгляд это действительно сбивает с толку.

Что нам нужно знать об этом в NEMU? Ничего. Большинство современных операционных систем больше не используют механизм сегментации, и даже в руководстве по i386 упоминается, что его можно как-то «обойти» ради повышения производительности: установить базовый адрес сегмента в 0, а длину — в 4 ГБ, тогда всё выглядит так, будто понятия сегментов вовсе нет, — это и есть упомянутый в руководстве по i386 «плоский режим» (flat mode). Разумеется, «обход» здесь не означает простое отключение механизма сегментации (на самом деле его и невозможно отключить): понятие уровня привилегий, о котором мы говорили в PA3 применительно к механизму защиты i386, на самом деле как раз обеспечивается механизмом сегментации i386, и отказываться от него было бы крайне неразумно. Однако мы и не планируем реализовывать механизм защиты в NEMU, поэтому различные понятия механизма сегментации мы тоже не будем добавлять в NEMU.