Алгоритм заміщення комірок пам'яті FIFO
FIFO (англ. first in, first out) — перший прийшов перший вийшов — є загальний принцип накопичення та обробки завдань (об'єктів). Принцип пов'язаний з поняттям черги: хто перший прийшов — той перший отримав обслуговування. Чергу можна представити у вигляді труби — з однієї сторони щось входить (стає в чергу) з іншої сторони виходить (оброблюється або обслуговується).
Протилежним принципом є LIFO (last in first out) — останній прийшов перший вийшов. Цей принцип пов'язаний із поняттям стек. Стек можна представити також трубою, але тільки з однією відкритою стороною. Можна або щось добавити в стек, або дістати і обробити (обслужити), але це буде той об'єкт, який потратив у стек останнім (наприклад, патрони в ріжку автомата — перший вистрілює той, який був заправлений останнім).
Обидва принципи є інтуїтивно зрозумілими і широко застосовуються у техніці, програмуванні, логістиці, бухгалтерії, математиці (обхід графу) і т. д.
Принцип FIFO використовується при пошуку на графі у ширину. Принцип LIFO — при пошуку у глибину.
Нижче наведений один з прикладів. Інші приклади можна знайти за посиланнями: черга, стек, LIFO.
Нехай процес містить 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 с.
 |