Алгоритм заміщення комірок пам’яті FIFO

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Перший зайшов — перший вийшов

Приклад використання стратегії заміщення FIFO[ред. | ред. код]

Нехай процес містить 8 віртуальних сторінок на диску, а йому виділено чотири фіксованих кадри основної пам'яті. Далі виконуються звернення до наступних сторінок: 1 0 2 2 1 7 6 7 0 1 Вкажемо послідовність розміщення сторінок в кадрах при використанні алгоритму заміщення сторінок FIFO. 8 віртуальних сторінок — це цифри, які ми розміщатимемо у таблиці. 4 фіксованих кадри основної пам'яті зазначають розмір рядків у таблиці. Отже сформуємо пусту таблицю.

1 0 2 2 1 7 6 7 0 1

Заповнення таблиці відбувається вертикально. Зараз у нас є 4 вільних фіксованих кадрів. Отже, після заповнення у них знаходитимуться цифри: 1 0 2 7. Наша таблиця набуде вигляду:

1 0 2 2 1 7 6 7 0 1
1 1 1 1 1 1
0 0 0 0 0
2 2 2 2
7

Як бачимо, нам потрібно задіяти сторінку 6, а місця на неї — не залишилось. Згідно з правил принципу нам потрібно помістити цифру на місце тієї, яка використовувалась найпершою, а це цифра 1. Ось що получиться:

1 0 2 2 1 7 6 7 0 1
1 1 1 1 1 1 6 6 6
0 0 0 0 0 0 0 0
2 2 2 2 2 2 2
7 7 7 7

Тепер нам знову потрібно звернутись до сторінки 1, якої уже нема у фіксованих кадрах. Згідно таблиці, першою була задіяна цифра 0, на її місце помістимо цифру 1. Заповнена таблиця матиме вигляд:

1 0 2 2 1 7 6 7 0 1
1 1 1 1 1 1 6 6 6 6
0 0 0 0 0 0 0 0 1
2 2 2 2 2 2 2 2
7 7 7 7 7

Розмір таблиці може змінюватись від кількості сторінок, фіксованих кадрів та послідовності і кількості звертань.

Джерела[ред. | ред. код]

Загородній А. Г., Партин Г. О. Бухгалтерський облік: Основи теорії та практики: Підручник. — 2-е вид., перероб. і доп. Затверджено МОН. Знання, 2009. 422 с.