Сетевые операционные системы

Глава 5. Управление памятью

Продолжение

Разделяемые сегменты памяти

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

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

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

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

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

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

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

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

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

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

Кэширование данных

Иерархия запоминающих устройств

Память вычислительной машины представляет собой иерархию запо-минающих устройств (ЗУ), отличающихся средним временем доступа к дан-ным, объемом и стоимостью хранения одного бита (рис. 5.24). Фундаментом этой пирамиды за-поминающих устройств служит внешняя память, как пра-вило, представляемая жестким диском. Она имеет большой объем (десятки и сотни гигабайт), но ско-рость доступа к данным является невысокой. Время доступа к диску измеряется миллисекундами.

На следующем уровне располагается более быстродействующая (вре-мя доступа равно примерно 10-20 наносекундам) и менее объемная (от де-сятков мегабайт до нескольких гигабайт) оперативная память, реализуемая на относительно мед-ленной динамической памяти DRAM.

Для хранения данных, к которым необходимо обеспечить быстрый доступ, ис-пользуются компактные быстродействующие запоминающие уст-ройства на ос-нове статической памяти SRAM, объем которых составляет от нескольких де-сятков до нескольких сотен килобайт, а время доступа к дан-ным обычно не превышает 8 нс.

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

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

Кэш-память

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

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

Кэш-памятью, или кэшем, часто называют не только способ организа-ции работы двух типов запоминающих устройств, но и одно из устройств - "быстрое" ЗУ.

Оно стоит дороже и, как правило, имеет сравнительно небольшой объем. "Мед-ленное" ЗУ далее будем называть основной памятью, противо-поставляя ее вспо-могательной кэш-памяти.

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

Принцип действия кэш-памяти

Рассмотрим одну из возможных схем кэширования (рис. 5.25). Со-держимое кэш-памяти представляет собой совокупность записей обо всех за-груженных в нее элементах данных из основной памяти. Каждая запись об элементе данных включает в себя:

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

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

если данные обнаруживаются в кэш-памяти, то есть произошло кэш-попада-ние (cache-hit), они считываются из нее и результат передается ис-точнику за-проса;
если нужные данные отсутствуют в кзш-памяти, то есть произошел кэш-про-мах (cache-miss), они считываются из основной памяти, передаются ис-точни-ку запроса и одновременно с этим копируются в кэш-память.

Интуитивно понятно, что эффективность кэширования зависит от ве-роятности попадания в кэш. Покажем это путем нахождения зависимости среднего време-ни доступа к основной памяти от вероятности кэш-попаданий. Пусть имеется ос-новное запоминающее устройство со средним временем доступа к данным tl и кэш-память, имеющая время доступа t2, очевидно, что t2<tl. Пусть t - среднее время доступа к данным в системе с кэш-памятью, а р - вероятность кэш-попа-дания. По формуле полной вероятности имеем:

t = t1(l - р) + t2p - (t2 -t1)p + t1

Среднее время доступа к данным в системе с кэш-памятью линейно зависит от вероятности попадания в кэш и изменяется от среднего времени доступа в ос-новное запоминающее устройство tl при р=0 до среднего време-ни доступа непо-средственно в кэш-память t2 при р=1. Отсюда видно, что ис-пользование кэш-па-мяти имеет смысл только при высокой вероятности кэш-попадания.

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

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

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

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

Продолжение следует...

В следующем выпуске:

• Проблема согласования данных
• Способы отображения основной памяти на кэш
• Схемы выполнения запросов в системах с кэш-памятью