Кэширование памяти и tlb

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

Две стратегии поведения при замещении модифицированных значений.

• write-through -измененные значения сразу записываются на свое место

• write-back -запись измененных значений задерживается на время или до момента замещения. Обеспечивает большую эффективность, но опасно применять к ненадежным системам. Например, отложенная запись при кэшировании файловой системы может привести к потере данных или разрушению файловой системы.

Методы загрузки и замещения страниц Методы загрузки страниц

Статистика выполнения программ такова: 90% времени используется 10% кода программы. Нет необходимости держать в памяти всю программу. Поэтому виртуальная память распределяется на диске, а оперативная память используется в качестве кэша.

Существуют две стратегии загрузки страниц в память: с опережением и по запросу.

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

1. При трансляции виртуального адреса по таблице страниц анализируется бит присутствия страницы. Если страницы нет в памяти, то генерируется прерывание по отсутствию страницы.

2. ОС выбирает страницу в памяти для замещения.

3. Если замещаемая страница была модифицирована, ее содержимое записывается на диск.

4. Изменяется элемент таблицы страниц и элемент TLB замещаемой страницы.

5. В память загружается новая страница.

6. Изменяется элемент таблицы страниц для загружаемой страницы

7. Управление передается процессу, вызвавшему прерывание по отсутствию страницы.

Методы замещения страниц

• MIN. Замещение страницы, которая дольше всего не потребуется. Если бы можно было реализовать этот метод, то это оптимальная стратегия.

• RANDOM. Случайным образом. Прост и обычно применяется для кэшированияTLB.

• FIFO. Замещается страница загруженная раньше других. Метод плохо работает для страниц, к которым часто обращаются.

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

Примеры поведения разных стратегий

Пусть имеется три страничных фрейма и следующая последовательность обращения к страницам: A B C D A B E A B C D E.

MIN (7 замещений)

Слот

A

B

C

D

A

B

E

A

B

C

D

E

1

A

C

2

B

D

3

C

D

E

FIFO (9 замещений)

Слот

A

B

C

D

A

B

E

A

B

C

D

E

1

A

D

E

2

B

A

C

3

C

B

D

LRU (10 замещений)

Слот

A

B

C

D

A

B

E

A

B

C

D

E

1

A

D

E

C

2

B

A

D

3

C

B

E

LRU плохо себя ведет, в случае, когда происходит обращение к только что выгруженной странице.

Увеличим число страничных слотов на 1

LRU (8 замещений)

Слот

A

B

C

D

A

B

E

A

B

C

D

E

1

A

E

2

B

3

C

E

D

4

D

C

FIFO (10 замещений)

Слот

A

B

C

D

A

B

E

A

B

C

D

E

1

A

E

D

2

B

A

E

3

C

B

4

D

C

Этот эффект известен как аномалия FIFO (Belady)

Для стратегий LRU и MIN содержимое памяти из Х страниц является подмножеством содержимого памяти в случае Х+1 страниц при одинаковой последовательности обращения к страницам. (Для стратегии FIFO это свойство не выполняется)