Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ѕ–»ћ≈„јЌ»≈. ”же достаточно давно пользователи столкнулись с проблемой размещени€ в пам€ти программы, размер которой превышает имеющуюс€ в наличии свободную пам€ть




”же достаточно давно пользователи столкнулись с проблемой размещени€ в пам€ти программы, размер которой превышает имеющуюс€ в наличии свободную пам€ть. ќдним из первых решений было разбиение программы на части, называемые оверле€ми.  огда первый оверлей заканчивал свое выполнение, он вызывал другой оверлей. ¬се оверлеи хранились на диске и перемещались между пам€тью и диском средствами операционной системы на основании €вных директив программиста, содержащихс€ в программе. Ётот способ, несмотр€ на внешнее сходство, имеет принципиальное отличие от виртуальной пам€ти, заключающеес€ в том, что разбиение программы на части и планирование их загрузки в оперативную пам€ть должны были выполн€тьс€ заранее программистом во врем€ написани€ программы.

¬иртуализаци€ пам€ти может быть осуществлена на основе двух различных подходов:

  • свопинг (swapping) Ч образы процессов выгружаютс€ на диск и возвращаютс€ в оперативную пам€ть целиком;
  • виртуальна€ пам€ть (virtual memory) Ч между оперативной пам€тью и диском перемещаютс€ части (сегменты, страницы и т. п.) образов процессов.

—вопинг представл€ет собой частный случай виртуальной пам€ти и, следовательно, более простой в реализации способ совместного использовани€ оперативной пам€ти и диска. ќднако подкачке свойственна избыточность: когда ќ— решает активизировать процесс, дл€ его выполнени€, как правило, не требуетс€ загружать в оперативную пам€ть все его сегменты полностью Ч достаточно загрузить небольшую часть кодового сегмента с подлежащей выполнению инструкцией и частью сегментов ƒанных, с которыми работает эта инструкци€, а также отвести место под сегмент стека. јналогично при освобождении пам€ти дл€ загрузки нового процесса очень часто вовсе не требуетс€ выгружать другой процесс на диск целиком, достаточно вытеснить на диск только часть его образа. ѕеремещение избыточной информации замедл€ет работу системы, а также приводит к неэффективному использованию пам€ти.  роме того, системы, поддерживающие свопинг, имеют еще один очень существенный недостаток: они не способны загрузить дл€ выполнени€ процесс, виртуальное адресное пространство которого превышает имеющуюс€ в наличии свободную пам€ть.

1 ¬ некоторых современных ќ—, например верси€х UNIX, основанных на коде SVR4, механизм свопинга используетс€ как дополнительный к виртуальной пам€ти, включающийс€ только при серьезных перегрузках системы.

»менно из-за указанных недостатков свопинг как основной механизм управлени€ пам€тью почти не используетс€ в современных ќ—1. Ќа смену ему пришел более совершенный механизм виртуальной пам€ти, который, как уже было сказано, заключаетс€ в том, что при нехватке места в оперативной пам€ти на диск выгружаютс€ только части образов процессов.

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

  • —транична€ виртуальна€ пам€ть организует перемещение данных между пам€тью и диском страницами Ч част€ми виртуального адресного пространства, фиксированного и сравнительно небольшого размера.
  • —егментна€ виртуальна€ пам€ть предусматривает перемещение данных сегментами Ч част€ми виртуального адресного пространства произвольного размера, полученными с учетом смыслового значени€ данных,
  • —егментно-странична€ виртуальна€ пам€ть использует двухуровневое деление: виртуальное адресное пространство делитс€ на сегменты, а затем сегменты дел€тс€ на страницы. ≈диницей перемещени€ данных здесь €вл€етс€ страница. Ётот способ управлени€ пам€тью объедин€ет в себе элементы обоих предыдущих подходов.

ƒл€ временного хранени€ сегментов и страниц на диске отводитс€ либо специальна€ область, либо специальный файл, которые во многих ќ— по традиции продолжают называть областью, или файлом свопинга, хот€ перемещение информации между оперативной пам€тью и диском осуществл€етс€ уже не в форме полного замещени€ одного процесса другим, а част€ми. ƒругое попул€рное название этой области Ч страничный файл (page file, или paging file). “екущий размер страничного файла €вл€етс€ важным параметром, оказывающим вли€ние на возможности операционной системы: чем больше страничный файл, тем больше приложений может одновременно выполн€ть ќ— (при фиксированном размере оперативной пам€ти). ќднако необходимо понимать, что увеличение числа одновременно работающих приложений за счет увеличени€ размера страничного файла замедл€ет их работу, так как значительна€ часть времени при этом тратитс€ на перекачку кодов и данных из оперативной пам€ти на диск и обратно. –азмер страничного файла в современных ќ— €вл€етс€ настраиваемым параметром, который выбираетс€ администратором системы дл€ достижени€ компромисса между уровнем мультипрограммировани€ и быстродействием системы.

—траничное распределение

Ќа рис. 5.12 показана схема страничного распределени€ пам€ти. ¬иртуальное адресное пространство каждого процесса делитс€ на части одинакового, фиксированного дл€ данной системы размера, называемые виртуальными страницами (virtual pages). ¬ общем случае размер виртуального адресного пространства процесса не кратен размеру страницы, поэтому последн€€ страница каждого процесса дополн€етс€ фиктивной областью.

¬с€ оперативна€ пам€ть машины также делитс€ на части такого же размера, называемые физическими страницами (или блоками, или кадрами). –азмер страницы выбираетс€ равным степени двойки: 512, 1024, 4096 байт и т. д. Ёто позвол€ет упростить механизм преобразовани€ адресов.

–ис. 5.12. —траничное распределение пам€ти

ѕри создании процесса ќ— загружает в оперативную пам€ть несколько его виртуальных страниц (начальные страницы кодового сегмента и сегмента данных).  опи€ всего виртуального адресного пространства процесса находитс€ на диске. —межные виртуальные страницы не об€зательно располагаютс€ в смежных физических страницах. ƒл€ каждого процесса операционна€ система создает таблицу страниц Ч информационную структуру, содержащую записи обо всех виртуальных страницах процесса.

«апись таблицы, называема€ дескриптором страницы, включает следующую информацию:

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

ѕризнаки присутстви€, модификации и обращени€ в большинстве моделей современных процессоров устанавливаютс€ аппаратно, схемами процессора при выполнении операции с пам€тью. »нформаци€ из таблиц страниц используетс€ дл€ решени€ вопроса о необходимости перемещени€ той или иной страницы между пам€тью и диском, а также дл€ преобразовани€ виртуального адреса в физический. —ами таблицы страниц, так же как и описываемые ими страницы, размещаютс€ в оперативной пам€ти. јдрес таблицы страниц включаетс€ в контекст соответствующего процесса. ѕри активизации очередного процесса операционна€ система загружает адрес его таблицы страниц в специальный регистр процессора.

ѕри каждом обращении к пам€ти выполн€етс€ поиск номера виртуальной страницы, содержащей требуемый адрес, затем по этому номеру определ€етс€ нужный элемент таблицы страниц, и из него извлекаетс€ описывающа€ страницу информаци€1. ƒалее анализируетс€ признак присутстви€, и, если данна€ виртуальна€ страница находитс€ в оперативной пам€ти, то выполн€етс€ преобразование виртуального адреса в физический, то есть виртуальный адрес замен€етс€ указанным в записи таблицы физическим адресом. ≈сли же нужна€ виртуальна€ страница в данный момент выгружена на диск, то происходит так называемое страничное прерывание. ¬ыполн€ющийс€ процесс переводитс€ в состо€ние ожидани€, и активизируетс€ другой процесс из очереди процессов, наход€щихс€ в состо€нии готовности. ѕараллельно программа обработки страничного прерывани€ находит на диске требуемую виртуальную страницу (дл€ этого операционна€ система должна помнить положение вытесненной страницы в страничном файле диска) и пытаетс€ загрузить ее в оперативную пам€ть. ≈сли в пам€ти имеетс€ свободна€ физическа€ страница, то загрузка выполн€етс€ немедленно, если же свободных страниц нет, то на основании прин€той в данной системе стратегии замещени€ страниц решаетс€ вопрос о том, какую страницу следует выгрузить из оперативной пам€ти.

ѕосле того как выбрана страница, котора€ должна покинуть оперативную пам€ть, обнул€етс€ ее бит присутстви€ и анализируетс€ ее признак модификации. ≈сли выталкиваема€ страница за врем€ последнего пребывани€ в оперативной пам€ти была модифицирована, то ее нова€ верси€ должна быть переписана на диск. ≈сли нет, то принимаетс€ во внимание, что на диске уже имеетс€ предыдуща€ копи€ этой виртуальной страницы, и никакой записи на диск не производитс€. ‘изическа€ страница объ€вл€етс€ свободной. »з соображений безопасности в некоторых системах освобождаема€ страница обнул€етс€, с тем чтобы невозможно было использовать содержимое выгруженной страницы.

1 «десь не учитываетс€ возможность кэшировани€ записей из таблицы страниц, котора€ рассматриваетс€ несколько позже.

ƒл€ хранени€ информации о положении вытесненной страницы в страничном файле ќ— может использовать пол€ таблицы страниц или же другую системную структуру данных (например, дескриптор сегмента при сегментно-страничной организации виртуальной пам€ти).

¬иртуальный адрес при страничном распределении может быть представлен в виде пары (р, sv), где р Ч пор€дковый номер виртуальной страницы процесса (нумераци€ страниц начинаетс€ с 0), a sv Ч смещение в пределах виртуальной страницы. ‘изический адрес также может быть представлен в виде пары (n, sf), где n Ч номер физической страницы, a sf Ч смещение в пределах физической страницы. «адача подсистемы виртуальной пам€ти состоит в отображении (р, sv) в (n, sf).

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

ѕервое из них состоит в том, что объем страницы выбираетс€ равным степени двойки Ч 2k. »з этого следует, что смещение s может быть получено простым отделением k младших разр€дов в двоичной записи адреса, а оставшиес€ старшие разр€ды адреса представл€ют собой двоичную запись номера страницы (при этом неважно, €вл€етс€ страница виртуальной или физической). Ќапример, если размер страницы 1  байт (210), то из двоичной записи адреса 50718 = 101 000 111 0012 можно определить, что он принадлежит странице, номер которой в двоичном выражении равен 102 и смещен относительно ее начала на 1 000 111 0012 байт (рис. 5.13).

–ис. 5.13. ƒвоичное представление адресов

»з рисунка хорошо видно, что номер страницы и ее начальный адрес легко могут быть получены один из другого дополнением или отбрасыванием k нулей, соответствующих смещению. »менно по этой причине часто говор€т, что таблица страниц содержит начальный физический адрес страницы в пам€ти (а не но^ мер физической страницы), хот€ на самом деле в таблице указаны только старшие разр€ды адреса. Ќачальный адрес страницы называетс€ базовым адресом.

¬торое свойство заключаетс€ в том, что в пределах страницы непрерывна€ последовательность виртуальных адресов однозначно отображаетс€ в непрерывную последовательность физических адресов, а значит, смещени€ в виртуальном и физическом адресах sv и sf равны между собой (рис. 5.14).

–ис. 5.14. ѕри отображении виртуального адреса в физический смещение не измен€етс€

ќтсюда следует проста€ схема преобразовани€ виртуального адреса в физический (рис. 5.15). ћладшие разр€ды физического адреса, соответствующие смещению, получаютс€ переносом такого же количества младших разр€дов из виртуального адреса. —таршие разр€ды физического адреса, соответствующие номеру физической страницы, определ€ютс€ из таблицы страниц, в которой указываетс€ соответствие виртуальных и физических страниц.

»так, пусть произошло обращение к пам€ти по некоторому виртуальному адресу. јппаратными схемами процессора выполн€ютс€ следующие действи€:

1. »з специального регистра процессора извлекаетс€ адрес AT таблицы страниц активного процесса. Ќа основании начального адреса таблицы страниц, номера виртуальной страницы р (старшие разр€ды виртуального адреса) и длины отдельной записи в таблице страниц L (системна€ константа) определ€етс€ адрес нужного дескриптора в таблице страниц: a=AT+(pxL).

2. »з этого дескриптора извлекаетс€ номер соответствующей физической страницы Ч n.

3.   номеру физической страницы присоедин€етс€ смещение s (младшие разр€ды виртуального адреса).

“ипична€ машинна€ инструкци€ требует 3-4 обращений к пам€ти (выборка команды, извлечение операндов, запись результата). » при каждом обращении происходит либо преобразование виртуального адреса в физический, либо обработка страничного прерывани€. ¬рем€ выполнени€ этих операций в значительной степени вли€ет на общую производительность вычислительной системы, поэтому столь большое внимание разработчиков удел€етс€ оптимизации виртуальной пам€ти.

–ис. 5.15. —хема преобразовани€ виртуального адреса в физический при страничной организации пам€ти

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

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

ѕри выборе страницы на выгрузку могут быть использованы различные критерии, смысл которых сводитс€ к одному: на диск выталкиваетс€ страница, к которой в будущем начина€ с данного момента дольше всего не будет обращений. ѕоскольку точно предсказать ход вычислительного процесса невозможно, то невозможно точно определить страницу, подлежащую выгрузке. ¬ таких услови€х решение принимаетс€ на основе неких эмпирических критериев, часто основывающихс€ на предположении об инерционности вычислительного процесса. “ак, например, из того, что страница не использовалась долгое врем€, делаетс€ вывод о том, что она, скорее всего, не будет использоватьс€ и в ближайшее врем€. ќднако привлечение критериев такого рода не исключает ситуаций, когда сразу после выгрузки страницы к ней происходит обращение и она снова должна быть загружена в пам€ть. ¬еро€тность таких Ђнапрасныхї перемещений настолько велика, что в некоторых реализаци€х виртуальной пам€ти вообще отказываютс€ от количественных критериев и предпочитают случайный выбор, при котором на диск выгружаетс€ перва€ попавша€с€ страница. ¬озникающее при этом некоторое увеличение интенсивности страничного обмена компенсируетс€ снижением вычислительных затрат на поддержание и анализ критери€ выборки страниц на выгрузку.

Ќаиболее попул€рным критерием выбора страницы на выгрузку €вл€етс€ число обращений к ней за последний период времени. ¬ычисление этого критери€ происходит следующим образом. ќперационна€ система ведет дл€ каждой страницы программный счетчик. «начени€ счетчиков определ€ютс€ значени€ми признаков доступа. ¬с€кий раз, когда происходит обращение к какой-либо странице, процессор устанавливает в единицу признак доступа в относ€щейс€ к данной странице записи таблицы страниц. ќ— периодически просматривает признаки доступа всех страниц во всех существующих в данный момент запис€х таблицы страниц. ≈сли какой-либо признак оказываетс€ равным 1 (было обращение), то система сбрасывает его в 0, увеличива€ при этом на единицу значение св€занного с этой страницей счетчика обращений.  огда возникает необходимость удалить какую-либо страницу из пам€ти, ќ— находит страницу, счетчик обращений которой имеет наименьшее значение. ƒл€ того чтобы критерий учитывал интенсивность обращений за последний период, ќ— с соответствующей периодичностью обнул€ет все счетчики.

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

ƒругим важным резервом повышени€ производительности системы €вл€етс€ правильный выбор размера страницы.  аким же должен быть оптимальный размер страницы? — одной стороны, чтобы уменьшить частоту страничных прерываний, следовало бы увеличивать размер страницы. — другой стороны, если страница велика, то велика и фиктивна€ область в последней виртуальной странице каждого процесса. ≈сли учесть, что в среднем в каждом процессе фиктивна€ область составл€ет половину страницы, то в сумме при большом объеме страницы потери могут составить существенную величину. »з приведенных соображений еледует, что выбор размера страницы €вл€етс€ сложной оптимизационной задачей, требующей учета многих факторов. Ќа практике же разработчики ќ— и процессоров ограничиваютс€ неким рациональным решением, пригодным дл€ широкого класса вычислительных систем. “ипичный размер страницы составл€ет несколько килобайт, например, наиболее распространенные процессоры х86 и Pentium компании Intel, а также операционные системы, устанавливаемые на этих процессорах, поддерживают страницы размером 4096 байт (4  байт)1.

1 ѕроцессор Pentium позвол€ет использовать также страницы размером до 4 ћбайт одно- ' временно со страницами объемом 4  байт.

–азмер страницы вли€ет также на количество записей в таблицах страниц. „ем меньше страница, тем более объемными €вл€ютс€ таблицы страниц процессов и тем больше места они занимают в пам€ти. ”читыва€, что в современных процессорах максимальный объем виртуального адресного пространства процесса, как правило, не меньше 4 √байт (232), то при размере страницы 4  байт (212) и длине записи 4 байта дл€ хранени€ таблицы страниц может потребоватьс€ 4 ћбайт пам€ти! ¬ыходом в такой ситуации €вл€етс€ хранение в пам€ти только той части таблицы страниц, котора€ активно используетс€ в данный период времени Ч так как сама таблица страниц хранитс€ в таких же страницах физической пам€ти, что и описываемые ею страницы, то принципиально возможно временно вытесн€ть часть таблицы страниц из оперативной пам€ти.

»менно такой результат может быть достигнут путем более сложной структуризации виртуального адресного пространства, при котором все множество виртуальных адресов процесса делитс€ на разделы, а разделы дел€тс€ на страницы (рис. 5.16). ¬се страницы имеют одинаковый размер, а разделы содержат одинаковое количество страниц. ≈сли размер страницы и количество страниц в разделе выбрать равными степени двойки (2k и 2" соответственно), то принадлежность виртуального адреса к разделу и странице, а также смещение внутри страницы можно определить очень просто: младшие k двоичных разр€дов дают смещение, следующие п разр€дов представл€ют собой номер виртуальной страницы, а оставшиес€ старшие разр€ды (обозначим их количество т) содержат номер раздела.

ƒл€ каждого раздела строитс€ собственна€ таблица страниц.  оличество дескрипторов в таблице и их размер подбираютс€ такими, чтобы объем таблицы оказалс€ равным объему страницы. Ќапример, в процессоре Pentium при размере страницы 4  байт длина дескриптора страницы составл€ет 4 байта и количество записей в таблице страниц, помещающейс€ на страницу, равн€етс€ соответственно 1024.  ажда€ таблица страниц описываетс€ дескриптором, структура которого полностью совпадает со структурой дескриптора обычной страницы. Ёти дескрипторы сведены в таблицу разделов, называемую также каталогом страниц. ‘изический адрес таблицы разделов активного процесса содержитс€ в специальном регистре процессора и поэтому всегда известен операционной системе. —траница, содержаща€ таблицу разделов, никогда не выгружаетс€ из пам€ти, в противном случае работа виртуальной пам€ти была бы невозможна.

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

–ис. 5.16. —труктура виртуального адресного пространства с разделами

ѕроследим более подробно схему преобразовани€ адресов дл€ случа€ двухуровневой структуризации виртуального адресного пространства (рис. 5.17).:

1. ѕутем отбрасывани€ k+n младших разр€дов в виртуальном адресе определ€етс€ номер раздела, к которому принадлежит данный виртуальный адрес.

2. ѕо этому номеру из таблицы разделов извлекаетс€ дескриптор соответствующей таблицы страниц. ѕровер€етс€, находитс€ ли данна€ таблица страниц в пам€ти. ≈сли нет, происходит страничное прерывание и система загружает нужную страницу с диска.

3. ƒалее из этой таблицы страниц извлекаетс€ дескриптор виртуальной страницы, номер которой содержитс€ в средних п разр€дах преобразуемого виртуального адреса. —нова выполн€етс€ проверка наличи€ данной страницы в пам€ти и при необходимости ее загрузка.

4. »з дескриптора определ€етс€ номер (базовый адрес) физической страницы, в которую загружена данна€ виртуальна€ страница.   номеру физической страницы пристыковываетс€ смещение, вз€тое из k младших разр€дов виртуального адреса. ¬ результате получаетс€ искомый физический адрес.

–ис. 5.17. —хема преобразовани€ виртуального адреса дл€ двухуровневой структуризации адресного пространства

—траничное распределение пам€ти может быть реализовано в упрощенном варианте, без выгрузки страниц на диск. ¬ этом случае все виртуальные страницы всех процессов посто€нно наход€тс€ в оперативной пам€ти. “акой вариант страничной организации хот€ и не предоставл€ет пользователю преимуществ работы с виртуальной пам€тью большого объема, но сохран€ет другое достоинство страничной организации Ч позвол€ет успешно боротьс€ с фрагментацией физической пам€ти. ƒействительно, во-первых, программу можно разбить на части и загрузить в разрозненные участки свободной пам€ти, во-вторых, при загрузке виртуальных страниц никогда не образуетс€ неиспользуемых остатков, так как размеры виртуальных и физических страниц совпадают. “акой режим работы системы управлени€ пам€тью используетс€ в некоторых специализированных ќ—, когда требуетс€ высока€ реактивность системы и способность выполн€ть переменный набор приложений (пример Ч ќ— семейства Novell NetWare 3.x и 4.x).

—егментное распределение

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

 роме того, разбиение виртуального адресного пространства на Ђосмысленныеї части делает принципиально возможным совместное использование фрагментов программ разными процессами. ѕусть, например, двум процессам требуетс€ одна и та же подпрограмма, котора€ к тому же обладает свойством реентерабельности. “огда коды этой подпрограммы могут быть оформлены в виде отдельного сегмента и включены в виртуальные адресные пространства обоих процессов. ѕри отображении в физическую пам€ть сегменты, содержащие коды подпрограммы из обоих виртуальных пространств, проецируютс€ на одну и ту же область физической пам€ти. “аким образом оба процесса получат доступ к одной и той же копии подпрограммы (рис. 5.18).

»так, виртуальное адресное пространство процесса делитс€ на части Ч сегменты, размер которых определ€етс€ с учетом смыслового значени€ содержащейс€ в них информации. ќтдельный сегмент может представл€ть собой подпрограмму, массив данных и т. п. ƒеление виртуального адресного пространства на сегменты осуществл€етс€ компил€тором на основе указаний программиста или по умолчанию, в соответствии с прин€тыми в системе соглашени€ми. ћаксимальный размер сегмента определ€етс€ разр€дностью виртуального адреса, например при 32-разр€дной организации процессора он равен 4 √байт. ѕри этом максимально возможное виртуальное адресное пространство процесса представл€ет собой набор из N виртуальных сегментов, каждый размером по 4 √байт. ¬ каждом сегменте виртуальные адреса наход€тс€ в диапазоне от 0000000016 до FFFFFFFF16. —егменты не упор€дочиваютс€ друг относительно друга, так что общего дл€ сегментов линейного виртуального адреса не существует, виртуальный адрес задаетс€ парой чисел: номером сегмента и линейным виртуальным адресом внутри сегмента.

1 –еентерабельность (reentrantable) Ч свойство повторной входимости кода, которое позвол€ет одновременно использовать его несколькими процессами. ѕри выполнении реентерабельного кода процессы не измен€ют его, поэтому в пам€ть достаточно загрузить только одну копию кода.

–ис. 5.18. –аспределение пам€ти сегментами

ѕри загрузке процесса в оперативную пам€ть помещаетс€ только часть его сегментов, полна€ копи€ виртуального адресного пространства находитс€ в дисковой пам€ти. ƒл€ каждого загружаемого сегмента операционна€ система подыскивает непрерывный участок свободной пам€ти достаточного размера. —межные в виртуальной пам€ти сегменты одного процесса могут занимать в оперативной пам€ти несмежные участки. ≈сли во врем€ выполнени€ процесса происходит обращение по виртуальному адресу, относ€щемус€ к сегменту, который в данный момент отсутствует в пам€ти, то происходит прерывание. ќ— приостанавливает активный процесс, запускает на выполнение следующий процесс из очереди, а параллельно организует загрузку нужного сегмента с диска. ѕри отсутствии в пам€ти места, необходимого дл€ загрузки сегмента, операционна€ система выбирает сегмент на выгрузку, при этом она использует критерии, аналогичные рассмотренным выше критери€м выбора страниц при страничном способе управлени€ пам€тью.

Ќа этапе создани€ процесса во врем€ загрузки его образа в оперативную пам€ть система создает таблицу сегментов процесса (аналогичную таблице страниц), в которой дл€ каждого сегмента указываетс€:

  • базовый физический адрес сегмента в оперативной пам€ти;
  • размер сегмента;
  • правила доступа к сегменту;
  • признаки модификации, присутстви€ и обращени€ к данному сегменту, а также некотора€ друга€ информаци€.

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

 ак видно, сегментное распределение пам€ти имеет очень много общего со страничным распределением.

ћеханизмы преобразовани€ адресов этих двух способов управлени€ пам€тью тоже весьма схожи, однако в них имеютс€ и существенные отличи€, которые €вл€ютс€ следствием того, что сегменты в отличие от страниц имеют произвольный размер. ¬иртуальный адрес при сегментной организации пам€ти может быть представлен парой (g, s), где g Ч номер сегмента, a s Ч смещение в сегменте. ‘изический адрес получаетс€ путем сложени€ базового адреса сегмента, который определ€етс€ по номеру сегмента g из таблицы сегментов и смещени€ s (рис. 5.19).

–ис. 5.19. ѕреобразование виртуального адреса при сегментной организации пам€ти

¬ данном случае нельз€ обойтись операцией конкатенации, как это делаетс€ при страничной организации пам€ти. ƒействительно, поскольку размер страницы равен степени двойки, следовательно, в двоичном виде он выражаетс€ числом с несколькими нул€ми в младших разр€дах. —траницы имеют одинаковый размер, а значит, их начальные адреса кратны размеру страниц и выражаютс€ также числами с нул€ми в младших разр€дах. »менно поэтому ќ— заносит в таблицы страниц не полные адреса, а номера физических страниц, которые совпадают со старшими разр€дами базовых адресов. —егмент же может в общем случае располагатьс€ в физической пам€ти начина€ с любого адреса, следовательно, дл€ определени€ местоположени€ в пам€ти необходимо задавать его полный начальный физический адрес. »спользование операции сложени€ вместо конкатенации замедл€ет процедуру преобразовани€ виртуального адреса в физический по сравнению со страничной организацией.

ƒругим недостатком сегментного распределени€ €вл€етс€ избыточность. ѕри сегментной организации единицей перемещени€ между пам€тью и диском €вл€етс€ сегмент, имеющий в общем случае объем больший, чем страница. ќднако во многих случа€х дл€ работы программы вовсе не требуетс€ загружать весь сегмент целиком, достаточно было бы одной или двух страниц. јналогично при отсутствии свободного места в пам€ти не стоит выгружать целый сегмент, когда можно обойтись выгрузкой нескольких страниц.

Ќо главный недостаток сегментного распределени€ Ч это фрагментаци€, котора€ возникает из-за непредсказуемости размеров сегментов. ¬ процессе работы системы в пам€ти образуютс€ небольшие участки свободной пам€ти, в которые не может быть загружен ни один сегмент. —уммарный объем, занимаемый фрагментами, может составить существенную часть общей пам€ти системы, привод€ к ее неэффективному использованию.

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

ќдним из существенных отличий сегментной организации пам€ти от страничной €вл€етс€ возможность задани€ дифференцированных прав доступа процесса к его сегментам. Ќапример, один сегмент данных, содержащий исходную информацию дл€ приложени€, может иметь права доступа Ђтолько чтениеї, а сегмент данных, представл€ющий результаты, Ч Ђчтение и записьї. Ёто свойство дает принципиальное преимущество сегментной модели пам€ти над страничной.

—егментно-страничное распределение

ƒанный метод представл€ет собой комбинацию страничного и сегментного механизмов управлени€ пам€тью и направлен на реализацию достоинств обоих подходов.

“ак же как и при сегментной организации пам€ти, виртуальное адресное пространство процесса разделено на сегменты. Ёто позвол€ет определ€ть разные права доступа к разным част€м кодов и данных программы.

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

¬ большинстве современных реализаций сегментно-страничной организации пам€ти в отличие от набора виртуальных диапазонов адресов при сегментной организации пам€ти (рис. 5.20, а) все виртуальные сегменты образуют одно непрерывное линейное виртуальное адресное пространство (рис. 5.20, б).

 оординаты байта в виртуальном адресном пространстве при сегментно-страничной организации можно задать двум€ способами. ¬о-первых, линейным виртуальным адресом, который равен сдвигу данного байта относительно границы общего линейного виртуального пространства, во-вторых, парой чисел, одно из которых €вл€етс€ номером сегмента, а другое Ч смещением относительно начала сегмента. ѕри этом в отличие от сегментной модели, дл€ однозначного задани€ виртуального адреса вторым способом необходимо каким-то образом указать также начальный виртуальный адрес сегмента с данным номером. —истемы виртуальной пам€ти ќ— с сегментно-страничной организацией используют второй способ, так как он позвол€ет непосредственно определить принадлежность адреса некоторому сегменту и проверить права доступа процесса к нему.

–ис. 5.20. ƒва способа сегментации

ƒл€ каждого процесса операционна€ система создает отдельную таблицу сегментов, в которой содержатс€ описатели (дескрипторы) всех сегментов процесса. ќписание сегмента включает назначенные ему права доступа и другие характеристики, подобные тем, которые содержатс€ в дескрипторах сегментов при сегментной организации пам€ти. ќднако имеетс€ и принципиальное отличие. ¬ поле базового адреса указываетс€ не начальный физический адрес сегмента, отведенный ему в результате загрузки в оперативную пам€ть, а начальный линейный виртуальный адрес сегмента в пространстве виртуальных адресов (на рис. 5.20 базовые физические адреса обозначены SI, S2, S3, а базовые виртуальные адреса Ч fl, f2, f3).

Ќаличие базового виртуального адреса сегмента в дескрипторе позвол€ет однозначно преобразовать адрес, заданный в виде пары (номер сегмента, смещение в сегменте), в линейный виртуальный адрес байта, который затем преобразуетс€ в физический адрес страничным механизмом.

ƒеление общего линейного виртуального адресного пространства процесса и физической пам€ти на страницы осуществл€етс€ так же, как это делаетс€ при страничной организации пам€ти. –азмер страниц выбираетс€ равным степени двойки, что упрощает механизм преобразовани€ виртуальных адресов в физические. ¬иртуальные страницы нумеруютс€ в пределах виртуального адресного пространства каждого процесса, а физические страницы Ч в пределах оперативной пам€ти. ѕри создании процесса в пам€ть загружаетс€ только часть страниц, остальные загружаютс€ по мере необходимости. ¬рем€ от времени система выгружает уже ненужные страницы, освобожда€ пам€ть дл€ новых страниц. ќ— ведет дл€ каждого процесса таблицу страниц, в которой указываетс€ соответствие виртуальных страниц физическим.

Ѕазовые адреса таблицы сегментов и таблицы страниц процесса €вл€ютс€ частью его контекста. ѕри активизации процесса эти адреса загружаютс€ в специальные регистры процессора и используютс€ механизмом преобразовани€ адресов.

ѕреобразование виртуального адреса в физический происходит в два этапа (рис. 5.21):

1. Ќа первом этапе работает механизм сегментации. »сходный виртуальный адрес, заданный в виде пары (номер сегмента, смещение), преобразуетс€ в линейный виртуальный адрес. ƒл€ этого на основании базового адреса таблицы сегментов и номера сегмента вычисл€етс€ адрес дескриптора сегмента. јнализируютс€ пол€ дескриптора и выполн€етс€ проверка возможности выполнени€ заданной операции. ≈сли доступ к сегменту разрешен, то вычисл€етс€ линейный виртуальный адрес путем сложени€ базового адреса сегмента, извлеченного из дескриптора, и смещени€, заданного в исходном виртуальном адресе.

2. Ќа втором этапе работает страничный механизм. ѕолученный линейный виртуальный адрес преобразуетс€ в искомый физический адрес. ¬ результате преобразовани€ линейный виртуальный адрес представл€етс€ в том виде, в котором он используетс€ при страничной организации пам€ти, а именно в виде пары (номер страницы, смещение в странице). Ѕлагодар€ тому что размер страницы выбран равным степени двойки, эта задача решаетс€ простым отделением некоторого количества младших двоичных разр€дов. ѕри этом в старших разр€дах содержитс€ номер виртуальной страницы, а в младших Ч смещение искомого элемента относительно начала страницы. “ак, если размер страницы равен 2k, то смещением €вл€етс€ содержимое младших k разр€дов, а остальные, старшие разр€ды содержат номер виртуальной страницы, которой принадлежит искомый адрес. ƒалее преобразование адреса происходит так же, как при страничной организации: старшие разр€ды линейного виртуального адреса, содержащие номер виртуальной страницы, замен€ютс€ номером физической страницы, вз€тым из таблицы страниц, а младшие разр€ды виртуального адреса, содержащие смещение, остаютс€ без изменени€.

–ис. 5.21. ѕреобразование виртуального адреса в физический при сегментно-страничной организации пам€ти

 ак видно, механизм сегментации и страничный механизм действуют достаточно независимо друг от друга. ѕоэтому нетрудно представить себе реализацию сегментно-страничного управлени€ пам€тью, в которой механизм сегментации работает по вышеописанной схеме, а страничный механизм изменен. ќн реализует двухуровневую схему, в которой виртуальное адресное пространство делитс€ сначала на разделы, а уж потом на страницы. ¬ таком случае преобразование виртуального адреса в физический происходит в несколько этапов. —начала механизм сегментации обычным образом, использу€ таблицу сегментов, вычисл€ет линейный виртуальный адрес. «атем из данного виртуального адреса вычлен€ютс€ номер раздела, номер страницы и смещение. » далее по номеру раздела из таблицы разделов определ€етс€ адрес таблицы страниц, а затем по номеру виртуальной страницы из таблицы страниц определ€етс€ номер физической страницы, к которому пристыковываетс€ смещение.»менно такой подход реализован компанией Intel в процессорах 1386, i486 и Pentium.

–ассмотрим еще одну возможную схему управлени€ пам€тью, основанную на комбинировании сегментного и страничного механизмов. “ак же как и в предыдущих случа€х, виртуальное пространство процесса делитс€ на сегменты, а каждый сегмент, в свою очередь, делитс€ на виртуальные страницы. ѕервое отличие состоит в том, что виртуальные страницы нумеруютс€ не в пределах всего адресного пространства процесса, а в пределах сегмента. ¬иртуальный адрес в этом случае выражаетс€ тройкой (номер сегмента, номер страницы, смещение в странице).

«агрузка процесса выполн€етс€ операционной системой постранично, при этом часть страниц размещаетс€ в оперативной пам€ти, а часть Ч на диске. ƒл€ каждого процесса создаетс€ собственна€ таблица сегментов, а дл€ каждого сегмента Ч сво€ таблица страниц. јдрес таблицы сегментов загружаетс€ в специальный регистр процессора, когда активизируетс€ соответствующий процесс.

“аблица страниц содержит дескрипторы страниц, содержимое которых полностью аналогично содержимому ранее описанных дескрипторов страниц. ј вот таблица сегментов состоит из дескрипторов сегментов, которые вместо информации о расположении сегментов в виртуальном адресном пространстве содержат описание расположени€ таблиц страниц в физической пам€ти. Ёто €вл€етс€ вторым существенным отличием данного подхода от ранее рассмотренной схемы сегментно-страничной организации.

–ис. 5.22. ≈ще одна схема преобразовани€ виртуального адреса в физический дл€ сегментно-страничной организации пам€ти

Ќа рис. 5.22 показана схема преобразовани€ виртуального адреса в физический дл€ данного метода.

1. ѕо номеру сегмента, заданному в виртуальном адресе, из таблицы сегментов извлекаетс€ физический адрес соответствующей таблицы страниц.

2. ѕо номеру виртуальной страницы, заданному в виртуальном адресе, из таблицы страниц извлекаетс€ дескриптор, в котором указан номер физической страницы.

3.   номеру физической страницы пристыковываетс€ младша€ часть виртуального адреса Ч смещение.

 

–аздел€емые сегменты пам€ти

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

’от€ основной задачей операционной системы при управлении пам€тью €вл€етс€ защита областей оперативной пам€ти, принадлежащей одному из процессов, от доступа к ней остальных процессов, в некоторых случа€х оказываетс€ полезным организовать контролируемый совместный доступ нескольких процессов к определенной области пам€ти. Ќапример, в том случае, когда несколько пользователей одновременно работают с некоторым текстовым редактором, нецелесообразно многократно загружать его код в оперативную пам€ть. √ораздо экономичней загрузить всего одну копию кода, котора€ обслуживала бы всех пользователей, работающих в данное врем€ с этим редактором (дл€ этого код редактора должен быть реентерабельным). ќчевидно, что сегмент данных редактора не может присутствовать в пам€ти в единственном раздел€емом экземпл€ре Ч дл€ каждого пользовател€ должна быть создана сво€ копи€ этого сегмента, в которой помещаетс€ редактируемый текст и значени€ других переменных редактора, например его конфигураци€, индивидуальна€ дл€ каждого пользовател€, и т. п.

ƒругим примером применени€ раздел€емой области пам€ти может быть использование ее в качестве буфера при межпроцессном обмене данными. ¬ этом случае один процесс пишет в раздел€емую область, а другой Ч читает.

ƒл€ организации раздел€емого сегмента при наличии подсистемы виртуальной пам€ти достаточно поместить его в виртуальное адресное пространство каждого процесса, которому нужен доступ к данному сегменту, а затем настроить параметры отображени€ этих виртуальных сегментов так, чтобы они соответствовали одной и той же области оперативной пам€ти. ƒетали такой настройки завис€т от типа используемой в ќ— модели виртуальной пам€ти: сегментной или сегментно-страничной (чисто странична€ организаци€ не поддерживает пон€тие Ђсегментї, что делает невозможным решение рассматриваемой задачи). Ќапример, при сегментной организации необходимо в дескрипторах виртуального сегмента каждого процесса указать один и тот же базовый физический адрес. ѕри сегментно-страничной организации отображение на одну и ту же область пам€ти достигаетс€ за счет соответствующей настройки таблицы страниц каждого процесса.

¬ приведенном выше описании подразумевалось, что раздел€емый сегмент помещаетс€ в индивидуальную часть виртуального адресного пространства каждого процесса (рис. 5.23, а) и описываетс€ в каждом процессе индивидуальным дескриптором сегмента (и индивидуальными дескрипторами страниц, если используетс€ сегментно-страничный механизм). Ђѕопаданиеї же этих виртуальных сегментов на общую часть оперативной пам€ти достигаетс€ за счет согласованной настройки операционной системой многочисленных дескрипторов дл€ множества процессов.

–ис. 5.23. ƒва способа создани€ раздел€емого сегмента пам€ти

¬озможно и более экономичное дл€ ќ— решение этой задачи Ч помещение единственного раздел€емого виртуального сегмента в общую часть виртуального адресного пространства процессов, то есть в ту часть, котора€ обычно используетс€ дл€ модулей ќ— (рис. 5.23, б). ¬ этом случае настройка дескриптора сегмента (и дескрипторов страниц) выполн€етс€ только один раз, а все процессы пользуютс€ такой настройкой и совместно используют часть оперативной пам€ти.

ѕри работе с раздел€емыми сегментами пам€ти ќ— должна выполн€ть некоторые функции, общие дл€ любых раздел€емых между процессами ресурсов Ч файлов, семафоров и т. п. Ёти функции состо€т в поддержке схемы именовани€ ресурсов, проверке прав доступа определенного процесса к ресурсу, а также в отслеживании количества процессов, пользующихс€ данным ресурсом (чтобы удалить его в случае ненадобности). ƒл€ того чтобы отличать раздел€емые сегменты пам€ти от индивидуальных, дескриптор сегмента должен содержать поле, имеющее два значени€: shared (раздел€емый) или private (индивидуальный).

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

¬о втором случае операционна€ система сама в определенных ситуаци€х принимает решение о том, что нужно создать раздел€емый сегмент. Ќаиболее типичным примером такого рода €вл€етс€ поступление нескольких запросов на выполнение одного и того же приложени€. ≈сли кодовый сегмент приложени€ помечен в исполн€емом файле как реентерабельный и раздел€емый, то ќ— не создает при поступлении нового запроса новую индивидуальную дл€ процесса копию кодового сегмента этого приложени€, а отображает уже существующий раздел€емый сегмент в виртуальное адресное пространство процесса. ѕри закрытии приложени€ каким-либо процессом ќ— провер€ет, существуют ли другие процессы, пользующиес€ данным приложением, и если их нет, то удал€ет данный раздел€емый сегмент.

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

 

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

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

ѕам€ть вычислительной машины представл€ет собой иерархию запоминающих устройств («”), отличающихс€ средним временем доступа к данным, объемом и стоимостью хранени€ одного бита (рис. 5.24). ‘ундаментом этой пирамиды запоминающих устройств служит внешн€€ пам€ть, как правило, представл€ема€ жестким диском. ќна имеет большой объем (дес€тки и сотни гигабайт), но скорость доступа к данным €вл€етс€ невысокой. ¬рем€ доступа к диску измер€етс€ миллисекундами.

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

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

1 ¬се перечисленные характеристики «” быстро измен€ютс€ по мере совершенствовани€ вычислительной аппаратуры. ¬ данном случае важны не абсолютные значени€ времени доступа или объема пам€ти, а их соотношение дл€ разных типов «апоминающих устройств.

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

–ис. 5.24. »ерархи€ запоминающих устройств

“аким образом, можно констатировать печальную закономерность Ч чем больше объем устройства, тем менее быстродействующим оно €вл€етс€. Ѕолее того, стоимость хранени€ данных в расчете на один бит также увеличиваетс€ с ростом быстродействи€ устройств. ќднако пользователю хотелось бы иметь и недорогую, и быструю пам€ть.  эш-пам€ть представл€ет некоторое компромиссное решение этой проблемы.

 эш-пам€ть

 эш-пам€ть, или просто кэш (cache), Ч это способ совместного функционировани€ двух типов запоминающих устройств, отличающихс€ временем доступа и стоимостью хранени€ данных, который за счет динамического копировани€ в Ђбыстроеї «” наиболее часто используемой информации из Ђмедленногої «” позвол€ет, с одной стороны, уменьшить среднее врем€ доступа к данным, а с другой стороны, экономить более дорогую быстродействующую пам€ть.

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

 эш-пам€тью, или кэшем, часто называют не только способ организации работы двух типов запоминающих устройств, но и одно из устройств Ч Ђбыстроеї «”.

ќно стоит дороже и, как правило, имеет сравнительно небольшой объем. Ђћедленноеї «” далее будем называть основной пам€тью, противопоставл€€ ее вспомогательной кэш-пам€ти.

 эширование Ч это универсальный метод, пригодный дл€ ускорени€ доступа к оперативной пам€ти, к диску и к другим видам запоминающих устройств. ≈сли кэширование примен€етс€ дл€ уменьшени€ среднего времени доступа к оперативной пам€ти, то в качестве кэша используют быстродействующую статическую пам€ть. ≈сли кэширование используетс€ системой ввода-вывода дл€ ускорени€ доступа к данным, хран€щимс€ на диске, то в этом случае роль кэш-пам€ти выполн€ют буферы в оперативной пам€ти, в которых оседают наиболее активно используемые данные. ¬иртуальную пам€ть также можно считать одним из вариантов реализации принципа кэшировани€ данных, при котором оперативна€ пам€ть выступает в роли кэша по отношению к внешней пам€ти Ч жесткому диску. ѕравда, в этом случае кэширование используетс€ не дл€ того, чтобы уменьшить врем€ доступа к данным, а дл€ того, чтобы заставить диск частично подменить оперативную пам€ть за счет перемещени€ временно неиспользуемого кода и данных на диск с целью освобождени€ места дл€ активных процессов. ¬ результате наиболее интенсивно используемые данные Ђоседаютї в оперативной пам€ти, остальна€ же информаци€ хранитс€ в более объемной и менее дорогосто€щей внешней пам€ти.

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

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

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

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

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

–ис. 5.25. —хема функционировани€ кэш-пам€ти

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

t - t1(d - р) + t2p - (t2 -t1)p + t1

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

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

  • ¬ременна€ локальность. ≈сли произошло обращение по некоторому адресу, то следующее обращение по тому же адресу с большой веро€тностью произойдет в ближайшее врем€.
  • ѕространственна€ локальность. ≈сли произошло обращение по некоторому адресу, то с высокой степенью веро€тности в ближайшее врем€ произойдет обращение к соседним адресам.

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

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

ѕроблема согласовани€ данных

¬ процессе работы содержимое кэш-пам€ти посто€нно обновл€етс€, а значит, врем€ от времени данные из нее должны вытесн€тьс€. ¬ытеснение означает либо простое объ€вление свободной соответствующей области кэш-пам€ти (сброс бита действительности), если вытесн€емые данные за врем€ нахождени€ в кэше не были изменены, либо в дополнение к этому копирование данных в основную па*-м€ть, если они были модифицированы. јлгоритм замены данных в кэш-пам€ти существенно вли€ет на ее эффективность. ¬ идеале такой алгоритм должен, во-первых, быть максимально быстрым, чтобы не замедл€ть работу кэш-пам€ти, а во-вторых, обеспечивать максимально возможную веро€тность кэш-попаданий. ѕоскольку из-за непредсказуемости вычислительного процесса ни один алгоритм замещени€ данных в кэш-пам€ти не может гарантировать оптимальный результат, разработчики ограничиваютс€ рациональными решени€ми, которые по крайней мере, не сильно замедл€ют работу кэша Ч запоминающего устройства, изначально призванного быть быстрым.

Ќаличие в компьютере двух копий данных Ч в основной пам€ти и в кэше Ч порождает проблему согласовани€ данных. ≈сли происходит запись в основную пам€ть по некоторому адресу, а содержимое этой €чейки находитс€ в кэше, то в результате соответствующа€ запись в кэше становитс€ недостоверной. –ассмотрим два подхода к решению этой проблемы:

  • —квозна€ запись (write through). ѕри каждом запросе к основной пам€ти, в том числе и при записи, просматриваетс€ кэш. ≈сли данные по запрашиваемому адресу отсутствуют, то запись выполн€етс€ только в основную пам€ть. ≈сли же данные, к которым выполн€етс€ обращение, наход€тс€ в кэше, то запись выполн€етс€ одновременно в кэш и основную пам€ть.
  • ќбратна€ запись (write back). јналогично при возникновении запроса к пам€ти выполн€етс€ просмотр кэша, и если запрашиваемых данных там нет, то запись выполн€етс€ только в основную пам€ть. ¬ противном же случае запись производитс€ только в кэш-пам€ть, при этом в описателе данных делаетс€ специальна€ отметка (признак модификации), котора€ указывает на то, что при вытеснении этих данных из кэша необходимо переписать их в основную пам€ть, чтобы актуализировать устаревшее содержимое основной пам€ти.

¬ некоторых алгоритмах замещени€ предусматриваетс€ первоочередна€ выгрузка модифицированных, или, как еще говор€т, Ђгр€зныхї данных. ћодифицированные данные могут выгружатьс€ не только при освобождении места в кэш-пам€ти дл€ новых данных, но и в Ђфоновом режимеї, когда система не очень загружена.

—пособы отображени€ основной пам€ти на кэш

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

ѕри случайном отображении элемент оперативной пам€ти в общем случае может быть размещен в произвольном месте кэш-пам€ти. ƒл€ того чтобы в дальнейшем можно было найти нужные данные в кэше, они помещаютс€ туда вместе со своим адресом, то есть тем адресом, который данные имеют в оперативной пам€ти. ѕри каждом запросе к оперативной пам€ти выполн€етс€ поиск в кэше, причем критерием поиска выступает адрес оперативной пам€ти из запроса. ќчевидна€ схема простого перебора дл€ поиска нужных данных в случае кэша оказываетс€ непригодной из-за недопустимо больших временных затрат. ƒл€ кэшей со случайным отображением используетс€ так называемый ассоциативный поиск, при котором сравнение выполн€етс€ не последовательно с каждой записью кэша, а параллельно со всеми его запис€ми (рис. 5.26). ѕризнак, по которому выполн€етс€ сравнение, называетс€ тегом (tag). ¬ данном случае те-гом €вл€етс€ адрес данных в оперативной пам€ти. Ёлектронна€ реализаци€ такой схемы приводит к удорожанию пам€ти, причем стоимость существенно возрастает с увеличением объема запоминающего устройства. ѕоэтому ассоциативна€ кэш-пам€ть используетс€ в тех случа€х, когда дл€ обеспечени€ высокого процента попадани€ достаточно небольшого объема пам€ти.

¬ кэшах, построенных на основе случайного отображени€, вытеснение старых данных происходит только в том случае, когда вс€ кэш-пам€ть заполнена и нет свободного места. ¬ыбор данных на выгрузку осуществл€етс€ среди всех записей кэша. ќбычно этот выбор основываетс€ на тех же приемах, что и в алгоритмах замещени€ страниц, например выгрузка данных, к которым дольше всего не было обращений, или данных, к которым было меньше всего обращений.

–ис. 5.26. јссоциативный поиск в кэше со случайным отображением

¬торой, детерминированный способ отображени€ предполагает, что любой элемент основной пам€ти всегда отображаетс€ в одно и то же место кэш-пам€ти. ¬ этом случае кэш-пам€ть разделена на строки, кажда€ из которых предназначена дл€ хранени€ одной записи об одном элементе данных1 и имеет свой номер. ћежду номерами строк кэш-пам€ти и адресами оперативной пам€ти устанавливаетс€ соответствие Ђодин ко многимї: одному номеру строки соответствует несколько (обычно достаточно много) адресов оперативной пам€ти.

¬ качестве отображающей функции может использоватьс€ простое выделение нескольких разр€дов из адреса оперативной пам€ти, которые интерпретируютс€ как номер строки кэш-пам€ти (такое отображение называетс€ пр€мым). Ќапример, пусть в кэш-пам€ти может хранитьс€ 1024 записи, то есть кэш имеет 1024 строки, пронумерованные от 0 до 1023. “огда любой адрес оперативной пам€ти может быть отображен на адрес кэш-пам€ти простым отделением 10 двоичных разр€дов (рис. 5.27).

1 ¬ действительности запись в кэше обычно содержит несколько элементов данных.

ѕри поиске данных в кэше используетс€ быстрый пр€мой доступ к записи по номеру строки, полученному путем обработки адреса оперативной пам€ти из запроса. ќднако поскольку в найденной строке могут находитьс€ данные из любой €чейки оперативной пам€ти, младшие разр€ды адреса которой совпадают с номером строки, необходимо выполнить дополнительную проверку. ƒл€ этих целей кажда€ строка кэш-пам€ти дополн€етс€ тегом, содержащим старшую часть адреса данных в оперативной пам€ти. ѕри совпадении тега с соответствующей частью адреса из запроса констатируетс€ кэш-попадание.

–ис. 5.27. ѕр€мое отображение

≈сли же произошел кэш-промах, то данные считываютс€ из оперативной пам€ти и  опируютс€ в кэш. ≈сли строка кэш-пам€ти, в которую должен быть скопирован элемент данных из оперативной пам€ти, содержит другие данные, то последние вытесн€ютс€ из кэша. «аметим, что процесс замещени€ данных в кэш-пам€ти на основе пр€мого отображени€ существенно отличаетс€ от процесса замещени€ данных в кэш-пам€ти со случайным отображением. ¬о-первых, вытеснение данных происходит не только в случае отсутстви€ свободного места в кэше, во-вторых, никакого выбора данных на замещение не существует.

¬о многих современных процессорах кэш-пам€ть строитс€ на основе сочетани€ этих двух подходов, что позвол€ет найти компромисс между сравнительно низкой стоимостью кэша с пр€мым отображением и интеллектуальностью алгоритмов замещени€ в кэше со случайным отображением. ѕри смешанном подходе произвольный адрес оперативной пам€ти отображаетс€ не на один адрес кэш-па* м€ти (как это характерно дл€ пр€мого отображени





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-05-08; ћы поможем в написании ваших работ!; просмотров: 746 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ћучша€ месть Ц огромный успех. © ‘рэнк —инатра
==> читать все изречени€...

505 - | 486 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.159 с.