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

 Среди современных  ОС довольно много систем, использующих  тот или иной способ сборки  при загрузке (связывающий загрузчик). Таким образом устроена, например, Novell Netware. Таким же образом организован ряд систем реального времени, таких как OS-9 или VxWorks. Сборка при загрузке существенно замедляет процесс загрузки программы, но упрощает, с одной стороны, разделение кода, а с другой стороны - разработку программ.

 В системах MS Windows и OS/2 используется способ загрузки, промежуточный между сборкой в момент загрузки и сборкой заранее. Загрузочный модуль в этих системах может быть полностью самодостаточным, а может содержать ссылки на другие модули, называемые DLL (Dynamically Loadable Library - динамически загружаемая библиотека). Самое хорошее в этой схеме то, что модуль, по собственному желанию, может выбирать различные библиотеки. Единственное ограничение состоит в том, что такие библиотеки обязаны быть совместимыми по вызовам.

 Например, программа  CorelDRAW! может импортировать и экспортировать изображения в различных видах, начиная от собственного внутреннего формата .CDR или Windows Bitmap, и кончая сильноупакованным форматом Jpeg или специализированными форматами, вроде Targa-файлов. Импорт и экспорт каждого формата выполняется отдельной DLL.

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

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

 Кроме того, использование DLL сильно замедляет  процесс загрузки программ и  несколько снижает общую производительность  систем с виртуальной памятью.  Системы семейства Unix использующие монолитный загрузочный модуль и/или разделяемые библиотеки, заметно быстрее, чем OS/2 и Windows NT, использующие DLL.

Лекция 13. Кэширование данных. Иерархия запоминающих устройств. Кэш память. Принцип действия кэш-памяти. Проблемы согласования данных. Проблемы отображения  основной памяти в  кэш.

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

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

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

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

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

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

  Кэш-память

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

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

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

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

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

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

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

значение элемента данных;

адрес, который  этот элемент данных имеет в основной памяти;

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

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

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

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

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

t = t1(1 - р) + t2p = (t2 –t1)p + t1

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

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

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

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

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

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

Проблема  согласования данных

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