Концепция локального и рабочего множества программ в системах с виртуальной памятью

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

Свойство локальной концентрации может проявляться в двух видах:

1. Во времени;

2. В пространстве.

В связи с этим существует два вида локальности:

1. Временная локальность;

2. Пространственная локальность.

· Временная локальность – это концентрация каких-либо событий или явлений во времени.

Вероятность повторения события будет расти с уменьшением dt.

· Пространственная локальность означает, что соседние объекты, то есть объекты, расположенные физически близко относительно друг друга, будут описываться одинаковыми или близкими свойствами.

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

1. Использованием программных структур типа циклов.

2. Применением процедур и функций, параметры которых хранятся в стеках.

3. Применением структур данных типа стеков и очередей.

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

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

1. Широким использованием структур данных типа массивов и записей.

2. Стремление программистов размещать описания взаимосвязанных переменных в относительной близости друг от друга.

3. Последовательным характером выполнения команд в программе.

Для изучения явления локальности проводились различные исследования, в частности, исследовалась зависимость частоты f прерываний процесса по отсутствию нужных страниц от объема выделенной для процесса памяти, который может быть оценен в виде доли k страниц процесса, находящихся в ОП.

a – теоретическая зависимость, b – реальная зависимость.

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

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

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

В общем случае, рабочим множеством процесса W(t, dt) для некоторого момента времени t, считается некоторый набор страниц, к которым процесс активно обращается в течение интервала [t-dt, t]. Интервал dt в данном случае называется размером окна рабочего множества.

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

Иногда к текущему множеству могут добавляться новые страницы, либо из него могут удаляться составляющие. Следовательно, рабочее множество меняется во времени.