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

FIFO (англ. first in, first out) — перший прийшов перший вийшов — є загальний принцип накопичення та обробки завдань (об'єктів). Принцип пов'язаний з поняттям черги: хто перший прийшов — той перший отримав обслуговування. Чергу можна представити у вигляді труби — з однієї сторони щось входить (стає в чергу) з іншої сторони виходить (оброблюється або обслуговується).

Перший зайшов — перший вийшов

Протилежним принципом є LIFO (last in first out) — останній прийшов перший вийшов. Цей принцип пов'язаний із поняттям стек. Стек можна представити також трубою, але тільки з однією відкритою стороною. Можна або щось добавити в стек, або дістати і обробити (обслужити), але це буде той об'єкт, який потратив у стек останнім (наприклад, патрони в ріжку автомата — перший вистрілює той, який був заправлений останнім).

Обидва принципи є інтуїтивно зрозумілими і широко застосовуються у техніці, програмуванні, логістиці, бухгалтерії, математиці (обхід графу) і т. д.

Принцип FIFO використовується при пошуку на графі у ширину. Принцип LIFO — при пошуку у глибину.

Нижче наведений один з прикладів. Інші приклади можна знайти за посиланнями: черга, стек, LIFO.

Приклад використання стратегії заміщення 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 с.