Логический уровень организации памяти - страницы и сегменты.

Напиши свою ОС! #9

<p>
Здравствуйте, уважаемые, дорогие и любимые подписчики.
</p>
<p>
По объективным причинам общего состояния мозга на прошлой неделе этот выпуск пришел к вам сегодня, в понедельник,
а не как обычно, в пятницу. Снова я, Химов Роман. Снова буду обрушивать на ваш мозг горы и кучи полезной информации.
Но вы же не против?
</p>

Страницы и сегменты
Сначала я хотел бы рассказать о страничной/сегментной организации памяти поподробнее.
Итак, что, зачем и почему.
Страничная организация памяти

<p>
Странички были придуманы в свое время для того, чтобы компенсировать недостаток памяти. Ранее приходилось разбивать
программы на <i></i> и постепенно подгружать необходимые оверлеи по ходу выполнения. Забота об их
организации полностью отдавалась на откуп программисту.
</p>
<p>
Естественно это было не очень хорошо, уже хотя бы потому, что это лишний раз напрягало программистов на подвиги с
реализацией разбивки на оверлеи. Поэтому было придумано красивое решение - виртуальная память со страничной
организацией памяти.
</p>
<p>
Виртуальная память (а ее можно придумать сколько угодно, 4 Гб, 64 Гб, 4 Тб, вам сколько завернуть?) нарезается
кусочками, называемыми страницами. Как правило размер страницы - от 512 байт до 64 Кб. Так как реальной оперативной
памяти у нас несколько меньше, чем виртуальной (сравните 256 Мб и 64 Гб), то в оперативной памяти находится только
некоторый набор страниц.
</p>
<table align=center>
<tr>
<td>Физическая память
</td>
<td>Виртуальная память
</td>
</tr>
<tr>
<td>
<table border=2 align=center>
<tr><td>
Страница 4
</td></tr>
<tr><td>
Страница 2
</td></tr>
<tr><td>
Страница 1
</td></tr>
<tr><td>
Страница 7
</td></tr>
<tr><td>
Страница 3
</td></tr>
</table>
</td>
<td>
<table border=2 align=center>
<tr><td>
Страница N
</td></tr>
<tr><td>
Страница N-1
</td></tr>
<tr><td>
Страница ...
</td></tr>
<tr><td>
Страница 4
</td></tr>
<tr><td>
Страница 3
</td></tr>
<tr><td>
Страница 2
</td></tr>
<tr><td>
Страница 1
</td></tr>
</table>
</td>
</tr>
</table>
<p>
Все это дает нам один большой плюс - мы можем постранично хранить содержимое памяти на любом носителе и только
используемые на данный момент страницы - в оперативной памяти. Это и называется пейджингом - неиспользуемые
страницы скидываются на HDD и ждут своего часа.
</p>
<p>
Единственное "" - все обращения программы к виртуальной памяти надо транслировать на память реальную! Именно
этому и служат дескрипторы страниц. Дескрипторы страниц содержат информацию о занятости страницы и хранят
соответствие между виртуальными адресами и номером нужной страницы. Ну а поскольку любая трансляция - это потеря
времени, то, чтобы это время было незначительным, механизмы страничной организации памяти встроены прямо в процессоры.
Но об этом чуть попозже.
</p>

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

<p>
В этом случае программе (или ее части!) предоставляется сегмент памяти, в котором адреса начинаются прямо с 0 и
размер сегмента может быть любым (ограничение - фантазия, в случае программной реализации, и архитектура процессора
в случае реализации железной).
</p>
<p>
В чем отличие от страничной организации. Отличие в первую очередь в том, что сегмент может иметь <i>лю</i>
размер. Плюс к этому, как я уже написал выше, сегмент создает новое виртуальное адресное пространство, где свободны
абсолютно любые адреса. Это очень полезно, так как это способствует защите потоков/процессов друг от друга. Ведь
если каждому потоку выделить свой сегмент, то куда бы он не обращался, это будет обращение в пределах его сегмента и
никуда более (системные вызовы пока опустим)!
</p>
<p>
В целом сегменты очень способствуют одной очень важной функции - отделении мух от котлет. Это для нас очень важно,
поскольку смешивание разнородных данных всегда чревато какими-либо проблемами. Так, мы можем выделить данные в один
сегмент, а код в другой и выставить соответствующие флаги - данные для чтения/записи, а код на чтение и запуск.
</p>
<p>
Однако с чистыми сегментами возникает проблема фрагментации памяти. Посмотрите:
<table align=center border=1>
<tr>
<td width=150>
Момент времени Х.
</td>
<td width=150>
Момент времени Х+1.
</td>
<td width=150>
Момент времени Х+2.
</td>
<td width=150>
Момент времени Х+3.
</td>
</tr>
<tr>
<td width=150>
<table border=2>
<tr><td height=60 bgcolor=#00FF00>
Куча свободного места
</tr></td>
<tr><td height=30 bgcolor=#FF0000>
Сегмент 3
</tr></td>
<tr><td height=40 bgcolor=#FF0000>
Сегмент 2
</tr></td>
<tr><td height=20 bgcolor=#FF0000>
Сегмент 1
</tr></td>
<tr><td height=25 bgcolor=#FF0000>
Сегмент 0
</tr></td>
</table>
</td>
<td width=150>
<table border=2>
<tr><td height=60 bgcolor=#00FF00>
Куча свободного места
</tr></td>
<tr><td height=30 bgcolor=#FF0000>
Сегмент 3
</tr></td>
<tr><td height=40 bgcolor=#00FF00>
Вполне свободное местечко
</tr></td>
<tr><td height=20 bgcolor=#FF0000>
Сегмент 1
</tr></td>
<tr><td height=25 bgcolor=#FF0000>
Сегмент 0
</tr></td>
</table>
</td>
<td width=150>
<table border=2>
<tr><td height=10 bgcolor=#00FF00>

</tr></td>
<tr><td height=50 bgcolor=#FF0000>
Сегмент 4
</tr></td>
<tr><td height=30 bgcolor=#FF0000>
Сегмент 3
</tr></td>
<tr><td height=40 bgcolor=#00FF00>
Вполне свободное местечко
</tr></td>
<tr><td height=20 bgcolor=#FF0000>
Сегмент 1
</tr></td>
<tr><td height=25 bgcolor=#FF0000>
Сегмент 0
</tr></td>
</table>
</td>
<td width=150>
<table border=2>
<tr><td height=10 bgcolor=#00FF00>

</tr></td>
<tr><td height=50 bgcolor=#FF0000>
Сегмент 4
</tr></td>
<tr><td height=30 bgcolor=#FF0000>
Сегмент 3
</tr></td>
<tr><td height=20 bgcolor=#00FF00>
Свободное место.
</tr></td>
<tr><td height=20 bgcolor=#FF0000>
Сегмент 5
</tr></td>
<tr><td height=20 bgcolor=#FF0000>
Сегмент 1
</tr></td>
<tr><td height=25 bgcolor=#00FF00>
Свободная память.
</tr></td>
</table>
</td>
</tr>
<tr>
<td width=150>
Сегменты только что были загружены в память и аккуратно расположены в ней.
</td>
<td width=150>
Вдруг выяснилось, что кое-какие сегменты нам сейчас ненужны (например, программа завершила работу)
</td>
<td width=150>
А пользователь запустил новую программу. Места в дырке от второго сегмента ей мало.
</td>
<td width=150>
Закрыл одну, и запустил другую.
</td>
</tr>
</table>
</p>
<p>
Думаю, получившаяся картинка в комментариях не нуждается - все очевидно. Довольно быстро мы можем получить
множество маленьких дырок в памяти, которые ни туда и ни сюда - нормальный сегмент программы туда не поместится, а
в то же время память не используется. Плохо. Надо производить перераспределене сегментов в памяти. А это не такая уж
шустрая операция.
</p>

Mini-summary

<p>
Сравнивать два вышеприведенныхспособа организации памяти вообще говоря некорректно. Они изначально преследуют
совершенно разные цели. Страничная организация памяти была придумана ради того, чтобы получить большое линейное
адресное пространство без добавления новой физической памяти и освободить программистов от необходимости придумывать
методики замещения одних программных блоков другими. Основная цель сегментой организации памяти - обеспечить четкое
разграничение программ и данных на логически независимые адресные пространства, а также облегчить совместный доступ
к памяти и улучшить защиту.
</p>

А если их скрестить?

<p>
Впервые попытка объединить сегментацию со страничной организацией памяти была предпринята создателями системы MULTICS.
В системе MULTICS адрес был 34-разрядным, его структура:
<table border=2 bgcolor=#FFFF00>
<tr>
<td width=270>
Номер сегмента (<tt>18</tt> бит)
</td>
<td width=94>
Номер страницы (<tt>6</tt>)
</td>
<td width=150>
Смещение внутри страницы (<tt>10</tt>)
</td>
</tr>
</table>
</p>
<p>
Общая схема получения физического адреса из виртуального получается такой:
<table border=2>
<tr>
<td align=center>
<tt>Номер <br>
\/</tt>
<table border=0 width=100%>
<tr height=100 bgcolor=#FFFF00><td>&nbsp
</td></tr>
<tr bgcolor=#FF0000><td>
Дескриптор сегмента
</td><td bgcolor=#00FF00><tt>>></tt></td></tr>
<tr height=50 bgcolor=#FFFF00><td>&nbsp
</td></tr>
</table>
</td>
<td align=center>
<tt>Номер <br>
\/</tt>
<table border=0 width=100%>
<tr height=50 bgcolor=#FFFF00><td>&nbsp
</td></tr>
<tr bgcolor=#FF0000><td>
Дескриптор страницы
</td><td bgcolor=#00FF00><tt>>></tt></td></tr>
<tr height=100 bgcolor=#FFFF00><td>&nbsp
</td></tr>
</table>
<td align=center>
<tt>Смещение внутри <br>
\/</tt>
<table border=0 width=100%>
<tr height=70 bgcolor=#FFFF00><td>&nbsp
</td></tr>
<tr bgcolor=#FF0000><td>
Данные
</td></tr>
<tr height=80 bgcolor=#FFFF00><td>&nbsp
</td></tr>
</table>
</td>
</tr>
<tr bgcolor=#00FF00>
<td>
Сегмент дескрипторов
</td>
<td>
Таблица страниц
</td>
<td>
Страница
</td>
</tr>
</table>
</p>
<p>
Что-то нынче очень цветастый выпуск получается! Вы не заметили?
</p>
<p>
Такая схема, комбинирует достоинства сегментной и страничной виртуальной памяти, но имеет серьезный недостаток -
приходится туда-сюда все вертеть через дескрипторы, в общем это не очень хорошо сказывается на производительноти.
Хотя, это не трагично.
</p>

x86

<p>
Хотел написать поподробнее о реализации сегментов и страничек в современных x86 процессорах, но, глянув в <a href='http://www.osrc.info/content.php?article.8'>четвертый </a>, понял, что добавить мне практически нечего. Те же самые <tt>GDT</tt> и <tt>LDT</tt>.
</p>
<p>
В целом, можно добавить, что страничная организация поддерживается железом почти на всех платформах, чего не скажешь
о сегментной.
</p>

Заключение

<p>
Кхе. А тогда получается, что более мне добавить нечего. Можно было, конечно, написать кое-чего про алгоритмы замещения
страниц, но честно говоря, это слишком просто для простых алгоритмов, а более сложные алгоритмы конечно интерсны, но
там довольно много грузящей математики. Поэтому не стоит. Я и так в последнее время оказывал излишне высокое давление
на ваш мозг (одна Ext 2/3 чего стоила! , поэтому лишний раз злоупотреблять не буду.
</p>
<p>
Можно еще было бы рассказать о том как ядро операционной системы может распределять память, но у меня прорва
недоделанных дел осталась с прошлой недели, извините, не могу. Да это и не так интересно.
</p>
<p>
Будем считать тему с памятью закрытой, хотя, если у вас остались некоторые вопросы, задавайте на форуме, я с радостью отвечу. Следующий выпуск подготовит Олег, выйдет он, как обычно, в пятницу. Тема... А впрочем, увидите сами. Думаю, вам это будет интересно.
</p>