\section[Базовая адpесация]{Системы с базовой виртуальной адресацией}

Как уже говорилось, в системах с открытой памятью
возникают большие сложности при организации многозадачной работы.
Чтобы устранить их, необходимо предоставлять каждой задаче
свое виртуальное адресное пространство. Наиболее простым способом
организовать различные адресные пространства является так называемая
\term{базовая адресация}. По-видимому, это исторически наиболее ранний
способ.

Вы можете заметить, что термин \term{базовая адресация} уже занят
-- мы называли таким образом адресацию по схеме \verb"reg[offset]".
Дело в том, что метод, о котором сейчас идет речь, состоит в формировании
адреса по той же схеме. Отличие состоит в том, что регистр, относительно
которого происходит адресация, не доступен прикладной программе. Кроме того,
его значение прибавляется ко {\it всем} адресам, в том числе к <<абсолютным>>
адресным ссылкам или переменным типа указатель. По существу, такая адресация
является способом организации виртуального адресного пространства.
Действительно, распечатав значение указателя, вы увидите число,
равное, например, \verb"0x000A25". Однако такой адрес будет соответствовать
физическому адресу \verb"BASE + 0x000A25" и меняться вместе со значением
регистра \verb"BASE".

{\small
Если говоpить о pазнице между двумя значениями слов <<базовая адpесация>>,
нельзя не упомянуть о поучительной истоpии, связанной с упpавлением памятью
в системах линии \machname{IBM System 360}.

В этих машинах не было аппаpатных сpедств упpавления памятью и все пpогpаммы
pазделяли общее виpтуальное адpесное пpостpанство, совпадающее с физическим.
Адpесные ссылки в пpогpамме задавались 12-битовым смещением относительно
базового pегистpа. В качестве базового pегистpа мог использоваться,
в пpинципе, любой из 16 32-битных pегистpов общего назначения.
Пpедполагалось, что пользовательские пpогpаммы не модифициpуют базовый
pегистp, поэтому можно загpужать их с pазличных адpесов пpосто пеpенастpаивая
значение этого pегистpа. Таким обpазом была pеализована одновpеменная загpузка
многих пpогpамм в многозадачной системе \sysname{OS/360}.

Однако после загpузки пpогpамму уже нельзя было пеpемещать по памяти:
напpимеp пpи вызове подпpогpаммы адpес возвpата сохpаняется в стеке
в виде абсолютного 24-битного адpеса\footnote{В \machname{System 360}
под адpес отводилось 32-pазpядное слово, но использовались только 24 младших
бита адpеса. В \machname{System 370} адpес стал полностью 32-pазpядным.}
и пpи возвpате базовый pегистp не используется. Аналогично, базовый pегистp
не используется пpи ссылках на паpаметpы подпpогpамм языка \progname{FORTRAN},
пpи pаботе с указателями в \progname{PL/I} и т.д..
Пеpемещение пpогpаммы, даже с пеpенастpойкой базового pегистpа, наpушило бы
все такие ссылки.

Разpаботчики фиpмы \entname{IBM} вскоpе осознали пользу пеpемещения пpогpамм
после их загpузки и попытались как-то pешить эту пpоблему. Очень любопытный
документ <<Preparing to Rollin-Rollout Guideline>>\footnote{К сожалению,
автоpам не удалось найти полного текста этого документа.} описывает действия,
котоpые пpогpамма должна была бы пpедпpинять после пеpемещения. Фактически
пpогpамма должна была найти в своем сегменте данных все абсолютные адpеса и
сама пеpенастpоить их.

Естественно, никто из pазpаботчиков компилятоpов и пpикладного пpогpаммного
обеспечения не собиpался следовать этому pуководству. В pезультате пpоблема
пеpемещения пpогpамм в \sysname{OS/360} не была pешена вплоть до появления
машин \machname{System 370} со стpаничным или стpанично-сегментным диспетчеpом
памяти и ОС \sysname{MVS}.
}

Как правило, машины, использующие базовую адpесацию, имеют два
регистра. Один из регистров задает базу для адресов, второй устанавливает
верхний предел. В системе \machname{ICL1900/Одренок} эти регистры называются
соответственно \verb"BASE" и \verb"DATUM".
Если адрес выходит за границу, установленную значением \verb"DATUM",
возникает \termin{исключительная ситуация}{exception} ошибочной адресации.
Как правило, это приводит к тому, что система принудительно завершает
работу программы.

При помощи этих двух регистров мы сразу решаем две важные проблемы.

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

Во-вторых, мы получаем возможность передвигать адресные
пространства задач по физической памяти так, что сама программа не замечает,
что ее передвинули. За счет этого мы решаем проблему фрагментации памяти
и даем программам возможность наращивать свое адресное пространство.
Действительно, в системе с открытой памятью программа может добавлять себе
память только до тех пор, пока не упрется в начало следующей программы.
После этого мы должны либо говорить, что памяти нет, либо мириться с тем,
что программа может занимать несмежные области физического адресного
пространства. Второе решение резко усложняет управление памятью, как со
стороны системы, так и со стороны программы, и часто оказывается неприемлемым
(подробнее связанные с этим проблемы обсуждаются в разделе \ref{OpenMemory}).
В случае же базовой адресации мы можем просто сдвинуть мешающую нам программу
вверх по физическим адресам.

Часто системы, работающие на таких архитектурах, умеют сбрасывать
на диск те задачи, которые долго не будут исполняться. Это самая простая из
форм \termint{своппинга}{swapping}{обмен}\footnote{Термин <<страничный обмен>>
довольно широко распространен, но в данном случае его использование звучало
бы неправильно}.

В современных системах базовая виртуальная адресация используется
редко. Дело не в том, что она плоха, а в том, что более сложные методы,
такие как сегментная и страничная трансляция адресов, оказались намного
лучше. Часто под словами <<виpтуальная память>> подpазумевают именно
сегментную или стpаничную адpесацию.

\section[Виpтуальная память]{Сегментная и страничная виртуальная память}

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

Такая адресация реализуется аппаратно. Процессор, как правило,
имеет специальное устройство, называемое \term{диспетчером памяти}.
В некоторых процессорах, например в \machname{MC68020} или \machname{MC68030}
или в некоторых RISC-системах, это устройство реализовано на отдельном
кристалле; в других, таких как \machname{i386} или \machname{Alpha},
диспетчер памяти интегрирован в процессор.

 Диспетчер памяти содержит регистр -- указатель на
\term{таблицу трансляции}.
Эта таблица размещается где-то в физической памяти. Ее элементами
являются \term{дескрипторы} каждой страницы/сегмента. Такой дескриптор
содержит права доступа к странице, признак присутствия этой страницы в
памяти и физический адрес страницы/сегмента. Для сегментов в дескрипторе
также хранится длина сегмента.

Как правило, диспетчер памяти имеет также \termin{кэш}{cache}
дескрипторов -- быструю память с ассоциативным доступом.
В этой памяти хранятся дескрипторы часто используемых страниц.

Алгоритм доступа к памяти по виртуальному адресу \verb"page:offset"
получается следующим:
\begin{itemize}
\item Проверить, существует ли страница \verb"page" вообще.
Например, у машин семейства VAX адресное пространство {\it может} состоять
из 8М страниц, что
соответствует 4 Гбайтам, но реальные программы используют намного меньше
памяти, и размеры их таблиц трансляции соответственно уменьшаются.
Естественно, про страницу, для которой нет соответствующего элемента таблицы,
можно сказать, что ее не существует.
Такая проверка осуществляется простым сравнением номера страницы с длиной
таблицы трансляции.
Если страницы не существует, возникает
\termin{особая ситуация ошибки сегментации}{segmentation violation}
\item Попытаться найти дескриптор страницы в кэше.
\item Если его нет в кэше, загрузить дескриптор из таблицы в памяти.
\item Проверить, имеет ли процесс соответствующее право доступа к странице.
Иначе также возникает ошибка сегментации.
\item Проверить, находится ли страница в оперативной памяти. Если ее там
нет, возникает \term{особая ситуация отсутствия страницы}
или \termin{стpаничный отказ}{page fault}.
Как правило, реакция на нее состоит в том, что вызывается специальная
программа-обработчик (\term{trap} -- ловушка), которая подкачивает требуемую
страницу с диска. В многозадачных системах во время такой подкачки может
исполняться другой процесс.
\item Если страница есть в памяти, взять из ее дескриптора
физический адрес \verb"phys_addr".
\item Если мы имеем дело с сегментной адресацией, сравнить смещение в
сегменте с длиной этого сегмента. Если смещение оказалось больше, также
возникает ошибка сегментации.
\item Произвести доступ к памяти по адресу \verb"phys_addr[offset]".
\end{itemize}

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

{\bf Во-первых,} мы можем связать с каждой задачей свою таблицу
трансляции, а значит и свое виртуальное адресное пространство.
Благодаря этому даже в многозадачных ОС мы можем пользоваться
абсолютным загрузчиком.
Кроме того, программы оказываются изолированными друг от друга,
и мы можем обеспечить их безопасность.

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

\note{
Это не один регистр, а, как минимум, два -- указатель на таблицу и ее длина.
В большинстве современных процессоров диспетчер памяти еще сложнее.
Часто он работает с несколькими таблицами, может иметь дополнительные
управляющие регистры и т.д.
}

{\bf Во-вторых,} мы можем сбрасывать на диск редко используемые
области виртуальной памяти программ -- не всю программу целиком, а только ее
часть. Кроме того, в отличие от оверлеев, программа вообще не обязана знать,
какая ее часть может быть сброшена.

\note{
Другое дело, что в системах реального
времени программе может быть нужно, чтобы определенные ее части никогда
не сбрасывались на диск. Действительно, система реального времени
{\it обязана} гарантировать время реакции, и это гарантированное время обычно
намного меньше времени доступа к диску. Естественно, что код, обрабатывающий
событие, и используемые при этом данные должны быть всегда в памяти.
}

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

\note{
Так, в \sysname{VAX/VMS} свободная память отслеживается при помощи
битовой маски физических страниц. В этой маске свободной странице
соответствует 1, а занятой -- 0. Если кому-то нужна страница, система
просто ищет в этой маске установленный бит. Если учесть, что \machname{VAX}
имеет специальную команду для поиска установленного бита в массиве,
все работает очень быстро и просто.

В результате виртуальное пространство программы может оказаться
отображено на физические адреса очень причудливым образом, но это никого
не волнует -- скорость доступа ко всем страницам одинакова.
}

{\bf В-четвертых,} система может обеспечивать не только защиту
программ друг от друга, но и защиту программы от самой себя -- например,
от ошибочной записи данных на место кода.

{\bf В-пятых,} различные задачи могут использовать общие области
памяти для взаимодействия или, скажем, просто для того, чтобы работать с
одной копией библиотеки подпрограмм.

Перечисленные преимущества настолько серьезны, что считается
невозможным реализовать многозадачную систему общего назначения, такую
как \sysname{UNIX} или \sysname{VMS} (Virtual Memory System) на машинах
без диспетчера памяти.

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

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

Что будет считаться <<слишком>> большим или, наоборот, маленьким,
в действительности зависит от среднего количества памяти, используемого
программой. Так, если вы работаете со старой \sysname{UNIX}-системой
и пользуетесь только программами типа \verb"ls", \verb"grep" или \verb"sed",
а редактор \verb"vi" считается чем-то почти сверхъестественным, то
средний размер ваших программ будет измеряться десятками килобайт и редко
выходить за сотню. Если же вы используете современные графические оконные
интерфейсы, систему \sysname{X Windows}, \verb"emacs" и прочие красоты,
то типичная программа требует около мегабайта памяти, а некоторые и по
несколько десятков. Казалось бы, размер страницы при этом также должен
измениться на два-три порядка. На самом деле, здесь в игру вступает еще один
параметр -- размер сектора на диске, с которого осуществляется
подкачка\ellipsis

В реальных системах размер страницы меняется от 512 байт у машин
семейства \machname{VAX} до нескольких килобайт. Например, \sysname{i3/486}
имеет страницу размером 4 К. Некоторые диспетчеры памяти, например у
\machname{MC6801/2/30}, имеют переменный размер страницы -- в том смысле,
что система при запуске программирует диспетчер и устанавливает, помимо
прочего, этот размер, и дальше работает со страницами выбранного размера.
У процессора \machname{i860} размер страницы переключается между 4 К и
4 Мбайтами.

С сегментными диспетчерами памяти ситуация  сложнее. С одной стороны,
хочется, чтобы один программный модуль влезал в сегмент, поэтому сегменты
обычно делают большими, от 32К и более. С другой стороны, хочется, чтобы
в адресном пространстве можно было сделать много сегментов. Кроме того,
может возникнуть проблема: как быть с {\it большими} неразделимыми объектами,
например хэш-таблицами компиляторов, под которые часто выделяются сотни
килобайт.
С третьей стороны, при подкачке сегментов с диска не хочется качать за
один раз много данных.

Третье обстоятельство вынуждает многих разработчиков идти на
двухступенчатую виртуальную память -- сегментную адресацию, в которой
каждый сегмент, в свою очередь, разбит на страницы. Это дает ряд мелких
преимуществ, например, позволяет раздавать права доступа сегментам,
а подкачку с диска осуществлять постранично. Таким образом организована
виртуальная память в \machname{IBM System 370} и ряде других больших
компьютеров, а также в \machname{i3/486}.
Правда, в последнем виртуальная память используется несколько странным образом.

{\small
Вообще говоря, \machname{i386} может работать с двумя типами
адресов:
\begin{itemize}
\item 32-разрядным адресом, в котором 16 бит задают смещение в сегменте,
14 бит -- номер сегмента, и 2 бита используются для разных загадочных целей.
При этом размер сегмента не более 64К, а общий  объем виртуальной памяти
не превышает 1 Гбайта.
\item 48-разрядным адресом, в котором смещение в сегменте занимает 32 бита.
В этом случае размер сегмента может быть до 4 Гбайт, а общий объем виртуальной
памяти до $2^{48}$ байт.
\end{itemize}
В обоих случаях сегмент может быть разбит на страницы по 4 К.
При этом сегментная часть адреса и его смещение лежат в разных регистрах,
и с ними можно работать раздельно. В \term{реальном режиме} возможность
такой работы порождает весь зоопарк <<моделей памяти>>, с которыми знакомы те,
кто писал на C для \sysname{MS~DOS}. В случае \machname{i386} большинство
систем программирования выделяют программе один сегмент с 32-разрядным
смещением, и программа живет там так, будто это обычная машина с 32-разрядным
линейным адресным пространством.
Так поступают все известные авторам реализации \sysname{Unix} для
\machname{i386}, ряд так называемых \termin{расширителей ДОС}{DOS extenders},
\sysname{Oberon/386}, \sysname{Novell~Netware} и т.д.

С другой стороны, \sysname{MS~Windows} в \verb"enhanced" режиме используют
\machname{i386} именно как машину с двухслойной сегментно-страничной
адресацией, то есть загружают программу по сегментам, и права доступа ей
выдают на сегменты, а подкачку с диска делают постранично. Это обусловлено
не столько настоящей потребностью в сегментации, сколько требованием
совместимости со \verb"standard" режимом, в котором \sysname{MS~Windows}
работают на процессоре \machname{80286}
}

\section{Страничный обмен}\label{swapping}

\term{Подкачка}, или \termint{своппинг}{swapping}{обмен}, --
это процесс сброса редко используемых областей виртуального
адресного пространства программы на диск или другое устройство массовой
памяти. Такая массовая память всегда намного дешевле оперативной, хотя и
намного медленнее. Во многих учебниках по ОС приводятся таблицы следующего
вида:

\begin{table}[h]
\newlength{\lengtha}
\settowidth{\lengtha}{доступа}
\newsavebox{\ColHeader}
\sbox{\ColHeader}{\parbox[t]{\lengtha}{\centering Время доступа}}

\begin{tabularx}{\textwidth}{|X|c|X|X|}
\hline
Тип памяти         & \usebox{\ColHeader} & Цена 1Мбайта & Способ использования\\ \hline
Статическая память & 15нс          & \$200  & Регистры, кэш-память\\
Динамическая память & 70 нс         & \$30 {\small\sl (4Mb~SIMM)\/} & Основная память\\
Жесткие магнитные диски & 1-10 мс   & \$3 {\small\sl (1.2Gb~EIDE)\/} & Файловые системы, устройства своппинга\\
Магнитные ленты &     секунды       & \$0.025 {\small\sl (8mm~Exabyte)\/} &%
Устройства резервного копирования\\ \hline
\end{tabularx}
\end{table}

При разработке системы всегда есть желание сделать память как можно
быстрее. С другой стороны, потребности в памяти очень велики и постоянно
растут. Современные персональные системы имеют около 500 Мбайт дисковой памяти,
и этого часто оказывается недостаточно, особенно если идет работа с
Multimedia или просто с высококачественными изображениями.

{\small
Существует эмпирическое наблюдение, что {\it любой} объем дисковой
памяти будет полностью занят за две недели. Жизненный опыт обоих авторов
подтверждает его.
}

Очевидно, что система с 500 М статического ОЗУ будет иметь стоимость,
скажем так, совершенно не персональную, не говоря уже о габаритах,
потребляемой мощности и прочем. К счастью, далеко не все, что хранится
в памяти системы, используется одновременно. В каждый заданный момент
исполняется только часть программного обеспечения, и оно работает только
с частью данных.

Статистика утверждает, что в пределах одной программы 90\% времени
исполняется код, который занимает 10\% места, а остальные 90\% кода
исполняются только 10\% времени. Для данных разница в частоте использования,
по-видимому, не столь резкая, но также существует.

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

Естественно, для того чтобы автоматизировать процесс удаления
<<барахла>> -- редко используемых данных и программ, -- мы должны
иметь какой-то легко формализуемый критерий, по которому
определяется, какие данные считаются редко используемыми.
Для ручного переноса данных критерий очевиден -- нужно удалять%
\footnote{Вообще говоря, под \termin{удалением}{removal} почему-то
обычно понимают разрушение данных. В данном разделе мы временно
вернем этому слову исходный смысл: \term{удалить} что-либо будет означать:
перенести это на более медленный физический носитель, из кэша -- в ОЗУ,
из ОЗУ -- на диск, с диска -- на магнитную ленту или другое дешевое и
медленное устройство массовой памяти.}
то, что дольше всего не будет использоваться в будущем. Конечно,
любые предположения о будущем имеют условный характер, все может
неожиданно измениться. Тем не менее, обычно человек располагает такой
информацией о системе и ее использовании, которая принципиально
недоступна самой этой системе.
А для автомата будущее неизвестно, и он должен делать догадки о будущем
только на основании данных об использовании системы в прошлом.

Алгоритм автомата должен быть как можно более простым. Например,
кэш-контроллер обычно делается на основе <<жесткой логики>>, потому что
он должен быть очень быстрым. Даже микропрограммный автомат с точки зрения
скорости оказывается недопустимым, не говоря уже о сложных алгоритмах,
использующих динамические структуры данных. Для алгоритма управления
страничной подкачкой простота также важна -- очень не хочется, чтобы
большую часть времени система занималась размышлениями о том, какую
страницу можно сбросить на диск.
Сравните с армейским афоризмом: <<командир должен уметь принимать
{\it быстрое} решение, а если оно случайно окажется правильным,
то это будет вообще замечательно>> (цит. по \cite{RH}).

Один простой критерий выбора очевиден -- при прочих равных условиях,
в первую очередь, мы должны выбирать в качестве \termin{жертвы}{victim}
для удаления тот объект, который не был изменен за время жизни в
быстрой памяти. Действительно, вы скорее удалите с винчестера саму игрушку
(если у вас есть ее копия на дискетах), чем файлы сохранения!

Самый простой алгоритм -- выкидывать случайно выбранный объект.
Такой алгоритм хорош тем, что очень прост -- не надо набирать никакой
статистики о частоте использования и т.д. Очевидно, при этом удаленный
объект совершенно необязательно будет ненужным\ellipsis

Можно также удалять то, что дольше всего находится
в данном слое памяти. Это называется алгоритмом \termint{FIFO}%
{First In - First Out}{первый вошел - первый вышел}.
Видно, что это уже чуть сложнее случайного
удаления -- нужно запоминать, когда мы что загружали.
Понятно также, что это лишь очень грубое приближение к тому, что нам
требуется.

Наиболее честным будет удалять тот объект, к которому дольше всего
не было обращений в прошлом \termin{LRU}{Least Recently Used}.
Это требует набора статистики обо всех обращениях. Для страничного
или сегментного управления памятью это также
требует аппаратной поддержки -- мы ведь не в состоянии программно
отслеживать все обращения ко всем страницам без катастрофического
падения производительности системы.

Такая поддержка на практике должна состоять в том, что диспетчер памяти
поддерживает в дескрипторе каждой страницы счетчик обращений, и при каждой
операции чтения или записи над этой страницей увеличивает этот счетчик на
единицу. Это требует довольно больших накладных расходов -- в ряде работ
(\cite{Crac}) утверждается, что они будут недопустимо большими. Поэтому
такая техника применяется только в экспериментальных установках, используемых
для оценки производительности тех или иных алгоритмов. Она также применяется
в некоторых контроллерах кэш-памяти и программно реализованных дисковых
кэшах.

Остроумным приближением к алгоритму LRU является так называемый
\term{clock}-алгоритм. Он состоит в следующем:
\begin{itemize}
\item Дескриптор каждой страницы содержит бит, указывающий, что к данной
странице было обращение. Этот бит иногда называют clock-битом.
\item При первом обращении к странице, в которой clock-бит был сброшен,
диспетчер памяти устанавливает этот бит.
\item Программа, занимающаяся поиском жертвы, циклически просматривает
все дескрипторы страниц. Если clock-бит сброшен, данная страница объявляется
жертвой, и просмотр заканчивается -- до появления потребности в новой
странице. Если clock-бит установлен, то программа сбрасывает его и
продолжает поиск.
\end{itemize}

Название \term{clock}, по-видимому, происходит от внешнего сходства
процесса циклического просмотра с движением стрелки часов. Подумав,
можно убедиться, что вероятность оказаться жертвой для страницы, к
которой часто происходят обращения, существенно ниже.

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

Экспериментальные исследования показывают любопытный факт:
реальная производительность системы довольно слабо зависит от применяемого
алгоритма поиска жертвы. Статистика исполнения реальных программ
говорит о том, что каждая программа имеет некоторый набор страниц,
называемый \term{рабочим множеством}, который ей в данный момент
{\it действительно} нужен. Размер такого набора сильно зависит от
алгоритма программы, он изменяется на различных этапах исполнения и т.д.,
но в большинство моментов мы можем довольно точно указать его. Если
все страницы рабочего набора попадают в память, то частота ошибок отсутствия
страницы резко снижается.
В случае, когда памяти не хватает, программе почти на каждой команде
требуется новая страница, и производительность системы катастрофически --
в тысячи раз -- падает. В случае машин типа \machname{IBM PC/AT386} с
дисковым контроллером \machname{IDE},
в которых процессор задействуется при операциях с диском, это может привести,
практически, к блокировке системы. Это состояние по-английски называется
\term{overswap} или \term{thrashing} -- чрезмерный своппинг и является
крайне нежелательным.

В системах коллективного пользования размер памяти часто выбирают так,
чтобы система балансировала где-то между состоянием, когда все программы
держат свое рабочее множество в ОЗУ, и оверсвопом. Точное положение точки
балансировки определяется в зависимости от соотношения скорости процессора
со скоростью обмена с диском и с потребностями прикладных программ.
Во многих старых учебниках рекомендуется подбирать объем памяти так,
чтобы канал дискового обмена был загружен на 50\% \cite{Crac}.

Еще одно эмпирическое правило приводится в документации фирмы
\entname{Amdahl}: сбалансированная система должна иметь
по мегабайту памяти на каждый MIPS (Million of Instructions Per Second --
миллион операций в секунду) производительности центрального процессора.
Если система не использует память, определенную по этой формуле, есть
основания считать, что процессор также работает с недогрузкой.
Иными словами, это означает, что вы купили слишком мощный для ваших
целей процессор и заплатили лишние деньги.

Это правило было выработано на основе опыта эксплуатации больших компьютеров
четвертого поколения, в основном на задачах управления базами данных.
Скорость дисковой подсистемы в этих машинах была примерно сравнима с
дисковыми контроллерами современных персоналок, поэтому аналогичный
критерий оценки применим и к ПК, особенно работающим под управлением
систем с виртуальной памятью -- \sysname{OS/2}, \sysname{Windows~NT}
и системами семейства \sysname{Unix}.

В соответствии с этим правилом, машины с процессором \machname{i486}
должны иметь 8-16 мегабайт памяти, а с процессором \machname{Pentium} --
от 20 и более. Эти цифры подтверждаются опытом реальной эксплуатации
систем на основе соответствующих процессоров.

В <<персональных>> операционных системах, таких как \sysname{Windows~3.x}
и \sysname{Windows~95}, ситуация с памятью, и вообще с производительностью,
несколько иная.

Дело в том, что пользователя ПК интересует не производительность в целом, а
только время реакции текстового редактора или электронных таблиц на
нажатие кнопки. С одной стороны, это вынуждает устанавливать в систему
больше памяти, потому что страничный обмен во время отработки команды в
редакторе существенно снижает время реакции и, соответственно, наблюдаемую
скорость системы. Поэтому память часто подбирают так, чтобы используемые
программы и их данные входили в память целиком, а не только рабочие
множества. Но, так как пользователь обычно работает только с одной
программой, часто оказывается возможным ограничиться 4 или 8 мегабайтами
памяти. С другой стороны, низкокачественные прикладные программы часто
вынуждают пользователей покупать чрезмерно мощные процессоры, чтобы обеспечить
приемлемое время реакции. Так например, редактор \progname{MS~Word 6.0}
требует процессора класса \machname{i486/Pentium} для редактирования
текстов -- работы, с которой вполне справляется даже 8-разрядный
процессор типа \machname{Z-80}.

Поэтому во многих конторах часто можно увидеть машину класса
\machname{Pentium} с 8 мегабайтами памяти, используемую только
для печати бумажек, то есть очень сильно разбалансированную и очень
сильно недогруженную по стандартам систем общего назначения.


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