Принцип локальности

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

На основе заключения свойства локальности сформулирована теория рабочего множества. Рабочее множество – подмножество страниц, к которым процесс активно обращается. Для обеспечения эффективного выполнения программы необходимо, чтобы её рабочее множество находилось в первичной памяти. В противном случае может возникнуть режим чрезмерно интенсивной подкачки страниц. Во время работы процесса его рабочие множества динамически меняются. Иногда происходят резкие изменения. Выделение основной памяти при управлении памятью на основе рабочих множеств можно представить следующим образом:

Рабочие множества время

К - количество страниц первичной памяти выделенных данному процессу.

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