Операционные системы: управление памятью. Макаров П.С. - 51 стр.

UptoLike

Составители:

Рубрика:

Рис. 36

Когда требуется загрузить блок в заполненный до предела кэш, какой-

либо другой блок должен быть удален из кэша (и записан на диск, если он был

модифицирован в кэше). Эта ситуация очень похожа на страничную

организацию памяти, и к ней применимы все обычные алгоритмы замены такие

как, mFIFO (First In First Out — первым прибыл — первым обслужен), «вторая

попытка» и LRU (Least Recently Used — с наиболее давним использованием).

Одно приятное отличие кэширования от страничной организации памяти

состоит в том, что обращения к кэшу производятся относительно нечасто, что

позволяет хранить все блоки в точном LRU-порядке со связными списками.

К сожалению, здесь есть одна загвоздка. Теперь, когда мы можем

реализовать точное выполнение алгоритма LRU, оказывается,

что алгоритм

LRU является нежелательным. Вызвано это тем, что буквальное применение

алгоритма LRU снижает надежность файловой системы и угрожает ее

непротиворечивости (обсуждавшейся в предыдущем разделе). Если в кэш

считывается и модифицируется критический блок, например блок i-узла, но не

записывается тут же на диск, то компьютерный сбой может привести к тому,

что файловая

система окажется в противоречивом состоянии. Если блок i-узла

поместить в конец цепочки LRU, то может пройти довольно много времени,

прежде чем этот блок попадет в ее начало и будет записан на диск.