hrybnyak / lab1_os Goto Github PK

Алгоритм відповідає даним в описі лабораторної роботи: Під час ініціалізації аллокатора запитується деяка область пам'яті у ОС. При запиті на виділення блоку пам'яті, в цій області пам'яті шукається вільний блок пам'яті потрібного розміру, позначається як зайнятий і його адреса повертається з додатком. При запиті на звільнення блоку пам'яті, цей блок позначається як вільний. аналогічно реалізується функція зміни розміру блоку. Якщо виділеної області пам'яті недостатньо, то виділяється ще одна область пам'яті. Кожен блок пам'яті складається з заголовка фіксованого розміру і даних. В заголовку вказується розмір поточного блоку, розмір попереднього блоку і ознака зайнятості блоку. Вибирається область пам'яті, яка містить хоча б один вільний блок. Далі в знайденої області пам'яті скануються всі блоки по порядку, і вибирається перший відповідний вільний блок. знайдений блок розділяється на два, один позначається як вільний, а другий позначається як зайнятий і адреса його даних повертається з додатком. Якщо в знайденої області пам'яті не вдалося знайти вільний блок достатнього розміру, то проводиться пошук в іншій області пам'яті. При звільненні блоку виробляється склейка з лівим і правим вільними блоками.

Оцінка часу для вільного блоку: Θ (n) де n поточну кількість блоків в аллокаторе так як пошук лінійний, отже в залежності від стану аллокатора дана оцінка буде сильно мінятися. Оцінка часу для зайнятого блоку: Θ (1) так як для звільнення блоку необхідно лише виставити прапор зайнятості а також провести необхідну дефрагментацію блоків (склейку даного з сусідніми по можливості) Оцінка для збереження системних даних(трата пам’яті): На 64 бітної системі необхідні службові заголовки повинні займати по 12 байт (3 int) і їх буде 2 (отже 24 байта) а так само по 12 байт на кожен новий виділений блок. Переваги: ● простота ● легкість реалізації ● універсальність Недоліки: ● неоптимальна робота для конкретних завдань ● відсутність оптимізацій ● великий обсяг службової інформації