Центральный процессор передает

Диспетчер пам'яті посилає фізичну адресу в пам'ять

Рис. 3.8. Розташування та призначення диспетчера пам'яті (MMU). Тут диспетчер пам'яті показаний у складі мікросхеми центрального процесора.

Такі згенеровані програмним способом адреси називаються Віртуальними адресами, саме вони і формують віртуальний адресний простір. На комп'ютерах, що не використовують віртуальну пам'ять, віртуальні адреси виставляють безпосередньо на шині пам'яті, що призводить до читання або запису слова фізичної пам'яті з такою ж адресою. При використанні віртуальної пам'яті віртуальні адреси не виставляються безпосередньо на шині пам'яті. Замість цього вони надходять в диспетчер пам'яті (MMU, Memory Management Unit), який відображає віртуальні адреси на адреси фізичної пам'яті, як показано на рис. 3.8.

Дуже простий приклад роботи такого відображення показаний на рис. 3.9. У цьому прикладі у нас є комп'ютер, який генерує 16-розрядні адреси, від 0 і до 64 К. Це віртуальні адреси. Але у цього комп'ютера є тільки 32 Кбайт фізичної пам'яті. І хоча для нього можна написати програми обсягом в 64 Кбайт, цілком завантажити в пам'ять і запустити такі програми не представляється можливим. Але повний дублікат вмісту пам'яті всієї програми, аж до 64 Кбайт, може розміщуватися на диску, дозволяючи вводити її по частинах у міру потреби.

______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

3.2 Таблиці сторінок

Призначення таблиці сторінок полягає ________________________________________________

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

При користуванні результату цієї функції поле віртуальної сторінки у віртуальному адресу можна замінити полем сторінкового блоку, формуючи таким чином адреса фізичної пам'яті.

3.3. Прискорення роботи сторінкової організації пам'яті

У будь-якій системі з сторінкової організацією пам'яті необхідно розглянути два основні питання:

1. Відображення віртуального адреси на фізичний має бути швидким.

2. Якщо простір віртуальних адрес занадто велике, таблиця сторінок буде мати вельми солідний розмір.

Перший пункт є наслідком того, що відображення віртуальної пам'яті на фізичну повинно здійснюватися при кожному зверненні до пам'яті. __________________________________________________

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Другий пункт випливає з факту, що всі сучасні комп'ютери використовують як мінімум 32-розрядні віртуальні адреси, але все більш звичайними становляться 64-розрядні адреси. При розмірі сторінки, скажімо, в 4 Кбайт, 32-разрядні адресний простір має 1 мільйон сторінок, а 64-розрядне адресний простір має набагато більше сторінок, ніж вам може знадобитися. При 1 мільйон сторінок у віртуальному адресному просторі таблиця сторінок повинна містити 1000000 записів. Також слід пам'ятати, що кожному процесу потрібно своя власна таблиця сторінок (оскільки у нього своє власне віртуальне адресний простір).

Лекція 14.

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

При виникненні помилки відсутності сторінки операційна система повинна вибрати «виселяють» (видаляємо з пам'яті) сторінку, щоб звільнити місце для завантажуваної сторінки. Якщо призначена для видалення сторінка за час свого перебування в пам'яті зазнала змін, вона повинна бути переписана на диску, щоб привести дискову копію в актуальний стан. Але якщо сторінка не змінювалася (наприклад, вона містила текст програми), дискова копія не втратила своєї актуальності, і перезапис не потрібно. Тоді прочитується сторінка просто пишеться поверх «виселяють».

Оптимальний алгоритм заміщення сторінок

Оптимальний алгоритм заміщення сторінок свідчить, що повинна бути вилучена сторінка, що має позначку з найбільшим значенням. Якщо якась сторінка не буде використовуватися протягом 8 мільйонів команд, а інша якась сторінка не буде використовуватися протягом 6 мільйонів команд, то видалений першої з них приведе до помилки відсутності сторінки, в результаті якої вона буде знову обрана з диска в самому віддаленому майбутньому.

Єдиною проблемою такого алгоритму є неможливість його реалізації. До того часу, коли станеться помилка відсутності сторінки, у операціонної системи не буде способу дізнатися, коли кожна зі сторінок буде вимагати в наступний раз

Алгоритм виключення недавно використовувалася сторінки

Алгоритм виключення недавно використовувалася сторінки - NRU (Not Recently Used) видаляє довільну сторінку, що відноситься до найнижчого непорожнього класу. У цей алгоритм закладена ідея, суть якої в тому,____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Головна привабливість алгоритму NRU в тому, що порівняно просто реалізувати і добитися від нього продуктивності, яка, звичайно, не оптимальна, але може бути цілком прийнятна.

Алгоритм «першою прийшла, першої і пішла»

Іншим низьковитратних алгоритмом заміщення сторінок є алгоритм FIFO (First-In, First-Out - тобто «першою прийшла, першої і пішла»).

Для алгоритму заміщення сторінок можна скористатися тією ж ідеєю __________________________

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Алгоритм «другий шанс»

Простий модифікацією алгоритму FIFO, що виключає проблему видалення часто запитуваної сторінки, може стати перевірка біта R самої старої сторінки. Якщо його значення дорівнює нулю, значить, сторінка не тільки стара, але і незатребуваний, тому вона тут же віддаляється. Якщо біт R має значення 1, він скидається, а сторінка поміщається в кінець списку сторінок, і час її завантаження оновлюється, як ніби вона щойно надійшла в пам'ять. Потім пошук триває.

Дія цього алгоритму, названого другий шанс, показано на рис. 3.14.

Сторінки з Л по Я містяться у зв'язаному списку відсортованими по часу їх надходження в пам'ять.

Алгоритм «другий шанс» займається _________________________________________________________

______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Лекція 15

Алгоритм «часи»

При всій своїй логічності алгоритм «другий шанс» занадто неефективний, оскільки він постійно переміщує сторінки в своєму списку. Краще містити всі сторінкові блоки в циклічному списку у вигляді годинника, як показано на рис. 3.15. Стрілка вказує на найстарішу сторінку.

При виникненні помилки відсутності сторінки перевіряється та сторінка, на яку вказує стрілка. Якщо її біт R має значення 0, сторінка виселяється, на її місце в «циферблаті» вставляється нова сторінка, і стрілка пересувається вперед на одну позицію. Якщо значення біта R дорівнює 1, то він скидається, і стрілка переміщається на наступну сторінку. Цей процес повторюється до тих пір, поки не буде знайдена сторінка з R = 0.

Алгоритм заміщення найменш затребуваною сторінки

В основі непоганого наближення до оптимального алгоритму лежить спостереження, що сторінки, інтенсивно використовуються декількома останніми командами, будуть, швидше за все, знову затребувані наступними кількома командами. І навпаки, довгий час незатребувані сторінки напевно ще довго так і залишаться незатребуваними. Ця думка наштовхує на цілком здійсненний алгоритм: при виникненні помилки відсутності сторінки потрібно позбутися тієї сторінки, яка тривалий час не була затребувана. Ця стратегія називається заміщенням найменш затребуваною сторінки - LRU (Least Recently Used).

Теоретично реалізувати алгоритм LRU цілком можливо, але його практична реалізація дається нелегко. Для його повної реалізації необхідно вести пов'язаний список всіх сторінок, що знаходяться в пам'яті. На початку цього списку повинна бути тільки що затребувана сторінка, а в кінці - найменш затребувана. Складність в тому, що цей список повинен оновлюватися при кожному зверненні до пам'яті. Для пошуку сторінки в списку, її видалення з нього і подальшого переміщення цієї сторінки вперед потрібно досить багато часу, навіть якщо це буде покладено на апаратне забезпечення (якщо припустити, що таке обладнання можна створити).

Алгоритм «Робочий набір»

_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ Такий підхід називається моделлю робочого набору (Denning, 1970). Він був розроблений для ____________ ______________________________________________________________________________________________ Завантаження сторінок до того, як процесу буде дозволено відновити роботу, називається також випереджаючої підкачкою сторінок (prepaging).

Алгоритм WSC1оск (Самостійно законспектувати)

Коротка порівняльна характеристика алгоритмів заміщення сторінок

Реалізація управління пам'яттю ОС