ий прохід витрачається більше часу, ніж на всі інші проходи, то сторінки, що містять код для наступних проходів, можуть завжди мати нижчі показники лічильників, ніж сторінки, що використовувалися при першому проході. Внаслідок цього операційна система буде заміщати потрібні сторінки замість тих, потреба в яких вже відпала.
На щастя, невелика модифікація алгоритму NFU дозволяє досить близько підійти до імітації алгоритму LRU. Модифікація складається з двох частин. По-перше, перед додаванням до лічильників значення біта R їх значення зсувається на один розряд вправо. По-друге, значення біта R додається до самого лівому, а не до самого правому биту.
На рис. 2 показано, як працює модифікований алгоритм, відомий як алгоритм старіння. Припустимо, що після першого переривання від таймера біт R для сторінок від 0 до 5 має, відповідно, значення 1, 0, 1, 0, 1 і 1 (для сторінки 0 воно дорівнює 1, для сторінки 1 - 0, для сторінки 2 -1, і т. д.). Іншими словами, між перериваннями від таймера, відповідними тактам 0 і 1, було звернення до сторінок 0, 2, 4 і 5, в результаті якого їх біти R були встановлені в 1, а у решти сторінок їх значення залишилося рівним 0. Після того як були зміщені значення шести відповідних лічильників і зліва було вставлено значення біта R, вони придбали значення, показані на рис. 2, а. У чотирьох решти стовпцях показані стану шести лічильників після наступних чотирьох переривань від таймера.
Рис. 2. Алгоритм старіння є програмною моделлю алгоритму LRU. Тут показано шість сторінок в моменти п'яти таймерних переривань, позначених буквами від а до д.
операційний псевдопараллельний диспетчеризація пам'ять
При виникненні помилки відсутності сторінки видаляється та сторінка, чий лічильник має найменше значення. Очевидно, що у сторінки, до якої не було При виникненні помилки відсутності сторінки видаляється та сторінка, чий лічильник має найменше значення. Очевидно, що у сторінки, до якої не було звернень за, скажімо, чотири переривання від таймера, в її лічильнику буде чотири провідних нуля, і тому значення її лічильника буде меншим, ніж у лічильника сторінки, до якої не було звернень протягом трьох переривань від таймера. Цей алгоритм відрізняється від алгоритму LRU двома особливостями. Розглянемо сторінки 3 і 5 на рис. 2, д. Ні до однієї з них за два переривання від таймера не було жодного звернення, але до обох було звернення за переривання від таймера, попереднє цим двом. Відповідно до алгоритму LRU якщо сторінка повинна бути видалена, то ми повинні вибрати одну з цих двох сторінок. Проблема в тому, що ми не знаємо, до якої з них зверталися в останню чергу між тактом 1 і тактом 2. При записи тільки одного біта за інтервал між двома перериваннями від таймера ми втратили можливість відрізнити більш раннє звернення від пізнішого. Все, що ми можемо зробити, - це видалити сторінку 3, оскільки до сторінці 5 також було звернення двома тактами раніше, а до сторінці 3 такого звернення не було. Друге розходження між алгоритмом LRU і алгоритмом старіння полягає в тому, що в алгоритмі старіння лічильник має обмежену кількість біт (в даному прикладі - 8 біт), яке звужує проглядається їм горизонт минулого. Припустимо, що у кожної з двох сторінок значення лічильника дорівнює нулю. Все, що ми можемо зробити, - це вибрати одну з них довільним чином. Насправді цілком може вияви...
